You have coded RK45 and called solve_ivp. This lesson is the why: why subtracting two answers estimates an error, where the controller’s exponent comes from, and what rtol and atol measure. A spacecraft on an eccentric orbit crawls far from the planet and whips around the close approach; a fixed step small enough for the close approach wastes nearly every evaluation of on the quiet part.
It builds on 4.1 Local Error, Global Error & Order (local and global error, order) and 4.3 Runge–Kutta Methods & Butcher Tableaux (tableaux and order conditions, not rederived here). Its limit is 4.5 Stability Regions & Stiffness.
Transcript
- An embedded pair gives two answers from one set of stages: the same k's, two weight vectors. On y prime equals y times one minus y, the slopes 0.09 and 0.123975 give Euler 0.145 and Heun 0.1535. Exact is 0.1548. The second answer costs no extra evaluation.
- Why is the difference an error estimate? The two results share every order condition up to the lower order, so the difference is the lower method's own local error. Estimate over true error tends to one as h shrinks, here 0.4 to 0.025: Heun Euler 0.8888, 0.9702, 0.9924. Bogacki Shampine's 3.87 at h 0.4 is not yet asymptotic.
- At h one half the estimate is 0.00849375. Euler's true error is 0.00982810; Heun's is only 0.00133435. The solver steps with the better answer, Heun's, and uses the difference to judge the worse one: local extrapolation.
- Three pairs: orders two and one, three and two, five and four; b minus b hat first acts at order 2, 3, 5. Bogacki Shampine and Dormand Prince are FSAL: the last row of A equals b, so the last stage is the next step's first. Dormand Prince needs 6 new evaluations a step, not 7.
- Assume the scaled error is C h to the q plus one, q the lower order. Meeting the tolerance gives h times safety 0.9 times err to the minus one over q plus one, the factor held between 0.2 and 10. Scipy uses q 4 for RK45, 2 for RK23. Accept when err is below one.
- Worked step, Heun Euler, h one half, rtol ten to the minus 3, atol ten to the minus 6. Estimate over scale is error norm 54.978: rejected. Raw factor 0.1214 is under the floor, so the factor is 0.2. Norm 3.2255: rejected, h 0.0501. Norm 0.8513: accepted.
- The scale is atol plus rtol times the larger absolute value. The norm is a root mean square: scaled errors three and four give 3.5355, not four. Relative tolerance rules above y equal atol over rtol, here 0.001; below, atol is the floor.
- Kepler, e 0.9, rtol ten to the minus 6: 63 steps accepted, 21 rejected, 506 evaluations. The first step, 0.00392, grows by exactly ten; the largest, 0.4540, is at t 1.063; the smallest, 0.004467, at pi: ratio 101.6. 30 of 63 steps have r below a half; all 21 rejected trials begin on the approach.
- Fixed RK4, same evaluations. At rtol ten to the minus 6, Dormand Prince is off by 1.752 times ten to the minus 5; RK4 with 126 steps is 3.982 off. At minus 3: 0.1045 against 12.21; at minus 8: 8.969 times ten to the minus 8 against 1.265. To match the first, RK4 needs at most 2300 steps, 9200 evaluations, 18.2 times as many.
- Dense output: one Dormand Prince step of 0.454 from the exact state at t 1.0631. End of step error 9.232 times ten to the minus 8. Midpoint: Hermite cubic 2.488 times ten to the minus 5, scipy's interpolant 2.044 times ten to the minus 7.
- A local tolerance is not a global bound. After one orbit at rtol ten to the minus 6 the error is 17.5 times rtol; after ten orbits, 628 times, 36 times the one-orbit error for ten times the time. I have not derived the growth rate.
- Nor does it cure stiffness. For y prime equals minus 1000 times y minus cos t, RK45 takes 912 steps, 6350 evaluations, error 4.0 times ten to the minus 4, below the tolerance: accuracy did not pick the step. The Dormand Prince stability limit is z equals minus 3.3066; median accepted h lambda, 3.2593. Radau takes 15 steps, BDF 55.
- Recap: two answers from one set of stages; the difference estimates the lower method's error; the step keeps the better one. A tolerance is local, and does not cure stiffness. Next: stability and stiffness.
Two answers from one set of stages
An embedded pair computes one set of stages (one , one ) and combines them with two weight vectors:
The second answer costs no extra evaluations of . Let have order and order ; the pair is written . Heun–Euler 2(1) has a second bottom row:
Why the difference is an error estimate
Measure errors as exact minus numerical, for a step started on the exact solution through . The order- result has local error , the order- result . Subtract:
The difference is the local error of the lower method, to leading order. In weights it is with . In Taylor series the coefficient of each elementary differential is , the difference of the two methods’ order conditions for the rooted tree (4.3 Runge–Kutta Methods & Butcher Tableaux). Both meet them through order , so first acts on trees with nodes. Block A confirms it in exact fractions: the first nonzero order of is for Heun–Euler, Bogacki–Shampine and Dormand–Prince, i.e. for .
Block B measures it on one step of , :
| (estimate) / (lower method’s true error) | |||
|---|---|---|---|
| Heun–Euler | |||
| Bogacki–Shampine | |||
| Dormand–Prince |
- The estimate is only asymptotic. The ratio tends to (Heun–Euler’s distance from is , shrinking like ), but at Bogacki–Shampine overstates by . Hence the safety margins below.
- The step uses the better answer. Block B also prints (true error of ) / (true error of ): at it is , , , so the estimate is pessimistic about the value used. This is local extrapolation, done by scipy in both RK23 and RK45. At it fails for Bogacki–Shampine, whose higher-order value is worse (ratio ): the asymptotics have not started.
The estimate is also local in a stricter sense: it refers to the solution through the current point, not the curve you started on (last section).
Three pairs, and FSAL
Bogacki–Shampine 3(2) (the pair behind RK23):
Dormand–Prince 5(4) has seven stages, , and its full tableau is in block A. I wrote it from memory and checked it in exact fractions: meets every order condition through order 5 (the rooted trees), through order 4 and not 5, the row sums equal , and the arrays equal scipy’s RK45. Block A checks the other two pairs too.
FSAL, first same as last. For Bogacki–Shampine and Dormand–Prince the last row of equals (with ); block A prints True. So the last stage sits at , exactly where the next step’s is needed: new evaluations per step for Dormand–Prince instead of , instead of for Bogacki–Shampine. It needs the step to use the higher-order weights, so it depends on local extrapolation. Heun–Euler is not FSAL (False): stage 2 sits at the Euler point, the accepted point is Heun’s.
The controller
Suppose the scaled estimate behaves like , with about the same on the next step. The step that would give exactly the tolerance solves :
Here is the order of the lower method, because that is what err measures: scipy uses for RK45 and for RK23 (block C prints error_estimator_order), exponents and , although the steps are taken with orders 5 and 3. In scipy err is already divided by the tolerance, so and a step is accepted when err is below 1.
- Safety . Aim below the tolerance, since drifts. The predicted error after the change is : , , for (block B).
- Ratio limits. The factor stays in (
MIN_FACTOR,MAX_FACTOR) because the estimate is asymptotic; after a rejection the next accepted step may not grow. - Reject. If err is not below 1, retry from the same with the smaller , reusing .
Worked example (Heun–Euler). , , , , . Stages , ; Heun gives , Euler , exact . The estimate compares with Euler’s true error (Heun’s: ). The scale is , so the error norm is : reject. The raw factor is below , so . Its error norm is : reject, factor , giving with error norm : accept.
The first step has no history, so scipy guesses from and (a heuristic of Hairer, Nørsett and Wanner): in scaled norms, an Euler probe (one extra evaluation) for how fast changes, then the exponent again. On the orbit below it starts at and the controller multiplies it by the maximum .
rtol and atol
The error vector is divided by a scale per component and reduced to one number:
scipy uses this root mean square over the components (block C: the norm of is , not ), with defaults , . Where is large, rtol sets correct digits per step; where a component passes near zero rtol alone would demand impossible accuracy, and atol is the floor. The crossover is . Two cautions: the RMS lets one component exceed its own scale by up to (Problem 3); and one atol serves positions and velocities alike (the orbit below uses because every component crosses zero).
Worked example: an eccentric orbit
A Kepler orbit , semi-major axis , period , eccentricity , starting at apoapsis . The close approach is at : , speed , so a passage lasts about . The exact position comes from Kepler’s equation (Newton’s method, machine precision), so every error below is a true distance. Block D integrates one period with Dormand–Prince () and with fixed-step RK4 given the same evaluations ( steps):
| rtol | DP accepted / rejected / nfev | DP final error | RK4 steps | RK4 final error |
|---|---|---|---|---|
At equal cost the fixed-step body has left the orbit: an error of exceeds the apoapsis distance , and its step is about twice the passage time. To match RK4 needs about steps, evaluations (a scan in steps of ), times as many. At the largest step is (at ), the smallest after the first at , a ratio of ; of accepted steps have . All rejected trials begin between and , on the approach. A plausible mechanism, read off the pattern and not proved: going in, the error constant rises fast, so a step sized from the last error is too long; going out, falls.
Things to try:
- Defaults: accepted , rejected , nfev , final error ; RK4 ends away.
- Bogacki–Shampine: accepted , rejected , nfev .
rtol: final error .- Orbits : watch the third plot climb.
Dense output
Animation frames, t_eval and event detection (a zero crossing inside a step) need values between step ends. Dense output is a per-step interpolant built from stages already computed, so it costs no extra evaluations; it should be about as accurate as the step. Block F takes one Dormand–Prince step of from the exact state at : end-of-step error . At the midpoint, the cubic Hermite interpolant from and at both ends has error , about times larger; scipy’s own continuous extension has . Fitting and , the errors scale as (step end), (Hermite), (scipy), so the cubic falls behind more as shrinks (ratio at ).
What the tolerance does not promise
Global error is not the tolerance. Each step keeps its local error below the tolerance, but the dynamics carry local errors forward (4.1 Local Error, Global Error & Order). Block E1 repeats the orbit at :
| orbits | accepted | rejected | nfev | final error | error / rtol |
|---|---|---|---|---|---|
Every step met its tolerance, yet after ten orbits the position is off by times rtol, growing faster than the number of orbits (-fold for -fold time; I did not derive the rate). For a global bound, rerun with a tighter rtol and compare.
Adaptive steps do not cure stiffness. Take , on , default tolerances: plus a transient dying like . Block E2: RK45 takes steps and evaluations with final error , below the tolerance, so accuracy did not pick the step. Stability did: on the real axis at for Dormand–Prince, so . The median step after the transient has , and all rejected trials after had : the controller rides the stability boundary and bounces off it. Implicit Radau and BDF take and steps (, evaluations); why they escape the bound is 4.5 Stability Regions & Stiffness.
Exercise: an adaptive Bogacki–Shampine integrator
Implement the step, error norm, step factor and driver. The tests compare your step count, evaluation count and final state with scipy’s RK23 from the same first step.
Problems
For , , try with Heun–Euler, , , safety , exponent .
- Compute the Euler value, the Heun value and the estimate.
- Find the error norm. Accepted? If not, what is the next ?
- Compare the estimate with the true errors ().
- Try the new .
Show worked solution
- , Euler ; , Heun . Estimate .
- Scale , norm : reject. Factor , so .
- True errors: Euler , Heun . The estimate overstates Euler’s error by and is times Heun’s.
- : , estimate , norm : accepted, matching the predicted exactly because the estimate is exactly quadratic in .
Use the Bogacki–Shampine tableau above.
- Compute , , , .
- Find and compute , .
- Give the orders of and , the first condition where is nonzero, and the controller’s exponent.
- For error norm , what factor does this pair give, and Dormand–Prince?
Show worked solution
- , . , .
- Rows give , , , : . Then and .
- meets all four conditions through order 3 (): third order. misses both order-3 conditions ( for , for ): second order. is first nonzero at order 3 (, ), so the estimate is , , exponent .
- . Dormand–Prince: , a milder cut because its error falls faster with .
A step from to has estimate ; , .
- Compute the scales and scaled errors.
- Compute the RMS and max norms. Accepted under each?
- Show that RMS below forces . What does that allow for the four-component orbit?
- What happens to the second component if ?
Show worked solution
- , . Scaled errors and .
- RMS : accepted. Max : rejected. The small component is over its tolerance and scipy accepts.
- Every term of is nonnegative, so for each . For one component may be up to times over its scale ( for , consistent with ).
- Its scale becomes and its scaled error : the RMS exceeds , rejected. As a component nears zero its scale vanishes and the step shrinks without limit;
atolis the floor.
Key Takeaways
- An embedded pair gets a second answer free; is, to leading order, the local error of the lower-order result, because and share their order conditions through .
- The solver steps with the higher-order result (local extrapolation); the estimate is only asymptotic.
- From : , for RK45 and for RK23, factor in , no growth right after a rejection; a rejected step retries from the same .
- The scale is , the norm an RMS over components (one can be up to over); defaults , .
- Bogacki–Shampine and Dormand–Prince are FSAL:
nfevfor RK45. - On the orbit the step spans a factor of about ; evaluations gave , while fixed RK4 at that cost gave and needed times as many to match.
- Dense output must match the step’s accuracy: a cubic Hermite was times worse.
- The tolerance is local: after ten orbits the error was times
rtol. And it cannot fix stiffness: RK45 on rode the stability limit, steps against for Radau.