線形方程式１１月２４日今日のテーマ  T LU 分解と LDL 分解について •前回（ガウスの消去法）の復習 a11 x1  a12 x2   a1n xn  b1 a21 x1  a 22 x2   a2 n x n  b2 ( 1) a n1 x1  a n 2 x2   ann x n  bn ( 1) ( 1) (1 ) (1 ) (1 ) ( 1) (1 ) ( 1) ( 1) ( 1) (1) 次のような演算で消去を行い，右上三角行列を作り，方程式を解く方法（各係数の右上の添字は消去の過程を表すためにつけたもの） a  a m i j i j  i k a k j ( k  1 ) ( k ) ( k ) ( k ) ( i,j k 1 , ,n  1 ) ,m  a b  b m i i  i k b k ik ik /a k k (k  1 ) (k ) (k ) (k ) (k  1 ) (k) (k) • LU 分解 (1) (1) AA (a ij ) ( 1) m 21 a21  a11 (1 ) ，  1    m21 M 1    m31    m  n1 0 1 0 ， 0 0 1 0 0 0 0 0 (1 ) a n1 m n1  ( 1) a11 0  0 0  とおくと  0 1  とおき  a11( 1) a12( 1)  (1) (1 )  a 21 a22 (1 ) A    a (1) a ( 1) n2  n1 a1n   ( 1) a2 n    (1 ) ann  ( 1) M 1A A (1) (2) つまり，消去の第１段は行列 M 1 を左からかけたことに等しい．第 k段は 1  0  Mk      0  とおくと０ 0 0 1  mk 1, k  mn , k M kA A (k) 1 0 0 (k 1)       ，   1  m jk  a jk (k ) a kk ( k) (jk 1 , ,n ) と表せる  a11(1) a12( 1)  最終段まで進むと ( 2)  a22 ( n)  M M M M A U   n  1 n  2 2 1  A  ０   ( 1) a13 ( 2) a 23 ( 3) a33 a1n  ( 2) a 2n  ( 3)  a3n   ( n)  ann  ( 1) AX  b の右辺のベクトルb にも同様の操作 ( n ) を行なえば M M M M b  b n  1 n  2 2 1 AX  b は UX  b(n) となる M k の逆行列は Mk 1 1  0      0  ０ 0 1 mk 1, k 0 1 mn , k 1 0 0 で与えられる（これは Mk Mk I からわかる）         1   1  1 1 2  1  1 n  1 n  1 L  M MM M とおくと  1   m21 m L   31    m  n1 LU  M1 1 0 1 m32 0 0 1 0 0 1 mn 2 mn 3 1 M n 1 M n1 mnn 1 0  0 0   0  1  M1A A であり，これを A の LU 分解というとなる T •対称行列の LDL 分解 A の LU 分解を A  LU とするとき  a11(1 )   D   0  a22 ( 2) U  DV 1   V      v12 v13 1 v23 1 0      (n)  a nn  とおいて v1 n   v2 n   v  ， kj  1   akj (k) akk (k ) (k  j ) と表せる Aが対称行列（A  Aのこと）とする第（ｋ－１）段までで得られた行列第ｋ行以下の小行列を T  ak ,k ( k ) ak , k 1( k )  (k) (k)  a k 1, k ak 1, k 1 (k ) As     a (k ) a (k ) n , k 1  n, k とおくと (k ) As は対称である A (k ) の   (k) ak 1, n    (k ) a n, n  ak ,n (k ) なぜなら，第（ｋ－１）段で行われる変形は aij (k)  aij であるが， alm aml (1)  ( k  1) (1) ai , k  1 ( k 1) ak 1, k 1 ( k  1) ak 1, j であったから aij (2) ( k 1) aji が分かり (2) aij aji とつづき aij aji が分かる．ゆえに As は対称 (3) (3) vkj  (k) (k) akj (k ) akk (k )  a jk (k ) akk (k ) (k )  m jk となり V  LT である．つまり対称行列は A LDL と分解できる． A  LU ,U  DV T より A LDV これを A のLDL 分解という T