LUdecomposition of a matrix
This functionality does not run in MATLAB.
linalg::factorLU(A
)
linalg::factorLU(A)
computes an LUdecomposition
of an m×n matrix A,
i.e., a decomposition of the A into
an m×m lower
triangular matrix L and
an m×n upper
triangular matrix U such
that P A = L U,
where P is
a permutation matrix.
The diagonal entries of the lower triangular matrix L are equal to one (Doolittledecomposition). The diagonal entries of U are the pivot elements used during the computation.
The matrices L and U are unique.
pivindex
is a list [ r_{1},
r_{2}, ...]
representing the row exchanges
of A in
the pivoting steps, i.e., B = P A = L U,
where b_{ij} = a_{ri, j}.
A floatingpoint approximation of the decomposition is computed
using numeric::factorLU
,
if the matrix A
is defined over the component ring Dom::Float
. In this case
it is recommended to call numeric::factorLU
directly
for a better efficiency.
The algorithm also works for singular A. In this case either L or U is singular.
L and U are nonsingular if and only if A is nonsingular.
The component ring of the matrix A
must be
a field, i.e., a domain of category Cat::Field
.
We compute an LUdecomposition of the real matrix:
A := Dom::Matrix(Dom::Real)( [[2, 3, 1], [1, 1, 1], [0, 1, 1]] )
[L, U, pivlist] := linalg::factorLU(A)
The lower triangular matrix L is
the first element und the upper triangular matrix U is
the second element of the list LU
. The product
of these two matrices is equal to the input matrix A
:
L * U
An LUdecomposition of the 3×2 matrix:
A := Dom::Matrix(Dom::Real)([[2, 3], [1, 2], [2, 3]])
gives a 3×3 lower triangular matrix and a 3×2 upper triangular matrix:
[L, U, pivlist] := linalg::factorLU(A)
L * U
To compute the LUdecomposition of the matrix:
A := matrix([[1, 2, 1], [0, 0, 3], [0, 2, 1]])
one row interchange is needed, and we therefore get a nontrivial permutation list:
[L, U, pivlist] := linalg::factorLU(A)
The corresponding permutation matrix is the following:
P := linalg::swapRow(matrix::identity(3), 3, 2)
Hence, we have a decomposition of A into the product of the three matrices , L and U as follows:
P^(1) * L * U
You may compute an LUdecomposition of a matrix with symbolic components, such as:
delete a, b, c, d: A := matrix([[a, b], [c, d]])
The diagonal entries of the matrix U are the pivot elements used during the computation. They must be nonzero, if the inverse of U is needed:
[L, U, pivlist] := linalg::factorLU(A)
For example, if we use this decomposition to solve the linear system for arbitrary vectors , then the following result is only correct for a ≠ 0 and :
delete b1, b2: linalg::matlinsolveLU(L, U, matrix([b1, b2]))

A matrix of a domain of category 
List [L, U, pivindex]
with the two matrices L and U of
the domain Dom::Matrix
(R)
and
a list pivindex
of positive integers. R
is
the component ring of A
.
The following algorithm for solving the system with a nonsingular matrix A uses LUdecomposition:
Compute a LUdecomposition of A: A = L U.
Solve by forward substitution.
Solve by backward substitution.
The LUdecomposition of a matrix A is useful for solving several systems of linear equations with the same coefficient matrix A and several righthand side vectors , because then step one of the algorithm above needs to be done only once.