Implicit Runge-Kutta Methods - Executable Engineering: Interactive Numerical Methods in Python

We are now in a position to generalize the Runge-Kutta family to implicit schemes. Recall the $s$ -stage Runge-Kutta update:

y_{i+1} = y_i + h \sum_{n=1}^{s} a_n k_n

(1)

where each stage slope $k_n$ can now depend on all stage slopes $k_1, \dots, k_s$ :

k_n = f\!\left(t_i + p_n h,\; y_i + h \sum_{m=1}^{s} q_{nm} k_m\right)

(2)

The general Butcher tableau is therefore a full $s \times s$ matrix:

\begin{array}{c|cccc} p_1 & q_{11} & q_{12} & \dots & q_{1s} \\ p_2 & q_{21} & q_{22} & \dots & q_{2s} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ p_s & q_{s1} & q_{s2} & \dots & q_{ss} \\ \hline & a_1 & a_2 & \dots & a_s \end{array}

(3)

In explicit RK methods ( $q_{nm} = 0$ for $m \ge n$ ), the stages $k_n$ are evaluated sequentially. In implicit RK methods, the coupled system of $s$ nonlinear equations for $k_1, \dots, k_s$ must be solved simultaneously at every time step, trading higher computational cost for exceptional stability and accuracy.

Implicit Euler Method¶

The Implicit Euler (Backward Euler) method is the 1-stage, first-order implicit Runge-Kutta scheme:

y_{i+1} = y_i + h f(t_{i+1}, y_{i+1})

(4)

Its Butcher tableau has a single non-zero diagonal entry $q_{11} = 1$ :

\begin{array}{c|c} 1 & 1 \\ \hline & 1 \end{array}

(5)

Second-Order Implicit Runge-Kutta Methods¶

Implicit Midpoint Method¶

The 1-stage Implicit Midpoint method achieves second-order accuracy ( $\mathcal{O}(h^2)$ ) by evaluating the slope at the implicit midpoint:

y_{i+1} = y_i + h k_1, \qquad k_1 = f\!\left(t_i + \frac{1}{2}h,\; y_i + \frac{1}{2}h k_1\right)

(6)

Equivalently, $y_{i+1/2} = y_i + \frac{h}{2} f(t_i + \frac{1}{2}h, y_{i+1/2})$ , with Butcher tableau:

\begin{array}{c|c} \frac{1}{2} & \frac{1}{2} \\ \hline & 1 \end{array}

(7)

Implicit Trapezoid (Crank-Nicolson) Method¶

The Implicit Trapezoid method (widely known as the Crank-Nicolson scheme in PDE time-stepping) averages the explicit slope at $t_i$ and the implicit slope at $t_{i+1}$ :

y_{i+1} = y_i + \frac{h}{2} \left( f(t_i, y_i) + f(t_{i+1}, y_{i+1}) \right)

(8)

\begin{array}{c|cc} 0 & 0 & 0 \\ 1 & \frac{1}{2} & \frac{1}{2} \\ \hline & \frac{1}{2} & \frac{1}{2} \end{array}

(9)

Gauss-Legendre Order 4 (2 Stages)¶

By placing stage nodes at the roots of shifted Legendre polynomials (just like Gaussian quadrature!), an $s$ -stage implicit Gauss-Legendre method achieves the maximum possible order $2s$ . For $s = 2$ stages, we obtain a fourth-order ( $\mathcal{O}(h^4)$ ), unconditionally A-stable scheme with Butcher tableau:

\begin{array}{c|cc} \frac{1}{2} - \frac{\sqrt{3}}{6} & \frac{1}{4} & \frac{1}{4} - \frac{\sqrt{3}}{6} \\ \frac{1}{2} + \frac{\sqrt{3}}{6} & \frac{1}{4} + \frac{\sqrt{3}}{6} & \frac{1}{4} \\ \hline & \frac{1}{2} & \frac{1}{2} \end{array}

(10)

At each step, $k_1$ and $k_2$ are found by solving the coupled system:

\begin{aligned} k_1 &= f\!\left(t_i + \left(\frac{1}{2} - \frac{\sqrt{3}}{6}\right)h,\; y_i + h\left(\frac{1}{4}k_1 + \left(\frac{1}{4} - \frac{\sqrt{3}}{6}\right)k_2\right)\right) \\ k_2 &= f\!\left(t_i + \left(\frac{1}{2} + \frac{\sqrt{3}}{6}\right)h,\; y_i + h\left(\left(\frac{1}{4} + \frac{\sqrt{3}}{6}\right)k_1 + \frac{1}{4}k_2\right)\right) \end{aligned}

(11)

followed by the symmetric update:

y_{i+1} = y_i + \frac{h}{2}\left(k_1 + k_2\right)

(12)

Many additional families (such as Radau and Lobatto collocation methods, and diagonally implicit Runge-Kutta schemes) are catalogued in the list of Runge-Kutta methods.