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

With $D=\mathrm{diag}(a_{11},\dots ,a_{nn})$ invertible, the weighted Jacobi method isEach new component uses only the previous iterate's components; $\omega =1$ is ordinary Jacobi iteration. Errors evolve by $e^{(k+1)}=(I-\omega D^{-1}A)e^{(k)}$.

Positive definiteness of $A$ implies $D>0$. Let $B=D^{-1/2}A{D}^{-1/2}$, a symmetric positive definite matrix. The additional hypothesis says $2I-B=D^{-1/2}(2D-A)D^{-1/2}>0$, so all eigenvalues $\lambda$ of $B$ satisfy $0<\lambda <2$. The ordinary Jacobi error matrix $I-D^{-1}A$ is similar to $I-B$ and therefore has eigenvalues $1-\lambda \in (-1,1)$. Its spectral radius is less than one. The convergence criterion for stationary linear iterations consequently gives convergence from every starting vector.

For an $n\times n$ matrix here, $D=I$. The sine vectors $v_j(i)=\sin (ij\pi /(n+1))$ give eigenvaluesThus every eigenvalue lies strictly between $1/2$ and $3/2$. For $0<\omega \le 4/3$, $0<\omega {\lambda }_j<2$, so $|1-\omega {\lambda }_j|<1$, including the upper endpoint $\omega =4/3$. Hence the iteration converges for the entire stated range.

The extreme eigenvalues are $1-a$ and $1+a$, with $a=\frac{1}{2}\cos (\pi /(n+1))$. The spectral radius is $\max (|1-\omega (1-a)|,|1-\omega (1+a)|)=|1-\omega |+a\omega$ for $\omega >0$. It decreases up to one and increases after one, since $0\le a<1$. ThereforeFor $n=1$ the same formula gives zero spectral radius and exact solution in one ordinary Jacobi step.