📂행렬대수

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 분해라 읽어도 딱히 상관 없다.