Past exam of the numerical solution of differential equations course of the University of Oxford / 2010 / A (Numerical Solution of Differential Equations I)

Substitute a smooth exact solution into the linear multistep method and expand about $x_n$. Its residual isConsistency of a numerical method requires the coefficients of $y$ and $h{y}^{\prime }$ to vanish. Therefore $1+a+b=0$ and $3+a=1$, giving the unique choiceFor this choice the next coefficient is $9/2-1-2=3/2\ne 0$, so the residual is $\frac{3}{2}{h}^2{y}^{\prime \prime }+O(h^3)$. The normalized local truncation error, obtained by dividing the residual by $h$, is $O(h)$. Hence the method has order one.

A zero-stable has a uniformly bounded response to small perturbations of its starting values and accumulated residuals on a fixed time interval as $h\to 0$. Equivalently, its first characteristic polynomial satisfies the root condition for a multistep method: every root has modulus at most one, and each root on the unit circle is simple.

For the consistent parameters, the recurrence for $y^{\prime }=0$ is $y_{n+3}-2y_{n+1}+y_n=0$, with characteristic polynomialLet $r=(-1-\sqrt{5})/2$. Choose $y_1=r$ and $y_2=r^2$; together with $y_0=1$ these generate exactly $y_n=r^n$. Since $|r|=(1+\sqrt{5})/2>3/2$,This parasitic mode violates the root condition and grows without a bound independent of the number of steps. Scaling its starting amplitudes gives the same unbounded amplification for arbitrarily small initial perturbations. Thus the only consistent method in the family is not zero-stable.

A method has numerical convergence if it approximates the exact solution uniformly at mesh points on every fixed finite interval as $h\to 0$, whenever its starting approximations converge to the corresponding exact starting values, for sufficiently smooth solutions of a well-posed initial-value problem.

The Dahlquist equivalence theorem states that a fixed-coefficient linear multistep method is convergent if and only if it is consistent and zero-stable, under the usual Lipschitz condition on the differential equation and convergent starting data. In this family numerical consistency forces the parameters found in part (a), and part (b) proves that choice is not zero-stable. All other parameter choices are inconsistent. Therefore no member of the family is convergent.

With $d=\Delta x$, define the semidiscrete Fourier transform byFor finite-support sequences, expand the squared modulus and use orthogonality:ConsequentlyFor a general square-summable sequence, truncate it to $|j|\le N$. The identity makes the transformed truncations Cauchy in $L^2$, and completeness defines the transform as their $L^2$ limit. Passing to the limit proves the Parseval identityThe infinite series need not converge absolutely pointwise; the $L^2$ interpretation is sufficient for the stability analysis.

Transforming the spatial shifts and putting $\xi =k\Delta x$ gives the real amplification factorFor $0\le \theta \le 1$ the denominator is at least one, so the implicit step is a bounded Fourier multiplier on ${\ell }^2$. Set $v={\sin }^2(\xi /2)\in [0,1]$ and use ${\sin }^2\xi =4v(1-v)$. The numerator is no greater than the denominator, so $G\le 1$. The other inequality isIf $\theta \ge 1/2$, the bracket is nonpositive and this always holds. If $0\le \theta <1/2$, the concave quadratic has its maximum at $v=(1-2\theta )/[2(1-\theta )]$, with value $(1-2\theta {)}^2/[4(1-\theta )]$. Therefore $|G|\le 1$ precisely under the stated conditionand without a mesh-ratio restriction when $1/2\le \theta \le 1$. The Parseval identity now givesIteration proves stability with constant one. It is conditional for $\theta <1/2$ and unconditional for $\theta \ge 1/2$. The sampled initial data have finite support, hence belong to ${\ell }^2$. This is the Fourier stability threshold for a mixed-width heat scheme.

On nonnegative states the characteristic speed is $f^{\prime }(u)=1+p{u}^{p-1}>0$, so upwind finite difference scheme uses the left spatial difference. With $\lambda =\Delta t/\Delta x$, the conservative upwind finite difference scheme isExplicitly the flux difference is $(U_j^m-U_{j-1}^m)+[(U_j^m{)}^p-(U_{j-1}^m{)}^p]$. Preservation of nonnegativity under the given Courant restriction, proved next, justifies the same left-upwind direction at every step.

Write $M_0={\sup }_x{u}_0(x)<\infty$ and assume $\lambda (1+p{M}_0^{p-1})\le 1$. Suprema are understood where the printed maxima on the infinite domain are not attained. We prove the invariant interval $0\le U_j^m\le M_0$ simultaneously with the stated speed bound.

Suppose the interval property holds at time $m$. By the mean value theorem, the divided differenceis between $1$ and $1+p{M}_0^{p-1}$; when the two states coincide define it as $f^{\prime }(U_j^m)$. The update is the convex combinationBoth coefficients are nonnegative and sum to one, so the same interval property holds at time $m+1$. It is true initially and hence for all times by induction. ThereforeThe propagated nonnegativity is essential; it keeps the flux increasing on the entire range of the numerical solution.

The convex-combination formula proved in part (i) gives $0\le U_j^{m+1}\le {\sup }_{\ell }{U}_{\ell }^m$ for every $j$. Taking the supremum and using nonnegativity givesThis is the discrete maximum principle for the nonlinear upwind step and proves the requested conditional ${\ell }^{\infty }$ stability under the propagated Courant–Friedrichs–Lewy condition.