Collocation Runge-Kutta method

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.

This applies the collocation method to the time-step polynomial of an ordinary differential equation.

For distinct nodes $c_1,c_2\in [0,1]$, the two-stage collocation Runge-Kutta method has stability functionThe denominator has no zeros in the closed left half-plane. On the imaginary axis the denominator's squared modulus minus the numerator's is $(d^2-r^2)y^4$. Thus $d\ge r$, equivalently $c_1+c_2\ge 1$, is necessary and sufficient for A-stability, using the maximum modulus principle and the bound at infinity.

For $s$ distinct collocation nodes, let ${\pi }_s(t)={\prod }_{i=1}^s(t-c_i)$. If ${\int }_0^1{t}^j{\pi }_s(t)dt=0$ for $0\le j<k$, and the next moment is nonzero, the associated interpolatory quadrature has order $s+k$, and the collocation Runge-Kutta method has the same classical order for sufficiently smooth differential equations. Here $0\le k\le s$. Equivalently, if the quadrature is exact through degree $p-1$ but not degree $p$, the method has order $p$. The generic order is at least $s$, Gauss collocation methods reach $2s$, and Radau IIA methods reach $2s-1$.

For $s$ collocation nodes, the residual of the collocation polynomial vanishes at each node and contains the factor $\omega (\tau )={\prod }_i(\tau -c_i)$. Quadrature exactness through degree $q-1$ implies ${\int }_0^1\omega (\tau )p(\tau )d\tau =0$ for every polynomial of degree at most $q-s-1$. Expand the smooth vector-field interpolation error and the derivative of the exact flow in powers of the step. Every endpoint-error term of degree below $q$ has this vanishing weighted moment, so the endpoint local error is $O(h^{q+1})$, although the interior stage accuracy is generally only $s$. A step Lipschitz estimate and discrete Gronwall inequality then give global order $q$. Gaussian nodes attain $q=2s$, while the first nonexact quadrature moment bounds the order from above.

For a collocation Runge-Kutta method, $a_{ij}={\int }_0^{c_i}{\ell }_j(t)dt$, where the Lagrange interpolation basis obeys ${\sum }_j{\ell }_j=1$. Hence each row sum is its collocation node. Failure of this identity disproves a claimed collocation tableau with those nodes. The identity alone is necessary rather than sufficient: the individual integrated basis coefficients must also agree.

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$.

Choose $c_1,\dots ,c_s$ as the polynomial roots of $P_s(2c-1)$ in $(0,1)$, and form the Lagrange interpolation polynomials ${\ell }_j(t)={\prod }_{m\ne j}(t-c_m)/(c_j-c_m)$. The Gauss collocation method has $a_{ij}={\int }_0^{c_i}{\ell }_j(t)dt$ and $b_j={\int }_0^1{\ell }_j(t)dt$. This gives explicit coefficient formulas after finding polynomial roots: if ${\ell }_j(t)={\sum }_r{d}_{jr}{t}^r$, these integrals are ${\sum }_r{d}_{jr}{c}_i^{r+1}/(r+1)$ and ${\sum }_r{d}_{jr}/(r+1)$. Gaussian quadrature gives 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.

Suppose an $s$-stage Runge-Kutta method has order $2s-1$, an invertible matrix $A$, and $b^T{A}^{-1}1=1$. Its stability function is $R(z)=1+z{b}^T(I-zA{)}^{-1}1$. The adjugate matrix formula gives a rational function with denominator degree $s$ and numerator degree at most $s$; its zero limit at infinity lowers the latter degree to at most $s-1$. The order of a numerical method gives $R(z)-e^z=O(z^{2s})$, identifying the $[s-1/s]$ Padé approximant. Uniqueness follows because the cross-multiplied difference of two candidates has degree at most $2s-1$ but a zero of order at least $2s$, so is identically zero. The A-stability of near-diagonal exponential Padé approximants then proves A-stability, and the zero limit proves L-stability. These conditions identify the stability function; they do not alone claim uniqueness of all entries of the Runge-Kutta method tableau.

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 stage states $Y_i=y_n+h{\sum }_j{a}_{ij}{k}_j$ and a vector field with $Y_i^T{k}_i=0$, expansion of the new squared norm gives $\Vert y_{n+1}{\Vert }^2-\Vert y_n{\Vert }^2=-h^2{\sum }_{i,j}{M}_{ij}{k}_i^T{k}_j$, where $M_{ij}=b_i{a}_{ij}+b_j{a}_{ji}-b_i{b}_j$. Hence $M=0$ preserves the quadratic form exactly for every well-defined step. The same argument with a fixed symmetric matrix in the inner product preserves any quadratic invariant of the vector field. In particular it preserves the Euclidean norm for a skew-symmetric matrix differential equation.

An algebraically stable Runge-Kutta method is B-stable: for a dissipative vector field, a well-defined step cannot increase the distance between two starting values. This assumes that the compared stage equations have solutions, as required by stage solvability of an implicit Runge-Kutta method. The Runge-Kutta contractivity identity expresses the distance change as a nonpositive weighted term coming from the dissipative vector field minus a nonnegative quadratic form involving the matrix defining algebraic stability. Positive weights also rule out stage poles in the open left half-plane on the scalar test equation, giving A-stability there; zero-weight redundant stages need separate solvability attention.

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.