14-15. Runge-Kutta Methods

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$$

Link to original

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}$$

Link to original

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}$$

Link to original

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)$$

Link to original

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}))$$

Link to original

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}$$

Link to original

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}$$

Link to original

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$$

Link to original

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$$

Link to original

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 }$$

Link to original

Spectral Criterion for Asymptotic Stability

Fixed point ${\mathbf{y}}^{\ast }$ of an autonomous ODE is asymptotically stable if

$$\sigma (\mathbf{Df}({\mathbf{y}}^{\ast }))\subset {\mathbb{C}}^{-}:=\{z\in C:\mathrm{Re}(z)<0\}$$

where $\sigma (\mathbf{Df}({\mathbf{y}}^{\ast }))$ denotes set of eigenvalues of matrix $\mathbf{Df}({\mathbf{y}}^{\ast })$

Link to original

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}$$

Link to original

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)$

Link to original

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$$

Link to original

Runge–Kutta Solution of the Dahlquist Test Equation

Let $\{y_k{\}}_{k\in \mathbb{N}}$ be Runge-Kutta solution to Dahlquist test equation obtained with time step $h>0$
Then

$$y_k=S(zh{)}^k$$

Proof

By direct computation then

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

And

$$y_2=\mathbf{\Psi }(0,y_1,h,z)=\mathbf{\Psi }(0,1,1,zh)y_1=S(zh)y_1=S(zh{)}^2$$

Hence

$$y_k=S(h\lambda {)}^k$$

Link to original

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 }}$

Link to original

A-Stable

Runge Kutta method is A-stable if

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

Link to original

L-Stable

Runge Kutta method is L-stable if

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

Link to original