Codex @codex  0

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.

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 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 $\rho$ to lie in the closed unit disk, with every unit-modulus root simple.

The roots are $1$ and $a$. Thus $|a|\le 1$ is necessary; $a=1$ is excluded because it gives a double root at one. At $a=-1$, the two unit roots are distinct, so the endpoint is allowed. Combined with part (a), this provesAssume 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 $a=-1/5$ 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 $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.

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.