Spectral radius

OBJECTIVE-

• To determine Eigen values of iteration matrix.
• To determine Spectral radius of iteration matrix.
• To 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.

The given system of equation is,

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

X=[x1;x2;x3]

B=[10 -14 33]

The eigen values for a given matrix can be determined by the below procedure;

if A is matrix,

then solving for `|A-lamdaI|=0`

by solving the above charactertics equation we get the values of `lamda` which denotes the eigen values and the maximum value of eigen value corresponds the spectral radius.

The coefficient matrix can be decomposed into diagonal matrix,upper triangular matrix and lower triangular matrix.

A=D+U+L

The iteration matrix for jacobi method is,

`T_(jac)=D^-1*(L+U)`

The iteration matrix for Gauss-Seidal method is,

`T_(gauss)=(D+L)^-1*U`

The iteration matrix for SOR method is,

`T_(SOR) =(D+w*L)^-1*(w*U+(w-1)*D)`

Solution using jacobi,gauss-seidal and SOR

`x^(k+1)=D^-1*B-T_(jac)*x^k` (jacobi)

`x^(k+1)=(D+L)^-1*B-T_(gauss)*x^k` (gauss-seidal)

`x^(k+1)=(D+w*L)^-1*w*B-T_(SOR)*x^k` (SOR)

Results:

Eigen values and spectral radius of iteration matrix.(for diagonal magnifier=1)

For jacobi

For gauss seidal

For SOR

Comparision between spectral radius and diagonal magnification.

Comparision between spectral radius and number of iterations.

Conclusion:

1. From the above graphs it can be concluded that as the diagonal magnification increases the spectral radius decreases or in other words increase in diagonal term of iteration matrix decreases the spectral radius.

2. It can be also seen that as the spectral radius of iteration matrix increases the no iterations also increases.So a for high spectral the solution does not converge well.

3. It was seen that for spectral radius above 1 the solution did not converge for al three iterative methods and showed error.

Matlab code:

%main program
close all;
clear all;
clc;

tol=1e-4;
m=linspace(1,5,9);
[rho_jac iter xjac]=spectral_radius_jacobi(tol);
[rho_gauss iter_gauss xgs]=spectral_radius_gs(tol);
[rho_sor iter_sor xsor]=spectral_radius_sor(tol);
figure(1)
subplot(3,1,1)
plot(rho_jac,iter,'-o','MarkerEdgeColor','red','MarkerFaceColor','red','linewidth',2)
xlabel('spectral radius')
ylabel('No of iterations')
title('jacobi iteration')
 grid on
 subplot(3,1,2)
 plot(rho_gauss,iter_gauss,'-o','MarkerEdgeColor','red','MarkerFaceColor','red','linewidth',2)
 xlabel('spectral radius')
ylabel('No of iterations')
title('gauss iteration')
 grid on
subplot(3,1,3)
 plot(rho_sor,iter_sor,'-o','MarkerEdgeColor','red','MarkerFaceColor','red','linewidth',2)
 xlabel('spectral radius')
ylabel('No of iterations')
title('sor iteration')
 grid on
 figure(2)
 subplot(3,1,1)
plot(m,rho_jac,'-o','MarkerEdgeColor','red','MarkerFaceColor','red','linewidth',2)
xlabel('magnification factor')
ylabel('spectral radius')
title('jacobi iteration')
 grid on
 subplot(3,1,2)
 plot(m,rho_gauss,'-o','MarkerEdgeColor','red','MarkerFaceColor','red','linewidth',2)
 xlabel('magnification factor')
ylabel('spectral radius')
title('gauss iteration')
 grid on
subplot(3,1,3)
 plot(m,rho_sor,'-o','MarkerEdgeColor','red','MarkerFaceColor','red','linewidth',2)
 xlabel('magnification factor')
ylabel('spectral radius')
title('sor iteration')
 grid on
 
 

function [rho_jac iter xjac]=spectral_radius_jacobi(tol)
D=[5 0 0;0 9 0;0 0 -7];
U=[0 1 2;0 0 4;0 0 0];
L=[0 0 0;-3 0 0;1 2 0];
A=D+L+U;
B=[10;-14;33];
xjac=[0;0;0];
xold=xjac;
m=linspace(1,5,9);
for i=1:length(m)
error=9e9;
 Dn=m(i)*D;
T_jac=inv(Dn)*(L+U);
I = eye(length(T_jac));
syms x
eq1 = det(T_jac-I*x) == 0 ;
eigval = double(solve(eq1,x))
 rho_jac(i)=max(real(eigval))
jacobi=1;
     while(error>tol)
 xjac=inv(Dn)*B-T_jac*xold;
error=max(max(abs(xold-xjac)));
xold=xjac;
jacobi=jacobi+1;
     end
     iter(i)=jacobi;
end
end

function [rho_gauss iter_gauss xgs]=spectral_radius_gs(tol)
D=[5 0 0;0 9 0;0 0 -7];
U=[0 1 2;0 0 4;0 0 0];
L=[0 0 0;-3 0 0;1 2 0];
A=D+U+L;
B=[10;-14;33];
xgs=[0;0;0];
xold=xgs;
m=linspace(1,5,9);
for i=1:length(m)
error=9e9;
 Dn=m(i)*D;
T_gauss=inv(Dn+L)*U;
I = eye(length(T_gauss));
syms x
eq1 = det(T_gauss-I*x) == 0 ;
eigval = double(solve(eq1,x))
 rho_gauss(i)=max(real(eigval))
GS=1;
     while(error>tol)
 xgs=inv(Dn+L)*B-T_gauss*xold;
error=max(max(abs(xold-xgs)));
xold=xgs;
GS=GS+1;
     end
     iter_gauss(i)=GS;
end
end
 

function [rho_sor iter_sor xsor]=spectral_radius_sor(tol)
D=[5 0 0;0 9 0;0 0 -7];
U=[0 1 2;0 0 4;0 0 0];
L=[0 0 0;-3 0 0;1 2 0];
A=D+L+U;
B=[10;-14;33];
xsor=[0;0;0];
xold=xsor;
m=linspace(1,5,9);
for i=1:length(m)
error=9e9;
 Dn=m(i)*D;
 w=1.2;
T_sor=inv(Dn+w*L)*(w*U+(w-1)*Dn);
I = eye(length(T_sor));
syms x
eq1 = det(T_sor-I*x) == 0 ;
eigval = double(solve(eq1,x))
rho_sor(i)=max(real(eigval))

SOR=1;
     while(error>tol)
 xsor=inv(Dn+w*L)*w*B-T_sor*xold;
error=max(max(abs(xold-xsor)));
xold=xsor;
SOR=SOR+1;
     end
     iter_sor(i)=SOR;
end
end