Why an endpoint is not enough
A solver may need to stop when a moving object reaches a height, or record when a concentration crosses a threshold. The event is specified by a scalar function : for the exact solution , an event time satisfies . Accepted numerical values generally do not land exactly on that time.
Definition 2.4.1
(Dense interpolant and numerical event function)
A dense interpolant of an accepted step is a function on that approximates the solution throughout the step, typically built from data of that step. The numerical event function is , and a numerical event is a zero of .
To locate an event numerically we apply a scalar root finder to , not to the unavailable function .
Assume and are continuous on the relevant step, so is continuous. Evaluate and . An endpoint value equal to zero is already a numerical event. Otherwise, if the signs differ, bisection can enclose at least one zero of . The direction of the sign change may be recorded if the application distinguishes upward from downward crossings. A rejected time step should not be treated as part of the accepted trajectory; use the interpolant of the accepted step.
Theorem 2.4.2
(Bisection encloses a numerical event)
Let be continuous, with . In exact arithmetic, repeatedly bisect the current interval and retain a half whose endpoint values have opposite signs, unless the midpoint is a zero and the algorithm stops. After nonterminating bisections, the retained interval contains a zero of and has length . Its midpoint obeys .
Proof
(Induction on the retained bracket)
The intermediate value theorem gives a zero in the original interval. If the midpoint value is nonzero, its sign agrees with exactly one of the two opposite endpoint signs, so the other half still has opposite endpoint signs. Induction preserves the bracket and halves its length each time. Continuity and the intermediate value theorem give a zero in every retained interval; the midpoint is at most half the interval length from that zero. The bracket need not contain a unique zero, and the argument does not identify the first event if several occur.
Proof X-ray
Which error has bisection controlled?
The proof uses , the interpolated event function, throughout. Continuity of is used only through the intermediate value theorem, and the sign bookkeeping is the invariant that the induction preserves. The proof bounds the distance from the reported midpoint to a zero of ; reducing that width does not by itself move the zero of closer to a zero of . The interpolation and accumulated numerical solution errors require their own estimate, which is the subject of the next section.
Relating the numerical event to the exact one
A useful conditional estimate makes the missing assumptions explicit.
Proposition 2.4.3
(Event-time perturbation estimate)
Let be an interval on which and are continuous, is differentiable in the interior of , there, and for all . If and with , then
Proof
(Mean value theorem at the numerical root)
Since , we have . If there is nothing to prove. Otherwise the mean value theorem applied between and gives a point strictly between them with , so . Combining the two inequalities gives .
If is the midpoint of a retained bracket contained in , the triangle inequality gives . The estimate assumes the exact event exists in ; the bound alone does not prove this. For example, if on and for all and in a set containing both trajectories, one may take . When is small, event time is sensitive; at a tangency the lower derivative bound fails and this linear estimate cannot be asserted.
Worked example
Worked example 2.4.4
(A tightly located interpolant root can still be shifted)
Let , , and let the event be . Thus and the exact event is . Suppose the accepted step has the continuous numerical interpolant . This deliberately shifted interpolant represents an accumulated starting-state error of and has . The endpoint signs are negative and positive. Bisection evaluates , then , then , leaving . The next midpoint is exactly a zero of . It is earlier than the exact event. Here and , so the conditional bound gives , attained in this example.
Worked example 2.4.5
(A threshold on an Euler step with a quantified bound)
Take , , and one Euler step of length , so . Its linear interpolant on is . For the threshold event we get with numerical event , and with exact event ; both lie in , and the crossing is downward.
Bisection from , evaluates , keeping , and then , keeping . The midpoint is within of .
For the error estimate, has derivative on , so its maximum is . Also . Hence . The actual distance is , well inside the bound. The bound is conservative, but every constant in it was computed from the step.
Worked example 2.4.6
(Two crossings hidden by positive endpoint values)
Let on . Both endpoint values equal , so the endpoint test reports nothing. Sampling the midpoint gives , which produces two brackets, and . Treating the earlier bracket first, its midpoint gives , so the algorithm stops at the exact numerical event without further halving; this is the stopping case in the theorem. The later bracket would give in the same way. The extra sample found both crossings here only because it happened to fall between them.
What a sign test can miss
A sign change is sufficient for a bracket, not necessary for an event. On , touches zero while both endpoint values are positive. Also has two crossings but positive values at both endpoints. A single endpoint sign test misses both examples, even with a perfectly continuous interpolant. Extra sampling or a smaller maximum step can help, but without further assumptions no fixed finite sampling rule detects every continuous function's roots. Conversely, a sign-changing numerical interpolant alone does not guarantee an exact event within the step.
Counterexample mode
A numerical crossing with no exact crossing in the step
Claim: if changes sign on an accepted step, the exact event function has a zero in that step. Take again , , one Euler step with and the linear interpolant , but now the threshold . Then has and , so bisection brackets the numerical event . The exact function is decreasing and , so is positive throughout ; the exact event lies in the next step. The repair is the hypothesis of the perturbation estimate: an exact event must be known to lie in the interval, or the interval must be enlarged until it does, before bounds the event-time error.
In floating-point computation, handle an endpoint zero before looking for opposite signs; compare signs directly rather than multiplying potentially extreme values. Stop when the requested time width is met, or report that the midpoint is indistinguishable from an endpoint. Nonfinite evaluations require failure or another explicitly specified response, not a certified bracket.
Common mistake
(Reading a small function value as a small time error)
Near a flat root a tiny value of says little about time. For , the value at is , yet the time error is . Stop bisection on the bracket width, which is the quantity the theorem controls.
Common mistake
(Searching the interpolant of a rejected step)
A rejected trial is not part of the computed trajectory. An event bracketed on its interpolant may not exist on the accepted, shorter step, and an event of the accepted step may be missed. Search only the dense interpolant of accepted steps.
Exercises and solutions
Quick check
(For on , perform two bisections and give the resulting bracket.)
Solution · Answer
, so retain ; , so retain . Its midpoint is within of a zero of , here .
Quick check
(Suppose and on an interval containing an exact zero and a numerical zero, and the numerical bracket is contained in that interval and has width . Bound the distance of its midpoint from the exact zero.)
Solution · Answer
The midpoint is within of a numerical zero, which by the perturbation estimate is within of the exact zero; the bound is .
Quick check
(Let and for . What happens to the event?)
Solution · Answer
has an event at but has none. An arbitrarily small uniform perturbation can remove this tangential event; the derivative lower bound of the perturbation estimate fails at the root, since .