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

Source paper: people.maths.ox.ac.uk/suli/MMSC_2020.pdf

This is the B1 paper for the MSc in mathematical modelling and scientific computing course of the University of Oxford. Questions 1–2 have original solutions below. The official revision page identifies public model solutions to questions 3–4, so those questions are skipped. The programme also advertises a student-only past-papers-and-solutions folder; its exact coverage of this paper has not been established.

Write the increment function of the one-step method as $\Phi (x,v,h)=f(x+\beta h,v+\beta hf(x,v))$. Its consistency error isAs $h\to 0$, the first term tends to $y^{\prime }(x_n)$ and the second tends to $f(x_n,y(x_n))=y^{\prime }(x_n)$ by continuity. Both limits are uniform along the exact-solution curve, a compact set: its small stage perturbations lie in a fixed compact neighborhood, so uniform continuity applies there. Thus ${\max }_{n<N}|T_n|\to 0$, proving consistency for every $\beta \in [0,1]$.

By the chain rule, $y^{\prime \prime }=f_x+f_{y}f$ along the exact solution. Applying Taylor's theorem to the exact increment and the two arguments of $f$ givesThe assumed differentiability makes the remainders uniform on $0\le x\le 1-h$. Subtracting gives the consistency errorHere $O$ denotes Big O notation. The general order of a numerical method is therefore one for $\beta \ne 1/2$ and at least two for $\beta =1/2$. For example, on $y^{\prime }=y$ with unit initial value, $y_N=(1+h+\beta h^2{)}^{1/h}$. Expanding its logarithm gives $y_N=e[1+(\beta -1/2)h+O(h^2)]$, so the first-order term is actually nonzero when $\beta \ne 1/2$.

To control accumulation, the mean value theorem and the bound on $f_y$ givePut $K_h=L(1+\beta hL)$, $q_h=1+h{K}_h$ and $e_n=y(x_n)-y_n$. The exact and numerical updates yield $|e_{n+1}|\le q_h|e_n|+h|T_n|$, with $e_0=0$. Iterating this recurrence, as in the Lipschitz one-step error bound, givesBecause $K_h\le L(1+L)$ for $h\le 1$, the prefactor is bounded independently of the mesh. When $\beta =1/2$, the consistency error is $O(h^2)$, hence the maximum global error is $O(h^2)$. This proves at least second-order numerical convergence of the explicit midpoint method.

For $f(x,y)=y$ and $\beta =1/2$, the explicit midpoint method multiplies the current value by $R=1+h+h^2/2$. Starting from one, induction givesLet $A=e^h$ and $B=R$. The Taylor theorem with Lagrange remainder for the exponential function givesThe difference of powers identity gives $A^n-B^n=(A-B){\sum }_{k=0}^{n-1}{A}^{n-1-k}{B}^k$. Every summand lies between one and $A^{n-1}$. Since $nh=x_n$, the global error therefore satisfiesThe same inequalities hold at $n=0$, where the error vanishes. At the fixed endpoint $x_N=1$, the lower bound $h^2/6$ prevents any higher order of a numerical method, while the upper bound is $e{h}^2/6$. Thus the convergence order is exactly two.

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.

New solutions are skipped: public model solutions to questions 3–4 are available.

New solutions are skipped: public model solutions to questions 3–4 are available.