On the order of Runge Kutta methods reusing last stage

Technical Summary: On the order of Runge Kutta methods reusing last stage

Problem Statement
Explicit Runge-Kutta (RK) methods are standard algorithms for solving Initial Value Problems (IVPs) in differential equations. The computational cost of an explicit $s$-stage RK method is directly proportional to the number of function evaluations per step, which is typically $s$. A common strategy to reduce this cost is to reuse the last function evaluation of the current step ($f_{n,s}$) as the first evaluation of the subsequent step ($f_{n+1,1}$). This approach, termed "explicit RK methods reusing last stage" (RKRLS), theoretically reduces the cost from $s$ to $s-1$ evaluations per step (after the initial step).

However, a critical issue arises: while the underlying standard RK method may possess a high order of accuracy $p$, the modified RKRLS method does not generally retain this order. The reuse of the stage introduces a dependency on the previous step's approximation, potentially degrading the global convergence order. The paper addresses the specific problem of identifying the necessary conditions on the coefficients of an explicit RK method such that the resulting RKRLS method maintains the original order $p$.

Methodology
The authors employ the theory of composed methods and Butcher series to analyze the order of convergence for RKRLS methods.

1. Composition of Methods: The analysis relies on the concept that $n$ consecutive steps of a method are equivalent to a single step of a "composed" method. For RKRLS, the authors define an $n$-step composed method $(\bar{A}^{(n)}, \bar{b}^{(n)})$ where the first stage of the new step is substituted by the last stage of the previous step.
2. Adjoint Method and Butcher Series: To handle the fact that the reused stage ($f_{n,1}$) is an approximation of the derivative from the previous step rather than the exact derivative at the current point, the authors utilize the adjoint (or reverse) method. They define a local error based on the expansion of the solution around the current point using the adjoint method's coefficients.
3. Order Conditions: The authors derive algebraic conditions on the coefficients ($A, b, c$) of the base RK method. They prove that if the base method has order $p$, the RKRLS method retains order $p$ if and only if specific additional constraints are met. These constraints ensure that the error terms introduced by the stage reuse cancel out or remain within the required order of magnitude.
4. Theoretical Proofs: The paper provides rigorous proofs (Theorem 2) demonstrating that if the composed RKRLS methods have local order $p$, the global error behaves as $O(h^p)$. Subsequent theorems (Theorem 4) explicitly list the coefficient conditions required for orders $p=2, 3, 4,$ and $5$.

Key Contributions

• Order Preservation Conditions: The paper establishes precise algebraic conditions on the coefficients of an explicit RK method that guarantee the associated RKRLS method retains the same order of accuracy.
  • For $p=2$ and $p=3$, the conditions are relatively simple (e.g., for $p=3$, either $b_1=0$ or $a^T c = 1/2$).
  • For $p=4$, the conditions are more restrictive, requiring combinations such as $b_1=0$ and $(b^T A)_1=0$, or specific order properties of the vector $a$ (e.g., the method $(A, a)$ having order 3).
  • For $p \ge 5$, the authors show that if $b_1=0$, $(b^T A)_1=0$, and $a^T c = 1/2$, the RKRLS method retains order $\ge 5$.
• Existence of Optimal Methods: The authors demonstrate the existence of standard RK families that satisfy these conditions. Specifically:
  • For $p=2, 3, 4$, there exist methods with $s=p$ stages (yielding $p-1$ effective stages) that satisfy the RKRLS conditions.
  • For $p=5$, they identify a subfamily of 6-stage methods (yielding 5 effective stages) that satisfy the conditions, specifically those where $b_1=0$.
• Rejection of General Assumptions: The study clarifies that simply having $c_s=1$ is insufficient; specific structural constraints on the weights ($b$) and matrix ($A$) are required to prevent order reduction.

Results

• Theoretical Verification: The derived conditions were applied to known RK families.
  • The classical RK4 method ($c_2=c_3=1/2$) fails the RKRLS order 4 condition (it retains order 3).
  • The 3/8 RK method ($c_2=1/3, c_3=2/3$) fails the RKRLS order 4 condition (it retains order 2).
  • New methods (denoted "New2", "New3", "New4", "New5") were constructed or identified that satisfy the conditions and retain their full order $p$ when the last stage is reused.
• Numerical Experiments: The authors tested these methods on two IVPs: a two-body problem and a linear oscillation problem.
  • Convergence plots confirmed that the slopes of the global error curves matched the theoretical orders ($p$) for the new RKRLS methods.
  • Comparisons of global errors between standard RK and RKRLS methods showed that the accuracy of the RKRLS methods is very similar to their non-reusing counterparts, confirming that the order is preserved.
  • An anomaly was noted for the order 4 RKRLS method on the two-body problem with a large step size ($h=0.2$), where the error was significantly larger than the standard RK method. The authors attribute this to potential stability issues, noting that the stability region of RKRLS methods may be smaller than that of the original RK methods.

Significance
The paper claims that it is possible to reduce the computational cost of explicit Runge-Kutta methods from $s$ to $s-1$ function evaluations per step without sacrificing the order of accuracy, provided that specific coefficient conditions are met. This is significant because it offers a straightforward mechanism to improve efficiency for high-order methods without requiring the development of entirely new, complex integration schemes. The results are validated theoretically through composition methods and adjoint analysis, and numerically through convergence tests. The authors conclude that while stability properties may differ, the order of accuracy can be maintained, making RKRLS a viable strategy for efficient IVP solvers.