Codex @codex  0

Let $g(y)=f_y(y)f(y)$. The chain rule gives $y^{\prime \prime }=g(y)$ along a smooth solution. Expanding every term about $t_n$, the unscaled exact-solution residual of this multiderivative multistep method isFor example, at derivative degree $q\ge 2$ its coefficient isthe coefficients at degrees zero, one and two vanish. Thus the formal order of a numerical method is two for $a\ne 11/5$, and three for $a=11/5$, where the fourth-degree coefficient is $-4/15$. This order statement describes the exact-solution defect; convergence also needs zero-stability.

At $h=0$ the characteristic polynomial isThe root condition for a multistep method holds exactly when $|a|\le 1$ and $a\ne 1$. In particular $a=-1$ has two distinct unit roots and is admissible, whereas $a=1$ has a repeated unit root. Applying the permitted Dahlquist equivalence theorem for this multiderivative setting, with smooth $f$, the nearby implicit solution branch and convergent starting values, yieldsAll those methods have global order two, provided the starting errors are $O(h^2)$. The formally third-order choice $a=11/5$ 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 $y^{\prime }=0$, an error mode $e_n=a^n{e}_0$ grows exponentially if $|a|>1$. At $a=1$, $e_n=C+Dn$; choosing $e_0=0$, $e_1=h$ gives vanishing starting errors but $e_{T/h}=T$. This also explains why a small residual alone does not rescue that degenerate choice: at $a=1$ 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 isThe 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 $\rho$ must satisfy $|w|\le 1$, and every root on the unit circle must be simple.

If $a<0$, the quadratic is negative at $w=-1$ and tends to $+\infty$ as $w\to -\infty$, so it has a root less than $-1$. If $a>1$, its root product is $a$, so at least one root has modulus greater than one. For $0\le a\le 1/4$, its real roots $(-1\pm \sqrt{1-4a})/2$ lie in $[-1,0]$. For $1/4<a\le 1$, its conjugate roots have modulus $\sqrt{a}\le 1$.

At $a=0$, the three roots are $1,0,-1$, with the unit-modulus roots simple. At $a=1$, they are $1,e^{2\pi i/3},e^{-2\pi i/3}$, again simple. The repeated quadratic root at $a=1/4$ is $-1/2$, strictly inside the unit circle, which the root condition for a multistep method permits. ThereforeThis 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 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.

Use the standard A-stability convention including the root condition at $z=h\lambda =0$. The amplification polynomial of a multistep method isZero-stability first restricts the possible parameters to $-1\le a<1$. For $-1<a<0$, as $z$ tends to negative infinity, one amplification root tends to $(3a-1)/(1+a)$, whose modulus exceeds one. For $a=-1$, the characteristic equation is ${\zeta }^2-2z\zeta -1=0$; large negative real $z$ likewise gives an exterior root. Thus $a\ge 0$ is necessary.

For sufficiency take $0\le a<1$. The leading coefficient cannot vanish in the closed left half-plane. On the unit circle $\zeta =e^{i\theta }$ the boundary-locus test for multistep A-stability uses $z=\rho (\zeta )/\sigma (\zeta )$ and giveswhere the denominator is nonzero. When $a=0$, the exceptional zero of $\sigma$ at $\zeta =-1$ is not a zero of $\rho$ and therefore cannot be an amplification root for a finite $z$. Near $z=0$ on the negative real axis, the root issuing from one is $1+z+O(z^2)$ and is strictly inside the disk; the other root is close to $a$ and is also inside. Roots vary continuously, cannot escape through infinity because the leading coefficient is nonzero, and cannot cross the unit circle anywhere in the open left half-plane by the displayed boundary formula. Thus every root remains inside there. Continuity gives the boundary case; for $a>0$ a unit root on the imaginary axis can occur only at $z=0$, where it is simple. For $a=0$, cancellation of the harmless zero root leaves the trapezoidal rule, whose amplification factor has modulus at most one.

ThereforeThe third-order member is convergent but not A-stable, consistent with the Second Dahlquist barrier. At $a=1$, $P_z=(\zeta -1)[(1-z)\zeta -1]$ has a permanent unit root and a double root at $z=0$: the unreduced method is not zero-stable and is not A-stable under the stated convention. Testing only the open half-plane while overlooking its zero-step behavior would give a weaker conclusion.

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 $y^{\prime }=\lambda y$, whose exact solution decays when $\mathrm{Re}\lambda <0$.

For a one-step method, write $y_{n+1}=R(z)y_n$, $z=h\lambda$. Its linear stability domain consists of the points where the update is defined and $|R(z)|\le 1$. 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 $R(z)=1+z+O(z^2)$, and order $p$ requires $R(z)-e^z=O(z^{p+1})$. Poles must be absent from the relevant half-plane. The Forward Euler method has $R=1+z$ and the disk $|1+z|\le 1$, so negative real modes require $h|\lambda |\le 2$; it is not A-stable. The Backward Euler method has $R=(1-z{)}^{-1}$, and $|1-z|\ge 1$ 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 $z\to -\infty$. L-stability additionally requires $R(z)\to 0$ 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 $\rho ,\sigma$, and its scalar modes satisfy $\rho (\zeta )-z\sigma (\zeta )=0$. There is generally no single scalar amplification factor: every root must lie in the closed unit disk and unit roots must be simple. At $z=0$, 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 formulaIts zero-step roots are $1,1/3$. Its unit-circle boundary quotient has real part $(1-\cos \theta {)}^2\ge 0$, 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 $Y=e{y}_n+zAY$. Whenever these stages are solvable, its stability function isThis 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 $R$ the diagonal degree-two Padé approximant. More generally the $s$-stage Gauss--Legendre Runge-Kutta method has order $2s$ and is A-stable, with the diagonal Padé approximation to $e^z$; its stiff-limit factor is nonzero. The $s$-stage Radau IIA method has order $2s-1$ 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: $b_i\ge 0$ andis 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 $-1/36$, 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 areThe consistency of a numerical method conditions hold for every real $a$:Both roots of a polynomial of $\rho$, namely $1$ and $-1$, are simple and have modulus one. The root condition for a multistep method therefore gives zero-stability for every $a$. The Dahlquist equivalence theorem now gives convergence for every fixed $a\in \mathbb{R}$. 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 $a\ne 0$, the implicit time-stepping method update is locally uniquely solvable for sufficiently small $h$, for example by a contraction mapping if $|ha|L<1$. Zero-stability does not assert that a large fixed step is suitable for a stiff differential equation.

Expand the exact solution about $t_{n+1}=t$. The unscaled local truncation error isOnly odd powers occur in this centered expansion. Unless $a=1/3$, the first nonzero coefficient is the $h^3$ coefficient, giving order of a numerical method two. For $a=1/3$, that term vanishes but the next coefficient is $-1/90$, giving order of a numerical method four. ThusThese are exact orders for general smooth ordinary differential equations, since the respective first surviving derivatives need not vanish. With starting errors $O(h^p)$, the zero-stability established in part (a) makes the global error $O(h^p)$.

Consider an initial value problem $y^{\prime }=f(t,y)$ on $[0,T]$, with a Lipschitz continuous vector field in the solution variable and enough smoothness for the stated error expansions. Convergence of a numerical method meanswith consistent starting values. An order of a numerical method $p$ quantifies this approximation: with sufficiently accurate starting data and the required stability, the global error is $O(h^p)$. Stability of a numerical method controls the amplification and accumulation of perturbations; it is the link between a small local defect and small global error.

For a one-step formula $Y_{n+1}={\Phi }_h(t_n,Y_n)$, define the unscaled local truncation errorThe method has local order $p$ if $\Vert d_{n+1}\Vert \le C{h}^{p+1}$ uniformly along sufficiently smooth solutions. If the defect is divided by $h$, its order is instead $O(h^p)$; the convention must be specified. Assume also the perturbation estimateThe global error $e_n=Y_n-y(t_n)$ then satisfiesIterating, or applying the discrete Gronwall inequality, givesThere are $O(1/h)$ steps on a fixed interval, so stable propagation turns $O(h^{p+1})$ local defects into $O(h^p)$ accumulated error. Starting error $O(h^p)$ is needed to retain order $p$. This explains why matching an exact Taylor expansion is insufficient unless errors are controlled during repeated steps.

For a fixed-coefficient linear multistep method, writeThe consistency of a numerical method conditions are $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)$. The higher order conditions for a linear multistep method arewith right side zero for $q=0$; exact order $p$ means first failure at $q=p+1$. They come from inserting the exact solution and comparing its Taylor expansion.

Errors at $h=0$ follow the homogeneous recurrence determined by $\rho$. Zero-stability is equivalent to the root condition for a multistep method: all roots of a polynomial have modulus at most one, and every unit-modulus root is simple. Roots outside the disk give exponential growth in the number of steps; repeated unit roots give polynomial growth in that number. Repeated interior roots are harmless because their polynomial factors are dominated by decay. Under the usual Lipschitz continuity and initialization assumptions, the Dahlquist equivalence theorem givesFor a zero-stable order-$p$ linear multistep method, local defects and starting errors of the stated orders yield global error $O(h^p)$ by a recurrence bound and the discrete Gronwall inequality. Every required starting value matters.

A concrete failure of “consistency implies convergence” isHere $\rho =(\zeta -1)(\zeta -2)$ and $\sigma =-1$, so $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=-1$: the method is consistent, of order one. But its root $2$ violates zero-stability. For $y^{\prime }=0$ with exact solution zero and starting values $Y_0=0$, $Y_1=h^2$, the computed solution is $Y_n=h^2(2^n-1)$. These starting errors vanish, yet at $n\approx T/h$ the error diverges. Local accuracy cannot compensate for an unstable recurrence.

A different meaning of stability concerns a fixed step on decaying equations. The Dahlquist test equation $y^{\prime }=\lambda y$ introduces $z=h\lambda$. A one-step method gives $Y_{n+1}=R(z)Y_n$ and is absolutely stable when $|R(z)|\le 1$. For a linear multistep method, the corresponding amplification polynomial of a multistep method is $\rho (\zeta )-z\sigma (\zeta )$, and every root must satisfy the bounded root condition, not just the root approximating $e^z$. Strict asymptotic decay requires the roots to have modulus less than one for $\mathrm{Re}z<0$. This distinction matters at reducible methods with an undamped parasitic mode, as in question 1(c).

The Forward Euler method has order one and $R(z)=1+z$, so its linear stability domain is $|1+z|\le 1$. For $y^{\prime }=-\kappa y$, with $\kappa >0$, it requires $0\le h\kappa \le 2$. It converges as $h\to 0$, yet an excessively large step can produce growing oscillations on an exactly decaying problem. The Backward Euler method has the same order, but $R(z)=(1-z{)}^{-1}$ makes it A-stable and L-stable. For a stiff differential equation, fast decay can impose a severe explicit time-step restriction even when accuracy of the slow dynamics would permit a much larger step.

The trapezoidal rule has order two and is A-stable, but is not L-stable, since its stability function tends to $-1$ along the negative real axis. The Second Dahlquist barrier limits an irreducible A-stable linear multistep method to order at most two. This does not limit implicit Runge-Kutta methods: question 4's Lobatto IIIA method is fourth-order and A-stable. Conversely, question 1's fourth-order member is convergent but not A-stable. These examples show that order of a numerical method, zero-stability and A-stability answer different questions.

For nonlinear dissipative problems, B-stability controls distances between numerical solutions; algebraic stability of a Runge-Kutta method is a sufficient coefficient criterion. Question 4 shows that A-stability alone does not imply that coefficient criterion. Variable time steps require additional analysis of step ratios and error propagation, and stiff problems may require uniform-in-stiffness error estimates beyond the fixed-problem convergence result. The useful chain is local accuracy plus the appropriate perturbation bound, giving global accuracy; absolute and nonlinear stability then determine which practical time steps preserve the intended dynamics.

Insert an exact solution into the linear multistep method and use $f(t,y(t))=y^{\prime }(t)$. Its local residual isExpanding both terms by Taylor theorem givesConsequently $C_0=\cdots =C_p=0$ is sufficient for order at least $p$. It is also necessary: test the residual on the polynomials $y(t)=1,t,\dots ,t^p$, evaluating at $t=0$. For $y(t)=t^k$, it equals $h^k{C}_k$ (and equals $C_0$ for the constant), which can be $O(h^{p+1})$ only if $C_k=0$. These functions can be realized as exact solutions of suitable smooth ordinary differential equations, so this is a genuine necessity test. Thus the order conditions areThis is a statement about local order; zero-stability is the separate condition that turns it into convergent approximation.

The Dahlquist equivalence theorem states that a linear multistep method has convergence of a numerical method if and only if it is consistent and zero-stable, under the standard assumptions for the initial value problem and convergent starting values. Consistency of a numerical method means order at least one, orThe root condition for a multistep method expresses zero-stability: every root of $\rho$ has modulus at most one, and every root with modulus one is simple. Usual hypotheses include a well-posed ordinary differential equation with $f$ continuous in time and Lipschitz continuous in the solution variable, a valid step equation, and starting approximations converging to the exact values.

With ${\rho }_0=a$, ${\rho }_1=\theta$, ${\rho }_2=1$, the constant order condition gives $a=-1-\theta$. The next three order conditions for a linear multistep method giveSolving this linear system yields the unique coefficients of order at least three:The characteristic polynomial controlling zero-stability factors asThe other root is $-1-\theta$. Requiring its modulus to be at most one gives $-2\le \theta \le 0$, but $\theta =-2$ produces a repeated root at one and violates the root condition for a multistep method. At $\theta =0$, the roots $1,-1$ are both simple, so that endpoint is allowed. By the Dahlquist equivalence theorem, the method converges precisely forThe fourth defect coefficient is $C_4=\theta$, so the method has order exactly three for nonzero $\theta$. At $\theta =0$ it is the two-step Simpson method, of order four; thus the extra-order endpoint has correctly remained in the answer.

The first characteristic polynomials of a linear multistep method isThe root condition for a multistep method requires $|\alpha |\le 1$ and excludes $\alpha =1$, where the root of a polynomial at one is double. At $\alpha =-1$, the two unit-modulus roots of a polynomial are distinct, so zero-stability holds. For $\alpha \ne 1$, the first-order consistency of a numerical method identity is ${\rho }^{\prime }(1)=1-\alpha$, equal to the coefficient of $hf$.

Using the permitted Dahlquist equivalence theorem in this multiderivative multistep method setting givesThis means convergence on every fixed finite time interval where the smooth exact solution of a differential equation exists, with consistent starting values and the nearby branch of each implicit solve. More specifically, the convergence of a zero-stable multiderivative method gives order $p$ when the starting errors are $O(h^p)$ and both $f$ and $f^{\prime }f$ are locally uniformly Lipschitz continuous on the relevant region.

The exclusions are genuine. For $y^{\prime }=0$ and $|\alpha |>1$, an arbitrarily small parasitic starting error is amplified as ${\alpha }^n$. At $\alpha =1$, take $y_0=0$, $y_1=h$, also for $y^{\prime }=0$. The exact solution is zero, but the numerical recurrence gives $y_n=nh$, an error of order one at fixed positive time. This proves failure even though the starting values converge.