LDU分解

サイトのTOP→理系インデックス
行列分解のTOP→行列分解インデックス




定義 ( 単位三角行列 )

対角成分がすべて1である上三角行列を 『 単位上三角行列 』 という。

対角成分がすべて1である下三角行列を 『 単位下三角行列 』 という。

明らかに、単位上三角行列の逆行列は、単位上三角行列である。

また、単位下三角行列の逆行列は、単位下三角行列である。

注意!

以下、L は単位下三角行列であるとする。

また、U は単位上三角行列であるとする。

定義 ( 首座部分行列 )

A を n×n 行列とする。

次のように分割する。



11 は r×r 行列であるとする。

このとき、A11 を 『 r×r 首座部分行列 』 という。

D30 ( 補題 )

A を n×n 行列とする。

次のように分割する。



ただし、A、L、U、D は(n−1)×(n−1)行列であるとする。

このとき、次は同値である。

補足

とくに、(*)は A の LDU 分解を意味することに注意。

証明

明らかである。

D31 ( LDU分解の特徴づけ〜その1 )

A を n×n 行列とする。

n≧2 とする。

次のように分割する。



ただし、A は(n−1)×(n−1)行列であるとする。

このとき、次は同値である。

(1) A は LDU 分解をもつ。

(2) A は LDU 分解をもつ。また、a∈C(A)、b∈R(A)である。

証明

(1)を仮定する。

L、U、D を次のように分割する。



いま、A=L である。(※D30)

また、a=Lu、b=Ul である。

いま、a=Lu=A−1u∈C(A)である。

また、b=l=l−1∈R(A)である。

−−−−−−−−−−−−−−−−−−−−

(2)を仮定する。

いま、a∈C(A)、b∈R(A)である。

よって、あるベクトル r、s が存在して、a=Ar、b=s となる。

よって、a=L(Ur)、b=U(Ls)である。

ここで、u=Ls、l=Ur とおく。

いま、a=Lu、b=Ul である。

ここで、d=c−lu とおく。

いま、次が成り立つ。(※D30)

D32 ( UDU 分解の特徴づけ〜その1 )

A を n×n 対称行列とする。

n≧2 とする。

次のように分割する。



ただし、A は(n−1)×(n−1)行列であるとする。

このとき、次は同値である。

(1) A は UDU 分解をもつ。

(2) A は UDU 分解をもつ。また、a∈C(A)である。

証明

明らかである。(※D31において b=a、L=U とすればよい )

D33 ( 首座部分行列と LDU 分解の関係 )

A を n×n 行列とする。

n≧2 とする。

11 を、A の r×r 首座部分行列とする。

ただし、1≦r≦n−1とする。

A=LDU であるとする。

次のように分割する。



ただし、L11、U11、D は r×r 次であるとする。

このとき、A11=L1111 である。

補足

r は任意であることに注意。

証明

明らかである。

D34 ( LDU分解の漸化的構築 )

A=(aij)を n×n 行列とする。

を A の i×i 首座部分行列とする。( i=1、・・・、n )

次のように分割する。



=(1)、U=(1)、D=(a11)とする。(★1)

i=2、・・・、n に対し、a∈C(Ai−1)、b∈R(Ai−1)であるとする。(★2)

このとき、ある L、D、U が存在して、次を満たす。



補足

つまり、A=L である。

証明

仮定(★1)(★2)より、(1)の形で、A=L と表せる。(※D31証明)

i=k−1 ( 3≦k≦n ) について、(1)の形で Ak−1=Lk−1k−1k−1 と表せるとする。

仮定(★2)より、(1)の形で A=L と表せる。(※D31証明)

D35 ( UDU の漸化的構築 )

A=(aij)を n×n 対称行列とする。

を、A の i×i 首座部分行列とする。( i=1、・・・、n )

次のように分割する。



=(1)、D=(a11)とする。

i=2、・・・、n に対し、a∈C(Ai−1)であるとする。

このとき、ある U、D が存在して、次を満たす。



証明

D34と同様に証明できる。ただし、D31の代わりにD32を用いる。

D36 ( LDU分解の特徴づけ〜その2 )

A=(aij)を n×n 行列とする。

を、A の i×i 首座部分行列とする。( i=1、・・・、n )

次のように分割する。



このとき、次は同値である。

(1) A はLDU 分解をもつ。

(2) i=2、・・・、n に対し、a∈C(Ai−1)かつ b∈R(Ai−1)である。

証明

(1)を仮定する。

いま、A、・・・、An−1 は LDU 分解をもつ。(※D33)

また、i=2、・・・、n に対し、a∈C(Ai−1)、b∈R(Ai−1)である。(※D31)

一方、(2)⇒(1)は明らかである。(※D34)

D37 ( UDU分解の特徴づけ〜その2 )

A=(aij)を n×n 対称行列とする。

を、A の i×i 首座部分行列とする。( i=1、・・・、n )

次のように分割する。



このとき、次は同値である。

(1) A は UDU 分解をもつ。

(2) i=2、・・・、n に対し、a∈C(Ai−1)である。

証明

D36と同様である。

D38

A を n×n 行列とする。

rankA=r とする。

A=LDU であるとする。

L=(lij)、D=(dij)、U=(uij)と表す。

このとき、次が成り立つ。

(1) D の対角成分は一意的である。

次に、D の第 i、・・・、i 成分は 0 でないとする。

このとき、次が成り立つ。

(2) i=i、・・・、i と j>i に対し、uij と lji は一意である。

(3) i≠i、・・・、i と j>i に対し、uij と lji は任意である。

補足

つまり、(1)と(2)は次を意味する。

(*1) U において、第 i、・・・、i 行の成分は一意であり、残りの行は任意である。

(*2) L において、第 i、・・・、i 列の成分は一意であり、残りの列は任意である。

(1)の証明

A=L とする。

いま、(L−1LD=(L−1(LDU)U−1=(L−1(L)U−1=D−1 である。

明らかに、(L−1 は単位下三角行列で、U−1 は単位上三角行列である。

よって、(L−1LD の対角成分は d、・・・、d である。

また、D−1 の対角成分は d、・・・、d である。

よって、d=d である。

よって、D=D である。

(2)の証明

A の第 i、・・・、i行と第 i、・・・、i 列を残し、他の行と列を削除して r×r 行列 A11 を作る。

=diag(di1、・・・、dir)とおく。

L、L の第 i、・・・、i 行を残し、他の行を削除して r×n 行列 L、L を作る。

L、L の第 i、・・・、i 行と第 i、・・・、i 列を残し、他の行と列を削除して r×r 行列 L11、L11 を作る。

同様に、U と U から、U、U と U11、U11 を作る。

いま、明らかに、A11=LDU=L11 である。

また、明らかに、A11=L=LDU=L1111 である。

よって、L1111=L1111 である。(★1)

上式の両辺に、左から L11−1 を掛け、右から U11−1−1 を掛ける。

すると、(L11−111=D1111−1−1 である。

明らかに、L11−111 は単位下三角行列である。

明らかに、D1111−1−1 は上三角行列である。

よって、L11−111 である。(★2)

よって、U11=U11 である。(★3)

−−−−−−−−−−−−−−−−−−−−

A の第 i、・・・、i 列を残し、他の列をすべて削除して n×r 行列 A を作る。

A の第 i、・・・、i 行を残し、他の行をすべて削除して r×n 行列 A を作る。

L、L の第 i、・・・、i 列を残し、他の列をすべて削除して n×r 行列 L、L を作る。

いま、明らかに、A=LDU=LDU11 である。

また、(★3)より、A=L=LDU=L11=L11 である。

よって、L11=L11 である。

よって、L=L である。(★4)

いま、明らかに、A=LDU=L11 である。

また、(★2)より、A=L=LDU=L11=L11 である。

よって、L11=L11 である。

よって、U=U である。(★5)

(★4)、(★5)より、uij=uij かつ lji=lji である。(★6)

−−−−−−−−−−−−−−−−−−−−

いま、明らかに、A=LDU=L である。

つまり、L において L 以外の成分は値 LDU に影響しない。(★7)

また、U において U 以外の成分は値 LDU に影響しない。(★8)

(★6)〜(★8)より、定理が示された。

D39

A を n×n 行列とする。

A は LDU 分解をもつとする。

Aの(n−1)×(n−1)首座部分行列は正則であるとする。

このとき、A の LDU 分解は一意的である。

証明

11 を、A の(n−1)×(n−1)首座部分行列とする。

A=LDU とする。

次のように分割する。



ただし、L11、U11、D は(n−1)×(n−1)行列であるとする。

いま、A11=L1111 である。(※D30)

仮定より、A11 は正則である。

よって、D は正則である。

つまり、D の対角成分はいずれも 0 ではない。

つまり、D の第1、・・・、n−1対角成分は 0 ではない。

よって、A の LDU 分解は一意である。(※D38)

D40 ( LDU分解の存在 )

A を n×n 行列とする。

i=1、・・・、n−1とする。

を、A の i×i 首座部分行列とする。

、・・・、An−1 は正則であるとする。

このとき、A は一意な LDU 分解をもつ。

補足

D39 と D40 の違いに注意しよう。

D39 は一意性のみを述べている。

今回は存在性を述べている。

証明

A=(aij)とおく。

i=2、・・・、n に対し、a=(a1i、・・・、ai−1、i とおく。

i=2、・・・、n に対し、b=(a1i、・・・、ai、i−1)とおく。

いま、i=2、・・・、n に対し、a∈C(Ai−1)、b∈R(Ai−1)である。

よって、A は LDU 分解をもつ。(※D36)

また、この分解は一意的である。(※D39)

D41 ( 対称行列の一意な LDU 分解は UDU 分解である )

A を対称行列とする。

A は一意に LDU 分解をもつとする。

このとき、L=U である。

証明

A=LDU であるとする。

いま、A=A=UDL である。

明らかに、U は単位下三角行列であり、L は単位上三角行列である。

つまり、A=UDL は LDU 分解である。

よって、L=U である。

D42

A を n×n 正定値行列とする。

このとき、次が成り立つ。

(1) A は一意に LDU 分解をもつ。

(2) D の対角成分はすべて正である。

(1)の証明

いま、A の主部分行列は正定値である。(※D17)

よって、これは正則である。(※D14)

よって、A は一意に LDU 分解をもつ。(※D40)

(2)の証明

B=DU(L−1 とおく。

いま、明らかに、(L−1 は単位上三角行列である。

よって、B の対角成分は D の対角成分と一致する。

また、B=L−1(LDU)(L−1=L−1A(L−1 である。

よって、B は正定値である。(※D16)

よって、B の対角成分は正である。(※D17)

D43

A を n×n 対称行列とする。

このとき、次は同値である。

(1) A は正定値である。

(2) A は一意に UDU 分解をもち、D の対角成分は正である。

証明

(1)⇒(2)は明らかである。(※D42、D41)

(2)⇒(1)は明らかである。(※D18)