You have written Euler, three of its variants, RK4 and RK45, and you have seen that RK4 beats Euler by a mile. Nothing in your code said why, or by how much, or when the advantage disappears. This lesson supplies the vocabulary and the measurements: local error, global error and order. It also gives the test that every serious fluid or flight code is checked with: halve the step and see whether the error shrinks by the factor the theory promises.
Earlier lessons supply the tools: Taylor expansions (2.4 Taylor Series in One and Several Variables), the first look at Euler’s error in 3.2 Direction Fields & Euler's Method Revisited, and the Lipschitz constant from 3.7 Existence & Uniqueness. The story: what one step costs, how steps add up, and what happens as goes to zero on a real computer.
Transcript
- RK4 beats Euler by a mile. Why, and by how much? Two errors answer that. The local error is the miss of one step that starts exactly on the true curve. The global error is the miss at the end of a whole run, whose later steps start off the curve.
- Test problem: y prime equals minus two t y, exact solution e to the minus t squared. Start on the curve at t equals one, take one step of 0.05, and compare with the exact value. The misses run from 9.5 times ten to the minus four for Euler to 3.3 times ten to the minus eight for RK4.
- Halve the step to 0.025 and the misses shrink by 4.1, 8.1 and 33.2: near two squared, two cubed and two to the fifth. A method of order p has one-step error proportional to h to the p plus one.
- Now run Euler to t equals one. Each step plants a local error d k, and the equation carries it forward. The slope of f in y is minus two t, so a gap planted at t k shrinks by e to the minus T squared minus t k squared. Call that G k: it runs from 0.37 up to one.
- Weight each local error by G k and add: at h equals 0.05 that gives 6.459 times ten to the minus three, against an actual 6.505, within about one percent. Unweighted it is 1.896 times ten to the minus two, nearly three times too big: the equation damps errors, early ones most. Global error is the local errors filtered by the equation.
- Now the global error at t equals one, halving h from 0.1 four times, on log-log axes. Each method falls on a straight line, parallel to its dashed reference with slope one, two or four.
- The order is log base two of E at h over E at h over two: Euler's drifts from 1.09 to 1.01, Heun's from 1.96 to 2.00, RK4's sits at four. Local error h to the p plus one becomes global error h to the p: about one over h steps, one power lost.
- Smaller h does not always help. Round the stored state to a 32-bit float after every step. Each rounding is a fresh error up to six times ten to the minus eight, whatever h, and halving h doubles their number. For RK4 the dashed float32 curve leaves the solid float64 one at h equal 3.2 times ten to the minus two, then wanders.
- Euler and Heun do the same, later: float32 leaves Euler at 1.8 times ten to the minus five and Heun at 3.2 times ten to the minus four. Higher order, larger h: its truncation error falls so fast it sinks below round-off early.
- At the smallest steps we ran, RK4 reaches 8.3 times ten to the minus sixteen in float64 but only 5.6 times ten to the minus seven in float32. Past the floor, refining hurts: stop where the error stops falling.
- Now a trap. Put the exact solution into this two-step scheme: what is left, over h to the fourth, heads to one sixth. Local error h to the fourth: third order, better on paper than Heun. It is consistent.
- Run it on y prime equals minus y. At t equals one the error is 7.045 for h equals 0.1, 4.652 million for 0.05, 2.883 times ten to the nineteen for 0.025: finer is worse, and not round-off, since this is 80-digit arithmetic. One root is near one, the true solution; the other, near minus five, multiplies any error by about five every step. Consistent, not stable: no convergence.
- Recap: local error is one step from the curve; global error is those errors filtered by the equation. Order p: local h to the p plus one, global h to the p, read from a log-log slope. Round-off makes the error U-shaped, with the floor at larger h for higher order. Consistency plus stability gives convergence. Next: the Euler family.
Two different errors
Write one step of a method as a map: . For Euler, . Two questions can be asked about its accuracy, and they have different answers.
Local truncation error (LTE): start the step on the exact solution, so , take one step, and measure the miss:
Global error: run the whole computation from to and compare with the exact solution there, .
The local error is a clean idea and a slightly fictional one: a step that begins exactly on the true curve happens only once, at the start. Every later step starts from a numerical point already off the curve, the equation does something to that earlier error, and the new step adds its own on top. So the global error is not the sum of the local errors, and the rest of this lesson is the story of the difference.
Where the order comes from
The cleanest laboratory is . Put . One step multiplies by a polynomial in :
(For Heun: , , so ; RK4 is the same bookkeeping with four stages.) The exact step multiplies by . Each method copies the Taylor series of and stops. The first term it leaves out is the local error:
A method has order when it reproduces the first Taylor terms of the true step. The mismatch is then proportional to . The same holds for nonlinear , where the matching uses the multivariable chain rule (2.4 Taylor Series in One and Several Variables, and 4.3 Runge–Kutta Methods & Butcher Tableaux for the general family). For Heun and RK4 the leading constant on a general is a combination of derivatives, so only the power of carries over from the linear case; for Euler the constant does too: .
We watch this on a running example:
The cell below prints four labelled blocks, A to D, which we read in turn. Block A is the one-step error at for three methods started on the exact curve. For Euler, equals at , so the Taylor estimate is at .
Block A: the measured Euler error at is , against the Taylor estimate . Halving divides the one-step error by , and for Euler, Heun and RK4, which is up to the next Taylor term’s small correction. That is local error made visible.
From local to global: the error is carried, not just added
Block B runs the whole computation, with halved four times. Euler’s global error at goes from to , Heun’s from to , and RK4’s from to . The printed orders are for Euler, for Heun and for RK4. So local error becomes global error : one power of is lost.
Why one power? Taking steps adds about local errors of size , and . But adding them naively is wrong: the equation carries each error from where it was planted to the final time. A step at plants ; the solution through the wrong point is a neighbour of the true one, and the gap obeys the variational equation, the linearization of the ODE (2.2 Linearization, the Chain Rule & the Jacobian): . Here , so
Call that survival factor (it is the sensitivity of to a nudge at ). Then, to first order,
The global error is the sum of local errors, each multiplied by the factor the ODE applies between that step and the end. Block C tests this on Euler. At the actual error is . The plain sum of local errors gives , nearly three times too large because this equation damps errors (every is below ). With the factors the sum is , within one percent; at and the weighted sums are and against actual errors of and .
The Lipschitz bound, in plain terms
The variational picture needs the exact solution’s sensitivity. Often all we know is a speed limit: from 3.7 Existence & Uniqueness, if , two solutions separate at most at rate , so one Euler step stretches a gap to at most . Split the new global error into a fresh local error plus the old error carried forward: . The first bracket is at most and the second at most times the old error, so the global error obeys
Unrolling it (the sum of a geometric series, and then ):
For Euler, with , which gives the standard bound
For a method of order replace the numerator by and the result is . Three things to take from it:
- The power of is right. One factor of cancels the terms.
- The constant is exponential in , because solutions can separate that fast. That is why long runs of sensitive systems cannot be trusted at any step size.
- It is a bound, not an estimate. For on we can take (the maximum of is at ) and . At the bound is against an actual , a factor of : the bound assumes the worst case and this equation forgives errors. For the growing twin the bound is against an actual , only times too big. (Both printed in block C.)
Order on a log-log plot
If , then : on a log-log plot a method of order is a straight line of slope , and only moves it up or down. That is why convergence studies are plotted that way, and why the order from two runs is
The lab below runs the three methods on three equations (final time for , for the logistic equation from , for the oscillator ), sweeps over a grid with four points per decade, and fits a line by least squares to the float64 points inside a shaded window.
Things to try (all numbers refer to the default equation ):
- With the default window to (five grid points) the fitted slopes are for Euler, for Heun and for RK4. Euler reads because is not yet small: the next error term, proportional to , still adds a little. With the window at to it reads .
- Move the window to the right, to . Euler’s slope becomes , Heun’s and RK4’s : outside the asymptotic range the slope is not the order.
- For RK4, put the window at to : the slope reads , because the float64 errors there (about to ) brush double precision’s own floor.
The other end: round-off and the floor
So far smaller always helps. On a computer it stops helping, because each step also makes an arithmetic error: rounding the stored state by a relative amount up to is a second kind of local error, of size about and independent of . Errors from steps pile up, so the round-off part of the global error is somewhere between about (if the roundings are random and partly cancel) and (if they all push the same way), and either way it grows as shrinks. Take the aligned worst case as a simple model and add the two contributions:
The sum has a minimum: a U-shaped curve, the ODE twin of the finite-difference picture in 2.4 Taylor Series in One and Several Variables.
Double-precision round-off () needs enormous step counts to show in an ODE solver. So the lab reruns every sweep with the state stored in single precision: after each step every component is rounded to the nearest 32-bit float (relative size at most ) while the arithmetic inside the step stays in double. That models storage round-off; it is not a bit-exact emulation of a GPU. The red curve is whatever that rounding produces. It is deterministic but irregular, so no slope is fitted to it.
On with the default settings, the red float32 curve leaves the blue float64 curve (error more than twice as large) at:
| method | float32 leaves the line at | at the smallest grid : float64 error | float32 error |
|---|---|---|---|
| Euler | (at ) | ||
| Heun | (at ) | ||
| RK4 | (at ) |
The higher the order, the larger the at which the floor appears. In the model above, truncation falls so quickly for RK4 that it is below the round-off level by , while Euler’s falls so slowly that it only meets that level near , with steps. Setting the two terms equal gives a crossing at , which increases with ; the table is the measured version. Note the last two columns for RK4: past its crossing, refining buys nothing in float32 (the error at the smallest step is , while the float64 run reaches ), and the float64 curve itself flattens near for the smallest steps, which is double precision’s own floor on this problem.
Consistency, stability, convergence
Put the pieces into three words.
- A scheme is consistent if its local error shrinks faster than : as (order ). It says the scheme is aiming at the right equation.
- A scheme is stable (in the sense that matters here, called zero-stability for multistep methods) if errors planted at each step are not magnified without limit as : the growth factor stays bounded, like above.
- A scheme converges if the global error goes to zero as .
The idea, and it is only an idea here, not a proof: consistency plus stability gives convergence, at the order of the consistency. The proof has the shape of the bound above: global error is at most (bounded growth factor) times (sum of local errors). For one-step methods on Lipschitz problems stability is free, so consistent means convergent. The same pattern is the Dahlquist equivalence theorem for multistep methods and the Lax–Richtmyer equivalence theorem for linear PDE schemes on a grid (standard textbook results, stated without proof).
Why bother with the stability half? Because consistency alone can be useless. Here is a two-step scheme, one that uses the two previous values (see 4.6 Multistep Methods):
Put the exact solution into the formula and measure what is left over (the residual). Block D prints residual at , heading to : the terms through cancel and the left-over is . Local error : this is a third-order consistent scheme, better on paper than Heun. Block D then runs it on with exact starting values and reports the error at .
At the error is , and .
The error grows as shrinks: no convergence. The recurrence runs in 80-digit decimal arithmetic, so this is not round-off; the seed is the scheme’s own truncation error, of size about .
The mechanism is in the recurrence. On it reads for the growth factor per step. As this becomes , with roots and . The root near is the real solution (, , at ). The root near is a parasitic solution (, , ): any error component that lands in it is multiplied by about at every step, and the truncation error of the first steps puts a little there. After steps the damage is about times a small seed, which grows faster as shrinks. The growth factor is not bounded as : exactly the stability property that fails.
This differs from the stability you met with in 3.2 Direction Fields & Euler's Method Revisited, where is fixed and Euler blows up once exceeds . That is absolute stability, a statement about one particular (4.2 The Euler Family: Forward, Backward, Heun & Midpoint, 4.5 Stability Regions & Stiffness). Zero-stability is the statement about . A good method needs both.
Exercise: measure the order yourself
Do what a solver developer does on day one: measure the order from error ratios. The equation is the logistic equation , , exact solution , run to . Implement the global error at , the observed order from a list of halving step sizes, and the local exponent from one-step errors started on the exact curve.
Once it works, notice that the local exponents are one more than the global orders (about against ).
Problems
A fluid solver has error (made-up constants, but the structure is typical: first order in time, second order in space). Start from .
- Compute at , and , and the two error ratios. What order would you read off, and what order do you expect in the limit?
- Instead halve only from the start: compute and its ratio to . What does that say about refining only the space grid?
Show worked solution
- ; ; . The ratios are and . The observed orders are and . In the limit the time term dominates (it falls like , the space term like ), so the ratio tends to and the observed order to , not .
- , a ratio of . The time term is untouched, so refining space alone can never get below it. You must refine the dominant term.
For , on , Euler gives .
- Show that the actual error is about for small .
- Find and and write the bound .
- Find the limit of bound over actual as ; evaluate it for .
Show worked solution
- , so . The error is .
- , so . The solution is , so and . The bound is .
- Dividing, bound over actual tends to . For that is . The bound is only a single-digit factor too large when errors really grow (compare for the decaying equation in the lesson).
Model the total error of a method of order as , with the accumulated round-off per unit step.
- Find the minimizing step and the minimum error in terms of , and .
- Take and . Evaluate and for and , and compare.
Show worked solution
- gives , so . At that point , hence .
- For : , so and . For : , so and . The fourth-order method has its best step about times larger (cheaper) and its best error about times smaller. The constants are invented, but the direction matches the lab: the higher the order, the larger .
What comes next
Next: 4.2 The Euler Family: Forward, Backward, Heun & Midpoint (implicit variants and absolute stability), 4.3 Runge–Kutta Methods & Butcher Tableaux (order conditions) and 4.4 Adaptive Step Size & RK45 (estimate on the fly and choose to keep it at a target).
Key Takeaways
- Local truncation error is the miss of one step started on the exact solution; global error is what a whole run produces. It is not the sum of the local errors: the ODE multiplies each one by a growth factor on its way to the end.
- A method of order matches the first Taylor terms of the true step: local error proportional to , global error to , because about steps add up.
- On a log-log plot error against is a line of slope ; the order is , valid only inside the asymptotic range.
- The Lipschitz bound gets the power of right and the constant too large (by for a decaying and for a growing equation here); is why long runs of sensitive systems cannot be trusted at any .
- Round-off adds an error that grows as shrinks, so total error is U-shaped; higher order moves the bottom to a larger .
- Consistency plus stability gives convergence; a consistent third-order two-step scheme with a parasitic root near diverges as .
- In a refinement study, refine every error source together and expect the lowest order present to dominate once is small.