A lower triangular matrix inversion using 2 methods: 1) forward/backward substitution 2)Neumann series
10 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Nurulhuda Ismail
le 9 Mar 2020
Réponse apportée : Gouri Chennuru
le 12 Mar 2020
Hi,
I tried to solve a linear equation using Gauss-Seidel method and execute it in MATLAB. To solve a lower triangular matrix inversion in the Gauss-Seidel method, I use 2 different approaches: 1) Forward/Backward substitution method, 2) Series of matrix multiplication or we called it Neumann series.
1) Forward Substitution method
invL=zeros(K,K);
nn=length(L);
I=eye(K);
for k = 1:nn
for i = 1:nn
invL(k,i) = (I(k,i) - L(k,1:(k-1))*invL(1:(k-1),i))/L(k,k); % Lower triangular matrix inversion (L^(-1))
end
end
2) Neumann series
LL= 1:1:4
Ik=eye(K);
theta=1/D; %D is a diagonal matrix which consists of a diagonal elements of a lower triangular matrix L
t=(Ik-(theta*L)); %inner loop of Neumann series technique
T=zeros(K,K);
for n=0:LL
t1=t^n;
T=T+t1;
end
InvL=T*theta; %Lower triangular matrix inversion (L^(-1))
Based on the results, I found that the execution time using Neumann series is shorter than Forward/backward substitution, even though the computational complexity of Forward/backward substitution is simpler than the Neumann series. Why this happen?
Hope to hear from you.
Thank you.
0 commentaires
Réponse acceptée
Gouri Chennuru
le 12 Mar 2020
In case of Forward Substitution Method,
The time complexity is O(n^2) because there is nested for loop and the statement,
invL(k,i) = (I(k,i) - L(k,1:(k-1))*invL(1:(k-1),i))/L(k,k);
gets executed for nn^2 times.
In case of Neumann series,
The time complexity is O(n) because the set of statements inside the for loop i.e.,
t1=t^n;
T=T+t1;
Get executed for LL times.
0 commentaires
Plus de réponses (0)
Voir également
Catégories
En savoir plus sur Loops and Conditional Statements dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!