COMPUTING EIGEN VALUES AND SPECTRAL RADIUS

ABSTRACT:

The main objective of this challenge is to write a matlab code which calculates Eigen Values, Spectral radius of a matrix. As well it should be able to find Iterative matrix and solution for variables using Jacobian, Gauss Seidel and Successive over Relaxation method.

Given matrix are:

EIGEN VALUE CALCULATION:

Spectral radius is the maximum real number of Eigen values obtained from the above step. Simply a set of matrices can be said it can converge easily or not by examining the value of spectral radius. If the spectral radius of given set of matrices is less than one it can converge easily, else it will not converge quickly and will lead to Infinity result or number not exist result in Matlab. For finding spectral radius of matrix, a square matrix should be divided into three as follows:

1. Diagonal Matrix (D)

2. Upper Triangular Matrix (U)

3. Lower Triangular Matrix (L)

Tolerance used throughot the case is 1e-4

MAIN PROGRAM CODE:

clear all
close all
clc

% Given matrix and its decomposition
A = [5 1 2 ; -3 9 4; 1 2 -7];
D = diag(diag(A));                                                        
L = tril(A) - D;                                                            
U = triu(A) - D;

% Given RHS
B = [10;-14;33];

% Diagonal magnifier
mag = [0.5 1 2 3 5 6];


for i = 1:length(mag)

D = diag(diag(A)); 

% magnification of the diagonal terms
D = mag(i)*D;    

% Components of the iteration matrices                                                  
S_jac = D;
T_jac = -(L+U);
S_GS =  L+D;
T_GS = -U;
w = 1.5;                   % over relaxation factor
S_SOR = (w*L+D);
T_SOR = (((1-w)*D)-w*U);


% Iteration matrices
jacobi_it_mat = inv(S_jac)*T_jac;
GS_it_mat = inv(S_GS)*T_GS;
SOR_it_mat = inv(S_SOR)*T_SOR;

% Eigen value calculation without using the inbuilt function eig()
eig_j = roots(poly(jacobi_it_mat));
eig_GS = roots(poly(GS_it_mat));
eig_SOR = roots(poly(SOR_it_mat));

% spectral radius 
rho_j(i) = max(abs(eig_j));
rho_GS(i) = max(abs(eig_GS));
rho_SOR(i) = max(abs(eig_SOR));


%% Calculating the no.of iterations required to find x[] using function, with tolerance 1e-4

% jacobi
if rho_j(i) < 1
 [iter_j(i),x_j] = iterative_solution(jacobi_it_mat, S_jac, B);
 printf("Jacobi_iterations, with %d as diagonal magnifier and %d as the rho value = %dn",mag(i),rho_j(i),iter_j(i));
else
% The following command is used here to avoid the error "warning: axis: omitting non-positive data in log plot".
% Because, the log of zero is -infinity. This is the reason for the error.
   iter_j(i) = nan;
   printf("rho_jacobi = %d. Therefore solution doesn't converge with %d as diagonal magnifiern", rho_j, mag(i));
end

% GS
if rho_GS(i) < 1
 [iter_GS(i),x_GS] = iterative_solution(GS_it_mat, S_GS, B);
 printf("GS_iterations, with %d as diagonal magnifier and %d as the rho value = %dn",mag(i),rho_GS(i),iter_GS(i));
else
% The following command is used here to avoid the error "warning: axis: omitting non-positive data in log plot".
% Because, the log of zero is -infinity. This is the reason for the error.
 iter_GS(i) = nan;
 printf("rho_GS = %d. Therefore solution doesn't converge with %d as diagonal magnifiern", rho_GS(i),mag(i));
end


% SOR
if rho_SOR(i) < 1
 [iter_SOR(i),x_SOR] = iterative_solution(SOR_it_mat, S_SOR, B*w);
 printf("SOR_iterations, with %d as diagonal magnifier and %d as the rho value = %dnn",mag(i),rho_SOR(i),iter_SOR(i));
else
% The following command is used here to avoid the error "warning: axis: omitting non-positive data in log plot".
% Because, the log of zero is -infinity. This is the reason for the error.
  iter_SOR(i) = nan;
  printf("rho_SOR = %d. Therefore solution doesn't converge with %d as diagonal magnifiernn", rho_SOR(i),mag(i));
end

end


% Plotting

graphics_toolkit("gnuplot");

figure(1)
subplot(2,1,1)
plot(mag,rho_j,'-ro','linewidth',2,'markersize',4,'markeredgecolor','b','markerfacecolor','c');
xlabel('Diagonal magnifier');
ylabel('rho');
title('JACOBI METHOD','Fontsize',16);
axis([min(mag) max(mag) 0 max(rho_j)]);


subplot(2,1,2)
loglog(rho_j,iter_j,'-ro','linewidth',2,'markersize',4,'markeredgecolor','b','markerfacecolor','c');
xlabel('rho');
ylabel('Iterations');
axis([min(rho_j) sort(rho_j)(end-1) 4 20]);
saveas(gca,"Jacobi_plot.png");

figure(2)
subplot(2,1,1)
plot(mag,rho_GS,'-ro','linewidth',2,'markersize',4,'markeredgecolor','b','markerfacecolor','c');
xlabel('Diagonal magnifier');
ylabel('rho');
title('GS METHOD','Fontsize',16);
axis([min(mag) max(mag) 0 max(rho_GS)]);


subplot(2,1,2)
loglog(rho_GS,iter_GS,'-ro','linewidth',2,'markersize',4,'markeredgecolor','b','markerfacecolor','c');
xlabel('rho');
ylabel('Iterations');
axis([min(rho_GS) sort(rho_GS)(end-1) 3 13]);
saveas(gca,"GS_plot.png");

figure(3)
subplot(2,1,1)
plot(mag,rho_SOR,'-ro','linewidth',2,'markersize',4,'markeredgecolor','b','markerfacecolor','c');
xlabel('Diagonal magnifier');
ylabel('rho');
title('SOR METHOD','Fontsize',16);
axis([min(mag) max(mag) 0 max(rho_SOR)]);


subplot(2,1,2)
loglog(rho_SOR,iter_SOR,'-ro','linewidth',2,'markersize',4,'markeredgecolor','b','markerfacecolor','c');
xlabel('rho');
ylabel('Iterations');
axis([min(rho_SOR) sort(rho_SOR)(end-2) 16 120]);
saveas(gca,"SOR_plot.png");

FUNCTION CODE:

function [iter,xnew] = iterative_solution(iterative_matrix, S, B)

error = 9e9;
tol = 1e-4;
x = 0.01*ones(3,1);
iter = 0;
xold = x;


while error > tol
 x = iterative_matrix*xold + inv(S)*B;
 error = max(abs(xold-x));
 xold = x;
 iter = iter + 1;
end 
  xnew = x;

end

OBSERVATION & RESULTS:

Following results are plotted down in graphs : 

rho_jacobi = 1.02042. Therefore solution doesn't converge with 0.5 as diagonal magnifier
rho_GS = 1.38147. Therefore solution doesn't converge with 0.5 as diagonal magnifier
rho_SOR = 4.44667. Therefore solution doesn't converge with 0.5 as diagonal magnifier

Jacobi_iterations, with 1 as diagonal magnifier and 0.510208 as the rho value = 18
GS_iterations, with 1 as diagonal magnifier and 0.327645 as the rho value = 12
rho_SOR = 1.63434. Therefore solution doesn't converge with 1 as diagonal magnifier

Jacobi_iterations, with 2 as diagonal magnifier and 0.255104 as the rho value = 9
GS_iterations, with 2 as diagonal magnifier and 0.0859319 as the rho value = 6
SOR_iterations, with 2 as diagonal magnifier and 0.916528 as the rho value = 117

Jacobi_iterations, with 3 as diagonal magnifier and 0.170069 as the rho value = 7
GS_iterations, with 3 as diagonal magnifier and 0.0408032 as the rho value = 5
SOR_iterations, with 3 as diagonal magnifier and 0.75 as the rho value = 35

Jacobi_iterations, with 5 as diagonal magnifier and 0.102042 as the rho value = 5
GS_iterations, with 5 as diagonal magnifier and 0.0164951 as the rho value = 4
SOR_iterations, with 5 as diagonal magnifier and 0.637911 as the rho value = 22

Jacobi_iterations, with 6 as diagonal magnifier and 0.0850347 as the rho value = 5
GS_iterations, with 6 as diagonal magnifier and 0.0120298 as the rho value = 4
SOR_iterations, with 6 as diagonal magnifier and 0.612542 as the rho value = 20

CONCLUSIONS FROM THE RESULT: 

As the values of the diagonal elements of the given matrix increases, the value of spectral radius decreases.

As the value of the spectral radius increases, the no.of iterations required for convergence increases, i.e they both are directly proportional.             

Iterative techniques fail to converge when the spectral radius becomes greater than 1.