Codex @codex  0

A numerical time-stepping method is $A(\alpha )$-stable if its absolute stability region contains the negative-axis sector $\{z:|\arg (-z)|\le \alpha \}$, for $0<\alpha \le \pi /2$. With a stability function $R$, this requires $|R(z)|\le 1$ throughout that sector. At $\alpha =\pi /2$, this is A-stability.

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.

An algebraically stable Runge-Kutta method is B-stable: for a dissipative vector field, a well-defined step cannot increase the distance between two starting values. This assumes that the compared stage equations have solutions, as required by stage solvability of an implicit Runge-Kutta method. The Runge-Kutta contractivity identity expresses the distance change as a nonpositive weighted term coming from the dissipative vector field minus a nonnegative quadratic form involving the matrix defining algebraic stability. Positive weights also rule out stage poles in the open left half-plane on the scalar test equation, giving A-stability there; zero-weight redundant stages need separate solvability attention.

The classical four-stage explicit Runge-Kutta method usesIt satisfies the fourth-order conditions for a Runge-Kutta method. Its polynomial stability function excludes A-stability, while $|R(iq){|}^2=1-q^6/72+q^8/576$ gives the imaginary-axis stability interval $|q|\le 2\sqrt{2}$.

For the two-dimensional heat equation with zero Dirichlet boundary conditions, the Crank-Nicolson diffusion scheme preserves the interval between the minimum and maximum of the initial nodal values and zero under the displayed restriction. The old-time coefficients form a convex combination, while the new-time matrix has positive diagonal, nonpositive off-diagonal entries and row diagonal-dominance margin one. A hypothetical new value above the old maximum makes the new-time row at least that value while its right side is at most the old maximum, a contradiction; apply the reversed inequality at a new minimum. In particular initial nonnegative or nonpositive values preserve their sign. The step restriction guarantees these value bounds even though scalar A-stability holds without it.

A Lobatto IIIA method collocates at the Lobatto quadrature nodes, including both endpoints of the time interval. Its three-stage version hasThe Butcher order conditions give order four. Its stability function iswhich is A-stable but not L-stable. It is not algebraically stable: the first diagonal entry of the defining matrix is $2b_1{a}_{11}-b_1^2=-1/36$. This distinguishes linear A-stability from nonlinear algebraic stability.

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.

Suppose an $s$-stage Runge-Kutta method has order $2s-1$, an invertible matrix $A$, and $b^T{A}^{-1}1=1$. Its stability function is $R(z)=1+z{b}^T(I-zA{)}^{-1}1$. The adjugate matrix formula gives a rational function with denominator degree $s$ and numerator degree at most $s$; its zero limit at infinity lowers the latter degree to at most $s-1$. The order of a numerical method gives $R(z)-e^z=O(z^{2s})$, identifying the $[s-1/s]$ Padé approximant. Uniqueness follows because the cross-multiplied difference of two candidates has degree at most $2s-1$ but a zero of order at least $2s$, so is identically zero. The A-stability of near-diagonal exponential Padé approximants then proves A-stability, and the zero limit proves L-stability. These conditions identify the stability function; they do not alone claim uniqueness of all entries of the Runge-Kutta method tableau.

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.

The original PDF has a sign defect in the lower-left stage coefficient. Put $d=c_2-c_1$. With the printed negative sign, the row sums and the relevant Butcher order conditions areThus the claimed universal second order is false. For example $c_1=0,c_2=1$ gives, on $y^{\prime }=y$, two stages equal to $y$ and the update $Y=(1+h)y$. This is the first-order Forward Euler method. For the literal tableau, order at least two holds exactly when $c_1=1/2$ or $c_2=0$, subject to distinct allowed nodes.

For completeness the literal tableau's A-stability can also be classified algebraically. DefineThe stability function obtained from $R(z)=1+z{b}^T(I-zA{)}^{-1}e$ isIf $D\ge 0$, the denominator has no zero in the closed left half-plane: its reciprocal roots are the stage-matrix eigenvalues, whose positive sum and nonnegative product give positive real parts for nonzero eigenvalues. On the imaginary axis,Consequently for the literal tableau with uniquely solvable stages throughout the left half-plane, the complete parameter criterion isThese explicit inequalities in $c_1,c_2$ are necessary by the small and large imaginary parameters, and sufficient by the maximum modulus principle, including the bound at infinity. For $D=0$ the last inequality forces $r=0$, leaving the stable linear-fractional case. For $D<0$ there is a negative real stage pole. If one defines stability solely through an analytically continued scalar stability function, the only additional possibilities areIndeed these are precisely the cases where the left pole cancels and $R(z)=[1+(1-q)z]/[1-qz]$ is an A-stable theta method. The original stage equations are nevertheless singular at $z=-1/(q-a)$, so they do not give uniquely determined stages there. This distinction prevents a canceled rational factor from concealing an ill-defined stage solve.

The natural intended repair is to replace just the lower-left coefficient by $+c_2^2/(2d)$. This makes the method the collocation Runge-Kutta method on the two nodes. To derive the repaired entries, takeIntegration gives the other three printed entries and the weights unchanged, with the positive lower-left entry. Since $L_1+L_2=1$ and $c_1{L}_1+c_2{L}_2=t$, it follows that $Ae=c$, $b^{T}e=1$ and $b^{T}c=1/2$. Hence the corrected family is always of order at least two.

For the corrected family let $a=(c_1+c_2)/2$, $D=c_1{c}_2/2$ and $r=(1-c_1)(1-c_2)/2$. Its stability function has the same displayed rational form, now with $q=1/2$. The denominator again has no left-half-plane zero, and on the imaginary axis the squared-modulus difference is $(D^2-r^2)y^4$. Because $D,r\ge 0$, the necessary and sufficient inequality is $D\ge r$, orFor sufficiency, $|R|\le 1$ on the imaginary axis and at infinity; apply the maximum modulus principle on growing left half-discs to get the same bound inside. If $D=0$, the condition leaves the endpoint trapezoidal rule and its linear denominator. If $c_1+c_2<1$, every nonzero imaginary argument gives $|R|>1$. This is the two-node collocation A-stability criterion, explicitly distinguished from the literal defective tableau.

Introduce one stage $k=f(t_n+h/2,Y)$ with $Y=y_n+hk/2$, and update $y_{n+1}=y_n+hk$. This is the implicit midpoint rule as a one-stage Runge-Kutta method, with Butcher tableauFor a smooth vector field, write $\Delta =y_{n+1}-y_n$. Expanding its stage equation giveswhich matches the exact Taylor expansion through degree two. The method therefore has order at least two. On the Dahlquist test equation $y^{\prime }=\lambda y$, its stability function isThe third coefficient differs from the exponential's $1/6$, so the order is exactly two.

There is no pole in $\mathrm{Re}z\le 0$, andThus $|R(z)|\le 1$ throughout the closed left half-plane:This conclusion is A-stability, not strong damping of arbitrarily stiff modes: $R(z)\to -1$ along the negative real axis.

Only $\alpha >0$ needs consideration, by the preceding zero-stability analysis. On the Dahlquist test equation, all roots of the amplification polynomialmust satisfy the unit-disk root condition if the method is A-stable. Evaluate it at $\zeta =-1$:Take a real negative $z<-4/\alpha$. Then $P_z(-1)<0$, whereas the leading coefficient $2+\alpha -z$ is positive and $P_z(\zeta )\to +\infty$ as $\zeta \to -\infty$. The intermediate value theorem gives a real root strictly below $-1$. Its numerical mode grows in modulus, contradicting absolute stability at this negative test parameter. ConsequentlyThis proof detects an unstable root directly; the second-order value alone would not exclude A-stability. Equivalently the limiting derivative polynomial has an exterior root $-\alpha -\sqrt{1+{\alpha }^2}$, explaining the instability for large negative $z$.

Applying the stage equations to $y^{\prime }=\lambda y$ gives the stability functionThe poles are $3\pm i\sqrt{3}$, both in the right half-plane. To determine the whole domain rather than only its boundary, multiply numerator and denominator by 12 and put $z=x+iy$. Direct expansion givesThus $|R(z)|\le 1$ exactly when $x\le 0$, with no pole in that set. ConsequentlyOn the imaginary axis $|R|=1$, and in the open left half-plane it is less than one. Its limit along the negative real axis is one, so A-stability here does not imply stiff decay or L-stability.

An ODE solver must distinguish the error made by one step started from exact data from the error accumulated along the computed trajectory. For an order-$p$ one-step map ${\Phi }_h$, define the exact-start defect $d_n=y(t_{n+1})-{\Phi }_{h_n}(t_n,y(t_n))=O(h_n^{p+1})$. If the step map is Lipschitz with factor $1+L{h}_n$, its global error obeysIteration, using $1+Lh\le e^{Lh}$, proves the variable-step global ODE error boundIt explains the difference between local defect order $p+1$ and global order $p$, and why local tolerance control alone does not certify a prescribed global error. Strong dynamical amplification can magnify many individually small defects.

A practical solver needs an inexpensive local error estimator. In step-doubling error estimation, compare one full step $Y_h$ with two half steps $Y_f$. Smoothness and propagation through the second half step give $Y_h=y_{\mathrm{exact}}+C{h}^{p+1}+O(h^{p+2})$ and $Y_f=y_{\mathrm{exact}}+C{h}^{p+1}/2^p+O(h^{p+2})$. ThereforeThe difference estimates the finer local correction with the correct denominator and sign; adding it cancels the leading error by Richardson extrapolation. The common starting value and the smooth error expansion are essential, and the extra evaluations make this estimator relatively expensive.

An embedded Runge-Kutta pair instead shares the stage computations and uses two output weight vectors. For orders $p$ and $p-1$, their difference is generally $O(h^p)$ and estimates the lower-order local defect, even when the higher-order output is accepted. Its controller exponent is therefore $1/p$, not $1/(p+1)$. For example the explicit Euler and Heun outputs share the first slope; their difference is $h(k_2-k_1)/2=O(h^2)$, while Heun's own defect is $O(h^3)$. Predictor-corrector differences can also estimate a defect when scaled by the appropriate leading error constants; an uncalibrated raw difference need not be the corrected method's error.

For a vector equation, choose positive component scalesThe absolute and relative error tolerances allow meaningful tests both near zero and for large components with different physical scales. The max-norm criterion $E\le 1$ controls every scaled estimated component. A root-mean-square criterion is another common choice but has a weaker individual-component implication.

If the estimate scales like $E\simeq C{h}^q$, an adaptive step-size controller useswith lower and upper bounds on the change factor. A rejected step leaves the old state and time unchanged and recomputes with a smaller step; an accepted step advances with the chosen output and adjusts the next step. A zero estimate receives capped finite growth rather than division by zero. The safety factor allows for variation in the error constant. Step doubling has $q=p+1$, whereas a $p/(p-1)$ embedded pair usually has $q=p$. If a solver instead controls defect per unit time, division by $h$ changes the scaling exponent and must be included in the controller design.

Using previous estimates can smooth the sequence of accepted steps. A proportional-integral controller can take $h_{n+1}/h_n=\eta E_n^{-a}{E}_{n-1}^b$ with $0<b<a$, appropriate scaling by the estimator order and bounded factors. It avoids overreacting to a single noisy estimate, but needs safeguards after rejected steps, changes of order and abrupt coefficient changes. Event locations and discontinuities require locating the event and restarting the error expansion; blindly applying a smooth-step estimator across a jump can be misleading.

For a multistep method, adaptive step sizes change the interpolation history and coefficients. Constant-step coefficients cannot simply be reused with arbitrary step ratios. Variable-step formulas, compatible starting/restarting procedures and bounded ratios preserve the needed stability; local error and sometimes order are selected together to balance evaluation cost against accuracy.

Stiffness imposes an additional requirement. On a rapidly decaying mode $y^{\prime }=-\kappa y$, explicit Euler requires $h\kappa \le 2$ for absolute stability. Once $y$ is small, a local absolute-tolerance test can propose a large step even though roundoff or a small perturbation would then be amplified. A stiff solver therefore also uses a suitable implicit A-stable or L-stable method and solves its algebraic equations accurately enough for the estimator to be meaningful. A-stability alone does not ensure stiff decay, as the Lobatto stability function in question 4 tends to one for large negative arguments.

Finally, over-tightening tolerance eventually encounters roundoff and algebraic-solve error rather than further truncation-error improvement. Inexact Newton or linear solves must have errors below the local budget; a tiny time step with an inaccurate stage solve does not deliver the formal order. Global error assessment can use controlled refinements, defect propagation or adjoint weighting for a chosen output. Sensible error and step-size control therefore combines asymptotic estimators, tolerance scaling, stability, event handling and implementation error, rather than treating the accepted local estimate as a complete guarantee about the trajectory.

For the linear test equation $f(y)=\lambda y$ put $z=h\lambda$. The second stage solves $(1-az)k_2=\lambda y[1+(1-a)z]$, and substitution into the update gives the stability functionA-stability requires no poles and $|R(z)|\le 1$ throughout the closed left half-plane. If $a\ne 1/2$, the quadratic numerator gives unbounded magnitude as $z\to -\infty$; when $a=0$ the denominator is constant and the same conclusion holds. Thus $a=1/2$ is necessary. At this value $R(z)=(1+z/2)/(1-z/2)$, whose only pole is at positive $z=2$. Moreoveron the left half-plane. Hence the method is A-stable exactly for $\boxed{a=1/2}$. Its limit at negative infinity is $-1$, so it is not L-stable.

For $|\alpha |>1$, an exterior polynomial root of $\rho$ persists by continuity for sufficiently small negative real $z$ in the stability polynomial $\rho (w)-z\sigma (w)$. Hence these parameters cannot be A-stable.

For $-1\le \alpha <1$, the principal polynomial root at $w=1,z=0$ is simple. Let $s(z)=\log w(z)$ denote its analytic logarithm near zero. Using the expansion in part (b), and ${\rho }^{\prime }(1)=2(1-\alpha )$, solve the polynomial root equation to obtainIndeed the residual at $s=z$ is $-(\alpha +5)z^4/12$, and the correction in $s$ cancels it by multiplication with $2(1-\alpha )$. Choose $z=-C{\epsilon }^4/2+i\epsilon$. This lies strictly in the left half-plane, butfor small positive $\epsilon$. Thus $|w(z)|=e^{\mathrm{Re}s(z)}>1$, proving linear instability within the A-stability domain. This is a direct principal-root obstruction to A-stability, rather than an appeal to an order-barrier theorem alone.

Finally, at $\alpha =1$, the full stability polynomial isIt retains a double unit polynomial root for every negative $z$, allowing growing parasitic solutions. ThereforeThe canceled Backward Euler method recurrence at $\alpha =1$ is A-stable, but its admissible solutions and starting relations differ from those of the original method.

A collocation Runge-Kutta method approximates an ordinary differential equation by a polynomial whose derivative agrees with the vector field at selected times. Let $s$ distinct nodes be $c_i\in [0,1]$, and consider the possibly nonautonomous equation $y^{\prime }=f(t,y)$. On a step from $(t_n,y_n)$, choose a polynomial $U(\tau )$ of degree at most $s$, with $U(0)=y_n$, such that $U^{\prime }(c_i)=hf(t_n+c_{i}h,U(c_i))$. Here $\tau =(t-t_n)/h$ is scaled time; the numerical endpoint is $y_{n+1}=U(1)$.

Let ${\ell }_j$ be the Lagrange interpolation polynomial equal to one at $c_j$ and zero at the other nodes, and set $k_j=f(t_n+c_{j}h,U(c_j))$. Interpolation of the polynomial derivative givesEvaluating at the nodes and endpoint derives the Runge-Kutta method coefficients:Thus collocation is a specific family of generally implicit RK methods, not a separate update mechanism. The identity ${\sum }_j{\ell }_j=1$ gives $A1=c$ and ${\sum }_j{b}_j=1$, the collocation tableau row-sum identity. For sufficiently small $h$, a vector field with Lipschitz constant $L$ gives a contraction of the stage map when $hL{\max }_i{\sum }_j|a_{ij}|<1$, on a suitable bounded neighborhood. The Banach fixed-point theorem then gives a unique nearby stage solution. Equivalently smooth stage equations have identity derivative in the stage variables at $h=0$, so the inverse function theorem gives a smooth nearby branch. Arbitrarily large-step solvability is a separate issue for an implicit Runge-Kutta method.

Order analysis has two levels: polynomial accuracy at stages and extra accuracy at the endpoint. Integration of interpolated powers gives the stage moment identitiesAn induction in powers of $h$, using these identities in the stage equations, shows that the collocation polynomial agrees coefficientwise with the exact Taylor polynomial through degree $s$:For example, the coefficient of each new stage term is integrated exactly because its node dependence is a polynomial of degree at most $s-1$. This proves stage order $s$ and bounded actual-time derivatives of the collocation polynomial up to degree $s$. Assuming the vector field is sufficiently smooth on a fixed compact solution neighborhood, its composition with this polynomial has uniformly bounded derivatives of all finite orders needed below.

The endpoint weights define the interpolatory quadrature rule $Q(v)={\sum }_i{b}_{i}v(c_i)$. Suppose it is exact through degree $q-1$, but not through degree $q$. Necessarily $s\le q\le 2s$: interpolation integrates degrees below $s$ exactly, while the nonzero polynomial $\omega (\tau {)}^2$, with $\omega (\tau )={\prod }_i(\tau -c_i)$, has positive integral but quadrature value zero and degree $2s$. Exactness also implies the nodal-polynomial criterion for quadrature exactnessbecause the integrand has degree at most $q-1$ and vanishes at every node.

Here is the endpoint-error argument underlying the collocation order theorem. Let $v(t)=U((t-t_n)/h)$ and $\delta (t)=v^{\prime }(t)-f(t,v(t))$ be its residual. It vanishes at the collocation times, and if $F_h(\tau )=f(t_n+h\tau ,U(\tau ))$, then $\delta ={\mathcal{I}}_s{F}_h-F_h$, where ${\mathcal{I}}_s$ is interpolation at the nodes. Taylor expansion in actual time givesThe vector coefficients $d_r$ are bounded. Each bracket has the factor $\omega (\tau )$, with quotient degree $r-s$. In particular the residual is $O(h^s)$ throughout the step.

Write $\varphi (t_{\ast },t,z)$ for the exact flow from time $t$ and state $z$ to $t_{\ast }=t_n+h$. Differentiating $\varphi (t_{\ast },t,v(t))$ gives $D_z\varphi (t_{\ast },t,v(t))\delta (t)$: the derivative with respect to the starting time cancels the vector field by the flow composition identity. Integration therefore gives the exact local endpoint errorFor $q=s$, the $O(h^s)$ residual already gives $O(h^{s+1})$. For $q>s$, Taylor-expand the smooth matrix weight as $\Psi (t_n+h\tau )={\sum }_{\ell =0}^{q-s-1}{h}^{\ell }{\Psi }_{\ell }{\tau }^{\ell }+O(h^{q-s})$. Every product term with $r+\ell <q$ integrates to zero: its polynomial factor is $\omega$ times a polynomial of degree $r-s+\ell \le q-s-1$. All remaining terms are $O(h^q)$ before the time integration, including both remainders. HenceThis is collocation endpoint superconvergence by quadrature orthogonality. For the global assertion, the stage contraction estimate gives a one-step Lipschitz bound $1+Ch$ on a fixed solution neighborhood. Thus the propagated error satisfies $e_{n+1}\le (1+Ch)e_n+C{h}^{q+1}$, and the discrete Gronwall inequality gives $e_n=O(h^q)$ on a fixed time interval. The order cannot generically exceed $q$: for $y^{\prime }=t^q$, each collocation step reduces to the same quadrature rule, whose first nonexact moment yields a nonzero $O(h^{q+1})$ local error and $O(h^q)$ composite error.

The usual node families illustrate the result. Gauss collocation methods use interior Gaussian nodes and have $q=2s$, the maximum possible order. Right-endpoint Radau nodes give the Radau IIA method of order $2s-1$. Including both endpoints with Lobatto quadrature gives the Lobatto IIIA method of order $2s-2$ for $s\ge 2$. One-stage Gaussian collocation is the second-order implicit midpoint rule, while collocation at the right endpoint is the first-order Backward Euler method. The two-stage Gaussian nodes $1/2\pm \sqrt{3}/6$ give $b=(1/2,1/2)$ anda fourth-order method. Node placement, rather than just stage count, controls the superconvergent endpoint order.

There is also a structural link with Question 2. For Gaussian nodes, let $L_i(\tau )={\int }_0^{\tau }{\ell }_i(v)dv$. The derivative of $L_i{L}_j$ has degree at most $2s-1$, so Gaussian quadrature is exact on it. The integral is $b_i{b}_j$, while evaluating at the nodes gives $b_i{a}_{ij}+b_j{a}_{ji}$. Thus Gaussian collocation satisfies $M=0$ and has Runge-Kutta conservation of quadratic invariants. For the scalar test equation, any RK method has stability function $R(z)=1+z{b}^T(I-zA{)}^{-1}1$. For implicit midpoint this is $(1+z/2)/(1-z/2)$; the identity $|1-z/2{|}^2-|1+z/2{|}^2=-2\mathrm{Re}z$ proves A-stability. High order, stage solvability, invariant preservation and damping are distinct design considerations, so no stability conclusion should be inferred from collocation order alone.

Consistency was established in part (a). By the Dahlquist equivalence theorem, convergence additionally requires the root condition for a multistep method. Since $\rho (w)=(w-1)(w-\alpha )$, its roots lie in the closed unit disk with each unit-modulus root simple exactly forThe endpoint $\alpha =-1$ is zero-stability although it has a simple parasitic root at minus one; $\alpha =1$ has a repeated root at one and is excluded.

For every parameter in this convergent range, the leading coefficient of $\sigma$ is $(5+\alpha )/12>0$, whileSince $\sigma (w)\to +\infty$ as $w\to -\infty$, it has a real root $w_{\ast }<-1$. Its other real root lies between minus one and one because $\sigma (1)=1-\alpha >0$, so the exterior root is simple.

On the Dahlquist test equation, the amplification polynomial of a multistep method is $P_z(w)=\rho (w)-z\sigma (w)$, with $z=h\lambda$. For $|z|\to \infty$, the equivalent polynomial $-P_z/z=\sigma -\rho /z$ tends coefficientwise to $\sigma$, and its leading coefficient stays nonzero. Choose a small closed disk about $w_{\ast }$ lying wholly outside the unit disk and containing no other root of $\sigma$. On its boundary $|\sigma |$ has a positive minimum, while $|\rho /z|$ is smaller for every sufficiently large $|z|$. Rouché's theorem then puts one root of $P_z$ inside this exterior disk for all such complex $z$.

That root violates the stability root condition for a multistep method. Hence there is a finite radius $R_{\alpha }$ 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 a Runge-Kutta method with real stage matrix $A=(a_{ij})$ and weights $b_i$, defineThe method has algebraic stability of a Runge-Kutta method ifThe matrix condition means $z^{T}Mz\ge 0$ for every real vector $z$. Its significance is nonlinear contractivity: an algebraically stable method, on well-defined stage solutions, is B-stable for a dissipative vector field satisfying $⟨f(t,y)-f(t,z),y-z⟩\le 0$. This is distinct from scalar A-stability, which concerns the linear test equation. The contractivity proof in part (b) explains the matrix criterion directly.

The Butcher contractivity theorem states that an algebraically stable Runge-Kutta method is B-stable: for a dissipative vector field and any positive step for which the stage problems are solved, its step does not increase the distance between two numerical solutions. The required condition on the dissipative vector field isfor all compared states at each common time. The inner product can be real Euclidean or complex Hermitian. The stage solvability of an implicit Runge-Kutta method is assumed in this comparison, not a conclusion from a distance estimate alone.

Let $d$ be the difference of starting values, $D_i$ the differences of corresponding stages and $F_i$ the differences of their vector-field values. ThenExpanding the squared norm of the update givesSubstitute $d=D_i-h{\sum }_j{a}_{ij}{F}_j$ in the linear term. Symmetrizing the double sum proves the Runge-Kutta contractivity identityEach inner product in the first sum is nonpositive by the defining inequality for a dissipative vector field, and its weight is nonnegative. The final quadratic form is nonnegative: resolve the vectors $F_i$ into components and apply positive semidefiniteness of $M$ to each component vector. Hence $\boxed{\Vert d_{+}\Vert \le \Vert d\Vert }$, which is exactly B-stability. No linearization of the vector field has been used.

For the Dahlquist test equation $y^{\prime }=\lambda y$ with $\mathrm{Re}\lambda \le 0$, this also bounds the amplification factor by one wherever the stages are well defined. With strictly positive weights, no stage pole can occur in the open left half-plane. Indeed, if $(I-zA)v=0$ for nonzero $v$, thenwhen $\mathrm{Re}z<0$, contradicting $M⪰0$. This proves the usual A-stability corollary for the scalar stability function; boundedness from the open half-plane makes any boundary pole in that rational function removable. Zero-weight redundant stages require their own solvability treatment. The nonlinear B-stability statement is stronger than A-stability, and the two notions should not be conflated.