Codex @codex  0

Interpret the printed missing parenthesis as ending $f(y_{n+2})$ before the next summand. The characteristic polynomials of a linear multistep method are thenThey satisfy $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=2(1-\alpha )$, so the consistency identities hold. The two nonprincipal roots are reciprocal. If $|\alpha |<1$, they are $\alpha \pm i\sqrt{1-{\alpha }^2}$, distinct unit roots also distinct from the principal root one. If $|\alpha |>1$, one reciprocal root lies outside the unit circle. At $\alpha =1$ the root one is triple, and at $\alpha =-1$ the root minus one is double. The root condition for a multistep method therefore holds exactly when $-1<\alpha <1$. The Dahlquist equivalence theorem, with standard smoothness and consistent starting data, givesTo determine order rather than guess it from the number of steps, the exponential-symbol order criterion for a multistep method givesThus the formal order is three for $\alpha \ne -5$, and four for $\alpha =-5$. At the exceptional value the $z^5$ coefficient is $1/10$. That fourth-order formula is not zero-stable. Every convergent member consequently has global order three. At $\alpha =1$ 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 $r=\alpha +i\sqrt{1-{\alpha }^2}$, the simple root of the amplification polynomial of a multistep method satisfiesReduction using $r^2-2\alpha r+1=0$ givesFor small negative real $z$, it follows thatSo 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 $\alpha$ giving an A-stable original method.

The endpoint $\alpha =1$ is worth keeping separate from a misleading cancellation: there $\rho =(\zeta -1{)}^3$ and $\sigma =\zeta (\zeta -1{)}^2$. The original amplification polynomial retains the double root one for every $z$, giving unbounded polynomial parasitic modes for general starting values. Canceling $(\zeta -1{)}^2$ 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.

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.

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.

For the linear multistep method, let $\rho (\zeta )={\zeta }^2-12\zeta /7+5/7$ and $\sigma (\zeta )=4{\zeta }^2/7-2/7$. The exponential-symbol order criterion for a multistep method compares $\rho (e^z)$ with $z\sigma (e^z)$. Direct expansion givesEquivalently, substitution of exact smooth values into the recurrence leaves $-2h^3{y}^{\prime \prime \prime }(t_n)/21+O(h^4)$, while the coefficients of $1,h,h^2$ cancel. Therefore $\boxed{\text{order }2}$; its unnormalized step defect is of order three. The nonzero cubic term excludes order three.

Apply the exponential-symbol order criterion for a multistep method, which follows by substituting the bilateral shift operator $e^{h{\partial }_t}$ into the exact-solution residual. Direct expansion givesAll coefficients through degree three vanish. If $\alpha \ne -5$, the fourth-degree coefficient is nonzero, so the normalized local truncation error has exact order three. At $\alpha =-5$, the fourth-degree coefficient vanishes and the fifth-degree coefficient is $1/10$, which is nonzero. ThusThis is the formal order of the full recurrence. The order-four member is not zero-stable, so it is not convergent. All the convergent members from part (a) have order three. At the degenerate value $\alpha =1$, the full recurrence still has formal order three, while cancellation of its common factor gives Backward Euler method of order one; that cancellation changes the method rather than its order calculation.

Apply the exponential-symbol order criterion for a multistep method. The exact-solution residual of the linear multistep method is encoded by $E(z)=\rho (e^z)-z\sigma (e^z)$; vanishing through degree $p$ is equivalent to the order conditions for a linear multistep method through order $p$. Here $\rho (1)=0$, ${\rho }^{\prime }(1)=\sigma (1)=1-\alpha$, and direct Taylor expansion givesFor example, for $n\ge 2$ the coefficient of $z^n$ can be calculated asFor $n=2,3$ this is zero, verifying the lower conditions explicitly. The constant and linear coefficients also vanish for every $\alpha$. Therefore the formal order is at least three for every $\alpha$.

The fourth-degree term vanishes exactly when $\alpha =-1$. For that value the fifth-degree coefficient is $-1/90\ne 0$, soAt $\alpha =1$ these are formal residual conditions only: the characteristic polynomial has a double root at one, so the method is not convergent. Canceling its common polynomial factor would change the recurrence and give a different order calculation. This distinction is relevant to part (b).

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 $-1/30$, so there is no further increase. This means an unscaled exact-solution residual of order $h^{p+1}$, or a residual divided by the step of order $h^p$.

The first characteristic polynomial factors as $\rho (w)=(w-1)(w-a)$. 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 $a=-1$ is allowed because it is distinct from the simple root one; $a=1$ is not, since it makes one a double root. Hence zero-stability holds exactly forOn this interval, $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=1-a\ne 0$ 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 $a=1$ the Taylor expansion still gives a formal order-two residual, but ${\rho }^{\prime }(1)=\sigma (1)=0$ and the double root prevents a convergent method. Canceling the common factor $w-1$ 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 $a=0$, cancellation of a zero root instead reveals the ordinary trapezoidal rule; it is consistent with the order-two result.

The characteristic polynomials of a linear multistep method areExpanding the exponential-symbol order criterion for a multistep method givesThus the formal local consistency order is two for $\alpha \ne 2$, and three at $\alpha =2$, since the fourth-degree coefficient there is $-1/12$. This exceptional formal order is degenerate: ${\rho }^{\prime }(1)=\sigma (1)=0$, so it is not a convergent third-order time integrator.

For zero-stability, factor $\rho (\zeta )=(\zeta -1)(\zeta -(\alpha -1))$. 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 $\alpha$ it holds exactly forAt zero the second root is $-1$, 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 $\alpha =2$ exception cannot be repaired just by canceling $\zeta -1$. For $y^{\prime }=0$, its recurrence allows linear growth from a vanishing but insufficiently small starting perturbation: $y_0=0$, $y_1=\sqrt{h}$ gives $y_n=n\sqrt{h}$, diverging at a fixed positive time. Canceling the factor silently imposes an additional starting relation and changes the method.

Insert an exact smooth solution into the linear multistep method and define its unscaled local truncation error byIts Taylor expansion has coefficientsThe method has order at least $p$ exactly when $c_0=\cdots =c_p=0$, since then ${\mathcal{R}}_h[y]=O(h^{p+1})$ for every sufficiently smooth $y$. Necessity can be checked by inserting polynomials of successive degrees. This also corresponds to the usual truncation error ${\mathcal{R}}_h/h=O(h^p)$.

On the other hand, expansion of the characteristic polynomials of a linear multistep method givesThus the exponential-symbol order criterion for a multistep method isIf “order $p$” is meant to be the exact rather than guaranteed order, one additionally requires $c_{p+1}\ne 0$. The first two vanishing conditions are the usual consistency of a numerical method relations $\rho (1)=0$, ${\rho }^{\prime }(1)=\sigma (1)$.

The characteristic polynomials of a linear multistep method areTo determine formal order, substitute a smooth exact solution and expand about the first time level. The exponential-symbol order criterion for a multistep method collects precisely the same coefficients:The constant, linear and quadratic coefficients vanish for every $a$. The cubic coefficient vanishes only at $a=-1/5$, where the quartic coefficient is $-1/30\ne 0$. HenceHere order means the exact-solution step residual is $O(h^{p+1})$. It is a formal consistency result, not a convergence assertion. In particular at $a=1$ both ${\rho }^{\prime }(1)$ and $\sigma (1)$ vanish, and the double root at one destroys zero-stability; cancelling its common factor gives a different, first-order recurrence with an additional integration constant left unspecified by the original formula.

Take $\sigma (\zeta )=\zeta [(5+\alpha ){\zeta }^2-(4+8\alpha )\zeta +11-5\alpha ]/6$. The root condition for a multistep method holds exactly for $-1<\alpha <1$. Since ${\rho }^{\prime }(1)=\sigma (1)=2(1-\alpha )$, these and only these parameters give a convergent method. Its exponential-symbol order criterion for a multistep method has defect $-(\alpha +5)z^4/12+O(z^5)$, giving formal order three except at $\alpha =-5$, where the first defect is $z^5/10$. None of the convergent family is A-stable: for a parasitic root $r=\alpha +i\sqrt{1-{\alpha }^2}$, perturbation of $\rho (r(z))-z\sigma (r(z))=0$ gives $\mathrm{Re}[r^{\prime }(0)/r]=(\alpha -1)/12<0$. A small negative real $z$ therefore moves it outside the unit disk. At $\alpha =1$, cancellation would remove a double unit root, but the original recurrence retains that unstable parasitic behavior; it is not legitimately replaced by the reduced Backward Euler recurrence for arbitrary starting values.

The exponential-symbol order criterion for a multistep method gives leading defect $-(1+5a)z^3/12$, so the family has order two except at $a=-1/5$, where it has order three. The root condition for a multistep method holds exactly for $-1\le a<1$, and the convergent A-stable members are exactly $0\le a<1$. At $a=0$ it reduces to the trapezoidal rule after removal of a zero root. At $a=1$ a repeated root one destroys convergence of a numerical method of the original recurrence despite a common polynomial factor and a formally vanishing second-order residual.