数学 すうがく における行列 ぎょうれつ の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 2 個 こ の式 しき を解 と くことにより、行列 ぎょうれつ L , U を求 もと めるのだが、このままでは未知 みち の係数 けいすう の個数 こすう (n (n + 1) 個 こ )が式 しき の個数 こすう (n 2 個 こ )より多 おお いので解 と けない。これを解 と くための解法 かいほう には ドゥーリトル法 ほう と クラウト法 ほう の2つがある。
ドゥーリトル法 ほう では、行列 ぎょうれつ L の対 たい 角 かく 成分 せいぶん の全 すべ てを 1 とおき、(1, 1) 成分 せいぶん , (2, 1) 成分 せいぶん , (3, 1) 成分 せいぶん , ... , (1, 2) 成分 せいぶん , (2, 2) 成分 せいぶん , ... の順 じゅん に n 2 個 こ の式 しき を解 と く。
クラウト法 ほう では、行列 ぎょうれつ U の対 たい 角 かく 成分 せいぶん の全 すべ てを 1 とおき、(1, 1) 成分 せいぶん , (1, 2) 成分 せいぶん , (1, 3) 成分 せいぶん , ... , (2, 1) 成分 せいぶん , (2, 2) 成分 せいぶん , ... の順 じゅん に n 2 個 こ の式 しき を解 と く。
ドゥーリトル法 ほう による2次 じ 行列 ぎょうれつ のLU分解 ぶんかい を行 おこな う。与 あた えられた正方 せいほう 行列 ぎょうれつ A の成分 せいぶん をaij とする。
下 しも 三角 さんかく 行列 ぎょうれつ L の対 たい 角 かく 成分 せいぶん を全 すべ て 1 とおき、残 のこ りの成分 せいぶん 、(1, 2)を0、(2, 1)を変数 へんすう l 21 とおく。
L
=
[
1
0
l
21
1
]
{\displaystyle L={\begin{bmatrix}1&0\\l_{21}&1\end{bmatrix}}}
上 うえ 三角 さんかく 行列 ぎょうれつ U の対 たい 角 かく 成分 せいぶん と対 たい 角 かく 成分 せいぶん より上 うえ の成分 せいぶん を変数 へんすう におく。
U
=
[
u
11
u
12
0
u
22
]
{\displaystyle U={\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}}
A =LU の両辺 りょうへん を係数 けいすう 比較 ひかく する。
a
11
=
u
11
a
12
=
u
12
a
21
=
l
21
u
11
a
22
=
l
21
u
12
+
u
22
{\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}}}
上 うえ 式 しき を上 うえ から順 じゅん に解 と くことでL , U が求 もと められる。
L
=
[
1
0
a
21
a
11
1
]
U
=
[
a
11
a
12
0
a
22
−
a
21
a
12
a
11
]
{\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次 じ 方程式 ほうていしき
A
x
=
b
{\displaystyle A{\boldsymbol {x}}={\boldsymbol {b}}}
の解 と き方 かた に、行列 ぎょうれつ A を LU分解 ぶんかい する方法 ほうほう がある。L , U は下 しも 三角 さんかく 行列 ぎょうれつ 、上 うえ 三角 さんかく 行列 ぎょうれつ であるため、逆 ぎゃく 行列 ぎょうれつ を求 もと めることなく計算 けいさん することが可能 かのう である。このため、同 おな じA に対 たい しb だけを変 か えていくつも連立 れんりつ 方程式 ほうていしき を解 と く場合 ばあい 、LU分解 ぶんかい は有用 ゆうよう である[ 1] 。
与 あた えられた方程式 ほうていしき
A
x
=
L
U
x
=
b
{\displaystyle A{\boldsymbol {x}}=LU{\boldsymbol {x}}={\boldsymbol {b}}}
に対 たい し、変数 へんすう y を
U
x
=
y
{\displaystyle U{\boldsymbol {x}}={\boldsymbol {y}}}
とおき、これを上 うえ 式 しき に代入 だいにゅう する。
L
y
=
b
{\displaystyle L{\boldsymbol {y}}={\boldsymbol {b}}}
から変数 へんすう y を求 もと める[ 注釈 ちゅうしゃく 1] 。求 もと めた解 かい y をUx = y の右辺 うへん に代入 だいにゅう し、解 かい x を求 もと めることができる[ 注釈 ちゅうしゃく 2] 。
Ly = b はガウスの消去 しょうきょ 法 ほう の前進 ぜんしん 消去 しょうきょ 、Ux = y は後退 こうたい 代入 だいにゅう に対応 たいおう する。
行列 ぎょうれつ A を LU 分解 ぶんかい すると、
A
−
1
=
U
−
1
L
−
1
{\displaystyle A^{-1}=U^{-1}L^{-1}}
により逆 ぎゃく 行列 ぎょうれつ A -1 を求 もと められる。
また、
L
U
x
i
=
e
i
(
i
=
1
,
2
,
…
,
n
)
{\displaystyle LU{\boldsymbol {x_{i}}}={\boldsymbol {e_{i}}}\quad (i=1,2,\dots ,n)}
(e i は単位 たんい 行列 ぎょうれつ I の第 だい i 列 れつ )
の解 かい x i を並 なら べた行列 ぎょうれつ
X
=
[
x
1
,
x
2
,
…
,
x
n
]
{\displaystyle X=[{\boldsymbol {x_{1}}},{\boldsymbol {x_{2}}},\dots ,{\boldsymbol {x_{n}}}]}
は AX = I を満 み たすので、このようにしても逆 ぎゃく 行列 ぎょうれつ A -1 を求 もと めることができる。
行列 ぎょうれつ A を LU 分解 ぶんかい できれば、その行列 ぎょうれつ 式 しき は簡単 かんたん に求 もと めることができる。なぜならば、行列 ぎょうれつ L および U は三角 さんかく 行列 ぎょうれつ であることから、それらの行列 ぎょうれつ 式 しき |L | , |U | は対 たい 角 かく 成分 せいぶん の積 せき で表 あらわ され、|A | は、
|
A
|
=
|
L
|
|
U
|
{\displaystyle |A|=|L||U|}
と計算 けいさん できるからである。
LDU 分解 ぶんかい
下 しも 三角 さんかく 行列 ぎょうれつ L と対 たい 角 かく 行列 ぎょうれつ D と上 うえ 三角 さんかく 行列 ぎょうれつ U の積 せき に分解 ぶんかい する。
A
=
L
D
U
{\displaystyle A=LDU}
LUP 分解 ぶんかい
下 しも 三角 さんかく 行列 ぎょうれつ L と上 うえ 三角 さんかく 行列 ぎょうれつ U と置換 ちかん 行列 ぎょうれつ P の積 せき に分解 ぶんかい する。
P
A
=
L
U
{\displaystyle PA=LU}
^ 左辺 さへん Ly を計算 けいさん し、左辺 さへん と右辺 うへん を係数 けいすう 比較 ひかく すれば、y が求 もと まる。
^ 左辺 さへん Ux を計算 けいさん し、左辺 さへん と右辺 うへん を係数 けいすう 比較 ひかく すれば、x が求 もと まる。
^ Joel H. Ferziger; Milovan Perić 著 ちょ 、小林 こばやし 敏雄 としお 、谷口 たにぐち 伸行 のぶゆき 、坪倉 つぼくら 誠 まこと 訳 やく 『コンピュータによる流体 りゅうたい 力学 りきがく 』シュプリンガー・フェアラーク東京 とうきょう 、2003年 ねん 、90頁 ぺーじ 。ISBN 4-431-70842-1 。