In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix (see matrix multiplication and matrix decomposition). The product sometimes includes a permutation matrix as well. LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using LU decomposition, and it is also a key step when inverting a matrix or computing the determinant of a matrix. It is also sometimes referred to as LR decomposition (factors into left and right triangular matrices). The LU decomposition algorithm for general matrices was introduced by the Polish astronomer Tadeusz Banachiewicz in 1938.
Definitions
Let A be a square matrix. An LU factorization refers to expression of A into product of two factors – a lower triangular matrix L and an upper triangular matrix U such that A = LU. Sometimes factorization is impossible without prior reordering of A to prevent division by zero or uncontrolled growth of rounding errors. Hence alternative expression becomes PAQ = LU, where in formal notation permutation matrix factors P and Q indicate permutation of rows (or columns) of A. In theory P (or Q) is obtained by permutations of rows (or columns) of the identity matrix; in practice the corresponding permutations are applied directly to rows (or columns) of A. Matrix A of side n has n 2 {\displaystyle n^{2}} coefficients while two triangle matrices combined contain n(n + 1) coefficients, and therefore n coefficients of matrices LU are not independent. The convention is to set L unitriangular, i.e. with all n main diagonal elements equal to one. However, setting instead U matrix unitriangular reduces to the same procedure after transpose of matrix product (cf. properties of matrix transposition):
B = A T = ( L U ) T = U T L T . {\displaystyle B=A^{\textsf {T}}=(LU)^{\textsf {T}}=U^{\textsf {T}}L^{\textsf {T}}.}
After transposition, UT is lower triangle while LT is upper unitriangular factor of B. This demonstrates also, that operations on rows (e.g. pivoting) are equivalent to those on columns of a transposed matrix, and in general choice of row or column algorithm offers no advantage. In the lower triangular matrix all elements above the main diagonal are zero, in the upper triangular matrix, all the elements below the diagonal are zero. For example, for a 3 × 3 matrix A, its LU decomposition looks like this:
… excerpt ends here. Continue reading the full article.
