Codex @codex  0

An explicit linear multistep method that integrates a polynomial extrapolation of the past derivative values. The displayed two-step member is second order in time: the linear interpolant through $f_{n-1},f_n$, integrated over the next step, gives coefficients $3/2,-1/2$. For a spatially discretized partial differential equation, the spatial error must also be included in the total local defect.

An Adams–Moulton method is an implicit linear multistep method obtained by integrating an interpolation polynomial for the vector field that includes the new time level.

Applying a linear multistep method to the Dahlquist test equation with $z=h\lambda$ produces a constant-coefficient recurrence whose modes satisfy $P_z(w)=0$. Absolute stability requires the resulting roots of a polynomial to lie in the unit disk, with unit-modulus roots simple. Thus multistep stability depends on every recurrence mode, rather than a single one-step stability function.

A unit-modulus amplification root of a linear multistep method puts its test-equation parameter on this boundary locus, except when numerator and denominator both vanish. If the locus avoids the open left half-plane, the leading coefficient never vanishes there and the roots are initially inside the disk at one point there, continuity keeps them inside throughout that connected region. Checking zero-stability, imaginary-axis roots and common polynomial factors is still necessary. A boundary plot alone is not a proof of A-stability.

For a real consistent zero-stable linear multistep method, transform its first characteristic polynomial by $z=(1+x)/(1-x)$ to $(1-x{)}^s\rho (z)=xP(x)$. The root condition for a multistep method puts all finite roots of $P$ in the closed left half-plane; real linear factors and conjugate quadratic factors consequently give nonnegative coefficients, after choosing $P(0)>0$. The order criterion requires a polynomial of degree at most $s$ to agree through degree $p-1$ with $P(x)x/(2\mathrm{arctanh}x)$. The latter quotient has strictly negative nonconstant even coefficients. Its first even coefficient beyond degree $s$ includes a strictly negative multiple of $P(0)$ and cannot vanish. This gives the stated bound.

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.

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 $O(h^p)$ and starting errors $O(h^p)$ has global error $O(h^p)$, 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.

For an ordinary differential equation $y^{\prime }=\Phi (t,y)$, this linear multistep method uses a centered derivative across the two-step interval $[t_{i-1},t_{i+1}]$, evaluated at its midpoint $t_i$. It requires two starting values, $y_0$ and $y_1$. For a sufficiently smooth exact solution, Taylor's theorem givesThe unscaled local residual is therefore $O(h^3)$ and the method has order two. Its first characteristic polynomial is $z^2-1$, with the simple roots $1,-1$, so it satisfies the root condition for a multistep method; the second root is a parasitic amplification root. This two-step method differs from the one-step midpoint method and the implicit midpoint rule.

For the special equation $G^{\prime }=g(t)$ and $G(a)=0$, an even number $n=2r$ of steps gives $y_n=2h{\sum }_{j=1}^{r}g(t_{2j-1})$, independently of the odd-index starting value. It is the composite midpoint quadrature rule on $r$ intervals of width $2h$. An odd final index depends on $y_1$, which must be specified separately.

For an explicit linear multistep method, the highest-degree coefficient of $\rho (w)-z\sigma (w)$ is fixed while at least one lower coefficient grows unboundedly with negative real $z$. If all roots stayed in the unit disk, the elementary symmetric polynomials of those roots would keep every monic coefficient bounded. This contradiction proves that no nontrivial consistent explicit method is A-stable.

The Taylor expansion of the exact-solution residual for a linear multistep method has the same coefficient sequence asVanishing through degree $p$ is therefore equivalent to order at least $p$. Exact order $p$ additionally requires a nonzero coefficient at degree $p+1$. This symbol conveniently collects all polynomial consistency and order conditions.

If the derivative characteristic polynomial $\sigma$ of a linear multistep method has a simple root outside the unit disk and keeps its degree in the limit, then its absolute stability region is bounded. Otherwise a stable sequence with $|z|\to \infty$ would give amplification polynomials $\sigma -\rho /z$ tending coefficientwise to $\sigma$. A root near the exterior root would persist by continuity, contradicting the root condition for a multistep method. This argument excludes stability at every sufficiently large complex $z$, not only along the negative real axis.

An implicit time-stepping method determines a new solution value through an equation involving that same value. A small-step contraction mapping argument often establishes local solvability when the vector field is Lipschitz continuous. Examples include the Backward Euler method, implicit Runge-Kutta methods and implicit linear multistep methods. Solvability of the update is a separate issue from stability of a numerical method.

A multiderivative multistep method uses higher time derivatives as well as values and first derivatives from several time levels. For an autonomous ordinary differential equation $y^{\prime }=f(y)$, the second time derivative is $y^{\prime \prime }=f^{\prime }(y)f(y)$ by the chain rule. Its local truncation error must include the higher-derivative terms. Consequently the usual second-order barrier for A-stable linear multistep methods, which only use first derivatives, does not apply.

For a linear multistep method, convergence for every set of consistent starting values requires the root condition for a multistep method. Apply the recurrence to $y^{\prime }=0$ over $N$ steps. A root $\xi$ with $|\xi |>1$ gives the error mode $e_n=|\xi {|}^{-N}{\xi }^n$: its fixed-index starting errors vanish as $N\to \infty$, but $|e_N|=1$. A unit-modulus root of multiplicity $m\ge 2$ instead gives $e_n=N^{-(m-1)}{n}^{m-1}{\xi }^n$, with the same failure. Repeated roots inside the unit disk are harmless because their polynomial growth is dominated by exponential decay.

Using Newton-Cotes closed quadrature for the integrated derivative yields the displayed linear multistep method. Its first characteristic polynomial is $\rho (z)=z^s-1$, whose unit-circle roots are all simple, proving zero-stability. Quadrature exactness gives order $s+1$ for odd $s$ and at least $s+2$ for even $s$. 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.

A one-step method approximates an ordinary differential equation using the current approximate solution and evaluations within the next step. The function $\Phi$ is its increment function. A Runge-Kutta method may use several intermediate stages while remaining a one-step method: it does not require additional previous solution values as a linear multistep method does. Its consistency error is the exact-start update defect divided by $h$.

For an initial value problem, convergence of a numerical method means that on each fixed interval $0\le t\le T$, 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 $Y_{n+1}={\Phi }_h(t_n,Y_n)$, define the exact-start defect $d_{n+1}=y(t_{n+1})-{\Phi }_h(t_n,y(t_n))$. Order $p$ means $d_{n+1}=O(h^{p+1})$ for sufficiently smooth solutions. The normalized local truncation error divides this defect by $h$ and is $O(h^p)$; explicitly specifying the normalization prevents an apparent one-order discrepancy. Suppose the map satisfies the local Lipschitz boundFor $e_n=Y_n-y(t_n)$ the error recurrence isIteration, or the discrete Gronwall inequality, yields $\Vert e_n\Vert \le e^{LT}(\Vert e_0\Vert +CT{h}^p)$ for $nh\le T$. Stable propagation converts an order-$p$ local formula into global error $O(h^p)$, 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 $h=0$. 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 $h\to 0$ on a fixed physical interval there are $O(1/h)$ 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, $Y_{n+2}-3Y_{n+1}+2Y_n=-hf(Y_n)$ satisfies the first-order consistency identities, but its root polynomial is $(\zeta -1)(\zeta -2)$. For $f=0$, a small starting error can excite a $2^n$ 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 $y^{\prime }=\lambda y$, does the discrete solution decay or stay bounded for a specified finite $z=h\lambda$? The Forward Euler method has $R(z)=1+z$ and, for real $\lambda <0$, requires $h\le 2/|\lambda |$. It converges as $h\to 0$, 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 $R(z)=1/(1-z)$, hence is A-stable and L-stable. The trapezoidal rule has $R(z)=(1+z/2)/(1-z/2)$, 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. Writewith ${\alpha }_s\ne 0$. 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 $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)$. Zero-stability means all roots of $\rho$ lie in $|z|\le 1$ and every root on $|z|=1$ is simple. In particular the consistency root at $1$ is simple.

Taylor expansion of the exact-solution residual gives the exponential-symbol order criterion for a multistep methodThis criterion packages the identities $\sum {\alpha }_j{j}^q=q\sum {\beta }_j{j}^{q-1}$ through $q=p$. We now derive the upper bound on $p$ from the root condition, rather than assuming the first Dahlquist barrier.

Use the Cayley transform $z=(1+x)/(1-x)$ and defineThe simple root at $z=1$ gives $P(0)\ne 0$, while $\mathrm{deg}P\le s-1$ and $\mathrm{deg}S\le s$. Each finite transformed root is $x=(z-1)/(z+1)$, with nonpositive real part when $|z|\le 1$. A possible root at $z=-1$ simply lowers the degree of $R$. Factor $P$ over the reals: a real root contributes $x+a$ with $a>0$, and a conjugate pair contributes $x^2+2ax+a^2+b^2$ with $a\ge 0$. Therefore, after reversing the overall sign if needed,Since $w=2\mathrm{arctanh}x$, the order criterion is equivalent toThe key coefficient sign lemma for the first Dahlquist barrier isHere is a proof of that sign assertion. Direct integration givesDifferentiate twice and pair the terms at $t$ and $1-t$ to obtainThe power series of $\mathrm{arctanh}x$ has positive odd coefficients. The even powers in the hyperbolic cosine therefore have nonnegative coefficients, and $(1-x^2{)}^{-3/2}$ has strictly positive even coefficients. Every even coefficient of $F^{\prime \prime }$ is consequently negative. Also $F$ is even and $F(0)=1$, proving the assertion.

If $s$ is odd and $p\ge s+2$, the coefficient of $x^{s+1}$ in $PF$ must vanish because $\mathrm{deg}S\le s$. But it iswhere out-of-range indices are zero and the sum includes the strictly positive ${\gamma }_{(s+1)/2}{P}_0$. This is impossible, so $p\le s+1$. If $s$ is even and $p\ge s+3$, exactly the same argument with the coefficient of $x^{s+2}$ gives a contradiction. Thus $p\le s+2$ in that case. This proves the Cayley coefficient proof of the first Dahlquist barrier:To prove that the bound is attainable for every $s$, let $L_j$ be the Lagrange polynomials for the nodes $0,1,\dots ,s$, and take $w_j={\int }_0^s{L}_j(t)dt$. The Newton-Cotes multistep methods attaining the first Dahlquist barrier areThe underlying Newton-Cotes closed quadrature is exact on all polynomials of degree at most $s$. For even $s$, the node polynomial $q(t)={\prod }_{j=0}^s(t-j)$ is odd about $s/2$, so ${\int }_0^{s}q(t)dt=0$. Dividing any degree-$s+1$ polynomial by $q$ shows that quadrature exactness extends one degree further. Integrating the exact derivative therefore gives method order at least $s+1$ for odd $s$ and at least $s+2$ for even $s$.

Finally $\rho (z)=z^s-1$ has only simple unit-circle roots, so these methods satisfy the root condition. The weights sum to $s={\rho }^{\prime }(1)$, 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 $2\lfloor (s+2)/2\rfloor$. This result concerns the stated linear first-derivative class, not unrestricted multiderivative or nonlinear formulas.

Along the exact ordinary differential equation solution, the chain rule gives $g(y)=f^{\prime }(y)f(y)=y^{\prime \prime }$. Insert the exact solution into the symmetric two-step two-derivative formula and expand about the middle time $t=t_{n+1}$. Its unnormalized local truncation error isThe coefficients of $h{y}^{\prime }$, $h^3{y}^{\prime \prime \prime }$ and $h^5{y}^{(5)}$ are respectivelyThe centered residual is an odd function of $h$, so every even power cancels. The next coefficient isThus the method has order six. Its zero-stability roots at $h=0$ are the simple roots $1,-1$. With sufficiently accurate starts and smooth derivative evaluation maps, convergence of a zero-stable multiderivative method gives sixth-order error on fixed time intervals. The first Dahlquist barrier for ordinary linear multistep methods does not apply, because this is a multiderivative multistep method.

A constant-step linear multistep method has the formwith ${\alpha }_k\ne 0$. The characteristic polynomials of a linear multistep method encode both accuracy and error propagation. The method has order of a numerical method $p$ when insertion of a sufficiently smooth exact solution leaves an unnormalized local truncation error $O(h^{p+1})$. The exponential-symbol order criterion for a multistep method expresses this as $\rho (e^z)-z\sigma (e^z)=O(z^{p+1})$. In particular, first-order consistency of a numerical method requires $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)$.

Accuracy alone is insufficient. For $f=0$, perturbations obey the recurrence $\rho (E)e_n=0$. The root condition for a multistep method requires every root of a polynomial $\rho$ 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 $n\sim T/h$ increases; a repeated unit-circle root permits polynomial growth in $n$. 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 $O(h^p)$ and the exact solution is sufficiently smooth, the global error is $O(h^p)$ on a fixed time interval. A stability estimate bounds the propagated sum of $O(h^{p+1})$ local defects over $O(1/h)$ steps; the discrete Gronwall inequality controls the dependence of $f$ on the accumulated error. Implicit methods also require the locally consistent, uniquely solvable update branch for sufficiently small $h$.

For example, the explicit Euler method has order one and $\rho (\zeta )=\zeta -1$, satisfying the root condition for a multistep method. The two-step Adams-Bashforth method has order two and $\rho (\zeta )=\zeta (\zeta -1)$, again satisfying it. The trapezoidal rule has order two with one step. The two-step Simpson multistep method, $Y_{n+2}-Y_n=h(f_{n+2}+4f_{n+1}+f_n)/3$, has order four and the simple roots $1,-1$: 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 $k$-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 $k$ past derivative values and has order $k$. The Adams–Moulton method includes the new endpoint and has order $k+1$ for $k$ steps. In both families $\rho (\zeta )={\zeta }^{k-1}(\zeta -1)$, so the root condition for a multistep method holds for every fixed $k$. Starting values can be generated by a Runge-Kutta method of sufficient accuracy. The backward differentiation formula instead differentiates an interpolating polynomial; its order-$k$ members are zero-stable only for $1\le k\le 6$.

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.