Spectral radius of matrix from SOR method

Question

Suppose we write a matrix $A = L + D + U$ with lower triangular, diagonal and upper triangular parts. When trying to solve the equation $Ax=b$, we use a successive overrelaxation technique such that $x^{k+1}=\left(-\omega U+(1-\omega)D\right)(D+\omega L)^{-1}x^k + \omega (D+\omega L)^{-1}b$. Start with a guess for $x^0$ and eventually it will converge to the right $x$

It turns out that the spectral radius of $\left(-\omega U+(1-\omega)D\right)(D+\omega L)^{-1}$ is greater than or equal to $|\omega - 1|$.

Can someone help me prove this lower bound result for the spectral radius? I know the spectral radius is the largest eigenvalue but I'm not sure how to start getting the eigenvalues of the matrix I need.

Answer 1

For the definition of $L, U$ such that $A = D \color{red} - \color{\black} L \color{red} - \color{\black} U$ the scheme turns out to be

$$x^{k+1} = (D-\omega L)^{-1} \big(\omega U + (1-\omega)D \big) x^{k} + \omega (D-\omega L)^{-1}b$$ This can be reformulated into regular Matrix splitting form from which one obtains the iteration matrix $$G = I - (D/\omega - L)^{-1} A.$$ For the SOR method the matrix $B$ from the Wikipedia article is given by $B=D/\omega - L$ and the iteration / error propagation matrix by $G = I - B^{-1} A.$

Recall some basic properties for invertible matrices $A,B$:

1. $(AB)^{-1} = B^{-1} A^{-1}$
2. $AC = A I C = A B^{-1} B C$
3. $A = \big(A^{-1}\big)^{-1}$

Now come back to \begin{align} G &= I - (D/\omega - L)^{-1} A \\ &= I - (D/\omega - L)^{-1} IA \\ &= I - (D/\omega - L)^{-1} ( D/\omega) (D/\omega)^{-1} A \\ &= I - (D/\omega - L)^{-1} \Big(( D/\omega)^{-1}\big)^{-1} (D/\omega)^{-1} A \\ &= I - \big( \omega D^{-1} \big(D/\omega - L) \big)^{-1} \omega D^{-1} A \\ &= I - (I - w D^{-1}L)^{-1} \omega D^{-1} A \end{align} Recall $A = D - L - U$ to obtain \begin{align} G &= I - (I - w D^{-1}L)^{-1} \omega D^{-1} (D - L - U) \\ &=I - (I - w D^{-1}L)^{-1} \omega (I - D^{-1}L - D^{-1}U) \end{align} To shorten things, define $\hat L := D^{-1} L, \hat U := D^{-1} U$. Then: \begin{align} G &= I - (I - w \hat L)^{-1} \omega (I - \hat L - \hat U) \\ &= I - (I-\omega \hat L)^{-1} \Big[ -\omega \hat L + \omega(I - \hat U) \Big] \\ &= I + (I-\omega \hat L)^{-1} \omega \hat L - (I-\omega \hat L)^{-1} \omega(I - \hat U) \\ &= (I-\omega \hat L)^{-1} (I-\omega \hat L) + (I-\omega \hat L)^{-1} \omega \hat L + (I-\omega \hat L)^{-1} \omega(I - \hat U) \\ &=(I-\omega \hat L)^{-1} \big[ (I-\omega \hat L) + \omega \hat L \big] - (I-\omega \hat L)^{-1} \omega(I - \hat U) \\ &=(I-\omega \hat L)^{-1} I - (I-\omega \hat L)^{-1} \omega(I - \hat U) \\ &= (I-\omega \hat L)^{-1} \big((1-\omega)I + \hat U \big) \end{align} Now recall that $\det(AB) = \det(A) \det(B)$. Since $L, U$ are strictly lower/upper triagonal matrices, same holds for $\hat L, \hat U$. As a consequence, $\det \Big((I-\omega \hat L)^{-1} \Big) = 1 $ since triangular matrices preserve their structure under inversion (still triangular) and for triangular matrices, the determinant is equal to the product of the diagonal elements. Consequently, $\det \Big(\big((1-\omega)I + \hat U \big) \Big) = (1-\omega)^n$. Finally, you know that the determinant equals the product of the eigenvalues: $$ \prod_i \lambda_i = (1-\omega)^n \Rightarrow \bigg \vert \prod_i \lambda_i \bigg \vert = \bigg \vert(1-\omega)^n \bigg \vert \Rightarrow \prod_i \vert \lambda_i \vert = \vert1-\omega \vert^n $$ Thus, there has to be at least one eigenvalue with modulus $ \vert \lambda_i \vert \geq \vert 1 - \omega \vert$ (assume the opposite: If every eigenvalue would be smaller in absolute value, how would you reach the $\vert 1-\omega \vert^n$?) Thus, you see that for $\omega \notin (0,2)$ the spectral radius of the error propagation matrix is larger than $1$.