Lesson 23 of 24

Accepted steps, rejections and work

Execute and audit a bounded adaptive Euler step-doubling trace.

Loading your saved responses…

Try the optional starting-point checks and targeted refreshers. You can continue directly into this lesson.

Try

A solver tried three steps but advanced its solution only twice. Has it wasted work, or prevented a bad update? Audit the accepted state and the work ledger separately. Our dimensionless synthetic problem is

y′=fλ(t,y)=−λ(y−t²)+2t, y(0)=1, 0≤t≤1.

The parameter λ is one of 1, 4, 16, 64. Substitution verifies the reference y(t)=t²+exp(−λt). This reference is useful for checking this manufactured problem; it does not turn the algorithm into a general certified solver. Larger λ produces a faster initial transient.

Review Euler’s local error and step-control theory. Here the new action is to audit an actual proposed-step policy, including rejection, work and stopping boundaries.

Predict

From an accepted pair (t,Y), a trial of length h computes a coarse Euler value and a fine value from two Euler half steps. Predict whether both values need independent evaluations of the initial derivative.

k₁=fλ(t,Y), Yc=Y+hk₁, Ym=Y+(h/2)k₁,

k₂=fλ(t+h/2,Ym), Yf=Ym+(h/2)k₂, e=|Yf−Yc|.

There are exactly two derivative evaluations per trial in this implementation: k₁ is shared. The estimator e compares two computations started at the same accepted state. Neither is the exact next solution. Before reading the trace, calculate λ=4, (t,Y)=(0,1), h=1/4. Compare e with the predeclared absolute tolerance 1/8.

Experiment

Live investigation: accepted steps, rejected work and exact bounds

Study y′ = −λ(y−t²)+2t with y(0)=1 on 0≤t≤1. Its exact solution is t²+exp(−λt). Predict the first trial before running. Both methods retain the result of two Euler half steps; the adaptive method can reject the trial. Settings and results are temporary.

Decay rate λ Local tolerance 2⁻ᑫ Initial proposed step 2⁻ᵏ Trial cap per method Exact integer bit cap

Acceptance uses |fine−coarse|≤tolerance. After acceptance, the next proposal doubles only if the estimate≤tolerance/4; after rejection it halves, down to 2⁻¹². The bound uses M=2+λ² on every accepted half step and is separate from this heuristic controller. Exact reduced dyadic integers are bounded by the selected bit cap; resource exhaustion never switches to floating point. Counts exclude BigInt operations, certificate calculations, plotting and worker overhead, so equal derivative counts do not establish equal total computation.

Keep the defaults: decay rate λ=4, local tolerance q=3 (1/8), initial proposed step k=2 (1/4), trial cap 512 and bit cap 4096. Before selecting Run both investigations, predict the first rejection and retry. Expand Inspect every completed adaptive trial and compare its first two rows with the exact table below. The fixed comparison also keeps two half steps per trial, but does not reject. Inspect each method’s status separately. Changing a setting clears the previous results; Reset investigation restores the defaults without starting a run. The changed three-trial exercise below is a paper audit, not a request for an unavailable select option.

Keep a paper record of accepted time, accepted value, proposed step and cumulative derivative calls. Complete the two trial rows independently, then compare them with the exact table. A rejection must not overwrite the accepted state.

Trial	Start (t,Y)	h	Ym	k₂	Yc	Yf	e	Decision	Calls so far
1	(0,1)	1/4	1/2	−27/16	0	37/128	37/128	Reject	2
2	(0,1)	1/8	3/4	−183/64	1/2	585/1024	73/1024	Accept	4

After trial 1 the accepted pair is still (0,1), not (1/4,37/128). After trial 2 it is (1/8,585/1024). The accepted path contains the two half steps of trial 2, through (1/16,3/4). Trial 1’s midpoint is a trial calculation, not a point on the accepted path. Since 73/1024 exceeds tolerance/4=1/32, the next proposed step remains 1/8.

The arrows encode decisions, not a time plot. Text equivalent: trial, reject without state change, halve h, retry, accept the fine result.

Now change only the tolerance to 1/2. Predict the first decision and next step. The first trial is accepted, but its estimate 37/128 exceeds (1/2)/4, so the next proposed step stays 1/4. A looser tolerance can change the accepted trajectory, not merely the number of printed rows.

Understand

A precise state and controller contract

The proposed step is dyadic, h=2⁻ᵏ with integer 0≤k≤12, initially k=2. Tolerance is 2⁻ᑫ for integer 0≤q≤20. At most 1–512 trials are permitted, according to the selected cap. Before a trial, shorten its actual length to the exact remaining distance to t=1 if needed. Dyadic arithmetic represents that endpoint distance exactly. Record proposed and actual lengths separately; a shortened last step is not evidence of an earlier full-length trial.

Accept when e≤tolerance, including equality. Commit (t+h,Yf), including both accepted half-step nodes. If e≤tolerance/4, propose twice the step next, capped by the allowed maximum; otherwise retain its size. On rejection preserve (t,Y) and the accepted path, then halve the proposed step. A rejected trial still increases the trial counter by one and the derivative ledger by two. This contract recomputes k₁ on retries; an implementation that caches it has a different work ledger and must say so.

If the requested smaller step falls below the minimum, stop with a minimum-step failure. If the trial budget is exhausted before the endpoint, report incomplete work. Reaching t=1 is completion of this numerical run, not proof that its error is within tolerance. Exact rational computations also have a 4096-bit resource bound: reaching an arithmetic resource limit must be reported, not silently converted to floating arithmetic. Invalid inputs are not successful solves. The accepted state must remain distinguishable from any unfinished candidate.

Why rejection preserves the accepted solution

Induct on the trial count. Initially the accepted state is the prescribed initial condition. A rejected trial changes only controller/work information, so the previously accepted Euler half-step path remains unchanged. An accepted trial appends precisely the two half steps used to compute Yf. Consequently every accepted pair lies at the end of a well-defined numerical path, and all rejected trials are excluded from that path. This is an algorithmic invariant, not an assertion that the numerical path is the exact ODE solution.

The distinction matters when restarting: after our first rejection, retrying from its candidate value or its candidate time solves a different discrete problem. A small subsequent estimate cannot repair that mutation. Retain the rejected row so another reader can check both the decision and its work cost.

What the estimator does not prove

For sufficiently regular problems in a small-step regime, step doubling compares leading local discretization errors. But e is not a proved bound on accumulated global error. It does not include the error already present in Y, and stability can amplify that error. For y′=−λy, the accepted two-half-step map multiplies initial errors by (1−λh/2)². If λh>4 this factor exceeds 1. At Y=0 both numerical trial values and their difference are zero, regardless of the amplification of a perturbation. Thus a zero local comparison is not a general stability certificate.

For our manufactured family a separate proof can bound global error using y″=2+λ²exp(−λt)≤M=2+λ². On each accepted half step of length s, the affine Euler error obeys Bnext=|1−λs|B+Ms²/2, starting B=0. This follows from Taylor’s remainder and the exact state-difference factor; it is not the acceptance estimator. For the first h=1/4 trial, if accepted, λ=4 and s=1/8 give first bound 9/64 and second bound 27/128, different from e=37/128. If rejected, neither trial half step belongs in the accepted-path bound. The following lesson develops these certificates and their arithmetic limits.

Tolerance here is an absolute number in the units of y. Changing numerical output units by a factor c>0 scales Y, both trial differences and an equivalent absolute tolerance by c, when the ODE is transformed consistently. Relative tolerances and mixed absolute-relative controllers are other algorithms; they are not silently implemented here.

Apply

Repeat the same initial λ=4 experiment with tolerance 1/32 and a cap of three trials. Predict the terminal status, accepted pair, next proposal and work. Then explain what changes if the cap is only two, without claiming the accepted endpoint was reached.

Check the changed trace

The first two trials reject: 37/128>1/32 and 73/1024>1/32. The h=1/16 retry has Ym=7/8, k₂=−879/256, Yc=3/4, Yf=6289/8192 and e=145/8192≤1/32. Its estimate exceeds tolerance/4=1/128, so the next proposal stays 1/16. Three trials used six derivative evaluations, but advanced only to (1/16,6289/8192). The run is incomplete at its work cap, not an endpoint solve. With a cap of two, both trials reject and the accepted pair remains (0,1), with four derivative evaluations. Both records are useful evidence of the declared computation, not successful completion of the integration interval.

Continue

Write a trace audit that separates inputs, trial calculations, accepted path, total work and stopping status. Identify one invariant you checked independently and one conclusion the trace does not justify. Return to verification and method selection when comparing methods: use the same endpoint and accuracy question, and count rejected work. A public trace audit demonstrates guided reasoning; independent implementation also requires executable code and retained tests.

Apply · explain · revise

Practice and reasoning

Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.