LU分解

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "LU分解" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2013年4月)

数学における行列のLU分解（エルユーぶんかい、英: LU decomposition）とは、正方行列 A を下三角行列 L と上三角行列 U の積に分解すること。すなわち A = LU が成立するような L と U を求めることをいう。正方行列 A のLU分解が存在する必要十分条件はすべての首座小行列式が 0 でないことである。また L の対角成分をすべて 1 とすれば分解はただ一通りに定まる。文献によってはLR分解とも呼ばれる（それはAを左三角(left triangular)と右三角(right triangular)の行列の積に分解するということにちなむ）。

以下、n 次正方行列の場合で説明する。基本的にはA = LU の各成分について書き下した n² 個の式を解くことにより、行列 L , U を求めるのだが、このままでは未知の係数の個数（n (n + 1) 個）が式の個数（n²個）より多いので解けない。これを解くための解法には ドゥーリトル法 と クラウト法 の2つがある。

• ドゥーリトル法では、行列 L の対角成分の全てを 1 とおき、(1, 1) 成分 , (2, 1) 成分 , (3, 1) 成分 , ... , (1, 2) 成分, (2, 2) 成分, ... の順に n² 個の式を解く。
• クラウト法では、行列 U の対角成分の全てを 1 とおき、(1, 1) 成分 , (1, 2) 成分 , (1, 3) 成分 , ... , (2, 1) 成分, (2, 2) 成分, ... の順に n² 個の式を解く。

ドゥーリトル法による2次行列のLU分解を行う。与えられた正方行列A の成分をa_ij とする。

1. 下三角行列 L の対角成分を全て 1 とおき、残りの成分、(1, 2)を0、(2, 1)を変数l₂₁ とおく。

   ${\displaystyle L={\begin{bmatrix}1&0\\l_{21}&1\end{bmatrix}}}$

2. 上三角行列 U の対角成分と対角成分より上の成分を変数におく。

   ${\displaystyle U={\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}}$

3. A=LU の両辺を係数比較する。

   ${\displaystyle {\begin{aligned}a_{11}&=u_{11}\\a_{12}&=u_{12}\\a_{21}&=l_{21}u_{11}\\a_{22}&=l_{21}u_{12}+u_{22}\end{aligned}}}$

4. 上式を上から順に解くことでL , U が求められる。

   ${\displaystyle {\begin{aligned}L&={\begin{bmatrix}1&0\\{\frac {a_{21}}{a_{11}}}&1\end{bmatrix}}\\U&={\begin{bmatrix}a_{11}&a_{12}\\0&a_{22}-{\frac {a_{21}a_{12}}{a_{11}}}\end{bmatrix}}\end{aligned}}}$

連立1次方程式

${\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}}$

の解き方に、行列 A を LU分解する方法がある。L , U は下三角行列、上三角行列であるため、逆行列を求めることなく計算することが可能である。このため、同じA に対しb だけを変えていくつも連立方程式を解く場合、LU分解は有用である^[1]。

与えられた方程式

${\displaystyle A{\boldsymbol {x}}=LU{\boldsymbol {x}}={\boldsymbol {b}}}$

に対し、変数y を

${\displaystyle U{\boldsymbol {x}}={\boldsymbol {y}}}$

とおき、これを上式に代入する。

${\displaystyle L{\boldsymbol {y}}={\boldsymbol {b}}}$

から変数y を求める^{[注釈 1]}。求めた解y をUx = y の右辺に代入し、解 x を求めることができる^{[注釈 2]}。

Ly = bはガウスの消去法の前進消去、Ux = yは後退代入に対応する。

行列 A を LU 分解すると、

${\displaystyle A^{-1}=U^{-1}L^{-1}}$

により逆行列A^-1 を求められる。

また、

${\displaystyle LU{\boldsymbol {x_{i}}}={\boldsymbol {e_{i}}}\quad (i=1,2,\dots ,n)}$

（e_i は単位行列I の第i 列）

の解x_i を並べた行列${\displaystyle X=[{\boldsymbol {x_{1}}},{\boldsymbol {x_{2}}},\dots ,{\boldsymbol {x_{n}}}]}$は AX = I を満たすので、このようにしても逆行列A^-1 を求めることができる。

行列 A を LU 分解できれば、その行列式は簡単に求めることができる。なぜならば、行列 L および U は三角行列であることから、それらの行列式 |L | , |U | は対角成分の積で表され、|A | は、

${\displaystyle |A|=|L||U|}$

と計算できるからである。

LDU 分解

下三角行列 L と対角行列 D と上三角行列 U の積に分解する。

${\displaystyle A=LDU}$

LUP 分解

下三角行列 L と上三角行列 U と置換行列 P の積に分解する。

${\displaystyle PA=LU}$

• en:Crout matrix decomposition

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ