Abnormal behavior algorithm implemented in matlab depending of the input

Question

I'm doing a homework assignment for scientific computing, specifically the iterative methods Gauss-Seidel and SOR in matlab, the problem is that for a matrix gives me unexpected results (the solution does not converge) and for another matrix converges.

Heres the code of sor, where:

• A: Matrix of the system A * x = b
• Xini: array of initial iteration
• b: array independent of the system A * x = b
• maxiter: Maximum Iterations
• tol: Tolerance;
• In particular, the SOR method, will receive a sixth parameter called w which corresponds to the relaxation parameter.

Here´s the code for sor method:

 function [x2,iter] = sor(A,xIni, b, maxIter, tol,w)            
     x1 = xIni;
     x2 = x1;
     iter = 0;
     i = 0;
     j = 0;
     n = size(A, 1);

     for iter = 1:maxIter,
         for i = 1:n
             a = w / A(i,i);
             x = 0;
             for j = 1:i-1
                 x = x + (A(i,j) * x2(j));
             end
             for j = i+1:n
                 x = x + (A(i,j) * x1(j));
             end
             x2(i) = (a * (b(i) - x)) + ((1 - w) * x1(i)); 
         end
         x1 = x2;
         if (norm(b - A * x2) < tol);
             break;
         end
     end

Here´s the code for Gauss-seidel method:

function [x, iter] = Gauss(A, xIni, b, maxIter, tol)

x = xIni;
xnew = x;
iter = 0;
i = 0;
j = 0;
n = size(A,1);

for iter = 1:maxIter,
    for i = 1:n
        a = 1 / A(i,i);
        x1 = 0;
        x2 = 0;
        for j = 1:i-1
            x1 = x1 + (A(i,j) * xnew(j));
        end
        for j = i+1:n
            x2 = x2 + (A(i,j) * x(j));
        end
        xnew(i) = a * (b(i) - x1 - x2);
    end
    x= xnew;
    if ((norm(A*xnew-b)) <= tol);
        break;
    end
end

For this input:

A = [1 2 -2; 1 1 1; 2 2 1];
b = [1; 2; 5];

when call the function Gauss-Seidel or sor :

[x, iter] = gauss(A, [0; 0; 0], b, 1000, eps)
[x, iter] = sor(A, [0; 0; 0], b, 1000, eps, 1.5)

the output for gauss is:

x =

  1.0e+304 *

    1.6024
   -1.6030
    0.0011


 iter =

            1000

and for sor is:

x =

   NaN
   NaN
   NaN


iter =

        1000

however for the following system is able to find the solution:

A = [    4 -1  0 -1  0  0;
        -1  4 -1  0 -1  0;
         0 -1  4  0  0 -1;
        -1  0  0  4 -1  0;
         0 -1  0 -1  4 -1;
         0  0 -1  0 -1  4   ]
b = [1 0 0 0 0 0]'

Solution:

[x, iter] = sor(A, [0; 0; 0], b, 1000, eps, 1.5)
x =

    0.2948
    0.0932
    0.0282
    0.0861
    0.0497
    0.0195


iter =

    52

The behavior of the methods depends on the conditioning of both matrices? because I noticed that the second matrix is better conditioned than the first. Any suggestions?

Answer 1

From the wiki article on Gauss-Seidel:

convergence is only guaranteed if the matrix is either diagonally dominant, or symmetric and positive definite

Since SOR is similar to Gauss-Seidel, I expect the same conditions to hold for SOR, but you might want to look that one up.

Your first matrix is definitely not diagonally dominant or symmetric. Your second matrix however, is symmetric and positive definite (because all(A==A.') and all(eig(A)>0)).

If you use Matlab's default method (A\b) as the "real" solution, and you plot the norm of the difference between each iteration and the "real" solution, then you get the two graphs below. It is obvious the first matrix is not ever going to converge, while the second matrix already produces acceptable results after a few iterations.

Always get to know the limitations of your algorithms before applying them in the wild :)