JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Cholesky 與 LDL^T:對稱性的回報

當 A 是對稱正定矩陣時,LU 有一半是冗餘的。Cholesky 把它扔掉——A = LL^T——換來兩倍速度和一次免費的正定性檢驗。

對稱性該換來好處

實務中出現的許多矩陣——共變異數矩陣、最小二乘的法方程 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
一個完整算出的 3x3 Cholesky;每個對角步都取實平方根,因為 A 是 SPD。

在對角元為正的約束下,Cholesky 是唯一的——恰好存在一個這樣的 L。對比 LU,那裡你得按慣例把 L 的對角線固定為 1;而這裡 A 的正定性免費完成了這個固定。這是由結構*贏得*的唯一性,而非人為規定的。

LDL^T:免開方的 Cholesky

平方根略微昂貴,且對*非*正定的對稱矩陣(不定情形,在最佳化中很常見)無定義。LDL^T 分解同時繞開這兩個問題:把 A 寫成 A = LDL^T,其中 L 是單位下三角、D 是對角矩陣。D 中的符號現在記錄不定性,而不會讓演算法崩潰——按 Sylvester 慣性定律,D 上正、負、零元的個數是 A 的一個不變量。