Gauss-Seidel Method – How to Confirm System Solvability

convergence-divergencenumerical methodsproof-verificationsystems of equations

Given the system

$$\left(\begin{matrix}5&1&2\\-2&5&2\\-1&3&3\end{matrix}\right)\left(\begin{matrix}x_3\\x_1\\x_2\end{matrix}\right) = \left(\begin{matrix}0\\1\\0\end{matrix}\right)$$

I have to say something concerning the convergence of Gauss-Seidel Method.

My work: What I understand is that first of all I should look and see if it fits the convergence criteria for the method.

  1. The line criteria, i.e., the strictly or irreducibly diagonally dominant criteria for the matrix of coefficients is not true because that $3 < 1 + 3$.
  2. The symmetric positive-definite it is not true either because the coefficient matrix is not symmetric: e.g. $1\neq-2$.
  3. Also the Sassenfeld Criteria does not fit.

Could I say as an answer that the method could still converge even though these criteria doesn't hold? Does there exists other ways to prove that the method will converge? Most importantly:

Does there exists an iff statement like 'Gauss-Seidel will converge iff something is true' or at least can such a statement exist? Or could such a thing never exist?

Best Answer

Using the comments above - I'll answer my own question just for the question dont remain unanswered - and the paper given in the answer we have to use the theorem:

Let $G := - (D+L)^{-1}U$ such that $D$,$L$ and $U$ are the diagonal, lower and upper parts of the matrix $A$. Let $\sigma(G)$ be the spectrum of $G$, i.e., be such that $\sigma(G)$ is the set of eigenvalues of $G$ and define $$\rho(G):= \max_{\lambda \in \sigma(G)}\vert \lambda \vert$$Then the method converges iff $$\rho(G)<1$$

So, for this A we have

$$D + L = \pmatrix{5 & 0 & 0 \\ -2 & 5 & 0 \\-1 & 3 & 3}$$

and $$U = \pmatrix{0 & 1 & 2 \\ 0 & 0 & 2 \\0 &0 &0}$$

For that then we have that $$(D+L)^{-1} = \pmatrix{1/5 & 0 & 0\\ 2/25 & 1/5 & 0 \\-1/75 &-1/5 &1/3}$$

So

$$G = \pmatrix{0 & -1/5 & -2/5 \\ 0 & -2/25 & -14/25 \\0 &1/75 &32/75}$$

Now, finding the eigenvalues of $G$ we have to solve $\det(G - \lambda I)=0$

$$\lambda\left(-\lambda^2-\frac{26}{75}\lambda - \frac{50}{1875}\right)=0$$

The solutions are

$\lambda_0 = 0 $, $\lambda_{+}=\frac{26+2\sqrt{11\cdot29}}{150} \approx 0.41$, $\lambda_{-} =\frac{26-2\sqrt{11\cdot29}}{150} \approx -0.064 $.This way we get that $\rho(G) = 0.41 < 1$ so the method converges.

Related Question