Codex @codex  0

A collocation method chooses an approximate solution from a finite-dimensional trial space and forces the residual of a differential equation to vanish at selected nodes. Collocation Runge-Kutta methods apply this principle to polynomial approximations on each time step.

For $s$ distinct collocation nodes, let ${\pi }_s(t)={\prod }_{i=1}^s(t-c_i)$. If ${\int }_0^1{t}^j{\pi }_s(t)dt=0$ for $0\le j<k$, and the next moment is nonzero, the associated interpolatory quadrature has order $s+k$, and the collocation Runge-Kutta method has the same classical order for sufficiently smooth differential equations. Here $0\le k\le s$. Equivalently, if the quadrature is exact through degree $p-1$ but not degree $p$, the method has order $p$. The generic order is at least $s$, Gauss collocation methods reach $2s$, and Radau IIA methods reach $2s-1$.

For a collocation Runge-Kutta method, $a_{ij}={\int }_0^{c_i}{\ell }_j(t)dt$, where the Lagrange interpolation basis obeys ${\sum }_j{\ell }_j=1$. Hence each row sum is its collocation node. Failure of this identity disproves a claimed collocation tableau with those nodes. The identity alone is necessary rather than sufficient: the individual integrated basis coefficients must also agree.

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.

For one stage, first-order consistency of a numerical method gives $b_1=1$. The condition $b^T{A}^{-1}1=1$ then gives $a_{11}=1$. Hence the scheme is the Backward Euler method:It is a one-node collocation Runge-Kutta method with $c_1=1$. Specifically, choose a linear polynomial $p(t)$ on $[t_n,t_n+h]$ with $p(t_n)=y_n$ and impose $p^{\prime }(t_n+h)=f(t_n+h,p(t_n+h))$. Its derivative is constant, so $p(t_n+h)-p(t_n)=h{p}^{\prime }(t_n+h)$, exactly the Backward Euler method update.

The nodes are $c=(0,1/2,1{)}^T$. Their Lagrange interpolation basis on the normalized step isIntegrating these polynomials from zero to each node gives $a_{ij}={\int }_0^{c_i}{\ell }_j(s)ds$. At $c_1=0$ the row vanishes; at $c_2=1/2$ the integrals are $(5/24,1/3,-1/24)$; at $c_3=1$ they are $(1/6,2/3,1/6)$. The endpoint integrals also give $b=(1/6,2/3,1/6{)}^T$. These are exactly the coefficients in the original PDF.

Indeed, the degree-three polynomial $q$ determined by $q(0)=y_n$ and $q^{\prime }(hs)={\sum }_j{\ell }_j(s)f(q(h{c}_j))$ satisfies $q^{\prime }(h{c}_i)=f(q(h{c}_i))$. Integrating it to the nodes gives precisely the stage equations, and integrating to the endpoint gives the update. This proves it is a collocation Runge-Kutta method, specifically the three-stage Lobatto IIIA method.

For an explicit order proof, the collocation integrals imply $A1=c$, $Ac=c^2/2$ and $A{c}^2=c^3/3$, with powers componentwise. The endpoint weights are Simpson weights, so $b^T{c}^j=1/(j+1)$ for $j=0,1,2,3$. Therefore the eight Butcher order conditions through order four are satisfied:For example the last expression is $b^T{c}^3/6$, because $A^{2}c=A{c}^2/2=c^3/6$. These conditions are obtained by matching all elementary differential terms through degree four in the exact and numerical Taylor expansions, not just by testing a scalar linear equation. Nonautonomous equations are included by adjoining $t^{\prime }=1$.

To exclude higher order, the scalar stability function computed below satisfies $R(z)-e^z=-z^5/720+O(z^6)$. The local defect is therefore nonzero at degree five even on the scalar test equation. Hence $\boxed{\text{the classical order is exactly }4}$.

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.

For $y^{\prime }=f(t,y)$ and step $h$, a collocation Runge-Kutta method constructs a polynomial $P$ of degree at most $s$ on $[t_n,t_n+h]$ satisfyingThe step value is $y_{n+1}=P(t_n+h)$. Thus the differential equation holds exactly at the prescribed collocation nodes, while the initial value fixes the integration constant. For a smooth vector field and small enough $h$, the implicit stage equations have the local solution branch continuing the zero-step initial state; arbitrary large steps need not have a unique nonlinear solution.

A-stability removes the scalar linear decay restriction on the step size; it does not replace accuracy, nonlinear solvability or a suitable system norm. Its importance is clearest for a stiff differential equation, where rapidly decaying modes coexist with slowly varying quantities of interest. On the Dahlquist test equation $y^{\prime }=\lambda y$, the exact solution decays for $\mathrm{Re}\lambda <0$. A stable time integrator should not turn that decay into numerical growth.

For a one-step method write $y_{n+1}=R(z)y_n$, where $z=h\lambda$ and $R$ is its stability function. Its linear stability domain consists of parameters with $|R(z)|\le 1$ and a well-defined update. The method is A-stable when this domain contains the closed left half-plane. A consistent order-$p$ one-step method has $R(z)=e^z+O(z^{p+1})$ near zero, but that local agreement alone says nothing about stability at large negative $z$.

For a Runge-Kutta method with stage matrix $A$, weights $b$ and $1=(1,\dots ,1{)}^T$, eliminating the stages on the test equation givesAn explicit finite-stage method has a polynomial $R$. A nonconstant polynomial is unbounded along the negative real axis, so no consistent explicit Runge-Kutta method is A-stable. The explicit Euler method, with $R(z)=1+z$, is stable in the disk $|1+z|\le 1$ and on the negative real axis only for $-2\le z\le 0$. A stiff mode with a large negative eigenvalue therefore forces an unnecessarily small step even after its exact contribution has almost disappeared.

The Backward Euler method has $R(z)=1/(1-z)$. For $\mathrm{Re}z\le 0$, $|1-z{|}^2=1-2\mathrm{Re}z+|z{|}^2\ge 1$, so it is A-stable. The trapezoidal rule hasand is also A-stable. The implicit midpoint method has the same scalar stability function, although its nonlinear update differs from the trapezoidal rule. The first method has order one and the latter two order two. Their implicit solves trade greater work per step for freedom from the scalar stiff stability restriction.

Damping of very stiff modes separates A-stability from L-stability. For a one-step method, the latter additionally requires $R(z)\to 0$ as $z$ tends to infinity in the left half-plane. Backward Euler method satisfies this. The trapezoidal and midpoint rules instead have $R(z)\to -1$ along the negative real axis: a very stiff mode can alternate in sign with little damping even though its amplitude remains bounded. L-stability is often preferable for diffusion and rapid relaxation, while retaining oscillatory modes can be desirable in conservative dynamics.

For a linear multistep method, writeIts test-equation amplification roots satisfy $\rho (\zeta )-z\sigma (\zeta )=0$. Absolute stability requires every root to lie in the unit disk or on its boundary with all unit-modulus roots simple; all parasitic modes matter. At $z=0$ this is the zero-stability root condition. Consistency requires $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)$, and the Dahlquist equivalence theorem combines consistency and zero-stability to characterize convergence. Thus a claim of stability obtained by canceling a common factor is not a proof about the original recurrence and its arbitrary consistent starting data.

Explicit linear multistep methods cannot be A-stable either. If ${\beta }_k=0$ and ${\alpha }_k\ne 0$, some lower coefficient of $\rho -z\sigma$ becomes unbounded as $z\to -\infty$, while the leading coefficient stays fixed. If all roots remained in the unit disk, every coefficient-to-leading-coefficient ratio, an elementary symmetric function of those roots, would remain bounded. This contradiction forces an unstable root.

An important implicit example is BDF2 method, whose characteristic equation is $(3-2z){\zeta }^2-4\zeta +1=0$. A unit root $\zeta =e^{i\theta }$ givesThe leading coefficient vanishes only at $z=3/2$, outside the left half-plane. Near a small negative $z$, both roots are inside the disk; no unit-circle crossing can occur in the connected open left half-plane. On the imaginary axis the boundary equality can occur only at $z=0$, where the roots are $1,1/3$. Hence BDF2 is A-stable and its two roots tend to zero for very large negative $z$, giving strong stiff-mode damping. This is a complete boundary-locus argument, not just a boundary plot.

The Second Dahlquist barrier says that a convergent A-stable ordinary linear multistep method has order at most two. This theorem does not limit implicit Runge-Kutta methods or multiderivative multistep methods. In particular the A-stable third-order two-step multiderivative method in question 1 uses $y^{\prime \prime }$ and satisfies different order conditions. Among collocation Runge-Kutta methods, the standard family results give Gauss collocation methods order $2s$ with diagonal $[s/s]$ Padé approximants to $e^z$ as stability functions, and Radau IIA methods order $2s-1$ with subdiagonal $[s-1/s]$ approximants. Both families are A-stable; the Gauss functions have a nonzero limit at infinity, whereas Radau IIA is L-stable. The corrected two-stage right-Radau method, for example, haswhich matches the exponential through cubic order and tends to zero at infinity. Its poles $2\pm i\sqrt{2}$ lie in the right half-plane. For $z=-r+iy$, $r\ge 0$, direct subtraction givesproving its A-stability directly.

Sectorial A-alpha stability relaxes the requirement to a sector around the negative real axis, useful when the spectrum of a stiff problem remains in that sector; higher-order backward differentiation formulas illustrate the usefulness of this weaker requirement. For a normal linear system $y^{\prime }=Ly$, unitary diagonalization reduces the numerical update to its scalar factors $R(h{\lambda }_j)$. For a nonnormal system, a scalar eigenvalue test alone does not give a uniform bound in the chosen norm. Nonlinear stability is different again: B-stability asks for contractivity when $\mathrm{Re}⟨f(u)-f(v),u-v⟩\le 0$, and algebraic stability of a Runge-Kutta method is a standard sufficient criterion. Thus A-stability addresses a precise and valuable linear test, while step selection still has to meet accuracy requirements and the actual implicit equations must be solved on the relevant branch.

Let $p$ be the collocation polynomial of degree at most $s$ over one step, with $p(t_n)=y_n$, and let $Y_i=p(t_n+c_{i}h)$. Its derivative, of degree at most $s-1$, is fixed by its values at the distinct nodes. Lagrange interpolation therefore givesIntegrating from zero to $\tau$ yieldsAt $\tau =c_i$ this gives the stage equations of an implicit Runge-Kutta method; at $\tau =1$ it gives the update. ConsequentlyConversely, stages satisfying these equations define the integrated polynomial displayed above. It takes the stage values at the nodes and has the required derivative there, so it solves the collocation equations. This proves equivalence for every common solution branch, not merely equality on the scalar test equation. Also ${\sum }_j{a}_{ij}=c_i$, since the Lagrange polynomials sum to one. Stage existence or uniqueness requires the usual implicit-solvability assumptions; for a Lipschitz vector field a sufficiently small step gives a contraction. This is the collocation Runge-Kutta method construction.

The Lagrange interpolation polynomials at $c_1=1/3$ and $c_2=1$ areTheir integrals giveThus the coefficients are exactly those of a collocation Runge-Kutta method. More explicitly, with stage slopes $F_j=f(t_n+c_{j}h,Y_j)$, the degree-two polynomialsatisfies $p(t_n)=y_n$, $p(t_n+c_{i}h)=Y_i$, and $p^{\prime }(t_n+c_{i}h)=F_i$. These are the collocation Runge-Kutta method equations, and $y_{n+1}=p(t_n+h)$. For an implicit Runge-Kutta method, the nearby stages exist uniquely for sufficiently small $h$ under Lipschitz continuity; see stage solvability of an implicit Runge-Kutta method.

Write $e=(1,1{)}^T$, $c=Ae$, and interpret powers of $c$ componentwise. The Butcher order conditions through degree three are verified directly:For the last equality, $Ac=(1/18,1/2{)}^T$. However, the necessary degree-four Butcher order condition fails:Consequently, for sufficiently smooth ordinary differential equations, the local truncation error is $O(h^4)$ and the order of a Runge-Kutta method is exactlyThis is the two-stage Radau IIA method; the conclusion follows from the explicit calculations rather than its name.

The tableau is the three-stage Lobatto IIIA method. For its stage matrix $A$, weights $b$, nodes $c$ and $C=\mathrm{diag}(c)$, the Butcher order conditions through order four arewhere $c^{\circ j}$ means coordinatewise powers. Direct substitution verifies all eight identities. Equivalently, this is a collocation Runge-Kutta method at the three Lobatto quadrature nodes, whose weights integrate cubic polynomials exactly.

Order five would require $b^T{c}^{\circ 4}=1/5$, but here $b^T{c}^{\circ 4}=5/24$. Therefore the method has exactly order four.

For the nodes $c_1=\alpha$ and $c_2=1$, the Lagrange basis isDirect integration givesand thereforeThe collocation Runge-Kutta method also requiresThis exposes a sign error in the printed tableau: its lower-right entry is shown as $(-1+2\alpha )/[2(1-\alpha )]$. With $1-2\alpha$ in that position, the tableau is exactly the claimed collocation method. Taken literally, the printed weights satisfy $b^{T}1=\alpha /(1-\alpha )$, so the method is not even consistent unless $\alpha =1/2$ and cannot be a collocation method for general $\alpha$.

The Lagrange interpolation polynomial basis at $c_1,c_2$ isThe collocation Runge-Kutta method has stages and updatewhere $a_{ij}={\int }_0^{c_i}{\ell }_j(s)ds$ and $b_j={\int }_0^1{\ell }_j(s)ds$. Explicitly,

For distinct nodes $c_1,c_2\in [0,1]$, the two-stage collocation Runge-Kutta method has stability functionThe denominator has no zeros in the closed left half-plane. On the imaginary axis the denominator's squared modulus minus the numerator's is $(d^2-r^2)y^4$. Thus $d\ge r$, equivalently $c_1+c_2\ge 1$, is necessary and sufficient for A-stability, using the maximum modulus principle and the bound at infinity.