numerical methods
Can you please give me criteria for convergence of these 2 iterative methods(Gauss–Seidel and Jacobi methods)?
What is necessary and sufficient condition and what just a sufficient from these 3?
1.The standard convergence condition (for any iterative method) is when the spectral radius of the iteration matrix is less than 1.
2.The method is guaranteed to converge if the matrix A is strictly or irreducibly diagonally dominant.
3.Norm of the iteration matrix is less than 1.
With the spectral radius, you are on the right track.
Let us write down what we have:
$$ A = \left( \begin{array}{ccc} &1 & 2 & 3 \\ &2 & -1 & 2 \\ &3 & 1 & -2 \end{array} \right)$$ and (less importantly) $$b = \left( \begin{array}{c} 5 \\ 1 \\ -1 \end{array} \right).$$
So how do we formulate Gauss-Seidel? Note that there are different formulation, but I will do my analysis based on this link, page 1. Let $ A = L+D+U$ be its decomposition in lower, diagonal and upper matrix. Then Gauss-Seidel works as follows: \begin{align} (D+L)x^{k+1}&= -Ux^k+b \\ \Leftrightarrow x^{k+1} &= Gx^k+\tilde{b} \end{align} with $$ G = -(D+L)^{-1} U.$$ Note that you don't actually calculate it that way (never the inverse)! Let $x$ be the solution of the system $Ax=b$, then we have an error $e^k=x^k-x$ from which it follows (see reference above) that $$ e^{k+1} = Ge^k$$ Thus Gauss-Seidel converges ($e^k\rightarrow 0$ when $k\rightarrow \infty$) iff $\rho(G)<1$. When you have calculated $\rho(G)$ and it is greater than 1, Gauss-Seidel will not converge (Matlab also gives me $\rho(G)>1$).
With the Jacobi method it is basically the same, except you have $A=D+(A-D)$ and your method is $$ Dx^{k+1} = -(A-D)x^k+b, $$ from which we obtain $$ x^{k+1} = Gx^k+\tilde{b}, $$ with $$ G = -D^{-1} (A-D).$$ As before, we have $e^{k+1} = Ge^k$. We again have $\rho(G)>1$. Therefore, both methods diverge in the given case. In the following I have done a simple implementation of the code in Matlab.
function iterative_method
A=[ 1 2 3
2 -1 2
3 1 -2];
b=[ 5 1 -1]';
L=[ 0 0 0
2 0 0
3 1 0];
U=[ 0 2 3
0 0 2
0 0 0];
D=[ 1 0 0
0 -1 0
0 0 -2];
x0 = rand(3,1); % random start vector
x = A\b; % "exact" solution
% Gauss Seidel
figure(1)
semilogy(1,abs(x0-x),'xr')
hold on
xi =x0;
for i=2:100
xi = (D+L)\((-U*xi)+b);
semilogy(i,abs(xi-x),'xr')
end
% Jacobi
hold off
figure(2)
semilogy(1,abs(x0-x),'ob')
hold on
xi =x0;
for i=2:100
xi = D\(-(A-D)*xi+b);
semilogy(i,abs(xi-x),'ob')
end
end
This shows, that both methods diverge as expected (first one is Gauss-Seidel, second one is Jacobi, both log-scaled).
As we see from $ e^{k+1} = G e^k = G^k e^0$, we have exponential growth in our error. For comparison, I added two more plots, which are identically to the two plots above, except they also contain values of the function $y(\text{iteration number})=\rho(G)^\text{iteration number}$, added in green. We can see, that they match the calculated error.
Bonus
Even though this was no longer asked, I would like to say something about successive over-relaxation (SOR). This method is a modification of the Gauss-Seidel method from above. But here we introduce a relaxation factor $\omega>1$. And rewrite our method as follows: $$ (D+\omega ) x^{k+1} = -(\omega U + (\omega-1)D)x^k+\omega b$$ Normally one wants to increase the convergence speed by choosing a value for $\omega$. It basically means, that you stretch the step you take in each iteration, assuming your going in the right direction. But in our case we can make use of something similar, called under-relaxation. Here we take small steps by choosing $\omega<1$. I have done some calculations, playing with different values for $\omega$. The plot below shows the error of $x^{100}-x$ for different values of $\omega$ on the x-axis, once for $0.01<\omega<2$ and in the second plot for $0.01<\omega<0.5$. We can see, that for a value of $\omega\approx 0.38$ we get optimal convergence. Even though this might be a little more than you asked for, I still hope it might interest you to see, that small modifications in your algorithm can yield different results.
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.
Best Answer
Obviously all these three conditions are not necessary, as both iteration methods can be used to solve the matrix equation $A0=0$ regardless of $A$ (as long as the iteration matrices exist).
Apparently, you copied the first two conditions from the Wikipedia entries on Gauss-Seidal method and Jacobi method. If you read the two articles careful enough, you should know that both conditions 1 and 2 are sufficient conditions for convergence. As to condition 3, the answer depends on the norm. If the matrix norm in question is a consistent norm (which is true for virtually all matrix norms we encounter in practice) and the iteration matrix is $E$, then by the spectral radius formula, $\rho(E)\le\|E^k\|^{1/k}$ for any $k\in\mathbb{N}$. In particular, $\rho(E)\le\|E\|$. Since $\|E\|<1$, we conclude that the spectral radius $\rho(E)$ is also smaller than $1$ and hence both iteration methods converge.