Adams–Moulton method Created 2026-09-29 Updated 2026-11-05
An Adams–Moulton method is an implicit linear multistep method obtained by interpolating derivative values including the new time level and integrating that interpolation polynomial over the next interval. For uniform step size , linear interpolation through gives the second-order trapezoidal ruleQuadratic interpolation through instead gives the third-order formulaBecause depends on the unknown , a nonlinear vector field generally requires a solve. Substituting a predicted new value only once defines a different composite numerical procedure; it should not automatically inherit the fully implicit method's absolute stability region.
Bernoulli corrections for polynomial sums 2026-10-14
For a concrete comparison, take on . The integral is , whereas the unit-width left and right Riemann sums are and . The exact integer power sum formula givesThe endpoint choice explains the opposite signs of the correction. The remaining correction is one in both cases.
The same method is useful far beyond squares of numbers. Substituting , , and into the integer power sum formula gives the exact fourth-power resultAt , this isThus a finite polynomial calculation replaces ten additions, or a million additions if is a million. Although the individual corrections can be rational numbers, the result is the exact integer sum.
There is also a useful numerical integration interpretation. The average of the left and right Riemann sums is the composite trapezoidal rule. For , the endpoint corrections cancel but its value is , one above the true integral. Subtracting the correction makes this particular polynomial example exact. For , the two interior corrections above can be written and . These are exact identities for these polynomials; extending such corrections to general functions requires a separate error analysis.
Composite trapezoidal rule Created 2026-10-14 Updated 2026-10-31
On an equal-panel partition of an interval, with , sum the trapezoidal rule over adjacent panels:There are distinct quadrature nodes. Each interior sample belongs to two panels and therefore has quadrature weight , while each endpoint has quadrature weight . Equivalently, the composite trapezoidal rule integrates the piecewise linear function obtained by linear interpolation exactly.[ref]
For and , summing panel quadrature errors givesfor some . Thus panel quadrature errors of order accumulate to order , using big O notation.[ref]
3.5 Quadrature, subsection (i) Trapezoidal Rules. §3.5(i), equations 3.5.2–3.5.3: composite formula and signed error
On a nonuniform partition of an interval with widths and largest width , the bound is .For the polynomial on , direct summation yieldsBoth quadrature errors shrink by exactly four when doubles, with opposite signs. This exact relation belongs to this polynomial example; the trapezoidal rule is not always twice as inaccurate as the midpoint quadrature rule.
Quadratic quadrature errors fall by four on refinement while a common sample bias persists
. Details. The left plot uses exact polynomial sums; the right adds a common sample bias to the composite trapezoidal rule. That mathematical model converges to , showing why smaller panels alone do not ensure accuracy for noisy samples. It illustrates noise sensitivity of a quadrature rule, rather than measured data.
Crank-Nicolson method Created 2026-09-28 Updated 2026-10-14
The Crank--Nicolson method applies the trapezoidal rule to a semidiscrete evolution equation. For a linear system its update is
Extracted-ion chromatogram peak area 2026-11-05
An extracted-ion chromatogram peak area integrates selected ion signal over a stated chromatographic time interval, usually after estimating an extracted-ion chromatogram baseline. If is an extracted ion chromatogram for mass window and is its baseline,Both the extracted ion mass window and time boundaries are part of this definition. The selected-ion/time character follows the IUPAC extracted ion profile definition.[ref]
An original nonuniform-sampling example uses times minutes and signals . With baseline 1, corrected signals are . Straight-line interpolation and the trapezoidal rule giveThe discrete corrected-signal sum is 6, which ignores the acquisition intervals. Neither number is an amount of analyte without a response calibration.
Baseline error accumulates across the integration interval. Over this four-minute interval, overestimating a constant baseline by 0.5 signal units reduces the assigned area by signal-unit minutes, from 7 to 5. A broad weak feature can therefore be especially sensitive to its baseline convention.
Peak area can also include neighboring ions admitted by the mass window and coeluting compounds with the same recorded coordinate. More complete integration does not by itself make the assigned signal chemically specific. State boundaries, baseline, handling of negative corrected values and integration rule. Those choices can alter reported area even when the recorded spectra are unchanged, and differences in area need not mean proportional differences in analyte amount.
Finite samples do not certify quadrature accuracy Created 2026-10-14 Updated 2026-10-25
For any finite set of quadrature nodes in , , consider the polynomialEvery sample is zero, so every quadrature rule at these quadrature nodes gives . Yet is nonnegative and strictly positive away from its finitely many polynomial roots; its continuity makes the integral positive. Consequently the smooth functions and have identical samples but definite integrals and . Multiplying by any positive constant makes the difference arbitrarily large. This is an information limit, even with exact arithmetic; merely assuming smoothness without quantitative bounds does not remove it. The related degree ceiling for quadrature exactness uses the same squared nodal polynomial to limit polynomial exactness.
For example, the endpoint quadrature nodes give , , and . Both the zero function and produce zero under the one-panel trapezoidal rule, although . More generally, any estimate based only on their shared samples has absolute error at least for one of these two integrands, by the triangle inequality.
The obstruction also applies to a deterministic adaptive procedure that terminates after finitely many evaluations on the zero function: form using every quadrature node it visited. On , the same zero responses lead to the same choices and answer. Certified quadrature error control therefore needs additional information, such as a known bound on relevant derivatives, rather than agreement among sampled approximations alone.
Germund Dahlquist 2026-11-05
Germund Dahlquist established fundamental stability restrictions for linear multistep methods for ordinary differential equations. His 1963 paper analyzes A-stability and the associated order barrier, while identifying the special role of the trapezoidal rule. The result explains why increasing formal accuracy alone cannot guarantee stable integration of rapidly decaying differential equations.[ref]
Heun's method 2026-10-14
Here Heun's method means the explicit endpoint-averaging Runge-Kutta method: take an Euler predictor , sample there, and average it with for the output. The second Runge-Kutta stage is evaluated at the predictor, not at the corrected endpoint. In particular it requires no implicit solve as the ODE trapezoidal rule does. Naming conventions vary between books; the formulas specify the method unambiguously.[ref]
Numerical solution of ordinary differential equations: One step methods by André Jürgen Massing. André Massing, Numerical solution of ordinary differential equations: One step methods, October 3, 2021, page 1, Example 1.1: Euler and Heun increment functions
For smooth , a Taylor expansion about gives , where is the state Jacobian matrix. Consequently the output is , matching the exact solution through degree two by the chain rule. This gives local truncation error and, with the usual bounded smoothness and Lipschitz continuity hypotheses on a fixed finite interval, global error . The Euler-Heun embedded pair compares this output with its Euler predictor.
Euler-Heun stage geometry for y prime equals y: sample at the Euler predictor, then average slopes for the corrected endpoint
. Details. For , and , the sampled slopes are and . Transporting the second slope to the starting point would end at ; the average slope instead ends at . The exact exponential function reaches . The magnified endpoint comparison separates the pair difference from the actual Heun local defect .
Lift (force) Created 2026-10-13 Updated 2026-11-05
Lift is the component of the fluid force perpendicular to the far-field flow relative to the body. It need not point vertically: a tilted flow changes the lift direction, and a banked wing can produce a sideways component. In a planar problem choose a unit vector along the incoming relative velocity and a perpendicular unit vector pointing towards the chosen positive-lift side. ThenHere is drag and is signed lift; means a force towards the opposite side. In three dimensions the plane perpendicular to also admits a separate side-force direction, so a lift axis must be specified. Lift is also distinct from buoyancy, which can exist without a relative flow. [ref]
https://www1.grc.nasa.gov/beginners-guide-to-aeronautics/aerodynamic-forces/. NASA Glenn, Aerodynamic Forces: components relative to the flow
The force comes from adding local surface tractions, rather than assigning a single pressure to each side. Let be the wetted body surface and its unit normal vector pointing out of the body into the fluid. The pressure contribution pushes inwards; the viscous stress tensor also contributes, including tangential shear stress:Using a constant reference pressure is legitimate on a closed surface because . This surface integral makes the direction explicit: a surface-normal force is generally neither pure lift nor pure drag. Pressure and skin shear stress both enter the resultant, although the pressure term usually dominates lift on an airfoil. [ref]
https://www1.grc.nasa.gov/beginners-guide-to-aeronautics/aerodynamic-forces/. NASA Glenn, Aerodynamic Forces: pressure and shear contributions
The lift coefficient isolates a useful scale. For a finite wing of reference area (normally its projected planform area), and for a two-dimensional airfoil section of chord length , respectively,Here is dynamic pressure, is far-field mass density, and is lift per unit span, with units . The signs of and follow the chosen lift axis. For stipulated values , , and , and . Doubling gives four times the lift only if stays fixed: changes in Reynolds number, Mach number, surface condition or angle of attack can change it. [ref]
https://www1.grc.nasa.gov/beginners-guide-to-aeronautics/lift-coefficient/. NASA Glenn, Lift Coefficient: normalization and similarity limits
A motivating experiment is to compare two independently observed quantities: the lift registered by a force balance, and the lift inferred from surface pressures. A low-speed wind tunnel holds the model fixed while air passes it at adjustable speed; a calibrated balance measures forces, while small flush holes on both surfaces connect by tubing to differential-pressure sensors referenced to . Iowa State's GA(W)-1 teaching model has taps around a chord; its instructions give their coordinates and close the contour by repeating the first tap. A classroom comparison can combine this pressure-panel method with a balance on the same model; this is an experiment design, not a claim that those instructions report a combined measurement. [ref]
https://www.aere.iastate.edu/~huhui/teaching/2026-08F/AerE344/lab-instruction/AerE344L-Lab-05-Pressure-Airfoil-instruction.pdf. Hui Hu, Iowa State, AerE344 Lab 05, p. 2: GA(W)-1 taps and pressure panels
[ref]https://www1.grc.nasa.gov/beginners-guide-to-aeronautics/drag-measurement/. NASA Glenn, Drag Measurement: force balances and calibration
Before turning on the wind, apply known positive and negative loads to the balance through its resolving centre; use for the known load from a mass. Record all balance channels during loading and unloading, including response to drag and torque loads, to detect cross coupling, hysteresis and zero drift. Record a wind-off tare at each model orientation so its gravitational weight does not become an aerodynamic lift reading. Map tunnel flow direction and uniformity, rather than using the fan setting as a speed measurement. Covert's MIT guide describes these calibration, tare and flow-survey requirements. [ref]
https://ocw.mit.edu/courses/16-621-experimental-projects-i-spring-2003/f38ecde8773fd36c0d8f9069e6aa1df5_student_wt_guide.pdf. Eugene E. Covert, A Student's Introduction to the Wright Brothers Wind Tunnel at MIT, pp. 3–8
For each pressure channel, apply zero and several known pressure differences spanning the expected range; determine the voltage-to-pressure relation and recheck it after a run. Inspect tubing for leaks and blocked taps, and wait for readings to settle before averaging: tubing can delay a pressure signal. This calibration principle is used in NASA's electronically scanned pressure systems, where several applied calibration pressures determine each sensor's response and repeated calibration tracks drift. A simple pressure standard can instead use a liquid-column height difference and the hydrostatic pressure law. [ref]
Measure far-field static and total pressure outside the model's fluid wake; in low-speed incompressible flow their difference gives by the Bernoulli equation, so . Record temperature and ambient pressure to determine mass density using the ideal gas law. At fixed , step the angle of attack, repeat selected settings, and sweep back down to check reproducibility. Record balance lift, each tap's mean pressure, and fluctuation sizes. NASA describes pressure probes connected to differential transducers and emphasizes recording their reference pressure. [ref]
https://www.grc.nasa.gov/www/k-12/airplane/tunptm.html. NASA Glenn, Total Pressure Measurement: probes, tubing and pressure references
Convert each tap to a pressure coefficient . For consecutive taps bounding a panel of length with outward normal vector , a trapezoidal rule estimate of the pressure force per unit span isCompare this with balance lift divided by span only when the spanwise flow is approximately uniform. Agreement tests the pressure-resultant picture; disagreement calls for checking unresolved leading-edge pressure variations, skin shear stress, support loads and three-dimensional end effects before rejecting it. A force balance senses the total load, while taps alone reconstruct the pressure part. Tunnel walls and model blockage alter the effective flow and require corrections; end plates or a model extending between walls approximate two-dimensional flow but do not guarantee it. Record the Reynolds number and Mach number with the result, and do not interpret tunnel lift coefficients as universal wing data. [ref]
https://ocw.mit.edu/courses/16-621-experimental-projects-i-spring-2003/f38ecde8773fd36c0d8f9069e6aa1df5_student_wt_guide.pdf. Covert, pp. 8–9: flow characterization and wall effects
[ref]https://www1.grc.nasa.gov/beginners-guide-to-aeronautics/lift-coefficient/. NASA Glenn, Lift Coefficient: Reynolds and Mach number dependence
Take linearly independent basis functions and write . The weak formulation of the heat equation, tested against , isThus the semidiscrete finite element heat equation isThe vector contains the basis coefficients. A natural initial vector is the projection of the initial data: , where , and . Other consistent initial approximations can be specified, but exact representation of an arbitrary in the trial space is not implicit.
For a nonzero coefficient vector , the function is nonzero by basis independence. Hence , proving that the mass matrix is symmetric positive definite. Also : if the derivative vanished, would be a constant, and its zero endpoint traces would make it zero. Therefore is symmetric negative definite, not merely semidefinite, for these homogeneous Dirichlet conditions.
The squared spatial norm is . Differentiating and using the semidiscrete system gives the energy identityUsing the trapezoidal rule in time gives the Crank-Nicolson methodThe left matrix is positive definite for every , so every step exists uniquely. To prove stability, set and . The update says . Multiplying by givesConsequentlyThe same inequality applied to the difference of two discrete solutions proves nonamplification of initial perturbations. This is unconditional stability in the mass-matrix norm, exactly the spatial norm of the finite element functions.
function trapezoid(f, a, b, n):
dx = (b-a)/n
total = (f(a)+f(b))/2
for j in 1,...,n-1:
total += f(a+j*dx)
return dx*total
function midpoint(f, a, b, n):
dx = (b-a)/n
total = 0
for j in 0,...,n-1:
total += f(a+(j+1/2)*dx)
return dx*totalThe trapezoidal rule gives each endpoint half weight; the composite midpoint rule uses one interior point per subinterval. Both converge for a continuous integrand on the closed interval.
With independent samples and finite variance, Monte Carlo integration has a root-mean-square stochastic error proportional to . The estimated standard error measures that random sampling uncertainty; it is not a deterministic bound.
For a sufficiently smooth one-dimensional integrand, the composite trapezoidal rule has errorfor some , hence . It is normally much more efficient in one dimension. The stated continuity assumption alone guarantees convergence, but does not guarantee this second-order rate; bounded second derivatives are an additional assumption.
The dimensional advantage is different: a tensor grid with total points in dimensions has only about points per direction and typically error . The Monte Carlo exponent remains , although its variance prefactor can still deteriorate with dimension. This explains why the stochastic method becomes attractive for high-dimensional integrals.
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 2002 iii Paper 60 3 b Solution Created 2026-10-03 Updated 2026-10-14
The original PDF has a sign defect in the lower-left stage coefficient. Put . With the printed negative sign, the row sums and the relevant Butcher order conditions areThus the claimed universal second order is false. For example gives, on , two stages equal to and the update . This is the first-order Forward Euler method. For the literal tableau, order at least two holds exactly when or , subject to distinct allowed nodes.
For completeness the literal tableau's A-stability can also be classified algebraically. DefineThe stability function obtained from isIf , the denominator has no zero in the closed left half-plane: its reciprocal roots are the stage-matrix eigenvalues, whose positive sum and nonnegative product give positive real parts for nonzero eigenvalues. On the imaginary axis,Consequently for the literal tableau with uniquely solvable stages throughout the left half-plane, the complete parameter criterion isThese explicit inequalities in are necessary by the small and large imaginary parameters, and sufficient by the maximum modulus principle, including the bound at infinity. For the last inequality forces , leaving the stable linear-fractional case. For there is a negative real stage pole. If one defines stability solely through an analytically continued scalar stability function, the only additional possibilities areIndeed these are precisely the cases where the left pole cancels and is an A-stable theta method. The original stage equations are nevertheless singular at , so they do not give uniquely determined stages there. This distinction prevents a canceled rational factor from concealing an ill-defined stage solve.
The natural intended repair is to replace just the lower-left coefficient by . This makes the method the collocation Runge-Kutta method on the two nodes. To derive the repaired entries, takeIntegration gives the other three printed entries and the weights unchanged, with the positive lower-left entry. Since and , it follows that , and . Hence the corrected family is always of order at least two.
For the corrected family let , and . Its stability function has the same displayed rational form, now with . The denominator again has no left-half-plane zero, and on the imaginary axis the squared-modulus difference is . Because , the necessary and sufficient inequality is , orFor sufficiency, on the imaginary axis and at infinity; apply the maximum modulus principle on growing left half-discs to get the same bound inside. If , the condition leaves the endpoint trapezoidal rule and its linear denominator. If , every nonzero imaginary argument gives . This is the two-node collocation A-stability criterion, explicitly distinguished from the literal defective tableau.
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 2008 ii Paper 3 38C b Solution Created 2026-09-24 Updated 2026-10-14
For , the implicit step map is a contraction, so the Banach fixed-point theorem supplies a unique next value. Smoothness of the exact solution gives the one-step defectuniformly on , by the trapezoidal rule error estimate or a direct Taylor expansion. Let . Subtracting exact and numerical steps and applying the Lipschitz condition givesPut . With , iteration yields . Since , this is . For sufficiently small , , so whenever . ThereforeThis proves convergence with global order two directly from the defect bound and stability recurrence.
Past exam of the mathematics course of the University of Cambridge 2009 iii Paper 72 2 a Solution Created 2026-10-03 Updated 2026-10-14
For this two-step family with a third-order member, use the exponential-symbol order criterion for a multistep method. Expanding the exact-solution residual symbol givesThe constant, linear and quadratic coefficients vanish for every parameter. ThusAt the exceptional value the fourth-degree coefficient is , so there is no further increase. This means an unscaled exact-solution residual of order , or a residual divided by the step of order .
The first characteristic polynomial factors as . The root condition for a multistep method requires every root to have modulus at most one and each unit-modulus root to be simple. The root is allowed because it is distinct from the simple root one; is not, since it makes one a double root. Hence zero-stability holds exactly forOn this interval, and establish consistency of a numerical method. The Dahlquist equivalence theorem, for a fixed-step consistent linear multistep method applied to an ordinary differential equation with a Lipschitz continuous right-hand side with convergent starting values and well-defined small-step updates, says that convergence of a numerical method is equivalent to zero-stability. Therefore the same interval is exactly the convergence of a numerical method range. With sufficiently accurate starting values the convergent members have the orders just computed.
At the Taylor expansion still gives a formal order-two residual, but and the double root prevents a convergent method. Canceling the common factor produces the common-factor cancellation defect in a multistep recurrence and changes the starting relations and cannot repair convergence of a numerical method of the original recurrence. At , cancellation of a zero root instead reveals the ordinary trapezoidal rule; it is consistent with the order-two result.
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 2010 iii Paper 63 6 Solution Created 2026-10-03 Updated 2026-10-14
A-stability removes the scalar linear decay restriction on the step size; it does not replace accuracy, nonlinear solvability or a suitable system norm. Its importance is clearest for a stiff differential equation, where rapidly decaying modes coexist with slowly varying quantities of interest. On the Dahlquist test equation , the exact solution decays for . A stable time integrator should not turn that decay into numerical growth.
For a one-step method write , where and is its stability function. Its linear stability domain consists of parameters with and a well-defined update. The method is A-stable when this domain contains the closed left half-plane. A consistent order- one-step method has near zero, but that local agreement alone says nothing about stability at large negative .
For a Runge-Kutta method with stage matrix , weights and , eliminating the stages on the test equation givesAn explicit finite-stage method has a polynomial . A nonconstant polynomial is unbounded along the negative real axis, so no consistent explicit Runge-Kutta method is A-stable. The explicit Euler method, with , is stable in the disk and on the negative real axis only for . A stiff mode with a large negative eigenvalue therefore forces an unnecessarily small step even after its exact contribution has almost disappeared.
The Backward Euler method has . For , , so it is A-stable. The trapezoidal rule hasand is also A-stable. The implicit midpoint method has the same scalar stability function, although its nonlinear update differs from the trapezoidal rule. The first method has order one and the latter two order two. Their implicit solves trade greater work per step for freedom from the scalar stiff stability restriction.
Absolute stability domains of explicit Euler, backward Euler and the trapezoidal rule; shaded regions satisfy modulus of the amplification factor at most one
. Details. Damping of very stiff modes separates A-stability from L-stability. For a one-step method, the latter additionally requires as tends to infinity in the left half-plane. Backward Euler method satisfies this. The trapezoidal and midpoint rules instead have along the negative real axis: a very stiff mode can alternate in sign with little damping even though its amplitude remains bounded. L-stability is often preferable for diffusion and rapid relaxation, while retaining oscillatory modes can be desirable in conservative dynamics.
For a linear multistep method, writeIts test-equation amplification roots satisfy . Absolute stability requires every root to lie in the unit disk or on its boundary with all unit-modulus roots simple; all parasitic modes matter. At this is the zero-stability root condition. Consistency requires and , and the Dahlquist equivalence theorem combines consistency and zero-stability to characterize convergence. Thus a claim of stability obtained by canceling a common factor is not a proof about the original recurrence and its arbitrary consistent starting data.
Explicit linear multistep methods cannot be A-stable either. If and , some lower coefficient of becomes unbounded as , while the leading coefficient stays fixed. If all roots remained in the unit disk, every coefficient-to-leading-coefficient ratio, an elementary symmetric function of those roots, would remain bounded. This contradiction forces an unstable root.
An important implicit example is BDF2 method, whose characteristic equation is . A unit root givesThe leading coefficient vanishes only at , outside the left half-plane. Near a small negative , both roots are inside the disk; no unit-circle crossing can occur in the connected open left half-plane. On the imaginary axis the boundary equality can occur only at , where the roots are . Hence BDF2 is A-stable and its two roots tend to zero for very large negative , giving strong stiff-mode damping. This is a complete boundary-locus argument, not just a boundary plot.
The Second Dahlquist barrier says that a convergent A-stable ordinary linear multistep method has order at most two. This theorem does not limit implicit Runge-Kutta methods or multiderivative multistep methods. In particular the A-stable third-order two-step multiderivative method in question 1 uses and satisfies different order conditions. Among collocation Runge-Kutta methods, the standard family results give Gauss collocation methods order with diagonal Padé approximants to as stability functions, and Radau IIA methods order with subdiagonal approximants. Both families are A-stable; the Gauss functions have a nonzero limit at infinity, whereas Radau IIA is L-stable. The corrected two-stage right-Radau method, for example, haswhich matches the exponential through cubic order and tends to zero at infinity. Its poles lie in the right half-plane. For , , direct subtraction givesproving its A-stability directly.
Sectorial A-alpha stability relaxes the requirement to a sector around the negative real axis, useful when the spectrum of a stiff problem remains in that sector; higher-order backward differentiation formulas illustrate the usefulness of this weaker requirement. For a normal linear system , unitary diagonalization reduces the numerical update to its scalar factors . For a nonnormal system, a scalar eigenvalue test alone does not give a uniform bound in the chosen norm. Nonlinear stability is different again: B-stability asks for contractivity when , and algebraic stability of a Runge-Kutta method is a standard sufficient criterion. Thus A-stability addresses a precise and valuable linear test, while step selection still has to meet accuracy requirements and the actual implicit equations must be solved on the relevant branch.
Past exam of the mathematics course of the University of Cambridge 2012 iii Paper 69 4 2 Solution Created 2026-10-03 Updated 2026-10-14
Every convergent member is also A-stable. For , put and calculate its boundary-locus test for multistep A-stability:The denominator never vanishes on the unit circle in this parameter interval. It follows thatTherefore no amplification root can cross the unit circle as moves in the open left half-plane. For small negative real , the root near one moves to , inside the circle; the other begins at , also strictly inside. The leading coefficient never vanishes in the left half-plane. Continuity of polynomial roots and connectedness of that half-plane now keep both roots inside everywhere. On its imaginary boundary the same locus has zero real part only at , corresponding to ; that root is simple because .
At , the two interlaced subsequences follow the trapezoidal rule with step :The right side has modulus at most one for . Its unit-circle roots are simple; the double zero at lies strictly inside and is harmless. Thus the endpoint is also A-stable. Combining this with part 1, the requested range is , including the BDF2 method at .






