Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 67 / 5

Assume $n\ge 3$ and use periodic indices for the Jacobi method. At iteration $r$, it isAll values on its right side belong to the old iterate. For lexicographic Gauss-Seidel iteration, compute in the order $1,\dots ,n$ and use a newly available coordinate immediately:The wrap-around term in the last row uses the new $x_1$, while the wrap-around term in the first row uses the old $x_n$. This is important for the actual iteration matrix and its convergence behavior.

The circulant matrix is singular, so the meaning of convergence needs care. If $C$ is the cyclic shift, $A=C+C^{-1}-2I$ has Fourier eigenvalues $-4{\sin }^2(\pi j/n)$. Its null space consists of constants. Therefore $Ax=b$ is solvable exactly when ${\sum }_j{b}_j=0$, and any solution is determined only up to a constant. Neither iteration can converge to a unique solution for arbitrary right-hand sides.

For a compatible $b$, fix one solution $x_{\ast }$ and examine the error. The iteration matrix of the Jacobi method is $(C+C^{-1})/2$, with eigenvalues $\cos (2\pi j/n)$. The constant mode has eigenvalue one. For odd $n$ all other eigenvalues have modulus less than one, so the iterates converge to $x_{\ast }+c1$, with the constant selected by the initial mean. For even $n$, the alternating vector has eigenvalue $-1$, producing an undamped oscillation. With $b=0$ and alternating initial vector this is an explicit nonconvergent example. For even $n$ convergence occurs only when that error component vanishes. When $\sum b_j\ne 0$, the mean instead drifts by $-(\sum b_j)/(2n)$ at each step, so Jacobi cannot converge.

For Gauss-Seidel iteration, put $K=-A=D+L+U$, so $K$ is positive semidefinite with diagonal two. The homogeneous error iteration is $e^{+}=Be$, $B=-(D+L{)}^{-1}U$. Updating a coordinate exactly minimizes $E(e)=e^{T}Ke/2$ in that coordinate; completing the square gives an energy decrement $|\Delta e_j{|}^2$. Summing within a sweep givesThe same identity holds for the Hermitian energy of complex vectors. If $Be=\lambda e$ and $e$ is nonconstant, its energy is positive, so $|\lambda |\le 1$. Equality forces every update to be zero, whence $Ke=0$ and $e$ is constant, a contradiction. Thus all nonconstant eigenmodes have modulus strictly below one.

The eigenvalue one has only the constant eigenspace. To exclude a generalized eigenvector at one, observe thatIf $(B-I)v=1$, multiplication by $w^T$ would give $0=n$. Hence the constant eigenvalue is algebraically simple, andFor compatible $b$, Gauss-Seidel therefore converges from every start to some solution, for either parity of $n$. Its limit differs from $x_{\ast }$ by $1w^T(x^{(0)}-x_{\ast })/n$. For an incompatible $b$, the affine update gives $w^T{x}^{(r+1)}-w^T{x}^{(r)}=-{\sum }_j{b}_j$, so the iterates again cannot converge.

Thus semiconvergence of cyclic Poisson iterations gives the precise answer:Both have spectral radius one on the unrestricted space, so neither meets the strict stationary-iteration criterion for a unique limit independent of the starting constant. A spectral radius of one alone is not a proof that Gauss-Seidel's compatible iterates fail to converge. A normalization or projection removing the constant mode makes this distinction explicit.