08 - Numerical Methods for ODEs

First-Order ODE

Let $I=[x_0,X]\subset \mathbb{R}$ be a time interval
Let $D\subset {\mathbb{R}}^d$ be an open subset where $d\in {\mathbb{N}}^{+}$ denote space dimension

First Order Differential Equation (ODE) is an equation in form

$${\mathbf{y}}^{\prime }(x)=\mathbf{f}(x,\mathbf{y})$$

where $\mathbf{f}:I\times D\to {\mathbb{R}}^d$

Initial Value Problem

Let $I=[x_0,X]\subset \mathbb{R}$ be a time interval
Let $D\subset {\mathbb{R}}^d$ be an open subset where $d\in {\mathbb{N}}^{+}$ denote space dimension

Initial Value Problem (IVP) is an ODE with initial condition with

$${\mathbf{y}}^{\prime }(x)=\mathbf{f}(x,\mathbf{y}),\mathbf{y}(x_0)={\mathbf{y}}_0$$

Discretisation of an IVP

Dividing $[x_0,X]$ into $N\in {\mathbb{N}}^{+}$ subintervals defined by equidistance points

$$x_n=x_0+nh,n=0,\cdots ,N$$

where step size $h$ is defined by

$$h=\frac{X-x_0}{N}$$

with for each step $x_n$ then associate approximation

$${\mathbf{y}}_n\approx \mathbf{y}(x_n)$$

Explicit Euler Method

$${\mathbf{y}}_{n+1}={\mathbf{y}}_n+h\mathbf{f}(x_n,{\mathbf{y}}_n)$$

Implicit Euler Method

$${\mathbf{y}}_{n+1}={\mathbf{y}}_n+h\mathbf{f}(x_{n+1},{\mathbf{y}}_{n+1})$$

Implicit Midpoint Method

$${\mathbf{y}}_{n+1}={\mathbf{y}}_n+h\mathbf{f}\left(x_n+\frac{h}{2},\frac{{\mathbf{y}}_n+{\mathbf{y}}_{n+1}}{2}\right)$$

One-Step Method

One-step method is function $\Psi$ which takes
Triplet $(s,\mathbf{y},h)\subset \mathbb{R}\times {\mathbb{R}}^d\times \mathbb{R}$ and function $\mathbf{f}$ to compute approximation

$$\mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f})\text{ of }\mathbf{y}(s+h)$$

which is solution at $s+h$ of

$${\mathbf{y}}^{\prime }(x)=\mathbf{f}(x,\mathbf{y}),\mathbf{y}(s)=\mathbf{y}$$

Consistent One-Step Method

One-Step Method $\Psi$ is consistent if

$$\mathbf{\Psi }(s,\mathbf{y},0,\mathbf{f})=\mathbf{y}$$

and

$$\frac{d}{dh}\mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f}){\mid }_{h=0}=\mathbf{f}(s,\mathbf{y})$$

Consistency Error

Consistency error (aka local truncation error) $\tau$ is defined as

$$\begin{array}{rl}\tau (s,\mathbf{y},h,\mathbf{f})& :=\frac{\mathbf{y}(s+h)-\mathbf{y}}{h}-\frac{\mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f})-\mathbf{y}}{h}\\ & =\frac{\mathbf{y}(s+h)-\mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f})}{h}\end{array}$$

where $\mathbf{y}(s+h)$ is the solution at $s+h$ of IVP

Characterisation of Consistency lemma

Assume $h\mapsto \mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f})$ is continuously differentiable in neighbourhood of $0$ then

$\mathbf{\Psi }$ is consistent if and only if for any fixed $\mathbf{f}$

$$||\tau (\tilde{s},\tilde{\mathbf{y}},h,\mathbf{f})||\to 0\text{ as }h\to 0$$

locally uniformly in $(\tilde{s},\tilde{\mathbf{y}})\in R$ where $R$ is the cylinder from Picard’s Theorem

Increment Function Form of Consistency lemma

Assume $h\mapsto \mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f})$ is continuously differentiable in neighbourhood of $0$ then

$\mathbf{\Psi }$ is consistent if and only if there is continuous incremenent function

$$h\mapsto \psi (s,\mathbf{y},h,\mathbf{f})$$

such that

$$\mathbf{\Psi }(s,\mathbf{y},h,\mathbf{f})=\mathbf{y}+h\psi (s,\mathbf{y},h,\mathbf{f}),\psi (s,\mathbf{y},0,\mathbf{f})=\mathbf{f}(s,\mathbf{y})$$

Global Error

Global Error is defined by

$$e_n:=\mathbf{y}(x_n)-{\mathbf{y}}_n$$

Runge-Kutta Methods

Family of $s-$stage Runge-Kutta methods are defined by

$$\mathbf{\Psi }(x,\mathbf{y},h,\mathbf{f})=\mathbf{y}+h\sum _{i=1}^s{b}_i{\mathbf{k}}_i$$

where stages ${\mathbf{k}}_i$ are solutions of coupled system of equations

$${\mathbf{k}}_i:=\mathbf{f}\left(x+c_{i}h,\mathbf{y}+h\sum _{j=1}^s{a}_{ij}{\mathbf{k}}_j\right),i=1,\cdots ,s$$

with coefficients $\{c_i{\}}_{i=1}^s$ given by

$$c_i:=\sum _{j=1}^s{a}_{ij},i=1,\cdots ,s$$

Butcher Tableau

Coefficients of a Runge-Kutta method are commonly summarised in a Butcher Tableu as

$$\begin{array}{cc}\mathbf{c}& A\\ & {\mathbf{b}}^{\top }\end{array}$$

Explicit Euler Method

$$\begin{array}{cc}0& 0\\ & 1\end{array}$$

Implicit Euler Method

$$\begin{array}{cc}1& 1\\ & 1\end{array}$$

Implicit Midpoint Rule

$$\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ & 1\end{array}$$

Two-Stage Explicit Runge-Kutta Methods

Runge-Kutta Methods in form

$$y_{n+1}=y_n+h(b_1{k}_1+b_2{k}_2)$$

where

$$\begin{array}{rl}{k}_1& =f(x_n,y_n)\\ k_2& =f(x_n+c_{2}h,y_n+a_{21}h{k}_1)\end{array}$$

Modified Euler Method

Runge-Kutta Methods in form

$${\mathbf{y}}_{n+1}={\mathbf{y}}_n+hf\left(x_n+\frac{1}{2}h,{\mathbf{y}}_n+\frac{1}{2}hf(x_n,{\mathbf{y}}_n)\right)$$

and

$$\mathbf{\Psi }(x,\mathbf{y},h,f)=x+hf\left(x+\frac{1}{2}h,\mathbf{y}+\frac{h}{2}f(x,\mathbf{y})\right)$$

Improved Euler Method

Runge-Kutta Methods in form

$${\mathbf{y}}_{n+1}={\mathbf{y}}_n+\frac{1}{2}h[f(x_n,{\mathbf{y}}_n)+f(x_n+h,{\mathbf{y}}_n+hf(x_n,{\mathbf{y}}_n))]$$

and

$$\mathbf{\Psi }(x,\mathbf{y},h,\mathbf{f})=\mathbf{y}+\frac{1}{2}h\mathbf{f}(x,\mathbf{y})+\frac{1}{2}h\mathbf{f}(x+h,\mathbf{y}+h\mathbf{f}(x,\mathbf{y}))$$

Four-Stage Four-Order Explicit Runge Kutta Methods

Runge-Kutta Methods in form

$$\mathbf{\Psi }(x,\mathbf{y},h,\mathbf{f})=\mathbf{y}+\frac{1}{6}h({\mathbf{k}}_1+2{\mathbf{k}}_2+2{\mathbf{k}}_3+{\mathbf{k}}_4)$$

where

$$\begin{array}{rl}{\mathbf{k}}_1& =f(x,\mathbf{y})\\ {\mathbf{k}}_2& =f\left(x+\frac{1}{2}h,\mathbf{y}+\frac{1}{2}h{\mathbf{k}}_1\right)\\ {\mathbf{k}}_3& =f\left(x+\frac{1}{2}h,\mathbf{y}+\frac{1}{2}h{\mathbf{k}}_2\right)\\ k_4& =f(x+h,\mathbf{y}+h{\mathbf{k}}_3)\end{array}$$

with Butcher Table

$$\begin{array}{ccccc}0& 0& 0& 0& 0\\ \frac{1}{2}& \frac{1}{2}& 0& 0& 0\\ \frac{1}{2}& 0& \frac{1}{2}& 0& 0\\ 1& 0& 0& 1& 0\\ & \frac{1}{6}& \frac{2}{6}& \frac{1}{3}& \frac{1}{6}\end{array}$$

Consistent Runge-Kutta Method lemma

Runge-Kutta Method is consistent if and only if

$$\sum _{i=1}^s{b}_i=1$$

Consistency Order 2

Runge-Kutta Method has consistency order 2 if

$$\sum _{i=1}^s{b}_i{c}_i=\frac{1}{2}$$

Consistency Order 3

Runge-Kutta Method has consistency order 3 if

$$\sum _{i=1}^s{b}_i{c}_i^2=\frac{1}{2}\text{ and }\sum _{i=1}^s{b}_i\sum _{j=1}^s{a}_{ij}{c}_j=\frac{1}{6}$$

Order Bound for Runge–Kutta Method lemma

Consistency Order $p$ of an $s$-stage Runge-Kutta method is bounded by

$$p\le 2s$$

If Runge-Kutta method is explicit then

$$p\le s$$

Fixed Point

Fixed point of ${\mathbf{y}}^{\prime }=\mathbf{f}(\mathbf{y})$ is point ${\mathbf{y}}^{\ast }$ such that

$$\mathbf{f}({\mathbf{y}}^{\ast })=0$$

Asymptotically Stable

Fixed Point ${\mathbf{y}}^{\ast }$ is asymptotically stable if

Exists ball $B_{\delta }({\mathbf{y}}^{\ast })$ such that
whenever ${\mathbf{y}}_0\in B_{\delta }({\mathbf{y}}^{\ast })$ then solution to

$${\mathbf{y}}^{\prime }=\mathbf{f}(\mathbf{y}),\mathbf{y}(0)={\mathbf{y}}_0\text{ satisfies }\underset{x\to \infty }{\lim }\mathbf{y}(x)={\mathbf{y}}^{\ast }$$

Dahlquist Test Equation

Dahlquist Test Equation is defined by

$$y^{\prime }=zy,y(0)=1,\mathrm{Re}z<0$$

With solution

$$y(x)=\exp (zx)$$

So

$$\underset{x\to \infty }{\lim }y(x)=0\text{ and }{y}^{\ast }=0\text{ is an attractive fixed point}$$

Stability Function

Let $\mathbf{\Psi }$ be a Runge-Kutta method then

Stability Function of $\mathbf{\Psi }$ is defined as

$$S:\mathbb{C}\to \mathbb{C},z\mapsto S(z):=\mathbf{\Psi }(0,1,1,f:y\mapsto zy)$$

Note that it also written as $\mathbf{\Psi }(0,1,1,z)$ instead of $\mathbf{\Psi }(0,1,1,f:y\mapsto zy)$

Scaling Property of Runge–Kutta Methods

Let $\mathbf{\Psi }$ be a Runge-Kutta method then

$$\mathbf{\Psi }(0,\ell ,h,z)=\mathbf{\Psi }(0,1,1,zh)\ell$$

Stability Region

Stability Region of Runge-Kutta Method is defined by

$$S_{\mathbf{\Psi }}:=\{z\in \mathbb{C}:|S(z)|<1\}$$

So $\{y_k{\}}_{k\in \mathbb{N}}$ is asymptotically stable if $zh\in S_{\mathbf{\Psi }}$

A-Stable

Runge Kutta method is A-stable if

$${\mathbb{C}}^{-}\subset S_{\mathbf{\Psi }}$$

L-Stable

Runge Kutta method is L-stable if

$$\text{A-stable}\text{ and }\underset{\mathrm{Re}z\to -\infty }{\lim }|S(z)|=0$$