PLU 분해
정의 1 2
순열 행렬 $P^{T}$ 와 가역행렬 $A \in \mathbb{R}^{n \times n}$ 에 대해, 그들의 행렬곱 $P^{T} A$ 의 LU 분해를 $A$ 의 PLU 분해permutation LU decomposition라 한다. $P$ 는 순열 행렬이므로 직교행렬 즉 $P^{-1} = P^{T}$ 이고, 따라서 다음과 같이 나타낼 수 있다. $$ P^{T} A = LU \iff A = PLU $$
설명
LU 분해의 알고리즘: $(a_{ij}) \in \mathbb{R}^{n \times n}$ 가 가역행렬이라고 하자.
Step 1. $k = 1$
$u_{1j} = a_{1j}$ 을 대입하고 $\displaystyle l_{i1} = {{1} \over {u_{11}}} a_{i1}$ 을 계산한다.
Step 2. $k = 2, 3, \cdots , n-1$
- Step 2-1. 다음을 계산한다. $$ u_{kk} = a_{kk} - \sum_{s = 1}^{k-1} l_{ks} u_{sk} $$
- Step 2-2. $j = k+1 , k+2 , \cdots , n-1$ 에 대해 다음을 계산한다. $$ u_{kj} = a_{kj} - \sum_{s = 1}^{k-1} l_{ks} u_{sj} $$
- Step 2-3. $i = k+1 , k+2 , \cdots , n-1$ 에 대해 다음을 계산한다. $$ l_{ik} = {{ 1 } \over {u_{kk} }} \left\{ a_{ik} - \sum_{s = 1}^{k-1} l_{is} u_{sk} \right\} $$
Step 3. $k = n$ 에 대해 다음을 계산한다. $$ u_{nn} = a_{nn} - \sum_{s = 1}^{n-1} l_{ns} u_{sn} $$
행렬의 LU 분해를 위해서는 위와 같이 $u_{11} = a_{11}$ 혹은 $u_{kk}$ 의 역수를 취할 수 있어야하나, 단순히 $$ A = \begin{bmatrix} 0 & 3 \\ 2 & 1 \end{bmatrix} $$ 과 같은 행렬조차 이 알고리즘을 적용할 수 없다. 이에 따라 LU 분해를 수행할 수 있게끔 어떤 순열 행렬 $P^{T}$ 를 곱해주고, 아예 $A$ 를 $PLU$ 로 나타내는 것을 PLU 분해라고 부른다. 물론 좌냐 우냐, 행이냐 열이냐가 중요한 것은 아니기 때문에 $$ A P^{T} = LU \iff A = LUP $$ 이라 두고 LUP 분해라 읽어도 딱히 상관 없다.