A lower triangular matrix inversion using 2 methods: 1) forward/backward substitution 2)Neumann series
조회 수: 10 (최근 30일)
이전 댓글 표시
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
채택된 답변
Gouri Chennuru
2020년 3월 12일
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
추가 답변 (0개)
참고 항목
카테고리
Help Center 및 File Exchange에서 Loops and Conditional Statements에 대해 자세히 알아보기
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!