📂行列代数

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分解と読んでも全く問題ない。