LU decomposition, also known as LU factorization, is one of the common methods adopted to find the solution of linear simultaneous equations in numerical analysis and other engineering problems. In this post, I have included simple algorithm and flowchart for LU factorization method. Here’s a brief introduction to the method, and algorithm samples for Doolittle’s and Crout’s LU decomposition.
The basic principle used to write the LU decomposition algorithm and flowchart is – ““A square matrix [A] can be written as the product of a lower triangular matrix [L] and an upper triangular matrix [U], one of them being unit triangular, if all the principal minors of [A] are non-singular.”
So, for a linear system AX = b, the given matrix [A] can be decomposed into the product two lower and upper triangular matrices.
Here, I have presented a simple flowchart for the method. For the algorithm part, you can find images for Doolittle’s LU algorithm, Crout’s LU algorithm and a short algorithm for LU decomposition method itself.
LU Factorization Algorithm:
- Start
- Read the elements of augmented matrix into arrays a and b
- Calculate elements of L and U
- Print elements of L and U
- Find V by solving LV = B by forward substitution
- Find X by solving UX = V by backward substitution
- Print Array X as the solution
- Stop
The principle difference between Doolittle’s and Crout’s LU decomposition method is the calculation sequence these methods follow. Both the methods exhibit similarity in terms of inner product accumulation.
In Doolittle’s method, calculations are sequenced to compute one row of L followed by the corresponding row of U until A is exhausted. Below is the computational sequence and algorithm for Doolittle’s LU decomposition.
Whereas in Crout’s method, calculations are sequenced to compute one column of L followed by the corresponding row of U until A is exhausted. Below is the computational sequence and algorithm for Crout’s LU decomposition.
LU Decomposition Flowchart:
Also see,
LU Factorization C Program
Numerical Methods Tutorial Compilation
This LU decomposition algorithm and flowchart can be used to write source codes in any high level programming language. If you have any queries regarding the algorithm, flowchart or source code of LU method discussed here, bring them up to me from the comments section below.
English