對稱性該換來好處
實務中出現的許多矩陣——共變異數矩陣、最小二乘的法方程 A^T A、物理中的剛度矩陣——都是對稱且正定的(SPD):A = A^T,且對每個非零 x 都有 x^T A x > 0。在這樣的矩陣上跑通用 LU 是浪費,因為 L 與 U 除一個對角縮放外互為鏡像。分解應當體現這種對稱性,而非忽視它。
Cholesky 分解正是這樣做的:它把 A 寫成 A = LL^T,其中 L 為下三角且對角元*為正*。一個三角因子加上它的轉置就承載了全部資訊——無需單獨的 U,也無需選主元,因為正定性保證主元始終為正。它是整個稠密線性代數中最高效、最穩定的分解,只要你能證明 A 是 SPD,就該選用它。
逐列計算它
Cholesky 有一個乾淨的遞迴配方。把 LL^T 的元素與 A 匹配:(1,1)元強制 L_11 = sqrt(A_11);L 第一行的其餘部分是 A 的第一行除以 L_11;然後從剩餘塊中減去該行的外積,再重複。每個對角步都取一次平方根——若根號下某個值變為非正,則 A *不是*正定的。這個失敗本身就是一項特性。
A = [ 4 12 -16 ; L = [ 2 0 0 ;
12 37 -43 ; 6 1 0 ;
-16 -43 98 ] -8 5 3 ]
# L_11 = sqrt(4) = 2
# L_21 = 12/2 = 6 , L_31 = -16/2 = -8
# L_22 = sqrt(37 - 6^2) = sqrt(1) = 1
# L_32 = (-43 - (-8)(6)) / 1 = 5
# L_33 = sqrt(98 - (-8)^2 - 5^2) = sqrt(9) = 3
# check: L @ L^T == A在對角元為正的約束下,Cholesky 是唯一的——恰好存在一個這樣的 L。對比 LU,那裡你得按慣例把 L 的對角線固定為 1;而這裡 A 的正定性免費完成了這個固定。這是由結構*贏得*的唯一性,而非人為規定的。
LDL^T:免開方的 Cholesky
平方根略微昂貴,且對*非*正定的對稱矩陣(不定情形,在最佳化中很常見)無定義。LDL^T 分解同時繞開這兩個問題:把 A 寫成 A = LDL^T,其中 L 是單位下三角、D 是對角矩陣。D 中的符號現在記錄不定性,而不會讓演算法崩潰——按 Sylvester 慣性定律,D 上正、負、零元的個數是 A 的一個不變量。