MATH 417 Lecture 17

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

Review

${\begin{cases}y'(t)=f(t,y(t))\\y(a)=\alpha \end{cases}}$

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

Numerical Methods:

1. Euler's Method:
   • $w_{0}=\alpha$
   • $w_{n+1}=w_{n}+h\,f(t_{h},w_{h})$
   • error is $\left|y(t_{n})-w_{n}\right|\leq C\,h\in O(h)$
   • one-step error is $\underbrace {y_{n+1}} _{\mbox{exact}}-\left(y_{n}+h\,f(t_{n},y_{n})\right)\in O(h^{2})$ (but these errors accumulate).
2. Taylor Series-based Method:
   • $h\,T^{(n)}(t,y)=h\,\left(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 \right)$
   • 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}+h\,f(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'(t)+{\frac {h^{2}}{2}}\,y''(t)+O(h^{3})$

The $T^{(2)}$ method uses $y(t+h)\approx y(t)+h\,f(t,y(t))+{\frac {h^{2}}{2}}\,\left(f_{t}(t,y(t))+f_{y}(t,y(t))\,f(t,y(t))\right)+O(h^{3})$

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

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

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

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

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

${\begin{aligned}y(t+h)&\approx y+h\,f(t-\alpha ,y+\beta \,f(t,y))\\&=y(t)+h\,\left[f(t,y)+\alpha \,f_{t}(t,y)+\beta \,f(t,y)\cdot f_{y}(t,y)+O(\alpha ^{2}+(\beta \,f)^{2}\right]\\&=y(t)+h\,f(t,y(t))+\alpha \,h\,f_{t}+\beta \,h\,f\,f_{y}+h\,O(h^{2}+h^{2}\,f^{2})\\&=T^{(2)}(t,y)\quad \iff \quad \alpha ={\frac {h}{2}};\beta ={\frac {h}{2}}\end{aligned}}$

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

If we let $k_{1}=h\,f(t_{n},w_{n})$, we can write $w_{n+1}=w_{n}+h\,f(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,\ldots$
3. $k_{1}=h\,f(t_{n},w_{n})$
4. $w_{n+1}=w_{n}+h\,f\left(t+{\frac {h}{2}},w_{n}+{\frac {1}{2}}k_{1}\right)$

Modified Euler

Based on trapezoidal rule to approximate $y(t_{n}+h)=y(t_{n})+\int _{t_{n}}^{t_{n}+h}f(t_{n},y(t_{n}))\,\mathrm {d} t$

${\begin{aligned}y(t_{n}+h)&\approx y(t_{n})+{\frac {h}{2}}\,\left(y'(t_{n})+y'(t_{n+1})\right)\\&\approx y(t_{n})+{\frac {h}{2}}\,\left(f(t_{n},y(t_{n}))+f(t_{n}+h,y(t_{n}+h))\right)\end{aligned}}$

Use Euler's method to find $y(t_{n}+h)\approx y(t_{n})+h\,f(t_{n},y(t_{n}))$

${\begin{aligned}y(t_{n}+h)&\approx y(t_{n})+{\frac {h}{2}}\,\left(f(t_{n},y(t_{n}))+f(t_{n}+h,y(t_{n})+h\,f(t_{n},y(t_{n})))\right)\end{aligned}}$

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

${\begin{aligned}w_{n+1}&=w_{n}+{\frac {h}{2}}\,\left(f(t_{n},w_{n})+f(t_{n+1},w_{n}+h\,f(t_{n},w_{n}))\right)\\\end{aligned}}$

Heun's Method

Based on gaussian quadrature method to approximate $y_{n+1}=y_{n}+\int _{t_{n}}^{t_{n}+h}f(t,y(t)\,\mathrm {d} t\approx w_{n}+{\frac {h}{4}}\,f(t_{n},w_{n})+{\frac {3h}{4}}\,f\left(t_{n}+{\frac {2h}{3}},y\left(t_{n}+{\frac {2h}{3}}\right)\right)$

Here's the rule:

• $w_{0}=\alpha$
• $n=0,1,2,\ldots$
• $w_{n+1}=w_{n}+{\frac {h}{4}}\,f(t_{n},w_{n})+{\frac {3h}{4}}\,f\left(t_{n}+{\frac {2h}{3}},w_{n}+{\frac {2h}{3}}\,f(t_{n},w_{n})\right)$

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,\ldots$
• $k_{1}=h\,f(t_{n},w_{n})$
• $k_{2}=h\,f\left(t_{n}+{\frac {h}{2}},w_{n}+{\frac {1}{2}}\,k_{1}\right)$
• $k_{3}=h\,f\left(t_{n}+{\frac {h}{2}},w_{n}+{\frac {1}{2}}\,k_{2}\right)$
• $k_{4}=h\,f\left(t_{n}+h,w_{n}+k_{3}\right)$
• $w_{n+1}=w_{n}+{\frac {1}{6}}\,\left(k_{1}+2k_{2}+2k_{3}+k_{4}\right)$

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 $\ldots ,(t_{n-1},w_{n-1});(t_{n},w_{n})$.

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

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

Examples

No Solution Example

${\begin{cases}y'(t)=(y(t))^{2}\\y(0)=1\end{cases}}$

• $f(t,y)=y^{2}$, which is continuous
• $\left|{\frac {\partial f}{\partial y}}\right|=\left|2y\right|\not <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{cases}y'(t)=y(t)+t\\y(0)=1\end{cases}}$

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

For $0\leq t\leq 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}+h\,f(t_{0},w_{0})=1+{\frac {1}{2}}\,f(0,1)={\frac {3}{2}}$
• $w_{2}=w_{1}+h\,f(t_{1},w_{1})={\frac {3}{2}}+{\frac {1}{2}}\,f\left({\frac {1}{2}},{\frac {3}{2}}\right)={\frac {5}{2}}$

Midpoint

$w_{n+1}=w_{n}+{\frac {h}{2}}\,f\left(t_{n}+{\frac {h}{2}},w_{n}+{\frac {h}{2}}\,f(t_{n},w_{n})\right)$

Something's wrong here...

• $w_{0}=1$
• $w_{1}=1+{\frac {1}{2}}\,f\left({\frac {1}{4}},1+{\frac {1}{4}}\,f(0,1)\right)=1+{\frac {3}{8}}={\frac {11}{8}}$
• $w_{2}={\frac {11}{8}}+{\frac {1}{2}}\,f\left({\frac {3}{4}}+{\frac {11}{8}},1+{\frac {1}{4}}\,f\left({\frac {1}{2}},{\frac {11}{8}}\right)\right)=\ldots$

Modified Euler

$w_{n+1}=w_{n}+{\frac {h}{2}}\,\left(f(t_{n},w_{n})+f(t_{n}+h,w_{n}+h\,f(t_{n},w_{n}))\right)$

$k_{1}=h\,f(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}}\,\left(f(0,1)+f\left({\frac {1}{2}},1+{\frac {1}{2}}\,f(0,1)\right)\right)={\frac {7}{4}}$
• ${\frac {7}{4}}+{\frac {1}{4}}\,\left(f\left({\frac {1}{2}},{\frac {7}{4}}\right)+f\left(1,{\frac {7}{4}}+{\frac {1}{2}}\,f\left({\frac {1}{2}},{\frac {7}{4}}\right)\right)\right)=\ldots$