2

Prove that for the system \begin{cases} ax+by=p\\ cx+dy=q \end{cases} a necessary and sufficient condition of convergence for the Jacobi and Gauss-Seidel iterative methods is $|bc|<|ad|$.

I have tried to prove it using that the iterative method converges if and only if its espectral radius is $\rho<1$ without succeeding, however I am pretty sure I should use that

Chappers
  • 67,606
John Keeper
  • 1,281
  • 3
    Can you write down the relevant iteration matrices? Since everything is 2x2 you can calculate the spectral radius of such a matrix by hand. – Ian Jun 13 '18 at 16:33
  • 1
    @Ian I tried to calculate the eigenvalues and I have $\lambda_1=\frac{1}{2}(\sqrt{a^2-2ad+4bc+d^2}+a+d)$ and $\lambda_2=\frac{1}{2}(-\sqrt{a^2-2ad+4bc+d^2}+a+d)$. I don't know how can I get to $|bc|<|ad|$ from here. – John Keeper Jun 13 '18 at 16:53
  • 2
    The Jacobi iteration matrix is $\begin{bmatrix} a & 0 \ 0 & d \end{bmatrix}^{-1} \begin{bmatrix} 0 & b \ c & 0 \end{bmatrix}$ while the Gauss-Seidel iteration matrix is $\begin{bmatrix} a & 0 \ c & d \end{bmatrix}^{-1} \begin{bmatrix} 0 & b \ 0 & 0 \end{bmatrix}$. You need to compute the eigenvalues of each of these. You computed the eigenvalues of the system matrix, which do not really matter very much. – Ian Jun 13 '18 at 17:08
  • 1
    I intuitively see why the iteration matrix are these, and calculating the eigenvector for these matrix I get that $ab/cd$ must be $<1$. Where can I find a proof that the iteration matrices are like that? – John Keeper Jun 13 '18 at 17:27
  • 2
    It is the definition of the Jacobi and Gauss-Seidel methods. Jacobi writes $A=D+R$ where $D$ is diagonal and $R$ has zero diagonal entries to get $Ax=b$ equivalent to $(D+R)x=b$ equivalent to $x=D^{-1}(b-Rx)$. Gauss-Seidel writes $A=L+U$ where $L$ is lower triangular and $U$ is strictly upper triangular to get $Ax=b$ equivalent to $(L+U)x=b$ equivalent to $x=L^{-1}(b-Ux)$. So technically the iteration matrices are actually $-D^{-1}R$ and $-L^{-1}U$ but the minus sign doesn't change the spectral radius. – Ian Jun 13 '18 at 17:33

0 Answers0