Convergence of a numerical method Created 2026-10-06 Updated 2026-10-14
For an initial value problem, convergence means that the largest global error on each fixed finite time interval tends to zero as the step size tends to zero and the starting errors vanish. For linear multistep methods, the Dahlquist equivalence theorem separates this requirement into consistency of a numerical method and zero-stability.
Linear multistep method Created 2026-10-14 Updated 2026-11-05
A linear multistep method approximates an ordinary differential equation using values retained from several time levels. On a uniform grid , its constant-coefficient form is
The linearity is in the way values and derivatives are combined; the vector field itself can be nonlinear. The method is explicit when and implicit when the new value appears inside through . An implicit update requires a suitable algebraic solve, in addition to a formal recurrence.[ref]
The two-step Adams-Bashforth method, for example, uses . It reuses the preceding derivative rather than calculating several new Runge-Kutta stages within one step. A -step recurrence needs starting values, often supplied by a Runge-Kutta method of compatible accuracy.
Consistency controls the defect on a smooth exact solution; zero-stability controls the amplification of starting and local errors. Both are required by the Dahlquist equivalence theorem for convergence under its regularity assumptions. Changing the step sizes generally requires changing the coefficients and revisiting stability; uniform-grid coefficients cannot simply be reused at arbitrary time spacings.
Using Newton-Cotes closed quadrature for the integrated derivative yields the displayed linear multistep method. Its first characteristic polynomial is , whose unit-circle roots are all simple, proving zero-stability. Quadrature exactness gives order for odd and at least for even . The first Dahlquist barrier gives equality, while the Dahlquist equivalence theorem gives convergence with consistent starts. These are finite-time convergence statements, not claims of A-stability.
Interpret the printed missing parenthesis as ending before the next summand. The characteristic polynomials of a linear multistep method are then
They satisfy and , so the consistency identities hold. The two nonprincipal roots are reciprocal. If , they are , distinct unit roots also distinct from the principal root one. If , one reciprocal root lies outside the unit circle. At the root one is triple, and at the root minus one is double. The root condition for a multistep method therefore holds exactly when . The Dahlquist equivalence theorem, with standard smoothness and consistent starting data, gives
To determine order rather than guess it from the number of steps, the exponential-symbol order criterion for a multistep method gives
Thus the formal order is three for , and four for . At the exceptional value the coefficient is . That fourth-order formula is not zero-stable. Every convergent member consequently has global order three. At the third-order Taylor cancellation is only a formal defect property of a degenerate, nonconvergent recurrence.
Here is a direct A-stability test for the convergent parameters. For a nonprincipal unit root , the simple root of the amplification polynomial of a multistep method satisfies
Reduction using gives
For small negative real , it follows that
So even a small negative real test parameter has an amplifying parasitic mode. None of the convergent parameters is A-stable. Parameters outside this range already fail the necessary zero-step root condition, so there is no real giving an A-stable original method.
The endpoint is worth keeping separate from a misleading cancellation: there and . The original amplification polynomial retains the double root one for every , giving unbounded polynomial parasitic modes for general starting values. Canceling would yield a different, reduced Backward Euler method; it does not stabilize the original recurrence. This is the common-factor cancellation defect in a multistep recurrence. The family is summarized by the reciprocal-root three-step multistep family.
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 bound
For the error recurrence is
Iteration, 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.
Work in the standard class of real constant-coefficient linear multistep methods using only first-derivative evaluations. Write
with . The Dahlquist equivalence theorem states that such a method converges on each fixed finite time interval, for sufficiently regular Lipschitz initial value problems and every set of consistent starting values, if and only if it is consistent and zero-stable. Consistency means and . Zero-stability means all roots of lie in and every root on is simple. In particular the consistency root at is simple.
Taylor expansion of the exact-solution residual gives the exponential-symbol order criterion for a multistep method
This criterion packages the identities through . We now derive the upper bound on from the root condition, rather than assuming the first Dahlquist barrier.
Use the Cayley transform and define
The simple root at gives , while and . Each finite transformed root is , with nonpositive real part when . A possible root at simply lowers the degree of . Factor over the reals: a real root contributes with , and a conjugate pair contributes with . Therefore, after reversing the overall sign if needed,
Since , the order criterion is equivalent to
The key coefficient sign lemma for the first Dahlquist barrier is
Here is a proof of that sign assertion. Direct integration gives
Differentiate twice and pair the terms at and to obtain
The power series of has positive odd coefficients. The even powers in the hyperbolic cosine therefore have nonnegative coefficients, and has strictly positive even coefficients. Every even coefficient of is consequently negative. Also is even and , proving the assertion.
If is odd and , the coefficient of in must vanish because . But it is
where out-of-range indices are zero and the sum includes the strictly positive . This is impossible, so . If is even and , exactly the same argument with the coefficient of gives a contradiction. Thus in that case. This proves the Cayley coefficient proof of the first Dahlquist barrier:
To prove that the bound is attainable for every , let be the Lagrange polynomials for the nodes , and take . The Newton-Cotes multistep methods attaining the first Dahlquist barrier are
The underlying Newton-Cotes closed quadrature is exact on all polynomials of degree at most . For even , the node polynomial is odd about , so . Dividing any degree- polynomial by shows that quadrature exactness extends one degree further. Integrating the exact derivative therefore gives method order at least for odd and at least for even .
Finally has only simple unit-circle roots, so these methods satisfy the root condition. The weights sum to , proving consistency. The Dahlquist equivalence theorem gives convergence with consistent starts; the proved upper bound makes the attained formal orders exact; starting values accurate to those orders also give the corresponding global accuracy. Hence the highest convergent order is . This result concerns the stated linear first-derivative class, not unrestricted multiderivative or nonlinear formulas.
Use the coefficient in the numerator, as verified in the PDF; the converted TeX lost its . Multiplying the method by gives the characteristic polynomials of a linear multistep method
For every admissible real , and , giving consistency of a numerical method. Factorization gives
The second root is . The root condition for a multistep method requires and forbids a repeated root at one. For real ,
At both roots equal one, violating zero-stability. For the second root lies strictly inside the unit disk. The Dahlquist equivalence theorem therefore gives
To find the order rather than only consistency, expand the exact-solution residual through the generating function:
Thus its unnormalized local truncation error begins with when , and the global method order is exactly two for every convergent parameter. For comparison, has formal order three but is not convergent because of its double unit root:
These orders assume a smooth solution, the usual local Lipschitz condition and starting approximations of the required accuracy.
A constant-step linear multistep method has the form
with . 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.
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 .
The Dahlquist equivalence theorem states that a linear multistep method is convergent for well-posed sufficiently smooth initial-value problems, with consistent starting values, if and only if it is consistent and zero-stable. Zero-stability means that every root of its first characteristic polynomial lies in the closed unit disk, with roots on the unit circle simple.
Here the characteristic polynomials are
Consistency holds because and . The two remaining roots have product one. For they are distinct conjugate unit roots, and neither equals one. At , the root one is triple; at , the root minus one is double. Outside , the remaining roots are real reciprocal roots and one has modulus greater than one. Thus
The order conditions give and , which is nonzero throughout the convergent range. Therefore the order of convergence is exactly two, for starting approximations of matching accuracy.
Consistency was established in part (a). By the Dahlquist equivalence theorem, convergence additionally requires the root condition for a multistep method. Since , its roots lie in the closed unit disk with each unit-modulus root simple exactly for
The endpoint is zero-stability although it has a simple parasitic root at minus one; has a repeated root at one and is excluded.
For every parameter in this convergent range, the leading coefficient of is , while
Since as , it has a real root . Its other real root lies between minus one and one because , so the exterior root is simple.
On the Dahlquist test equation, the amplification polynomial of a multistep method is , with . For , the equivalent polynomial tends coefficientwise to , and its leading coefficient stays nonzero. Choose a small closed disk about lying wholly outside the unit disk and containing no other root of . On its boundary has a positive minimum, while is smaller for every sufficiently large . Rouché's theorem then puts one root of inside this exterior disk for all such complex .
That root violates the stability root condition for a multistep method. Hence there is a finite radius beyond which no point belongs to the absolute stability domain:
This proves boundedness in every complex direction, rather than only excluding A-stability. It is an instance of exterior roots of the derivative polynomial bound multistep stability.
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 gives
The constant, linear and quadratic coefficients vanish for every parameter. Thus
At 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 for
On 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.
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 method
with 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 form
The 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 has
It 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 satisfy
All 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 is
It has order two, roots at zero step and is A-stable. For its normalized polynomials , , the unit-circle boundary locus has
The 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.
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 gives
An 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 has
and 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.
Figure 1.
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, write
Its 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 gives
The 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, has
which matches the exponential through cubic order and tends to zero at infinity. Its poles lie in the right half-plane. For , , direct subtraction gives
proving 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.
The characteristic polynomials of a linear multistep method are
Expanding the exponential-symbol order criterion for a multistep method gives
Thus the formal local consistency order is two for , and three at , since the fourth-degree coefficient there is . This exceptional formal order is degenerate: , so it is not a convergent third-order time integrator.
For zero-stability, factor . The root condition for a multistep method requires every root to have modulus at most one and every unit-modulus root to be simple. For real it holds exactly for
At zero the second root is , simple and admissible; at two the root one is double and inadmissible. Outside the closed interval the second root has modulus greater than one. The Dahlquist equivalence theorem says that a consistent linear multistep method is convergent exactly when it is zero-stable, for a locally Lipschitz initial-value problem with consistent starting values and solvable implicit steps. Hence the displayed interval is also exactly the convergence range, and every convergent member has order two.
The common-factor cancellation defect in a multistep recurrence explains why the exception cannot be repaired just by canceling . For , its recurrence allows linear growth from a vanishing but insufficiently small starting perturbation: , gives , diverging at a fixed positive time. Canceling the factor silently imposes an additional starting relation and changes the method.
Let . The chain rule gives along a smooth solution. Expanding every term about , the unscaled exact-solution residual of this multiderivative multistep method is
For example, at derivative degree its coefficient is
the coefficients at degrees zero, one and two vanish. Thus the formal order of a numerical method is two for , and three for , where the fourth-degree coefficient is . This order statement describes the exact-solution defect; convergence also needs zero-stability.
At the characteristic polynomial is
The root condition for a multistep method holds exactly when and . In particular has two distinct unit roots and is admissible, whereas has a repeated unit root. Applying the permitted Dahlquist equivalence theorem for this multiderivative setting, with smooth , the nearby implicit solution branch and convergent starting values, yields
All those methods have global order two, provided the starting errors are . The formally third-order choice is not zero-stable and therefore is not convergent as a method for general initial-value problems.
One can see the failure without any nonlinear difficulty. For , an error mode grows exponentially if . At , ; choosing , gives vanishing starting errors but . This also explains why a small residual alone does not rescue that degenerate choice: at the first-derivative term disappears and the formula has no zero-stable first-order evolution interpretation.
The relevant one of the characteristic polynomials of a linear multistep method is
The coefficients on the right are chosen to give third order, so consistency of a numerical method is already available. By the Dahlquist equivalence theorem, convergence with convergent starting values is equivalent to zero-stability: every root of must satisfy , and every root on the unit circle must be simple.
If , the quadratic is negative at and tends to as , so it has a root less than . If , its root product is , so at least one root has modulus greater than one. For , its real roots lie in . For , its conjugate roots have modulus .
At , the three roots are , with the unit-modulus roots simple. At , they are , again simple. The repeated quadratic root at is , strictly inside the unit circle, which the root condition for a multistep method permits. Therefore
This is the root stability of a cubic multistep polynomial; oscillatory parasitic roots at the endpoints do not invalidate convergence when their starting amplitudes tend to zero.
The Dahlquist equivalence theorem states that a consistent linear multistep method is convergent for suitably consistent starting values exactly when it is zero-stable. The root condition for a multistep method requires every root of to lie in the closed unit disk, with every unit-modulus root simple.
The roots are and . Thus is necessary; is excluded because it gives a double root at one. At , the two unit roots are distinct, so the endpoint is allowed. Combined with part (a), this proves
Assume a locally Lipschitz vector field, a smooth solution on the fixed time interval, a nearby solvable implicit branch and starting errors of the required order. The global order is three at and two at the other convergent parameter values. Outside this interval, zero-step perturbations already grow through either an exterior root or a unit-root polynomial factor.
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 formula
Its 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 is
This 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: and
is 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.
The characteristic polynomials of a linear multistep method are
The consistency of a numerical method conditions hold for every real :
Both roots of a polynomial of , namely and , are simple and have modulus one. The root condition for a multistep method therefore gives zero-stability for every . The Dahlquist equivalence theorem now gives convergence for every fixed . As usual, this means convergence of a numerical method on each fixed finite interval for a sufficiently regular ordinary differential equation with a Lipschitz continuous vector field and starting values tending to the exact starting values. When , the implicit time-stepping method update is locally uniquely solvable for sufficiently small , for example by a contraction mapping if . Zero-stability does not assert that a large fixed step is suitable for a stiff differential equation.