# Spectral radius for Jacobi and Gauss Seidel iterative methods

Let $L= \left[ \begin{matrix} 0 & \ldots & & & &0 \\ a & 0 & \ldots & & &0 \\ 0 & a & 0 & \ldots & &0\\ 0 & 0& a & 0 & \ldots & 0 \\ \vdots \end{matrix} \right]$

that is $L$ has its sub-diagonal equal to $a$, the other elements are zero.

Show that

$$\rho(L+L^T)^2 = \rho((\text{Id}+L)^{-1} L^T)$$

where $\rho(M)$ is the spectral radius of the matrix $M$.

I can only remember the following proof. So there might be an easier way.

Definiton 1: Let $A∈ℝ^{n×n}$ be a matrix with $$A=L+D+R,$$ with $D$ invertible. If the eigenvalues of the matrix $$J(α)=-D^{-1}\{αL+α^{-1}R\}, α∈ℂ\setminus\{0\}$$ are independent of $α$, then we call $A$ consistently ordered.

Theorem 1: Tri-diagonal matrices of the following form are consistently ordered. $$\begin{pmatrix} d_1 & a_{12} & \\ a_{21}& d_2 & \ddots \\ & \ddots & \ddots & a_{n-1,n} \\ & & a_{n-1,n} & d_n \end{pmatrix}$$ with $d_i\neq0$. Why? Let $T=\text{diag}(1, α, …, α^{n-1})$, then we can do a similarity transformation: $$-J(α) = αD^{-1}L+α^{-1}D^{-1}R = T(D^{-1}L+D^{-1}R)T^{-1}$$ And we know that eigenvalues are preserved under similarity transformation.

In your case it is $A=L+I+L^\top$, which is a tri-diagonal matrix. Hence your matrix is consistently ordered. And the two matrices where you want to know the spectral radii are simply the Jacobi-matrix $J=D^{-1}(L+R)$ and the Gauß-Seidel-matrix $H=-(D+L)^{-1}L^\top$ of that $A$.

Theorem 2: Let $A∈ℝ^{n×n}$ be a consistently ordered matrix. Then the eigenvalues $μ∈σ(J)$ and $λ∈σ(H_ω)$ fulfil: $$\sqrt{λ}ωμ = λ+ω-1.$$

Probably $ω∈(0,2)$, so that the SOR-method converges. I don't remember the proof. You should be able to find it somewhere in these lecture notes. (I was an exercise group leader to that lecture, that is why I remember this answer.)

The Gauß-Seidel-matrix is the special case of the SOR-matrix $H_ω$ with $ω=1$. Hence: $$ρ(H_1)=ρ(J)^2$$

• What do you mean by "the eigenvalues fulfil"? There is more than one eigenvalue for both matrices. – amsmath Oct 16 '17 at 15:38
• Also, in your definition (and in Theorem 1) you should add that $D$ is supposed to be invertible and $\alpha\neq 0$. – amsmath Oct 16 '17 at 15:44
• Thx for your comments. I corrected what you mentioned in the second comment. About the first one: Well both matrices have eigenvalues and for each eigenvalue $λ_i$ of $J$ there is an eigenvalue $µ_i$ of $H_ω$ which is related by that equation. – P. Siehr Oct 16 '17 at 16:15
• Ok. I think you should correct this, too, because it is very confusing without that explanation. And is it clear that $H_\omega$ has only non-negative real eigenvalues? – amsmath Oct 16 '17 at 16:23
• @amsmath - No, in general they are complex. – P. Siehr Oct 17 '17 at 8:36