Overview

LU decomposition


Show Summary Details

Quick Reference

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= LLT

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

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.