LU decomposition
Definition 1
Let be an matrix. An LU decomposition (sometimes also called an LU factorization) of , if itexists, is an unit lower triangular matrix and an matrix U, in (upper) echelon form
, such that
The LU factorization is closely related to the row reductionalgorithm. In a very real sense, the factorization is a record of thesteps taken in row reducing a matrix to echelon form. The matrix “encodes” the sequence of row replacement operations
that rowreduce the given matrix to echelon form .
Proposition 2
Suppose that is an LU factorization, and let denotethe entries of . Then, the row reduction is accomplished by thefollowing sequence of row replacementoperations:
Note: the first steps clear out column , the next stepsclear out column , etc.
Proposition 3
Not every matrix admits an LU factorization. Indeed, an LUfactorization exists if and only if can be reduced to echelonwithout using row exchange operations. However, if an LUfactorization exists, then it is unique.
In the most general case, one has to employ row exchange operations.
Proposition 4
Let be an matrix. Then, there exists an permutation matrix (indeed, many such) such that the matrix admits an LU factorization, i.e., there exist matrices such that
The key idea behind LU factorization is that one does not need toemploy row scalings to do row reduction until the second half (theback-substitution phase) of the algorithm. This has significantimplication for numerical stability of the algorithm.
The LU decomposition of a given matrix is useful for the solutionof the systems of linear equations of the form . Indeed, itsuffices to first solve the linear system , and second, to solvethe system . This two-step procedure is easy to implement,because owing to the lower and upper-triangular nature of thematrices and , the required row operations are determined, moreor less, directly from the entries of and . Indeed, the firststep,
a sequence of row operations , and the second step
a sequence of row operations , are exactly the same row operationsone has to perform to row reduce directly to reduced echelon form :
Note: is the particular solution of that sits in therightmost colulmn of the augmented matrix at the termination of therow-reduction algorithm.