アルゴリズムの例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/12 06:28 UTC 版)
コレスキー法はガウスの消去法の改良版である。 ガウスの消去法は A の左方から順次 L を作用させ前進消去（LU分解に対応）するが、 A(i) = Li A(i+1) （ または、A(i+1) = Li−1 A(i) ） コレスキー法は A を順次 L とL* で挟んで前進消去していくと考えればよい。 A(i) = Li A(i+1) L* （ または、A(i+1) = Li−1 A(i) Li−1* ） このとき A(i+1) のエルミート性は保たれる。 詳細は以下の解説を参照。Aが実行列の場合は単純に、エルミート→対称、共役転置→転置と読み替えればよい。 コレスキー分解の再帰的アルゴリズムでは、まず最初に A(1) を下のように置く（定義する）。 A ( 1 ) := A {\displaystyle {\boldsymbol {A}}^{(1)}:={\boldsymbol {A}}} 以下、i 回目のステップを説明する。エルミート性を保ちながら A(i) の i 行と i 列を前進消去して A(i+1) を生成することを考える。A(i) は i − 1 行・列まで前進消去されたエルミート行列であるので、下式のように書ける。 A ( i ) = [ I i − 1 0 0 0 a i , i b i ∗ 0 b i B ( i ) ] {\displaystyle {\boldsymbol {A}}^{(i)}={\begin{bmatrix}{\boldsymbol {I}}_{i-1}&0&0\\0&a_{i,i}&{\boldsymbol {b}}_{i}^{*}\\0&{\boldsymbol {b}}_{i}&{\boldsymbol {B}}^{(i)}\end{bmatrix}}} ここで、Ii−1 は i − 1 次の単位行列、ai, i は i 番目の対角要素、bi は i 列目の下三角部、B(i) は、A(i) のi+1行・列以降の部分でやはりエルミートである。次に、Li を L i := [ I i − 1 0 0 0 a i , i 0 0 1 a i , i b i I n − i ] {\displaystyle {\boldsymbol {L}}_{i}:={\begin{bmatrix}{\boldsymbol {I}}_{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\dfrac {1}{\sqrt {a_{i,i}}}}{\boldsymbol {b}}_{i}&{\boldsymbol {I}}_{n-i}\end{bmatrix}}} と定義するとA(i)は、 A ( i ) = L i A ( i + 1 ) L i ∗ {\displaystyle {\boldsymbol {A}}^{(i)}={\boldsymbol {L}}_{i}{\boldsymbol {A}}^{(i+1)}{\boldsymbol {L}}_{i}^{*}} と書ける（A(i+1) = Li−1 A(i) Li*−1より）。ここで、A(i+1) は A ( i + 1 ) = [ I i − 1 0 0 0 1 0 0 0 B ( i ) − 1 a i , i b i b i ∗ ] {\displaystyle {\boldsymbol {A}}^{(i+1)}={\begin{bmatrix}{\boldsymbol {I}}_{i-1}&0&0\\0&1&0\\0&0&{\boldsymbol {B}}^{(i)}-{\dfrac {1}{a_{i,i}}}{\boldsymbol {b}}_{i}{\boldsymbol {b}}_{i}^{*}\end{bmatrix}}} である（ 注.ここで bi bi* は、行列の積 )。 以上が、i 回目のステップである。これにより、A(i) から A(i+1) が計算出来たことになる。n を A の次数として、このステップを n 回繰り返すと A(i+1) = Inとなりコレスキー分解は終了する。 A ( 1 ) = L 1 L 2 ⋯ L n A ( n + 1 ) L n ∗ ⋯ L 2 ∗ L 1 ∗ {\displaystyle {\boldsymbol {A}}^{(1)}={\boldsymbol {L}}_{1}{\boldsymbol {L}}_{2}\dotsb {\boldsymbol {L}}_{n}{\boldsymbol {A}}^{(n+1)}{\boldsymbol {L}}_{n}^{*}\dotsb {\boldsymbol {L}}_{2}^{*}{\boldsymbol {L}}_{1}^{*}} であり、 L := L 1 L 2 ⋯ L n {\displaystyle {\boldsymbol {L}}:={\boldsymbol {L}}_{1}{\boldsymbol {L}}_{2}\dotsb {\boldsymbol {L}}_{n}} と置くと、（これが最終的に求める L である。） A = L L ∗ {\displaystyle {\boldsymbol {A}}={\boldsymbol {L}}{\boldsymbol {L}}^{*}} であることが確認できる。
※この「アルゴリズムの例」の解説は、「コレスキー分解」の解説の一部です。
「アルゴリズムの例」を含む「コレスキー分解」の記事については、「コレスキー分解」の概要を参照ください。
- アルゴリズムの例のページへのリンク
