For collocation nodes, the residual of the collocation polynomial vanishes at each node and contains the factor . Quadrature exactness through degree implies for every polynomial of degree at most . Expand the smooth vector-field interpolation error and the derivative of the exact flow in powers of the step. Every endpoint-error term of degree below has this vanishing weighted moment, so the endpoint local error is , although the interior stage accuracy is generally only . A step Lipschitz estimate and discrete Gronwall inequality then give global order . Gaussian nodes attain , while the first nonexact quadrature moment bounds the order from above.
Convergence of a zero-stable multiderivative method Created 2026-10-05 Updated 2026-10-14
For a fixed-step multiderivative multistep method, the ordinary zero-stability root condition still controls propagation of the starting errors when all derivative evaluation maps are uniformly Lipschitz continuous on the relevant bounded region. A local defect then yields global error over a fixed time interval, provided the starting errors are and the implicit updates use the nearby solution branch.
For example, writing the numerical error equation as , with uniformly Lipschitz continuous, a bounded impulse response for the root condition for a multistep method givesAbsorbing the last current-step term for small and applying the discrete Gronwall inequality gives the stated order. The higher derivatives enter through , whose bound stays uniform as .
Dahlquist equivalence theorem Created 2026-09-24 Updated 2026-10-31
For a fixed-coefficient linear multistep method applied to a well-posed initial value problem with a continuous right-hand side uniformly Lipschitz continuous in the solution argument on the relevant region, consistency of a numerical method and zero-stability are equivalent to numerical convergence for arbitrary starting values whose errors tend to zero. The time interval is fixed while the step size tends to zero; an implicit numerical method must use its well-defined nearby solution branch for sufficiently small steps.
The quantitative statement is that a zero-stable method with consistency error and starting errors has global error , provided the exact solution is sufficiently smooth for that residual bound. A bounded response to step defects follows from the root condition for a multistep method, and the discrete Gronwall inequality controls the nonlinear error terms. Mere continuity of the right-hand side does not by itself supply these hypotheses or uniqueness of the exact solution.
Lipschitz one-step error bound 2026-10-31
Suppose the increment function of a one-step method is Lipschitz continuous in its solution argument with constant , uniformly in time and step size. Let be the global error, and let be the exact-start local truncation error. The triangle inequality gives . Iterating and summing a geometric series proves the displayed estimate. Since , uniformly bounded and consistency error give global error on a fixed time interval when . Here denotes Big O notation. This is a constant-step form of the discrete Gronwall inequality.
Past exam of the mathematics course of the University of Cambridge 2001 iii Paper 57 7 Solution Created 2026-10-03 Updated 2026-10-18
For an initial value problem, convergence of a numerical method means that on each fixed interval , the largest error at mesh points tends to zero as the step size tends to zero and the starting errors vanish. Order of a numerical method describes how rapidly an exact-start local defect decreases; stability of a numerical method controls propagation of that defect and of errors already present. These are related but different properties. A high-order expansion alone cannot ensure that accumulated error remains small.
For a one-step map , define the exact-start defect . Order means for sufficiently smooth solutions. The normalized local truncation error divides this defect by and is ; explicitly specifying the normalization prevents an apparent one-order discrepancy. Suppose the map satisfies the local Lipschitz boundFor the error recurrence isIteration, or the discrete Gronwall inequality, yields for . Stable propagation converts an order- local formula into global error , provided starting data are equally accurate. Consistency is the weaker requirement that the normalized local defect tend to zero.
For a linear multistep method, zero-stability concerns the recurrence at . Its roots must have modulus at most one, and unit-modulus roots must be simple. Roots outside the circle amplify errors exponentially in the number of steps; repeated unit roots introduce polynomial growth. The requirement is stronger than bounded propagation for one fixed number of steps: as on a fixed physical interval there are steps. Under the usual Lipschitz assumptions and consistent starting values, the Dahlquist equivalence theorem says consistency plus zero-stability is equivalent to convergence. Its sufficiency combines a bounded discrete recurrence propagator with the sum of local defects, while necessity follows by exciting an unstable homogeneous root or by observing the persistent error of an inconsistent formula.
For example, satisfies the first-order consistency identities, but its root polynomial is . For , a small starting error can excite a mode and destroy convergence as the number of steps increases. In contrast, simple parasitic unit roots such as the root minus one of a two-step centered method need not destroy zero-stability: they remain bounded, though they can create unwanted oscillations and affect practical behavior. Accurate starting procedures and suppression of accumulated parasitic error remain relevant.
Absolute stability asks a different question: for , does the discrete solution decay or stay bounded for a specified finite ? The Forward Euler method has and, for real , requires . It converges as , but a stiff decay mode can impose a severe practical step restriction unrelated to the accuracy needed for slowly varying components. The Backward Euler method has , hence is A-stable and L-stable. The trapezoidal rule has , is A-stable, but tends to minus one on a very stiff negative mode and can retain alternating transients rather than damping them rapidly.
Zero-stability therefore does not imply unrestricted absolute stability; the three-step family analyzed earlier in this paper is a particularly strong illustration. Conversely a stable large step need not be accurate. This distinction matters for a stiff equation. The Second Dahlquist barrier limits A-stable linear multistep methods to order at most two, whereas implicit Runge-Kutta methods can have much higher order and still be A-stable. That barrier concerns the specified method class, not every numerical time integrator.
Finally, the mathematical order depends on smoothness: nonsmooth solutions or forcing can lower observed rates. Roundoff, imperfect implicit solves and inaccurate derivative evaluations introduce additional defects. Smaller steps increase the number of such perturbations; truncation error alone does not describe arbitrarily fine computation. The useful organizing principle is consistency supplies vanishing defects, stability bounds their accumulation, convergence follows, and order quantifies its rate under the stated regularity and starting-error assumptions.
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 2005 iii Paper 69 2 b Solution Created 2026-10-03 Updated 2026-10-14
Factor the first characteristic polynomial:The unit root is simple and the other root is strictly inside the unit disk, so the method is zero-stable. Also and , giving numerical consistency. The Dahlquist equivalence theorem therefore makes it convergent.
The mechanism can also be seen directly. The zero-stable homogeneous recurrence has bounded propagators because its two error modes are and . Variation of constants for the perturbed recurrence bounds the error by a fixed multiple of its two starting errors and the sum of the step defects, plus times a sum of errors from the Lipschitz vector field. Absorb the current implicit error term for sufficiently small , then apply the discrete Gronwall inequality. On a fixed time interval the sum of exact-start defects is , giving second-order numerical convergence with second-order starting values. The implicit step is locally well defined, for example by contraction when for a Lipschitz constant .
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 71 6 Solution Created 2026-10-03 Updated 2026-10-14
A collocation Runge-Kutta method approximates an ordinary differential equation by a polynomial whose derivative agrees with the vector field at selected times. Let distinct nodes be , and consider the possibly nonautonomous equation . On a step from , choose a polynomial of degree at most , with , such that . Here is scaled time; the numerical endpoint is .
Let be the Lagrange interpolation polynomial equal to one at and zero at the other nodes, and set . Interpolation of the polynomial derivative givesEvaluating at the nodes and endpoint derives the Runge-Kutta method coefficients:Thus collocation is a specific family of generally implicit RK methods, not a separate update mechanism. The identity gives and , the collocation tableau row-sum identity. For sufficiently small , a vector field with Lipschitz constant gives a contraction of the stage map when , on a suitable bounded neighborhood. The Banach fixed-point theorem then gives a unique nearby stage solution. Equivalently smooth stage equations have identity derivative in the stage variables at , so the inverse function theorem gives a smooth nearby branch. Arbitrarily large-step solvability is a separate issue for an implicit Runge-Kutta method.
Order analysis has two levels: polynomial accuracy at stages and extra accuracy at the endpoint. Integration of interpolated powers gives the stage moment identitiesAn induction in powers of , using these identities in the stage equations, shows that the collocation polynomial agrees coefficientwise with the exact Taylor polynomial through degree :For example, the coefficient of each new stage term is integrated exactly because its node dependence is a polynomial of degree at most . This proves stage order and bounded actual-time derivatives of the collocation polynomial up to degree . Assuming the vector field is sufficiently smooth on a fixed compact solution neighborhood, its composition with this polynomial has uniformly bounded derivatives of all finite orders needed below.
The endpoint weights define the interpolatory quadrature rule . Suppose it is exact through degree , but not through degree . Necessarily : interpolation integrates degrees below exactly, while the nonzero polynomial , with , has positive integral but quadrature value zero and degree . Exactness also implies the nodal-polynomial criterion for quadrature exactnessbecause the integrand has degree at most and vanishes at every node.
Here is the endpoint-error argument underlying the collocation order theorem. Let and be its residual. It vanishes at the collocation times, and if , then , where is interpolation at the nodes. Taylor expansion in actual time givesThe vector coefficients are bounded. Each bracket has the factor , with quotient degree . In particular the residual is throughout the step.
Write for the exact flow from time and state to . Differentiating gives : the derivative with respect to the starting time cancels the vector field by the flow composition identity. Integration therefore gives the exact local endpoint errorFor , the residual already gives . For , Taylor-expand the smooth matrix weight as . Every product term with integrates to zero: its polynomial factor is times a polynomial of degree . All remaining terms are before the time integration, including both remainders. HenceThis is collocation endpoint superconvergence by quadrature orthogonality. For the global assertion, the stage contraction estimate gives a one-step Lipschitz bound on a fixed solution neighborhood. Thus the propagated error satisfies , and the discrete Gronwall inequality gives on a fixed time interval. The order cannot generically exceed : for , each collocation step reduces to the same quadrature rule, whose first nonexact moment yields a nonzero local error and composite error.
The usual node families illustrate the result. Gauss collocation methods use interior Gaussian nodes and have , the maximum possible order. Right-endpoint Radau nodes give the Radau IIA method of order . Including both endpoints with Lobatto quadrature gives the Lobatto IIIA method of order for . One-stage Gaussian collocation is the second-order implicit midpoint rule, while collocation at the right endpoint is the first-order Backward Euler method. The two-stage Gaussian nodes give anda fourth-order method. Node placement, rather than just stage count, controls the superconvergent endpoint order.
There is also a structural link with Question 2. For Gaussian nodes, let . The derivative of has degree at most , so Gaussian quadrature is exact on it. The integral is , while evaluating at the nodes gives . Thus Gaussian collocation satisfies and has Runge-Kutta conservation of quadratic invariants. For the scalar test equation, any RK method has stability function . For implicit midpoint this is ; the identity proves A-stability. High order, stage solvability, invariant preservation and damping are distinct design considerations, so no stability conclusion should be inferred from collocation order alone.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 72 7 Solution Created 2026-10-03 Updated 2026-10-14
A fixed-step linear multistep method for uses several previous solution and derivative values:The coefficients are fixed independently of the step size. It is explicit when and implicit otherwise. Its characteristic polynomials of a linear multistep method are and . The contraction mapping theorem gives a uniquely solvable implicit step under a Lipschitz continuity bound whenever , by contraction of the new-value equation on the appropriate solution region. A suitable starting procedure must supply the first values; the method alone does not determine them.
Order is defined by inserting a smooth exact solution into the recurrence. If the residual is and its first nonzero coefficient occurs at that degree, the method has order ; dividing the residual by gives an local truncation error. Taylor expansion gives the exact order conditions for a linear multistep methodwith the right side interpreted as zero at , and failure at for exact order. Equivalently,The basic consistency of a numerical method conditions are , ; for the ordinary nondegenerate consistent formulation this common value is nonzero. Exactness on constants and linear functions does not control propagation of numerical perturbations.
That propagation is the role of zero-stability. On the homogeneous recurrence is . Its modes are , with powers of determined by root multiplicities. The theorem on the root condition for a multistep method states that zero-stability is equivalent to every root of having modulus at most one, with every unit-modulus root simple. Interior repeated roots are permitted, since geometric decay dominates their polynomial factors. An exterior root amplifies perturbations geometrically; a repeated unit root amplifies them polynomially and violates a step-independent perturbation bound.
The Dahlquist equivalence theorem states that a fixed-step consistent linear multistep method is convergent exactly when it is zero-stable. This concerns ordinary differential equations with a uniformly Lipschitz continuous right-hand side on the solution region over a fixed finite interval, convergent starting values, and the well-defined nearby branch of each small-step implicit solve. For order convergence of a numerical method, the solution must have the required smoothness and the starting errors must be .
The mechanism can be sketched explicitly. The root condition for a multistep method bounds the recurrence's discrete Green function. For an order- exact-solution defect , the Lipschitz continuity error equation then gives an estimate of the formThe current-step term can be absorbed for small . The discrete Gronwall inequality says that a bound implies . There are defects on a fixed interval, so their sum is and this yields the claimed global order. Conversely, testing with vanishing starting perturbations in exterior-root or repeated-unit-root modes proves that convergence of a numerical method fails without the root condition for a multistep method.
For example, the two-step Adams-Bashforth method hasIt is explicit, order two and zero-stable, hence convergent with order-two starting values. By contrast, a recurrence with has solutions on the zero differential equation. Starting differences tend to zero yet become unbounded at a fixed positive time, since is of order . A small local defect or formal high order cannot rescue this mode. Canceling a common factor may remove it only by changing the allowed starting relations, as the parameter endpoint in Question 2 illustrates.
Absolute stability addresses a different limit: apply the method to the Dahlquist test equation and put . The amplification roots satisfyAll roots must satisfy the disk condition, with unit roots simple; one cannot inspect only the root that tends to one as . The degree and solvability of the recurrence must also be preserved. The resulting set of is the domain of absolute stability. A-stability means that it includes the whole closed left half-plane, so the numerical solutions of every Dahlquist test equation with are stable for every positive step size. It is a linear test-equation property, not a proof of arbitrary nonlinear contractivity or high accuracy at large steps.
Forward Euler method has order one and factor , so its stability region is the disk . Backward Euler method has factor and is A-stable. The trapezoidal rule is order two with factor ; its modulus is at most one throughout the left half-plane. These one-step methods are included as the simplest multistep examples. For the two-step Adams-Bashforth method, the negative-real stability interval is : its polynomial is , and the root reaches at . It therefore imposes a step restriction when applied to strongly decaying modes.
The genuinely two-step BDF2 method isIt has order two, roots at zero step and is A-stable. For its normalized polynomials , , the unit-circle boundary locus hasThe leading coefficient has no zero in the left half-plane, and the roots at a small negative are both inside the disk. Root continuity then proves open-half-plane stability; on the imaginary boundary the only possible unit root is the simple root one at . This gives a direct proof of the stated A-stability rather than relying on a boundary plot.
Two sharp order barriers explain the tradeoff. The first Dahlquist barrier states that a consistent zero-stable real linear -step method using only first derivatives has order at most for odd and for even ; an explicit method has order at most . The Second Dahlquist barrier states that an irreducible A-stable real linear multistep method has order at most two. These statements concern fixed constant coefficients and the ordinary first-derivative multistep class, not multiderivative methods or arbitrary variable-step formulations. Thus higher order alone is not a route to unconditional stiff stability. Question 2 provides a concrete illustration: its third-order member is zero-stable but not A-stable.
No nontrivial consistent explicit multistep method is A-stable. Its amplification polynomial of a multistep method has a fixed highest coefficient, while at least one lower coefficient grows without bound as real . Were all roots uniformly in the unit disk, their elementary symmetric polynomials would keep all the monic coefficients bounded, a contradiction. This is the coefficient argument behind explicit multistep methods cannot be A-stable.
In practice, selecting a method therefore involves accuracy, startup, the presence of a stiff differential equation, implicit-solve cost and step-size control. Zero-stability handles propagation as the step tends to zero; consistency of a numerical method supplies a vanishing defect; A-stability handles the numerical solutions of all decaying Dahlquist test equations at finite steps. None substitutes for the others, and variable steps or PDE discretizations require additional uniform stability arguments appropriate to their setting.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 68 7 Solution Created 2026-10-03 Updated 2026-10-18
Consider an initial value problem on , with a Lipschitz continuous vector field in the solution variable and enough smoothness for the stated error expansions. Convergence of a numerical method meanswith consistent starting values. An order of a numerical method quantifies this approximation: with sufficiently accurate starting data and the required stability, the global error is . Stability of a numerical method controls the amplification and accumulation of perturbations; it is the link between a small local defect and small global error.
For a one-step formula , define the unscaled local truncation errorThe method has local order if uniformly along sufficiently smooth solutions. If the defect is divided by , its order is instead ; the convention must be specified. Assume also the perturbation estimateThe global error then satisfiesIterating, or applying the discrete Gronwall inequality, givesThere are steps on a fixed interval, so stable propagation turns local defects into accumulated error. Starting error is needed to retain order . This explains why matching an exact Taylor expansion is insufficient unless errors are controlled during repeated steps.
For a fixed-coefficient linear multistep method, writeThe consistency of a numerical method conditions are and . The higher order conditions for a linear multistep method arewith right side zero for ; exact order means first failure at . They come from inserting the exact solution and comparing its Taylor expansion.
Errors at follow the homogeneous recurrence determined by . Zero-stability is equivalent to the root condition for a multistep method: all roots of a polynomial have modulus at most one, and every unit-modulus root is simple. Roots outside the disk give exponential growth in the number of steps; repeated unit roots give polynomial growth in that number. Repeated interior roots are harmless because their polynomial factors are dominated by decay. Under the usual Lipschitz continuity and initialization assumptions, the Dahlquist equivalence theorem givesFor a zero-stable order- linear multistep method, local defects and starting errors of the stated orders yield global error by a recurrence bound and the discrete Gronwall inequality. Every required starting value matters.
A concrete failure of “consistency implies convergence” isHere and , so and : the method is consistent, of order one. But its root violates zero-stability. For with exact solution zero and starting values , , the computed solution is . These starting errors vanish, yet at the error diverges. Local accuracy cannot compensate for an unstable recurrence.
A different meaning of stability concerns a fixed step on decaying equations. The Dahlquist test equation introduces . A one-step method gives and is absolutely stable when . For a linear multistep method, the corresponding amplification polynomial of a multistep method is , and every root must satisfy the bounded root condition, not just the root approximating . Strict asymptotic decay requires the roots to have modulus less than one for . This distinction matters at reducible methods with an undamped parasitic mode, as in question 1(c).
The Forward Euler method has order one and , so its linear stability domain is . For , with , it requires . It converges as , yet an excessively large step can produce growing oscillations on an exactly decaying problem. The Backward Euler method has the same order, but makes it A-stable and L-stable. For a stiff differential equation, fast decay can impose a severe explicit time-step restriction even when accuracy of the slow dynamics would permit a much larger step.
The trapezoidal rule has order two and is A-stable, but is not L-stable, since its stability function tends to along the negative real axis. The Second Dahlquist barrier limits an irreducible A-stable linear multistep method to order at most two. This does not limit implicit Runge-Kutta methods: question 4's Lobatto IIIA method is fourth-order and A-stable. Conversely, question 1's fourth-order member is convergent but not A-stable. These examples show that order of a numerical method, zero-stability and A-stability answer different questions.
For nonlinear dissipative problems, B-stability controls distances between numerical solutions; algebraic stability of a Runge-Kutta method is a sufficient coefficient criterion. Question 4 shows that A-stability alone does not imply that coefficient criterion. Variable time steps require additional analysis of step ratios and error propagation, and stiff problems may require uniform-in-stiffness error estimates beyond the fixed-problem convergence result. The useful chain is local accuracy plus the appropriate perturbation bound, giving global accuracy; absolute and nonlinear stability then determine which practical time steps preserve the intended dynamics.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 341 6 Solution Created 2026-10-03 Updated 2026-10-18
A Runge-Kutta method advances through stagesThe Butcher tableau records , normally with . Linear absolute stability tests the amplification of a linear decay mode; nonlinear B-stability compares distances between two solutions of a dissipative vector field. Both describe propagation of perturbations, but they impose different conditions.
For the Dahlquist test equation, elimination of stages givesThe linear stability domain consists of for which the step is defined and . Poles or singular stage systems must be excluded, even if an output formula has a formal cancellation. For a scalar test equation, the proof is : the powers are bounded exactly when . For , the update is . If is a normal matrix, unitary diagonalization of a normal matrix makes the operator norm equal to the largest scalar amplification modulus. For a diagonalizable matrix, powers are bounded by the condition number of the eigenvector matrix times the maximal scalar power. These constants must remain uniform for mesh-dependent systems. A defective unit-modulus eigenvalue can instead produce a growing Jordan block; the scalar spectral test alone does not control a general matrix.
An A-stable method accepts the entire closed left half-plane. The Explicit Euler method has and a disk of stability , so it is not A-stable. No nonconstant polynomial stability function can be A-stable, since it is unbounded on the negative real axis; this excludes all consistent explicit Runge-Kutta methods. The Backward Euler method has , and when , proving A-stability. It is also L-stable, because for large left-half-plane .
The implicit midpoint rule and the trapezoidal rule have the same scalar stability function,The identity proves A-stability. On the imaginary axis their amplification has unit modulus, and along the negative real axis it tends to . Thus neither is L-stable; very stiff decay can persist as alternating numerical values. In contrast, the two-stage Radau IIA method has , with the explicit nonnegative modulus-gap proof in question 1, and is L-stable. This illustrates why L-stability matters beyond A-stability for a stiff differential equation.
For nonlinear problems, assume a real or complex Euclidean inner product and the dissipativity hypothesisfor all relevant states at each common time. Exact solutions satisfyA B-stable Runge-Kutta method reproduces this nonexpansion of distances whenever its stages exist. Put , , and . Then . Expansion of the output squared norm, followed by substituting in its linear terms, proves the Runge-Kutta contractivity identityIf and is a positive semidefinite matrix, the first sum is nonpositive by dissipativity, and the second is nonnegative: expand each coordinate of the stage vectors to express it as a sum of nonnegative quadratic forms. These are exactly the conditions for algebraic stability of a Runge-Kutta method. Hence algebraic stability implies B-stability. Applying B-stability to the linear dissipative problem , or its two-dimensional real form, also proves A-stability whenever stages are well defined.
The Backward Euler method has , hence ; the implicit midpoint rule has , , hence . Both are algebraically stable and B-stable. For the two-stage Radau IIA method,a positive semidefinite matrix, while both weights are positive. It therefore combines third-order accuracy, B-stability, and L-stability. The distinction between stability and solvability is essential: for Lipschitz continuous , the stage map is a contraction when , so the contraction mapping theorem proves small-step unique solvability. The preceding algebraic stability proof is an estimate for existing stages; it is not a theorem asserting stage existence for arbitrary step sizes and domains.
Linear A-stability is insufficient for nonlinear B-stability. The trapezoidal rule fails B-stability, even though its scalar stability function is identical to that of the B-stable implicit midpoint rule. Its Runge-Kutta method coefficients areFailure of this sufficient algebraic stability test alone would not prove failure of B-stability. An actual counterexample does: take and . Dissipativity follows fromThe unique step map obeys , because the left-hand side is strictly increasing and onto. At , , and implicit differentiation givesNearby initial states expand in distance. This proves a true nonlinear failure rather than merely failure of a coefficient criterion.
Finally, stability of a numerical method on finite intervals connects these contractivity properties to accuracy. If a one-step map is nonexpansive and its exact one-step defect has norm at most , then the error satisfies , hence for . A Lipschitz step bound gives the same order using the discrete Gronwall inequality. For a stiff differential equation, the value of B-stability is that the propagation estimate need not grow with a large negative dissipative rate. The accuracy constant still needs appropriate smoothness and uniform derivative bounds; stability alone does not establish a mesh-uniform error order.
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.
Past exam of the mathematics course of the University of Cambridge 2019 iii Paper 341 1 a Solution Created 2026-10-03 Updated 2026-10-05
Expand about and use from the chain rule. The residual of the exact solution isThe coefficients through vanish, and the displayed fourth-order coefficient does not. Thus the multiderivative multistep method has order three.
At , its first characteristic polynomial isIts roots are and , with the unit-modulus root simple, so it satisfies the root condition for a multistep method and is zero-stable. Combining this with the defect estimate proves convergence of order three, assuming sufficiently smooth , order-three starting values, and the nearby branch of each implicit update.
More explicitly, the right-hand side is , where has a uniform local Lipschitz continuity bound for small . A bounded zero-stable impulse response and the discrete Gronwall inequality therefore control the accumulated defects by over fixed time intervals. This is convergence of a zero-stable multiderivative method, rather than a direct application of the first-derivative-only Dahlquist equivalence theorem.
Past exam of the mathematics course of the University of Cambridge 2021 ib Paper 1 17B ii Solution Created 2026-09-24 Updated 2026-10-05
Let . Subtracting the exact one-step relation from the numerical method and applying the stated Lipschitz continuity givesIf , iteration yields the discrete Gronwall inequalityFor ,andConsequently
Let be continuous in its first variable and uniformly Lipschitz continuous in its second variable, with constant . Retain the finite-interval smoothness assumptions and the bound from the preceding subpart. We first establish solvability of each implicit step. For a proposed starting state , the maphas Lipschitz constant . If , the contraction mapping theorem on the complete state space gives a unique next state .
To compute a useful Lipschitz constant for the method, introduce its increment function byFor two starting states ,Rearranging gives the implicit midpoint Lipschitz estimateThus, for example, gives an increment Lipschitz constant at most , uniformly as .
For an explicit global error estimate, set . Subtract the numerical formula from the exact-value identity containing :The Lipschitz condition and the triangle inequality implyand thereforeIterating this inequality is the elementary discrete Gronwall inequality argument. For , summing the geometric series and using givesFor , . If , this provesWith the exact initial value, , the global error is and tends uniformly to zero on every such finite interval. If , the recurrence instead gives , with the same conclusion. Starting values merely converging to the exact initial value also suffice for numerical convergence; second-order accuracy requires their errors to be . The result concerns exact implicit solves and convergence on fixed finite intervals, not uniform accuracy over an unbounded time interval.
Variable-step global ODE error bound 2026-10-14
If a one-step map is Lipschitz with factor at most and its exact-start defect is at most , iteration of the error recurrence gives the displayed global bound on a time interval of length . Since , the defect sum is at most . Local tolerance control alone is not a global accuracy certificate: propagation, the number of steps, stiffness, roundoff and nonlinear-solve errors also enter. The discrete Gronwall inequality organizes this distinction.