Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 57 (Numerical Solution of Differential Equations)

Let $A,b$ be the coefficients of the $\nu$-stage Runge-Kutta method. On the Dahlquist test equation $y^{\prime }=\lambda y$, its stability function isBoth polynomials have degree at most $\nu$, with denominator normalized to one at zero. Order $2\nu$ implies $R(z)-e^z=O(z^{2\nu +1})$. A rational function with these degree bounds and this accuracy is uniquely the diagonal Padé approximant $[\nu /\nu {]}_{e^z}$. To see uniqueness directly, if $P/Q$ and $\tilde{P}/\tilde{Q}$ have the required accuracy, then $P\tilde{Q}-\tilde{P}Q$ is a polynomial of degree at most $2\nu$ vanishing to order at least $2\nu +1$ at zero, hence identically zero.

The diagonal exponential Padé approximant can be writtenUse the permitted Padé property that the zeros of $P_{\nu }(-z)$ lie strictly in the right half-plane and numerator and denominator are coprime. Thus $R$ has no poles in the closed left half-plane. Its real coefficients give $P_{\nu }(-iy)=\overline{P_{\nu }(iy)}$, so $|R(iy)|=1$. Also $R(z)\to (-1{)}^{\nu }$ at infinity. Applying the maximum modulus principle on left half-disks and letting their radii increase proves $|R(z)|\le 1$ for $\mathrm{Re}z\le 0$. There are no hidden stage poles there either: the irreducible Padé denominator has degree $\nu$, exhausting the possible degree of $\det (I-zA)$, so the latter cannot contain an additional canceled factor. Every such maximal-order Runge-Kutta method is A-stable. This is maximal-order Runge-Kutta methods are A-stable; it does not assert L-stability, since the stability function does not tend to zero at infinity.

For admissible initial data, for example a square-integrable function on the interval, expand in the sine eigenfunctions of the Dirichlet Laplacian:The expansion follows either from separation of variables or the complete sine orthogonal basis. If $\kappa <{\pi }^2$, every growth rate is negative and Parseval's identity givesThus all finite-energy data decay. The convergence is also uniform in $x$ after any fixed positive time: apply Cauchy-Schwarz inequality to the sine series, using the summable factors $e^{-2(j^2-1){\pi }^{2}t}$, to bound its supremum by a constant times $e^{-({\pi }^2-\kappa )t}$ for $t\ge t_0>0$.

Conversely choose $u(x,0)=\sin \pi x$. Then $u(x,t)=e^{(\kappa -{\pi }^2)t}\sin \pi x$, which is stationary at equality and grows when $\kappa >{\pi }^2$. All initial conditions decay if and only if $\kappa <{\pi }^2$. This is the continuous part of the reaction-diffusion spectral decay threshold.

Write $h=\Delta x=1/(M+1)$. The semidiscrete matrix is $B=h^{-2}\mathrm{tridiag}(1,-2,1)+\kappa I$. For $j=1,\dots ,M$, set $v_m^{(j)}=\sin (j\pi m/(M+1))$. The endpoint values vanish and the sine addition formula givesThese form an orthogonal basis of eigenvectors. Every initial vector decays precisely when every eigenvalue is negative. Since the largest is ${\lambda }_1$, the necessary and sufficient condition isNecessity follows by taking the first eigenvector as the initial data; at equality it remains unchanged. Sufficiency follows by decomposing any vector into the displayed decaying modes. The discrete reaction-diffusion spectral decay threshold is below ${\pi }^2$, since $\sin x<x$ for $x>0$, and equals ${\pi }^2-{\pi }^4{h}^2/12+O(h^4)$ as the mesh is refined. Therefore a coarse semidiscretization can spuriously grow for some parameters for which the continuous equation still decays.

Insert a smooth exact solution, so $f(y(t))=y^{\prime }(t)$ and $g(y(t))=y^{\prime \prime }(t)$. Expand about $t_n$. The residual, left side minus right side, has the formal differential-operator symbolIts odd symmetry makes every even coefficient vanish. The coefficients of $z,z^3,z^5$ are respectivelyThe next coefficient is $1/4725\ne 0$, givingHence the local truncation error has exact defect order seven and the method has order six. The zero-step characteristic polynomial is ${\zeta }^2-1$, whose two unit roots are simple, so it is also zero-stable. With sufficiently accurate starting values and exact $g=f^{\prime }f$ evaluations, the usual accumulation of defects gives sixth-order global error. This is the symmetric sixth-order two-derivative method; approximate evaluations of $g$ must preserve the required accuracy if that order is to be retained.

Use the undirected graph of the symmetric off-diagonal sparsity pattern. Reading the original matrix gives the edgesThis connected nine-vertex, eight-edge graph is a tree. A leaf-removal perfect elimination ordering isThe corresponding lists of remaining neighbors are, in order, $\{1\},\{8\},\{7\},\{7\},\{5\},\{4\},\{1\},\{1\},\varnothing$. Thus simultaneous row and column permutation to this ordering allows Gaussian elimination without fill-in.

Here are the precise facts that justify the procedure. First, eliminating index $i$ makes the remaining entriesOnly pairs of remaining neighbors of $i$ can acquire a new nonzero entry. Consequently a vertex whose remaining neighbors form a clique can be eliminated without structural fill. Such a vertex is simplicial. An ordering in which each successive vertex is simplicial is a perfect elimination ordering. The graph characterization says that a graph admits such an ordering if and only if it is a chordal graph, meaning every cycle of length at least four has a chord. A tree has no cycles; more concretely, every nontrivial finite tree has a leaf, and removing a leaf leaves a forest. These statements explain why successive leaf removal works here without having to find a general-purpose chordal ordering.

Second, for a symmetric positive-definite matrix, every diagonal pivot and every successive Schur complement is positive definite. For example, if the first pivot is $a_{ii}$ and its coupling column is $b$, then for any nonzero remaining vector $x$,Thus no zero pivot requires abandoning the proposed ordering. Since each eliminated vertex here has at most one remaining neighbor, its Schur update changes only a diagonal entry. This proves the claimed fill-free LDL decomposition or Cholesky decomposition for every positive-definite matrix with the given pattern, including cases with additional accidental zeros. It is leaf elimination of a tree-pattern positive-definite matrix.

Let $S$ be the periodic forward-shift matrix, $(Su{)}_m=u_{m+1}$ with indices modulo $M$. The semidiscrete operator isFor ${\omega }_{\ell }=e^{2\pi i\ell /M}$, $\ell =0,\dots ,M-1$, the vector $v^{(\ell )}=(1,{\omega }_{\ell },\dots ,{\omega }_{\ell }^{M-1}{)}^T$ satisfies $S{v}^{(\ell )}={\omega }_{\ell }{v}^{(\ell )}$. These vectors divided by $\sqrt{M}$ form the unitary discrete Fourier transform basis. Hence the normal matrix $A$ has eigenvaluesEvery Fourier coefficient is multiplied by $e^{t{\lambda }_{\ell }/h}$ of modulus at most one. Parseval's identity therefore provesThe same estimate holds for differences of solutions and is uniform in the mesh. This is the required semidiscrete stability of a numerical method. The mean mode has eigenvalue zero and is conserved, consistently with periodic advection.

One can also verify the energy estimate without diagonalization. Since $S^{\ast }=S^{-1}$,The dissipative second-order forward advection semidiscretization thus damps nonconstant modes rather than amplifying them. This does not assert stability of an arbitrary further time-stepping method; its absolute stability region must contain the scaled eigenvalues. No nonnegativity condition on the periodic boundary value is needed: the printed trailing $t\ge 0$ specifies the time range.

Interpret the printed missing parenthesis as ending $f(y_{n+2})$ before the next summand. The characteristic polynomials of a linear multistep method are thenThey satisfy $\rho (1)=0$ and ${\rho }^{\prime }(1)=\sigma (1)=2(1-\alpha )$, so the consistency identities hold. The two nonprincipal roots are reciprocal. If $|\alpha |<1$, they are $\alpha \pm i\sqrt{1-{\alpha }^2}$, distinct unit roots also distinct from the principal root one. If $|\alpha |>1$, one reciprocal root lies outside the unit circle. At $\alpha =1$ the root one is triple, and at $\alpha =-1$ the root minus one is double. The root condition for a multistep method therefore holds exactly when $-1<\alpha <1$. The Dahlquist equivalence theorem, with standard smoothness and consistent starting data, givesTo determine order rather than guess it from the number of steps, the exponential-symbol order criterion for a multistep method givesThus the formal order is three for $\alpha \ne -5$, and four for $\alpha =-5$. At the exceptional value the $z^5$ coefficient is $1/10$. That fourth-order formula is not zero-stable. Every convergent member consequently has global order three. At $\alpha =1$ the third-order Taylor cancellation is only a formal defect property of a degenerate, nonconvergent recurrence.

Here is a direct A-stability test for the convergent parameters. For a nonprincipal unit root $r=\alpha +i\sqrt{1-{\alpha }^2}$, the simple root of the amplification polynomial of a multistep method satisfiesReduction using $r^2-2\alpha r+1=0$ givesFor small negative real $z$, it follows thatSo even a small negative real test parameter has an amplifying parasitic mode. None of the convergent parameters is A-stable. Parameters outside this range already fail the necessary zero-step root condition, so there is no real $\alpha$ giving an A-stable original method.

The endpoint $\alpha =1$ is worth keeping separate from a misleading cancellation: there $\rho =(\zeta -1{)}^3$ and $\sigma =\zeta (\zeta -1{)}^2$. The original amplification polynomial retains the double root one for every $z$, giving unbounded polynomial parasitic modes for general starting values. Canceling $(\zeta -1{)}^2$ would yield a different, reduced Backward Euler method; it does not stabilize the original recurrence. This is the common-factor cancellation defect in a multistep recurrence. The family is summarized by the reciprocal-root three-step multistep family.

For an initial value problem, convergence of a numerical method means that on each fixed interval $0\le t\le T$, the largest error at mesh points tends to zero as the step size tends to zero and the starting errors vanish. Order of a numerical method describes how rapidly an exact-start local defect decreases; stability of a numerical method controls propagation of that defect and of errors already present. These are related but different properties. A high-order expansion alone cannot ensure that accumulated error remains small.

For a one-step map $Y_{n+1}={\Phi }_h(t_n,Y_n)$, define the exact-start defect $d_{n+1}=y(t_{n+1})-{\Phi }_h(t_n,y(t_n))$. Order $p$ means $d_{n+1}=O(h^{p+1})$ for sufficiently smooth solutions. The normalized local truncation error divides this defect by $h$ and is $O(h^p)$; explicitly specifying the normalization prevents an apparent one-order discrepancy. Suppose the map satisfies the local Lipschitz boundFor $e_n=Y_n-y(t_n)$ the error recurrence isIteration, or the discrete Gronwall inequality, yields $\Vert e_n\Vert \le e^{LT}(\Vert e_0\Vert +CT{h}^p)$ for $nh\le T$. Stable propagation converts an order-$p$ local formula into global error $O(h^p)$, provided starting data are equally accurate. Consistency is the weaker requirement that the normalized local defect tend to zero.

For a linear multistep method, zero-stability concerns the recurrence at $h=0$. Its roots must have modulus at most one, and unit-modulus roots must be simple. Roots outside the circle amplify errors exponentially in the number of steps; repeated unit roots introduce polynomial growth. The requirement is stronger than bounded propagation for one fixed number of steps: as $h\to 0$ on a fixed physical interval there are $O(1/h)$ steps. Under the usual Lipschitz assumptions and consistent starting values, the Dahlquist equivalence theorem says consistency plus zero-stability is equivalent to convergence. Its sufficiency combines a bounded discrete recurrence propagator with the sum of local defects, while necessity follows by exciting an unstable homogeneous root or by observing the persistent error of an inconsistent formula.

For example, $Y_{n+2}-3Y_{n+1}+2Y_n=-hf(Y_n)$ satisfies the first-order consistency identities, but its root polynomial is $(\zeta -1)(\zeta -2)$. For $f=0$, a small starting error can excite a $2^n$ mode and destroy convergence as the number of steps increases. In contrast, simple parasitic unit roots such as the root minus one of a two-step centered method need not destroy zero-stability: they remain bounded, though they can create unwanted oscillations and affect practical behavior. Accurate starting procedures and suppression of accumulated parasitic error remain relevant.

Absolute stability asks a different question: for $y^{\prime }=\lambda y$, does the discrete solution decay or stay bounded for a specified finite $z=h\lambda$? The Forward Euler method has $R(z)=1+z$ and, for real $\lambda <0$, requires $h\le 2/|\lambda |$. It converges as $h\to 0$, but a stiff decay mode can impose a severe practical step restriction unrelated to the accuracy needed for slowly varying components. The Backward Euler method has $R(z)=1/(1-z)$, hence is A-stable and L-stable. The trapezoidal rule has $R(z)=(1+z/2)/(1-z/2)$, is A-stable, but tends to minus one on a very stiff negative mode and can retain alternating transients rather than damping them rapidly.

Zero-stability therefore does not imply unrestricted absolute stability; the three-step family analyzed earlier in this paper is a particularly strong illustration. Conversely a stable large step need not be accurate. This distinction matters for a stiff equation. The Second Dahlquist barrier limits A-stable linear multistep methods to order at most two, whereas implicit Runge-Kutta methods can have much higher order and still be A-stable. That barrier concerns the specified method class, not every numerical time integrator.

Finally, the mathematical order depends on smoothness: nonsmooth solutions or forcing can lower observed rates. Roundoff, imperfect implicit solves and inaccurate derivative evaluations introduce additional defects. Smaller steps increase the number of such perturbations; truncation error alone does not describe arbitrarily fine computation. The useful organizing principle is consistency supplies vanishing defects, stability bounds their accumulation, convergence follows, and order quantifies its rate under the stated regularity and starting-error assumptions.

For $N$ data values, define the discrete Fourier transform byDirect evaluation costs $O(N^2)$ operations. For even $N$, split the sum into even and odd indices. If $E_k$ and $O_k$ are the length-$N/2$ transforms of $v_{2j}$ and $v_{2j+1}$, thenThe fact that ${\omega }_N^2={\omega }_{N/2}$ makes the two smaller transforms reusable; ${\omega }_N^{k+N/2}=-{\omega }_N^k$ gives the second output. This is the FFT butterfly. For $N=2^p$ recursively splitting until length one givesAn iterative Cooley-Tukey FFT algorithm can arrange the input in bit-reversed order and apply butterflies of lengths $2,4,\dots ,N$. The factors ${\omega }_N^k$ are the twiddle factors. Each level uses $O(N)$ work, and in-place organization uses $O(N)$ storage. The inverse uses the conjugate roots with the final normalization $1/N$. Mixed-radix factorizations extend the same idea beyond powers of two. For a two-dimensional array, transforming rows and then columns implements the two-dimensional transform, again exploiting separability.

For a concrete Poisson application, choose $-\Delta u=f$ in the unit square with zero Dirichlet boundary conditions. Let $h=1/N$ and use interior indices $i,j=1,\dots ,N-1$. The five-point finite difference equation isThe product sine vectors diagonalize this matrix. Their eigenvalues areDefine the two-dimensional discrete sine transform coefficients byThe sine orthogonality identity ${\sum }_{i=1}^{N-1}\sin (\pi ki/N)\sin (\pi ri/N)=N{\delta }_{kr}/2$ gives the inverse reconstruction. The discrete sine transform Poisson solver is thereforeAll eigenvalues are positive, so there is no division by a zero mode for Dirichlet data. Nonzero prescribed boundary values are moved to the right side at neighboring interior points before transforming.

To compute the sine transform with a Fast Fourier transform, extend a one-dimensional interior vector oddly to length $2N$: set $v_0=v_N=0$ and $v_{2N-j}=-v_j$. Its length-$2N$ Fourier coefficient is $-2i{\sum }_{j=1}^{N-1}{v}_j\sin (\pi kj/N)$. Thus ordinary FFTs compute each sine transform. Apply this along all rows and columns, divide the coefficients, and apply inverse transforms. The total cost is $O(N^2\log N)$ operations and $O(N^2)$ storage for $O(N^2)$ unknowns. The method solves the finite-difference linear system directly to rounding accuracy; discretization error is separate and is second order for sufficiently smooth data and solution.

Boundary conditions determine the appropriate transform. Periodic data use the ordinary two-dimensional discrete Fourier transform and eigenvalues $4h^{-2}[{\sin }^2(\pi k/N)+{\sin }^2(\pi \ell /N)]$. The constant mode then requires zero-mean forcing, and the solution mean is fixed separately. Neumann conditions similarly use an appropriate discrete cosine transform, with a compatibility condition and an undetermined additive constant. A Fourier spectral discretization would use continuous spectral eigenvalues instead of the finite-difference eigenvalues above. The speed comes from a constant-coefficient separable operator on a regular rectangle; a general irregular domain or variable-coefficient equation is not diagonalized by this simple FFT construction.

Let $s_{\ast }$ be the unique sonic point, $f^{\prime }(s_{\ast })=0$. For a differentiable convex function, $f^{\prime }$ is nondecreasing, negative below $s_{\ast }$ and positive above it. Split the flux into the parts propagating right and left:Thus $f(u)=f(s_{\ast })+f^{+}(u)+f^{-}(u)$; explicitly, $f^{+}(u)=f(u)-f(s_{\ast })$ for $u>s_{\ast }$ and zero below, while $f^{-}(u)=f(u)-f(s_{\ast })$ for $u<s_{\ast }$ and zero above. The Engquist-Osher flux takes the right-going contribution from the left state and the left-going contribution from the right state:It is consistent, $F(u,u)=f(u)$. For a transonic rarefaction wave with $a\le s_{\ast }\le b$ it gives $f(s_{\ast })$; reversed transonic states give $f(a)+f(b)-f(s_{\ast })$. This is sonic-point splitting of a convex Engquist-Osher flux.

On cells of width $h$ let $U_j^n$ approximate the cell average and $\lambda =\Delta t/h$. The explicit Engquist-Osher method is the finite volume methodThe shared interface flux makes it conservative: sums telescope for periodic data, and the same applies on the infinite grid when boundary contributions vanish. To prove stability, choose an interval $[m,M]$ containing the initial states and impose the CFL conditionThe partial derivatives of the update areTherefore the update is a monotone conservative scheme. Because $H(q,q,q)=q$, componentwise comparison with the constant states $m,M$ proves $m\le U_j^{n+1}\le M$. Induction gives a mesh-independent maximum bound for every time level, and ensures the same CFL speed bound remains valid.

There is also a stronger L1 contraction of a monotone conservative scheme. Let $T$ denote one whole-grid update, and let $W=\min (U,V)$ and $Z=\max (U,V)$ componentwise. Monotonicity gives $TW\le TU,TV\le TZ$. Hence $|TU-TV|\le TZ-TW$ componentwise, and conservation yieldsThis applies to periodic grids or summable perturbations with vanishing end fluxes. Apply the same result to $U$ and its one-cell translate; translation commutes with $T$, soThus the method is a total variation diminishing scheme. Under the stated CFL condition it preserves the initial range, contracts differences in discrete $L^1$, and cannot increase total variation. These bounds give a precise nonlinear stability result, including across the sonic point.

Convexity alone does not remove the time-step restriction omitted in the question. For the Inviscid Burgers equation $f(u)=u^2/2$, linearize about a positive constant $U$. The update becomes $v_j^{n+1}=(1-\lambda U)v_j^n+\lambda U{v}_{j-1}^n$. Its alternating Fourier mode has multiplier $1-2\lambda U$, whose modulus exceeds one if $\lambda U>1$. Hence unrestricted explicit time steps are unstable even for a convex flux with one sonic point. This is CFL necessity for explicit Engquist-Osher stability.