linalg::factorLU

LU-decomposition of a matrix

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

linalg::factorLU(A)

Description

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 PA = LU, 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 [ r1, r2, ...] representing the row exchanges of A in the pivoting steps, i.e., B = PA = LU, where bij = ari, 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.

Examples

Example 1

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

Example 2

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

Example 3

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

Example 4

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]))

Parameters

A

A matrix of a domain of category Cat::Matrix

Return Values

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.

Algorithms

The following algorithm for solving the system with a nonsingular matrix A uses LU-decomposition:

  1. Compute a LU-decomposition of A: A = LU.

  2. Solve by forward substitution.

  3. 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.

Was this topic helpful?