The Central Idea
A fixed-resolution method chooses a step size, mesh, or approximation degree in advance.
An adaptive method instead follows the cycle
\[ \boxed{ \text{compute} \to \text{estimate error} \to \text{compare with tolerance} \to \text{refine or accept} }. \]The numerical method becomes self-correcting within the limits of its error estimator.
Why Adaptivity Matters
Numerical problems are rarely equally difficult everywhere.
A function may be smooth over most of an interval but have one sharp peak. An ODE solution may change slowly for a long time and then pass through a rapid transient.
Uniform refinement wastes work on easy regions.
Error Control Is a Feedback System
At each stage, the method measures its own performance through a computable indicator.
That indicator changes the next computational decision.
This feedback perspective connects numerical analysis with optimization, control, and adaptive modeling.
Exact Error Versus Estimated Error
The exact error is
\[ e = Q^*-Q, \]where \(Q^*\) is the unknown exact quantity.
Since \(Q^*\) is usually unavailable, practical algorithms use an error estimate
\[ \boxed{ E_{\text{est}}\approx |Q^*-Q| }. \]A Priori Error Estimates
An a priori estimate predicts error before the computation is completed.
It may depend on:
- step size;
- known derivative bounds;
- condition numbers;
- theoretical convergence order;
- regularity assumptions.
A Posteriori Error Estimates
An a posteriori estimate uses information produced by the numerical computation itself.
Examples include:
- differences between coarse and refined approximations;
- embedded Runge-Kutta pairs;
- residual norms;
- local defect estimates;
- mesh refinement indicators.
Absolute Tolerance
An absolute tolerance requires
\[ \boxed{ E_{\text{est}} \le \tau_{\text{abs}} }. \]This is natural when the quantity has a fixed physical scale.
Relative Tolerance
A relative tolerance scales the permitted error with the computed quantity:
\[ \boxed{ E_{\text{est}} \le \tau_{\text{rel}}|Q| }. \]This is useful when magnitudes vary widely.
Combined Tolerances
A common practical test is
\[ \boxed{ E_{\text{est}} \le \tau_{\text{abs}} + \tau_{\text{rel}}|Q| }. \]Absolute tolerance protects values near zero, while relative tolerance scales naturally for larger values.
Why Relative Error Alone Can Fail
If
\[ Q\approx0, \]the relative tolerance scale
\[ \tau_{\text{rel}}|Q| \]becomes tiny.
A combined criterion prevents unrealistic demands near zero.
Normalized Error
A dimensionless error ratio is
\[ \boxed{ r = \frac{ E_{\text{est}} }{ \tau_{\text{abs}}+\tau_{\text{rel}}|Q| } }. \]Then:
- \(r\le1\): accept;
- \(r>1\): refine or reject.
Step Acceptance and Rejection
In adaptive time stepping, a trial step is not automatically accepted.
The algorithm may:
- compute a tentative update;
- estimate its local error;
- accept the step if the estimate is small enough;
- reject and recompute it with smaller \(h\) otherwise.
Embedded Methods
An embedded method produces two approximations of different orders using much of the same computational work.
Suppose
\[ Q^{(p)} \]and
\[ Q^{(p+1)} \]are available. Their difference estimates local error:
\[ \boxed{ E_{\text{est}} \approx |Q^{(p+1)}-Q^{(p)}| }. \]Embedded Runge-Kutta Pairs
Adaptive ODE solvers often use Runge-Kutta pairs in which the same internal stage evaluations produce two formulas of nearby order.
One approximation advances the solution while the difference between the two controls the step size.
Step-Size Update
If the local error behaves approximately like
\[ E(h)\approx Ch^{p+1}, \]then a natural new step size is
\[ \boxed{ h_{\text{new}} = h \left( \frac{\tau}{E_{\text{est}}} \right)^{1/(p+1)} }. \]Safety Factors
Practical algorithms usually multiply the ideal step estimate by a safety factor \(s<1\):
\[ \boxed{ h_{\text{new}} = s h \left( \frac{\tau}{E_{\text{est}}} \right)^{1/(p+1)} }. \]Typical logic avoids pushing the next step exactly to the theoretical limit.
Step-Growth Limits
Even when the estimated error is extremely small, increasing \(h\) too aggressively can be risky.
Practical solvers cap the growth:
\[ h_{\text{new}} \le g_{\max}h. \]They may also enforce a minimum shrinkage after a rejected step.
Minimum and Maximum Step Sizes
Adaptive solvers often impose
\[ \boxed{ h_{\min} \le h \le h_{\max} }. \]These bounds prevent impractically tiny steps or unsafe large jumps.
What If the Required Step Falls Below \(h_{\min}\)?
If the solver cannot satisfy the tolerance without violating the minimum step, it should report failure rather than silently continue.
This may indicate:
- a singularity;
- stiffness;
- poor scaling;
- an unrealistic tolerance;
- model breakdown.
Adaptive Quadrature
Numerical integration provides one of the clearest examples of adaptive refinement.
Instead of using a fine mesh everywhere, estimate the local integration error on each subinterval and subdivide only where needed.
Adaptive Simpson Strategy
Compute a coarse Simpson estimate
\[ S(a,b) \]and a refined estimate
\[ S(a,m)+S(m,b), \qquad m=\frac{a+b}{2}. \]Their discrepancy gives an error indicator.
Adaptive Simpson Error Estimate
For Simpson's rule, a standard local estimate is
\[ \boxed{ E_{\text{est}} \approx \frac{ |S_{\text{refined}}-S_{\text{coarse}}| }{15} }. \]If the estimate exceeds the local tolerance, subdivide again.
Recursive Refinement
Adaptive quadrature naturally forms a tree of subintervals.
Smooth intervals stop refining early, while difficult intervals are split repeatedly.
Distributing a Global Tolerance
Suppose the requested total integration error is
\[ \tau. \]When an interval is split into two halves, one simple strategy assigns each half a tolerance
\[ \boxed{\tau/2}. \]More sophisticated schemes distribute error budgets according to estimated difficulty.
Local Versus Global Error Control
Controlling every local contribution does not automatically imply a perfectly sharp global bound.
Local estimates must be accumulated or budgeted in a way that supports the desired global tolerance.
Adaptive Mesh Refinement
In spatial problems, adaptivity changes the mesh rather than a time step.
Fine cells are placed where the solution changes rapidly, while coarse cells are retained where the solution is smooth.
Refinement Indicators
A mesh-refinement indicator might use:
- large residuals;
- large gradients;
- large curvature;
- jumps across neighboring cells;
- estimated interpolation error;
- local defect estimates.
Residual-Based Adaptivity
Suppose an approximate solution \(u_h\) is substituted into a differential equation operator \(L\):
\[ Lu=f. \]The residual is
\[ \boxed{ r_h = f-Lu_h }. \]Large residuals can indicate regions where the discretization should be refined.
Residual Is an Indicator, Not Always the Exact Error
The size of a residual and the size of the true solution error are connected through the conditioning and stability of the underlying problem.
A small residual can coexist with a larger solution error in an ill-conditioned problem.
Hierarchical Error Estimation
Another strategy compares approximations from nested spaces:
\[ u_h \]and
\[ u_{h/2}. \]Their difference estimates unresolved error:
\[ \boxed{ E_{\text{est}} \approx \|u_{h/2}-u_h\| }. \]h-Refinement
h-refinement reduces element or grid spacing.
In one dimension,
\[ h\to\frac{h}{2} \]creates more local resolution.
p-Refinement
p-refinement increases the polynomial degree while keeping the mesh fixed.
Smooth regions can often be approximated efficiently by increasing degree rather than subdividing.
hp-Adaptivity
hp-adaptive methods choose between:
- smaller elements through h-refinement;
- higher local polynomial degree through p-refinement.
Sharp features favor smaller elements, while smooth regions may favor higher order.
Adaptive Interpolation
Interpolation can also be adaptive.
Begin with a coarse set of nodes, estimate interpolation error, and insert new nodes where the approximation is poorest.
Adaptive Function Approximation
Function approximation may adapt by:
- adding basis terms;
- splitting intervals;
- raising polynomial degree;
- changing basis families;
- refining only where residuals are large.
Adaptive Root-Finding
Root-finding can combine robust and fast methods.
A safeguarded solver may:
- maintain a valid bracket;
- attempt a Newton or secant step;
- accept it if it remains reliable;
- fall back to bisection otherwise.
This is adaptivity in algorithm choice rather than mesh size.
Adaptive Precision
Some problems benefit from increasing arithmetic precision only when needed.
For example, if rounding prevents further convergence, the computation may switch from standard precision to extended or arbitrary precision.
Error Budgets
A complex numerical workflow may contain several error sources:
\[ E_{\text{total}} \lesssim E_{\text{data}} + E_{\text{model}} + E_{\text{discretization}} + E_{\text{iteration}} + E_{\text{roundoff}}. \]Error control should not drive one component far below the others unnecessarily.
Balanced Accuracy
If measurement uncertainty is about
\[ 10^{-4}, \]demanding numerical discretization error near
\[ 10^{-12} \]may provide little practical value.
Numerical tolerances should reflect the full error budget.
Stopping Criteria
An adaptive algorithm needs a rule for deciding when enough work has been done.
Typical conditions include:
- estimated error below tolerance;
- residual below tolerance;
- step or iterate change below tolerance;
- maximum iteration count;
- minimum step size;
- stagnation detection.
Multiple Stopping Tests Are Safer
A single criterion can be misleading.
For example, a tiny step change may result from stagnation rather than true convergence.
Combining residual, step-size, and iteration-limit tests is more reliable.
Error Estimator Reliability
Adaptivity is only as trustworthy as the error estimator.
A poor estimator may:
- underestimate the true error;
- overestimate the error and waste work;
- miss localized features;
- fail outside the asymptotic regime.
Effectivity Index
When the exact error is available for testing, define the effectivity index
\[ \boxed{ \eta = \frac{E_{\text{est}}}{E_{\text{true}}} }. \]An estimator with
\[ \eta\approx1 \]closely tracks the true error.
Reliable Versus Efficient Estimators
An estimator should ideally be:
- reliable: unlikely to miss large errors;
- efficient: not excessively larger than the true error;
- cheap: inexpensive compared with the main computation.
Convergence and Adaptivity
The previous lesson used the model
\[ E(h)\approx Ch^p. \]Adaptive methods invert that relationship to choose the resolution needed for a target error.
Choosing Resolution from the Error Model
If
\[ E(h)\approx Ch^p \]and we want
\[ E(h)\le\tau, \]then roughly
\[ \boxed{ h \lesssim \left( \frac{\tau}{C} \right)^{1/p} }. \]Adaptive Methods Estimate \(C\) Indirectly
The constant \(C\) is usually unknown.
Differences between coarse and fine approximations provide enough information to estimate the local error scale without explicitly computing \(C\).
Richardson-Based Error Estimation
Suppose
\[ Q(h)=Q^*+Ch^p \]and
\[ Q(h/2)=Q^*+C\left(\frac{h}{2}\right)^p. \]Then
\[ \boxed{ Q^*-Q(h/2) \approx \frac{ Q(h/2)-Q(h) }{ 2^p-1 } }. \]Adaptive Time-Step Example
Suppose the permitted local error is
\[ \tau=10^{-5} \]and the estimated error is
\[ E_{\text{est}}=8\times10^{-5}. \]Since the estimate exceeds tolerance by a factor of \(8\), the step should be reduced.
Example Step Update
Suppose the local error is third order:
\[ E(h)\sim h^3. \]Ignoring a safety factor,
\[ h_{\text{new}} = h \left( \frac{10^{-5}}{8\times10^{-5}} \right)^{1/3}. \]Therefore,
\[ h_{\text{new}} = h \left( \frac18 \right)^{1/3} = \boxed{\frac{h}{2}}. \]Adaptive Quadrature Example
Suppose
\[ S_{\text{coarse}}=1.2500 \]and
\[ S_{\text{refined}}=1.2515. \]The Simpson error estimate is
\[ \frac{|1.2515-1.2500|}{15} = \boxed{0.0001}. \]Adaptive Linear Solver Tolerances
Iterative linear solvers can also adjust effort dynamically.
For example, an inner linear solve inside a nonlinear method need not be solved to extreme precision during early outer iterations.
Inexact Newton Methods
Newton's method for a nonlinear system requires solving a linear system at each iteration.
In an inexact Newton method, that linear system is solved only accurately enough to support progress in the current nonlinear iteration.
Inner tolerances can tighten as the nonlinear solution is approached.
Nested Error Control
Large simulations may contain several nested algorithms:
- an ODE solver;
- inside it, a nonlinear Newton solve;
- inside Newton, an iterative linear solver.
Each layer has its own tolerance, and those tolerances should be coordinated.
Adaptivity and Computational Cost
Error control is not only about accuracy.
Its second goal is to avoid unnecessary work.
A useful adaptive method meets the requested error with near-minimal cost.
Over-Refinement
Refining too aggressively wastes computation and can eventually increase floating-point error.
Error estimators should stop refinement once the requested accuracy is reached.
Under-Refinement
If the mesh or step is too coarse, important structure may be missed entirely.
An error estimator should detect unresolved regions before accepting the result.
Feature Detection
Adaptive methods may need to identify:
- rapid transients;
- discontinuities;
- boundary layers;
- sharp peaks;
- singular points;
- rapid oscillations.
Discontinuities Require Special Care
High-order smooth error models can fail near a discontinuity.
A solver may need to locate the discontinuity, split the domain, and apply smooth methods separately on each side.
Event-Driven Adaptivity
Some methods refine because an event is approaching rather than because a local truncation error is large.
Examples include:
- impact;
- threshold crossing;
- switching;
- phase transition;
- contact between moving objects.
Error-Controlled Root-Finding
Bracketing provides a direct error certificate.
If a root lies in
\[ [a_n,b_n], \]then the midpoint error is at most
\[ \boxed{ \frac{b_n-a_n}{2} }. \]This is a simple form of rigorous adaptive error control.
Error-Controlled Linear Algebra
A linear solver can monitor:
\[ \|\mathbf{r}_k\| = \|\mathbf{b}-A\mathbf{x}_k\|. \]Iteration stops when the scaled residual meets the requested tolerance.
Conditioning determines how that residual relates to solution error.
Backward-Error Stopping Tests
A useful scaled residual is
\[ \boxed{ \frac{ \|\mathbf{b}-A\widehat{\mathbf{x}}\| }{ \|A\|\|\widehat{\mathbf{x}}\|+\|\mathbf{b}\| } }. \]This measures how large a relative perturbation is needed to make the computed solution exact.
Error-Controlled Approximation
In a basis expansion
\[ f(x) \approx \sum_{k=0}^{n}a_k\phi_k(x), \]rapidly decreasing coefficients can indicate that additional terms contribute little.
The approximation can stop when the tail falls below the error target.
Adaptive Polynomial Degree
If increasing degree reduces error efficiently, continue p-refinement.
If coefficient decay is poor or oscillation develops, subdividing the domain may be more effective.
Verification of Adaptive Algorithms
Adaptive algorithms are more complex than fixed-step formulas and require careful validation.
Verify:
- the error estimator;
- the accept/reject logic;
- step-size updates;
- tolerance scaling;
- minimum and maximum bounds;
- behavior near singular or difficult cases.
Tolerance Study
Run the algorithm with
\[ \tau, \qquad \frac{\tau}{10}, \qquad \frac{\tau}{100}. \]The output should stabilize in a way consistent with the requested accuracy and the method's convergence properties.
Work-Precision Diagrams
A useful comparison plots error against computational work.
Work may be measured by:
- function evaluations;
- matrix-vector products;
- accepted steps;
- total attempted steps;
- runtime.
The best method is often the one that achieves the desired accuracy with the least work.
Efficiency of Step Rejection
Rejected steps are not necessarily failures.
They provide information that helps the solver choose a safer resolution.
But excessive rejections indicate poor step prediction, stiffness, or an unsuitable method.
Controller Oscillation
A naive adaptive controller may alternate between overly large and overly small steps.
More sophisticated controllers use recent error history to smooth the step-size response.
Adaptivity Does Not Replace Analysis
Automatic refinement cannot rescue:
- an ill-posed model;
- bad data;
- an unstable algorithm;
- incorrect boundary conditions;
- a fundamentally inappropriate numerical method.
A Reliable Adaptive ODE Workflow
- Choose a method appropriate for stiffness and smoothness.
- Compute an embedded or otherwise estimated local error.
- Scale the error with absolute and relative tolerances.
- Accept the step if the normalized error is at most \(1\).
- Reject and reduce the step if necessary.
- Update the next step with a safety factor and growth limits.
- Monitor minimum step size and event locations.
- Verify results with tighter tolerances.
A Reliable Adaptive Quadrature Workflow
- Compute a coarse quadrature estimate.
- Subdivide the interval and recompute.
- Estimate local error from the discrepancy.
- Accept intervals meeting their local tolerance.
- Refine only the intervals that fail.
- Accumulate local estimates into a global error budget.
- Guard against excessive recursion and singular behavior.
A Reliable Adaptive Mesh Workflow
- Compute an initial coarse solution.
- Evaluate local residual or error indicators.
- Mark regions with the largest estimated error.
- Refine the marked regions.
- Recompute the solution.
- Repeat until the global tolerance is met.
- Coarsen regions when excess resolution is no longer needed.
Common Error: Treating the Error Estimate as Exact
An error estimator is itself an approximation.
Its reliability should be tested against known problems, refinement studies, or independent methods.
Common Error: Using Relative Tolerance Alone
Near zero, a purely relative criterion can demand impossible or meaningless accuracy.
Use combined absolute and relative scaling.
Common Error: Allowing Unlimited Step Growth
One unusually easy step should not cause the next step to grow without bound.
Growth caps prevent unstable controller behavior.
Common Error: Ignoring Rejected Steps
A high rejection rate can signal that the method, error estimator, or step controller is poorly matched to the problem.
Common Error: Refining Only by Geometry
A region may look small geometrically but still contain a large numerical error.
Refinement should be driven by the solution and error indicator, not geometry alone.
Common Error: Solving One Error Source Far Too Accurately
It is wasteful to reduce iteration error to \(10^{-12}\) when discretization error is still \(10^{-4}\).
Coordinate the full error budget.
Common Error: Assuming Adaptivity Guarantees Efficiency
Adaptive logic has overhead.
If the problem is uniformly smooth and simple, a well-chosen fixed method may be cheaper.
Common Error: Ignoring Conditioning
A tiny residual or local defect may not imply a tiny solution error when the problem is ill-conditioned.
Error estimators must be interpreted through problem sensitivity.
Practice 1: Combined Tolerance
Write a standard combined absolute-relative error criterion.
Practice 2: Normalized Error
What decision is typically made when the normalized error
\[ r=\frac{E_{\text{est}}}{\tau_{\text{abs}}+\tau_{\text{rel}}|Q|} \]satisfies \(r>1\)?
Practice 3: Embedded Estimate
Two embedded formulas produce
\[ Q^{(4)} \]and
\[ Q^{(5)}. \]Write a simple local error estimate.
Practice 4: Step-Size Update
Suppose
\[ E(h)\sim h^4. \]What exponent should appear in
\[ h_{\text{new}} = h \left( \frac{\tau}{E_{\text{est}}} \right)^\alpha? \]Practice 5: Adaptive Simpson
If
\[ S_{\text{coarse}}=2.000 \]and
\[ S_{\text{refined}}=2.015, \]estimate the local Simpson error using the factor \(1/15\).
Practice 6: h-Refinement
What does h-refinement change?
Practice 7: p-Refinement
What does p-refinement change?
Practice 8: Residual Indicator
For
\[ Lu=f, \]write the residual of an approximate solution \(u_h\).
Practice 9: Error Budget
Why is it usually wasteful to solve the numerical iteration far more accurately than the discretization error?
Practice 10: Verification
Name one practical way to verify that an adaptive solver is honoring its tolerance.
Practice Answers
Practice 1
\[ \boxed{ E_{\text{est}} \le \tau_{\text{abs}} + \tau_{\text{rel}}|Q| }. \]Practice 2
The approximation fails the requested tolerance. The usual response is to reject or refine the current step and recompute with more resolution.
Practice 3
\[ \boxed{ E_{\text{est}} \approx |Q^{(5)}-Q^{(4)}| }. \]Practice 4
Since the error behaves like \(h^4\),
\[ \boxed{\alpha=\frac14}. \]Practice 5
\[ E_{\text{est}} = \frac{|2.015-2.000|}{15} = \frac{0.015}{15} = \boxed{0.001}. \]Practice 6
h-refinement decreases the local mesh or step size, creating more spatial or temporal resolution.
Practice 7
p-refinement increases the local polynomial or approximation degree.
Practice 8
\[ \boxed{ r_h=f-Lu_h }. \]Practice 9
Once iteration error is much smaller than discretization error, further iterations do not materially improve the overall accuracy. They only increase computational cost.
Practice 10
Examples include rerunning with a tighter tolerance, comparing against a known solution, checking observed convergence, or comparing with an independent numerical method.
What to Remember
Adaptive methods use error estimates to control computational effort.
\[ \boxed{ \text{estimate} \to \text{compare} \to \text{accept or refine} }. \]- a priori estimates predict error before completion;
- a posteriori estimates use the computed solution itself;
- combined absolute and relative tolerances provide robust scaling;
- embedded methods estimate local error from two nearby-order approximations;
- step-size controllers use convergence order to predict a better next step;
- safety factors and growth limits stabilize adaptive control;
- adaptive quadrature refines only difficult subintervals;
- adaptive meshes use residuals or local indicators to place resolution where needed;
- h-refinement reduces element size while p-refinement increases approximation degree;
- error budgets should balance data, model, discretization, iteration, and roundoff error;
- stopping criteria should use more than one diagnostic when possible;
- adaptive methods still require conditioning, stability, and verification analysis.
Where We Go Next
This lesson completes the core sequence in Approximation and Numerical Analysis. The progression has moved from finite-precision representation and error propagation through conditioning, root-finding, matrix computation, interpolation, function approximation, differentiation, integration, differential equations, convergence analysis, and finally adaptive error control.
Together, these tools form a practical framework for asking not only Can a numerical answer be computed? but also How accurate is it, how stable is the method, how sensitive is the problem, and how much computational effort is actually necessary?