linalg::factorLU
--
LU-decomposition of a matrixlinalg::factorLU
(A)
computes an
LU-decomposition of an m x n matrix A, i.e., a
decomposition of the A into an m x m lower
triangular matrix L and an n x m upper triangular
matrix U such that P*A = L*U, where P
is a permutation matrix.
linalg::factorLU(A)
A |
- | a matrix of a domain of category Cat::Matrix |
a 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
.
linalg::factorQR
,
linalg::factorCholesky
,
linalg::inverseLU
,
linalg::matlinsolveLU
,
lllint
, numeric::factorLU
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[i,j] =
A[r[i],j].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.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]] )
+- -+ | 2, -3, -1 | | | | 1, 1, -1 | | | | 0, 1, -1 | +- -+
>> [L, U, pivlist] := linalg::factorLU(A)
-- +- -+ +- -+ -- | | 1, 0, 0 | | 2, -3, -1 | | | | | | | | | | 1/2, 1, 0 |, | 0, 5/2, -1/2 |, [1, 2, 3] | | | | | | | | | 0, 2/5, 1 | | 0, 0, -4/5 | | -- +- -+ +- -+ --
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
+- -+ | 2, -3, -1 | | | | 1, 1, -1 | | | | 0, 1, -1 | +- -+
An LU-decomposition of the 3 x 2 matrix:
>> A := Dom::Matrix(Dom::Real)([[2, -3], [1, 2], [2, 3]])
+- -+ | 2, -3 | | | | 1, 2 | | | | 2, 3 | +- -+
gives a 3 x 3 lower triangular matrix and a 2 x 3 upper triangular matrix:
>> [L, U, pivlist] := linalg::factorLU(A)
-- +- -+ +- -+ -- | | 1, 0, 0 | | 2, -3 | | | | | | | | | | 1/2, 1, 0 |, | 0, 7/2 |, [1, 2, 3] | | | | | | | | | 1, 12/7, 1 | | 0, 0 | | -- +- -+ +- -+ --
>> L * U
+- -+ | 2, -3 | | | | 1, 2 | | | | 2, 3 | +- -+
To compute the LU-decomposition of the matrix:
>> A := matrix([[1, 2, -1], [0, 0, 3], [0, 2, -1]])
+- -+ | 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)
-- +- -+ +- -+ -- | | 1, 0, 0 | | 1, 2, -1 | | | | | | | | | | 0, 1, 0 |, | 0, 2, -1 |, [1, 3, 2] | | | | | | | | | 0, 0, 1 | | 0, 0, 3 | | -- +- -+ +- -+ --
The corresponding permutation matrix is the following:
>> P := linalg::swapRow(matrix::identity(3), 3, 2)
+- -+ | 1, 0, 0 | | | | 0, 0, 1 | | | | 0, 1, 0 | +- -+
Hence, we have a decomposition of A into the product of the three matrices P^(-1), L and U as follows:
>> P^(-1) * L * U
+- -+ | 1, 2, -1 | | | | 0, 0, 3 | | | | 0, 2, -1 | +- -+
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]])
+- -+ | 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)
-- +- -+ +- -+ -- | | 1, 0 | | a, b | | | | | | | | | | c |, | b c |, [1, 2] | | | -, 1 | | 0, d - --- | | | | a | | a | | -- +- -+ +- -+ --
For example, if we use this decomposition to solve the linear system A*x=b for arbitrary vectors b=(b[1],b[2])^T, then the following result is only correct for a <> 0 and d-(b*c)/d <> 0:
>> delete b1, b2: linalg::matlinsolveLU(L, U, matrix([b1, b2]))
+- -+ | / c b1 \ | | b | b2 - ---- | | | \ a / | | b1 - --------------- | | b c | | d - --- | | a | | -------------------- | | a | | | | c b1 | | b2 - ---- | | a | | --------- | | b c | | d - --- | | a | +- -+