MATH566 Lesson 24: Numerical ODE - IVP

Overview

• Runge-Kutta methods

• Analysis of linear multistep methods

• Boundary locus method

Runge-Kutta methods

• An ODE is an equality between two operators $D=\frac{d}{dt},F=f(t,.)$ acting on $y$

  ${\displaystyle \frac{d}{dt}y=f(t,y)}$

• Numerical methods have been introduced to approximate:

  • $D=\frac{d}{dt}$ (Euler, leapfrog)

  • $f$, after integration over a time step $[t_i,t_{i+1}]$, $h=t_{i+1}-t_i$, Adams methods

• Yet another alternative technique to obtain a numerical method is to seek a weighted average of the slopes over a time step

  ${\displaystyle y_{i+1}=y_i+\sum _{j=1}^s{w}_j{k}_j}$ ${\displaystyle k_j=hf(t_i+{\alpha }_{j}h,y_i+\sum _{l=1}^{j-1}{\beta }_{jl}{k}_l)}$

• The parameters $w_j$ (weights), and ${\alpha }_j,{\beta }_{jl}$ (evaluation points) are found by Taylor series expansions

Runge-Kutta method example RK4

• A very widely used method is RK4

  ${\displaystyle y_{i+1}=y_i+\frac{1}{6}(k_1+2k_2+2k_3+k_4)}$ ${\displaystyle k_1=hf(t_i,y_i)}$ ${\displaystyle k_2=hf(t_i+h/2,y_i+k_1/2)}$ ${\displaystyle k_3=hf(t_i+h/2,y_i+k_2/2)}$ ${\displaystyle k_4=hf(t_i+h,y_i+k_3)}$

• As suggested by the name, RK4 is fourth order of accuracy over a finite interval $[0,T]$ $\epsilon =𝒪\left(h^4\right)$, and has a one-step error of fifth order $\tau =𝒪\left(h^5\right)$

Analysis of Adams-Bashforth, Adams-Moulton

• A-B, A-M schemes are examples of linear multistep methods (LMMs)

• Applied to $y^{\text{'}}=\lambda y$ an LMM leads to

  ${\displaystyle \sum _{k=0}^s{a}_k{y}_{i+k}=z\sum _{k=0}^s{b}_k{y}_{i+k},z=\lambda h}$

• The above is a finite difference equation. Guess solutions of form $y_n=r^n$, and obtain a characteristic equation of form

  ${\displaystyle \pi (r;z)=\rho \left(r\right)-z\sigma \left(r\right)=0}$

  with $\rho \left(r\right),\sigma \left(r\right)$ the polynomials

  ${\displaystyle \rho \left(r\right)=\sum _{k=0}^s{a}_k{r}^k,\sigma \left(r\right)=\sum _{k=0}^s{b}_k{r}^k.}$

• Consistency requires $\rho \left(1\right)=0,{\rho }^{\text{'}}\left(1\right)-\sigma \left(1\right)=0.$

• Stability requires roots $r_i$ of $\pi (r;z)$ to satisfy $\left|r_i\right|<1$.

Boundary locus method

• An LMM method is stable if the roots of $\pi (r;z)=\rho \left(r\right)-z\sigma \left(r\right)$ are less than 1

• Consider the limitng case in which a root is of magnitude 1

• Roots can be complex, write $\zeta =e^{i\theta }$, $\pi (e^{i\theta };z)=\rho \left(e^{i\theta }\right)-z\sigma \left(e^{i\theta }\right)=0\Rightarrow$

  ${\displaystyle z\left(\theta \right)=\frac{\rho \left(e^{i\theta }\right)}{\sigma \left(e^{i\theta }\right)}}$

• As $\theta \in [0,2\pi ]$ a locus of marginally stable $z=\lambda h$ values is graphed in $ℂ$

Figure 1. Boundary loci of various methods