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?
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?
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?
c | A
--|-----
| b^T
- 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?
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?
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?
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}$?
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?
(where $\mathbb C^- := \{z \in \mathbb C \mid \Re z < 0\}$).