Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 1 / 38C (Numerical Analysis)

Number the interior grid vertices in any order. The diagonal of $A$ is $10/3$, and off-diagonal weights are $-2/3$ for axial neighbors and $-1/6$ for diagonal neighbors. Each link weight is symmetric, so $A$ is symmetric. Extend the interior grid values by zero to the boundary. Since the eight stencil weights sum to $10/3$, grouping links giveswhere $w_{ij}=2/3$ or $1/6$ and each interior link is counted once. Every term is nonnegative. If the quadratic form vanishes, neighboring interior values agree, and every vertex linked to the boundary has value zero. The axial-link grid is connected and reaches the boundary, so all values are zero. Thus $\boxed{A\text{ is symmetric positive definite}}$. Reordering vertices replaces $A$ by $PA{P}^T$ for a permutation matrix $P$, preserving both properties.

For a linear system write $A=D+R$, where $D$ is the diagonal. The Jacobi method iteratesHere $D=(10/3)I$, and $B$ has nonnegative off-diagonal entries with row sums at most one. Rows adjacent to the boundary have sum strictly less than one; those at purely interior stencil vertices have sum one. Thus $\Vert B{\Vert }_{\infty }\le 1$.

To prove strict spectral radius below one, suppose $Bv=\zeta v$ with $|\zeta |=1$, and choose an index with $|v_i|=\Vert v{\Vert }_{\infty }>0$. Inequality forces that row sum to equal one and every linked neighbor to attain the same maximum modulus. Propagate this along the connected axial grid to a boundary-adjacent row, whose row sum is strictly less than one, a contradiction. All eigenvalues therefore have modulus strictly below one. Hence $B^k\to 0$ and the Jacobi errors tend to zero from every initial vector. The unique solution exists by positive definiteness, so $\boxed{\text{Jacobi converges for this discretization in any ordering}.}$