Documentation |
LU-decomposition of a matrix
This functionality does not run in MATLAB.
linalg::factorLU(A)
linalg::factorLU(A) computes an LU-decomposition 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 (Doolittle-decomposition). 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 floating-point 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 LU-decomposition 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 LU-decomposition 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 LU-decomposition of the matrix:
A := matrix([[1, 2, -1], [0, 0, 3], [0, 2, -1]])
one row interchange is needed, and we therefore get a non-trivial 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 LU-decomposition 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 non-zero, 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]))
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 LU-decomposition:
Compute a LU-decomposition of A: A = L U.
Solve by forward substitution.
Solve by backward substitution.
The LU-decomposition of a matrix A is useful for solving several systems of linear equations with the same coefficient matrix A and several right-hand side vectors , because then step one of the algorithm above needs to be done only once.