MATH 417 Lecture 17

« previous | Tuesday, March 25, 2014 | next »

Review

$\{\begin{array}{l}{y}^{\prime }(t)=f(t,y(t))\\ y(a)=\alpha \end{array}$

For $t\in [a,b]$.

Numerical Methods:

1. Euler's Method:
   • $w_0=\alpha$
   • $w_{n+1}=w_n+hf(t_h,w_h)$
   • error is $|y(t_n)-w_n|\le Ch\in O(h)$
   • one-step error is $\underset{\text{exact}}{\underbrace{y_{n+1}}}-(y_n+hf(t_n,y_n))\in O(h^2)$ (but these errors accumulate).
2. Taylor Series-based Method:
   • $h{T}^{(n)}(t,y)=h(f(t,y)+\frac{h}{2}\cdot \frac{\mathrm{d}f(t,y(t)}{\mathrm{d}t}+\frac{h^2}{3!}\cdot \frac{{\mathrm{d}}^{2}f(t,y(t))}{\mathrm{d}{t}^2}+\dots )$
   • Need to know partial derivatives
   • $T^{(n)}$ local error = $h^{n+1}$, and global error is $h^n$
   • Euler's method is $T^{(1)}$.

Runge-Kutta Method

Replaces derivatives with nested function evaluations.

$w_{n+1}=w_n+hf(t_n+\alpha ,w_n+\beta f(t_n,w_n))=$

We want $w_{n+1}=\dots =y_{n+1}+O(h^3)$

$y(t+h)=y(t)+h{y}^{\prime }(t)+\frac{h^2}{2}{y}^{″}(t)+O(h^3)$

The $T^{(2)}$ method uses $y(t+h)\approx y(t)+hf(t,y(t))+\frac{h^2}{2}(f_t(t,y(t))+f_y(t,y(t))f(t,y(t)))+O(h^3)$

Second order Runge-Kutta method (RK-2) uses $y(t+h)\approx y+hf(t+\alpha ,y+\beta f(t,y))+O(h^3)$

Hence $y(t)+hf(t,y(t))+\frac{h^2}{2}(f_t(t,y(t))+f_y(t,y(t))f(t,y(t)))=y(t+h)+hf(t+\alpha ,y(t)+\beta f(t,y(t)))$ up to $O(h^3)$ difference.

Taylor Series for $f(t,y)$:

$f(t+\mathrm{\Delta }t,y+\mathrm{\Delta }y)=f(t,y)+\mathrm{\Delta }t{f}_t(t,y)+\mathrm{\Delta }y{f}_y(t,y)+\frac{1}{2!}(\mathrm{\Delta }{t}^2{f}_{tt}(t,y)+2\mathrm{\Delta }t\mathrm{\Delta }y{f}_{ty}(t,y)+\mathrm{\Delta }{y}^2{f}_{yy}(t,y))+\dots +\frac{1}{n!}(\sum _{k=0}^n{\left(\mathrm{\Delta }t\right)}^{h-k}{\left(\mathrm{\Delta }y\right)}^k(\genfrac{}{}{0ex}{}{n}{k})\frac{{\partial }^{n-k}}{\partial t^{n-k}}\frac{{\partial }^k}{\partial y^k}f(t,y))+O({\left|\mathrm{\Delta }t\right|}^{n+1}+{\left|\mathrm{\Delta }y\right|}^{n+1})$

RK-2: $y(t+h)\approx y+hf(t-\alpha ,y+\beta f(t,y))$, where $\alpha ,\beta \in O(h)$

$\begin{array}{rl}y(t+h)& \approx y+hf(t-\alpha ,y+\beta f(t,y))\\ & =y(t)+h[f(t,y)+\alpha f_t(t,y)+\beta f(t,y)\cdot f_y(t,y)+O({\alpha }^2+(\beta f{)}^2]\\ & =y(t)+hf(t,y(t))+\alpha h{f}_t+\beta hf{f}_y+hO(h^2+h^2{f}^2)\\ & =T^{(2)}(t,y)⟺\alpha =\frac{h}{2};\beta =\frac{h}{2}\end{array}$

Hence RK-2 is the midpoint method: $w_{n+1}=w_n+hf(t_n+\frac{h}{2},w_n+\frac{h}{2}f(t_n,w_n))$

If we let $k_1=hf(t_n,w_n)$, we can write $w_{n+1}=w_n+hf(t_n+\frac{h}{2},w_n+\frac{1}{2}{k}_1$

Here comes the rule:

1. $w_0=\alpha$
2. $n=0,1,2,\dots$
3. $k_1=hf(t_n,w_n)$
4. $w_{n+1}=w_n+hf(t+\frac{h}{2},w_n+\frac{1}{2}{k}_1)$

Modified Euler

Based on trapezoidal rule to approximate $y(t_n+h)=y(t_n)+\underset{t_n}{\overset{t_n+h}{\int }}f(t_n,y(t_n))\mathrm{d}t$

$\begin{array}{rl}y(t_n+h)& \approx y(t_n)+\frac{h}{2}(y^{\prime }(t_n)+y^{\prime }(t_{n+1}))\\ & \approx y(t_n)+\frac{h}{2}(f(t_n,y(t_n))+f(t_n+h,y(t_n+h)))\end{array}$

Use Euler's method to find $y(t_n+h)\approx y(t_n)+hf(t_n,y(t_n))$

$\begin{array}{rl}y(t_n+h)& \approx y(t_n)+\frac{h}{2}(f(t_n,y(t_n))+f(t_n+h,y(t_n)+hf(t_n,y(t_n))))\end{array}$

To find our numeric method, let $w_n=y(t_n)$ and $w_{n+1}=y(t_n+h)$, then

$\begin{array}{rl}{w}_{n+1}& =w_n+\frac{h}{2}(f(t_n,w_n)+f(t_{n+1},w_n+hf(t_n,w_n)))\\ \end{array}$

Heun's Method

Based on gaussian quadrature method to approximate $y_{n+1}=y_n+\underset{t_n}{\overset{t_n+h}{\int }}f(t,y(t)\mathrm{d}t\approx w_n+\frac{h}{4}f(t_n,w_n)+\frac{3h}{4}f(t_n+\frac{2h}{3},y(t_n+\frac{2h}{3}))$

Here's the rule:

• $w_0=\alpha$
• $n=0,1,2,\dots$
• $w_{n+1}=w_n+\frac{h}{4}f(t_n,w_n)+\frac{3h}{4}f(t_n+\frac{2h}{3},w_n+\frac{2h}{3}f(t_n,w_n))$

The book has an error by saying this is $O(h^3)$. It is RK-2, so it must be $O(h^2)$.

RK-4

• $w_0=\alpha$
• $n=0,1,2,\dots$
• $k_1=hf(t_n,w_n)$
• $k_2=hf(t_n+\frac{h}{2},w_n+\frac{1}{2}{k}_1)$
• $k_3=hf(t_n+\frac{h}{2},w_n+\frac{1}{2}{k}_2)$
• $k_4=hf(t_n+h,w_n+k_3)$
• $w_{n+1}=w_n+\frac{1}{6}(k_1+2k_2+2k_3+k_4)$

Multi-Step Method

All methods we've discussed so far are 'one step methods: we only use $w_n$ to approximate $w_{n+1}$.

Assume that you have computed $\dots ,(t_{n-1},w_{n-1});(t_n,w_n)$.

$w_{n+1}=w_n+\frac{h}{720}(1901f(t_n,w_n)-2774f(t_{n-1},w_{n-1})+2616f(t_{n-2},w_{n-2})-1274f(t_{n-3},w_{n-3})+251f(t_{n-4},w_{n-4}))$

This is an order 5 method, but it has oscillating coefficients (so it is numerically unstable)

Examples

No Solution Example

$\{\begin{array}{l}{y}^{\prime }(t)=(y(t){)}^2\\ y(0)=1\end{array}$

• $f(t,y)=y^2$, which is continuous
• $\left|\frac{\partial f}{\partial y}\right|=\left|2y\right|<C$

Exact solution is $y(t)=\frac{1}{1-t}$, the reason the lipschitz discontinuity is because there is a singularity at $t=1$

Example 2

$\{\begin{array}{l}{y}^{\prime }(t)=y(t)+t\\ y(0)=1\end{array}$

• $f(t,y)=y+t$ (continuous)
• $\left|\frac{\partial f}{\partial y}\right|=1$, so Lipschitz continuous

For $0\le t\le 1$ and $h=0.5$, let's find Euler, Midpoint, and Modified Euler approximations:

Euler

$t_0=0$, $t_1=\frac{1}{2}$, and $t_2=1$.

• $w_0=1$
• $w_1=w_0+hf(t_0,w_0)=1+\frac{1}{2}f(0,1)=\frac{3}{2}$
• $w_2=w_1+hf(t_1,w_1)=\frac{3}{2}+\frac{1}{2}f(\frac{1}{2},\frac{3}{2})=\frac{5}{2}$

Midpoint

$w_{n+1}=w_n+\frac{h}{2}f(t_n+\frac{h}{2},w_n+\frac{h}{2}f(t_n,w_n))$

Something's wrong here...

• $w_0=1$
• $w_1=1+\frac{1}{2}f(\frac{1}{4},1+\frac{1}{4}f(0,1))=1+\frac{3}{8}=\frac{11}{8}$
• $w_2=\frac{11}{8}+\frac{1}{2}f(\frac{3}{4}+\frac{11}{8},1+\frac{1}{4}f(\frac{1}{2},\frac{11}{8}))=\dots$

Modified Euler

$w_{n+1}=w_n+\frac{h}{2}(f(t_n,w_n)+f(t_n+h,w_n+hf(t_n,w_n)))$

$k_1=hf(t_n,w_n)$ simplifies the above to $w_n+\frac{1}{2}{k}_1+\frac{h}{2}f(t_n+k_1,w_n+k_1)$

• $w_0=1$
• $w_1=1+\frac{1}{4}(f(0,1)+f(\frac{1}{2},1+\frac{1}{2}f(0,1)))=\frac{7}{4}$
• $\frac{7}{4}+\frac{1}{4}(f(\frac{1}{2},\frac{7}{4})+f(1,\frac{7}{4}+\frac{1}{2}f(\frac{1}{2},\frac{7}{4})))=\dots$