lu

Purpose

LU factorization of a matrix.

Synopsis

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

Description

lu(X) 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. Most of the algorithms for computing it 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 /.

[L,U] = lu(X) stores 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) stores an upper triangular matrix in U, a lower triangular matrix in L, and a permutation matrix in P, so that L*U = P*X.

By itself, lu(X) returns the output from the LINPACK routine ZGEFA.

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 1s 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
Triangular factorization is also used by a specialized function, rcond. This quantity is produced by several of the LINPACK subroutines as an estimate of the reciprocal condition number of the input matrix.

Algorithm

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

See Also

\, /, det, inv, qr, rcond, rref

References

[1] J.J. Dongarra, J.R. Bunch, C.B. Moler, and G.W. Stewart, LINPACK
User's Guide, SIAM, Philadelphia, 1979.

(c) Copyright 1994 by The MathWorks, Inc.