43.10.01 · numerical-analysis / numerical-odes

One-step methods: Euler, trapezoidal, Runge-Kutta; consistency and order

shipped3 tiersLean: none

Anchor (Master): Hairer-Nørsett-Wanner 1993 *Solving Ordinary Differential Equations I: Nonstiff Problems* 2e (Springer) §II.1-II.3 (the general one-step method, the order conditions, Butcher's rooted-tree theory at a high level); Butcher 2016 *Numerical Methods for Ordinary Differential Equations* 3e (Wiley) Ch. 2-3 (the algebraic theory of order); LeVeque 2007 (SIAM) Ch. 5-6 (consistency, zero-stability, and convergence for one-step and linear multistep methods)

Intuition Beginner

A differential equation tells you the slope of a curve at every point but does not hand you the curve itself. The starting equation here is the simplest kind: you know where the curve begins, and you have a rule that, given the time and the current height, returns the slope right now. The question is how to draw the whole curve forward in time when all you ever get to ask for is the slope at the spot where you currently stand.

The honest answer is to take small steps. Stand at the starting point, ask for the slope, and walk a short distance in that straight-line direction. You will not land exactly on the true curve, because the real curve bends while you walked straight, but if the step was short you land close. Now ask for the slope again at the new spot and take another short straight step. Repeating this is the whole idea of a one-step method: each new point is computed from the one before it using a single evaluation of the slope rule.

The plainest version, taking the slope at the point you are leaving, is Euler's method. It is easy to picture and easy to compute, but it leans on one slope for the entire step, so it drifts. Two fixes appear at once. You can use the slope at where you are about to arrive instead, which needs a small bit of solving but behaves better on stiff problems. Or you can average the slope at the start and the slope at the end, which is the trapezoidal rule and tracks curvature far more faithfully.

The deepest fix is to peek. Before committing to a full step, sample the slope at a few cleverly chosen interior points and combine those samples with carefully tuned weights. That is a Runge-Kutta method, and the famous four-sample recipe matches the true curve so closely that halving the step shrinks the error by a factor of sixteen. This unit is the root of the chapter: every later method for marching a differential equation forward is measured against the standards set here.

Visual Beginner

Picture a slope field: at a grid of points in the time-height plane, a short dash shows the slope the rule would report there. The true solution is the curve that stays tangent to every dash it passes through. A one-step method is a polygonal path that tries to shadow that curve, choosing each new segment from sampled dashes.

The table below contrasts the four methods of this unit by what slope information each step uses. Reading down the table, the methods spend more slope evaluations per step and, in return, hug the true curve more tightly. The rightmost column is the order: the power of the step size that controls how fast the error shrinks as the steps get shorter.

method	slope information used per step	cost per step	order
forward Euler	slope at the point you leave	one slope	$1$
backward Euler	slope at the point you arrive (solve for it)	one implicit slope	$1$
trapezoidal rule	average of the leaving and arriving slopes	one implicit slope	$2$
classical RK4	four sampled slopes, weighted $1, 2, 2, 1$ over $6$	four slopes	$4$

Each row is a recipe you can run by hand on a small example, and the rest of the unit explains why the order column reads exactly as it does and why a higher order is worth the extra slope samples.

Worked example Beginner

Let us march the equation whose slope rule is "the slope equals the current height," starting from height $1$ at time $0$ . The true solution is the growing curve $y = e^{t}$ , so we have an exact answer to compare against. Take a step size of $h = 0.5$ and advance with forward Euler to time $1$ .

Step 1. The rule is: new height equals old height plus $h$ times the slope, and the slope is the current height. Starting at height $u^{0} = 1$ , the first step gives $u^{1} = u^{0} + 0.5 \times u^{0} = 1 + 0.5 \times 1 = 1.5$ . We have arrived at time $0.5$ with height $1.5$ .

Step 2. Apply the same rule again from the new point: $u^{2} = u^{1} + 0.5 \times u^{1} = 1.5 + 0.5 \times 1.5 = 2.25$ . We have reached time $1$ with height $2.25$ .

Step 3. Compare with the truth. The exact height at time $1$ is $e^{1} \approx 2.718$ . The Euler march gives $2.25$ , an undershoot of about $0.468$ . Euler used the slope from the start of each step, and because this curve bends upward, the start-of-step slope is always a little too small, so the polygon falls below the curve.

Step 4. Halve the step and watch the error shrink. With $h = 0.25$ the four-step march gives $1.25, 1.5625, 1.9531, 2.4414$ , landing at $2.4414$ , an undershoot of about $0.277$ . Cutting the step roughly halved the final error, which is the signature of a first-order method: error falls in proportion to the step size.

What this tells us: a one-step method turns a differential equation into ordinary arithmetic you repeat, and the size of the leftover error is governed by the step size raised to the method's order. Euler is order one, so smaller steps help only in proportion. A higher-order method, with the same effort spent more cleverly, would have landed far closer with the very same step count.

Check your understanding Beginner

Formal definition Intermediate+

Consider the initial-value problem (IVP) for a system of first-order ordinary differential equations $$ y'(t) = f(t, y(t)), \qquad y(t_0) = y_0, \qquad y(t) \in \mathbb{R}^d, $$ with $f : [t_{0}, T] \times R^{d} \to R^{d}$ continuous and globally Lipschitz in $y$ : there is $L \geq 0$ with $∥ f (t, y) - f (t, z) ∥ \leq L ∥ y - z ∥$ for all $t \in [t_{0}, T]$ and $y, z \in R^{d}$ . Under this hypothesis the IVP has a unique $C^{1}$ solution on $[t_{0}, T]$ by the Picard-Lindelöf theorem 02.12.01. Fix a step $h > 0$ , set $t_{n} = t_{0} + nh$ , and write $u^{n} \approx y (t_{n})$ for the numerical approximation; the exact solution value is $y (t_{n})$ .

Definition (one-step method). A one-step method for the IVP is a recurrence $$ u^{n+1} = u^n + h,\Phi(t_n, u^n, h), $$ where the increment function $Φ : [t_{0}, T] \times R^{d} \times [0, h_{0}] \to R^{d}$ encodes the method. The method is explicit when $Φ$ is evaluated from data already known at step $n$ , and implicit when the formula for $u^{n + 1}$ contains $u^{n + 1}$ inside an $f$ -evaluation, so each step solves an algebraic equation for $u^{n + 1}$ .

The four basic instances are: forward (explicit) Euler, $Φ = f (t_{n}, u^{n})$ , giving $u^{n + 1} = u^{n} + h f (t_{n}, u^{n})$ ; backward (implicit) Euler, $u^{n + 1} = u^{n} + h f (t_{n + 1}, u^{n + 1})$ ; the trapezoidal rule, $u^{n + 1} = u^{n} + \frac{h}{2} (f (t_{n}, u^{n}) + f (t_{n + 1}, u^{n + 1}))$ ; and the implicit midpoint rule, $u^{n + 1} = u^{n} + h f (t_{n} + \frac{h}{2}, \frac{1}{2} (u^{n} + u^{n + 1}))$ .

Definition (local truncation error and consistency). The local truncation error (LTE) is the residual obtained by substituting the exact solution into the difference formula: $$ \tau^n ;=; \frac{y(t_{n+1}) - y(t_n)}{h} ;-; \Phi\big(t_n, y(t_n), h\big). $$ The method is consistent of order $p$ if $∥ τ^{n} ∥ \leq C h^{p}$ for some constant $C$ independent of $n$ and $h$ , as $h \to 0$ ; equivalently $τ^{n} = O (h^{p})$ . Consistency (order $\geq 1$ ) is the requirement $Φ (t, y, 0) = f (t, y)$ , i.e. the increment function reduces to the right-hand side in the zero-step limit. The integer $p$ is the order of the method.

Definition (explicit Runge-Kutta method). An $s$ -stage explicit Runge-Kutta (RK) method computes intermediate stages $k_{1}, \dots, k_{s}$ and advances by $$ k_i = f\Big(t_n + c_i h,; u^n + h!\sum_{j=1}^{i-1} a_{ij} k_j\Big), \qquad u^{n+1} = u^n + h \sum_{i=1}^{s} b_i, k_i, $$ so $Φ (t_{n}, u^{n}, h) = \sum_{i} b_{i} k_{i}$ . The coefficients are collected in the Butcher tableau $(A, b, c)$ with $A = (a_{ij})$ strictly lower triangular (the explicit condition), the weights $b = (b_{i})$ , and the nodes $c_{i} = \sum_{j} a_{ij}$ . The classical RK4 is $$ \begin{array}{c|cccc} 0 & & & & \ \tfrac12 & \tfrac12 & & & \ \tfrac12 & 0 & \tfrac12 & & \ 1 & 0 & 0 & 1 & \ \hline & \tfrac16 & \tfrac13 & \tfrac13 & \tfrac16 \end{array} \qquad u^{n+1} = u^n + \tfrac{h}{6}\big(k_1 + 2k_2 + 2k_3 + k_4\big). $$ The notation $τ^{n}$ , $Φ$ , the Butcher triple $(A, b, c)$ , and the $O (h^{p})$ Landau symbol are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"Consistency alone gives convergence." For one-step methods consistency plus the Lipschitz bound on $Φ$ does give convergence (the theorem below), but the implication is not automatic from $τ^{n} \to 0$ in isolation: the stability ingredient, here the Lipschitz constant of $Φ$ controlling error propagation, is essential. For multistep methods consistency without zero-stability fails outright 43.10.03.
"The local truncation error is the error after one step." The LTE $τ^{n}$ is the residual divided by $h$ ; the actual one-step error from exact data is $h τ^{n} = O (h^{p + 1})$ . The convergence theorem shows these $O (h^{p + 1})$ per-step errors accumulate over $O (1/ h)$ steps to a global error $O (h^{p})$ — one power of $h$ is lost to accumulation.
"Backward Euler and the trapezoidal rule are the same order because both are implicit." Implicitness is orthogonal to order. Backward Euler is order $1$ ; the trapezoidal rule is order $2$ . The order is fixed by Taylor matching of $Φ$ , not by whether the step is implicit.
"More stages always means higher order." The number of order conditions grows faster than the number of free tableau coefficients: an $s$ -stage explicit RK method attains order at most $s$ , and for $s \geq 5$ no explicit $s$ -stage method reaches order $s$ (the Butcher barriers). Stages buy order only up to these algebraic limits.

Key theorem with proof Intermediate+

The signature theorem is the convergence of one-step methods: a consistent method whose increment function is Lipschitz converges, with global error of the same order as the consistency order. It is the statement that makes "order $p$ " a promise about the answer and not merely about a single step, and every order claim in the chapter is read through it.

Theorem (convergence of one-step methods). Let $f$ be globally Lipschitz in $y$ with constant $L$ on $[t_{0}, T] \times R^{d}$ , and let the one-step method $u^{n + 1} = u^{n} + h Φ (t_{n}, u^{n}, h)$ have an increment function $Φ$ that is Lipschitz in its second argument, $∥Φ (t, y, h) - Φ (t, z, h) ∥ \leq Λ∥ y - z ∥$ for $t \in [t_{0}, T]$ , $h \in [0, h_{0}]$ . If the method is consistent of order $p$ , so that the local truncation error satisfies $∥ τ^{n} ∥ \leq C h^{p}$ , then the global error $e^{n} = y (t_{n}) - u^{n}$ satisfies $$ \max_{0 \le n \le N} |e^n| ;\le; e^{\Lambda (T - t_0)},|e^0| ;+; \frac{e^{\Lambda (T - t_0)} - 1}{\Lambda}, C h^p, \qquad Nh = T - t_0. $$ In particular, if $e^{0} = 0$ then $max_{n} ∥ e^{n} ∥ \leq K h^{p}$ with $K = \frac{e ^{Λ (T - t_{0})} - 1}{Λ} C$ ; the method converges and the global error is $O (h^{p})$ . ^{[LeVeque §5.3-5.4; Süli-Mayers §12.2-12.3]}

Proof. Subtract the numerical recurrence from the exact-solution identity. By the definition of the LTE, the exact solution satisfies $$ y(t_{n+1}) = y(t_n) + h,\Phi\big(t_n, y(t_n), h\big) + h,\tau^n . $$ The numerical solution satisfies $u^{n + 1} = u^{n} + h Φ (t_{n}, u^{n}, h)$ . Subtracting gives the error recurrence $$ e^{n+1} = e^n + h\big[\Phi(t_n, y(t_n), h) - \Phi(t_n, u^n, h)\big] + h,\tau^n . $$ Take norms and apply the Lipschitz bound on $Φ$ and the LTE bound: $$ |e^{n+1}| \le |e^n| + h\Lambda |e^n| + h|\tau^n| \le (1 + h\Lambda)|e^n| + C h^{p+1}. $$ This is a scalar linear recurrence in $ε_{n} := ∥ e^{n} ∥$ of the form $ε_{n + 1} \leq (1 + h Λ) ε_{n} + B$ with $B = C h^{p + 1}$ . Unrolling it, $$ \varepsilon_n \le (1 + h\Lambda)^n \varepsilon_0 + B \sum_{m=0}^{n-1} (1 + h\Lambda)^m = (1 + h\Lambda)^n \varepsilon_0 + B,\frac{(1 + h\Lambda)^n - 1}{h\Lambda}. $$ Use the elementary bound $1 + h Λ \leq e^{h Λ}$ , hence $(1 + h Λ)^{n} \leq e^{nh Λ} = e^{Λ (t_{n} - t_{0})} \leq e^{Λ (T - t_{0})}$ for $t_{n} \leq T$ . Substituting $B = C h^{p + 1}$ and dividing the geometric factor by $h$ , $$ \varepsilon_n \le e^{\Lambda(T - t_0)},\varepsilon_0 + \frac{e^{\Lambda(T - t_0)} - 1}{\Lambda},C h^p . $$ Taking the maximum over $0 \leq n \leq N$ yields the stated bound. With $e^{0} = 0$ the first term vanishes and $max_{n} ∥ e^{n} ∥ \leq K h^{p}$ with $K$ as stated. $□$

The recurrence $ε_{n + 1} \leq (1 + h Λ) ε_{n} + B$ is the discrete Gronwall inequality, the difference-equation shadow of the continuous Gronwall lemma used to prove uniqueness for the IVP 02.12.01. For forward Euler, $Φ (t, y, h) = f (t, y)$ is Lipschitz with $Λ = L$ , and a Taylor expansion gives $τ^{n} = \frac{h}{2} y^{''} (ξ_{n}) = O (h)$ , so $p = 1$ and the global error is $O (h)$ , the rate observed numerically in the Beginner worked example.

Bridge. This theorem is the foundational reason "order" is a property of the computed trajectory and not of a single step: the per-step residuals $h τ^{n} = O (h^{p + 1})$ accumulate across $O (1/ h)$ steps, and the discrete Gronwall factor $e^{Λ (T - t_{0})}$ is exactly the amplification budget that keeps the sum at $O (h^{p})$ rather than letting it blow up. The argument builds toward the multistep convergence theory of 43.10.02, where the scalar amplification factor $1 + h Λ$ is replaced by a companion matrix and the clean Gronwall bound must be supplemented by the root condition — this is exactly the point at which consistency stops implying convergence on its own and zero-stability 43.10.03 becomes a separate hypothesis. The structure generalises: "consistency plus stability implies convergence" is the central insight, and it appears again in the Lax-Richtmyer equivalence theorem for finite-difference PDE schemes, where stability becomes uniform power-boundedness of the evolution operator. Putting these together, the one-step theorem is the simplest member of a family in which the bridge is always the same — local accuracy controlled by Taylor matching, propagated under a stability bound that prevents error amplification — and the continuous Gronwall lemma that gives IVP uniqueness is dual to the discrete Gronwall lemma that gives numerical convergence.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that the trapezoidal rule has local truncation error $τ^{n} = - \frac{1}{12} h^{2} y^{'''} (t_{n}) + O (h^{3})$ , hence order $p = 2$ .

Hint

Insert the exact solution into $τ^{n} = \frac{y ( t _{n + 1} ) - y ( t _{n} )}{h} - \frac{1}{2} (y^{'} (t_{n}) + y^{'} (t_{n + 1}))$ and Taylor-expand both $y (t_{n + 1})$ and $y^{'} (t_{n + 1})$ about $t_{n}$ .

Answer

Expand $y (t_{n + 1}) = y + h y^{'} + \frac{h ^{2}}{2} y^{''} + \frac{h ^{3}}{6} y^{'''} + O (h^{4})$ and $y^{'} (t_{n + 1}) = y^{'} + h y^{''} + \frac{h ^{2}}{2} y^{'''} + O (h^{3})$ , all derivatives at $t_{n}$ . Then $\frac{y ( t _{n + 1} ) - y ( t _{n} )}{h} = y^{'} + \frac{h}{2} y^{''} + \frac{h ^{2}}{6} y^{'''} + O (h^{3})$ , while $\frac{1}{2} (y^{'} (t_{n}) + y^{'} (t_{n + 1})) = y^{'} + \frac{h}{2} y^{''} + \frac{h ^{2}}{4} y^{'''} + O (h^{3})$ . Subtracting, the $y^{'}$ and $\frac{h}{2} y^{''}$ terms cancel and $τ^{n} = (\frac{1}{6} - \frac{1}{4}) h^{2} y^{'''} + O (h^{3}) = - \frac{1}{12} h^{2} y^{'''} + O (h^{3})$ . Since $τ^{n} = O (h^{2})$ , the order is $p = 2$ . Rubric: full credit for both Taylor expansions, the cancellation of the order- $0$ and order- $1$ terms, and the coefficient $- \frac{1}{12}$ .

Exercise 6 (medium, symbolic).

Show that for the scalar linear test equation $y^{'} = λ y$ , an $s$ -stage explicit RK method advances by $u^{n + 1} = R (hλ) u^{n}$ with $R$ a polynomial of degree $\leq s$ in $z = hλ$ , and that order $p$ forces $R (z) = 1 + z + \frac{z ^{2}}{2} + \dots + \frac{z ^{p}}{p !} + O (z^{p + 1})$ .

Hint

For $f = λ y$ every stage is an affine function of $u^{n}$ ; collect the result as $R (z) u^{n}$ . Then match against the exact one-step map $u^{n} \mapsto e^{hλ} u^{n}$ .

Answer

With $f (t, y) = λ y$ , stage $i$ reads $k_{i} = λ (u^{n} + h \sum_{j < i} a_{ij} k_{j})$ , a triangular linear system whose solution makes each $k_{i}$ a polynomial in $z = hλ$ times $λ u^{n}$ ; substituting into $u^{n + 1} = u^{n} + h \sum_{i} b_{i} k_{i}$ gives $u^{n + 1} = R (z) u^{n}$ with $R (z) = 1 + z b^{⊤} (I - z A)^{- 1} 1$ . Since $A$ is strictly lower triangular and nilpotent, $(I - z A)^{- 1} = \sum_{m = 0}^{s - 1} (z A)^{m}$ is a polynomial, so $R$ has degree $\leq s$ . The exact map is $u^{n} \mapsto e^{z} u^{n}$ , and order $p$ means the one-step error from exact data is $O (z^{p + 1})$ , i.e. $R (z) - e^{z} = O (z^{p + 1})$ , forcing the first $p + 1$ Taylor coefficients of $R$ to match those of $e^{z}$ : $R (z) = \sum_{k = 0}^{p} z^{k} / k! + O (z^{p + 1})$ . This $R$ is the stability function central to 43.10.04. Rubric: full credit for the affine-stage reduction, the nilpotency argument bounding the degree, and the Taylor match against $e^{z}$ .

Exercise 7 (hard, symbolic).

Derive the four order conditions for a general explicit RK method to have order $3$ in the autonomous scalar case $y^{'} = f (y)$ , by matching the Taylor expansion of $u^{n + 1}$ against that of $y (t_{n} + h)$ through $h^{3}$ .

Hint

Write $y (t_{n} + h) = y + h f + \frac{h ^{2}}{2} f^{'} f + \frac{h ^{3}}{6} (f^{''} f^{2} + (f^{'})^{2} f) + O (h^{4})$ (all at $y = y (t_{n})$ , $f^{'} = \partial_{y} f$ ). Expand the stages $k_{i}$ to the needed order and collect $Φ = \sum_{i} b_{i} k_{i}$ .

Answer

The exact increment is $\frac{y ( t _{n} + h ) - y}{h} = f + \frac{h}{2} f^{'} f + \frac{h ^{2}}{6} (f^{''} f^{2} + (f^{'})^{2} f) + O (h^{3})$ . Expanding the stages: $k_{1} = f$ ; $k_{i} = f + f^{'} (h \sum_{j < i} a_{ij} k_{j}) + \frac{1}{2} f^{''} (h \sum_{j < i} a_{ij} k_{j})^{2} + O (h^{3})$ . To leading orders $\sum_{j < i} a_{ij} k_{j} = c_{i} f + h f^{'} f \sum_{j < i} a_{ij} c_{j} + O (h^{2})$ , using $\sum_{j} a_{ij} = c_{i}$ . Substituting and collecting $Φ = \sum_{i} b_{i} k_{i}$ against the exact increment yields, at orders $h^{0}, h^{1}, h^{2}$ respectively, $$ \sum_i b_i = 1, \qquad \sum_i b_i c_i = \tfrac12, \qquad \sum_i b_i c_i^2 = \tfrac13, \qquad \sum_{i,j} b_i a_{ij} c_j = \tfrac16. $$ The first matches $f$ ; the second matches $\frac{1}{2} f^{'} f$ ; the third and fourth together match the two $h^{2}$ terms $\frac{1}{6} f^{''} f^{2}$ (from $\sum b_{i} c_{i}^{2}$ ) and $\frac{1}{6} (f^{'})^{2} f$ (from $\sum b_{i} a_{ij} c_{j}$ ). These four equations are the order- $3$ conditions. Rubric: full credit for the exact-increment expansion, the stage expansion to second order, and all four conditions with the correct right-hand sides.

Exercise 8 (hard, symbolic).

Prove that the trapezoidal rule converges with global error $O (h^{2})$ on a globally Lipschitz IVP, by checking the hypotheses of the one-step convergence theorem. Address the implicitness: show the increment function $Φ$ is well-defined and Lipschitz for $h$ small.

Hint

The trapezoidal step defines $u^{n + 1}$ implicitly; solve $u^{n + 1} = u^{n} + \frac{h}{2} (f (t_{n}, u^{n}) + f (t_{n + 1}, u^{n + 1}))$ for $u^{n + 1}$ as a fixed point and show the map is a contraction for $h < 2/ L$ , then read off $Φ$ .

Answer

For fixed $u^{n}$ and $h$ , the map $w \mapsto u^{n} + \frac{h}{2} (f (t_{n}, u^{n}) + f (t_{n + 1}, w))$ has Lipschitz constant $\frac{h}{2} L < 1$ whenever $h < 2/ L$ , so by the contraction mapping theorem it has a unique fixed point $u^{n + 1}$ , depending continuously on $u^{n}$ ; this defines $Φ (t_{n}, u^{n}, h) = \frac{u ^{n + 1} - u ^{n}}{h}$ . To see $Φ$ is Lipschitz in $u^{n}$ : if $u^{n + 1}, v^{n + 1}$ solve the implicit equation for data $u^{n}, v^{n}$ , subtracting and using the Lipschitz bound gives $∥ u^{n + 1} - v^{n + 1} ∥ \leq ∥ u^{n} - v^{n} ∥ + \frac{h}{2} L (∥ u^{n} - v^{n} ∥ + ∥ u^{n + 1} - v^{n + 1} ∥)$ , hence $∥ u^{n + 1} - v^{n + 1} ∥ \leq \frac{1 + h L /2}{1 - h L /2} ∥ u^{n} - v^{n} ∥$ , so $Φ$ is Lipschitz with constant $Λ = \frac{L}{1 - h L /2}$ , bounded for $h \leq h_{0} < 2/ L$ . By Exercise 3 the LTE is $O (h^{2})$ , so consistency order $p = 2$ . The one-step convergence theorem then gives $max_{n} ∥ e^{n} ∥ \leq K h^{2}$ . Rubric: full credit for the contraction argument defining $u^{n + 1}$ , the Lipschitz bound on $Φ$ , and the invocation of the convergence theorem with $p = 2$ .

Advanced results Master

The one-step convergence theorem is the elementary stratum. Its reach extends through the algebraic theory of order conditions, the structure of implicit and collocation methods, the asymptotic expansion of the global error that underlies extrapolation, and the distinction between the $h \to 0$ convergence proved above and the fixed- $h$ stability that governs practical computation.

Theorem 1 (Butcher order conditions and the order barriers). An explicit RK method with tableau $(A, b, c)$ has order $p$ if and only if the order conditions $\sum_{i} b_{i} Φ_{i} (t) = 1/ γ (t)$ hold for every rooted tree $t$ with at most $p$ vertices, where $γ (t)$ is the tree's density and $Φ_{i} (t)$ the elementary-weight monomial in the tableau coefficients indexed by $t$ . The count of conditions is the number of rooted trees: $1, 2, 4, 8, 17, \dots$ through orders $1, 2, 3, 4, 5$ . Because an $s$ -stage explicit method has $(2 s) + s$ free coefficients while the conditions proliferate, the attainable order is bounded: an explicit $s$ -stage RK has order $\leq s$ , with equality impossible for $s \geq 5$ (no $5$ -stage explicit method has order $5$ ; order $5$ needs $6$ stages), and order $8$ needs at least $11$ stages — the Butcher barriers ^{[Hairer-Nørsett-Wanner §II.3]}.

Theorem 2 (implicit RK, collocation, and the Gauss methods). A fully implicit $s$ -stage RK method (general, not strictly lower-triangular $A$ ) can reach order $2 s$ . The $s$ -stage Gauss-Legendre collocation method, with nodes $c_{i}$ the roots of the shifted Legendre polynomial of degree $s$ , attains the maximal order $2 s$ and is symplectic; the trapezoidal and implicit-midpoint rules are the $s = 1$ Gauss ( $2 s = 2$ ) and Lobatto/Gauss instances. Collocation reframes the method: $u^{n + 1}$ is the value at $t_{n + 1}$ of the degree- $s$ polynomial $P$ with $P (t_{n}) = u^{n}$ and $P^{'} (t_{n} + c_{i} h) = f (t_{n} + c_{i} h, P (t_{n} + c_{i} h))$ at the $s$ collocation nodes, so the order is the quadrature order of the underlying node set ^{[Hairer-Nørsett-Wanner §II.7]}.

Theorem 3 (global error expansion and Richardson extrapolation). For a method of order $p$ applied to a smooth IVP, the global error admits an asymptotic expansion $u^{n} - y (t_{n}) = h^{p} e_{p} (t_{n}) + h^{p + 1} e_{p + 1} (t_{n}) + \dots$ , where $e_{p}$ solves the linear variational equation $e_{p}^{'} = f_{y} (t, y (t)) e_{p} + ψ_{p} (t)$ with $ψ_{p}$ built from the principal LTE coefficient. The leading $h^{p} e_{p} (t_{n})$ being computable in principle is what makes Richardson extrapolation work: combining the numerical solutions at steps $h$ and $h /2$ as $\frac{2 ^{p} u _{h /2} - u _{h}}{2 ^{p} - 1}$ cancels the $h^{p}$ term and raises the order to $p + 1$ , iterated in the Gragg-Bulirsch-Stoer scheme ^{[LeVeque §5.5]}.

Theorem 4 (A-stability obstruction for one-step vs. multistep). The stability function $R (z)$ of an explicit RK method is a polynomial, so $∣ R (z) ∣ \to \infty$ as $∣ z ∣ \to \infty$ : no explicit method can be A-stable, and explicit one-step methods inherit a bounded absolute-stability region. Implicit RK methods have rational $R (z) = 1 + z b^{⊤} (I - z A)^{- 1} 1 = det (I - z A + z 1 b^{⊤}) / det (I - z A)$ , and A-stability is the condition $∣ R (z) ∣ \leq 1$ on the left half-plane $ℜ z \leq 0$ , characterised for the diagonal Padé approximants of $e^{z}$ realised by the Gauss methods. This is the one-step face of the stiffness theory whose multistep form is the Dahlquist second barrier 43.10.05.

Theorem 5 (B-convergence and the one-sided Lipschitz condition). The convergence theorem's constant $K = \frac{e ^{Λ (T - t_{0})} - 1}{Λ} C$ degrades catastrophically when the Lipschitz constant $L$ is large, as for stiff systems. Replacing the Lipschitz bound by the one-sided Lipschitz condition $⟨ f (t, y) - f (t, z), y - z ⟩ \leq ν ∥ y - z ∥^{2}$ with $ν$ moderate (possibly $ν \leq 0$ ) gives B-convergence: for algebraically stable implicit RK methods the global error bound depends on $ν$ rather than $L$ , so the estimate stays meaningful in the stiff limit $L \to \infty$ . This is the rigorous form of the observation that implicit methods, not explicit ones, are the right tool when $f$ has widely separated time scales ^{[Hairer-Nørsett-Wanner §II.1]}.

Synthesis. The one-step convergence theorem is the foundational reason numerical integration of an IVP is a controlled approximation rather than an open-ended drift: local accuracy is fixed by Taylor matching of the increment function $Φ$ against $f$ , measured by the order $p$ of the local truncation error, and that local accuracy is propagated to a global $O (h^{p})$ bound by the discrete Gronwall stability estimate. The central insight is that this is one mechanism with two halves — consistency and stability — and the entire chapter is the systematic refinement of each half: the order conditions of Butcher's rooted-tree algebra make consistency an exact combinatorial calculus, and the absolute-stability and zero-stability theories make stability a precise spectral condition. This generalises directly: the same consistency-plus-stability template, with the scalar amplification factor $1 + h Λ$ promoted to the companion matrix of a multistep method 43.10.02, produces the Dahlquist equivalence theorem 43.10.03, and promoted to the evolution operator of a discretised partial differential equation produces the Lax-Richtmyer equivalence theorem.

Putting these together, the convergence theorem proved here is dual to the Picard-Lindelöf uniqueness theorem 02.12.01 — the continuous Gronwall lemma giving uniqueness of the exact flow is exactly the discrete Gronwall lemma giving convergence of the numerical flow — and the bridge from the elementary Euler bound to the full stiffness theory is the recognition that for large Lipschitz constants the convergence constant must be re-derived from a one-sided bound, which is precisely why the implicit methods of this unit, not the explicit ones, survive the passage to stiff problems 43.10.05. The global error expansion completes the picture: the leading $h^{p}$ term is itself the solution of a variational equation, so the error is not merely bounded but asymptotically structured, and that structure is what extrapolation exploits to manufacture higher order from the same family of methods.

Full proof set Master

Proposition 1 (discrete Gronwall inequality). Let $(ε_{n})_{n \geq 0}$ be non-negative reals satisfying $ε_{n + 1} \leq (1 + a) ε_{n} + b$ for constants $a > 0$ , $b \geq 0$ . Then $ε_{n} \leq e^{na} ε_{0} + \frac{e ^{na} - 1}{a} b$ for all $n \geq 0$ .

Proof. Unrolling the recurrence, $ε_{n} \leq (1 + a)^{n} ε_{0} + b \sum_{m = 0}^{n - 1} (1 + a)^{m} = (1 + a)^{n} ε_{0} + b \frac{( 1 + a ) ^{n} - 1}{a}$ , the geometric sum being valid since $a > 0$ . The inequality $1 + a \leq e^{a}$ (from the convexity of $e^{x}$ , or the series $e^{a} = 1 + a + a^{2} /2 + \dots \geq 1 + a$ ) gives $(1 + a)^{n} \leq e^{na}$ . Substituting into both terms, and using that the map $x \mapsto \frac{x - 1}{a}$ is increasing so $(1 + a)^{n} - 1 \leq e^{na} - 1$ , yields $ε_{n} \leq e^{na} ε_{0} + \frac{e ^{na} - 1}{a} b$ . $□$

Proposition 2 (order of forward Euler). For an IVP with $y \in C^{2}$ , forward Euler has local truncation error $τ^{n} = \frac{h}{2} y^{''} (ξ_{n})$ for some $ξ_{n} \in (t_{n}, t_{n + 1})$ , hence order $p = 1$ ; if $f$ is globally Lipschitz the global error is $O (h)$ .

Proof. By Taylor's theorem with Lagrange remainder, $y (t_{n + 1}) = y (t_{n}) + h y^{'} (t_{n}) + \frac{h ^{2}}{2} y^{''} (ξ_{n})$ for some $ξ_{n} \in (t_{n}, t_{n + 1})$ . The forward-Euler increment is $Φ (t_{n}, y (t_{n}), h) = f (t_{n}, y (t_{n})) = y^{'} (t_{n})$ . Hence $$ \tau^n = \frac{y(t_{n+1}) - y(t_n)}{h} - y'(t_n) = \frac{1}{h}\Big(h y'(t_n) + \tfrac{h^2}{2}y''(\xi_n)\Big) - y'(t_n) = \tfrac{h}{2}y''(\xi_n). $$ With $y^{''} = \frac{d}{d t} f (t, y (t)) = f_{t} + f_{y} f$ bounded on the compact trajectory, $∥ τ^{n} ∥ \leq \frac{h}{2} M = O (h)$ , so $p = 1$ . Forward Euler has $Φ = f$ with Lipschitz constant $Λ = L$ , so the one-step convergence theorem gives $max_{n} ∥ e^{n} ∥ \leq \frac{e ^{L (T - t_{0})} - 1}{L} \cdot \frac{M}{2} h = O (h)$ . $□$

Proposition 3 (existence and Lipschitz continuity of the implicit-Euler increment). If $f$ is globally Lipschitz with constant $L$ and $h < 1/ L$ , the backward-Euler equation $u^{n + 1} = u^{n} + h f (t_{n + 1}, u^{n + 1})$ has a unique solution $u^{n + 1}$ , and the increment function $Φ$ it defines is Lipschitz in $u^{n}$ with constant $Λ = \frac{L}{1 - h L}$ .

Proof. Fix $u^{n}$ . The map $g (w) = u^{n} + h f (t_{n + 1}, w)$ satisfies $∥ g (w) - g (w^{'}) ∥ = h ∥ f (t_{n + 1}, w) - f (t_{n + 1}, w^{'}) ∥ \leq h L ∥ w - w^{'} ∥$ , a contraction since $h L < 1$ . By the Banach fixed-point theorem $g$ has a unique fixed point $u^{n + 1}$ , which is the backward-Euler step. For Lipschitz continuity of $Φ$ : let $u^{n + 1}, v^{n + 1}$ solve the equation for data $u^{n}, v^{n}$ . Subtracting, $u^{n + 1} - v^{n + 1} = (u^{n} - v^{n}) + h (f (t_{n + 1}, u^{n + 1}) - f (t_{n + 1}, v^{n + 1}))$ , so $∥ u^{n + 1} - v^{n + 1} ∥ \leq ∥ u^{n} - v^{n} ∥ + h L ∥ u^{n + 1} - v^{n + 1} ∥$ , giving $∥ u^{n + 1} - v^{n + 1} ∥ \leq \frac{1}{1 - h L} ∥ u^{n} - v^{n} ∥$ . Since $Φ = (u^{n + 1} - u^{n}) / h = f (t_{n + 1}, u^{n + 1})$ , $∥Φ (t_{n}, u^{n}, h) - Φ (t_{n}, v^{n}, h) ∥ = ∥ f (t_{n + 1}, u^{n + 1}) - f (t_{n + 1}, v^{n + 1}) ∥ \leq L ∥ u^{n + 1} - v^{n + 1} ∥ \leq \frac{L}{1 - h L} ∥ u^{n} - v^{n} ∥$ . $□$

Proposition 4 (RK4 has order four on the linear test equation). The classical RK4 stability function is $R (z) = 1 + z + \frac{z ^{2}}{2} + \frac{z ^{3}}{6} + \frac{z ^{4}}{24}$ , matching $e^{z}$ through $z^{4}$ ; hence on $y^{'} = λ y$ the method is order $4$ .

Proof. For $f (t, y) = λ y$ with $z = hλ$ , compute the stages: $k_{1} = λ u^{n}$ ; $k_{2} = λ (u^{n} + \frac{h}{2} k_{1}) = λ u^{n} (1 + \frac{z}{2})$ ; $k_{3} = λ (u^{n} + \frac{h}{2} k_{2}) = λ u^{n} (1 + \frac{z}{2} + \frac{z ^{2}}{4})$ ; $k_{4} = λ (u^{n} + h k_{3}) = λ u^{n} (1 + z + \frac{z ^{2}}{2} + \frac{z ^{3}}{4})$ . Then $$ u^{n+1} = u^n + \tfrac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4) = u^n\Big[1 + \tfrac{z}{6}\big(1 + 2(1 + \tfrac{z}{2}) + 2(1 + \tfrac{z}{2} + \tfrac{z^2}{4}) + (1 + z + \tfrac{z^2}{2} + \tfrac{z^3}{4})\big)\Big]. $$ The bracket inside is $6 + 3 z + z^{2} + \frac{z ^{3}}{4}$ , so $u^{n + 1} = u^{n} [1 + \frac{z}{6} (6 + 3 z + z^{2} + \frac{z ^{3}}{4})] = u^{n} (1 + z + \frac{z ^{2}}{2} + \frac{z ^{3}}{6} + \frac{z ^{4}}{24})$ . Thus $R (z) = \sum_{k = 0}^{4} z^{k} / k!$ , which agrees with $e^{z} = \sum_{k \geq 0} z^{k} / k!$ through order $z^{4}$ ; the one-step error $R (z) - e^{z} = - z^{5} /120 + O (z^{6}) = O (h^{5})$ , giving consistency order $p = 4$ and, by the convergence theorem, global error $O (h^{4})$ . $□$

Connections Master

The linear multistep methods of 43.10.02 retain the local-truncation-error and order framework defined here but replace the single-step recurrence by an $r$ -step recurrence; the consistency conditions become conditions on the first and second characteristic polynomials $ρ, σ$ , and the clean discrete-Gronwall stability bound of the one-step theorem no longer holds automatically. That unit is where consistency and convergence first come apart, motivating the separate zero-stability hypothesis; this unit supplies the LTE/order definitions it specialises.
The zero-stability and Dahlquist equivalence theorem of 43.10.03 is the multistep generalisation of the one-step convergence theorem proved here: "consistency plus stability implies convergence" reappears with the scalar amplification factor $1 + h Λ$ promoted to a companion matrix whose powers must stay bounded (the root condition). The order- $p$ global-error conclusion is identical in form; only the stability ingredient changes from a Lipschitz bound to a spectral condition.
The absolute-stability theory of 43.10.04 takes the stability function $R (z) = 1 + z + \dots$ derived here for the linear test equation $y^{'} = λ y$ and studies the region ${z : ∣ R (z) ∣ \leq 1}$ , which governs the maximum stable step for a fixed problem rather than the $h \to 0$ convergence. The explicit-RK stability polynomials computed in this unit's proof set are exactly the objects whose sublevel sets that unit maps.
The stiffness and A-stability theory of 43.10.05 explains why the implicit methods introduced here — backward Euler and the trapezoidal rule — are indispensable: their rational stability functions can satisfy $∣ R (z) ∣ \leq 1$ on the entire left half-plane, which no explicit RK polynomial can. The Dahlquist second barrier there limits the order of A-stable linear multistep methods, with the trapezoidal rule of this unit as the optimal second-order A-stable member.
The continuous existence-uniqueness theory of 02.12.01 is the input the convergence theorem assumes: the Picard-Lindelöf theorem guarantees the exact solution $y (t)$ that the local truncation error is defined against, and the continuous Gronwall lemma used in that uniqueness proof is the exact analogue of the discrete Gronwall lemma driving the convergence proof here. The matrix-exponential solution of linear systems in 02.06.03 is the closed form of the linear test problem $y^{'} = λ y$ used throughout to read off stability functions.

Historical & philosophical context Master

Euler's method appears in Leonhard Euler's Institutiones calculi integralis (1768-1770) ^{[Euler 1768]}, where the polygonal advance $u^{n + 1} = u^{n} + h f (t_{n}, u^{n})$ is introduced to approximate solutions of differential equations that resist closed-form integration; the method and its first-order error were understood by Euler as a limiting process recovering the exact solution as $h \to 0$ . Augustin-Louis Cauchy turned the polygonal construction into the first rigorous existence proof for the IVP in his 1820s-1830s lectures, the Cauchy-Euler method later completed by Lipschitz (1876) and given its fixed-point form by Picard (1890) and Lindelöf (1894), so the numerical scheme and the existence theorem share a single origin.

The higher-order one-step methods are due to Carl Runge (1895) ^{[Runge 1895]}, who introduced the idea of sampling the slope at interior points to cancel low-order error terms, and Wilhelm Kutta (1901) ^{[Kutta 1901]}, who systematised the order conditions and exhibited the classical fourth-order tableau now bearing both names; Karl Heun (1900) gave the second-order improved-Euler method in the same period. The algebraic theory of order — the rooted-tree calculus that turns the Taylor-matching conditions into a combinatorial enumeration and proves the order barriers — is the work of John Butcher, beginning with his 1963 paper on the coefficients of RK processes and developed into the B-series framework now standard. The unifying convergence-equivalence viewpoint, that consistency plus stability is equivalent to convergence, was crystallised for ordinary differential equations by Germund Dahlquist (1956) and for partial differential equations by Peter Lax and Robert Richtmyer (1956) in the same year, the structural parallel that organises the rest of this chapter.

Bibliography Master

@book{leveque2007fdm,
  author    = {LeVeque, Randall J.},
  title     = {Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems},
  publisher = {Society for Industrial and Applied Mathematics (SIAM)},
  year      = {2007}
}

@book{sulimayers2003,
  author    = {S\"{u}li, Endre and Mayers, David F.},
  title     = {An Introduction to Numerical Analysis},
  publisher = {Cambridge University Press},
  year      = {2003}
}

@book{hnw1993,
  author    = {Hairer, Ernst and N\o{}rsett, Syvert P. and Wanner, Gerhard},
  title     = {Solving Ordinary Differential Equations I: Nonstiff Problems},
  edition   = {2},
  series    = {Springer Series in Computational Mathematics},
  volume    = {8},
  publisher = {Springer-Verlag},
  year      = {1993}
}

@book{butcher2016,
  author    = {Butcher, John C.},
  title     = {Numerical Methods for Ordinary Differential Equations},
  edition   = {3},
  publisher = {John Wiley \& Sons},
  year      = {2016}
}

@book{euler1768institutiones,
  author    = {Euler, Leonhard},
  title     = {Institutiones calculi integralis, Volumen Primum},
  publisher = {Impensis Academiae Imperialis Scientiarum},
  address   = {Petropoli (St. Petersburg)},
  year      = {1768}
}

@article{runge1895,
  author  = {Runge, Carl},
  title   = {\"{U}ber die numerische Aufl\"{o}sung von Differentialgleichungen},
  journal = {Mathematische Annalen},
  volume  = {46},
  number  = {2},
  year    = {1895},
  pages   = {167--178}
}

@article{kutta1901,
  author  = {Kutta, Wilhelm},
  title   = {Beitrag zur n\"{a}herungsweisen Integration totaler Differentialgleichungen},
  journal = {Zeitschrift f\"{u}r Mathematik und Physik},
  volume  = {46},
  year    = {1901},
  pages   = {435--453}
}

@article{butcher1963,
  author  = {Butcher, John C.},
  title   = {Coefficients for the study of Runge-Kutta integration processes},
  journal = {Journal of the Australian Mathematical Society},
  volume  = {3},
  number  = {2},
  year    = {1963},
  pages   = {185--201}
}

@article{dahlquist1956,
  author  = {Dahlquist, Germund},
  title   = {Convergence and stability in the numerical integration of ordinary differential equations},
  journal = {Mathematica Scandinavica},
  volume  = {4},
  year    = {1956},
  pages   = {33--53}
}

Prerequisites

02.12.01
02.06.03
02.05.05

Tier anchors

beginner: LeVeque 2007 *Finite Difference Methods for Ordinary and Partial Differential Equations* (SIAM) §5.1-5.2 (the forward-Euler picture and the slope-field intuition); Süli-Mayers 2003 *An Introduction to Numerical Analysis* (Cambridge) §12.1-12.2 (Euler's method as the elementary first step)
intermediate: Süli-Mayers 2003 *An Introduction to Numerical Analysis* (Cambridge) §12.2-12.4 (one-step methods, truncation error, the convergence theorem for Euler) and §12.5 (Runge-Kutta); LeVeque 2007 (SIAM) §5.2-5.6, §6.2-6.3 (LTE, order, and the explicit RK families)
master: Hairer-Nørsett-Wanner 1993 *Solving Ordinary Differential Equations I: Nonstiff Problems* 2e (Springer) §II.1-II.3 (the general one-step method, the order conditions, Butcher's rooted-tree theory at a high level); Butcher 2016 *Numerical Methods for Ordinary Differential Equations* 3e (Wiley) Ch. 2-3 (the algebraic theory of order); LeVeque 2007 (SIAM) Ch. 5-6 (consistency, zero-stability, and convergence for one-step and linear multistep methods)

References

LeVeque, R. J. — Finite Difference Methods for Ordinary and Partial Differential Equations: Steady-State and Time-Dependent Problems · SIAM 2007. Chapter 5 sets up the IVP $u'(t)=f(u(t),t)$ and the one-step framework; §5.2 defines the local truncation error $\tau^n$ by inserting the exact solution into the difference formula, §5.3-5.4 develop consistency, zero-stability, and the convergence theorem for one-step methods (global error $=O(h^p)$ from a consistency order $p$ plus the Lipschitz stability bound via the discrete Gronwall inequality). Chapter 6 gives forward/backward Euler, the trapezoidal rule and the explicit Runge-Kutta families with the classical fourth-order method and its order conditions.
Süli, E. & Mayers, D. F. — An Introduction to Numerical Analysis · Cambridge University Press 2003. Chapter 12 derives Euler's method from the Taylor expansion of the exact solution, defines the truncation error and the order of a one-step method, and proves the convergence theorem $\max_n |y(t_n)-u^n| \le C h$ for Euler under a global Lipschitz condition using the Gronwall/discrete-Gronwall argument; §12.5 introduces the general one-step increment function $\Phi(t,u,h)$, consistency as $\Phi(t,u,0)=f(t,u)$, the trapezoidal and improved-Euler schemes, and the explicit Runge-Kutta family with its order conditions through fourth order.
Hairer, E., Nørsett, S. P. & Wanner, G. — Solving Ordinary Differential Equations I: Nonstiff Problems · Springer, 2nd revised edition 1993. §II.1 collects Euler, the Runge-Kutta methods and their Butcher tableaux; §II.2-II.3 give the order conditions via the rooted-tree / B-series algebra, the classical RK4, embedded pairs, and the precise order-$p$ Taylor-matching conditions on the tableau coefficients $(A,b,c)$.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m