跳至內容

科列斯基分解

出自Taiwan Tongues 台語維基
於 2025年8月23日 (六) 11:06 由 TaiwanTonguesApiRobot​（留言 | 貢獻） 所做的修訂 （從 JSON 檔案批量匯入）

(差異) ←上個修訂 | 已批准修訂 (差異) | 最新修訂 (差異) | 下個修訂→ (差異)

線性代數中，科列斯基分解（英語：Cholesky decomposition抑是Cholesky factorization）是講將一个正定的埃爾米特矩陣分解做一个下三角矩陣佮其共擔轉置之乘積。這種的分解方式咧提高代數運算效率、蒙特卡羅方法等場合中十分有用。實數矩陣的科列斯基分解由安德烈-路易 ・ 科列斯基上代先發明。實際應用中，科列斯基分解佇求解線性方程組中的效率差不多兩倍佇 LU 分解。

是咧講

嘿正定埃爾米特矩陣 $ \ mathbf { A } $ 進行科列斯基分解，即求矩陣 $ \ mathbf { L } $ 了後使下式成立


$ \ mathbf { A }=\ mathbf { LL } ^ { * } $

其中，$ \ mathbf { L } $ 是一个下三角矩陣而且所有對角元素均為正實數，$ \ mathbf { L } ^ { * } $ 表示 $ \ mathbf { L } $ 的共擔轉置。每一个正定埃爾米特矩陣攏有一个唯一的科列斯基分解。

當矩陣 $ \ mathbf { A } $ 是一个半正定的埃爾米特矩陣，若允准 $ \ mathbf { L } $ 的對角線元素為零，著 $ \ mathbf { A } $ 也存在上述形式的分解。

當 $ \ mathbf { A } $ 為實數矩陣，著 $ \ mathbf { L } $ 嘛為實數矩陣而且科列斯基分解會當改寫 $ \ mathbf { A }=\ mathbf { LL } ^ { \ mathbf { T } } $。

當 $ \ mathbf { A } $ 是正定候時，科列斯基分解是唯一的，即只存在一个對角元素攏真嚴格大於零的下三角矩陣，使 $ \ mathbf { A }=\ mathbf { LL } ^ { * } $ 成立。毋過，當 $ \ mathbf { A } $ 是半正定時間，分解則無一定是唯一的。

定理的逆命題自然成立：對某乜可逆矩陣 $ \ mathbf { L } $（下三角矩陣抑是其他矩陣）， 若是 $ \ mathbf { A } $ 有可能予人寫做 $ \ mathbf { LL } ^ { * } $，著 $ \ mathbf { A } $ 是一个正定的埃爾米特矩陣。

LDL 分解

經典科列斯基分解的一个變形是 LDL 分解，即


: $ \ mathbf { A }=\ mathbf { LDL } ^ { * } $

其中，$ \ mathbf { L } $ 是一个單位下三角矩陣，$ \ mathbf { D } $ 是一个對角矩陣。

該分解佮經典科列斯基分解猶有關聯，如下：


$ \ mathbf { A }=\ mathbf { LDL } ^ { * }=\ mathbf { LD } ^ { \ frac { 一 } { 二 } } ( \ mathbf { D } ^ { \ frac { 一 } { 二 } } ) ^ { * } \ mathbf { L } ^ { * }=\ mathbf { LD } ^ { \ frac { 一 } { 二 } } ( \ mathbf { LD } ^ { \ frac { 一 } { 二 } } ) ^ { * } $

抑是講，因為 $ \ mathbf { L } $ 的對角元素著愛為 $ 一 $，而且 $ \ mathbf { L } ^ { Cholesky } $ 佮 $ \ mathbf { L } $ 攏是下三角矩陣，故若已經知影經典科列斯基分解 $ \ mathbf { L } ^ { Cholesky } $，著 $ \ mathbf { LDL } ^ { T } $ 形式會當提出來求出，設S是包括 $ \ mathbf { L } ^ { Cholesky } $ 對角元素的對角矩陣，


$ \ mathbf { D }=\ mathbf { S } ^ { 二 } $


$ \ mathbf { L }=\ mathbf { L } ^ { Cholesky } \ mathbf { S } ^ { 影一 } $

LDL 百百款若著以有效執行，構造佮使用的時所需求的空間佮計算的複雜性佮經典科列斯基分解是仝款的，但是會當避免講號伊的平方根。某一寡無存在科列斯基分解的無定矩陣，嘛會當執行 LDL 分解，現此時矩陣 $ \ mathbf { D } $ 中會出現負數的元素。所以人閣較傾向著使用 LDL 分解。對著實數矩陣，該種的分解的形式會當予人改寫做


$ \ mathbf { A }=\ mathbf { LDL } ^ { \ mathbf { T } } $

這个形式通常叫做LDLT 分解（抑是LDLT 分解）。 伊佮實對稱矩陣的特徵分解密切相關，因為對實在講起先，存在特徵分解 $ \ mathbf { A }=\ mathbf { Q \ Lambda Q } ^ { \ mathbf { T } } $。

實例

以下乃一个實對稱矩陣的科列斯基分解 ︰


$ { \ begin { aligned } \ left ( { \ begin { array } { * { 三 } { r } } 四 & 十二 & 鋪十六 \ \ 十二 & 三十七 & 鋪四十三 \ \ 鋪十六 & 鋪四十三 & 九十八 \ \ \ end { array } } \ right )=\ left ( { \ begin { array } { * { 三 } { r } } 二 & 零 & 零 \ \ 六 & 一 & 零 \ \ ma八 & 五 & 三 \ \ \ end { array } } \ right ) \ left ( { \ begin { array } { * { 三 } { r } } 二 & 六 & ma八 \ \ 零 & 一 & 五 \ \ 零 & 零 & 三 \ \ \ end { array } } \ right ) \ end { aligned } } $

以下乃其 LDLT 分解 ︰


$ { \ begin { aligned } \ left ( { \ begin { array } { * { 三 } { r } } 四 & 十二 & 鋪十六 \ \ 十二 & 三十七 & 鋪四十三 \ \ 鋪十六 & 鋪四十三 & 九十八 \ \ \ end { array } } \ right ) &=\ left ( { \ begin { array } { * { 三 } { r } } 一 & 零 & 零 \ \ 三 & 一 & 零 \ \ 扳四 & 五 & 一 \ \ \ end { array } } \ right ) \ left ( { \ begin { array } { * { 三 } { r } } 四 & 零 & 零 \ \ 零 & 一 & 零 \ \ 零 & 零 & 九 \ \ \ end { array } } \ right ) \ left ( { \ begin { array } { * { 三 } { r } } 一 & 三 & 扳四 \ \ 零 & 一 & 五 \ \ 零 & 零 & 一 \ \ \ end { array } } \ right ) \ end { aligned } } $

應用

科列斯基分解主要被用佇線性方程組 $ \ mathbf { Ax }=\ mathbf { b } $ 的求解。若是A是一个對稱正定的，咱會當先共求出 $ \ mathbf { A }=\ mathbf { LL } ^ { \ mathbf { T } } $，隨後借向後替換法嘿y求解 $ \ mathbf { Ly }=\ mathbf { b } $，才閣向前替換法嘿x求解 $ \ mathbf { L } ^ { \ mathbf { T } } \ mathbf { x }=\ mathbf { y } $ 到尾仔解決。

另外一種會當避免佇咧計算 $ \ mathbf { LL } ^ { \ mathbf { T } } $ 攏愛解平方根的方法就是算 $ \ mathbf { A }=\ mathbf { LDL } ^ { \ mathrm { T } } $，然後嘿y求解 $ \ mathbf { Ly }=\ mathbf { b } $，最後求解 $ \ mathbf { DL } ^ { \ mathrm { T } } \ mathbf { x }=\ mathbf { y } $

對會當予人改寫做對稱矩陣的線性方程組，科列斯基分解及其 LDL 變形是一个較高效率猶閣有較高數值穩定性的求解方法。比並之下，效率差不多誠濟 LU 分解的兩倍。

矩陣求逆

如果要從埃爾米特矩陣直接求逆，會當通過科列斯基分解，類似求解線性方程組一般求出逆矩陣，這需要 $ n ^ { 三 } $ 次運算（$ { \ frac { 一 } { 二 } } n ^ { 三 } $ 次乘法運算）。 _ 該方法就算欲趕緊踏差不多算嘛有效率。_

非埃爾米特矩陣 $ \ mathbf { B } $ 嘛會使通過下例性質求逆，因為這內底 $ \ mathbf { BB } ^ { * } $ 總是埃爾米特矩陣 ︰


$ \ mathbf { B } ^ { 影一 }=\ mathbf { B } ^ { * } ( \ mathbf { BB } ^ { * } ) ^ { 影一 } $

計算

有各種各樣的方法用佇咧計算科列斯基分解。捷用的演算法的計算複雜度佇一般情形下為 $ O ( n ^ { 三 } ) $。

下底的演算法何者較緊取決佇執行的時具體條件。母體來講，第一个演算法會小可仔慢，因為其實以一種無蓋尋常的方式去讀數據。

科列斯基演算法

用於計算矩陣 $ \ mathbf { L } $ 的科列斯基演算法，是以高斯消去法共基礎調整起來的。

遞迴演算法由 $ i :=一 $ 開始，令


$ \ mathbf { A } ^ { ( 一 ) } :=\ mathbf { A } $

佇咧步數 $ i $，矩陣 $ A ^ { ( i ) } $ 彼个形式到下底：


$ \ mathbf { A } ^ { ( i ) }={ \ begin { pmatrix } \ mathbf { I } _ { i 影一 } & 零 & 零 \ \ 零 & a _ { i , i } & \ mathbf { b } _ { i } ^ { * } \ \ 零 & \ mathbf { b } _ { i } & \ mathbf { B } ^ { ( i ) } \ end { pmatrix } } , $

其中，$ \ mathbf { I } _ { i 影一 } $ 代表 $ i 影一 $ 維的單位矩陣。

現此時定義矩陣 $ \ mathbf { L } _ { i } $ 為


$ \ mathbf { L } _ { i } :={ \ begin { pmatrix } \ mathbf { I } _ { i 影一 } & 零 & 零 \ \ 零 & { \ sqrt { a _ { i , i } } } & 零 \ \ 零 & { \ frac { 一 } { \ sqrt { a _ { i , i } } } } \ mathbf { b } _ { i } & \ mathbf { I } _ { n-i } \ end { pmatrix } } , $

隨即 $ \ mathbf { A } ^ { ( i ) } $ 會當予人改寫做


$ \ mathbf { A } ^ { ( i ) }=\ mathbf { L } _ { i } \ mathbf { A } ^ { ( i + 一 ) } \ mathbf { L } _ { i } ^ { * } $

其中


$ \ mathbf { A } ^ { ( i + 一 ) }={ \ begin { pmatrix } \ mathbf { I } _ { i 影一 } & 零 & 零 \ \ 零 & 一 & 零 \ \ 零 & 零 & \ mathbf { B } ^ { ( i ) }-{ \ frac { 一 } { a _ { i , i } } } \ mathbf { b } _ { i } \ mathbf { b } _ { i } ^ { * } \ end { pmatrix } } . $

注意 ︰在此 $ \ mathbf { b } _ { i } \ mathbf { b } _ { i } ^ { * } $ 是一个外積。

重複此步驟到 $ i $ 對 $ 一 $ 到 $ n $。$ n $ 步了後，咱得著 $ A ^ { ( n + 一 ) }=\ mathbf { I } $。所以，所求的下三角矩陣 $ L $ 為


$ \ mathbf { L } :=\ mathbf { L } _ { 一 } \ mathbf { L } _ { 二 } \ dots \ mathbf { L } _ { n } . $

科列斯基-巴彼齊呢維茨佮科列斯基-克勞特演算法

寫出等式 $ \ mathbf { A }=\ mathbf { LL } ^ { * } $，


$ { \ begin { aligned } { \ mathbf { A=LL ^ { T } } } &={ \ begin { pmatrix } \ mathbf { L } _ { 十一 } & 零 & 零 \ \ \ mathbf { L } _ { 二十一 } & \ mathbf { L } _ { 二十二 } & 零 \ \ \ mathbf { L } _ { 三十一 } & \ mathbf { L } _ { 三十二 } & \ mathbf { L } _ { 三十三 } \ \ \ end { pmatrix } } { \ begin { pmatrix } \ mathbf { L } _ { 十一 } & \ mathbf { L } _ { 二十一 } & \ mathbf { L } _ { 三十一 } \ \ 零 & \ mathbf { L } _ { 二十二 } & \ mathbf { L } _ { 三十二 } \ \ 零 & 零 & \ mathbf { L } _ { 三十三 } \ end { pmatrix } } \ \ &={ \ begin { pmatrix } \ mathbf { L } _ { 十一 } ^ { 二 } & & ( { \ text { symmetric } } ) \ \ \ mathbf { L } _ { 二十一 } \mathbf { L } _ { 十一 } & \ mathbf { L } _ { 二十一 } ^ { 二 } + \ mathbf { L } _ { 二十二 } ^ { 二 } & \ \ \ mathbf { L } _ { 三十一 } \ mathbf { L } _ { 十一 } & \ mathbf { L } _ { 三十一 } \ mathbf { L } _ { 二十一 } + \ mathbf { L } _ { 三十二 } \ mathbf { L } _ { 二十二 } & \ mathbf { L } _ { 三十一 } ^ { 二 } + \ mathbf { L } _ { 三十二 } ^ { 二 } + \ mathbf { L } _ { 三十三 } ^ { 二 } \ end { pmatrix } } \ end { aligned } } $

則得著矩陣 $ \ mathbf { L } $ 的元素的計算公式如下 ︰


$ \ mathbf { L } _ { j , j }={ \ sqrt { A _ { j , j }-\ sum _ { k=一 } ^ { j 影一 } \ mathbf { L } _ { j , k } ^ { 二 } } } $


$ \ mathbf { L } _ { i , j }={ \ frac { 一 } { \ mathbf { L } _ { j , j } } } \ left ( A _ { i , j }-\ sum _ { k=一 } ^ { j 影一 } \ mathbf { L } _ { i , k } \ mathbf { L } _ { j , k } \ right ) , \ qquad { \ text { for } } i > j $

只要 $ \ mathbf { A } $ 是實數正定的正定，則平方根下的表達式恆為正。

對複埃爾米特矩陣，著愛用公式的：


$ \ mathbf { L } _ { j , j }={ \ sqrt { A _ { j , j }-\ sum _ { k=一 } ^ { j 影一 } \ mathbf { L } _ { j , k } \ mathbf { L } _ { j , k } ^ { * } } } . $


$ \ mathbf { L } _ { i , j }={ \ frac { 一 } { \ mathbf { L } _ { j , j } } } \ left ( \ mathbf { A } _ { i , j }-\ sum _ { k=一 } ^ { j 影一 } \ mathbf { L } _ { i , k } \ mathbf { L } _ { j , k } ^ { * } \ right ) , \ qquad { \ text { for } } i > j . $

所以，愛計算 $ \ mathbf { L } _ { i , j } ( i \ neq j ) $ 干焦需要利用其的倒、上方元素的值。計算通常是以下其中的順序之行的。

  • 科列斯基-巴彼齊呢維茨彼个算法對矩陣 L 的左上角開始，依行進行計算。
  • 科列斯基-克勞特演算法對矩陣 L 的左上角開始，依列進行計算。

若有需要，_ 規个矩陣會當逐个元素計算會出 _，無論講按怎用順序來讀。

計算的穩定性

假使咱要求解一个良置的線性方程組。採用矣 LU 分解的演算法，除非進行某種踅軸踅，抑無是無穩定的；若演算法進行踅軸踅，著其他的精差是攏取決定著 _ 增加因為 _，這个數通常（但是有總是）足細的。

這馬乎，假使演算法適用科列斯基分解。如何咧講，演算法的效率將會是原來的兩倍。此外，無必要進行踅軸旋轉而且精差總是足細。具體來講，若是要求解 $ \ mathbf { Ax }=\ mathbf { b } $，$ \ mathbf { y } $ 表示已經計算出的解，閣會當解出 _ 干擾方程組 _ $ ( \ mathbf { A } + \ mathbf { E } ) \ mathbf { y }=\ mathbf { b } $，其中


$ \ | \ mathbf { E } \ | _ { 二 } \ leq c _ { n } \ varepsilon \ | \ mathbf { A } \ | _ { 二 } . $

佇遮，$ \ | \ quad \ | _ { 二 } $ 是指矩陣二-範數，而且 $ c _ { n } $ 是一个號決於 $ n $ 的細常數，$ \ varepsilon $ 表示單位會當捨入。

價值咧講的是，科列斯基分解佮平方根的使用有關係。若予人分解的矩陣是正定的，遮爾仔只要 _ 運算精確 _，陣中帶有平方根的元素的平方根下的數字永遠是正數。不幸的是，因為存在想欲入誤差，遮的數字可能為負數，並使演算法靠礁。毋過，這款的情形唯若準陣為病態的時陣才會出現。一種會當解決這个問題的方式，是加添一个對角修正矩陣至待分解矩陣，以增加矩陣的正定性。  這條法雖然會減少分解的準確性，但是有佇咧某一款情形煞誠有做為；譬如講，執行應用佇上優化的牛頓法的時，若初期值距上優值較遠，對這个時陣會當引入對角矩陣會當提高演算法的穩定性。

LDL 分解

科列斯基分解的另外一種形式—— LDL 分解的計算方式如下所示，


$ { \ begin { aligned } { \ mathbf { A=LDL } ^ { \ mathrm { T } } } &={ \ begin { pmatrix } 一 & 零 & 零 \ \ L _ { 二十一 } & 一 & 零 \ \ L _ { 三十一 } & L _ { 三十二 } & 一 \ \ \ end { pmatrix } } { \ begin { pmatrix } D _ { 一 } & 零 & 零 \ \ 零 & D _ { 二 } & 零 \ \ 零 & 零 & D _ { 三 } \ \ \ end { pmatrix } } { \ begin { pmatrix } 一 & L _ { 二十一 } & L _ { 三十一 } \ \ 零 & 一 & L _ { 三十二 } \ \ 零 & 零 & 一 \ \ \ end { pmatrix } } \ \ &={ \ begin { pmatrix } D _ { 一 } & & ( \ mathrm { symmetric } ) \ \ L _ { 二十一 } D _ { 一 } & L _ { 二十一 } ^ { 二 } D _ { 一 } + D _ { 二 } & \ \ L _ { 三十一 } D _ { 一 } & L _ { 三十一 } L _ { 二十一 } D _ { 一 } + L _ { 三十二 } D _ { 二 } & L _ { 三十一 } ^ { 二 } D _ { 一 } + L _ { 三十二 } ^ { 二 } D _ { 二 } + D _ { 三 } . \ end { pmatrix } } \ end { aligned } } $

若是 $ \ mathbf { A } $ 是實數矩陣，下述之遞迴計算式適用佇矩陣 $ \ mathbf { D } $ 佮 $ \ mathbf { L } $ 中的所有的元素 ︰


$ D _ { j }=A _ { jj }-\ sum _ { k=一 } ^ { j 影一 } L _ { jk } ^ { 二 } D _ { k } $


$ L _ { ij }={ \ frac { 一 } { D _ { j } } } \ left ( A _ { ij }-\ sum _ { k=一 } ^ { j 影一 } L _ { ik } L _ { jk } D _ { k } \ right ) , \ qquad { \ text { for } } i > j . $

若是 $ \ mathbf { A } $ 是複埃爾米特矩陣，則陣 $ \ mathbf { D } $ 佮 $ \ mathbf { L } $ 的計算適用以下的公式矣：


$ D _ { j }=A _ { jj }-\ sum _ { k=一 } ^ { j 影一 } L _ { jk } L _ { jk } ^ { * } D _ { k } $


$ L _ { ij }={ \ frac { 一 } { D _ { j } } } \ left ( A _ { ij }-\ sum _ { k=一 } ^ { j 影一 } L _ { ik } L _ { jk } ^ { * } D _ { k } \ right ) , \ qquad { \ text { for } } i > j . $

仝款所在，若是需求，_ 該讀的順序會當每一計算矩陣中的每一个元素。_

分塊矩陣變形

當 $ \ mathbf { A } $ 是一个無定著的陣，LDL 分解佇咧未經過謹慎的踅軸旋轉的狀況下是無穩定的；  特別是，分解出的矩陣的元素可能是任意的。一个可取的改進手段是執行矩陣分塊後才閣執行分解，通常就共原矩的陣分做包括 $ 二 \ times 二 $ 伊的小矩陣的分塊矩陣：


$ { \ begin { aligned } { \ mathbf { A=LDL } ^ { \ mathrm { T } } } &={ \ begin { pmatrix } \ mathbf { I } & 零 & 零 \ \ \ mathbf { L } _ { 二十一 } & \ mathbf { I } & 零 \ \ \ mathbf { L } _ { 三十一 } & \ mathbf { L } _ { 三十二 } & \ mathbf { I } \ \ \ end { pmatrix } } { \ begin { pmatrix } \ mathbf { D } _ { 一 } & 零 & 零 \ \ 零 & \ mathbf { D } _ { 二 } & 零 \ \ 零 & 零 & \ mathbf { D } _ { 三 } \ \ \ end { pmatrix } } { \ begin { pmatrix } \ mathbf { I } & \ mathbf { L } _ { 二十一 } ^ { \ mathrm { T } } & \ mathbf { L } _ { 三十一 } ^ { \ mathrm { T } } \ \ 零 & \ mathbf { I } & \ mathbf { L } _ { 三十二 } ^ { \ mathrm { T } } \ \ 零 & 零 & \ mathbf { I } \ \ \ end { pmatrix } } \ \ &={ \ begin { pmatrix } \ mathbf { D } _ { 一 } & & ( \ mathrm { symmetric } ) \ \ \ mathbf { L } _ { 二十一 } \ mathbf { D } _ { 一 } & \ mathbf { L } _ { 二十一 } \ mathbf { D } _ { 一 } \ mathbf { L } _ { 二十一 } ^ { \ mathrm { T } } + \ mathbf { D } _ { 二 } & \ \ \ mathbf { L } _ { 三十一 } \ mathbf { D } _ { 一 } & \ mathbf { L } _ { 三十一 } \ mathbf { D } _ { 一 } \ mathbf { L } _ { 二十一 } ^ { \ mathrm { T } } + \ mathbf { L } _ { 三十二 } \ mathbf { D } _ { 二 } & \ mathbf { L } _ { 三十一 } \ mathbf { D } _ { 一 } \ mathbf { L } _ { 三十一 } ^ { \ mathrm { T } } + \ mathbf { L } _ { 三十二 } \ mathbf { D } _ { 二 } \ mathbf { L } _ { 三十二 } ^ { \ mathrm { T } } + \ mathbf { D } _ { 三 } \ end { pmatrix } } \ end { aligned } } $

在此，矩陣內底每一个元素攏是一个子矩陣。故此，會當照發達遞迴公式類比計算：


$ \ mathbf { D } _ { j }=\ mathbf { A } _ { jj }-\ sum _ { k=一 } ^ { j 影一 } \ mathbf { L } _ { jk } \ mathbf { D } _ { k } \ mathbf { L } _ { jk } ^ { \ mathrm { T } } $


$ \ mathbf { L } _ { ij }=\ left ( \ mathbf { A } _ { ij }-\ sum _ { k=一 } ^ { j 影一 } \ mathbf { L } _ { ik } \ mathbf { D } _ { k } \ mathbf { L } _ { jk } ^ { \ mathrm { T } } \ right ) \ mathbf { D } _ { j } ^ { 影一 } $

上述計算牽連矩陣相乘仝精確的求逆，故事實踐中袂當使用過大的分塊矩陣。

_ 修正 _ 分解

咱的實踐中經常有 _ 修正 _ 科列斯基分解的需求。即，經過算一寡矩陣 $ \ mathbf { A } $ 的科列斯基分解 $ \ mathbf { A }=\ mathbf { LL } ^ { * } $，然後佇 $ \ mathbf { A } $ 上小可仔做修改抑若產生的矩陣 $ { \ tilde { \ mathbf { A } } } $，要從其進行一個修正的科列斯基分解 $ { \ tilde { \ mathbf { A } } }={ \ tilde { \ mathbf { L } } } { \ tilde { \ mathbf { L } } } ^ { * } $。問題是，是毋是用已經的 $ \ mathbf { A } $ 的分解去修正 $ { \ tilde { \ mathbf { A } } } $ 的分解。

秩為一的修正（相加）

若是 _ 修正 _ 矩陣 $ { \ tilde { \ mathbf { A } } }=\ mathbf { A } + \ mathbf { xx } ^ { * } $，是其修正的分解予人號做秩是一的修正（相加）。。

以下是一个  MATLAB  語言寫的實現秩為一的修正的小程式：

秩為一的修正（相減）

若是 $ { \ tilde { \ mathbf { A } } }=\ mathbf { A }-\ mathbf { x } \ mathbf { x } ^ { * } $，遮爾仔干焦做 $ { \ tilde { \ mathbf { A } } } $ 猶原是正定的時陣愛方法較適用。 此條件下，頂懸的代碼嘛會當用減的狀況，只需要將 ` r ` 和 ` L ( k + 一 : n , k ) ` 的這个價值的加號替換做減號。

證明半正定矩陣的科列斯基分解唯一

頂的演算法表明，每一个正定矩陣 $ A $ 攏有一个科列斯基分解。此結論會當 _ 加入一寡限制條件 _ 後，推廣到半正定的情形。但是 _ 條件 _ 並無被完全建立，比如講，伊無佮出明確的數值演算法以計算科列斯基因。

若是 $ A $ 是一个 $ n \ times n $ 半正定陣，則序列 $ \ { \ mathbf { A } \ }=\ { \ mathbf { A } + ( 一 / k ) \ mathbf { I } _ { n } \ } $ 是一个由正定陣構成的序列。而且，佇咧算子範數內底


$ \ mathbf { A } _ { k } \ rightarrow \ mathbf { A } $

佇正定的情形下，彼每一个 $ \ mathbf { A } _ { k } $ 攏有伊科列斯基分解 $ \ mathbf { A } _ { k }=\ mathbf { L } _ { k } \ mathbf { L } _ { k } ^ { * } $。根據算子範數的性質，


$ \ | \ mathbf { L } _ { k } \ | ^ { 二 } \ leq \ | \ mathbf { L } _ { k } \ mathbf { L } _ { k } ^ { * } \ |=\ | \ mathbf { A } _ { k } \ | $

因而 $ \ { \ mathbf { L } _ { k } \ } $ 是算子巴攑赫空間上的一个有界集，所以是相對緊空間（因為基礎向量空間有限的）。 所以，伊有一个帶有限制 $ \ mathbf { L } $ 收斂仔序列，也咧記 $ \ { \ mathbf { L } _ { k } \ } $。較𠢕驗證，矩陣 $ \ mathbf { L } $ 有需要的特色，比如講，滿足 $ \ mathbf { A }=\ mathbf { LL } ^ { * } $ 以及 $ \ mathbf { L } $ 是下三角矩陣而且其對角元素非負。對所有的 $ x $ 和 $ y $ 攏有，


$ \ langle \ mathbf { A } x , y \ rangle=\ langle \ lim \ mathbf { A } _ { k } x , y \ rangle=\ langle \ lim \ mathbf { L } _ { k } \ mathbf { L } _ { k } ^ { * } x , y \ rangle=\ langle \ mathbf { L } \ mathbf { L } ^ { * } x , y \ rangle $

所以，$ \ mathbf { A }=\ mathbf { LL } ^ { * } $。因為基礎向量空間有限的，所以算子空間的所有的拓結構攏是等價的。故此，範數頂懸 $ \ mathbf { L } _ { k } $ 收斂佇 $ \ mathbf { L } $，意味著，$ \ mathbf { L } _ { k } $ 每一个元素攏獨立地收斂佇咧 $ \ mathbf { L } $。同時暗示，因為每一个 $ \ mathbf { L } _ { k } $ 攏是對角元素非負的下三角矩陣，$ \ mathbf { L } $ 亦如此。

推廣

科列斯基分解會當推廣到元素內底包括算子的矩陣（號做是算子矩陣）。 令 $ \ { { \ mathcal { H } } _ { n } \ } $ 是希爾伯特空間上的一个序列。考慮著如下算子矩陣


$ \ mathbf { A }={ \ begin { bmatrix } \ mathbf { A } _ { 十一 } & \ mathbf { A } _ { 十二 } & \ mathbf { A } _ { 十三 } & \ ; \ \ \ mathbf { A } _ { 十二 } ^ { * } & \ mathbf { A } _ { 二十二 } & \ mathbf { A } _ { 二十三 } & \ ; \ \ \ mathbf { A } _ { 十三 } ^ { * } & \ mathbf { A } _ { 二十三 } ^ { * } & \ mathbf { A } _ { 三十三 } & \ ; \ \ \ ; & \ ; & \ ; & \ ddots \ end { bmatrix } } $

滿足直和


$ { \ mathcal { H } }=\ oplus _ { n } { \ mathcal { H } } _ { n } , $

其中每一个


$ \ mathbf { A } _ { ij } : { \ mathcal { H } } _ { j } \ rightarrow { \ mathcal { H } } _ { i } $

攏是一个有界算子。若是 $ \ mathbf { A } $ 是正定抑是半正定，即對有限的 $ k $ 佮任意的


$ h \ in \ oplus _ { n=一 } ^ { k } { \ mathcal { H } } _ { k } , $

攏有 $ \ langle h , \ mathbf { A } h \ rangle \ geq 零 $，則存在一个下三角的算子矩陣 $ \ mathbf { L } $ 予得 $ \ mathbf { A }=\ mathbf { LL } ^ { * } $。此外嘛會當共 $ \ mathbf { L } $ 的對角元素化為正數。

用程式語言實現

  • C 語言 ︰GNU 科學庫提供幾个科列斯基分解的實現。
  • Maxima 電腦代數系統 ︰ 函式 _ Cholesky _ 可以佇計算科列斯基分解。
  • GNU Octave 數值計算系統提供一寡函式以計算，修正佮應用科列斯基分解。
  • LAPACK 庫提供一个高效能的科列斯基分解的實現，會用得 Fortran，C 語言佮其他的大多數語言讀取。
  • 佇咧 Python 中，numpy . linalg 模組內底的命令 _ Cholesky _ 會當執行科列斯基分解。
  • 佇咧 Matlab 中，_ chol _ 命令會當簡單來對一个矩陣進行科列斯基分解。
  • 佇咧 R 語言內底，_ chol _ 函式會當進行科列斯基分解。
  • 佇咧 Wolfram Mathematica 中，函式 _ CholeskyDecomposition _ 會當對一个矩陣執行科列斯基分解。
  • 佇咧 C + + 中，armadillo 庫中的命令 _ chol _ 會當執行科列斯基分解。特徵庫提供了疏疏矩陣佮稠密矩陣的科列斯基分解。
  • 佇咧 Analytica 中，函式 _ Decompose _ 提供科列斯基分解。
  • Apache Commons 數學庫中有科列斯基分解的實現，可應用佇咧 Java、Scala 佮任何其他 JVM 語言。

參見

  • 象徵性科列斯基分解
  • 上低次數演算法
  • 矩陣分解
  • 西爾維斯特慣性定理
  • 箍秩
  • 矩陣的平方根

跤註

參考文獻

  • Dereniowski , Dariusz ; Kubale , Marek . 五 th International Conference on Parallel Processing and Applied Mathematics ( PDF ) . Lecture Notes on Computer Science三千空一十九. Springer-Verlag : 九百八十五–九百九十二 . 兩千空四 [二千空一十七刣八孵三十] . ISBN  九百七十八追三鋪五百四十二孵一千九百四十六鼻空 . doi : 十 . 九百七十八分之一千空七孵三鋪五百四十二孵四千六百六十九九九分 \ _ 一百二十七喔 .（原始的內容 ( PDF ) 存檔佇二千空一十一鋪七堵十六）.   .
  • Golub , Gene H . ; Van Loan , Charles F . Matrix Computations 三 rd . Baltimore : Johns Hopkins . 九百九十六 . ISBN  九百七十八追空九八千空一十八追五千四百一十四追九 .
  • Horn , Roger A . ; Johnson , Charles R . Matrix Analysis . Cambridge University Press . 一千九百八十五 . ISBN  空九五百二十一孵三鋪八千六百三十二孵二 .   .
  • S . J . Julier and J . K . Uhlmann . " A General Method for Approximating Nonlinear Transformations of ProbabilityDistributions " .
  • S . J . Julier and J . K . Uhlmann , " A new extension of the Kalman filter to nonlinear systems , " in Proc . AeroSense : 十一 th Int . Symp . Aerospace / Defence Sensing , Simulation and Controls , 一千九百九十七 , pp .   一百八十二–一百九十三 .
  • Trefethen , Lloyd N . ; Bau , David . Numerical linear algebra . Philadelphia : Society for Industrial and Applied Mathematics . 一千九百九十七 . ISBN  九百七十八追空抹八七九千八百七十一孵三百六十一孵九 .   .

外部連結

科學史

  • _ Sur la résolution numérique des systèmes d'équations linéaires _ , Cholesky's 一千九百十二 manuscript , online and analyzed on BibNum（法文）（英文）[ for English , click'A télécharger']

資訊

  • Hazewinkel , Michiel ( 編 ) , Cholesky factorization , 被鋪百科全鋪排，Springer , 兩千空一 , ISBN  九百七十八孵一一鋪五千六百空八鋪十跡四
  • Cholesky Decomposition . PlanetMath .
  • Cholesky Decomposition , The Data Analysis BriefBook
  • Cholesky Decomposition on www . math-linux . com
  • Cholesky Decomposition Made Simple on Science Meanderthal

電腦代碼

  • LAPACK，一个求解誠濟線性代數問題的 FORTRAN 子程式的集合
  • ALGLIB，包含部份對 LAPACK 到 C + +、C #、Delphi、Visual Basic 等的埠頭
  • libflame，帶有 LAPACK 功能的 C 函式庫
  • 德克薩斯大學奧斯汀分校，有關科列斯基分解高效能佇實現的筆記佮影片
  • Google，Library " Ceres Solver " .
  • MATLAB 程式，LDL 分解
  • Armadillo，一个 C + + 線性函式包 ( package )

類比中矩陣的利用

  • 生做相關的隨機變數，Martin Haugh，哥倫比亞大學

線頂算機

  • 線上矩陣運算，會當執行科列斯基分解。
取自「https://wiki.taigi.ima.org.tw/w/index.php?title=科列斯基分解&oldid=454684」