You have already coded forward Euler, backward Euler, the trapezoidal rule with its explicit cousin Heun, and the midpoint method. This lesson is the why. Where do the formulas come from? Why do two need a solve at every step, and what does that buy? And the question that decides what a fluid or flight code can use: at what step size does each one stay sane?
It builds on 4.1 Local Error, Global Error & Order (order, local error) and the Euler picture of 3.2 Direction Fields & Euler's Method Revisited. Oversized steps on nonlinear problems appeared in 3.8 Autonomous Equations, Equilibria & Stability: Euler on the logistic equation turns into the logistic map, and RK4 can invent steady states. Here we study the same failure on a linear equation, where everything can be computed exactly.
Transcript
- Four methods, one idea. Over one step, y gains the integral of g, the slope along the true solution. We cannot do that integral exactly, because g depends on the unknown solution, so each method swaps in a quadrature rule.
- Left rectangle: forward Euler. Right rectangle: backward Euler. Trapezoid: the trapezoidal rule. Middle rectangle: the midpoint method, using half an Euler step to find y there. The trapezoid overshoots by 0.104, the midpoint undershoots by about half that. Rules exact for lines leave h cubed errors, for constants h squared.
- Backward Euler and the trapezoid have y n plus one on both sides: each step is an equation. Take y prime equals minus y squared, y one, h one: G of w is w minus one plus w squared, root 0.618034. Newton jumps to where each tangent crosses zero: 1, 0.666667, 0.619048, 0.618034, roughly squaring the error each pass.
- Fixed-point iteration sets w to one minus w squared: no derivative, no solve. From one it goes 1, 0, 1, 0, forever. Each pass multiplies the error by the update's slope at the root, minus 1.236, bigger than one in size. It converges only if h times f y is below one in size: a step limit again.
- Heun breaks the circle. An Euler predictor lands at 0.2, on slope minus one; the slope there is minus 0.04. The trapezoid's average slope, minus 0.52, lands at 0.584, against the exact 0.5556. That is one fixed-point pass from the Euler value. Order two survives; the implicit equation is lost.
- On the test equation, y prime equals lambda y, one step multiplies by R of z, with z equal to h lambda. Forward Euler: one plus z. Backward Euler: one over one minus z. Trapezoid: one plus z over two, over one minus z over two. Heun and midpoint, both: one plus z plus z squared over two. Halving z shrinks the gap to e to the z by 4, 4, 8, 8.
- Heun and midpoint agree on the test equation, and only there. In units of h cubed, y prime equals minus y gives minus 0.1661 for both. For 3 t squared, no predictor error: Heun minus 0.5, midpoint plus 0.25. For minus y squared: minus 0.4877 and minus 0.7377, near the formulas' minus 0.5 and minus 0.75.
- Plot R against e to the z, with size one dashed. Forward and backward Euler peel away first, their gap starting at z squared; the trapezoid and Heun hold on to z cubed. At z equals minus two, forward Euler reaches minus one and Heun plus one, and both keep going.
- Forward Euler on y prime equals minus ten y, to t equals three. At h 0.05 each step multiplies by 0.5: smooth decay to 8.67 times ten to the minus 19. At 0.15, minus 0.5: decay to 9.54 times ten to the minus 7, flipping sign. At 0.2, minus one: plus or minus one forever. At 0.25, minus 1.5: 130.
- At h 0.25, backward Euler multiplies by 0.2857 and ends at 2.96 times ten to the minus 7. The trapezoid, minus 0.1111, alternates to 3.54 times ten to the minus 12. Heun multiplies by 1.625 and reaches 339: its degree-two polynomial R exceeds one in size beyond z equals minus two.
- This is the sign and size of R. The step sizes sit at z equals minus ten h. Forward Euler: smooth to minus one, sign flips to minus two, then growth. Backward Euler: smooth always. The trapezoid goes negative past minus two, and at minus 100 is still minus 0.9608: it rings. Heun and midpoint grow past minus two.
- Recap: four rules, four methods. An implicit step is an equation, solved by Newton. Heun is the trapezoid with an Euler predictor. Order is how long R matches e to the z. Backward Euler stays smooth; forward Euler, Heun and midpoint need z at least minus two; the trapezoid rings. Next: Runge-Kutta.
One integral, four rules
Integrating over one step is exact:
The trouble is that depends on the unknown solution. Every method in the family replaces the integral by a quadrature rule and deals with the unknown in its own way. Write and , since .
- Left rectangle uses the slope we know: forward Euler, . Taylor expansion of about gives , so the rule is off by .
- Right rectangle uses the slope at the new point: backward Euler, . Expanding about , the rule is off by .
- Trapezoid averages the two: the trapezoidal rule, .
- Midpoint samples the middle, but that needs at the half step. Take half an Euler step to get it: the midpoint method, .
Why do the last two beat the first two? Expand about the midpoint : . The linear term integrates to zero over the symmetric interval, so , and the midpoint rule is off by . The trapezoid rule is , so it is off by . Rules exact for straight lines leave errors, rules exact only for constants leave : the local errors of the last lesson, orders .
| method | slope used | explicit? | error of the quadrature | order |
|---|---|---|---|---|
| forward Euler | at | yes | 1 | |
| backward Euler | at | no | 1 | |
| trapezoid | average of both ends | no | 2 | |
| midpoint | at | yes (Euler half step) | , plus the half-step error | 2 |
For the implicit rows the error is the residual left when the exact solution is substituted into the formula; it matches the “start on the curve, take one step” error of the last lesson to leading order. The midpoint row hides a subtlety: the half step is itself approximate, so the quadrature error is not the whole story (see below).
Implicit steps: solving for
Forward Euler and the midpoint method compute from known quantities. Backward Euler and the trapezoidal rule have on both sides, so each step is an equation to solve. For a linear equation that is easy: gives . For a nonlinear it is a root-finding problem. Call the unknown and put everything on one side:
Newton’s method linearizes at the current guess and jumps to the root of that line. Since ,
(For a system, becomes the Jacobian matrix and each update solves the linear system : the price of an implicit step.) The alternative is fixed-point iteration, : no derivative, no solve. Its error is multiplied by about per pass, so it converges only if , a limit on of the same kind the explicit methods have, which defeats the purpose.
Block F of the cell below takes one backward Euler step for from with , so and the root is . Newton goes , roughly doubling the correct digits each pass. Fixed-point iteration goes forever, because at the root .
The rest of the cell is the whole family at work (the implicit steps call a scipy root-finder). Block A checks the formulas of a later section against actual steps, B measures orders on (exact ), C compares Heun and midpoint, D runs at four step sizes, E uses imaginary , G tabulates , H is a diffusion grid.
Heun: the trapezoid with a predictor
The trapezoidal rule has the best accuracy of the lot per unit of work, but needs the unknown. Heun’s method breaks the circle by predicting with a forward Euler step and then correcting with the trapezoid formula:
Equivalently, it is one pass of the fixed-point iteration for the trapezoid equation, started from the Euler value. What survives? The predictor’s error is , and it enters the corrector multiplied by , which makes an contribution, the same size as the trapezoid’s own error. So order 2 survives:
(The trapezoid’s error plus the price of the predictor.) More correction passes (the “PECE” pattern, see 4.6 Multistep Methods) drag the result toward the true trapezoid value, at a rate set by . What is lost is not accuracy but the implicit equation itself: the trapezoid’s amplification factor is a ratio of polynomials whose denominator tames large steps; Heun’s is a bare polynomial. The next sections show the consequence.
Midpoint versus Heun. On the test equation they coincide (derived in the next section). Block A prints identical numbers for the two, and the sim’s max difference readout is zero to round-off. That is a statement about a linear constant-coefficient equation, no more. On a general they have different error constants; the same expansion gives
Block C tests this, printing the one-step error over . For both give at , heading to . For there is no in the right side, hence no predictor error, and the quadrature errors show alone: Heun , midpoint (that is and ). For from : , , , so the formulas predict for Heun and for midpoint; the block prints and at . So two second-order methods can differ in error constant by a factor on a nonlinear problem. Block B shows it: the global error at and is for Heun, for midpoint and for the trapezoid.
The test equation and amplification factors
The standard pencil-solvable comparison is the test equation , exact solution . It is not arbitrary: near a steady state, small deviations obey the linearization (3.8 Autonomous Equations, Equilibria & Stability), and for a system the same holds along each eigen-direction of the Jacobian. A method that mishandles mishandles nearby nonlinear problems too. We take (decay).
Every method here is linear in on this equation, so one step multiplies by a number that depends only on :
Deriving is one line per method:
- Forward Euler: , so .
- Backward Euler: , so .
- Trapezoid: , so .
- Heun: , , so and .
- Midpoint: , , so : the same as Heun.
Compare each with by expanding. Forward Euler: . Backward Euler: , so . Trapezoid: , so . Heun and midpoint: . The first two agree with through the term, the others through : a method has order when matches through the term, which is the Taylor-matching statement from the last lesson in its cleanest form. (Check: on this equation , so Heun’s coefficient is and midpoint’s is .)
Block A confirms it by halving from to . The gap shrinks by (forward), (backward), (trapezoid), (Heun and midpoint): .
A first look at stability
For the true solution decays monotonically; the numerical one is . Two failures show in alone: makes it grow, and makes it flip sign every step, an oscillation the exact solution lacks. Requiring is absolute stability, a statement about one fixed , unlike the stability of the last lesson. The table is block G.
| forward Euler | |||||
| backward Euler | |||||
| trapezoid | |||||
| Heun, midpoint | |||||
| exact |
Read the formulas against it.
Forward Euler. exactly when , that is . Inside that, for (monotone decay) and for : it decays but oscillates. At , and the solution flips between forever; past it, it explodes. On block D prints at (exact: ): at , with alternating signs at , exactly at , and at .
Backward Euler. For , lies strictly between and : monotone decay for every , no oscillation, no blow-up ( at in block D). It is not accurate ( at is far above ), but never wrong in kind. The catch is on another axis. For oscillating problems, , , so backward Euler damps motion that should persist. Block E takes so 64 steps is one period: backward Euler keeps of the amplitude per period, forward Euler gains to , the trapezoid keeps and Heun .
Trapezoid. for every , so it never blows up, and it is neutral on the imaginary axis. But as , , not . For the sign flips each step and the amplitude barely shrinks: at the exact solution has collapsed by while the trapezoid still has . This is ringing, the cost of averaging both ends.
Heun and midpoint. , so never goes negative, but it is at most only for . The real stability limit is 2, the same as forward Euler’s, despite the higher order. A degree-2 polynomial must go to infinity for large ; more order buys accuracy near , not stability far from it. Stability regions in the complex plane are the subject of 4.5 Stability Regions & Stiffness.
Things to try, with as in block D (the readout’s last-step value matches it):
- Sweep upward with only forward Euler ticked: the marker crosses at (sign flips begin), touches the lower dashed line at , then leaves .
- At tick Backward Euler and Trapezoid: the first stays on the axis, the second alternates in sign with at the end.
- Tick Heun and Midpoint together: the max-difference readout is zero to round-off ( at ).
- Raise to at (): Heun blows up, the trapezoid and backward Euler stay bounded.
Exercise: implicit steps by hand
Implement backward Euler twice, in closed form for a linear equation and with Newton’s method for a general one, then run both: a stiff linear problem with , and a nonlinear decay.
Problems
Take .
- For forward Euler, find the ranges of giving (a) monotone decay, (b) decay with sign flips, (c) growth.
- Take . Find for backward Euler and for the trapezoid. How many steps does each need to bring below ? Compare with the exact value of .
Show worked solution
- . Monotone decay: , so . Sign flips with decay: , so . At , (constant size). Growth: .
- gives . Backward Euler: . After 1, 2, 3 steps the factor is , , , so 3 steps. Trapezoid: ; we need , , so 35 steps, with alternating sign. The exact one-step factor is : both are bounded, neither is accurate, and the trapezoid rings.
The -method is with .
- Show that , , give forward Euler, backward Euler and the trapezoid, and find in general.
- Expand to order and show that only gives order 2.
- Show that as and that for all exactly when . For find the stability limit. Evaluate for and .
Show worked solution
- On the test equation , so . Then gives , gives , and gives .
- , so . This matches only if .
- Dividing by : , of magnitude at most iff . For , reaches when , i.e. : the limit is ( for , for ). Values: : ; : , outside the limit and unstable.
A mode decays as , and you step it with .
- Find , and for backward Euler and for the trapezoid. Find the limit of each as .
- How many steps does each take to bring the amplitude below of its start? What does the exact solution do in one step?
- Which would you use if you only care about the slow modes of a system that also contains this fast one? How could you keep the trapezoid’s accuracy without its ringing?
Show worked solution
- . Backward Euler: , with limit as . Trapezoid: , with limit .
- Backward Euler: after one step, after two, so 2 steps. Trapezoid: , so 87 steps, alternating in sign. The exact solution multiplies by in one step.
- Backward Euler: it kills the fast mode within a step or two and leaves the slow modes alone. The trapezoid leaves an alternating residue of the fast mode, visible as noise on a smooth solution, for about steps. To keep second order without ringing, use a method with at (see 4.5 Stability Regions & Stiffness), or take a few backward Euler steps first to damp the mode.
What comes next
4.3 Runge–Kutta Methods & Butcher Tableaux makes multi-slope sampling systematic, 4.4 Adaptive Step Size & RK45 chooses automatically, and 4.5 Stability Regions & Stiffness redraws stability in the complex plane.
Key Takeaways
- Each method is a quadrature rule for : left rectangle (forward Euler), right rectangle (backward Euler), trapezoid, midpoint with an Euler half step. Rules exact for lines give order 2, for constants order 1.
- Implicit methods solve an equation per step: closed form if is linear, Newton with otherwise. Fixed-point iteration needs , which brings back the step restriction.
- Heun is the trapezoid with an Euler predictor: order 2 survives, the implicit equation (and the denominator in ) does not.
- On one step multiplies by , : , , , and for both Heun and midpoint. Order means matches through .
- Heun and midpoint agree on the test equation but not on nonlinear : for their error constants are and (units of ).
- Forward Euler, Heun and midpoint are stable on the real axis only for ; forward Euler oscillates for .
- Backward Euler is stable for every but over-damps oscillations; the trapezoid is neutral on the imaginary axis but rings () on stiff modes.
- Diffusion on a fine grid is a set of very fast decays: hence implicit diffusion in fluid codes.