Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 40E (Numerical Analysis)

A complex square matrix $A$ is a normal matrix if it commutes with its conjugate transpose:By unitary diagonalization of a normal matrix, there are a unitary matrix $U$ and a diagonal matrix $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_N)$ such thatThe matrix 2-norm is invariant under multiplication by unitary matrices, soFor a diagonal matrix,with equality on a coordinate vector belonging to an eigenvalue of greatest modulus. Hencethe matrix 2-norm of a normal matrix.

Let $D\in {\mathbb{R}}^{M\times M}$ be the Toeplitz antisymmetric tridiagonal matrix with $D_{m,m+1}=1$, $D_{m,m-1}=-1$, and zero diagonal. Fixed homogeneous endpoint values give the homogeneous updateThe hint gives the eigenvaluesBecause each $d_j$ is purely imaginary, $1-(\mu /4)d_j\ne 0$ for every real $\mu$, so the left matrix is invertible. The two matrices are polynomials in $D$ and therefore have the same orthonormal eigenvectors. The amplification matrixhas eigenvaluesThe numerator and denominator are complex conjugates, so $|q_j|=1$. Moreover, the common orthonormal eigenbasis makes $Q$ a normal matrix. By the matrix 2-norm of a normal matrix,for every $n$. Thus the Crank-Nicolson centered-advection scheme on a finite interval is unconditionally stable:

Insert the Fourier modeinto the leapfrog advection scheme. This givesand hence the amplification polynomialIts roots areIf $0<\mu <1$, the square root is real for every $\theta$, andIf $\mu >1$, choosing $|\sin \theta |>1/\mu$ makes the roots non-real multiples of $i$ with reciprocal moduli, one of which exceeds one, so the method is unstable.

The endpoint $\mu =1$ requires care. At $\theta =\pi /2$ the polynomial isso a generic mode has the form $(c_1+c_{2}n)i^n$ and grows linearly. It satisfies the weaker test $|{\zeta }_{\pm }|\le 1$ often quoted in elementary Fourier analysis, but it violates the root condition for a multistep method because the unit-modulus root is repeated. Therefore the rigorous uniform stability range for arbitrary two-level initial data isIf “stable” is being used only for the non-amplification condition on root moduli, the conventionally quoted range is $0<\mu \le 1$, with $\mu =1$ a defective marginal endpoint rather than a uniformly stable case.