Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 72 / 4

For an $s$-stage Runge-Kutta method with coefficient matrix $A=(a_{ij})$ and weights $b=(b_i)$, put $B=\mathrm{diag}(b_i)$. It is algebraically stable whenEquivalently, $m_{ij}=b_i{a}_{ij}+b_j{a}_{ji}-b_i{b}_j$ defines a positive semidefinite symmetric matrix. The condition concerns the full coefficient tableau and nonlinear contractivity, not merely the scalar stability function. It is normally used with a consistent Runge-Kutta method and stage equations satisfying the necessary stage solvability of an implicit Runge-Kutta method.

The Butcher contractivity theorem states that an algebraically stable Runge-Kutta method is B-stable: for a dissipative vector field and any positive step for which the stage problems are solved, its step does not increase the distance between two numerical solutions. The required condition on the dissipative vector field isfor all compared states at each common time. The inner product can be real Euclidean or complex Hermitian. The stage solvability of an implicit Runge-Kutta method is assumed in this comparison, not a conclusion from a distance estimate alone.

Let $d$ be the difference of starting values, $D_i$ the differences of corresponding stages and $F_i$ the differences of their vector-field values. ThenExpanding the squared norm of the update givesSubstitute $d=D_i-h{\sum }_j{a}_{ij}{F}_j$ in the linear term. Symmetrizing the double sum proves the Runge-Kutta contractivity identityEach inner product in the first sum is nonpositive by the defining inequality for a dissipative vector field, and its weight is nonnegative. The final quadratic form is nonnegative: resolve the vectors $F_i$ into components and apply positive semidefiniteness of $M$ to each component vector. Hence $\boxed{\Vert d_{+}\Vert \le \Vert d\Vert }$, which is exactly B-stability. No linearization of the vector field has been used.

For the Dahlquist test equation $y^{\prime }=\lambda y$ with $\mathrm{Re}\lambda \le 0$, this also bounds the amplification factor by one wherever the stages are well defined. With strictly positive weights, no stage pole can occur in the open left half-plane. Indeed, if $(I-zA)v=0$ for nonzero $v$, thenwhen $\mathrm{Re}z<0$, contradicting $M⪰0$. This proves the usual A-stability corollary for the scalar stability function; boundedness from the open half-plane makes any boundary pole in that rational function removable. Zero-weight redundant stages require their own solvability treatment. The nonlinear B-stability statement is stronger than A-stability, and the two notions should not be conflated.

For the first Butcher tableau, $b=(1/2,1/2{)}^T$ and the off-diagonal entries sum to $1/2$, while each diagonal entry is $1/4$. ThusThe positive weights and zero matrix prove that method 1 is algebraically stable. It is the two-stage Gauss collocation method.

The second method is explicit and has $b=(1/4,3/8,3/8{)}^T$. Its first diagonal algebraic-stability entry isA positive semidefinite matrix cannot have a negative diagonal quadratic form, so method 2 is not algebraically stable. The negative value supplies a direct test; its order is irrelevant to this conclusion.

For the third method, $A=\left(\begin{array}{cc}1/4& -1/4\\ 1/4& 5/12\end{array}\right)$ and $b=(1/4,3/4{)}^T$. Direct computation givesBoth weights are positive, so method 3 is algebraically stable.