LU decomposition

views updated

LU decomposition A method used in numerical linear algebra in order to solve a set of linear equations, Ax = b

where A is a square matrix and b is a column vector. In this method, a lower triangular matrix L and an upper triangular matrix U are sought such that LU = A

For definiteness, the diagonal elements of L may be taken to be 1. The elements of successive rows of U and L may easily be calculated from the defining equations.

Once L and U have been determined, so that LUx = b,

the equation Ly = b

is solved by forward substitution. Thereafter the equation Ux = y

is solved for x by backward substitution. x is then the solution to the original problem.

A variant of the method, the method of LDU decomposition, seeks lower and upper triangular matrices with unit diagonal and a diagonal matrix D, such that A = LDU

If the matrix A is symmetric and positive definite, there is an advantage in finding a lower triangular matrix L such that A = L LT

(see transpose). This method is known as Cholesky decomposition; the diagonal elements of L are not, in general, unity.

More From encyclopedia.com