Adaptive Euler step doubling for exponential decay Created 2026-10-14 Updated 2026-10-14
Consider the nonstiff scalar initial value problem , , on . Its exact solution is the exponential decay . Use step-doubling error estimation with the explicit Euler method: from the same numerical starting value , form one coarse step and two half steps giving :Accept when the absolute and relative error tolerances test passes, with . There is no Richardson extrapolation in the accepted value. Both approximations have order of a numerical method one, while this local error estimator has step exponent . Consequently the adaptive step-size controller uses a square root, not a cube root:Start with . A rejected trial retains both and , caps at one, and retries. A zero estimate uses . Before every trial, cap at . Stop with a failure if floating-point arithmetic gives , or after 100000 trials. These rules specify the example completely; they are not a prescription for every ordinary differential equation solver.
Adaptive two-half-step Euler decay: exact and numerical trajectories, accepted step sizes and rejected trials
. Details. The first two trials, and , have and and are rejected. The next trial has and and is accepted. For positive decreasing numerical values, , so the local error estimator givesWhen the relative term dominates, this suggests nearly constant accepted steps, approximately . When falls below the crossover size , the absolute term increasingly permits longer steps. The sharp final decrease in only lands on ; it does not indicate a sudden loss of smoothness.
The actual signed local defect from the same numerical input isHere is Big O notation, obtained from Taylor's theorem for the exponential function. Thus agrees with the leading term as , but is not identical to . At , , the estimate is while the actual local defect is . Their closeness improves for the smaller accepted steps. Had we added using Richardson extrapolation, the accepted formula would instead be , of order of a numerical method two; the same raw difference would still scale as and would not estimate that improved value's leading defect.
Estimated versus actual local Euler defects, rejected trials, and actual accumulated global error scaled by the local tolerance
. Details. The global error obeys an exact recurrence relation involving the actual local defects:Each previous global error contracts, yet the local defects keep adding. In the plotted run, 101 steps are accepted and two trials are rejected. Every accepted is at most approximately , while the largest is approximately . At , the numerical value is approximately , compared with the exact , giving absolute error approximately . The right-hand plot deliberately scales actual global error by the same used for local acceptance; it is not a new global error tolerance test.
Tightening both absolute and relative error tolerances by a factor ten gives 315 accepted steps and endpoint absolute error approximately ; tightening both by a factor one hundred gives 991 accepted steps and endpoint absolute error approximately . This is a convergence comparison for this particular initial value problem. The endpoint error decreases by about a factor three per tenfold tightening, rather than by ten: a first-order Euler method accumulates defects across many steps, while its local error estimator varies quadratically with . A variable-step global ODE error bound needs propagation information as well as accepted local tests.
The absolute stability boundary remains a separate constraint. On the Dahlquist test equation with , the accepted two-half-step formula has stability function . It strictly damps perturbations only for . Its local error estimator is , which can pass an absolute-tolerance test at tiny even outside this damping interval. In a stiff two-mode linear system, a fast mode can therefore constrain the step long after its visible amplitude has become small. An adaptive step-size controller does not turn an explicit Euler method into an A-stable method. Official solver documentation likewise distinguishes explicit Runge-Kutta methods for nonstiff problems from implicit Runge-Kutta methods and backward differentiation formulas for stiff equations.[ref]
scipy.integrate.solve_ivp. solve_ivp, method parameter: explicit versus implicit methods and stiffness
BDF2 discrete energy identity Created 2026-10-06 Updated 2026-10-14
For three vectors in an inner product space, expansion of each squared norm provesTherefore the second-order backward differentiation formula with a dissipative operator decreases the discrete energy . This quadratic form is equivalent to the product norm of the two time levels with constants independent of and . It proves uniform stability even when amplification roots of a polynomial coalesce inside the unit disk, where an eigenvector-separation proof may lose its bound.
Past exam of the mathematics course of the University of Cambridge 2004 iii Paper 69 6 Solution Created 2026-10-03 Updated 2026-10-18
A constant-step linear multistep method has the formwith . The characteristic polynomials of a linear multistep method encode both accuracy and error propagation. The method has order of a numerical method when insertion of a sufficiently smooth exact solution leaves an unnormalized local truncation error . The exponential-symbol order criterion for a multistep method expresses this as . In particular, first-order consistency of a numerical method requires and .
Accuracy alone is insufficient. For , perturbations obey the recurrence . The root condition for a multistep method requires every root of a polynomial to lie in the closed unit disk, with each unit-circle root simple. This is zero-stability. A root outside the unit disk causes geometric amplification as increases; a repeated unit-circle root permits polynomial growth in . Either can destroy convergence even for starting perturbations tending to zero.
The Dahlquist equivalence theorem states that, for a fixed-coefficient method and a well-posed ordinary differential equation with a suitably Lipschitz continuous right-hand side, consistency of a numerical method and zero-stability are equivalent to convergence for all convergent starting data. If the starting errors are and the exact solution is sufficiently smooth, the global error is on a fixed time interval. A stability estimate bounds the propagated sum of local defects over steps; the discrete Gronwall inequality controls the dependence of on the accumulated error. Implicit methods also require the locally consistent, uniquely solvable update branch for sufficiently small .
For example, the explicit Euler method has order one and , satisfying the root condition for a multistep method. The two-step Adams-Bashforth method has order two and , again satisfying it. The trapezoidal rule has order two with one step. The two-step Simpson multistep method, , has order four and the simple roots : it is zero-stable, although its parasitic amplification root can spoil long-time decay. These examples distinguish finite-time numerical convergence from absolute stability.
The first Dahlquist barrier gives the maximum possible order of a convergent ordinary real -step method:These bounds assume only first-derivative evaluations, fixed coefficients and zero-stability; the sixth-order multiderivative multistep method in solution is outside that class.
To obtain arbitrarily high convergent order within the ordinary class, increase the number of steps. The Adams-Bashforth method integrates a polynomial interpolation of past derivative values and has order . The Adams–Moulton method includes the new endpoint and has order for steps. In both families , so the root condition for a multistep method holds for every fixed . Starting values can be generated by a Runge-Kutta method of sufficient accuracy. The backward differentiation formula instead differentiates an interpolating polynomial; its order- members are zero-stable only for .
Finally, high order and favorable stiff stability are separate design goals. By the Second Dahlquist barrier, an ordinary A-stable linear multistep method has order at most two. One may accept a smaller linear stability domain, use suitable backward differentiation formula members for stiff problems, or switch to high-order implicit Runge-Kutta methods or multiderivative multistep methods. A convergent high-order formula still needs time steps appropriate to its stability properties and the problem's eigenvalues.
Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 4 39B a Solution Created 2026-09-24 Updated 2026-10-14
Interpolate through the values at , and differentiate the interpolation polynomial at its newest node. In the backward coordinate , the Newton form iswith the factor interpreted as one and . For , the derivative of the factor at zero is . Thus the backward differentiation formula isIf denotes the forward-shift variable, corresponds to . Consequently the requested polynomial isThe first form is a polynomial valid also at . The second form is convenient for relating it to the truncated series of . Differentiation of the degree- interpolant has local derivative error , giving order for smooth solutions.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 66 6 Solution Created 2026-10-03 Updated 2026-10-18
A stiff differential equation can contain rapidly decaying modes as well as a slowly changing solution of interest. An explicit scheme may need a very small step solely to keep those already small fast modes from numerical growth. A-stability addresses this restriction through the Dahlquist test equation , whose exact solution decays when .
For a one-step method, write , . Its linear stability domain consists of the points where the update is defined and . A-stability means that this domain contains the closed left half-plane. This is a scalar linear stability property, not an order condition, an existence theorem for an implicit solve, or a general nonlinear contractivity assertion.
For a rational approximation to the exponential, consistency requires , and order requires . Poles must be absent from the relevant half-plane. The Forward Euler method has and the disk , so negative real modes require ; it is not A-stable. The Backward Euler method has , and on the left half-plane, so it is A-stable. The trapezoidal rule and the implicit midpoint rule both have, on the scalar linear problem,They are second-order and A-stable despite being different nonlinear methods. No nonconstant polynomial approximation is A-stable, because its modulus grows without bound on the negative real axis. In particular every nontrivial explicit Runge-Kutta method has a bounded-step stability restriction.
A-stability prevents growth but need not eliminate extremely stiff modes: the trapezoidal factor tends to minus one as . L-stability additionally requires within the left half-plane. Backward Euler is L-stable; trapezoidal and implicit midpoint are not. The distinction explains persistent alternating transients in otherwise stable Crank-Nicolson calculations. Accuracy still constrains useful step sizes even for an A-stable method.
A linear multistep method is characterized by polynomials , and its scalar modes satisfy . There is generally no single scalar amplification factor: every root must lie in the closed unit disk and unit roots must be simple. At , this is the zero-stability root condition. Consistency plus zero-stability gives convergence by the Dahlquist equivalence theorem, with suitable starting values. A-stability demands the amplification root condition throughout the left half-plane, including the zero-step condition. The Second Dahlquist barrier says that an irreducible A-stable linear multistep method has order at most two, and an explicit linear multistep method cannot be A-stable.
Examples include backward Euler, trapezoidal, and the second-order backward differentiation formulaIts zero-step roots are . Its unit-circle boundary quotient has real part , and the leading coefficient is nonzero on the left half-plane, giving A-stability by the same continuation argument as in Question 2. Conversely the third-order member of that question fails A-stability. A formal high order without zero-stability, or after silently cancelling a problematic unit factor, does not evade the barrier.
For an implicit Runge-Kutta method, the stages on the test equation satisfy . Whenever these stages are solvable, its stability function isThis rational function is used to test scalar A-stability; the Butcher order conditions separately establish nonlinear order. The Lobatto IIIA method in Question 3 is an A-stable fourth-order example with the diagonal degree-two Padé approximant. More generally the -stage Gauss--Legendre Runge-Kutta method has order and is A-stable, with the diagonal Padé approximation to ; its stiff-limit factor is nonzero. The -stage Radau IIA method has order and is L-stable. Thus Runge-Kutta stages permit arbitrarily high A-stable order, unlike irreducible linear multistep formulas.
For a normal matrix, scalar amplification bounds transfer through unitary diagonalization. For a non-normal matrix, eigenvalue information alone does not assert Euclidean contraction: transient growth and eigenvector conditioning can matter. Direct energy method arguments, such as the dissipative Cayley-transform proof in Question 1, use the symmetric part and are more informative in that setting.
For nonlinear dissipative vector fields, the stronger B-stability property asks that distances between two numerical solutions not increase. A standard sufficient condition for Runge-Kutta methods is algebraic stability: andis positive semidefinite. It follows from the Runge-Kutta contractivity identity when the implicit stages exist. The three-stage Lobatto IIIA method is A-stable but has the first diagonal entry of that matrix equal to , so scalar A-stability should not be confused with that sufficient nonlinear condition. Stage solvability of an implicit Runge-Kutta method remains a separate issue and computational cost of the implicit equations must be considered. A-stability removes a scalar decay-mode stability restriction; order, stiff damping, nonlinear stability and solvability remain distinct properties.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 341 4 ii Solution Created 2026-10-03 Updated 2026-10-14
The spatial shift in the PDF also requires a boundary value beyond the supplied right endpoint: if is the last interior index, the newest value is outside the interval. Thus the printed Dirichlet method has no specified boundary closure, and no unique stability range can be assigned to it as stated.
For completeness, the literal interior formula has an exact von Neumann stability analysis on an infinite or periodic grid. Substitution of a Fourier mode givesFor the root of a polynomial tending to one as , expansion givesConsequently is unstable: sufficiently small nonzero frequencies have a root of a polynomial of modulus greater than one, and arbitrarily fine periodic grids contain such frequencies.
Conversely, if and , thenFor with ,Since , the complex quadratic Schur criterion yields both roots of a polynomial in the unit disk, strictly inside except at , where they are and . Uniform stability follows directly from the BDF2 discrete energy identity: the modal recurrence is , whose energy decreases because . Summing the modal energies proves a bound independent of the grid and even of ; no eigenvector-separation assumption is needed. This is the stability of a spatially shifted BDF2 stencil. Thus the literal periodic-grid result isThis cannot establish stability of an unspecified Dirichlet boundary condition closure. It also does not restore consistency of a numerical method.
For the intended unshifted backward differentiation formula, a spatial eigenvalue givesThe Schur stability criterion gives the root condition for a multistep method for every , with strict inequalities for . A useful uniform energy method proof, including the repeated interior roots that a bare separation argument would miss, is the BDF2 discrete energy identity. With andthe corrected Dirichlet discrete Laplacian scheme satisfiesThis follows by taking the inner product of with and using summation by parts. It controls both time levels uniformly, regardless of the mesh ratio. Hence the corrected method is stable for
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 341 4 i Solution Created 2026-10-03 Updated 2026-10-06
The original PDF has a spatial shift , so the printed scheme is not the usual second-order BDF discretization. The PDF does have on the right; the TeX aid loses that factor two, and that transcription must not be used.
Let , , and expand an exact smooth heat equation solution about . Relative to the standard unshifted backward differentiation formula, the printed newest value addsDividing the raw residual by , its expansion isIn particular, for the usual refinement with fixed , the term generally diverges. A concrete smooth counterexample is , which satisfies the Dirichlet boundary conditions and has at . Thus the printed scheme has no consistent order under fixed- refinement. Its normalized shift error is , so one could only investigate a special coupled limit such as after specifying a valid boundary closure; it has no standard joint second-order accuracy.
For the likely intended correction , the extra shift terms disappear. The normalized local truncation error isWith a stable, suitably accurate starter, the corrected backward differentiation formula combined with the second-order central difference therefore hasThis is a correction to the printed method, not a claim about it.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 341 7 Solution Created 2026-10-03 Updated 2026-10-14
For a fully discrete linear partial differential equation evolution, write in a specified discrete norm. Finite-time stability of a numerical method meanswith independent of the allowed meshes. For a multistep method, augment the state with its time-history values and include a stable starter. Bounds may grow as when the continuous problem has growth; demanding decay for all time would be a stronger assertion. The treatment of initial data, forcing, Dirichlet boundary conditions, and the norm is part of the hypothesis, not a detail supplied by an interior calculation.
For constant coefficients on an infinite or periodic uniform grid, von Neumann stability analysis substitutes the Fourier mode . The discrete Fourier transform and the Parseval identity turn a uniform multiplier estimate into a discrete L2 norm estimate. In a one-step scalar scheme, proves contractivity, while gives finite-time stability. In a multilevel scheme, every root of a polynomial in its amplification polynomial of a multilevel finite difference scheme matters, as does uniform control of the associated companion matrix.
For the Forward Euler diffusion scheme with ,Thus for all frequencies exactly whenSufficiency follows since ; necessity follows from the highest-frequency mode on even periodic grids. This gives the usual parabolic mesh restriction . For the Backward Euler diffusion scheme,so every is stable. The Crank-Nicolson method hasagain of modulus at most one for all , but stiff modes approach rather than zero. These are PDE manifestations of the A-stability and L-stability distinctions for time integration.
For advection , assume and set . The upwind finite difference scheme is , withIt is contractive when . This also has a direct maximum-norm proof: each newest value is a convex combination of two old values. The resulting Courant–Friedrichs–Lewy condition expresses that the numerical domain of dependence covers the physical one. For negative , the upwind direction must be reversed. By contrast, Forward Euler method time stepping with the centered first finite difference has and for nonzero . Under fixed nonzero refinement it is unstable, since a fixed nontrivial mode grows geometrically over steps. This is not a claim of instability under every imaginable mesh coupling: instead bounds its spurious finite-time growth, since .
The leapfrog advection scheme illustrates a multilevel subtlety. Its amplification polynomial of a multilevel finite difference scheme isFor , both roots of a polynomial have unit modulus and separation at least . A uniformly conditioned eigenbasis of the companion matrix then proves power boundedness of a two-level Fourier scheme for arbitrary history data. At and a grid admitting , the roots coincide on the unit circle, and a Jordan block produces growth. Thus the endpoint fails the ordinary arbitrary-history root condition for a multistep method; checking only that both moduli equal one misses the instability. Restricting the starter or filtering the parasitic mode is an additional hypothesis.
The energy method handles variable coefficients and finite boundaries for which Fourier stability analysis may be unavailable. For the Backward Euler diffusion scheme with homogeneous Dirichlet boundary conditions, define . The discrete summation by parts identity isTake the inner product of with . The elementary identity givesThis proves unconditional contractivity including the actual boundary treatment. More generally, a dissipative operator gives of operator norm at most one: with , dissipativity implies , and the Cauchy-Schwarz inequality gives . In finite dimensions this also proves invertibility. For the second-order backward differentiation formula, the BDF2 discrete energy identity used in question 4 controls both time levels and proves unconditional diffusion stability. A repeated root strictly inside the disk is harmless here; the energy argument supplies the uniform bound without a singular eigenvector formula.
A second technique is eigenvalue stability analysis of a finite difference method. Under the method of lines, a time integrator advances by . If is a normal matrix, the scalar linear stability domain criterion on all controls its powers exactly in the corresponding L2 norm. For the centered Dirichlet discrete Laplacian, its eigenvalues lie between and zero; intersecting this interval with a time integrator's stability interval determines its mesh restriction. A uniform bound on the diagonalization of a matrix is needed for nonnormal diagonalizable systems. Eigenvalues alone can be misleading. For example,has both eigenvalues inside the disk for , but the upper-right entry of is . Taking , , this grows like . Hence stable scalar eigenvalues do not give mesh-uniform stability. Boundary closures can introduce precisely the extra growth that an interior Fourier symbol overlooks, so boundary stability of a finite-difference method must be checked separately.
For nonlinear spatial discretizations, a useful replacement for Fourier stability analysis is a convexity argument. If the Forward Euler method map is nonexpansive in a chosen norm for , the second-order strong stability preserving Runge-Kutta methodis also nonexpansive under the same restriction. Indeed, for two inputs, the triangle inequality gives . Its Taylor expansion is , proving order two. Such strong stability preserving Runge-Kutta methods transfer suitable forward-step bounds without relying on a linear spectral calculation.
Finally, consistency of a numerical method explains what stability buys. For a linear Hadamard well-posed problem, the Lax equivalence theorem equates convergence of a consistent discretization with its stability, under the stated approximation-space and norm hypotheses. Directly, if the error satisfies , iteration gives the discrete Duhamel principleThus vanishing normalized local truncation error and initial error yield convergence. With a nonlinear Lipschitz step estimate, the discrete Gronwall inequality plays the same role. A stable but inconsistent stencil, such as the literal defective formulas in questions 3 and 4 under their usual refinement, is not rescued by any amplification bound. The decisive checks are a mesh-uniform evolution bound, a valid boundary closure, and consistency with the actual PDE.

