Proof of Runge-Kutta Order Conditions

Deriving the order conditions for Runge-Kutta methods requires matching Taylor expansions of the numerical and exact solutions. The combinatorial complexity grows rapidly with order, motivating the elegant theory of Butcher trees.

Setup

Theorem7.3Order Conditions for Explicit RK Methods

An $s$ -stage explicit Runge-Kutta method with Butcher tableau $(a_{ij}, b_i, c_i)$ has order $p$ if and only if certain algebraic conditions on the coefficients are satisfied. For orders 1 through 4:

Order 1 (1 condition): $\sum_i b_i = 1$

Order 2 (1 condition): $\sum_i b_i c_i = 1/2$

Order 3 (2 conditions): $\sum_i b_i c_i^2 = 1/3$ , $\sum_{i,j} b_i a_{ij} c_j = 1/6$

Order 4 (4 conditions): $\sum_i b_i c_i^3 = 1/4$ , $\sum_{ij} b_i c_i a_{ij} c_j = 1/8$ , $\sum_{ij} b_i a_{ij} c_j^2 = 1/12$ , $\sum_{ijk} b_i a_{ij} a_{jk} c_k = 1/24$

Proof (Orders 1 and 2)

Proof

Consider $y' = f(t, y)$ , $y(t_0) = y_0$ . The exact solution satisfies $y(t_0 + h) = y_0 + hy'_0 + \frac{h^2}{2}y''_0 + O(h^3)$ where $y' = f$ , $y'' = f_t + f_y f$ .

The RK method computes $k_i = f(t_0 + c_i h, y_0 + h\sum_j a_{ij}k_j)$ and $y_1 = y_0 + h\sum_i b_i k_i$ .

Order 1. Expand $k_i$ to zeroth order in $h$ : $k_i = f(t_0, y_0) + O(h) = f_0 + O(h)$ . Then $y_1 = y_0 + h(\sum_i b_i) f_0 + O(h^2)$ . Matching with $y(t_0+h) = y_0 + hf_0 + O(h^2)$ gives $\sum_i b_i = 1$ .

Order 2. Expand $k_i$ to first order: $k_i = f_0 + h c_i f_t + h(\sum_j a_{ij}k_j^{(0)})f_y + O(h^2) = f_0 + h(c_i f_t + c_i f_y f_0) + O(h^2)$ (using $\sum_j a_{ij} = c_i$ and $k_j^{(0)} = f_0$ ). Here we used the row-sum condition $c_i = \sum_j a_{ij}$ .

Then $y_1 = y_0 + h\sum_i b_i [f_0 + h c_i(f_t + f_y f_0)] + O(h^3) = y_0 + h f_0 + h^2 (\sum_i b_i c_i)(f_t + f_y f_0) + O(h^3)$ .

The exact expansion is $y(t_0+h) = y_0 + hf_0 + \frac{h^2}{2}(f_t + f_y f_0) + O(h^3)$ .

Matching the $h^2$ coefficients: $\sum_i b_i c_i = 1/2$ .

Higher orders proceed similarly but the Taylor expansion of $f(t + ch, y + h\sum a_{ij}k_j)$ involves higher derivatives of $f$ , leading to products of the Butcher coefficients. At order $p$ , there are as many conditions as there are rooted trees with $p$ vertices (1, 1, 2, 4, 9, 20, 48, ... for $p = 1, 2, 3, 4, 5, 6, 7, ...$ ), connected to the Butcher group and B-series theory. $\square$

■

ExampleMinimum Stage Count

The minimum number of stages $s$ for an explicit RK method of order $p$ : $s = p$ for $p \leq 4$ ; $s = p + 1$ for $p = 5, 6$ ; $s = p + 2$ for $p = 7$ ; and $s \geq p + 3$ for $p = 8$ . The classical RK4 achieves the optimal 4 stages for order 4 (matching 4 conditions with 4 stages provides 10 free parameters and 4 constraints).

RemarkButcher Trees and B-Series

Butcher's formalism associates each order condition with a rooted tree. The order condition for tree $\tau$ is $\sum b_i \Phi_i(\tau) = 1/\gamma(\tau)$ where $\Phi_i(\tau)$ is a product of $a_{ij}$ 's determined by the tree structure, and $\gamma(\tau)$ is the density (product of subtree sizes). This elegant framework unifies RK theory and connects to Hopf algebras and renormalization in quantum field theory (Connes-Kreimer).