Past exam of the numerical analysis course of the University of Oxford / 2021 / 3

Use $x_n=nh$, $h=1/N$, and $y_n$ for the numerical approximation in the scalar initial value problem $y^{\prime }=f(x,y)$, $y(0)=y_0$, on $[0,1]$.

Here $y^{\prime }=x/(1+y^2)$ and $y(0)=1$. Since $x\ge 0$, the solution is nondecreasing, so $y(x)\ge 1$. In fact $0\le y^{\prime }\le 1/2$ on $[0,1]$, which also bounds the solution and ensures it extends across this entire interval. The smooth right-hand side makes $y$ twice continuously differentiable, with second derivativeFor $y\ge 1$ and $0\le x\le 1$,so $y^{\prime \prime }\ge 0$. The subtracted term in the first expression is nonnegative, giving the useful boundThe integral form of the Taylor remainder now givesTherefore the normalized local truncation error satisfies the stronger estimateThis proves the requested bound for $n=1,\dots ,N-1$, and also for $n=0$, which will be needed to start the global error estimate. For $N=1$ the stated range is empty, but the estimate at $n=0$ still applies.

For $0\le x\le 1$ and every real $z$,where $2|z|\le 1+z^2$ was used. The mean value theorem therefore proves Lipschitz continuity in $y$ with constant $1$.

Let $e_n=y(x_n)-y_n$. The explicit Euler method and the exact-solution identity from part (i) giveUsing the requested local truncation error bound $|{\tau }_n|\le h/2$, including at $n=0$, yieldsIteration and the finite geometric series giveSince $1+h\le e^h$ and $Nh=1$,Keeping the stronger bound $|{\tau }_n|\le h/4$ from part (i) improves the same proof to $(e-1)h/4$. The requested inequality follows already from the weaker bound.

For $f(x,y)=-x{y}^2$, the explicit Euler method evaluates the right-hand side at the known point $(x_n,y_n)$. ThereforeThis update requires no root finding.

The Backward Euler method uses the new point:Writing $a=h(x_n+h)>0$ gives the quadratic equation $a{y}_{n+1}^2+y_{n+1}-y_n=0$. Starting from $y_n>0$, its two polynomial roots have opposite signs. The positive root, which continues the solution as $h\to 0$, isThe other root is negative and does not approach $y_n$ as $h\to 0$. Rationalizing the numerator gives an equivalent form that avoids cancellation error when the step size is small:The defining quadratic equation gives $0<y_{n+1}<y_n$ for this root, so positivity is maintained inductively from $y_0=1$. The branch choice is part of specifying the Backward Euler method here: the algebraic update alone has two solutions.

With $f(x,y)=-x{y}^2-y^5$, write $t=x_{n+1}=x_n+h$ and $z=y_{n+1}$. The Backward Euler method requiresor the monic quintic polynomial equationConstruct its $5\times 5$ companion matrixIts characteristic polynomial is $\det (zI-C_n)=p(z)$. Thus the polynomial roots needed for this update are exactly the eigenvalues of $C_n$.

At each step, assemble $C_n$, compute its eigenvalues, for example with the QR algorithm, and choose its unique positive real eigenvalue as $y_{n+1}$. To justify this selection, letIf $y_n>0$, then $F(0)=-y_n<0$, $F(y_n)=h{y}_n^5+ht{y}_n^2>0$, andThe intermediate value theorem and strict monotonicity prove there is exactly one positive polynomial root, located in $(0,y_n)$. Starting at $y_0=1$ therefore makes every update well defined, positive and decreasing. In numerical arithmetic, select the nearly real eigenvalue in this interval and check the polynomial residual $|F(z)|$; a final Newton root-finding iteration can refine it. This reduces each update to the requested eigenvalue problem.

No. A necessary condition for consistency of a numerical method is reproduction of the constant solution $y(x)=1$ of the ordinary differential equation $y^{\prime }=0$. In a linear multistep method this givesBut the reverse triangle inequality gives, under the strict coefficient inequality,Thus the necessary order conditions for a linear multistep method already fail at order zero, regardless of the values of the ${\beta }_j$.

As appropriate for a genuine $k$-step linear multistep method, take ${\alpha }_k\ne 0$. Suppose the characteristic polynomial has a polynomial root $\xi$ with modulus $|\xi |>1$. From $\rho (\xi )=0$ and the triangle inequality,Dividing by the positive number $|{\alpha }_k||\xi {|}^{k-1}$ gives $|\xi |\le 1$, a contradiction. HenceThe nonzero leading coefficient matters: if ${\alpha }_k=0$, the assumed inequality forces all the ${\alpha }_j$ to vanish, so $\rho$ is the zero polynomial rather than a characteristic polynomial with $k$ roots. This degenerate case does not define the method in the question.

Yes: for $k=2$ the stated inequality guarantees zero-stability. Part (ii) puts every polynomial root in the closed unit disc. The remaining root condition for a multistep method is that every root on the unit circle has multiplicity of a root one.

If this failed for a quadratic polynomial, it would have a repeated root $\xi$ with $|\xi |=1$, andConsequently $|{\alpha }_1|=2|{\alpha }_2|$ and $|{\alpha }_0|=|{\alpha }_2|$, contradictingbecause ${\alpha }_2\ne 0$. Thus all roots on the unit circle are simple andThis conclusion does not assert consistency of a numerical method: part (i) rules out consistency of a numerical method whenever the coefficient inequality is strict. Zero-stability and consistency of a numerical method are separate requirements.