# SOR method converges for $\left( \begin{array}{ccc}2& -1\\-2 & 2\end{array} \right)$

Prove that the SOR method converges in $\mathbb{R}^n$ for the matrix $\left( \begin{array}{ccc}2& -1\\-2 & 2\end{array} \right)$ iff $\omega\in(0,2)$.

With the usual splitting of $A$ in the form $A=D+L+U$ to the diagonal, lower and upper triangular part, the iteration matrix of SOR is $$T=(D+\omega L)^{-1}[(1-\omega)D-\omega U].$$ Hence $$T = \begin{bmatrix} 1 - \omega & \frac{\omega}{2} \\ \omega(1-\omega) & 1 - \omega + \frac{\omega^2}{2} \end{bmatrix}.$$ The characteristic polynomial of $T$ is $$p(\lambda)=\lambda^2-\lambda\left(\frac{\omega^2}{2}-2\omega+2\right)+(\omega-1)^2.$$ I invite you to show that the roots $\lambda_+$ and $\lambda_-$ of $p$ satisfy $|\lambda_{\pm}|<1$ for $\omega\in(0,2)$.
• I can prove that if p(T)<1, we need $\omega\in(0,2)$,but I don't know how to prove the counter direction. – 89085731 Apr 19 '14 at 15:33
• Try expressing the eigenvalues of $T$ in terms of $\omega$. – Algebraic Pavel Apr 19 '14 at 15:39