Some notes on order reduction in Runge-Kutta methods

Order reduction in RK methods is a phenomenon in which the observed convergence rate for some problems is not the design order (classical order) of the method, but rather the stage order. Stage order refers to the order of the truncation error for each stage \(y_i\), viewed as an approximation to \(u(t_n + h c_i)\). The stage order of an RK method is the minimum stage order over its stages.

Some causes of RK order reduction are:

• Stiffness
• Differential-algebraic equations (DAEs)
• Boundary conditions in IBVPs

These all seem related: in the infinite-stiffness limit, stiff systems become DAEs. Boundary conditions can be viewed as algebraic constraints, thus also leading to DAEs. So one viewpoint is that all order reduction results from the interaction of algebraic constraints with RK handling of ODEs.

Each stage \(y_i\) of the RK method has a truncation error \(\tau_i = O(h^{q_i+1})\) (when viewed as an approximation to \(u(t_n + h c_i)\)). Typically, high order methods are carefully designed so that, in the linear combination used to compute \(u_{n+1}\) (determined by the choice of quadrature weights \(b_i\)) leading terms in the error precisely cancel out. When some of the equations are algebraic, the natural approach is to impose the algebraic constraints exactly at each intermediate stage. This involves an \(O(h^{q_i+1})\) perturbation, and this perturbation will not cancel out in the computation of \(u_{n+!}\).

Ref. 1 below contains a lovely explanation of order reduction from boundaries, with a worked example and techniques for avoiding it. The essence of the problem is that imposing the exact boundary value at the intermediate stages is a O(stage order) perturbation. The analysis is performed by writing the semi-discretization inhomogeneously as

where \(g(t)\) is the boundary condition.

In Ref. 2, the viewpoint is different. The whole semidiscrete system, including the boundary value, is written as a single system:

References:

1. Carpenter, MH, D Gottlieb, S Abarbanel, and W-S Don. 1995. “The theoretical accuracy of Runge–Kutta time discretizations for the initial boundary value problem: a study of the boundary error.” SIAM Journal on Scientific … 16(6): 1241–1252. http://cat.inist.fr/?aModele=afficheN&cpsidt=2889973 (August 10, 2012).

2.

-