Understanding linear systems

Objective:-

A=[5 1 2 ; -3 9 4; 1 2 -7]

X=[x1;x2;x3]

B=[10 -14 33]

Determine

• Eigen values of iteration matrix.
• Spectral radius of iteration matrix.
• Solve the system using Jacobi, Gauss-seidel and SOR methods
• Compute the iteration Matrix for the above mentioned iterative methods.
• Increase the Spectral radius to 1.1 by changing the diagonal terms suitably.

Formula for Jacobi ,Gauss & Successive over-Relaxation

Eigen value & Eigen vectors:-

• In linear algebra an eigenvector or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue is the factor by which the eigenvector is scaled.

• Geometrically an eigenvector, corresponding to a real nonzero eigenvalue, points in a direction in which it is streached by the transformation and the eigenvalue is the factor by which it is stretched. If the eigenvalue is negative, the direction is reversed. Loosely speaking, in a multidimensional vector space the eigenvector is not rotated. However, in a one-dimensional vector space, the concept of rotation is meaningless.

Eigenvectors (Example):-

Once the (exact) value of an eigenvalue is known, the corresponding eigenvectors can be found by finding nonzero solutions of the eigenvalue equation, that becomes a system of linear equation with known coefficients. For example, once it is known that 6 is an eigenvalue of the matrix

we can find its eigenvectors by solving the equation , that is

This matrix equation is equivalent to two linear equation

that is

Both equations reduce to the single linear equation . Therefore, any vector of the form , for any nonzero real number is an eigenvector of with eigenvalue .

The matrix above has another eigenvalue . A similar calculation shows that the corresponding eigenvectors are the nonzero solutions of , that is, any vector of the form , for any nonzero real number b.

Main Programe :-

clear all
close all
clc

% matrix decomposition 
L = [0 0 0;-3 0 0;1 2 0];
U = [0 1 2;0 0 4;0 0 0];
D = [5 0 0;0 9 0;0 0 -7];

% co-efficient matrix
A = L+U+D;

% Rhs 
B = [10;-14;33];

% changing the diagonal element 
E = linspace(0.5,2,10);
x = [0;0;0];
D_old = D;
omega = 0.9;

% solving using Iterative methods
 for i = 1 : length(E)
     D = E(i)*D_old;
     
     %jacobi
     %Iterative_Matrix
 
     T_jacobi = (inv(D))*(L+U);
     [jacobi_iter(i), jacobi_error, x] = LS_Jacobi(L,D,U,B);
     eigen_value_jacobi = eig(T_jacobi);
     jacobi_spectral(i) = max(abs(real(eigen_value_jacobi)));
     
     
     
     % Gauss seidal 
     T_gauss = (inv(D+L))*(U);
     [gauss_iter(i), gauss_error, x] = LS_Gauss(L,D,U,B);
     eigen_value_gauss = eig(T_gauss);
     gauss_spectral(i) = max(abs(real(eigen_value_gauss)));
     
     
     
     %Successive over Relaxation
     T_sor = ((inv(D+(omega*L)))*((omega-1)*D+(omega*U)));
     [sor_iter(i), sor_error, x] = LS_SOR(L,D,B,U,omega);
     eigen_value_sor = eig(T_sor);
     sor_spectral(i) = max(abs(real(eigen_value_sor)));
     
      
     
 end
 
 figure(1);
 subplot(2,1,1);
 plot(E, jacobi_spectral, 'b');
 xlabel('diagonal magnification');
 ylabel('spectral radius')
 title('jacobi iterative method ')
 legend('Diagonal magnification vs spectral radius');
 grid on
 hold on 
 subplot(2,1,2);
 plot(jacobi_spectral , jacobi_iter, 'b');
 loglog(jacobi_spectral,jacobi_iter,'r');
 xlabel('spectral radius');
 ylabel('no. of iterations');
 legend('Spectral radius vs no.of iterations','location','northwest');
 grid on
 
 figure(2);
 subplot(2,1,1);
 plot(E, gauss_spectral, 'b');
 xlabel('Diagonal Magnification');
 ylabel('Spectral Radius');
 title('Gauss Seidel Method');
 legend('Diagonal magnification vs spectral radius');
 hold on
 grid on
 subplot(2,1,2);
 plot(gauss_spectral, gauss_iter, 'b');
 loglog(gauss_spectral,gauss_iter,'r');
 xlabel('spectral radius');
 ylabel('no. of iterations');
 legend('Spectral radius vs no.of iterations','location','northwest');
 grid on 
 figure(3);
 subplot(2,1,1)
 plot(E, sor_spectral, 'b');
 xlabel('diagonal magnification');
 ylabel('spectral radius')
 title('SOR iterative method')
 legend('Diagonal magnification vs spectral radius');
 hold on
 grid on 
 subplot(2,1,2);
 plot(sor_spectral, sor_iter, 'b');
 loglog(sor_spectral,sor_iter,'r');
 xlabel('spectral radius');
 ylabel('no. of iterations');
 legend('Spectral radius vs no.of iterations','location','northwest');
 grid on 

Function Programe :-

Jacobi Iteration:-

% Function for jacobi Method

function [jacobi_iter, jacobi_error, x] = LS_Jacobi(L,D,U,B)

x = [0;0;0];
x_old = x;
jacobi_error = 9e9;
tol = 1e-04;
jacobi_iter = 1 ;

% iterative matrix
T_jacobi = (inv(D))*(L+U);

while (jacobi_error > tol)
    x = ((inv(D))*(L+U)*x_old)+(inv(D))*B;
    jacobi_error  = max(abs(x_old-x));
    x_old = x;
    
    jacobi_iter = jacobi_iter +1 ;
    
end

end

Gauss Iteration :-

% Function for Gauss Iteration 

function  [gauss_iter, gauss_error, x] = LS_Gauss(L,D,U,B)

x = [0;0;0];
x_old = x;
gauss_error = 9e9;
tol = 1e-04;
gauss_iter = 1;

% iterative matrix
T_gauss = (inv(D+L))*U;

while (gauss_error > tol )
    x = ((inv(D+L))*(U)*x_old)+(inv(D+L))*B;
    gauss_error = max(abs(x_old-x));
    x_old = x ;
    gauss_iter = gauss_iter + 1;
    
end 
end

Sucessive Over-Relaxation :-

%Function for Successive-Over Relaxation

function [sor_iter, sor_error, x] = LS_SOR(L,D,B,U,omega)

x = [0;0;0];
x_old = x;
sor_error = 9e9;
tol = 1e-04;
sor_iter = 1;
omega = 0.9;

% Iterative method
 T_sor = ((inv(D+(omega*L)))*((omega-1)*D+(omega*U)));

while (sor_error > tol)
    x =((inv(D+L*omega)*((omega-1)*D+(omega.*U))*x_old)+(inv(D+omega*L))*B);
    sor_error = max(abs(x_old-x));
    x_old = x;
    
    sor_iter = sor_iter + 1;
end
end

Explanation of the programe :-

• We have define the co-effficient matrix A and matrix B is on the right hand side of the equation like AX=B.
• Then us command of linspace for asign value and x value we have assign as (0;0;0);
• We have to define decompostion matrix L,D,U . L is lower triangle diagonal, D is diagonal matrix and U is upper triangle matrix.
• Then you have to define magnification factor . It will magnify the diagonal matrix D.
• We assume (x1;x2;x3)= 0 .it wil calculate the jacobi , Gauss, and successive over-Relaxation. we have to update x1 value in gauss seidal method and it will calculate the value value for x1,x2,x3. after we have to update gauss seidal value to successive over -relaxation method .
• now we define the for loop which runs from 1 to length of magnification factor inside the for loop calculated the spectral value of iteration matrix , the iteration matrix keeps on changing becuse it depends on diagonal matrix because of maginification factor in this way we get different spectral radius for each loop . herer we also calculating eigen value for iteration matrix.
• Then we have to create function loop for jacobi ,gauss seidal , successive over relaxation .
• After that we have to plot the graph using the plotting command .

Error faced on programe :-

No - Error

Result :-

Jacobi:-

Gauss Iteration :-

Successive Over-Relaxation

Conclusion :-

• The above graphs show the compaision of spectral radius vs number of iterations and spectrall radius vs magnification factor. The comparsion is made of three iterative techniques (jacobi,gauss,and successive over-relaxation).
• The spectral radius increase with nuber of iteration.so we can say that spectral radius is directley proportional to number of iteration.
• From the graph all the three method spectral radius from low point to increased to high .