LU分解

数値解析と線形代数では、下三角行列と上三角行列の積として行列を因数分解する下上三角行列分解（LU分解）が行われます（行列の乗算と行列の分解を参照）。この積には置換行列が含まれる場合もあります。LU分解はガウス消去法の行列形式と見なすことができます。コンピュータは通常、LU分解を使用して正方線形方程式系を解き、行列の逆行列を計算したり、行列式を計算したりする際の重要なステップでもあります。また、 LR分解（左三角行列と右三角行列に因数分解する）と呼ばれることもあります。一般行列に対するLU分解アルゴリズムは、1938年にポーランドの天文学者タデウシュ・バナヒエヴィチによって導入されました。 ^[¹^]

定義

$A を$ 正方行列とする。LU分解とは、 $A$ を下三角行列 $L$ と上三角行列 $U$ の 2 つの因子の積として表現し、 $A = LU$ とすることである。ゼロ除算や丸め誤差の無制限な増加を防ぐために、 $A$ を事前に並べ替えなければ分解が不可能な場合がある。そのため、代替表現は $PAQ$ $=$ $LU$ となり、形式表記では、置換行列因子 $P$ と $Q は$ $A$ の行 (または列) の置換を示す。理論的には、 $P$ (または $Q ) は$ 単位行列の行 (または列) の置換によって得られるが、実際には対応する置換が $A$ の行 (または列) に直接適用される。

$n$ 辺の行列 $A$ は $n^{2}$ 2 つの三角行列を組み合わせた場合、係数は $n (n + 1)$ 個となり、したがって行列 $LUの$ $n$ 個の係数は独立ではありません。慣例として、 $L は$ 単三角行列、つまり $n$ 個の主対角要素すべてが 1 となるように設定されています。ただし、代わりに $U行列を単三角行列に設定すると、行列積の$ 転置後の手順は同じになります(行列転置の性質を参照)。 $B=A^{\textsf {T}}=(LU)^{\textsf {T}}=U^{\textsf {T}}L^{\textsf {T}}.$ 転置後、 $UT は$ $B$ の下三角行列、 $LT は$ 上三角行列の単位三角因子となります。これはまた、転置行列の行に対する操作（ピボット操作など）が列に対する操作と等価であることを示しており、一般に行アルゴリズムと列アルゴリズムの選択に利点はありません。

下三角行列では、主対角線より上の要素はすべてゼロであり、上三角行列では、主対角線より下の要素はすべてゼロです。例えば、3×3行列 $A$ の場合、そのLU分解は次のようになります。 ${\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0&0\\\ell _{21}&\ell _{22}&0\\\ell _{31}&\ell _{32}&\ell _{33}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}}.$

行列に適切な順序や順列がない場合、因数分解が実現しない可能性があります。たとえば、（行列の乗算を展開することで）簡単に確認できます。 ${\textstyle a_{11}=\ell _{11}u_{11}}$ 。もし ${\textstyle a_{11}=0}$ そうすれば、少なくとも以下のいずれか $\ell _{11}}$ そして $u_11$ はゼロでなければならず、これは $L$ または $Uが$ 特異行列であることを意味します。A $が$ 非特異行列（可逆行列）である場合、これは不可能です。演算の観点から、 $A$ の最初の列の残りの要素をゼロにする/消去するには、次の除算が必要です。 ${\textstyle a_{21},a_{31}}$ と ${\textstyle a_{11}}$ $0 の場合は不可能です。これは手続き上の問題です。行列A$ の行を並べ替えて、置換行列の最初の要素がゼロ以外になるようにすることで、この問題は解消できます。後続の因数分解ステップにおける同じ問題も同様の方法で解消できます。丸め誤差や小さな数による除算に対する数値的安定性を確保するには、選択することが重要です。 ${\textstyle a_{11}}$ 絶対値が大きい（ピボット操作を参照）。

LU を再帰的に実行

上記の3 × 3行列の例では、関連する行列の最上行と最左端の列の行列積が $LU$ の成功に特別な役割を果たすことが示されています。行列の連続バージョンを次のようにマークします。 $(0),\;(1),\dots$ そして、行列積を書いてみましょう $A\equiv A^{(0)}=L^{(0)}U^{(0)}$ これらの行と列が他の行と列から分離されるようにします。その際、ブロック行列表記を使用します。例えば、 $a\equiv a_{11}$ は普通の数です。 ${\bf {w}}^{\textsf {T}}\equiv (a_{12},a_{13})^{\textsf {T}}$ は行ベクトルであり、 ${\bf {v}}=(a_{21},a_{31})$ は列ベクトルであり、 $A'$ は行列のサブ行列です $A^{(0)}$ 一番上の行と一番左の列を除いて。そうすれば置き換えることができます $A^{(0)}=L^{(0)}U^{(0)}$ ブロック行列積を用いる。つまり、行列ブロックは、通常の数値のように、つまり行×列のように乗算できることがわかる。ただし、この場合、ブロックの成分は部分行列であり、場合によってはスカラーまたはベクトルに縮小される。したがって $u{\bf {l}}$ は、から得られたベクトルを表します。 ${\bf {l}}$ 各成分に数値を乗じた後 $u$ 、 ${\bf {lu}}^{\textsf {T}}$ ベクトルの外積 ${\bf {l,u}}$ つまり、最初の列が $u_{12}{\bf {l}}$ 次は $u_{13}{\bf {l}}$ そして、すべてのコンポーネントについて同様です。 ${\bf {u}}$ そして $L^{(1)}U^{(1)}$ は、部分行列の積です。 $L^{(0)},\;U^{(0)}$ ${\begin{aligned}\left({\begin{array}{c|c}a&{\bf {w}}^{\textsf {T}}\\\hline \\[-0.5em]{\bf {v}}&\quad A'\quad \\[-0.5em]\\\end{array}}\right)&=\left({\begin{array}{c|c}{\rm {1}}&{\bf {0}}^{\textsf {T}}\\\hline \\[-0.5em]{\bf {l}}&\quad L^{(1)}\quad \\[-0.5em]\\\end{array}}\right)\;\left({\begin{array}{c|c}u&{\bf {u}}^{\textsf {T}}\\\hline \\[-0.5em]{\bf {0}}&\quad U^{(1)}\\[-0.5em]\\\end{array}}\right)\\&=\left({\begin{array}{c|c}u&{\bf {u}}^{\textsf {T}}\\\hline \\[-0.5em]u{\bf {l}}&\quad {\bf {lu}}^{\textsf {T}}+L^{(1)}U^{(1)}\\[-0.5em]\\\end{array}}\right)\end{aligned}}$

最初と最後の行列の等価性から、最終的な $u=a$ 、 ${\bf {u=w}}$ 、 ${\bf {l}}={(1/a)}{\bf {v}}$ 行列 $A'$ 更新/置き換えられる $A^{(1)}\equiv L^{(1)}U^{(1)}=$ $A'-{\bf {lu}}^{\textsf {T}}$ ここで重要な観察が続きます。 $A^{(1)}$ 我々がしたのと同じように $A^{(0)}$ 繰り返し。寸法が $A$ $n$ × $n$ であり、 $n - 1 回$ のステップの後、すべての列が ${\bf {v}}$ 三角形行列の副対角部分を形成する $L$ そしてすべてのピボット $a$ 行と組み合わせる $\displaystyle {\bf {w}}^{\textsf {T}}}$ 上三角行列を形成する $U$ 必要に応じて。上記の例では $n = 3なので$ 、 2 つのステップだけで十分です。

上記の手順は、どのステップにおいても上部の対角ピボット要素が $a$ 連続する部分行列の要素はゼロになることがあります。これを避けるために、列または行を入れ替えることで、 $a$ はゼロ以外になります。このような順列を含む手順は、 LUP（ピボット分解）と呼ばれます。

列の順列は行列の積に対応する $AQ^{(0)}$ どこ $Q^{(0)}$ は置換行列、すなわち単位行列である。 $I$ 同じ列の順列の後。すべてのステップの後、このような LUP 分解が適用されます。 $AQ^{(0)}\cdots Q^{(n-1)}\equiv AQ=LU$ 現在の計算スキームとCormenら^{[ 2 ]}の類似のスキームは、再帰アルゴリズムの例である。これらはLU分解の2つの一般的な特性を示している。

各段階で方向転換する必要性、そして
$L$ 行列と $U$ 行列の最終値は、1ステップにつき1行または1列ずつ、段階的に取得されます。

$再帰アルゴリズムは代数演算の面ではそれほどコストがかからないものの、各ステップでA$ のほとんどの要素を更新して保存する必要があるため、実用上の欠点がある。計算順序を組み替えることで、中間値の保存を不要にできることがわかるだろう。

部分ピボット選択によるLU分解

$既知の異常なケースを除き、行（または列）の適切な順列によって絶対最大ピボットa 11$ を選択することで、数値的に安定した LU 分解が可能になることがわかります。これは「部分ピボット付き LU 分解」（LUP）と呼ばれます。 $PA=LU,\quad (AQ=LU),$ ここで、 $L$ と $U$ は再び下三角行列と上三角行列であり、 $P$ と $Q は$ 対応する置換行列であり、これらを $A$ にそれぞれ左から右に掛けると、 $A$ の行と列が入れ替わります。すべての正方行列はこの形式で因数分解できることがわかっています^{[ 3 ]}。また、因数分解は実際には数値的に安定しています^{[ 4 ]} 。このため、LUP 分解は実際には有用な手法となります。

「ルークピボット」と呼ばれる変種では、各ステップでチェス盤上のルークの動きにならい、列、行、列と順に最大要素を探し、行と列の両方でピボットとなる最大要素に到達するまで探索を続けます。ランダムな要素からなる大きな行列の場合、各ステップでの演算コストは、完全ピボットの場合の行列の正方形とは異なり、部分ピボットと同様に行列の辺の長さに比例することが証明できます。

LU分解（全ピボット選択付き）

「フルピボット付きLU分解」では、行と列の両方の順列を用いて、部分行列全体における絶対最大要素を見つけます。 $PAQ=LU,$ ここで、 $L$ 、 $U$ 、 $P$ は前述のように定義され、 $Qは$ $A$ の列を並べ替える置換行列である。^{[ 5 ]}

下対角上（LDU）分解

「下対角線上分解」（LDU）とは、次の形式の分解である。 $A=LDU,$ ここで $、Dは$ 対角行列であり、 $L$ と $Uは$ 単位三角行列である。つまり、 $L$ と $U$ の対角成分はすべて1である。

長方形行列

$上記ではA が$ 正方行列であることを要求しましたが、これらの分解はすべて長方形行列にも一般化できます。 ^{[ 6 ]}この場合、 $L$ と $D$ はどちらも $A$ と同じ行数を持つ正方行列であり、 $U は$ $A$ とまったく同じ次元を持ちます。「上三角」とは、左上隅から始まる主対角線より下の要素がすべてゼロであることを意味します。同様に、 $U$ のより正確な用語は、行列 $Aの$ 行階段形であるということです。

例

次の2×2行列を因数分解します。 ${\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0\\\ell _{21}&\ell _{22}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}.$

この単純な行列のLU分解を求める一つの方法は、線形方程式を目視で解くことです。行列の乗算を展開すると次のようになります。 $\left\{{\begin{alignedat}{4}\ell _{11}\cdot u_{11}&&\;+\;&&0\cdot 0&&\;=\;&&4\\\ell _{11}\cdot u_{12}&&\;+\;&&0\cdot u_{22}&&\;=\;&&3\\\ell _{21}\cdot u_{11}&&\;+\;&&\ell _{22}\cdot 0&&\;=\;&&6\\\ell _{21}\cdot u_{12}&&\;+\;&&\ell _{22}\cdot u_{22}&&\;=\;&&3\end{alignedat}}\right.$

この連立方程式は不確定です。この場合、 $L 行列$ と $U$ 行列の任意の 2 つの非ゼロ要素は解のパラメータであり、任意の非ゼロ値に設定できます。したがって、一意の LU 分解を見つけるには、 $L 行列$ と $U$ 行列に何らかの制約を設ける必要があります。たとえば、下三角行列 $L を$ 単位三角行列にすることで、主対角のすべての要素を 1 に設定できます。すると、連立方程式は次の解を持ちます。 ${\begin{aligned}\ell _{11}&=\ell _{22}=1\\\ell _{21}&=1.5\\u_{11}&=4\\u_{12}&=3\\u_{22}&=-1.5\end{aligned}}$

これらの値を上記のLU分解に代入すると、 ${\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}1&0\\1.5&1\end{bmatrix}}{\begin{bmatrix}4&3\\0&-1.5\end{bmatrix}}.$

存在と独自性

正方行列

任意の正方行列 $A は$ LUP および PLU 分解を許容します。^{[ 3 ]} $Aが$ 可逆行列である場合、すべての主小行列式がゼロでない場合に限り、 LU (または LDU) 分解を許容します^[⁷^]^[⁸^] (例えば $\left[{\begin{smallmatrix}0&1\\1&0\end{smallmatrix}}\right]$ LU分解やLDU分解は許容しない）。A $が$ ランク $kの$ 特異行列である場合、最初の $k$ 個の主小行列式がゼロでないならばLU分解を許容するが、その逆は真ではない。^[⁹^]

正方行列で可逆行列が LDU 分解 ( $L$ と $Uのすべての対角要素が$ $1$ に等しい) を持つ場合、分解は一意です。^{[ 8 ]} $この場合、 L$ または $U$ のいずれかの対角要素が 1 で構成されていることを要求すれば、LU 分解も一意になります。

一般に、任意の正方行列 $A n \times n は、$ 以下のいずれかを持つ可能性があります。

（前述のとおり）一意のLU分解。
最初の $(n - 1)$ 列のいずれかが線形従属である場合、無限に多くの LU 分解が存在する。
最初の $(n - 1)$ 列が線形独立であり、かつ少なくとも 1 つの主小行列式がゼロである場合、LU 分解は行いません。

$ケース3では、対角成分a ijを$ $a ij \pm ε$ に変更することで、主小行列式がゼロになるのを回避し、LU分解を近似することができる。 ^{[ 10 ]}

対称正定値行列

$A$ が対称行列（ $A$ が複素数の場合はエルミート行列）の正定値行列である場合、 $Uが$ $L$ の共役転置行列となるように配置することができます。つまり、 $Aを$ 次のように書くことができます。 $A=LL^{*}\,.$

この分解はコレスキー分解と呼ばれます。行列 $A$ が正定値行列であれば、コレスキー分解は存在し、一意です。さらに、コレスキー分解の計算は、他のLU分解の計算よりも効率的で、数値的にも安定しています。

一般行列

任意の体上の（必ずしも可逆ではない）行列に対して、LU分解を持つための正確な必要十分条件が知られています。これらの条件は、特定のサブ行列のランクで表されます。LU分解を得るためのガウス消去アルゴリズムも、この最も一般的なケースに拡張されています。^{[ 11 ]}

アルゴリズム

閉じた式

LDU分解が存在し、かつ一意である場合、元の行列 $Aの特定$ $のサブ行列の行列式の比を用いて$ $、$ $L$ 、 $D$ 、 $U$ の要素を表す閉じた（明示的な）式が存在する。^[¹²^]特に、 $D1$ $=$ $A1,1であり、$ $i$ $= 2, ...,$ $n$ に対して、 $Di$ $は$ $i$ 番目の主サブ行列と $($ $i$ $-1)$ 番目の主サブ行列の比である。行列式の計算は計算コストが高いため、この明示的な式は実際には使用されない。

ガウス消去法を用いる

以下のアルゴリズムは、基本的にガウス消去法の修正版です。このアルゴリズムを使用してLU分解を計算するには、低次の項を無視して、2/3 n 3回の浮動小数点演算が必要です。部分 $ピボットでは 2 次項のみ$ が $追加$ されますが、これは完全ピボットでは当てはまりません。^{[ 13 ]}

一般化された説明

表記法

$N$ × $N$ 行列が与えられた場合 $A=(a_{i,j})_{1\leq i,j\leq N}$ 、定義する $A^{(0)}$ $は、行列A$ の元の未変更バージョンです。行列 $A$ の括弧付き上付き文字 (例: $(0)$ )は、行列のバージョンです。行列 $A$ $($ $n$ $)$ $は、最初のn列についてガウス消去法によって$ 主対角線より下の要素が既に 0 に消去された $A$ 行列です。

以下は、表記法を覚えるのに役立つ行列です（各 $* は$ 行列内の任意の実数を表します）。

$A^{(n-1)}={\begin{pmatrix}*&&&\cdots &&&*\\0&\ddots &&&&\\&\ddots &*&&&\\\vdots &&0&a_{n,n}^{(n-1)}&&&\vdots \\&&\vdots &a_{i,n}^{(n-1)}&*\\&&&\vdots &\vdots &\ddots \\0&\cdots &0&a_{i,n}^{(n-1)}&*&\cdots &*\end{pmatrix}}$

手順

この過程で、行操作を用いて行列 $A$ を徐々に変更し、主対角線より下の要素がすべてゼロになる行列 $Uにします。この過程で、$ $PA$ $=$ $LU$ となるような2 つの別々の行列 $P$ と $L$ を同時に作成します。

最終的な置換行列 $Pは、行列$ $A$ と同じ行がすべて同じ順序で入れ替わった単位行列であり、行列 $U$ に変換されるときに同じ行が入れ替わっているものと定義します。行列 $A (n -1)$ $の場合、まず行を入れ替えて、 n$ 番目の列に必要な条件を満たすようにします。たとえば、行を入れ替えて部分的なピボット操作を実行したり、主対角線上のピボット要素 $a n,n を$ ゼロ以外の値に設定してガウス消去を完了できるようにしたりできます。

行列 $A (n -1)$ に対して、以下のすべての要素を設定したい。 $a_{n,n}^{(n-1)}$ ゼロに（ $a_{n,n}^{(n-1)}$ $は主対角線のn$ 列目の要素です。以下では各要素を次のように表記します。 $a_{n,n}^{(n-1)}$ として $a_{i,n}^{(n-1)}$ （ここで $i = n +1, ... , N$ ）。設定するには $a_{i,n}^{(n-1)}$ ゼロにするために、各行 $iに対して$ $行 i = 行 i - (ℓ i,n)\cdot 行 n$ を設定します。この操作では、 ${\textstyle \ell _{i,n}:={a_{i,n}^{(n-1)}}/{a_{n,n}^{(n-1)}}}$ $最初のN - 1$ 列に対して行操作を実行すると、上三角行列 $A (N -1 )$ が得られ、これは $U$ で表されます。

また、以下の式を用いて、以前に計算した $ℓ$ $i,n$ の値を直接入力することで、 $L$ と表記される下三角行列を作成することもできます。

$L={\begin{pmatrix}1&0&\cdots &0\\\ell _{2,1}&\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &0\\\ell _{N,1}&\cdots &\ell _{N,N-1}&1\end{pmatrix}}$

例

行列が与えられた場合 $A={\begin{pmatrix}0&5&{\frac {22}{3}}\\4&2&1\\2&7&9\\\end{pmatrix}},$ 部分ピボット操作を実行することを選択し、最初の行と2番目の行を交換することで、行列 $A$ と行列 $P$ の最初の反復がそれぞれ次のようになります。 $A^{(0)}={\begin{pmatrix}4&2&1\\0&5&{\frac {22}{3}}\\2&7&9\\\end{pmatrix}},\quad P^{(0)}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\\\end{pmatrix}}.$ 行を入れ替えたら、次の操作を実行することで、最初の列の主対角線より下の要素を削除できます。 ${\begin{alignedat}{0}row_{2}=row_{2}-(\ell _{2,1})\cdot row_{1}\\row_{3}=row_{3}-(\ell _{3,1})\cdot row_{1}\end{alignedat}}$ そのため、 ${\begin{alignedat}{0}\ell _{2,1}={\frac {0}{4}}=0\\\ell _{3,1}={\frac {2}{4}}=0.5\end{alignedat}}$ これらの行を差し引くと、 $A (1)$ から行列が導出されます。 $A^{(1)}={\begin{pmatrix}4&2&1\\0&5&{\frac {22}{3}}\\0&6&8.5\\\end{pmatrix}}.$

部分ピボット操作を実行するため、導出された行列の2行目と3行目をそれぞれ交換し、現在の $P$ 行列のバージョンを取得して、 $A^{(1)}={\begin{pmatrix}4&2&1\\0&6&8.5\\0&5&{\frac {22}{3}}\\\end{pmatrix}},\quad P^{(1)}={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}.$ $次に、行 3 = 行 3 - (ℓ 3,2)\cdot 行 2$ を実行することにより、2 列目の主対角線より下の要素を削除します。ここで、 $ℓ 3,2 = ⁠ 5 / 6 ⁠$ $です。この行減算後の現在のA$ の反復では主対角線より下に非ゼロの要素が存在しないため、この行減算によって最終的な $A行列 ($ $U$ と表記) と最終的な $P$ 行列が得られます。 $A^{(2)}=A^{(N-1)}=U={\begin{pmatrix}4&2&1\\0&6&8.5\\0&0&0.25\\\end{pmatrix}},\quad P={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}.$ 対応する行を入れ替えると、最終的な $L$ 行列が得られます。 $L={\begin{pmatrix}1&0&0\\\ell _{3,1}&1&0\\\ell _{2,1}&\ell _{3,2}&1\\\end{pmatrix}}={\begin{pmatrix}1&0&0\\0.5&1&0\\0&{\frac {5}{6}}&1\\\end{pmatrix}}$

$これらの行列は、 PA = LU$ という関係を持つ。

行が交換されない場合のリレーション

このプロセス中に行を全く交換しなかった場合、各列 $n$ に対して行操作を同時に実行できます。 $A^{(n)}:=L_{n}^{-1}A^{(n-1)},$ どこ $L_{n}^{-1}$ $は、 n$ 番目の列が転置ベクトル $(0$ $\dots$ $0$ $1$ $-$ $ℓ$ $n$ $+1,$ $n$ $\dots$ $-$ $ℓ$ $N$ $,$ $n$ $)$ $Tに置き換えられた$ $N$ × $N$ 単位行列です。

言い換えれば、下三角行列 $L_{n}^{-1}={\begin{pmatrix}1&&&&&\\&\ddots &&&&\\&&1&&&\\&&-\ell _{n+1,n}&&&\\&&\vdots &&\ddots &\\&&-\ell _{N,n}&&&1\end{pmatrix}}.$

$最初のN - 1$ 列のすべての行操作を実行するには、 $A^{(n)}:=L_{n}^{-1}A^{(n-1)}$ この式は、分解を求めることと同等です。 $A=L_{1}L_{1}^{-1}A^{(0)}=L_{1}A^{(1)}=L_{1}L_{2}L_{2}^{-1}A^{(1)}=L_{1}L_{2}A^{(2)}=\dotsm =L_{1}\dotsm L_{N-1}A^{(N-1)}.$ $A$ $=$ $LA$ $($ $N$ $-1)$ $=$ $LU$ となるように、 $L = L 1 \dots L N -1$ と表します。

$それでは、$ $L 1 \dots L N -1$ のシーケンスを計算してみましょう。L $i は$ 次の式で表されることがわかっています。 $L_{n}={\begin{pmatrix}1&&&&&\\&\ddots &&&&\\&&1&&&\\&&\ell _{n+1,n}&&&\\&&\vdots &&\ddots &\\&&\ell _{N,n}&&&1\end{pmatrix}}$

主対角線に1を持つ2つの下三角行列があり、どちらの行列も主対角線より下の同じ列に非ゼロの要素を持たない場合、同じ位置にあるすべての非ゼロの要素を2つの行列の積に含めることができます。例：

$\left({\begin{array}{ccccc}1&0&0&0&0\\77&1&0&0&0\\12&0&1&0&0\\63&0&0&1&0\\7&0&0&0&1\end{array}}\right)\left({\begin{array}{ccccc}1&0&0&0&0\\0&1&0&0&0\\0&22&1&0&0\\0&33&0&1&0\\0&44&0&0&1\end{array}}\right)=\left({\begin{array}{ccccc}1&0&0&0&0\\77&1&0&0&0\\12&22&1&0&0\\63&33&0&1&0\\7&44&0&0&1\end{array}}\right)$

最後に、 $L 1$ を掛け合わせて、融合行列 $L$ を生成します(前述のとおり)。行列 $L$ を使用すると、 $A = LU$ が得られます。

このアルゴリズムが機能するためには、 $a_{n,n}^{(n-1)}\neq 0$ $各ステップで（ ℓ i,n$ の定義を参照）。この仮定が途中で破綻した場合は、続行する前に $n$ 番目の行をその下の別の行と交換する必要があります。これが、一般に LU 分解が $P -1 A = LU$ のようになる理由です。

LUバナキエヴィッチ分解

バナキエヴィッチ (1938) の LU 分解アルゴリズムはプログラム可能な電子計算機の登場に先立っていましたが、インデックスの交換、転置、列ごとの乗算はほとんどのプログラミング言語のネイティブな組み込み機能であり、実際の実行の遅延がほとんどなくコンパイラのみで処理されるため、コードに直接実装できる状態でした。バナキエヴィッチが使用した独特の行列表記により、行列を列ごとに乗算することができ、定規を次の行にスライドさせることで連続する因数を明らかにすることができたため、機械計算には便利な機能でした。しかし、人間の読者にとっては、彼の方程式は標準的な行列表記に変換するのが最適です。完全な行列 $A$ から三角行列 $U$ と $L の計算を取得するには、まず$ $Aの最上行と最左端の列をそれぞれ行列$ $U$ と $L$ の対応する位置にコピーします $。L$ の既知の単位対角要素は、プロセス全体を通して保存も使用もされません。次の計算は、 $A$ の右下隅まで次の行と列に対して続きます。

この図は、前の段階が既に完了していると仮定した場合の、3行目と3列目の計算を示しています。関係する行列は、その内容を示す四角の上に名前が付けられています。行列の積と減算は、太い枠で囲まれたボックス内の要素にのみ適用されます。緑色で塗りつぶされた細い枠で囲まれたボックスは、前の段階で既にわかっている値を示します。青色のボックスは、 $U行列$ と $L行列で結果を格納する場所を示します。各段階で、$ $L$ 行列の結果要素を、 $U行列$ の主対角線上の対応するピボット要素で割る必要があることに注意してください。これは、 $L$ 行列の左端の列にも適用されます。

$第3段階の完了後、行列A$ の関連要素は使用されなくなり、前の段階の要素も同様に使用されなくなることに注意してください。これにより、これらの要素を $U$ と $L$ の結果値で置き換えることが可能になります。つまり、LU分解をその場で実行し、 $L$ の単位対角線を除く $A$ 全体を $U$ と $L$ で置き換えます。バナキエヴィッチLUアルゴリズムは、 $U$ の新たに計算された行から絶対最大ピボットを選択し、その後列を交換して主対角線上に配置することで、部分ピボットに適しています。詳細は、添付のFortran90コードを参照してください。

すべての部分ピボットLUアルゴリズムは、ほぼ同じオーダーのコストがかかります。 ${\textstyle O\left({2 \over 3}n^{3}\right)}$ 演算。ここで $nは$ $A$ の行数または列数です。

LUクラウト分解

この手順で得られる分解はドゥーリトル分解 $であることに注意してください。つまり、 L$ の主対角線はすべて 1 で構成されています。行の倍数を追加して対角線より上の要素を削除するのではなく、列の倍数を追加して主対角線より上の要素を削除すると、 $U$ の主対角線がすべて 1 であるクラウト分解が得られます。

与えられた行列 $Aの Crout 分解を生成するもう 1 つの (同等の) 方法は、$ $A$ の転置行列の Doolittle 分解を取得することです。実際、このセクションで紹介したアルゴリズムによって $A T = L 0 U 0$ が LU 分解である場合、 $L = U T 0$ および $U = L T 0$ $とすることで、 A = LU$ が Crout 分解であることがわかります。

ランダム化アルゴリズム

ランダム化アルゴリズムを使用して、LU分解の低ランク近似を見つけることが可能です。入力行列 $A$ と目的の低ランク $k$ が与えられると、ランダム化 LU は、それぞれ $m$ × $k$ と $k$ × $n$ のサイズの順列行列 $P$ 、 $Q$ と下/上台形行列 $L$ 、 $Uを返します。$ 高い確率で $‖$ $PAQ$ $-$ $LU$ $‖$ $2$ $\leq$ $Cσ$ $k$ $+1$ となります。ここで、 $C$ はアルゴリズムのパラメータに依存する定数であり、 $σ$ $k$ $+1$ は入力行列 $Aの$ $($ $k$ $+1)$ 番目の特異値です。^[¹⁴^]

理論的複雑性

$n$ 次行列 2 つを時間 $M (n)$ で乗算できる場合(ただし、 $M (n) \geq n a$ $(a > 2$ の場合))、LU 分解は時間 $O(M (n))$ で計算できます。^{[ 15 ]}これは、例えば、Coppersmith–Winograd アルゴリズムに基づく $O(n 2.376)$ アルゴリズムが存在することを意味します。詳細については、高速行列乗算アルゴリズムの記事も参照してください。

疎行列分解

大規模な疎行列を因数分解するための特別なアルゴリズムが開発されている。これらのアルゴリズムは、疎な因子 $L$ と $U$ を見つけようとする。理想的には、計算コストは行列のサイズではなく、非ゼロ要素の数によって決まる。

これらのアルゴリズムは、行と列を入れ替える自由度を利用して、フィルイン（アルゴリズムの実行中に初期値がゼロからゼロ以外の値に変化するエントリ）を最小限に抑えます。

フィルインを最小化する順序付けの一般的な扱いは、グラフ理論を用いて扱うことができる。

アプリケーション

線形方程式を解く

行列形式の線形方程式系が与えられた場合 $A\mathbf {x} =\mathbf {b} ,$

$A$ と $b$ が与えられたとき、 $x$ に関する方程式を解きたい。A $の$ LUP分解が $PA$ $=$ $LU$ となるように既に得られていると仮定すると、 $LU$ $x$ $=$ $P$ $b$ となる。

この場合、解決策は2つの論理的なステップで実行されます。

まず、方程式 $L y = P bを$ $y$ について解きます。
次に、方程式 $U x = yを$ $x$ について解きます。

$どちらの場合も、三角行列（ L$ と $U$ ）を扱っており、ガウス消去法を用いなくても、前方代入と後方代入によって直接解くことができます（ただし、LU分解自体を計算するには、この方法またはそれに相当する方法が必要です）。

$上記の手順を繰り返し適用することで、異なるb$ に対して方程式を複数回解くことができます。この場合、ガウス消去法を毎回使用するよりも、行列 $A$ の LU 分解を一度行い、異なる $b$ に対して三角行列を解く方が高速（かつ便利）です。行列 $L$ と $U は$ 、ガウス消去法のプロセスを「符号化」していると考えることができます。

行列 $A の$ $サイズ$ が $nの場合、連立$ $一$ $次$ 方程式を解くコストは約 2/3 n 3 回の浮動小数点演算です $。$ $これ$ $は$ $、$ ハウスホルダー反射を使用した場合に約 4/3 n 3 回の浮動小数点 $演算$ $の$ $コスト$ $が$ $かかる$ $QR$ 分解に基づくアルゴリズムの 2 倍の速さです。 $この$ ため、通常は LU 分解が好まれます。^[¹⁶^]

行列の逆行列を計算する

連立方程式を解く場合、 $b$ $は通常、行列A$ の高さに等しい長さのベクトルとして扱われます。しかし、行列の逆行列を求める場合、ベクトル $b$ の代わりに、 $n$ × $p$ 行列である行列 $B$ $を$ 用います。つまり、行列 $X$ (これも $n$ × $p$ 行列) を求めようとしているのです。 $AX=LUX=B.$

先に示しておいたアルゴリズムと同じものを使って、行列 $X$ の各列を解くことができます。ここで、 $Bが$ $n$ サイズの単位行列、 $I n で$ あると仮定します。したがって、結果 $X は$ $A$ の逆行列でなければなりません。^{[ 17 ]}

行列式の計算

正方行列 $A$ のLUP 分解 $A = P -1 LU$ $が与えられた場合、 A$ の行列式は次のように簡単に計算できます。 ${\begin{aligned}\det(A)&=\det \left(P^{-1}\right)\det(L)\det(U)\\&=(-1)^{S}\left(\prod _{i=1}^{n}l_{ii}\right)\left(\prod _{i=1}^{n}u_{ii}\right).\end{aligned}}$

2 番目の式は、三角行列の行列式が単にその対角成分の積であること、および置換行列の行列式が $(-1) S$ $に等しいこと（S$ は分解における行交換の数）から導かれる。

LU分解でフルピボットを使用する場合、 $Sを$ 行と列の交換の総数とすると、 $det(A)$ も上記の式の右辺と等しくなります。

同様の方法は、 $Pを$ 単位行列に設定することで、LU分解にも容易に適用できる。

歴史

LU分解は、例えばラルストンが説明したように、線形方程式系の消去に関連しています。^{[ 18 ]} $N個の未知数を持つ$ $N$ 個の線形方程式を消去法で解く方法は、古代中国ではすでに知られていました。^[¹⁹^]ガウス以前には、ユーラシアの多くの数学者がこの方法を実行し、完成させていましたが、この方法が学校教育レベルに追いやられると、詳細な記述を残した人はほとんどいませんでした。したがって、ガウス消去法という名前は、複雑な歴史を簡略化したものに過ぎません。

ポーランドの天文学者タデウシュ・バナヒエヴィチは1938年にLU分解を導入した。^{[ 20 ]}バナヒエヴィチについて、ポール・ドワイヤーは次のように述べている。^{[ 21 ]}

ガウスとドゥーリトルは、消去法を対称方程式にのみ適用したようです。エイトケン、バナキエヴィッチ、ドワイヤー、クラウトなどの最近の著者は、非対称問題に関連して、この方法またはその変形を使用することを強調しています。バナキエヴィッチは、基本的な問題は実際には行列分解、または彼が「分解」と呼んだものの問題であるという点に気づきました。

—ポール・ドワイヤー著『線形計算』（1951年）

バナキエヴィッチ^{[ 20 ]}は、行列の観点から消去法を初めて検討し、図解で示されているようにLU分解を定式化した。彼の計算は通常の行列計算に従うが、表記法は異なり、彼は1つの因子を転置して記述することを好んだ。これは、両方の行列の連続する行に定規をスライドさせることで、列ごとに機械的に乗算できるようにするためである（算術計を使用）。添え字の順序を入れ替えた彼の式は、現代の表記法では次のようになる。 ${\begin{aligned}{\mathbf {x} }\cdot IA'={\mathbf {0} }&\rightarrow A'{\mathbf {x} =0}\equiv (A|{\mathbf {l} }){\mathbf {x} },\\A=G\cdot H&\rightarrow A^{T}=G^{T}H,\end{aligned}}$

ここで $、IA \to A T$ ; $x \equiv [x 1, ... , x n, -1]$ ; $A' は$ $、最後の列を追加したA$ を指し、 $x$ $の最後の要素は-1$ です。 LU 因子の行と列を再帰的に計算するための行列式は、Banachiewicz の論文の残りの部分で式 (2.3) および (2.4) として与えられています。 Banachiewicz によるこの論文には、それぞれ非対称行列と対称行列の $LU 因子$ と $R T R$ 因子の導出の両方が含まれています。後年の出版物では、彼の名前が Cholesky 分解の再発見のみに関連付けられる傾向があるため、これらは時々混同されます。バナキエヴィチ自身は行動を起こさなかったことを責められるべきではない。なぜなら、翌年には占領軍による迫害を受け、ザクセンハウゼン強制収容所に3ヶ月間収容され、釈放後、協力者であり同房者であったアントニ・ウィルクを列車から降ろしたが、ウィルクは1週間後に疲労困憊で亡くなったからである。

コード例

Fortran90コード例

Module mlu Implicit None Integer , Parameter :: SP = Kind ( 1 d0 ) ! 入出力の実精度を設定Private  Public luban , lusolve Contains  Subroutine luban ( a , tol , g , h , ip , condinv , detnth ) ! Banachiewicz (1938、以下 B38) による LU 分解法は、正方形 B=A^T=G^TH=LU となるような三角形 L=G^T および U=H を計算します。! 列置換 IP(:) による部分ピボットは、現代の追加機能です。! コード内では、a、g は B38 A^T および G^T に対応するため、a=gh が成り立ちます。! ! 通常の使用は正方形 A 用ですが、RHS l については既に知られています! (A|l)^T の入力は (L|y^T)^T を生成し、L^Tx=y の x は Ax=l の解です。Real ( SP ), Intent ( In ) :: a (:, :) ! 入力行列 A(m,n)、n<=m Real ( SP ), Intent ( In ) :: tol ! ゼロに近いピボットの許容値Real ( SP ), Intent ( Out ) :: g ( size ( a , dim = 1 ), size ( a , dim = 2 )) ! L(m,n) Real ( SP ), Intent ( Out ) :: h ( size ( a , dim = 2 ), size ( a , dim = 2 )) ! U(n,n) ! U 列は順列になっていることに注意してくださいReal ( SP ), Intent ( Out ) :: condinv ! 1/cond(A)、単数形のAの場合は0 Real ( SP ) 、Intent ( Out ) :: detnth ! sign*Abs(det(A))**(1/n) Integer 、Intent ( Out ) :: ip( size ( a , dim = 2 )) ! 列の順列! Integer :: k , n , j , l , isig Real ( SP ) :: tol0 , pivmax , pivmin , piv ! n = size ( a , dim = 2 ) tol0 = Max ( tol , 3._SP * epsilon ( tol0 )) ! tol=0 の場合はデフォルト値を使用! ! 長方形 A と G は、次の条件で許可されます: If ( n > size ( a , dim = 1 ) . Or . n < 1 ) Stop 91 Forall ( k = 1 : n ) ip ( k ) = k h = 0._SP g = 0._SP isig = 1 detnth = 0._SP pivmax = Maxval ( Abs ( a ( 1 , :))) pivmin = pivmax ! k = 1 、n ! Banachiewicz (1938) 式 (2.3) h ( k 、ip ( k :) ) = a ( k 、ip ( k :)) - Matmul ( g ( k 、: k - 1 ) 、h (: k - 1 、ip ( k :))) ! ! 行ピボットj = ( Maxloc ( Abs ( h ( k 、ip ( k :)))、dim = 1 ) + k - 1を見つける) If ( j /= k ) Then ! 列 j と k を入れ替えるisig = - isig ! 置換のため Det(A) の符号を変更するl = ip ( k ) ip ( k ) = ip ( j ) ip ( j ) = l End If piv = Abs ( h ( k , ip ( k ))) pivmax = Max ( piv , pivmax ) ! 条件を調整するpivmin = Min ( piv , pivmin ) If ( piv < tol0 ) Then ! 特異行列isig = 0 pivmax = 1._SP Exit  Else ! ピボットの寄与を Det(A) の符号と値に考慮するIf ( h ( k , ip ( k )) < 0._SP ) isig = - isig detnth = detnth + Log ( piv ) End If ! ! 転置された Banachiewicz (1938) 式。 (2.4) g ( k + 1 :, k ) = ( a ( k + 1 :, ip ( k )) - & Matmul ( g ( k + 1 :, : k - 1 ), h (: k - 1 , ip ( k )))) / h ( k , ip ( k )) g ( k , k ) = 1._SP End Do ! detnth = isig * Exp ( detnth / n ) condinv = Abs (isig ) * pivmin / pivmax ! 以下のコメントを解除して、A(n,n) の二乗をテストします! Print *, '|AQ-LU| ',Maxval (Abs(a(:,ip(:))-Matmul(g, h(:,ip(:))))) End Subroutine luban Subroutine lusolve ( l , u , ip , x ) ! 三角係数 LU=A を使用して Ax=b システムを解きます Real ( SP ), Intent ( In ) :: l (:, :) ! 下三角行列 L(n,n) Real ( SP ), Intent ( In ) :: u (:, :) ! 上三角行列 U(n,n) Integer , Intent ( In ) :: ip (:) !列の順列 IP(n) Real ( SP ), Intent ( InOut ) :: x (:, :) ! 入力: m 個の RHS セット B(n,m)、! 出力: 対応する未知数のセット X(n,m) Integer :: n , m , i , j n = size ( ip ) m = size ( x , dim = 2 ) If ( n < 1. Or . m < 1. Or . Any ([ n , n ] /= shape ( l )). Or . Any ( shape ( l ) /= shape ( u )). Or . & n /= size ( x , dim = 1 )) Stop 91 Do i = 1 , m Do j = 1 , n x ( j , i ) = x ( j , i ) - dot_product ( x(: j - 1 , i ), l ( j ,: j - 1 )) End Do  Do j = n , 1 , - 1 x ( j , i ) = ( x ( j , i ) - dot_product ( x ( j + 1 :, i ), u ( j , ip ( j + 1 :)))) / & u ( j , ip ( j )) End Do  End Do  End Subroutine lusolve End Module mlu

C言語コード例

/* 入力: A - 次元 N の正方行列の行へのポインタの配列* Tol - 行列が縮退に近い場合に失敗を検出するための小さな許容値* 出力: 行列 A が変更され、行列 LE と U の両方のコピーが A=(LE)+U として含まれ、P*A=L*U となります。* 置換行列は行列としてではなく、置換行列が「1」である列インデックスを含むサイズ N+1 の整数ベクトル P に格納されます。最後の要素 P[N]=S+N、* ここで S は行列式の計算に必要な行交換の数、det(P)=(-1)^S */ int LUPDecompose ( double ** A , int N , double Tol , int * P ) {int i 、j 、k 、imax ; double maxA 、* ptr 、absA ;for ( i = 0 ; i <= N ; i ++ ) P [ i ] = i ; // 単位置換行列、P[N] は N で初期化されますfor ( i = 0 ; i < N ; i ++ ) { maxA = 0.0 ; imax = i ;for ( k = i ; k < N ; k ++ ) if (( absA = fabs ( A [ k ][ i ])) > maxA ) { maxA = absA ; imax = k ; }if ( maxA < Tol ) return 0 ; //失敗、行列が縮退しているif ( imax != i ) { //ピボット P j = P [ i ]; P [ i ] = P [ imax ]; P [ imax ] = j ;// A の行をピボットしますptr = A [ i ]; A [ i ] = A [ imax ]; A [ imax ] = ptr ;//Nから始まるピボットをカウントする（行列式用）P [ N ] ++ ; }for ( j = i + 1 ; j < N ; j ++ ) { A [ j ][ i ] /= A [ i ][ i ];for ( k = i + 1 ; k < N ; k ++ ) A [ j ][ k ] -= A [ j ][ i ] * A [ i ][ k ]; } }return 1 ; // 分解完了}/* 入力: LUPDecompose で入力された A、P; b - 右辺ベクトル; N - 次元* 出力: x - A*x=b の解ベクトル*/ void LUPSolve ( double ** A , int * P , double * b , int N , double * x ) {for ( int i = 0 ; i < N ; i ++ ) { x [ i ] = b [ P [ i ]];for ( int k = 0 ; k < i ; k ++ ) x [ i ] -= A [ i ][ k ] * x [ k ]; }for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int k = i + 1 ; k < N ; k ++ ) x [ i ] -= A [ i ][ k ] * x [ k ];x [ i ] /= A [ i ][ i ]; } }/* 入力: LUPDecompose で埋められた A、P。N - 次元* 出力: IA は初期行列の逆行列です*/ void LUPInvert ( double ** A 、int * P 、int N 、double ** IA ) { for ( int j = 0 ; j < N ; j ++ ) { for ( int i = 0 ; i < N ; i ++ ) { IA [ i ][ j ] = P [ i ] == j ? 1.0 : 0.0 ;for ( int k = 0 ; k < i ; k ++ ) IA [ i ][ j ] -= A [ i ][ k ] * IA [ k ][ j ]; }for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int k = i + 1 ; k < N ; k ++ ) IA [ i ][ j ] -= A [ i ][ k ] * IA [ k ][ j ];IA [ i ][ j ] /= A [ i ][ i ]; } } }/* 入力: LUPDecompose で入力された A、P。N は次元。* 出力: 関数は初期行列の行列式を返します*/ double LUPDeterminant ( double ** A , int * P , int N ) {double det = A [ 0 ][ 0 ];for ( int i = 1 ; i < N ; i ++ ) det *= A [ i ][ i ];return ( P [ N ] - N ) % 2 == 0 ?デット: -デット; }

C#コード例

public class SystemOfLinearEquations { public double [] SolveUsingLU ( double [,] matrix , double [] rightPart , int n ) { // 行列の分解double [,] lu = new double [ n , n ]; double sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ i , k ] * lu [ k , j ]; lu [ i , j ] = matrix [ i , j ] - sum ; } for ( int j = i + 1 ; j < n ; j ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ j , k ] * lu [ k , i ]; lu [ j , i ] = ( 1 / lu [ i , i ]) * ( matrix [ j , i ] - sum ); } }// lu = L+UI // Ly = b の解を求めるdouble [] y = new double [ n ]; for ( int i = 0 ; i < n ; i ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ i , k ] * y [ k ]; y [ i ] = rightPart [ i ] - sum ; } // Ux = y の解を求めるdouble [] x = new double [ n ]; for ( int i = n - 1 ; i >= 0 ; i -- ) { sum = 0 ; for ( int k = i + 1 ; k < n ; k ++ ) sum += lu [ i , k ] * x [ k ]; x [ i ] = ( 1 / lu [ i , i ]) * ( y [ i ] - sum ); } return x ; } }

MATLABコード例

関数LU = LUDecompDoolittle ( A ) n =長さ( A ); LU = A ; k = 2 の場合: n i = 1 の場合: k - 1ラムダ= LU ( k , i ) / LU ( i , i ); LU ( k , i ) =ラムダ; LU ( k , i + 1 : n ) = LU ( k , i + 1 : n ) - LU ( i , i + 1 : n ) *ラムダ;終わり、終わり、終わりfunction x = SolveLinearSystem ( LU, B ) n = length ( LU ); y = zeros ( size ( B )); % Ly = B の解を求めるfor i = 1 : n y ( i ,:) = B ( i ,:) - LU ( i , 1 : i ) * y ( 1 : i ,:); end % Ux = y の解を求めるx = zeros ( size ( B )); for i = n :( - 1 ): 1 x ( i ,:) = ( y ( i ,:) - LU ( i ,( i + 1 ): n ) * x (( i + 1 ): n ,:)) / LU ( i , i ); end endA = [ 4 3 3 ; 6 3 3 ; 3 4 3 ] LU = LUDecompDoolittle ( A ) B = [ 1 2 3 ; 4 5 6 ; 7 8 9 ; 10 11 12 ] ' x = SolveLinearSystem ( LU , B ) A * x

注記

↑ Schwarzenberg-Czerny, A. (1995). "行列分解と効率的な最小二乗解について" .天文学および天体物理学補足シリーズ. 110 : 405. Bibcode : 1995A & AS..110..405S .
↑ Cormen et al. (2009)、p. 819、28.1 : 線形方程式系の解法。
1 2 Okunev & Johnson (1997) 、系3。
↑ Trefethen & Bau (1997)、p. 166.
↑ Trefethen & Bau (1997)、p. 161.
↑ Banachiewicz (1938) ; Lay, Lay & McDonald (2021)、p. 133、2.5: 行列分解。
↑ Rigotti (2001)、首席副主任。
1 2ホーン＆ジョンソン（1985）、系3.5.5
↑ Horn & Johnson (1985)、定理 3.5.2。
↑ Nhiayi, Ly; Phan-Yamada, Tuyetdong (2021). "可能なLU分解の検討". North American GeoGebra Journal . 9 (1).
↑オクネフ＆ジョンソン（1997）。
↑ハウスホルダー (1975)。
↑ Golub & Van Loan (1996) 、 112、119ページ
↑シャバット、ギル。シュムエリ、ヤニフ。アイゼンバド、ヤリブ。アーフェルブッフ、アミール (2016)。「ランダム化された LU 分解」。応用および計算高調波解析。44 (2 ) : 246–272。arXiv : 1310.7202 。土井：10.1016/j.acha.2016.04.006。S2CID 1900701。
↑バンチ＆ホップクロフト（1974）。
↑ Trefethen & Bau (1997)、p. 152.
↑ゴラブとヴァン・ローン (1996)、p. 121.
↑ラルストン (1965)。
↑ハート（2011）。
1 2バナキエヴィチ (1938)。
↑ドワイヤー (1951)。

参考文献

Banachiewicz、T. (1938)、「解決策の数値計算方法…」(PDF)、Bull.インターン。デ・ラカド。ポロネーズ、セリエA. Sc.数学。 : 393～ 404。
Bunch, James R.; Hopcroft, John (1974)、「高速行列乗算による三角行列の因数分解と逆行列計算」、Mathematics of Computation、28 (125): 231–236、doi : 10.2307/2005828、hdl : 1813 /6003 、ISSN 0025-5718、JSTOR 2005828 。
トーマス・H・コーメン;チャールズ・E・ライザーソン;ロナルド・L・リベスト; Stein、Clifford (2009)、Introduction to Algorithms (第 3 版)、MIT Press および McGraw-Hill、ISBN 978-0-262-03293-3。
ドワイヤー、ポール・S. (1951)、『線形計算』、ニューヨーク：ワイリー。
Golub, Gene H. ; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9。
ハート、ロジャー（2011）『線形代数の中国起源』ボルチモア：ジョンズ・ホプキンス大学出版局、ISBN 978-0801897559。
ホーン、ロジャー A.、ジョンソン、チャールズ R. (1985)、行列解析、ケンブリッジ大学出版局、ISBN 978-0-521-38632-6セクション3.5を参照。N − 1
ハウスホルダー、アルストン S. (1975)、『数値解析における行列の理論』、ニューヨーク：ドーバー出版、MR 0378371 。
Lay, David C.; Lay, Steven R.; McDonald, Judi J. (2021),線形代数とその応用（第6 版）, Pearson, ISBN 978-0-13-585125-8。
Okunev, Pavel; Johnson, Charles R. (1997),任意の行列の LU 分解の存在に必要な十分条件, arXiv : math.NA/0506382。
Poole, David (2006),線形代数：現代入門（第2 版）, カナダ：Thomson Brooks/Cole, ISBN 978-0-534-99845-5。
ラルストン、アンソニー（1965）、『数値解析入門』、ニューヨーク：マグロウヒル社、ISBN 978-0-070-51157-6。
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 2.3」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8。
トレフェセン、ロイド N. ; バウ、デイビッド (1997)、数値線形代数、フィラデルフィア：産業応用数学会、ISBN 978-0-89871-361-9。
リゴッティ、ルカ（2001）ECON 2001 - 数学的手法入門、講義8

外部リンク

参考文献

MathWorldにおけるLU分解。
Math-Linux上でのLU 分解。
ホリスティック数値解析研究所におけるLU分解
LU行列分解。MATLABリファレンス。

コンピュータコード

LAPACKは、密な線形代数問題を解くためのFORTRANサブルーチンの集合体である。
ALGLIBには、LAPACKをC++、C#、Delphiなどに部分的に移植したものが含まれています。
C++コード、J.ルーミス教授、デイトン大学
C言語コード、数学ソースライブラリ
Rustコード
X10のLU

オンラインリソース

LU分解を用いて線形方程式系を記述的に解くWebアプリケーション
LU分解を含む手順付き行列計算機
LU分解ツール、uni-bonn.de
LU分解、エド・ペッグ・ジュニア著、ウルフラム・デモンストレーション・プロジェクト、2007年。

[Schwarzenberg-1] Schwarzenberg-Czerny, A. (1995). "行列分解と効率的な最小二乗解について" .天文学および天体物理学補足シリーズ. 110 : 405. Bibcode : 1995A & AS..110..405S .

[FOOTNOTECormenLeisersonRivestStein2009[httpsarchiveorgdetailsintroduction-to-algorithms-third-edition-2009page819_819]28.1:_Solving_systems_of_linear_equations-2] Cormen et al. (2009)、p. 819、28.1 : 線形方程式系の解法。

[okunev-cor3-3] 1 2 Okunev & Johnson (1997) 、系3。

[FOOTNOTETrefethenBau1997166-4] Trefethen & Bau (1997)、p. 166.

[FOOTNOTETrefethenBau1997161-5] Trefethen & Bau (1997)、p. 161.

[FOOTNOTEBanachiewicz1938LayLayMcDonald2021[httpsarchiveorgdetailslinear-algebra-its-applications-6thpage133_133]2.5:_Matrix_Factorizations-6] Banachiewicz (1938) ; Lay, Lay & McDonald (2021)、p. 133、2.5: 行列分解。

[FOOTNOTERigotti2001Leading_Principal_Minor-7] Rigotti (2001)、首席副主任。

[horn-cor355-8] 1 2ホーン＆ジョンソン（1985）、系3.5.5

[FOOTNOTEHornJohnson1985Theorem_3.5.2-9] Horn & Johnson (1985)、定理 3.5.2。

[10] Nhiayi, Ly; Phan-Yamada, Tuyetdong (2021). "可能なLU分解の検討". North American GeoGebra Journal . 9 (1).

[FOOTNOTEOkunevJohnson1997-11] オクネフ＆ジョンソン（1997）。

[FOOTNOTEHouseholder1975-12] ハウスホルダー (1975)。

[FOOTNOTEGolubVan_Loan1996112,_119-13] Golub & Van Loan (1996) 、 112、119ページ

[14] シャバット、ギル。シュムエリ、ヤニフ。アイゼンバド、ヤリブ。アーフェルブッフ、アミール (2016)。「ランダム化された LU 分解」。応用および計算高調波解析。44 (2 ) : 246–272。arXiv : 1310.7202 。土井：10.1016/j.acha.2016.04.006。S2CID 1900701。

[FOOTNOTEBunchHopcroft1974-15] バンチ＆ホップクロフト（1974）。

[FOOTNOTETrefethenBau1997152-16] Trefethen & Bau (1997)、p. 152.

[FOOTNOTEGolubVan_Loan1996121-17] ゴラブとヴァン・ローン (1996)、p. 121.

[FOOTNOTERalston1965-18] ラルストン (1965)。

[FOOTNOTEHart2011-19] ハート（2011）。

[FOOTNOTEBanachiewicz1938-20] 1 2バナキエヴィチ (1938)。

[FOOTNOTEDwyer1951-21] ドワイヤー (1951)。

[

[ 3 ]

[ 4 ]

[ 5 ]

[

[

[

[ 10 ]

[ 11 ]

[

[ 13 ]

[

[ 15 ]

[

[ 17 ]

[ 18 ]

[

[ 20 ]

[ 21 ]

定義