Runge-Kutta method

A strong stability preserving Runge-Kutta method writes its stages as convex combinations of previously computed states and suitable Forward Euler method steps. It transfers any convex-functional nonincrease property of the forward step, such as a norm bound, under a proportionally scaled time-step restriction.

For example, if $E_k(U)=U+kF(U)$ is nonexpansive in a norm, then $Y=E_k(U)$ and $U_{\mathrm{new}}=(U+E_k(Y))/2$ is also nonexpansive: the triangle inequality bounds the new difference by one half of the initial difference plus one half of the twice-advanced difference. Both are at most the initial difference. A Taylor expansion yields $U_{\mathrm{new}}=U+kF(U)+k^2{F}^{\prime }(U)F(U)/2+O(k^3)$, so this is a second-order Runge-Kutta method. The forward-step hypothesis must hold on the stage states; preservation of one chosen convex bound is not the same as unconditional B-stability.

The classical four-stage explicit Runge-Kutta method usesIt satisfies the fourth-order conditions for a Runge-Kutta method. Its polynomial stability function excludes A-stability, while $|R(iq){|}^2=1-q^6/72+q^8/576$ gives the imaginary-axis stability interval $|q|\le 2\sqrt{2}$.

A Butcher tableau records a Runge-Kutta method's stage matrix $A$, nodes $c$, and output weights $b$ in the block array

A Butcher order condition equates the coefficient assigned by a Runge-Kutta method to a rooted tree with the corresponding exact Taylor coefficient. Satisfying every condition through tree order $p$ is equivalent to Runge–Kutta order at least $p$.

With $c=Ae$ and $C=\mathrm{diag}(c)$, a Runge-Kutta method has order at least four exactly when the eight Butcher order conditionshold; powers of $c$ are componentwise. These conditions match the numerical and exact coefficients indexed by rooted trees through order four. Matching the scalar Dahlquist test equation alone is insufficient to check the nonlinear Butcher order conditions.

The local truncation error of a one-step method is the defect after one numerical step started from the exact solution:A local error $O(h^{p+1})$ generally leads to global error $O(h^p)$ under a uniform stability bound.

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.

A one-step numerical method with step map ${\Phi }_h$ is time symmetric when ${\Phi }_{-h}={\Phi }_h^{-1}$. Its leading local-error power is odd, so every nontrivial consistent time-symmetric method has even order.

The order is the highest power through which the one-step expansion matches the exact Taylor expansion.

For an explicit Runge-Kutta method with coefficients $A,b$, put $c=A1$ and let $c^2$ mean componentwise squaring. The conditions $b^{T}1=1$, $b^{T}c=1/2$, $b^T{c}^2=1/3$ and $b^{T}Ac=1/6$ match the exact flow expansion through degree three: the two cubic differentials are $f^{\prime \prime }[f,f]$ and $(f^{\prime }{)}^{2}f$. For sufficiently smooth vector fields these give local error $O(h^4)$ and, under the usual finite-interval Lipschitz continuity assumptions, global error $O(h^3)$.