L-U Decomposition

MATLAB codes for lower–upper (LU) decomposition or factorization of a matrix

1. PRACTICAL Name- Saloni Singhal M.Sc. (Statistics) II-Sem. Roll No: 2046398 Course- MATH-409 L Numerical Analysis Lab Submitted To: Dr. S.C. Pandey 2.3

2. O BJECTIVE To write an m-file to implement L-U Decomposition (without pivoting) for solving system of linear equations. To write both script and function files for the same program.

3. Theory The system of equation is based on the observation that system of linear equation involving triangular Coefficient Matrix are easier to deal with. T he composition is the product of lower triangular Matrix and an upper triangular matrix

4. Script File % defines matrix A A = [2 1 5; 3 5 2;2 1 4] [ m,n ]=size(A); if m~=n fprintf ( "not square matrix" ) exit end L=eye(n); U=A; ref=[U L]; %decomposition for i =1:m-1 for j=i+1:m a=ref( j,i )/ref( i,i ); %back substitution ref(j,:)=ref(j,:)-a*ref( i ,:); end end %representation U=ref(1:n,1:n) L=ref(1:n,n+1:2*n); L=inv(L) %verification [c]=L*U

5. Function File   function [L,U] =decomposition(A) [ m,n ]=size(A); if m~=n fprintf ( "not square matrix" ) exit end L=eye(n); U=A; ref=[U L]; %decomposition for i =1:m-1 for j=i+1:m a=ref( j,i )/ref( i,i ); %back substitution ref(j,:)=ref(j,:)-a*ref( i ,:); end end %representation U=ref(1:n,1:n) L=ref(1:n,n+1:2*n); L= inv (L) %verification [c]=L*U end

6. Cases/Example

7. Time Complexity 7 For the given program it is calculated as: For i =1 T(j)=4n(m-1) For i =2 T(j)=4n(m-2)… on summation T(n)= 4n(m-1) +(m-2)4n+ 4n(m-3)…..1 T(n)=4n(m 2 – m(m-1)/2 ), since in square matrix m=n T(n 3 +n 2 )/ 2=O (n 3 ) Big O notation is the most common metric for calculating time complexity. It describes the execution time of a task in relation to the number of steps required to complete it.   Initially form i loop of range 1:n-1, we take n operations, then 4 operation inside the loop for j. ‘O’ takes its dominant value

8. Conclusion It is more efficient as it requires gaussian elimination to be performed once It is better for solving repeatedly and number of equation with same on the left hand side. It does not require augmented matrix. Cholesky decomposition is faster by a factor of 2 and take lesser memory and space

9. Caveats Using L-U Decomposition can be unstable in algorithm, we may run into blown up errors with poorly managed flops and operations. The original matrix is lost Sometimes it is impossible to write a matrix in the form of L-U composition if the leading matrix don't have a non-zero determinant

10. References https://learn.lboro.ac.uk/archive/olmp/olmp_resources/pages/workbooks_1_50_jan2008/Workbook30/30_3_lu_decmp.pdf Lecture Notes of Prof. S.C. Pandey Sir MATLAB Documetation