對稱正定矩陣的 Cholesky 分解

一個配得上捷徑的矩陣

到目前為止，對任何方陣，你都能靠計算 LU 分解再跑兩次三角求解來解 A x = b。那個方法很通用——它對 A 除了可逆之外別無要求——而通用是有代價的。本文要談的是：當 A 很特殊時，如何把這份特殊性換成現金。這份特殊結構叫做 對稱正定（SPD）：矩陣等於自己的轉置，A = A^T，而且對每個非零向量 x，數值 x^T A x 都嚴格為正。這類矩陣無所不在——它們從最小平方法的正規方程、從物理能量、從共變異數、從樑的勁度裡冒出來——而當你認出它們時，它們會慷慨地回報你。

先給兩個提醒，因為 SPD 的兩半都很重要。光有對稱還不夠：對角元為 1、1、非對角元為 2 的矩陣是對稱的，但對 x = (1, -1) 來說 x^T A x 會變負，所以它不是正定的。而沒有對稱的正定又是另一個更混濁、Cholesky 並不涵蓋的故事。讓一切成立的條件，是這兩者「同時」具備。對正定性最乾淨的心像是：碗狀曲面 z = x^T A x 在離開原點的每個方向上都嚴格向上彎，只有一個最低點——沒有平坦的山谷、也沒有鞍點。

以下是本文其餘部分會兌現的承諾。對一個 SPD 矩陣，你可以把 A 分解成「單一一個」三角矩陣與它的轉置，A = L L^T，而不是分解成兩個各自獨立的因子 L 與 U。這份分解的對稱性並非巧合；它正是矩陣自身的對稱性透出來的痕跡。而既然它把記帳量砍半，它也就把成本砍半。

Cholesky：對折後的 LU

Cholesky 分解把一個 SPD 矩陣寫成 A = L L^T，其中 L 是下三角矩陣、對角線上的元素嚴格為正。把它和先前的通用 A = L U 比一比：那裡下三角因子 L 裝著消去的乘數，上三角因子 U 裝著消去之後剩下的東西。對 SPD 矩陣而言，這兩個因子不再各自獨立——U 結果恰好就是 L^T（差一個對角縮放）。所以你不必同時儲存與計算 L 和 U，而只計算一個三角因子，另一個靠轉置就免費得到。你做的是你早已熟悉的同一套消去，只是只記錄其中一半。

general matrix :   A = L U          (two factors, L and U)
SPD matrix     :   A = L L^T        (one factor, reused transposed)

2x2 worked example, A = [ 4   2 ]
                        [ 2   5 ]

  L_11 = sqrt(4) = 2
  L_21 = 2 / L_11 = 1
  L_22 = sqrt(5 - 1^2) = sqrt(4) = 2

  so  L = [ 2  0 ]   and   L L^T = [ 4  2 ] = A   (check)
          [ 1  2 ]                 [ 2  5 ]

用一個因子取代兩個，外加一個你能手算驗證的 2x2 例子。

看看這個例子實際在做什麼。對角元 L_11 是一個平方根，下一個對角元 L_22 則是「5 減去我們已經用掉的部分」的平方根。那個減法正是喬裝過的消去步驟：它是 Schur 補，與你在高斯消去裡對剩餘子矩陣做的更新一模一樣。正定性恰恰保證了每個出現在平方根底下的量都嚴格為正，所以演算法永遠不會被要求去開負數的平方根、也永遠不會除以零。這就是這個方法安全的深層原因。

不需要樞紐選擇——以及為何這值得驚嘆

上一篇反覆強調，通用的高斯消去需要部分樞紐選擇：少了它，可能冒出一個極小或為零的樞紐，成長因子可能爆掉，毀掉準確度。Cholesky 完全不需要這些。你可以沿著對角線一路直接做下去，不換列、不搜尋最大樞紐，而它仍可證明是向後穩定的。這真的令人意外——就在一篇之前，樞紐選擇還像是非做不可的——所以值得弄懂為什麼 SPD 矩陣能拿到這份豁免。

原因在於，正定性管控了分解過程中曾出現的每一個元素的大小。有一個乾淨的界限：L 的每個元素的絕對值都不超過 A 對應對角元的平方根，所以不會像通用矩陣那樣有任何東西失控暴增。那些樞紐——也就是被開了平方根的對角量——其下界是由結構保證的，而非靠運氣。於是樞紐選擇本來要拆除的那個危險，在這裡根本無從出現。你省去樞紐選擇，不是因為魯莽，而是因為矩陣已經替你把安全工作做完了。

演算法，以及你真正省下的成本

以下是求解 SPD 系統 A x = b 的整套方法，從頭到尾走一遍。請注意，一旦你有了 L，求解就只是你早已掌握的那兩次三角求解——先用 L 做向前代入，再用 L^T 做向後代入——所以所有的新工作都在分解這一步裡。

分解：計算 L 使得 A = L L^T。對每一行，對角元取一個平方根，再以除法填滿它下方的整行，並減去已經交代過的貢獻（Schur 補更新）。
向前求解：用向前代入解 L y = b 求出 y——由上而下，每個未知數在你抵達時就已就緒。
向後求解：用向後代入解 L^T x = y 求出 x——由下而上——x 就是你的答案。
重複利用：要對新的右端 b 再解一次 A x = b，沿用同一個 L、只重跑第 2、3 步——這就是「分解一次、求解多次」的訣竅，和 LU 一模一樣。

現在來看浮點運算量上的招牌收益。對一個 n×n 矩陣做 LU 分解約需 (2/3) n^3 次浮點運算。Cholesky 約需 (1/3) n^3——幾乎正好是一半——因為對稱性讓你只需碰下三角、再把它重複用於上三角。它需要的儲存量也約只有一半，因為你保留一個三角而非兩個完整因子。三角求解依舊便宜，各為 O(n^2)，所以只要 n 大到值得在意，分解就主導全局，而在 Cholesky 適用之處它都是明顯的贏家。分解一次、求解多次的經濟學原封不動地延續：三次方的成本只付一次，之後每個新的右端都只是二次方的。

把 Cholesky 當成正定性檢驗，以及一個誠實的告誡

Cholesky 還有一份額外的事業：作為判定一個對稱矩陣是否正定最實用的檢驗。你只要試著做這個分解。如果每個對角量一路都嚴格保持為正，這矩陣就是 SPD，而你順手免費帶走了 L。如果在某一步，平方根底下的量掉到零或變負，那這矩陣就「不是」正定的，而你以與分解相同的 O(n^3) 成本、便宜地查清了這件事。直接檢查特徵值會更貴、在有限精度下也更不可靠——「試做 Cholesky」才是標準、被推薦的檢驗。

現在來說那個誠實的告誡，因為平方根會讓一些讀者緊張，而一個接近奇異的 SPD 矩陣正好就活在邊緣上。對策是它的近親 LDL^T 分解，它把 A 寫成 A = L D L^T，其中 L 是單位下三角、D 是對角。它計算出相同的資訊卻從不取平方根，迴避了開根的成本與捨入，並且對某些近乎臨界的情形處理得更優雅。當你想要 Cholesky 那份對稱省下的成本、卻又被純平方根形式弄得不安時，它就是自然的退路。

該帶往後續的事

這個教訓的適用範圍遠超過這一種分解：結構就是錢。當你認出一個矩陣是對稱正定的那一刻，你就把通用的 LU 換成 Cholesky、把工作量與儲存量砍半、徹底丟掉樞紐選擇，還白賺一個正定性檢驗——這一切，都因為矩陣告訴了你某件關於它自身的真相。數值計算獎勵這樣的習慣：在伸手去拿那把通用鐵錘之前，先問「關於這個矩陣，我究竟知道些什麼？」

本階的最後一篇會把這些線索收攏在一起。它會認真重訪那個三次方成本、展示當矩陣稀疏或帶狀時會有什麼改變——在那裡，Cholesky 無需樞紐的自由會成為控制填入（fill-in）的超能力——並解釋應用線性代數中最常被違反的一條規則：你幾乎從不為了解 A x = b 而去構造矩陣的逆。Cholesky 會是貫穿全篇的範例，因為一個稀疏的 SPD 系統，正是你最常被交付的那一類大型問題。