MATLAB Functions

LU matrix factorization

[L,U] = lu(X)
[L,U,P] = lu(X)
lu(X)

Description

The lu function expresses any square matrix X as the product of two essentially triangular matrices, one of them a permutation of a lower triangular matrix and the other an upper triangular matrix. The factorization is often called the LU, or sometimes the LR, factorization.

[L,U] = lu(X)

returns an upper triangular matrix in U and a psychologically lower triangular matrix (i.e., a product of lower triangular and permutation matrices) in L, so that X = L*U.

[L,U,P] = lu(X)

returns an upper triangular matrix in U, a lower triangular matrix in L, and a permutation matrix in P, so that L*U = P*X.

lu(X)

returns the output from the LINPACK routine ZGEFA.

Remarks

Most of the algorithms for computing LU factorization are variants of Gaussian elimination. The factorization is a key step in obtaining the inverse with inv and the determinant with det. It is also the basis for the linear equation solution or matrix division obtained with \ and /.

Arguments


`L`	A factor of `X`. Depending on the form of the function, `L` is either lower triangular, or else the product of a lower triangular matrix with a permutation matrix `P`.
`U`	An upper triangular matrix that is a factor of `X`.
`P`	The permutation matrix satisfying the equation `LU = PX`.

Examples

Start with

A =
    1    2    3
    4    5    6
    7    8    0

To see the LU factorization, call lu with two output arguments:

[L,U] = lu(A)
L =
    0.1429    1.0000         0
    0.5714    0.5000    1.0000
    1.0000         0         0
U =
    7.0000    8.0000    0.0000
         0    0.8571    3.0000
         0         0    4.5000

Notice that L is a permutation of a lower triangular matrix that has 1's on the permuted diagonal, and that U is upper triangular. To check that the factorization does its job, compute the product:

L*U

which returns the original A. Using three arguments on the left-hand side to get the permutation matrix as well

[L,U,P] = lu(A)

returns the same value of U, but L is reordered:

L =
    1.0000         0         0
    0.1429    1.0000         0
    0.5714    0.5000    1.0000
U =
    7.0000    8.0000         0
         0    0.8571    3.0000
         0         0    4.5000
P =
    0    0    1
    1    0    0
    0    1    0

To verify that L*U is a permuted version of A, compute L*U and subtract it from P*A:

P*A - L*U

The inverse of the example matrix, X = inv(A), is actually computed from the inverses of the triangular factors:

X = inv(U)*inv(L)

The determinant of the example matrix is

d = det(A)

which gives

d =
    27

It is computed from the determinants of the triangular factors:

d = det(L)*det(U)

The solution to Ax = b is obtained with matrix division:

x = A\b

The solution is actually computed by solving two triangular systems:

y = L\b, x = U\y

Algorithm

lu uses the subroutines ZGEDI and ZGEFA from LINPACK. For more information, see the LINPACK Users' Guide.