LU分解計算機

LU分解とは何か？

LU分解 (LU Decomposition) は、線形代数学において行列を2つの特定の種類の行列の積として表現する手法です。具体的には、正方行列 $A$ を、下三角行列 (Lower Triangular Matrix, $L$) と 上三角行列 (Upper Triangular Matrix, $U$) の積 $A = LU$ に分解します。

この分解により、連立一次方程式の解法、逆行列の計算、行列式の計算などが効率的に行えるようになります。特にコンピュータによる数値計算では、ガウスの消去法を効率化した形として広く利用されています。

構成要素

• 下三角行列 ($L$): 対角成分より上の要素がすべて0である行列です。通常、対角成分をすべて1とする（Doolittle法）か、あるいは$U$の対角成分を1とする（Crout法）などの規約があります。この計算機では、一般的に用いられるDoolittle法（$L$の対角成分がすべて1）を採用しています。
• 上三角行列 ($U$): 対角成分より下の要素がすべて0である行列です。

LU分解の計算手順 (Doolittle法)

2x2行列 $A = \\begin{pmatrix} a_{11} & a_{12} \\\\ a_{21} & a_{22} \\end{pmatrix}$ の場合を例にとります。これを以下の形に分解します。

$ \\begin{pmatrix} a_{11} & a_{12} \\\\ a_{21} & a_{22} \\end{pmatrix} = \\begin{pmatrix} 1 & 0 \\\\ l_{21} & 1 \\end{pmatrix} \\begin{pmatrix} u_{11} & u_{12} \\\\ 0 & u_{22} \\end{pmatrix} $

この行列積を展開すると、以下の関係式が得られます。

1. 第1行を比較:
   $1 \\cdot u_{11} = a_{11} \\Rightarrow u_{11} = a_{11}$
   $1 \\cdot u_{12} = a_{12} \\Rightarrow u_{12} = a_{12}$
2. 第2行を比較:
   $l_{21} \\cdot u_{11} = a_{21} \\Rightarrow l_{21} = a_{21} / u_{11}$
   $l_{21} \\cdot u_{12} + 1 \\cdot u_{22} = a_{22} \\Rightarrow u_{22} = a_{22} - l_{21}u_{12}$

これにより、未知数 $l_{21}, u_{11}, u_{12}, u_{22}$ がすべて求まります。3x3以上の行列でも同様に、上から下へ、左から右へと順次未知数を決定していくことができます。

LU分解の存在条件

すべての正方行列がLU分解できるわけではありません。分解の過程でピボット（対角成分）が0になる場合、単純なLU分解は行えません。その場合、行の入れ替えを行うPLU分解（$P$は置換行列）が必要になります。この計算機では、主小行列式が0にならない（ピボット交換なしで分解可能な）ケースを扱います。

LU分解の主な用途

よくある質問 (FAQ)