LU Decomposition

LU Factorization

In the lower triangular matrix all elements above the diagonal are zero, in the upper triangular matrix, all the elements below the diagonal are zero. For example, for a 3-by-3 matrix A, its LU decomposition looks like this:

${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}}={\begin{bmatrix}l_{11}&0&0\\l_{21}&l_{22}&0\\l_{31}&l_{32}&l_{33}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}}.}$

Without a proper ordering or permutations in the matrix, the factorization may fail to materialize. For example, it is easy to verify (by expanding the matrix multiplication) that ${\displaystyle a_{11}=l_{11}u_{11}}$. If ${\displaystyle a_{11}=0}$, then at least one of ${\displaystyle l_{11}}$ and ${\displaystyle u_{11}}$ has to be zero, which implies either L or U is singular. This is impossible if A is nonsingular. This is a procedural problem. It can be removed by simply reordering the rows of A so that the first element of the permuted matrix is nonzero. The same problem in subsequent factorization steps can be removed the same way; see the basic procedure below.

It turns out that a proper permutation in rows (or columns) is sufficient for the LU factorization. The LU factorization with Partial Pivoting refers often to the LU factorization with row permutations only,

${\displaystyle PA=LU,\,}$

where L and U are again lower and upper triangular matrices, and P is a permutation matrix which, when left-multiplied to A, reorders the rows of A. It turns out that all square matrices can be factorized in this form,^[3] and the factorization is numerically stable in practice.^[4] This makes LUP decomposition a useful technique in practice.

An LU factorization with full pivoting involves both row and column permutations,

${\displaystyle PAQ=LU,\,}$

where L, U and P are defined as before, and Q is a permutation matrix that reorders the columns of A.^[5]

An LDU decomposition is a decomposition of the form

${\displaystyle A=LDU,\,}$

where D is a diagonal matrix and L and U are unit triangular matrices, meaning that all the entries on the diagonals of L and U are one.

Above we required that A be a square matrix, but these decompositions can all be generalized to rectangular matrices as well. In that case, L and D are square matrices both of which have the same number of rows as A, and U has exactly the same dimensions as A. Upper triangular should be interpreted as having only zero entries below the main diagonal, which starts at the upper left corner.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

A = LU 를 지정할 때에,

U를 구하기 위해 A를 Gaussian Elimination을 수행한다.

결과가 되는 matrix가 U가 되고,

L의 경우 Lower triangle matrix가 되는데, 대각성분을 1로 지정해주고 나머지 성분을 연립방정식 계산을 통해 구한다.

이렇게 A를 LU로 분해하는 이유는,

대각행렬형태로 분해하면 Det 계산이 편리하며 역행렬을 구하는 데에 매우 수월하다.

이 LU_DECOMP라는 루틴을 사용하면 정방형 행렬 A에 대하여 LU 분해를 수행하여 얻어진 L, U 성분을 명확하게 얻을 수있다. 단, 유의할 점은 이 LU_DECOMP는 L, U를 따로 볼 수 있도록 결과를 산출해주는 역할만 수행한다. 만약 연립방정식의 해를 구하는 작업까지 염두에 둘 경우에는 여전히 LUDC, LUSOL을 사용하는 것이 맞다는 점만 염두에 두면 된다.

Reference :

http://blog.daum.net/swrush/327 (이상우 IDL 블로그)

https://en.wikipedia.org/wiki/LU_decomposition (Wikipedia)