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}$ が可逆行列であるとする。
ステップ1. $k = 1$
$u_{1j} = a_{1j}$ を代入して $\displaystyle l_{i1} = {{1} \over {u_{11}}} a_{i1}$ を計算する。
ステップ2. $k = 2, 3, \cdots , n-1$
- ステップ2-1. 次を計算する。 $$ u_{kk} = a_{kk} - \sum_{s = 1}^{k-1} l_{ks} u_{sk} $$
- ステップ2-2. $j = k+1 , k+2 , \cdots , n-1$ に対して次を計算する。 $$ u_{kj} = a_{kj} - \sum_{s = 1}^{k-1} l_{ks} u_{sj} $$
- ステップ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\} $$
ステップ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} $$ のような行列ですらこのアルゴリズムを適用できない。そのため、何らかの順列行列 $P^{T}$ を掛けて、$A$ を丸ごと $PLU$ として表すことをPLU分解と呼ぶ。もちろん左か右か、行か列かは重要ではないため $$ A P^{T} = LU \iff A = LUP $$ としても、LUP分解と読んでも全く問題ない。