UNDERSTANDING LINEAR SYSTEMS.
UNDERSTANDING LINEAR SYSTEMS.
Given Data:-
A=[5 1 2 ; -3 9 4; 1 2 -7]
X=[x1;x2;x3]
B=[10 -14 33]
To Find:-
- 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.
Soluton:-
Main objective is to solve a linear system using different iterative techniques for determnng the spectral radius. By changing the spectral radius, we observe its effect on the system and its stability .
Fro the given data, consider the following ;
Coefficient Matrix (A):
Coloumn Vector (X):
Row Vector (B):
Diagonal Matrix (D):
Lower Diagonal Matrix (L):
Lower Diagonal Matrix (U):
Finding the Eigen values:- A non-zero vector 'x' s an eigen vector of a square matriX 'A' if there exists a scalar 'λ' such that Ax=λx. Then λ is an eigen value of A.
Spectral Radius:- A spectral radius of a square matrix is the largest absolute value of eigen values. Bascially denoted by 'rho-ρ'.
>> In a matrix when diagonal terms are larger, the spectral radius becomes shorter.
>> In ths case, when spectral radius becomes larger, things dont converge very well i.e. we see increase in the number of iterations.
Now solving Ax=B using various iterative techniqes i.e. by Jacobi, Gauss-seidel and Successive Over Relaxation methods.
- JacobI Method:
-
Gauss-Seidel Method:
- Successive Over Relaxation Method:
Where, D - Diagonal Matrix.
L - Lower Diagonal Matrix.
U - Upper Diagonal Matrix.
ω - relaxaton factor.
Program to manually determine the Eigen Value and Spectral Radius of the given system of equations:
Main Code:
clear all
close all
clc
%inputs
A=[5 1 2; -3 9 4; 1 2 -7];
B=[10; -14; -33];
%Diagonal Matrix
D=[5 0 0; 0 9 0; 0 0 -7];
%Upper Diagonal Matrix
U=[0 1 2; 0 0 4; 0 0 0];
%Lower Diagonal Matrix
L=[0 0 0; -3 0 0; 1 2 0];
% Coefficient Matrix of A
A = D + L + U;
%RHS Matrix
B=[10 -14 33];
R =L+U;
%omega is relaxation factor for sor.
w = 1.25;
magnifying_factor=linspace(1,10,10);
for i=1:length(magnifying_factor)
D1 = magnifying_factor(i)*D;
% Computing iteration matrix.
T_jac = inv(D1)*(L+U);
T_gs = inv(D1+L)*U;
T_sor = inv(D1+w*L)*((1-w)*D1-w*U);
% Computing eigen values of iteration matrix.
eigenvalue_jac = roots(poly(T_jac));
eigenvalue_gs = roots(poly(T_gs));
eigenvalue_sor = roots(poly(T_sor));
% Computing spectral radius of iteration matrix.
%rho_jac = spectral_radius
spectral_radius_jac(i) = max(abs(eigenvalue_jac));
spectral_radius_gs(i) = max(abs(eigenvalue_gs ));
spectral_radius_sor(i) = max(abs(eigenvalue_sor));
% Calling iterative method.
[jacobi_iter(i), x_jac] = jacobi(D1,L,U,B);
[gs_iter(i),x_gs] = gaussiedle(D1,L,U,B);
[sor_iter(i),x_sor] = sor(D1,L,U,B,w);
end
% plotting
figure(1)
subplot(2,1,1)
plot(spectral_radius_jac,jacobi_iter);
xlabel('spectral_radius')
ylabel('no of iterations')
title('JACOBI METHOD')
grid on
subplot(2,1,2)
plot(spectral_radius_jac, magnifying_factor);
xlabel('spectral_radius')
ylabel(' magnifying_factor')
title('JACOBI METHOD')
grid on
figure(2)
subplot(2,1,1)
plot(spectral_radius_gs, magnifying_factor);
plot(spectral_radius_gs,gs_iter);
ylabel('no of iterations')
xlabel('spectral_radius')
title('GAUSS-SEIDAL METHOD')
grid on
subplot(2,1,2)
plot(spectral_radius_gs, magnifying_factor);
xlabel('spectral_radius')
ylabel(' magnifying_factor')
title('GAUSS-SEIDAL METHOD')
grid on
figure(3)
subplot(2,1,1)
plot(spectral_radius_sor,sor_iter);
xlabel('spectral_radius')
ylabel('no of iterations')
title('SOR METHOD')
grid on
subplot(2,1,2)
plot(spectral_radius_sor, magnifying_factor);
xlabel('spectral_radius')
ylabel(' magnifying_factor')
title('SOR METHOD')
grid on
Code for Jacobi function:
function [jacobi_iter,x_jac] = jacobi(D,L,U,B)
error = 9e9;
R = L+U;
tol = 1e-3;
x=[0;0;0];
xold=x;
jacobi_iter = 0;
while (error>tol)
x_jac = inv(D)* (B-(R*xold));
error = max(abs(x_jac-xold));
xold = x_jac;
jacobi_iter=jacobi_iter+1;
end
end
Code for Gauss-sedal function:
function [gs_iter,x_gs] = gaussiedle(D,L,U,B);
error = 9e9;
%R = L+U;
tol = 1e-3;
x=[0;0;0];
xold=x;
gs_iter = 1;
while (error>tol)
x_gs = (inv(D+L))*(B-(U*xold));
error = max(abs(x_gs-xold));
xold = x_gs;
gs_iter = gs_iter +1;
end
end Code for SOR function:
function [sor_iter,x_sor] = sor(D,L,U,B,w);
error = 9e9;
tol = 1e-3;
x=[0;0;0];
xold=x;
sor_iter = 1;
while (error>tol)
%x_sor = inv(D-w*L)*((1-w)*D+w*U)*xold*inv(D-w*L)*B;
x_sor = inv(D+w*L)*((w*B) - (w*U*xold)-((w-1)*D*xold));
error = max(abs(x_sor-xold));
xold = x_sor;
sor_iter = sor_iter +1;
end
end Explanation:-
>> Initially declair all the necessary inputs as per the given data.
>> Calculate the upper and lower diagonal matrx and define them.
>> Then coefficient of matrix should be mentioned along with the B matrix.
>> Magnifying factor s gven as linspace(1,10,10) respectively.
>> A for loop is created where declaring of iteration matrix, eigen values of iteration matrix, spectral radius of iteration matrix and Calling of iterative method should be done.
>> In this programme, multiple plots are plotted using subplot for the same methods. This is repeated for the other two methods also.
>> Individual function codes are created separately by following the code structure.
>> Through out the codng process tolerance is maintained as 1e-3 respectively.
Outcomes:-
1. Jacobi Method:
>> Jacobi_iter = 13 7 5 5 4 4 4 3 3
>>spectral_radius_jac = 0.5102 0.2551 0.17016 0.1276 0.1020 0.0850 0.0729 0.0638 0.0567 0.0510
2. Gauss-seidel Method:
>> gs_iter = 8 6 5 5 5 4 4 4 4 4
>>spectral_radius_gs = 0.3276 0.0859 0.0408 0.0244 0.0165 0.0120 0.0092 0.0074 0.0060 0.0051
3. SOR Method:
>> sor_iter = 172 7 7 7 6 6 6 6 6 6
>>spectral_radius_sor = 0.9623 0.5047 0.4011 0.3569 0.3325 0.3172 0.3066 0.2989 0.2930 0.2884
CONCLUSION:-
>> The above plotted graphs show the comparision of a spectral radius vs number of iterations and spectral radius vs magnifying factor. The above comparision s done by three iterative techniques i.e. jacobi, gauss-sedal and SOR methods.
>> It is observed that on increasing the spectral radius, the number of iteratons requred for convergence also increases. Hence spectral radius is directly praportional to number of iterations.
>> From spectral radius vs magnifying factor plots , it is concluded that on increasng the magnifying factor the spectral radius decreases. Hence spectral radius is inversly praportional to the magnifying factor.
>> In general for the larger values of the diaognal entries,smaller wll be the spectral radius.
>> If the spectral radius goes above 1, the matrx is unsolvable with the iterative techniques.