Implicit Runge-Kutta methods

We are now in a position to generalize the RK methods. Recalling:

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

with

\[ k_n = f(x_i + p_n, y_i + \sum_{m=1}^s q_{nm}k_m) \]

the Butcher tableau now expanded:

\[\begin{split} \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} \end{split}\]

In explicit methods, the \(k_n\)s could be built progressively on \(k_{n-1...}\), but this is not the case for implicit RK. Rather, a set of \(k_n\) may need to be solved simultaneously which can dramatically amplify the computaitonal expense.

The balance of computaional expense to increased accuracy has motivated a plethora of RK methods of varying stages, orders, and complexity of which we will only discuss a few:

Implicit Euler method

The Implicit Euler,

\[ y_{i+1} = y_i + f(x_{i+1}, y_{i+1}) h \]

has the tableau:

\[\begin{split} \begin{array}{c|c} 1 & 1 \\ \hline & 1 \\ \end{array} \end{split}\]

RK2 implicit

Implicit midpoint method

\[ \begin{align} y_{i+1} &= y_i + h k_1 \end{align}\]

where

\[k_1 = f(x_{i+\frac{1}{2}}, y_{i+\frac{1}{2}}) \]

which is found through the implicit solution of:

\[ y_{i+\frac{1}{2}} = y_n + \frac{h}{2} f\big(x_i+\frac{1}{2}h, y_{i+\frac{1}{2}}\big) \]

and has the Butcher Tableau, $\( \begin{array}{c|c} \frac{1}{2} & \frac{1}{2} \\ \hline & 1 \\ \end{array} \)$

Implicit trapezoid / Crank-Nicholson method

\[ y_{n+1} = y_n + \frac{h}{2} \left( f(t_n, y_n) + f(t_{n+1}, y_{n+1}) \right) \]

with Tableau $\( \begin{array}{c|cc} 0 & 0 & 0 \\ 1 & \frac{1}{2} & \frac{1}{2} \\ \hline & \frac{1}{2} & \frac{1}{2} \\ \end{array} \)$

Gauss-Legendre order 4 (2 stages)

As an example of the complexity, the Gauss-Legendre order 4 method has a 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} \)$

such that

\[\begin{split} \begin{align*} k_1 &= f\left(t_n + \left(\frac{1}{2} - \frac{\sqrt{3}}{6}\right)h, y_n + 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_n + \left(\frac{1}{2} + \frac{\sqrt{3}}{6}\right)h, y_n + h\left(\left(\frac{1}{4} + \frac{\sqrt{3}}{6}\right)k_1 + \frac{1}{4}k_2\right)\right) \end{align*} \end{split}\]

with the update for ( y_{n+1} ) is then given by:

\[ y_{n+1} = y_n + h\left(\frac{1}{2}k_1 + \frac{1}{2}k_2\right) \]

and so on.