Past exam of the numerical linear algebra and numerical solution of differential equations course of the University of Oxford / 2020 / 2

A constant-coefficient linear multistep method, normalized so that ${\alpha }_k=1$, has the formHere $Y_n$ approximates the solution $y(x_n)$ of the initial value problem, and $Y_0,\dots ,Y_{k-1}$ are starting approximations. The coefficients are independent of $n$ and $h$. If ${\beta }_k=0$, the update is explicit; otherwise it is an implicit time-stepping method, whose new value must satisfy the displayed equation.

Fix the following normalization of the local truncation error, also called the consistency error: insert a smooth exact solution into the linear multistep method and divide the residual by $h$,Thus the unscaled defect is $h{T}_n(h)$. Consistency of a numerical method means that $T_n(h)\to 0$ uniformly over mesh points in each fixed interval for every sufficiently smooth exact solution. Write the characteristic polynomials of a linear multistep method asBy Taylor's theorem, consistency of a numerical method is equivalent toor $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)$.

Second-order accuracy means $T_n(h)=O(h^2)$ for smooth solutions, equivalently an unscaled local truncation error $O(h^3)$. In addition to the two consistency conditions, its order conditions requireAn order of a numerical method of exactly two additionally requires that the next order condition fails. These statements concern the local defect; a second-order global error requires stability and suitably accurate starting values as well.

For a constant-coefficient linear multistep method, zero-stability means uniform boundedness of the propagation of starting perturbations as $h\to 0$. Equivalently, every solution of the homogeneous linear recurrencesatisfies $|v_n|\le K{\max }_{0\le j<k}|v_j|$ for all $n\ge 0$, with $K$ independent of $n$ and the starting values. The equivalent root condition for a multistep method is that every root of a polynomial $\zeta$ of the degree-$k$ polynomial $\rho$ satisfies $|\zeta |\le 1$, and every root on $|\zeta |=1$ is simple. Indeed, a root of multiplicity $m$ produces recurrence modes $n^q{\zeta }^n$, $0\le q<m$: repeated roots strictly inside the disk are harmless, whereas roots outside it or repeated roots on its boundary produce unbounded modes.

The coefficients of this linear multistep method are ${\alpha }_0=b$, ${\alpha }_1=-a$, ${\alpha }_2=1$ and ${\beta }_0={\beta }_1=0$, ${\beta }_2=c$. Substitution into the order of a numerical method conditions givesThe second equation gives $c=2-a$; substituting this into the third gives $-2+3a/2=0$. Consequently there is exactly one second-order choice,The resulting scheme is the BDF2 method,For a $C^4$ exact solution, Taylor's theorem in the original normalization gives the exact leading order defectIn particular the coefficient $-2/9$ is nonzero: the method has formal order exactly two, rather than three. Bounded third derivatives already suffice for the uniform estimate $T_n(h)=O(h^2)$; the stronger smoothness above only makes the displayed remainder immediate. Multiplying the recurrence by $3/2$ instead gives the common derivative normalization with leading defect $-h^2{y}^{\prime \prime \prime }(x_n)/3$.

The first of the characteristic polynomials of a linear multistep method isBoth roots are simple and lie in the closed unit disk, so the root condition for a multistep method proves zero-stability.

The Dahlquist equivalence theorem states that, for fixed-coefficient linear multistep methods on the usual class of initial value problems with a right-hand side continuous in $x$ and uniformly Lipschitz continuous in $y$, convergence of a numerical method for every such problem and every convergent set of starting values is equivalent to consistency of a numerical method and zero-stability. The statement is on fixed finite intervals where the exact solution exists, with implicit updates well defined. Its order estimate says that a zero-stable method with $T_n(h)=O(h^p)$ and starting errors $O(h^p)$ has global error $O(h^p)$ under the corresponding solution smoothness and Lipschitz continuity assumptions; merely convergent starting values do not ensure the order-$p$ rate.

For this application, sufficient assumptions are a unique solution $y\in C^3([x_0,x_0+T])$, a uniform Lipschitz continuity bound $L$ in $y$ on a neighborhood of its graph, and the nearby solution branch of each implicit update. For sufficiently small $h$, the mapis a contraction mapping with factor at most $2hL/3<1$ on a suitable small closed neighborhood. The Banach fixed-point theorem supplies local solvability of the nearby update. With starting errorsthe order estimate givesThus the BDF2 method is second-order convergent under these standard hypotheses. Exact $Y_0=y(x_0)$ together with one Euler method step for $Y_1$ already gives the required starting error when $y^{\prime \prime }$ is bounded, since only one starting step is taken.

The question's assumption of continuity of $f$ alone does not establish uniqueness, the needed solution smoothness, or this uniform convergence estimate. The added Lipschitz continuity condition is a sufficient hypothesis for the theorem used here; its failure does not imply that every particular initial value problem is nonunique or that its numerical approximations cannot converge.