Notes - Numerical Analysis HT24, Runge-Kutta methods


Flashcards

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

Can you define what it means for a one-step method $\pmb \Psi(s, \pmb y, h, \pmb f)$ to be an $s$-stage Runge-Kutta method, and define the corresponding Butcher tableau?


\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

The corresponding Butcher tableau is

c |  A
--|-----
  | b^T

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have the approximations

  • Explicit Euler’s method: $\pmb y _ {n + 1} = \pmb y _ n + h f(x _ n, \pmb y _ n)$
  • Implicit Euler’s method: $\pmb y _ {n + 1} = \pmb y _ n + hf(x _ n, \pmb y _ {n+1})$
  • Implicit midpoint rule: $\pmb y _ {n + 1} = \pmb y _ n + hf\left(x _ n + h/2, (\pmb y _ {n+1} + \pmb y _ n)/2 \right)$

Can you give the Butcher tableau for each?


Each has the structure

c |  A
--|-----
  | b^T
  • Explicit Euler’s method:
0 | 0
--|---
  | 1
  • Implicit Euler’s method:
1 | 1
--|---
  | 1
  • Implicit midpoint rule:
1/2 | 1/2
----|-----
    |  1

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

and use the 4th order explicit Runge-Kutta method given by

\[\pmb y_{n+1} = \pmb y_n + \frac h 6(\pmb k_1 + 2\pmb k_2 + 2\pmb k_3 + \pmb k_4)\]

where

\[\begin{aligned} \pmb k_1 &= \pmb f(x, \pmb y_n) \\\\ \pmb k_2 &= \pmb f\left(x + \frac 1 2 h, \pmb y_{n} + \frac 1 2 h\pmb k_1\right) \\\\ \pmb k_3 &= \pmb f\left(x + \frac 1 2h, \pmb y_n + \frac 1 2 h \pmb k_2\right) \\\\ \pmb k_4 &= \pmb f(x + h, \pmb y + h \pmb k_3) \end{aligned}\]

Can you give the corresponding Butcher tableau?


  0  |  0    0    0    0  
 1/2 | 1/2   0    0    0  
 1/2 |  0   1/2   0    0  
  1  |  0    0    1    0  
-----|---------------------
     | 1/6  2/6  2/6  1/6

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

Can you state necessary and sufficient conditions for the method to be consistent?


\[\sum^s_{i = 1} b_i = 1\]

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

Can you state a theorem that gives bounds on the consistency order of such an approximation?


The order $p$ is bounded by $p \le 2s$ where $s$ is the number of stages. If the method is explicit, then $p \le s$.

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

It’s convenient to summarise this in a Butcher tableau:

c |  A
--|-----
  | b^T

Given this, how does $A$ change when the method is explicit, diagonally-implicit and implicit?


  • Explicit: $A$ is strictly lower triangular (hence the system is easy to solve)
  • Diagonally-implicit: $A$ is lower triangular (hence the system can be solved by considering a sequence of simpler nonlinear problems)
  • Implicit: No restrictions on $A$, finding $\pmb k$ will probably be difficult

Suppose we have the autonomous IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(\pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

What does it mean for a point $\pmb y^\star$ to be a fixed point?


\[\pmb f(\pmb y^\star) = \pmb 0\]

Suppose we have the autonomous IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(\pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

What does it mean for a fixed point $\pmb y^\star$ to be asymptotically stable (or attractive)?


$\exists \delta > 0$ such that whenever $\pmb y _ 0 \in B(\pmb y^\star, \delta)$, the solution $\pmb y(x)$ satisfies

\[\lim_{x \to \infty} \pmb y(x) = \pmb y^\star\]

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(\pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

Recall the definition that a fixed point $\pmb y^\star$ is asymptotically stable (or attractive) if $\exists \delta > 0$ such that whenever $\pmb y _ 0 \in B(\pmb y^\star, \delta)$, the solution $\pmb y(x)$ satisfies

\[\lim_{x \to \infty} \pmb y(x) = \pmb y^\star\]

Can you state a theorem that gives a sufficient condition for when an autonomous ODE is asymptotically stable?


\[\lambda(\mathbf D\pmb f(\pmb y^\star)) \subseteq \mathbb C^- := \\{z \in \mathbb C \mid \Re(z) < 0\\}\]

where $\lambda(\cdot)$ denotes the set of eigenvalues of the corresponding matrix.

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(\pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

Recall the definition that a fixed point $\pmb y^\star$ is asymptotically stable (or attractive) if $\exists \delta > 0$ such that whenever $\pmb y _ 0 \in B(\pmb y^\star, \delta)$, the solution $\pmb y(x)$ satisfies

\[\lim_{x \to \infty} \pmb y(x) = \pmb y^\star\]

We have a theorem that states $\pmb y^\star$ will be asymptotically stable if

\[\lambda(\mathbf D\pmb f(\pmb y^\star)) \subseteq \mathbb C^- := \\{z \in \mathbb C \mid \Re(z) < 0\\}\]

where $\lambda(\cdot)$ denotes the set of eigenvalues of the corresponding matrix. This actually makes our life much easier, because we can instead analyse the linear problem

\[\pmb y' = \mathbf D \pmb f(\pmb y^\star) (\pmb y - \pmb y^\star)\]

(Why? Not really sure… it’s sort of like approximating $\pmb y’$ with a first-order Taylor expansion. I wish I had taken a DEs course before this one). Considering just one dimensional problems, and applying the eigenvalue condition above, and changing coordinates to get rid of $\pmb y^\star$, we get the Dahlquist test equation:

\[y' = zy, \quad y(0) = 1, \quad \Re(z) < 0\]

We know that this has an attractive fixed point since $\lim _ {x \to \infty} y(x) = 0$. How we can use this as a metric to evaluate how good a one-step method for solving IVPs is?


Such methods compute a list of $\{y _ k\}$ which approximate $\pmb y(\pmb x + kh)$. It would be nice if the method also respected $y _ k \to 0$ as $k \to \infty$ (and in a way, this doesn’t just show that the algorithm does well on the Dahlquist test equation, but because of the analysis above it actually should perform well on a big class of problems).

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(\pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

Recall the definition that a fixed point $\pmb y^\star$ is asymptotically stable (or attractive) if $\exists \delta > 0$ such that whenever $\pmb y _ 0 \in B(\pmb y^\star, \delta)$, the solution $\pmb y(x)$ satisfies

\[\lim_{x \to \infty} \pmb y(x) = \pmb y^\star\]

We have a theorem that states $\pmb y^\star$ will be asymptotically stable if

\[\lambda(\mathbf D\pmb f(\pmb y^\star)) \subseteq \mathbb C^- := \\{z \in \mathbb C \mid \Re(z) < 0\\}\]

where $\lambda(\cdot)$ denotes the set of eigenvalues of the corresponding matrix. This actually makes our life much easier, because we can instead analyse the linear problem

\[\pmb y' = \mathbf D \pmb f(\pmb y^\star) (\pmb y - \pmb y^\star)\]

(Why? Not really sure… it’s sort of like approximating $\pmb y’$ with a first-order Taylor expansion. I wish I had taken a DEs course before this one). Considering just one dimensional problems, and applying the eigenvalue condition above, and changing coordinates to get rid of $\pmb y^\star$, we get the Dahlquist test equation. Can you state this?


\[y' = zy, \quad y(0) = 1, \quad \Re(z) < 0\]

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

Can you define the corresponding stability function $S$, and given that the Runge-Kutta solution $\{y _ k\}$ to the Dahlquist test equation with time step $h > 0$ satisfies $y _ k = S(zh)^k$, can you define the stability region $S _ {\pmb \Psi}$?


\[S : \mathbb C \to \mathbb C\]

given by

\[S(z) := \pmb \Psi(0, 1, 1, f : y \to zy)\]

The stability region is

\[S_{\pmb \Psi} := \\{z \in \mathbb C : |S(z)| < 1 \\}\]

(i.e. the region where the solution doesn’t blow up).

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

The corresponding “stability function” is defined by

\[S : \mathbb C \to \mathbb C, \quad S(z) := \pmb \Psi(0, 1, 1, f : y \to zy)\]

Quickly prove that if $\{y _ k\}$ is the corresponding solution to the Dahlquist test equation ($y’ = zy, y(0) = 1, \Re(z) < 0$), then $y _ k = S(zh)^k$.


We have

\[\begin{aligned} y_1 &= \pmb \Psi(0, 1, h, f : y \mapsto zy) \\\\ &= 1 + h\sum^s_{i = 1}b_i \pmb f(\cdots) \\\\ &= 1 + \sum^s_{i = 1} b_i \pmb f(h \cdots) &&(1\star)\\\\ &= \pmb \Psi(0, 1, 1, f : y \mapsto hzy) \\\\ &= S(zh) \end{aligned}\]

Where:

  • $(1\star)$: This is applying the fact $\pmb f$ is a linear function

Then

\[\begin{aligned} y_2 &= \pmb \Psi(0, y_1, h, z) \\\\ &= \pmb \Psi(0, 1, 1, hz)y_1 \\\\ &= S(zh) y_1 \\\\ &= S(zh)^2 \end{aligned}\]

so continuing inductively, we see the result.

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

The corresponding “stability function” is defined by

\[S : \mathbb C \to \mathbb C, \quad S(z) := \pmb \Psi(0, 1, 1, f : y \to zy)\]

and the “stability region” is defined by

\[S_{\pmb \Psi} := \\{z \in \mathbb C : |S(z)| < 1 \\}\]

(these definitions are motivated by considering when the Runge-Kutta method will be asymptotically stable on the Dahlquist test equation).

In this context, what does it mean for a Runge-Kutta method to be $A$-stable?


\[\mathbb C^- \subseteq S_{\pmb \Psi}\]

(where $\mathbb C^- := \{z \in \mathbb C \mid \Re z < 0\}$).

Suppose we have the IVP:

  • $I = [x _ 0, X] \subset \mathbb R$ be an interval
  • $D \subset \mathbb R^d$ open subset
  • $\pmb y’ (x) = \pmb f(x, \pmb y)$
  • $\pmb y (x _ 0) = \pmb y _ 0$

We have a family of one-step methods called $s$-stage Runge-Kutta methods defined as:

\[\pmb \Psi(s, \pmb y, h, \pmb f) = \pmb y + h \sum^s_{i = 1} b_i \pmb k_i\]

where $\pmb k _ i$ are the “stages”

\[\pmb k_i := \pmb f(x + c_i h, \pmb y + h \sum^s_{j = 1} a_{ij} \pmb k_j)\]

and

\[c_i = \sum^s_{j = 1} a_{ij}\]

The corresponding “stability function” is defined by

\[S : \mathbb C \to \mathbb C, \quad S(z) := \pmb \Psi(0, 1, 1, f : y \to zy)\]

and the “stability region” is defined by

\[S_{\pmb \Psi} := \\{z \in \mathbb C : |S(z)| < 1 \\}\]

(these definitions are motivated by considering when the Runge-Kutta method will be asymptotically stable on the Dahlquist test equation).

In this context, a Runge-Kutta method is $A$-stable if

\[\mathbb C^- \subseteq S_{\pmb \Psi}\]

(where $\mathbb C^- := \{z \in \mathbb C \mid \Re z < 0\}$). What does it mean for the method to be $L$-stable?


\[\lim_{\Re z \to -\infty} |S(z)| = 0\]



Related posts