Motivation
A fixed step can waste work on a slowly changing solution and miss a rapid change elsewhere. An adaptive calculation makes a trial, compares two approximations over the same interval and decides whether to keep that trial. This decision requires more than the words “choose a smaller step”: we must specify the accepted value, what happens after rejection, how the endpoint is reached and when the calculation declares failure.
We use explicit Euler because every stage can be checked by hand. This is a practical, deliberately conservative controller: rejected steps are halved and accepted steps are never enlarged. The earlier Runge–Kutta note derives an embedded-pair indicator and an order-four doubling formula; the present question is how to turn a first-order comparison into a complete finite algorithm, and what a successful run actually establishes.
Definitions
Consider , , on , with . At an accepted pair , for a proposed , calculate
uses one whole Euler step, whereas uses two half steps. All comparisons start at the same numerical state , not at two independently accumulated trajectories.
Definition 2.3.1
(Scaled step-doubling indicator)
With prescribed absolute tolerances and relative tolerances , the scales and the scaled indicator of the trial are
The trial is accepted when , and the accepted value is , not .
The have the units of the corresponding state components; are dimensionless. Positive keep the denominator positive even at zero. In exact arithmetic the complete controller is:
- Set , , and depth . Choose a nonnegative integer maximum depth .
- If , return success and . Otherwise set , evaluate and as above.
- If , set , retain and return to step 2. Record the accepted pair if an output trajectory is required.
- If and , discard both trial values, set and return to step 2 with the same . If and , return failure together with the last accepted pair.
The chosen dyadic rule sacrifices automatic growth for a transparent finite bound. In exact arithmetic, the clipping minimum is never active before the endpoint for this particular choice and nondecreasing : all previously accepted steps are integer multiples of the current nominal step, as is the total interval. It remains in the specification as an endpoint safeguard for a variant using an arbitrary initial or for a carefully implemented floating-point calculation. In finite arithmetic, additionally fail if a stage or indicator is nonfinite, if , or if the midpoint is not distinguishable from an endpoint; use a consistent endpoint representation and record that failure rather than reporting success.
Theorem/proposition
Proposition 2.3.2
(The Euler comparison and finite termination)
Let be on an open set in time–state space, with and locally Lipschitz. Let be compact and suppose that, for starts and , the exact solution segments and both Euler stage points remain in a fixed compact neighborhood contained in . Write for the exact solution at started from at . Uniformly for and sufficiently small positive ,
The remainder is uniform on the compact set. For finite , the exact-arithmetic controller above makes finitely many trials, provided its stage values and indicators are defined and finite; it returns either success at or failure at a rejected depth- trial. Success certifies only the displayed acceptance tests, not a bound on the exact solution error.
Concept lensAnalytic
The indicator as a difference of two slopes
Subtracting the two formulas gives exactly
The indicator is times the change in slope over half a step, a difference quotient for scaled by . This explains the expansion of and also the zero-comparison example below: there the two sampled slopes coincide, so whatever happens between them.
Proof sketch or proof idea
Proof
(Second-order expansion of the comparison)
At the half-step stage, Taylor expansion in time and state gives
Consequently , while . Taylor expansion of the exact solution, using , gives . Subtraction proves both estimates. The exact-start condition means that is treated as the initial datum for the local comparison; it does not assert that along an already computed trajectory. Uniformity follows from the stated derivative control on a compact neighborhood.
Proof
(Finite termination of the dyadic controller)
For termination, every rejection increases and there can be at most such increases before either acceptance or failure. At the current depth , every previous accepted step and the total length are integer multiples of , because never decreases. Hence a positive remainder is at least the nominal step, and clipping is inactive. Every accepted step is therefore at least , so at most steps are accepted. There are finitely many trials. This says nothing about whether the chosen tolerance is achievable before depth .
Proof X-ray
Three separate links in an error claim
The expansion relates to the local defect only up to a remainder. The acceptance test checks against user-selected scales. A final error bound would additionally require a computable bound on that remainder and a propagation estimate for previously accumulated errors. Neither follows from the test alone. In particular, the inequality is not a proof that each true local error is at most its scale.
If a component , the leading scaled indicator behaves like while the scales change continuously; halving eventually reduces that leading term by about four. The finite algorithm does not rely on this asymptotic approximation to decide acceptance: it recomputes after every rejection. If the leading term vanishes, a smaller-order term or cancellation controls the comparison instead, so the factor-four prediction need not hold.
For perspective, if and the exact flow is Lipschitz with factor at most on all relevant segments and the actual local defects satisfy known bounds , then and hence
This is a conditional deterministic bound, not a formula obtained by setting : the unknown remainders must first be bounded. Adaptive local tolerances also do not automatically limit their sum to a desired final tolerance.
Worked examples
Worked example 2.3.3
(A complete run, including rejection at a later state)
Take , , , , , and . Here , , and . The table reports the unscaled indicator ; acceptance requires because the states are positive.
| Start | Decision | |||
|---|---|---|---|---|
| reject | ||||
| reject | ||||
| accept | ||||
| accept | ||||
| accept | ||||
| reject | ||||
| accept | ||||
| accept |
At the fourth quarter-step, , so and the time stays at . The last accepted value is
The exact value differs by about , larger than the local threshold . The calculation illustrates accumulation; it does not disprove any global theorem because no global tolerance was promised. Had , the fourth quarter-step would instead return failure at .
Worked example 2.3.4
(A zero comparison with nonzero error)
For , , on , both Euler stage slopes at and are zero. Thus and any positive scale accepts the full interval. But integration gives . The smooth polynomial between the sampled times is invisible to this particular comparison. A zero indicator is not a proof of exactness.
Worked example 2.3.5
(Stability is a different restriction)
For and , the two-half-step update has amplification , although the exact factor is . Repeated steps of this size grow rather than decay. A deliberately loose absolute tolerance can accept such a trial: with and , , , and . Tightening a tolerance can induce shorter steps, but the acceptance rule by itself is not an unconditional stability guarantee.
Common mistakes
Common mistake
(Borrowing the order-four denominator)
The factor for the fine error applies to a method of order under its common leading-defect expansion. Here , so the factor is one; using the order-four denominator from the Runge–Kutta doubling formula would understate the Euler estimate by a factor of fifteen. Nor is generally a rigorous upper bound merely because it approximates the signed fine error asymptotically.
Common mistake
(Retrying from a rejected state or a different interval)
A rejected state must not become the starting value of the retry. Clipping the trial to must occur before both approximations are computed, or the comparison no longer concerns the same interval. If an event or a discontinuity is known, split at it and use an appropriate one-sided model; smooth local expansions must not be carried across a jump without justification.
Common mistake
(Changing units without changing the tolerance)
The componentwise maximum tests each chosen scale. Changing the units of a component without changing the corresponding absolute tolerance changes the meaning of the test.
Summary
Step doubling compares a whole Euler step with two half steps, and their difference estimates the fine local defect to leading order under smoothness. A finite depth-limited accept/reject procedure can reach the endpoint or report a precise failure. Its successful local comparisons do not, on their own, certify a global tolerance or stability.
Exercises
Quick check
(For , , compute , , and the exact local fine error for a trial of length from . Does the estimate happen to be exact?)
Compute the second slope at the half-step time.
Solution · Answer
The first slope is zero and the midpoint slope is . Therefore , and . Integration gives , so . Here the higher remainder happens to vanish; this exact equality does not extend to arbitrary smooth .
Quick check
(Consider an isolated trial of a controller variant that allows an arbitrary initial , with , , , , and current nominal step . Perform the clipped trial. If the current depth equals the maximum, what does the variant return?)
Clip before evaluating stages.
Solution · Answer
The clipped length is . Then , and . The scaled indicator is , so the trial is rejected. At maximum depth the algorithm returns failure and the last accepted pair , without advancing time or retaining either trial state.
Quick check
(Starting from exact data, suppose a proof gives every true local defect at most in norm and the exact flow has factor at most for . Give a bound after accepted steps over total time ; explain why a comparison alone is insufficient.)
Use the propagation inequality from the proof.
Solution · Answer
The displayed bound gives because . This may be pessimistic but follows from the stated hypotheses. A comparison bound controls , whereas the actual defect is plus a remainder; without a bound for that remainder one cannot substitute for every true defect.
Quick check
(For , , find the positive step sizes for which the accepted fine Euler update has amplification magnitude at most one. What happens at the boundary?)
The fine amplification is a square.
Solution · Answer
The fine amplification is . It is at most one exactly when , or . At the amplification is one: the numerical state does not decay in magnitude even though the exact solution does. The strict interval gives decay per step for nonzero states.