Week-6: To determine the Eigenvalues and Spectral radius of an Iteration matrix:

To determine the Eigenvalues and Spectral radius of an Iteration matrix:

The given matrix is,

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

`X =[[x1],[x2], [x3]]`

`B= [[10] ,[-14] ,[33]];`

AX =B;

The matrix A could be split into 3 matrices as below:

Diagonal Matrix (D) = `[[5,0,0],[0,9,0],[0,0,-7]]`

Upper Traiagular matrix (U) = `[[0,0,0],[-3,0,0],[1,2,0]]`

Lower Triangular Matrix (L) = `[[0,1,2],[0,0,4],[0,0,0]]`

To calculate the Spectral radius of each iterative matrix, the following should be the equation to calculate the spectral radius:

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

GS Method, `T_(GS) =(L+D)^-1*U`

SOR Method, `T_(SOR)=(D+omega*L)^-1* (omega*U-(1-omega)*D)`

The omega value in SOR Method will be 0.9.

The eigenvalues will be calculated for these iteratives. And the spectral radius would be the maximum of real of eigenvalues.

To change the spectral value to diagonal magnification factor is used which will be multiplied with D to alter the spectral radius.

Main code:

clear all
close all
clc

%matrix A
A=[5 1 2;-3 9 4;1 2 -7];
B = [10;-14;33];

%matrix decomposition of A into L,D,U
D=diag(diag(A)); %diagonal matrix of A
L = tril(A)-D;   %Lower triangular matrix
U=triu(A)-D;     %Upper triangular matrix

%X = inv(A)*B;
D_old=D;

%omega value for SOR iteration
omega = 0.9;

%magnifying the diagonal matrix
d=linspace(0.2,2,8)






for j = 1:length (d)
    
[x_jac,jac_iter(j),rho_jac(j)]= jac_sol(L,U,B,D,d(j)); %calling Jacobi Function

[x_GS,GS_iter(j),rho_GS(j)]= GS_sol(L,D,B,U,d(j));  %calling GS Function

[x_SOR,SOR_iter(j),rho_SOR(j)]= SOR_sol(L,D,B,U,omega,d(j)); %calling SOR Function

end

%plotting for spectral radius and diagonal magnification
figure(1)
subplot(2,1,1)
plot(d,rho_jac)
grid on
xlabel('diagonal magnifier')
ylabel('spectral radius(rho)')
title('Jacobi method','FontSize',20);
hold on
subplot(2,1,2)
semilogy(rho_jac,jac_iter)
grid on
xlabel('spectral radius(rho)')
ylabel('iterations')


figure(2)
subplot(2,1,1)
plot(d,rho_GS)
grid on
xlabel('diagonal magnifier')
ylabel('spectral radius(rho)')
title('Gauss Seidel method','FontSize',20);
hold on
subplot(2,1,2)
semilogy(rho_GS,GS_iter)
grid on
xlabel('spectral radius(rho)')
ylabel('iterations')


figure(3)
subplot(2,1,1)
plot(d,rho_SOR)
grid on
xlabel('diagonal magnifier')
ylabel('spectral radius(rho)')
title('SOR method','FontSize',20);
hold on
subplot(2,1,2)
semilogy(rho_SOR,SOR_iter)
grid on
xlabel('spectral radius(rho)')
ylabel('iterations')

Function for Jacobi:

function [x_jac,jac_iter,rho_jac]= jac_sol(L,U,B,D,d)


D= d* D;
T_jac=inv(D)*(L+U); %iteration matrix for jacobi method

iteration = 0;
error = 9e9;
tolerance = 1e-4;
x_old= zeros(3,1);
while error> tolerance
    
    
    x = -(T_jac*x_old) +inv(D)*B;
    error = max(abs(x-x_old));
    x_old = x;
    
    iteration = iteration +1;
end
x_jac= x
jac_iter=iteration  %iteration count


eig_value =eig(T_jac); %Eigen value of iterative matrix
rho_jac= max(abs(real(eig_value))) %Spectral radius of the iterative matrix

end

    

Function for Gauss-Seidel:

function [x_GS,GS_iter,rho_GS]= GS_sol(L,D,B,U,d)
D= d* D;
T_GS =inv(L+D)*U;    %iteration matrix for Gauss-seidel method

iteration = 0;
error = 9e9;
tolerance = 1e-4;
x_old= zeros(3,1);

   
while error> tolerance
    
    
    x = -T_GS*x_old +inv(L+D)*B;
    error = max(abs(x-x_old));
    x_old = x;
    
    iteration = iteration +1;
end
x_GS=x
GS_iter=iteration %iteration count

eig_value =eig(T_GS); %Eigen value of iterative matrix
rho_GS= max(abs(real(eig_value))) %Spectral radius of the iterative matrix
end

    

Function for SOR:

function [x_SOR,SOR_iter,rho_SOR]= SOR_sol(L,D,B,U,omega,d)

iteration = 0;
error = 9e9;
tolerance = 1e-4;
x_old= zeros(3,1);

D= d* D;
T_SOR=inv(D+omega*L)* (omega*U-(1-omega)*D); %iteration matrix for SOR method

while error> tolerance
    
    
    x = T_SOR*x_old + inv(D+omega*L)*omega*B;
    error = max(abs(x-x_old));
    x_old = x;
    
    iteration = iteration +1;
end
x_SOR= x 
SOR_iter = iteration %iteration count


eig_value =eig(T_SOR); %Eigen value of iterative matrix
rho_SOR= max(abs(real(eig_value))) %Spectral radius of the iterative matrix

end

    

Results and Observation:

All the values have been tabulated as shown below:

Diagonal magnification Factor = 0.2

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.4878	Spectral radius =11.1738	Spectral radius =8.4436
No. of Iterations = 758	No. of Iterations = 297	No. of Iterations = 335
X1 = NaN	X1 = NaN	X1 = NaN
X2 = NaN	X2 = NaN	X2 = NaN
X3 =NaN	X3 =NaN	X3 =NaN

Diagonal magnification Factor =0.4571

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.2134	Spectral radius =1.6781	Spectral radius =1.1098
No. of Iterations = 6447	No. of Iterations= 1371	No. of Iterations = 6771
X1 = NaN	X1 = NaN	X1 = NaN
X2 = NaN	X2 = NaN	X2 = NaN
X3 =NaN	X3 =NaN	X3 =NaN

Diagonal magnification Factor = 0.7143

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.1366	Spectral radius = 0.6497	Spectral radius =0.2855
No. of Iterations = 35	No. of Iterations = 28	No. of Iterations = 11
X1 = 4.5737	X1 = 4.5737	X1 =-3.1452
X2 = 2.7977	X2 = 2.7978	X2 = -7.1921
X3 =-4.5662	X3 =-4.5661	X3 =-8.2684

Diagonal magnification Factor = 0.9714

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.1004	Spectral radius =0.3472	Spectral radius =0.1281
No. of Iterations = 18	No. of Iterations = 12	No. of Iterations = 7
X1 = 3.4022	X1 = 3.4022	X1 = -0.4827
X2 = 1.3727	X2 = 1.3728	X2 = -3.2462
X3 =-3.9489	X3 = -3.9489	X3 =-4.8098

Diagonal magnification Factor = 1.2286

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.0794	Spectral radius =0.2181	Spectral radius =0.1227
No. of Iterations = 14	No. of Iterations = 9	No. of Iterations = 7
X1 = 2.6191	X1 = 2.6191	X1 = 0.1217
X2 = 0.6664	X2 = 0.6664	X2 = -2.0502
X3 =-3.3777	X3 =-3.3777	X3 =-3.5181

Diagonal magnification Factor = 1.4857

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.0657	Spectral radius =0.1509	Spectral radius =0.1191
No. of Iterations = 11	No. of Iterations = 8	No. of Iterations = 7
X1 = 2.0915	X1 = 2.0915	X1 = 0.3201
X2 = 0.2944	X2 = 0.2944	X2 = -1.4843
X3 =-2.9154	X3 =-2.9154	X3 =-2.8045

Diagonal magnification Factor = 1.7429

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.0560	Spectral radius =0.1113	Spectral radius =0.1164
No. of Iterations = 10	No. of Iterations = 7	No. of Iterations = 7
X1 = 1.7227	X1 = 1.7227	X1 = 0.3904
X2 = 1.7227	X2 = 1.7227	X2 = -1.1579
X3 =-2.5495	X3 =-2.5495	X3 =-2.3422

Diagonal magnification Factor = 2

Jacobi Method	Gauss-Seidel Method	SOR Method
Spectral radius =0.0488	Spectral radius = 0.0859	Spectral radius =0.1144
No. of Iterations = 9	No. of Iterations = 6	No. of Iterations = 7
X1 = 1.4549	X1 = 1.4549	X1 = 0.4110
X2 = -0.0335	X2 = -0.0335	X2 = -0.9467
X3 =-2.2580	X3 =-2.2580	X3 =-2.0152

From this data, we could Observe that as the Diagonal Magnification factor increased, the spectral radius of the iterative matrix decreases and vice versa. The iterations are also directly proportional to the spectral radius.

However, as the spectral radius increased more than 1.1, the solution doesn't converge as the values will be NaN.