Dahlquist equivalence for a consistent linear multistep method

Assume consistency and the root condition. Let $C$ be the companion matrix of $\rho \mathrm{/}{\alpha }_k$. By [F3], ${\sup }_{m\ge 0}\mathrm{\parallel }{C}^m{\mathrm{\parallel }}_{\mathrm{\infty }}\le M$. For a $d$-vector IVP, lift $C$ to the block companion $\mathcal{C}=C\otimes I_d$; its induced max row-sum norm is the same as that of $C$. Define $\mathrm{\parallel }U{\mathrm{\parallel }}_{\ast }:={\sup }_{m\ge 0}\mathrm{\parallel }{\mathcal{C}}^{m}U{\mathrm{\parallel }}_{\mathrm{\infty }}$. Then $\mathrm{\parallel }U{\mathrm{\parallel }}_{\mathrm{\infty }}\le \mathrm{\parallel }U{\mathrm{\parallel }}_{\ast }\le M\mathrm{\parallel }U{\mathrm{\parallel }}_{\mathrm{\infty }}$ and $\mathrm{\parallel }\mathcal{C}U{\mathrm{\parallel }}_{\ast }\le \mathrm{\parallel }U{\mathrm{\parallel }}_{\ast }$.

Apply one step to the exact history. For an implicit method, [A2] supplies its selected root in $K$; subtracting the exact residual and using [A1] bounds its displacement from $y(t_{n+k})$ by $\mathrm{\parallel }{\tau }_n{\mathrm{\parallel }}_{\mathrm{\infty }}\mathrm{/}(\mathrm{\mid }{\alpha }_k\mathrm{\mid }-h\mathrm{\mid }{\beta }_k\mathrm{\mid }L)$. The denominator is at least $\mathrm{\mid }{\alpha }_k\mathrm{\mid }\mathrm{/}2$ for small $h$. For an explicit method, ${\beta }_k=0$ and the unique output differs from $y(t_{n+k})$ by $-{\tau }_n\mathrm{/}{\alpha }_k$, without evaluating $f$ at that output. By [F1] and [F2], ${\tau }_n=O(h^{p+1})$ for order at least $p$ (take $p=1$ for consistency). In either case the output for the exact history has displacement $O(h^{p+1})$ and lies in $K$ for small $h$, since the compact exact trajectory lies in its interior.

If the root condition fails, choose a violating root $\lambda$ of $\rho$. For $\mathrm{\mid }\lambda \mathrm{\mid }>1$, the homogeneous sequence $u_n={\lambda }^n$ gives, on $h=T\mathrm{/}N$, starting perturbations $h^{1\mathrm{/}2}(u_0,\dots ,u_{k-1})$ that tend to zero, while the terminal complex magnitude is $h^{1\mathrm{/}2}\mathrm{\mid }\lambda {\mathrm{\mid }}^N\to \mathrm{\infty }$. For a repeated unit root of multiplicity $m\ge 2$, the homogeneous mode $u_n=n^{m-1}{\lambda }^n$ has bounded initial entries and terminal complex magnitude $N^{m-1}$; scaling its initial entries by $h^{1\mathrm{/}2}$ makes them tend to zero but gives terminal complex magnitude $h^{1\mathrm{/}2}{N}^{m-1}=T^{m-1}{h}^{1\mathrm{/}2-(m-1)}\to \mathrm{\infty }$. For a repeated root the claimed mode satisfies the recurrence because $(E-\lambda {)}^m(n^{m-1}{\lambda }^n)=0$, where $E{u}_n=u_{n+1}$: each application reduces the polynomial degree by one, and $\rho (E)$ has this factor. For each $N$, choose $v_n=\mathrm{Re}{u}_n$ if $\mathrm{\mid }\mathrm{Re}{u}_N\mathrm{\mid }\ge \mathrm{\mid }\mathrm{Im}{u}_N\mathrm{\mid }$, and otherwise choose $v_n=\mathrm{Im}{u}_n$. Both projections solve the real scalar recurrence, and the chosen one has $\mathrm{\mid }{v}_N\mathrm{\mid }\ge \mathrm{\mid }{u}_N\mathrm{\mid }\mathrm{/}\sqrt{2}$. Its first $k$ entries remain bounded uniformly in $N$. The real $d$-dimensional run $Y_n=h^{1\mathrm{/}2}(v_n,0,\dots ,0)$ therefore has starting errors tending to zero and terminal error diverging for the exact zero solution of $y^{\mathrm{\prime }}=0$, for every fixed $d\ge 1$. The projection may depend on $N$, as the definition of convergence permits an arbitrary sequence of starting values.

If $\rho (1)\mathrm{\ne }0$, apply the recurrence to $y^{\mathrm{\prime }}=0$, $y\equiv 1$, with exact starting values. At the first generated value $Y_k-1=-\rho (1)\mathrm{/}{\alpha }_k\mathrm{\ne }0$, so the maximum grid error does not tend to zero. Thus convergence requires $\rho (1)=0$.

Choose $\delta >0$ so that every max-norm ball of radius $\delta$ about the exact trajectory lies in $K$. For an explicit method put $B=\mathrm{\mid }{\alpha }_k{\mathrm{\mid }}^{-1}{\sum }_{j<k}\mathrm{\mid }{\alpha }_j\mathrm{\mid }$ and $D=\mathrm{\mid }{\alpha }_k{\mathrm{\mid }}^{-1}L{\sum }_{j<k}\mathrm{\mid }{\beta }_j\mathrm{\mid }$. If a history has error at most ${\eta }_0<\delta$, subtraction of its explicit formula from the formula for the exact history bounds the output difference by $(B+hD){\eta }_0$. Choose ${\eta }_0>0$ so that $(B+1){\eta }_0<\delta \mathrm{/}2$ and take $h$ small; step 1.2 then puts every such output in $K$. For an implicit method take ${\eta }_0\le \eta$ small enough that all history values lie in $K$; [A2] puts its selected outputs in $K$. Write the history as $U_n=(Y_n,\dots ,Y_{n+k-1}{)}^T$. Its update is $U_{n+1}=\mathcal{C}{U}_n+h{e}_k{R}_n(U_n,(U_{n+1}{)}_k)$, where $e_k$ inserts a vector in the last state slot and $R_n$ is the derivative sum divided by ${\alpha }_k$. For any two histories in this neighborhood, [A1], step 1.1 and the finite coefficients give $\mathrm{\parallel }{U}_{n+1}-V_{n+1}{\mathrm{\parallel }}_{\ast }\le \mathrm{\parallel }{U}_n-V_n{\mathrm{\parallel }}_{\ast }+h{K}_0(\mathrm{\parallel }{U}_n-V_n{\mathrm{\parallel }}_{\ast }+\mathrm{\parallel }{U}_{n+1}-V_{n+1}{\mathrm{\parallel }}_{\ast })$. For explicit methods the endpoint term is absent. Absorbing it when $h{K}_0\le 1\mathrm{/}2$ gives $\mathrm{\parallel }{U}_{n+1}-V_{n+1}{\mathrm{\parallel }}_{\ast }\le (1+Ch)\mathrm{\parallel }{U}_n-V_n{\mathrm{\parallel }}_{\ast }$.

Suppose $\rho (1)=0$ but ${\rho }^{\mathrm{\prime }}(1)\mathrm{\ne }\sigma (1)$. If the root condition already fails, step 1.3 applies; otherwise the root at $1$ is simple and ${\rho }^{\mathrm{\prime }}(1)\mathrm{\ne }0$. Put $\delta ={\rho }^{\mathrm{\prime }}(1)-\sigma (1)$ and test $y^{\mathrm{\prime }}=1$, $y(t)=t$, with exact starts. The numerical error satisfies ${\sum }_j{\alpha }_j{e}_{n+j}=-h\delta$. The sequence $p_n=-\delta nh\mathrm{/}{\rho }^{\mathrm{\prime }}(1)$ is a particular solution because ${\sum }_j{\alpha }_j=0$ and ${\sum }_{j}j{\alpha }_j={\rho }^{\mathrm{\prime }}(1)$. The difference $e_n-p_n$ is homogeneous and has starting size $O(h)$, so [F3] bounds it by $O(h)$ uniformly. At $n=N$, $p_N=-\delta T\mathrm{/}{\rho }^{\mathrm{\prime }}(1)\mathrm{\ne }0$, contradicting convergence. Hence ${\rho }^{\mathrm{\prime }}(1)=\sigma (1)$ is necessary.

The state vector after $n$ homogeneous steps is $C^n$ times the initial state. A uniform bound on these powers therefore gives the zero-stability estimate for every $T$ and $N$. Conversely, if the powers are unbounded, choose an exponent $n$ and unit initial state with arbitrarily large amplification, then take $T=1$ and $N\ge n+k-1$ so the entire amplified history lies on the grid; this contradicts the zero-stability bound. By [F3] and the companion construction in step 1.1, the powers are uniformly bounded exactly under the root condition.

Let $E_n=\mathrm{\parallel }{U}_n-U_n^{\ast }{\mathrm{\parallel }}_{\ast }$, where $U_n^{\ast }$ is the exact history state. As long as the preceding history remains within the radius ${\eta }_0$ of step 2.1, steps 2.1 and 1.2 give $E_{n+1}\le (1+Ch)E_n+C{h}^{p+1}$. Iterating through any first possible exit from that neighborhood yields $E_n\le e^{CT}(E_0+CT{h}^p)$, since $(1+Ch{)}^N\le e^{CT}$ and $Nh=T$. Starting errors tending to zero make the right side tend to zero; starters of order $p$ make it $O(h^p)$. Since $\mathrm{\parallel }{U}_n-U_n^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le E_n$, for sufficiently small $h$ these bounds are strictly below ${\eta }_0$, so a first exit is impossible. The updates therefore exist through $t_N$, and the same estimate gives the asserted convergence and order.

Steps 1.2, 2.1, and 3.1 prove sufficiency and its order-$p$ estimate; steps 1.3, 1.4, and 2.2 prove necessity of the root condition and both consistency identities. Together with [F1] and step 2.3, these are exactly consistency and zero-stability, which proves the Dahlquist equivalence.