Successive Over-Relaxation (SoR) Method in MATLAB

Successive Over-Relaxation Method, also known as SOR method, is popular iterative method of linear algebra to solve linear system of equations. This method is the generalization of improvement on Gauss Seidel Method. Being extrapolated from Gauss Seidel Method, this method converges the solution faster than other iterative methods.

In this tutorial, we’re going to write a program for Successive Over-Relaxation – SoR method in MATLAB, and go through its mathematical derivation and theoretical background.

Derivation of SOR Method:

Consider the following sets of liner equations:

a₁₁x₁ + a₁₂x₂  + a₁₃x₃  + a₁₄x₄  . . .  . . . . . . . ..  . . . + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂  + a₂₃x₃  + a₂₄x₄  . . .  . . . . . . . ..  . . . + a_2nx_n = b₂

a₃₁x₁ + a₃₂x₂  + a₃₃x₃  + a₃₄x₄  . . .  . . . . . . . ..  . . . + a_3nx_n = b₃

. .  . . . . .  . . . . . .  . . . . . . . .  . . . . . . . .  . . . . . . . . . . . . . . . . . . .

. .  . . . . .  . . . . . .  . . . . . . . .  . . . . . . . .  . . . . . . . . . . . . . . . . . . .

a_n1x₁ + a_n2x₂  + a_n3x₃  + a_n4x₄  . . .  . . . . . . . ..  . . . + a_nnx_n = b_n

Express these equations in the form:  Ax = b

where,

Now, decompose matrix A into Diagonal component matrix D, Lower triangular matrix L, and upper triangular matrix U, such that:

A = D + L + U

where,

Rewrite the system linear equation as:

( D + ωL ) x = ωb – [ ωU + ( ω – 1 ) D ] x

Where, ω is the relaxation factor and ω > 1

During the iteration process, the left hand side of the equation is solved by using the previous value for x on right hand side.

The iteration equation is expressed analytically as:

x^(k+1) = ( D + ωL ) ^-1 (ωb – [ωU  + (ω – 1 ) D ] x ^(k) ) = L_ω ^(k) + c

Where, x^(k) is the k^th approximation for x and x(k+1) is (k+1)^th approximation for x.

Taking the advantage of triangular matrix form of ( D +  ωL), the (k+1)^th can be evaluated sequentially by using forward substitution. The expression obtained for x^(k+1) is:

SOR Method in MATLAB Code:

%for SOR method
function x = SOR( A ,B )
disp ( ' Enter system of equations in the form of AX=B')
% Calling matrix A
A = input ( ' Enter matrix A :   \n')
% check for matrix A
% it should be a square matrix
[na , ma ] = size (A);
if na ~= ma
    disp('ERROR:matrix A should be a square matrix')
    return
end
% calling matrix B
B = input ( ' Enter matrix B :   ')
% check for matrix B
[nb , mb ] = size (B);
if nb ~= na || mb~=1
   disp( 'ERROR:input error..pls re-enter data')
   return
end

w=input('Enter the relaxation parameter   ');
% A = D + L + U
D = diag(diag(A));
L = tril(A)- D;
U = triu(A)- D;

% check for convergence of system
e= max(eig(inv( D+w*L) * ( D*(1-w) - w*U)));

if abs(e) >= 1
    disp ('Since the modulus of largest eigen value of iterative matrix is not less than 1') 
    disp ('This process is not convergent. Please try some other process.')
    return
end

% initial guess for X..?
% default guess is [ 1 1 .... 1]'
r = input ( 'Any initial guess for X? (y/n):   ','s');
switch r 
    case 'y'
        % asking for initial guess
    X0 = input('pls enter initial guess for X :\n')
        % check for intial guess
    [nx, mx] = size(X0);
    if nx ~= na || mx ~= 1
        disp( 'ERROR: pls check input')
        return
    end
    otherwise
    X0 = ones(na,1);
end

%allowed error in final answer
t = input ( 'enter the error allowed in final ans:  ');
tol = t*ones(na,1);
k= 1;

X( : , 1 ) = X0;
err= 1000000000*rand(na,1); %intial error assumtion for looping
while sum(abs(err) >= tol) ~= zeros(na,1)
    X ( : ,k+ 1 ) = inv(D+w*L) * ( D*(1-w) - w*U)*X( : ,k) + inv(D+ w*L)*B;% SOR formula
    err = X( :,k+1) - X( :, k);% finding error
    k = k + 1;
    
end

fprintf (' The final ans obtaibed after %d itaration which is  \n', k)
X( : ,k)

The above code for Successive Over-Relaxation method in Matlab for solving linear system of equation is a three input program. Here, matrix A, matrix B, and relaxation parameter ω are the input to the program. The user defined function in the program proceeds with input arguments A and B and gives output X.

When the program is executed in MATLAB workspace, it asks for the value of coefficient matrix A and checks if it is square matrix or not. After getting valid input for A, another input matrix B is required to be entered to the program which must be a column matrix. Finally, the relaxation parameter is given as input and solution of linear equation comes as output.

While giving input to the program, the standard MATLAB syntaxes must be obeyed. Here’s a sample output of the MATLAB program for SOR method:

In this output of the Matlab program, 2x + y – z = 8, -3x – y + 2z = -11, and -2x + y +2z = -3 have been tried to be solved. But, the largest Eigen value of iterative matrix is not less than 1. As a result of which, the problem here is not suitable for SOR method.