數值線性代數:直接法

LDL^T 分解

喬列斯基分解很美,但有兩個小缺點:它要開平方根(成本略高,且要求根號下嚴格為正),而且只能處理正定矩陣。LDL^T 分解是把這兩個皺褶都撫平的近親。它把對稱矩陣寫成 A = L D L^T,其中 L 是單位下三角(對角線為 1),D 是吸收縮放的對角矩陣——所以不需要平方根。

你可以把它想成把平方根抽出到對角 D 的喬列斯基:若喬列斯基給出 A = G G^T,則令 D 存 G 對角線的平方、令 L 為各行重新縮放後的 G,便得 A = L D L^T。分解以與喬列斯基相同的一半工作量 O(n^3 / 3) 算出,求解同樣是一對三角求解加上一次平凡的對角求解(解 L y = b、再以除法解 D z = y、再解 L^T x = z),去掉平方根可略快也更乾淨。關鍵在於:當允許 D 含負元素或 2×2 區塊時,LDL^T 可推廣到不定的對稱矩陣——非正定——這是純喬列斯基碰不到的。

對於未知是否正定的對稱系統,LDL^T 是首選方法,這在最佳化(約束問題的 KKT 系統對稱但不定)與許多物理應用中不斷出現。對不定矩陣,它必須搭配對稱樞紐選擇(Bunch-Kaufman 策略,使用 1×1 與 2×2 樞紐區塊)才能在保持對稱的同時維持穩定。誠實的注意點:在正定矩陣上,LDL^T 與喬列斯基在成本和精度上基本等價,所以真正改用 LDL^T 的理由是不定的情況。

對列為 (4, 2) 與 (2, 5) 的 A,LDL^T 給出列為 (1, 0) 與 (0.5, 1) 的 L 與 D = diag(4, 4);驗證 L D L^T = A,過程中不開任何平方根。

對角 D 承載了喬列斯基會放到平方根下的縮放。

對不定的對稱矩陣,樸素的 LDL^T 可能崩潰或不穩定;你需要含 2×2 區塊的對稱(Bunch-Kaufman)樞紐選擇。在正定矩陣上,它相對於喬列斯基並無真正優勢。

又称
LDL^T decompositionsquare-root-free CholeskyLDLT分解無平方根喬列斯基