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

Integrate the ordinary differential equation across one step, using the fundamental theorem of calculus:The midpoint quadrature rule approximates the integral by $hf(x_n+h/2,y(x_n+h/2))$. Approximate the unknown midpoint state by the midpoint value of linear interpolation between the endpoint states:Combining these approximations gives the implicit midpoint ruleIt is an implicit time-stepping method because its new state occurs inside the evaluation of $f$. An equivalent derivation uses a straight-line approximation on the step and imposes the ordinary differential equation at its midpoint, a one-stage collocation method.

Work on a fixed finite interval $[a,a+T]$. Write $Y_n=y(x_n)$, $t=x_n+h/2$, and use the paper's normalized local truncation errorAssume $y$ has bounded continuous derivatives through order three on this interval, with $\Vert y^{\prime \prime }\Vert \le M_2$ and $\Vert y^{\prime \prime \prime }\Vert \le M_3$. Assume also that the Jacobian matrix $f_y$ has operator norm at most $L$ on the segments joining $y(t)$ to the endpoint averages. For a scalar equation this last hypothesis is simply $|\partial f/\partial y|\le L$ there.

Two symmetric estimates separate the errors. By Taylor's theorem applied to $y^{\prime }$ about $t$, the linear term integrates to zero on $[-h/2,h/2]$, givingLikewise the two linear terms in the endpoint expansions cancel, and their second-order remainders giveThe derivative bound on $f$ gives a Lipschitz condition in its second variable. Since $y^{\prime }(t)=f(t,y(t))$, the triangle inequality now yieldsThe constant is independent of $n$ and $h$ as long as the steps remain in the fixed interval. This implicit midpoint consistency bound proves numerical consistency of order two. The corresponding unnormalized residual is $h{\tau }_n=O(h^3)$; the two powers conventionally called local truncation error differ because the paper divides by the step size. If local error instead means the error of an exactly solved numerical step started at $Y_n$, the small-step Lipschitz condition gives the bound $h\Vert {\tau }_n\Vert /(1-hL/2)=O(h^3)$ as well.

Let $f$ be continuous in its first variable and uniformly Lipschitz continuous in its second variable, with constant $L\ge 0$. Retain the finite-interval smoothness assumptions and the bound $\Vert {\tau }_n\Vert \le K{h}^2$ from the preceding subpart. We first establish solvability of each implicit step. For a proposed starting state $u$, the maphas Lipschitz constant $hL/2$. If $hL/2<1$, the contraction mapping theorem on the complete state space gives a unique next state $v={\Psi }_{n,h}(u)$.

To compute a useful Lipschitz constant for the method, introduce its increment function byFor two starting states $u,w$,Rearranging gives the implicit midpoint Lipschitz estimateThus, for example, $hL\le 1$ gives an increment Lipschitz constant at most $2L$, uniformly as $h\to 0$.

For an explicit global error estimate, set $e_n=Y_n-y_n$. Subtract the numerical formula from the exact-value identity containing $h{\tau }_n$:The Lipschitz condition and the triangle inequality implyand thereforeIterating this inequality is the elementary discrete Gronwall inequality argument. For $L>0$, summing the geometric series and using $R_h-1=hL/(1-hL/2)$ givesFor $hL\le 1$, $R_h=1+hL/(1-hL/2)\le 1+2hL\le e^{2hL}$. If $nh\le T$, this provesWith the exact initial value, $e_0=0$, the global error is $O(h^2)$ and tends uniformly to zero on every such finite interval. If $L=0$, the recurrence instead gives $\Vert e_n\Vert \le \Vert e_0\Vert +KT{h}^2$, with the same conclusion. Starting values merely converging to the exact initial value also suffice for numerical convergence; second-order accuracy requires their errors to be $O(h^2)$. The result concerns exact implicit solves and convergence on fixed finite intervals, not uniform accuracy over an unbounded time interval.

Applying the implicit midpoint rule to the simple harmonic oscillator system givesFactor the change in the quadratic form $y^2+z^2$ and substitute these equations:Thus every step preserves the first integralFor completeness, the implicit equations are solvable for every real $h$: putting $s=h/2$, their coefficient matrix has determinant $1+s^2>0$ and the update isThis is an orthogonal matrix, as follows from $(1-s^2{)}^2+4s^2=(1+s^2{)}^2$. It therefore preserves the Euclidean norm, explaining geometrically the exact energy conservation. This is a concrete instance of Runge-Kutta conservation of quadratic invariants. Preservation of the circle does not assert that the numerical and exact solutions have the same phase at a fixed nonzero step size.