声明 エルミート 正定値行列 A
A = L L * 、 {\displaystyle \mathbf {A} =\mathbf {LL} ^{*},}
ここで、L 下三角行列であり、 L L 共役転置 を表します。すべてのエルミート正定値行列 (したがってすべての実対称正定値行列も) はコレスキー分解を持ち、対角成分が厳密に正であるという制約を課せば、下三角行列は一意になります。[ 3 ]
逆もまた自明である。Aが Lに対して LL *A
A A = L L T 、 {\displaystyle \mathbf {A} =\mathbf {LL} ^{\mathsf {T}},} L [ 4 ] [ 5 ] [ 6 ]
正定値半行列 エルミート行列A A = LL *の形の分解が存在し、 L [ 7 ] [ 0 0 0 1 ] = L L * 、 L = [ 0 0 コス θ 罪 θ ] 、 {\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}=\mathbf {L} \mathbf {L} ^{*},\quad \quad \mathbf {L} ={\begin{bmatrix}0&0\\\cos \theta &\sin \theta \end{bmatrix}},} 任意のθ に対して。ただし、 A r の場合、ちょうどr 個 の正の対角要素とn − r L が [ 8 ]
あるいは、ピボット選択が固定されている場合、分解は一意にすることができます。形式的には、A がランクrの n × n PAP Tが PAP T = LL * 置換行列 P が L = [ L 1 0 L 2 0 ] {\textstyle \mathbf {L} ={\begin{bmatrix}\mathbf {L} _{1}&0\\\mathbf {L} _{2}&0\end{bmatrix}}} L 1は正の対角成分を持つ r × r の [ 9 ]
LDL分解 古典的なコレスキー分解と密接に関連する変種として、LDL分解（バンチ・カウフマン分解とも呼ばれる）がある[ 10 ]。
A = L D L * 、 {\displaystyle \mathbf {A} =\mathbf {LDL} ^{*},}
ここで、L 下三角（単位三角） 行列、D は対角 行列です。つまり、分解において追加の対角行列D L [ 11 ]
このため、LDL 分解はしばしば平方根フリーのコレスキー 分解と呼ばれます。実数行列の場合、因数分解はA = LDL Tの形をとり、しばしば LDLT 分解LDL T LDL′ )と呼ばれます。これは実数対称行列の固有値分解 A = QΛQ T Λ D は 相似行列 ではないため、実際にはかなり異なります。
LDL分解は、LL *
A = L D L * = L D 1 / 2 （ D 1 / 2 ） * L * = L D 1 / 2 （ L D 1 / 2 ） * 。 {\displaystyle \mathbf {A} =\mathbf {LDL} ^{*}=\mathbf {L} \mathbf {D} ^{1/2}\left(\mathbf {D} ^{1/2}\right)^{*}\mathbf {L} ^{*}=\mathbf {L} \mathbf {D} ^{1/2}\left(\mathbf {L} \mathbf {D} ^{1/2}\right)^{*}.}
逆に、古典的なコレスキー分解を考えるとA = C C * {\textstyle \mathbf {A} =\mathbf {C} \mathbf {C} ^{*}} S が 主対角 成分を含む対角行列である場合C {\textstyle \mathbf {C} } Aは L D L * {\textstyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}} L = C S − 1 \displaystyle \mathbf {L} =\mathbf {C} \mathbf {S} ^{-1}} D = S S * 。 {\displaystyle \mathbf {D} =\mathbf {S} \mathbf {S} ^{*}.}
A D A L D L * {\textstyle \mathbf {L} \mathbf {D} \mathbf {L} ^{*}} 対角D A [ 12 ] コレスキー分解が存在しない不定行列の中には、 D n − 1 個の主小行列 式が非特異であれば十分である。[ 13 ]
例 対称な実数行列のコレスキー分解を以下に示します。
（ 4 12 − 16 12 37 − 43 − 16 − 43 98 ） = （ 2 0 0 6 1 0 − 8 5 3 ） （ 2 6 − 8 0 1 5 0 0 3 ） 。 {\displaystyle {\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}={\begin{pmatrix}2&0&0\\6&1&0\\-8&5&3\\\end{pmatrix}}{\begin{pmatrix}2&6&-8\\0&1&5\\0&0&3\\\end{pmatrix}}.\end{aligned}}}
そして、これがLDL T 分解です。
（ 4 12 − 16 12 37 − 43 − 16 − 43 98 ） = （ 1 0 0 3 1 0 − 4 5 1 ） （ 4 0 0 0 1 0 0 0 9 ） （ 1 3 − 4 0 1 5 0 0 1 ） 。 {\displaystyle {\begin{aligned}{\begin{pmatrix}4&12&-16\\12&37&-43\\-16&-43&98\\\end{pmatrix}}&={\begin{pmatrix}1&0&0\\3&1&0\\-4&5&1\\\end{pmatrix}}{\begin{pmatrix}4&0&0\\0&1&0\\0&0&9\\\end{pmatrix}}{\begin{pmatrix}1&3&-4\\0&1&5\\0&0&1\\\end{pmatrix}}.\end{aligned}}}
アプリケーション
線形最小二乗法 線形最小二乗 問題では、過剰決定系Ax = lの解 x を Ax-l N x = A T l {\displaystyle \mathbf {Nx} =\mathbf {A} ^{\mathsf {T}}\mathbf {l} } N = A T A {\displaystyle \mathbf {N} =\mathbf {A} ^{\mathsf {T}}\mathbf {A} } 偏微分方程式 の数値解法でよく起こります。
このような方法は経済的で多くの用途でうまく機能しますが、特異点に近い N A {\displaystyle \mathbf {A} } ここで、 N Ax = lの行列式の二乗です。この場合、SVD または QR 分解を適用するのが最適です。Givens QR には、通常の方程式と同様に、行列 A A
カルマンフィルター 無香料カルマンフィルタは 、一般的にコレスキー分解を用いて、いわゆるシグマ点のセットを選択します。カルマンフィルタは、システムの平均状態を長さN のベクトルx N × N P P LL T に分解できます。Lの列は、平均x シグマ点と呼ばれる 2N 個 、
行列の逆行列 エルミート行列の明示的な逆行列は 、線形システムを解くのと同様の方法で、コレスキー分解によって計算できます。n 3 {\textstyle n^{3}} 1 2 n 3 {\textstyle {\tfrac {1}{2}}n^{3}} [ 11 ]
非エルミート行列B BB * は常にエルミート行列となります。
B − 1 = B * （ B B * ） − 1 。 {\displaystyle \mathbf {B} ^{-1}=\mathbf {B} ^{*}(\mathbf {BB} ^{*})^{-1}.}
データ補完 コレスキー分解はデータの補完にも使用できます。他のデータ補完アルゴリズムの中でも、期待値最大化アルゴリズムのバリエーションはコレスキー分解を利用しています。[ 18 ]
計算 コレスキー分解を計算する方法はいくつかあります。一般的に使用されるアルゴリズムの計算複雑度はO ( n³ )[ 19 ] : ( 1/3 ) n³FLOPs ( n³ / 6 回 の 乗算と同数の加算)、複素フレーバーの場合(4/3) n³FLOPs を必要とします [ 20 ]。 ここ nは行列 A 2n³ / 3FLOPsを使用するLU分解 の半分のコストです(TrefethenとBau 1997を
以下のアルゴリズムのうちどちらが速いかは、実装の詳細によって異なります。一般的に、最初のアルゴリズムはデータへのアクセスが不規則なため、若干遅くなります。コレスキー分解は、ピボット操作を必要とせずに数値的に安定していることが示されています。[ 21 ]
コレスキー分解アルゴリズム 分解行列L スキー分解アルゴリズムは、 ガウス消去法 の改良版です。
再帰アルゴリズムはi := 1
A (1) := A ステップi において、行列A ( i ) A （ 私 ） = （ 私 私 − 1 0 0 0 1 私 、 私 b 私 * 0 b 私 B （ 私 ） ） 、 {\displaystyle \mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},} I i −1はi − 1 次元の単位行列 を表す。
行列L i L 私 := （ 私 私 − 1 0 0 0 1 私 、 私 0 0 1 1 私 、 私 b 私 私 n − 私 ） 、 {\displaystyle \mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},} （ A ( i ) a i,i A ( i ) A （ 私 ） = L 私 A （ 私 + 1 ） L 私 * {\displaystyle \mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}} A （ 私 + 1 ） = （ 私 私 − 1 0 0 0 1 0 0 0 B （ 私 ） − 1 1 私 、 私 b 私 b 私 * ） 。 {\displaystyle \mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.} b i b i 外積である ことに注意してください。したがって、このアルゴリズムは(Golub & Van Loan) では外積バージョンと呼ばれています。
これはi が1 からn まで繰り返されます。nステップ 後、A ( n +1) = I L は次のように計算されます。
L := L 1 L 2 … L n 。 {\displaystyle \mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.}
5×5行列に対するインプレース・コレスキー・バナキエヴィッチアルゴリズムのアクセスパターン（白）と書き込みパターン（黄） 方程式が A = L L T = （ L 11 0 0 L 21 L 22 0 L 31 L 32 L 33 ） （ L 11 L 21 L 31 0 L 22 L 32 0 0 L 33 ） = （ L 11 2 （ 対称的 ） L 21 L 11 L 21 2 + L 22 2 L 31 L 11 L 31 L 21 + L 32 L 22 L 31 2 + L 32 2 + L 33 2 ） 、 {\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\begin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\end{pmatrix}}\\[8pt]&={\begin{pmatrix}L_{11}^{2}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}}
書き出すと、次の結果が得られます。
L = （ A 11 0 0 A 21 / L 11 A 22 − L 21 2 0 A 31 / L 11 （ A 32 − L 31 L 21 ） / L 22 A 33 − L 31 2 − L 32 2 ） {\displaystyle {\begin{aligned}\mathbf {L} ={\begin{pmatrix}{\sqrt {A_{11}}}&0&0\\A_{21}/L_{11}&{\sqrt {A_{22}-L_{21}^{2}}}&0\\A_{31}/L_{11}&\left(A_{32}-L_{31}L_{21}\right)/L_{22}&{\sqrt {A_{33}-L_{31}^{2}-L_{32}^{2}}}\end{pmatrix}}\end{aligned}}}
したがって、 L
L j 、 j = （ ± ） A j 、 j − ∑ k = 1 j − 1 L j 、 k 2 、 {\displaystyle L_{j,j}=(\pm ){\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{2}}},} L 私 、 j = 1 L j 、 j （ A 私 、 j − ∑ k = 1 j − 1 L 私 、 k L j 、 k ） のために 私 > j 。 {\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right)\quad {\text{for }}i>j.}
複素行列および実数行列の場合、対角要素およびそれに関連する非対角要素の符号が任意に変化しても、結果に影響はありません。Aが 平方根 の中の式は常に正になります。
複素エルミート行列の場合、以下の式が適用されます。
L j 、 j = A j 、 j − ∑ k = 1 j − 1 L j 、 k * L j 、 k 、 {\displaystyle L_{j,j}={\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{j,k}}},} L 私 、 j = 1 L j 、 j （ A 私 、 j − ∑ k = 1 j − 1 L j 、 k * L 私 、 k ） のために 私 > j 。 {\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{i,k}\right)\quad {\text{for }}i>j.}
そして、次のことが示せる。L j 、 j {\displaystyle L_{j,j}} A 実数 かつ正の値をとる。 [ 22 ] ： 49
したがって、左と上のエントリが分かっていれば、( i , j ) エントリを計算することが可能です。計算は通常、以下のいずれかの順序で行われます。
チョレスキー・バナキエヴィッチアルゴリズムは、行列 L の左上隅から開始し、行列を1行ずつ計算していきます。 for ( i = 0 ; i < dimensionSize ; i ++ ) { for ( j = 0 ; j <= i ; j ++ ) { float sum = 0 ; for ( k = 0 ; k < j ; k ++ ) sum += L [ i ][ k ] * L [ j ][ k ]; if ( i == j ) L [ i ][ j ] = sqrt ( A [ i ][ i ] - sum ); else L [ i ][ j ] = ( 1.0 / L [ j ][ j ] * ( A [ i ][ j ] - sum )); } } 上記のアルゴリズムは、 Fortran などのベクトル化プログラミング言語において、ドット積 と行列乗算 を組み合わせたものとして、以下のように簡潔に表現できます。
do i = 1 , size ( A , 1 ) L ( i , i ) = sqrt ( A ( i , i ) - dot_product ( L ( i , 1 : i - 1 ), L ( i , 1 : i - 1 ))) L ( i + 1 :, i ) = ( A ( i + 1 :, i ) - matmul ( conjg ( L ( i , 1 : i - 1 )), L ( i + 1 :, 1 : i - 1 ))) / L ( i , i ) end do ここで、 はconjg要素の複素共役を表します。
チョレスキー・クラウト法は、行列 L の左上隅から開始し、行列を列ごとに計算していく。for ( j = 0 ; j < dimensionSize ; j ++ ) { float sum = 0 ; for ( k = 0 ; k < j ; k ++ ) { sum += L [ j ][ k ] * L [ j ][ k ]; } L [ j ][ j ] = sqrt ( A [ j ][ j ] - sum ); for ( i = j + 1 ; i < dimensionSize ; i ++ ) { sum = 0 ; for ( k = 0 ; k < j ; k ++ ) { sum += L [ i ][ k ] * L [ j ][ k ]; } L [ i ][ j ] = ( 1.0 / L [ j ][ j ] * ( A [ i ][ j ] - sum )); } } 上記のアルゴリズムは、 Fortran などのベクトル化プログラミング言語において、ドット積 と行列乗算 を組み合わせたものとして、以下のように簡潔に表現できます。
do i = 1 , size ( A , 1 ) L ( i , i ) = sqrt ( A ( i , i ) - dot_product ( L ( 1 : i - 1 , i ), L ( 1 : i - 1 , i ))) L ( i , i + 1 :) = ( A ( i , i + 1 :) - matmul ( conjg ( L ( 1 : i - 1 , i )), L ( 1 : i - 1 , i + 1 :))) / L ( i , i ) end do ここで、 はconjg要素の複素共役を表します。
どちらのアクセス方式でも、必要に応じて計算全体をその場で実行できます。
計算の安定性 条件の良い連立 一次方程式を解きたいとします。LU分解を用いる場合、何らかのピボット戦略を用いない限り、アルゴリズムは不安定になります。後者の場合、誤差は行列のいわゆる成長率に依存しますが、これは通常（常にではありませんが）小さい値です。
さて、コレスキー分解が適用可能だと仮定します。前述のように、アルゴリズムは2倍速くなります。さらに、ピボット操作は 不要で、誤差は常に小さくなります。具体的には、Ax = b y が y は A + E ) y = b ‖ E ‖ 2 ≤ c n ε ‖ A ‖ 2 。 {\displaystyle \|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.} 2 は行列の 2 ノルム 、c n はn に依存する小さな定数、ε は 単位丸め を表します。
コレスキー分解で注意すべき点の1つは、平方根の使用です。因数分解される行列が要求どおり正定値であれば、平方根の中の数値は厳密な算術演算では常に正になります。残念ながら、 丸め誤差 のために数値が負になる可能性があり、その場合はアルゴリズムを続行できません。ただし、これは行列の条件が非常に悪い場合にのみ発生します。これに対処する1つの方法は、正定値性を促進するために、分解される行列に対角補正行列を追加することです。[ 23 ] 最適化でニュートン法 を実行する場合、対角行列を追加すると、最適値から遠い場合の安定性が向上します。
LDL分解 A [ 22 ] ： 84A = L D L T = （ 1 0 0 L 21 1 0 L 31 L 32 1 ） （ D 1 0 0 0 D 2 0 0 0 D 3 ） （ 1 L 21 L 31 0 1 L 32 0 0 1 ） = （ D 1 （ s y m m e t r 私 c ） L 21 D 1 L 21 2 D 1 + D 2 L 31 D 1 L 31 L 21 D 1 + L 32 D 2 L 31 2 D 1 + L 32 2 D 2 + D 3 。 ） 。 {\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}D_{1}&&(\mathrm {symmetric} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}.\end{pmatrix}}.\end{aligned}}}
D L D j = A j j − ∑ k = 1 j − 1 L j k 2 D k 、 {\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}^{2}D_{k},} L 私 j = 1 D j （ A 私 j − ∑ k = 1 j − 1 L 私 k L j k D k ） のために 私 > j 。 {\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}D_{k}\right)\quad {\text{for }}i>j.}
これは、 D が実数であれば、 D L も
複素エルミート行列A
D j = A j j − ∑ k = 1 j − 1 L j k L j k * D k 、 {\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}L_{jk}^{*}D_{k},} L 私 j = 1 D j （ A 私 j − ∑ k = 1 j − 1 L 私 k L j k * D k ） のために 私 > j 。 {\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}D_{k}\right)\quad {\text{for }}i>j.}
繰り返しになりますが、このアクセスパターンにより、必要に応じて計算全体をその場で実行することが可能になります。
ブロックバリアント 不定行列で使用する場合、LDL * 因数分解は慎重なピボット操作なしでは不安定であることが知られています。[ 24 ] [ 25 ]
A = L D L T = （ 私 0 0 L 21 私 0 L 31 L 32 私 ） （ D 1 0 0 0 D 2 0 0 0 D 3 ） （ 私 L 21 T L 31 T 0 私 L 32 T 0 0 私 ） = （ D 1 （ s y m m e t r 私 c ） L 21 D 1 L 21 D 1 L 21 T + D 2 L 31 D 1 L 31 D 1 L 21 T + L 32 D 2 L 31 D 1 L 31 T + L 32 D 2 L 32 T + D 3 ） 、 {\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}\mathbf {I} &0&0\\\mathbf {L} _{21}&\mathbf {I} &0\\\mathbf {L} _{31}&\mathbf {L} _{32}&\mathbf {I} \\\end{pmatrix}}{\begin{pmatrix}\mathbf {D} _{1}&0&0\\0&\mathbf {D} _{2}&0\\0&0&\mathbf {D} _{3}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {I} &\mathbf {L} _{21}^{\mathrm {T} }&\mathbf {L} _{31}^{\mathrm {T} }\\0&\mathbf {I} &\mathbf {L} _{32}^{\mathrm {T} }\\0&0&\mathbf {I} \\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}\mathbf {D} _{1}&&(\mathrm {symmetric} )\\\mathbf {L} _{21}\mathbf {D} _{1}&\mathbf {L} _{21}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {D} _{2}&\\\mathbf {L} _{31}\mathbf {D} _{1}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{31}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}\mathbf {L} _{32}^{\mathrm {T} }+\mathbf {D} _{3}\end{pmatrix}},\end{aligned}}}
上記の行列の各要素は正方部分行列である。このことから、以下の類似した再帰関係が導かれる。
D j = A j j − ∑ k = 1 j − 1 L j k D k L j k T 、 {\displaystyle \mathbf {D} _{j}=\mathbf {A} _{jj}-\sum _{k=1}^{j-1}\mathbf {L} _{jk}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} },} L 私 j = （ A 私 j − ∑ k = 1 j − 1 L 私 k D k L j k T ） D j − 1 。 {\displaystyle \mathbf {L} _{ij}=\left(\mathbf {A} _{ij}-\sum _{k=1}^{j-1}\mathbf {L} _{ik}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} }\right)\mathbf {D} _{j}^{-1}.}
これには行列積と明示的な逆行列計算が含まれるため、実用的なブロックサイズが制限される。
分解の更新 実務でよく発生するタスクは、コレスキー分解を更新する必要があることです。より詳細には、すでにコレスキー分解を計算しています。A = L L * {\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}} A {\textstyle \mathbf {A} } A {\textstyle \mathbf {A} } A ～ {\textstyle {\tilde {\mathbf {A} }}} A ～ = L ～ L ～ * {\textstyle {\tilde {\mathbf {A} }}={\tilde {\mathbf {L} }}{\tilde {\mathbf {L} }}^{*}} A {\textstyle \mathbf {A} } A ～ {\textstyle {\tilde {\mathbf {A} }}}
行と列の追加と削除 対称かつ正定値行列の場合A {\textstyle \mathbf {A} }
A = （ A 11 A 13 A 13 T A 33 ） {\displaystyle \mathbf {A} ={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}}
そしてその上位コレスキー因子 L = （ L 11 L 13 0 L 33 ） 、 {\displaystyle \mathbf {L} ={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}},}
次に新しい行列についてA ～ {\textstyle {\tilde {\mathbf {A} }}} A {\textstyle \mathbf {A} } A ～ = （ A 11 A 12 A 13 A 12 T A 22 A 23 A 13 T A 23 T A 33 ） {\displaystyle {\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}}
現在、のコレスキー分解を見つけることに関心が集まっている。A ～ {\textstyle {\tilde {\mathbf {A} }}} S ～ {\textstyle {\tilde {\mathbf {S} }}} S ～ = （ S 11 S 12 S 13 0 S 22 S 23 0 0 S 33 ） 。 {\displaystyle {\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}.\end{aligned}}}
書き込みA ∖ b {\textstyle \mathbf {A} \setminus \mathbf {b} } A x = b {\textstyle \mathbf {A} \mathbf {x} =\mathbf {b} } チョル （ M ） {\textstyle {\text{chol}}(\mathbf {M} )} M {\textstyle \mathbf {M} } S 11 = L 11 、 S 12 = L 11 T ∖ A 12 、 S 13 = L 13 、 S 22 = c h o l （ A 22 − S 12 T S 12 ） 、 S 23 = S 22 T ∖ （ A 23 − S 12 T S 13 ） 、 S 33 = c h o l （ L 33 T L 33 − S 23 T S 23 ） 。 {\displaystyle {\begin{aligned}\mathbf {S} _{11}&=\mathbf {L} _{11},\\\mathbf {S} _{12}&=\mathbf {L} _{11}^{\mathrm {T} }\setminus \mathbf {A} _{12},\\\mathbf {S} _{13}&=\mathbf {L} _{13},\\\mathbf {S} _{22}&=\mathrm {chol} \left(\mathbf {A} _{22}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{12}\right),\\\mathbf {S} _{23}&=\mathbf {S} _{22}^{\mathrm {T} }\setminus \left(\mathbf {A} _{23}-\mathbf {S} _{12}^{\mathrm {T} }\mathbf {S} _{13}\right),\\\mathbf {S} _{33}&=\mathrm {chol} \left(\mathbf {L} _{33}^{\mathrm {T} }\mathbf {L} _{33}-\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}}
これらの式は、行と列の寸法が適切に設定されている（ゼロを含む）場合、任意の位置に行または列を挿入した後のコレスキー因子を決定するために使用できます。逆問題、
A ～ = （ A 11 A 12 A 13 A 12 T A 22 A 23 A 13 T A 23 T A 33 ） {\displaystyle {\begin{aligned}{\tilde {\mathbf {A} }}&={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}\\\mathbf {A} _{12}^{\mathrm {T} }&\mathbf {A} _{22}&\mathbf {A} _{23}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{23}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}}\end{aligned}}} S ～ = （ S 11 S 12 S 13 0 S 22 S 23 0 0 S 33 ） {\displaystyle {\begin{aligned}{\tilde {\mathbf {S} }}&={\begin{pmatrix}\mathbf {S} _{11}&\mathbf {S} _{12}&\mathbf {S} _{13}\\0&\mathbf {S} _{22}&\mathbf {S} _{23}\\0&0&\mathbf {S} _{33}\\\end{pmatrix}}\end{aligned}}}
そして、コレスキー因子を決定したいという願望 L = （ L 11 L 13 0 L 33 ） {\displaystyle {\begin{aligned}\mathbf {L} &={\begin{pmatrix}\mathbf {L} _{11}&\mathbf {L} _{13}\\0&\mathbf {L} _{33}\\\end{pmatrix}}\end{aligned}}}
行列のA {\textstyle \mathbf {A} } A = （ A 11 A 13 A 13 T A 33 ） 、 {\displaystyle {\begin{aligned}\mathbf {A} &={\begin{pmatrix}\mathbf {A} _{11}&\mathbf {A} _{13}\\\mathbf {A} _{13}^{\mathrm {T} }&\mathbf {A} _{33}\\\end{pmatrix}},\end{aligned}}}
次のようなルールが得られます。 L 11 = S 11 、 L 13 = S 13 、 L 33 = c h o l （ S 33 T S 33 + S 23 T S 23 ） 。 {\displaystyle {\begin{aligned}\mathbf {L} _{11}&=\mathbf {S} _{11},\\\mathbf {L} _{13}&=\mathbf {S} _{13},\\\mathbf {L} _{33}&=\mathrm {chol} \left(\mathbf {S} _{33}^{\mathrm {T} }\mathbf {S} _{33}+\mathbf {S} _{23}^{\mathrm {T} }\mathbf {S} _{23}\right).\end{aligned}}}
新しい行列のコレスキー分解を求める上記の式はすべて次の形式であることに注意してください。A ～ = A + c x x * {\textstyle {\tilde {\mathbf {A} }}=\mathbf {A} +c\,\mathbf {x} \mathbf {x} ^{*}} c = ± 1 {\displaystyle c=\pm 1} [ 19 ]
一般化 コレスキー分解は、演算子成分を持つ（必ずしも有限ではない）行列に一般化できる。{ H n } {\textstyle \{{\mathcal {H}}_{n}\}} ヒルベルト空間 の列とする。演算子行列を考える。
A = [ A 11 A 12 A 13 A 12 * A 22 A 23 A 13 * A 23 * A 33 ⋱ ] {\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{11}&\mathbf {A} _{12}&\mathbf {A} _{13}&\;\\\mathbf {A} _{12}^{*}&\mathbf {A} _{22}&\mathbf {A} _{23}&\;\\\mathbf {A} _{13}^{*}&\mathbf {A} _{23}^{*}&\mathbf {A} _{33}&\;\\\;&\;&\;&\ddots \end{bmatrix}}}
直接和に作用する
H = ⨁ n H n 、 {\displaystyle {\mathcal {H}}=\bigoplus _{n}{\mathcal {H}}_{n},}
それぞれ
A 私 j : H j → H 私 {\displaystyle \mathbf {A} _{ij}:{\mathcal {H}}_{j}\rightarrow {\mathcal {H}}_{i}}
は有界作用素 である。A が正（半正定値）である場合、すべて k および任意の に対してが成り立つ。
h ∈ ⨁ n = 1 k H k 、 {\displaystyle h\in \bigoplus _{n=1}^{k}{\mathcal {H}}_{k},}
がある⟨ h 、 A h ⟩ ≥ 0 {\textstyle \langle h,\mathbf {A} h\rangle \geq 0} すると、 A = LL * L の
プログラミングライブラリにおける実装 C言語 ：GNU科学ライブラリに は、コレスキー分解の実装がいくつか用意されています。Maxima コンピュータ代数システム ：choleskyコレスキー分解を計算する関数。GNU Octave 数値計算システムは、コレスキー分解を計算、更新、適用するためのいくつかの関数を提供します。LAPACKライブラリは、 Fortran 、C 、およびほとんどの言語からアクセスできる、高性能なコレスキー分解の実装を提供します。コレスキー分解は*POTRFサブルーチン群を通じて、LDL分解は*HETRFサブルーチン群を通じて利用可能です。 Python では、モジュールcholesky内の関数がnumpy.linalgコレスキー分解を実行します。このscipy.linalgモジュールにはldl、LDL分解を行う関数が含まれています。Matlab では、このchol関数はコレスキー分解を返します。cholデフォルトでは入力行列の上三角因子を使用することに注意してください。つまり、A = R * R {\textstyle A=R^{*}R} R {\textstyle R} R では、このchol関数は上三角コレスキー因子を返します[ 26 ] Julia では、標準ライブラリcholeskyの関数でLinearAlgebraコレスキー分解を実行できます。Mathematica では、関数 " CholeskyDecomposition" を行列に適用できます。C++ では、複数の線形代数ライブラリがこの分解をサポートしています。 Armadillo （C++ライブラリ） は、コレスキー分解を実行するためのコマンドを提供しますchol。 Eigenライブラリは、 疎行列と密行列の両方に対するコレスキー分解を提供します。 ROOT パッケージには、そのTDecompCholクラスが含まれています。Analytica では、この関数はDecomposeコレスキー分解を返します。Apache Commons Mathライブラリには、Java、Scala、およびその他のJVM言語で使用できる実装が含まれています。
注記 ↑ ブノワ（1924年）。 「Note sur une méthode de résolution des équations Normales proventant de l'application de la methode des moindres carrés à un système d'équations linéaires en nombre inférieur à celui des inconnues (Procédé du Commandant Cholesky)」。Bulletin Géodésique 2 : 66–67 。土井 : 10.1007/BF03031308。 1 2 Press, William H.; Saul A. Teukolsky; William T. Vetterling; Brian P. Flannery (1992). Numerical Recipes in C: The Art of Scientific Computing (second ed.). Cambridge University Press. pp. 96-97 . ISBN 0-521-43108-5 2025年7月29日 に取得 。↑ Golub & Van Loan (1996 , p. 143) 、 Horn & Johnson (1985 , p. 407) 、 Trefethen & Bau (1997 , p. 174) 。 ↑ Horn & Johnson (1985 、p. 407) 。 ↑ 「行列 - 複素対称行列の対角化」 。MathOverflow 。 2020年1月25日 取得 。 ↑ Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (2010-05-01). "Toward a parallel solver for generalized complex symmetric eigenvalue problems" . Procedia Computer Science . ICCS 2010. 1 (1): 437– 445. doi : 10.1016/j.procs.2010.04.047 . ISSN 1877-0509 . ↑ ゴラブと ヴァン・ローン (1996 年 、147 ページ ) 。 ↑ ジェントル、ジェームズ E. (1998). 統計学への応用における数値線形代数 . Springer. p. 94. ISBN 978-1-4612-0623-1 。↑ Higham, Nicholas J. (1990). "半正定値行列のコレスキー分解の解析" .In Cox, MG; Hammarling, SJ (eds.). Reliable Numerical Computation . Oxford, UK: Oxford University Press. pp. 161–185 . ISBN 978-0-19-853564-5 。↑ Bunch, James R.; Kaufman, Linda (1977). "慣性を計算し対称線形システムを解くためのいくつかの安定した方法". Mathematics of Computation . 31 (137): 163– 179. doi : 10.1090/S0025-5718-1977-0428694-0 . 1 2 Krishnamoorthy, Aravindh; Menon, Deepak. "Matrix Inversion Using Cholesky Decomposition". 2013 Signal Processing: Algorithms, Architectures, Arrangements, and Applications (SPA) . IEEE. pp. 70– 72. arXiv : 1111.4144 . ↑ Anthony Man-Cho (2007). A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions (PDF) (PhD). Theorem 2.2.6. ↑ Golub & Van Loan (1996 、定理4.1.3) ↑ Pope, Stephen B.「楕円体のためのアルゴリズム」コーネル大学レポートNo. FDA (2008): 08-01。 ↑ Schwarzenberg-Czerny, A. (1995). "行列分解と効率的な最小二乗解について". Astronomy and Astrophysics Supplement . 110 : 405– 410. Bibcode : 1995A & AS..110..405S . ↑ Arora, Jasbir Singh (2004-06-02). 最適設計入門 . Elsevier. ISBN 978-0-08-047025-2 。↑ Matlab randn のドキュメント。mathworks.com。 ↑ William Morokoff、「欠損データのある共分散推定のためのブラウンブリッジEMアルゴリズム」、Journal of Computational Finance。 1 2 3 Botev, Zdravko I.; Kroese, Dirk P.; Taimre , Thomas ( 2025). データサイエンスと機械学習：数学的および統計的手法 （第2 版）。ボカラトン 、ロンドン：CRC Press。pp. 545–546。ISBN 978-1-032-48868-4 。↑ ?potrf Intel® 数学カーネルライブラリ ↑ Turing, AM (1948). "行列処理における丸め誤差". Quart. J. Mech. Appl. Math . 1 : 287– 308. doi : 10.1093/qjmam/1.1.287 . 1 2 ワトキンス、D. (1991). 行列計算の基礎 . ニューヨーク: ワイリー. ISBN 0-471-61414-9 。↑ Fang, Haw-ren; O'Leary, Dianne P. (2008). "修正コレスキーアルゴリズム: 新しいアプローチのカタログ" (PDF) . Mathematical Programming . 115 (2): 319– 349. doi : 10.1007/s10107-007-0177-6 . hdl : 1903/3674 . MR 2411401 . ↑ ノセダル、ホルヘ (2000). 数値最適化 . スプリンガー. ↑ 方浩仁 (2011). 「ブロックの安定性解析」 L D L T {\displaystyle LDL^{T}} 「 対称不定行列の因数分解」。IMA Journal of Numerical Analysis。31 ( 2): 528–555。doi : 10.1093/imanum / drp053。MR 2813183 。 ↑ "CRAN: マニュアル" . cran.r-project.org . 2026-05-27 に取得.
参考文献 Dereniowski, Dariusz; Kubale, Marek (2004). "並列処理による行列のコレスキー分解とグラフのランキング".第5回並列処理と応用数学に関する国際会議 (PDF) . Lecture Notes on Computer Science. Vol. 3019. Springer-Verlag. pp. 985–992 . doi : 10.1007/978-3-540-24669-5_127 . ISBN 978-3-540-21946-0 2011年7月16日にオリジナル（PDF） からアーカイブされました。 Golub, Gene H. ; Van Loan, Charles F. (1996).行列計算 （第3 版）. ボルチモア：ジョンズ・ホプキンス大学出版局. ISBN 978-0-8018-5414-9 。ホーン、ロジャー A.、ジョンソン、チャールズ R. (1985).行列解析 . ケンブリッジ大学出版局. ISBN 0-521-38632-2 。 SJ Julier および JK Uhlmann。「確率分布の非線形変換を近似するための一般的な方法」。 SJ Julier および JK Uhlmann、「非線形システムへのカルマンフィルタの新しい拡張」、Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls、1997、pp. 182–193。 トレフェセン、ロイド・N. 、バウ、デイビッド（1997）。数値線形代数 。フィラデルフィア：応用数理学会。ISBN 978-0-89871-361-9 。オズボーン、マイケル（2010）。逐次予測、最適化、および求積のためのベイズガウス過程 （PDF） （学位論文）。オックスフォード大学。 Ruschel、João Paulo Tarasconi、学士号「CPU および GPU でのコレスキー分解の並列実装」、リオグランデドスル大学、Instituto De Informatica、2016 年、 29-30 ページ。
外部リンク
科学史 コレスキーの 1910 年の原稿、 Sur la résolution numérique des systèmes d'équations linéaires 、オンラインでBibNumで分析されています(フランス語と英語) [英語の場合は、「A Télécharger」をクリックしてください]
「コレスキー分解」 .数学百科事典 EMS Press . 2001 [1994]. コレスキー分解、データ分析概要書 www.math-linux.com のコレスキー分解 サイエンス・ミーアンダーサルによるコレスキー分解の解説
コンピュータコード LAPACKは、密な線形代数問題を解くためのFORTRANサブルーチンのコレクションです（DPOTRF、DPOTRF2、詳細パフォーマンス）。 ALGLIBには、LAPACKをC++、C#、Delphi、Visual Basicなどに部分的に移植したものが含まれています（spdmatrixcholesky、hpdmatrixcholesky）。 libflameはLAPACK機能を備えたCライブラリです。 テキサス大学オースティン校における、高性能なコレスキー分解の実装に関する資料と動画。 Cholesky : TBB + Threads + SSEは、TBB、スレッド、SSE を使用した CF の実装について解説した書籍です (スペイン語)。 Googleのライブラリ「Ceres Solver」 。 MatlabにおけるLDL分解ルーチン。 ArmadilloはC++の線形代数パッケージです。 Rosetta Code はプログラミングの選集サイトです。ページトピック。AlgoWikiは、アルゴリズムの特性と実装の特徴に関するオープンな百科事典です。 Intel® oneAPI 数学カーネルライブラリ数値計算向け Intel 最適化数学ライブラリ?potrf、?potrs
オンライン計算機 オンライン行列計算機は、行列のコレスキー分解をオンラインで実行します。
![{\textstyle V:=[v_{1}|v_{2}|\cdots |v_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/266ae54052e54b96385ac91dcbadcb5ada055f64)
![{\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\b egin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\end{pmatrix}}\\[8pt]&={\begi n{pmatrix}L_{11}^{2}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1698aea6d96c9be0ed8606821c0e07abc9487154)
![{\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}D_{1}&&(\mathrm {symmetric} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}.\end{pmatrix}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d868f0fc4a5a5f40e7e850e5b160e9b4db76333)
![{\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}\mathbf {I} &0&0\\\mathbf {L} _{21}&\mathbf {I} &0\\\mathbf {L} _{31}&\mathbf {L} _{32}&\mathbf {I} \\\end{pmatrix}}{\begin{pmatrix}\mathbf {D} _{1}&0&0\\0&\mathbf {D} _{2}&0\\0&0&\mathbf {D} _{3}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {I} &\mathbf {L} _{21}^{\mathrm {T} }&\mathbf {L} _{31}^{\mathrm {T} }\\0&\mathbf {I} &\mathbf {L} _{32}^{\mathrm {T} }\\0&0&\mathbf {I} \\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}\mathbf {D} _{1}&&(\mathrm {対称} )\\\mathbf {L} _{21}\mathbf {D} _{1}&\mathbf {L} _{21}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {D} _{2}&\\\mathbf {L} _{31}\mathbf {D} _{1}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{31}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}\mathbf {L} _{32}^{\mathrm {T} }+\mathbf {D} _{3}\end{pmatrix}},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fbf0e24f33c7f7d431f83dad4a5fc95e2b0b3cc)
