Implicit Runge-Kutta method

An implicit Runge-Kutta method defines one or more stages through equations involving those same stages.

For a vector field uniformly Lipschitz continuous in the state with constant $L$, the stage fixed-point map of an implicit Runge-Kutta method is a contraction in the maximum stage norm if $hL{\max }_i{\sum }_j|a_{ij}|<1$. The contraction mapping theorem then gives unique stages. This is a sufficient small-step condition; a dissipative vector field may permit solvability for larger steps. An algebraic stability or B-stability estimate compares existing stage solutions and should not be mistaken for an unqualified stage-existence theorem.

The implicit midpoint rule advances an autonomous ordinary differential equation byIt is a second-order, A-stable, time-symmetric numerical method.

The Crank--Nicolson method applies the trapezoidal rule to a semidiscrete evolution equation. For a linear system $u^{\prime }=Lu$ its update is

Given distinct nodes $c_i$, a collocation Runge-Kutta method uses the Lagrange basis ${\ell }_j$ with $a_{ij}={\int }_0^{c_i}{\ell }_j(\tau )d\tau$ and $b_j={\int }_0^1{\ell }_j(\tau )d\tau$. Its stages enforce the differential equation at the collocation nodes.

A Lobatto IIIA method collocates at the Lobatto quadrature nodes, including both endpoints of the time interval. Its three-stage version hasThe Butcher order conditions give order four. Its stability function iswhich is A-stable but not L-stable. It is not algebraically stable: the first diagonal entry of the defining matrix is $2b_1{a}_{11}-b_1^2=-1/36$. This distinguishes linear A-stability from nonlinear algebraic stability.

The $s$-stage Gauss--Legendre Runge--Kutta method collocates at the Gauss--Legendre quadrature nodes on $[0,1]$. It is symmetric, A-stable, and has order $2s$.

The two-stage Gauss--Legendre Runge-Kutta method uses nodes $c_{1,2}=1/2\mp \sqrt{3}/6$, weights $b_1=b_2=1/2$ and coefficients $a_{11}=a_{22}=1/4$, $a_{12}=1/4-\sqrt{3}/6$, $a_{21}=1/4+\sqrt{3}/6$. The Butcher order conditions give order four. Its stability function is the displayed rational function, which is A-stable. The algebraic stability matrix is zero, so positive weights also give nonlinear contractivity for dissipative vector fields.

An $s$-stage Radau IIA method collocates at the right-endpoint Radau nodes. It has order $2s-1$ and is both algebraically stable and L-stable.

A Runge-Kutta method is algebraically stable when $b_i\ge 0$ and the matrix $M$ with $M_{ij}=b_i{a}_{ij}+b_j{a}_{ji}-b_i{b}_j$ is positive semidefinite. Algebraic stability implies contractivity for dissipative differential equations.

For differences $D_i$ between corresponding stages and differences $F_i$ between their vector fields, a Runge--Kutta step satisfiesTo derive the identity, expand the squared norm of $d_{n+1}=d_n+h{\sum }_i{b}_i{F}_i$ and substitute $d_n=D_i-h{\sum }_j{a}_{ij}{F}_j$ in the linear term. Symmetrizing the double sum gives the displayed coefficients $m_{ij}$. For a dissipative vector field, the first sum is nonpositive when $b_i\ge 0$, and the second sum is nonnegative when the matrix $(m_{ij})$ is a positive semidefinite matrix. Thus algebraic stability implies B-stability.

The trapezoidal ODE rule averages vector fields at the old and new states and is A-stable.

The trapezoidal rule is A-stable but is not B-stable. For the dissipative vector field $f(y)=-y^3$ at step size one, its uniquely defined step map $T$ obeys $T+T^3/2=y-y^3/2$. At $y=\sqrt{2}$, $T=0$ and implicit differentiation gives $T^{\prime }=-2$, so nearby states expand rather than contract. This is a concrete nonlinear obstruction, rather than merely failure of the sufficient algebraic stability criterion.