A lower triangular matrix inversion using 2 methods: 1) forward/backward substitution 2)Neumann series
34 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Nurulhuda Ismail
el 9 de Mzo. de 2020
Respondida: Gouri Chennuru
el 12 de Mzo. de 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 comentarios
Respuesta aceptada
Gouri Chennuru
el 12 de Mzo. de 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 comentarios
Más respuestas (0)
Ver también
Categorías
Más información sobre Matrix Decomposition en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!