為何利用對稱性?
高斯(Gauss)消去法適用於許多矩陣,但即使係數矩陣對稱,仍須儲存兩個三角因子。對實對稱正定矩陣,一個三角因子便決定另一個。所得的 Cholesky 分解在精確算術下也無須選主元。相同矩陣配合多個右端項時,這尤其有用;但正定或分解成功並不代表原系統的條件良好。
本節設 對稱、;除非另有說明,計算均為精確算術。
定義 3.2.1
(正定矩陣與 Cholesky 因子)
若對每個非零 都有 ,則實對稱矩陣 稱為正定。 的 Cholesky 因子是對角元嚴格為正、滿足 的下三角矩陣 。
逐列構造
由 可確定計算次序。已知第 列後,令
空和為零,平方根取正值。下面的定理說明正定輸入保證這些運算有意義;單是寫出平方根並不能證明被開方數為正。
定理 3.2.2
(存在性與唯一性)
實對稱矩陣 正定,當且僅當存在對角元嚴格為正的下三角矩陣 滿足 。此 唯一,上面的逐列公式可將它算出。
證明
(經 Schur 補作歸納)
先證正定性推出分解,對維數歸納。 時 ,結論成立。若 ,分塊寫為
這裏 。對任意非零 ,取 ,則 且 ,所以 正定。歸納假設給出 ,其中 為對角元為正的下三角矩陣。因此
滿足 。反覆進行同樣的分塊步驟,得到逐列公式及正的被開方數。反過來,若 且 為對角元為正的三角矩陣,則 可逆,所以非零 滿足 。
唯一性來自逐項比較: 先強制 ,再確定第一列其餘元素。假設之前各列已確定,對角方程強制正值 ,非對角方程再確定每個 。歸納便確定全部元素。正對角約定不可省略:否則可以改變列的符號。
歸納中藏著一個不明顯的測試向量選擇,而唯一性部分依賴一個符號約定。下面的剖析把兩者分開。
證明透視
Schur 補為何保證下一主元為正
關鍵一步是測試向量 。展開 ,取 ,交叉項便抵消,只剩 。這一個恆等式把正定性由 傳給較小的 ,歸納才得以繼續。它亦解釋逐列公式:第 步的被開方數是第 個 Schur 補的首元,而正定矩陣的對角元為正(),所以每個平方根都取自正數。
對稱性用在分塊本身:同一個向量 同時出現在 的下方及右方,所以一個因子 連同其轉置已足夠。反方向只用到對角元為正的三角矩陣可逆,因此 時 。唯一性在每條對角方程 處使用符號約定:若不要求 ,每一列都可乘以 。
求解並重用因子
算出 後,先以前代解 ,再以回代解 ,無須構造逆矩陣。對稠密矩陣,按乘法和加法各計一次運算的慣例,分解約需 次運算;每對三角求解需 次。這是稠密情形的主要運算量,並非稀疏實作的保證:消元可能產生填充,排序也會影響儲存量。
例題 3.2.3
(一次分解,多次求解)
取
第一列為 。第二個對角元為 ,而 。最後 ,故
對角元為正且 ,也證明了 正定。前代得 ,回代得 ;直接相乘可檢驗 。若第二個右端項為 ,可重用同一個 ,解為 。分解只需做一次,但電腦中的每次求解都有各自的算術誤差。
哪些情況會失敗?
反例模式
對稱且對角元為正仍不足夠
對稱矩陣 的對角元為正,但 。第一個 Cholesky 主元為 ,第二個被開方數卻是 。矩陣雖可逆,卻不存在實分解 。對角元為正不能代替正定性。
正定與半正定之間的界線,在公式中清楚可見。
例題 3.2.4
(半正定矩陣遇到零主元)
取 。它對稱,且 ,在 時取等號,所以 半正定而非正定。逐列公式給出 、,然後
乘積 確實等於 ,但對角元並非嚴格為正,所以這不是定理意義下的 Cholesky 因子。在更大的矩陣中,零主元亦會使下一列的公式除以零。定理中的嚴格不等式正好排除這種情況。
例題 3.2.5
(正定但條件差)
即使 正定,較小的特徵值也會使解敏感。例如 ,,其因子是 ,但二範數條件數為 。若 變為 ,解從 變為 :數據的相對變化 造成解的相對變化 。穩定的分解無法消除問題固有的敏感性。
常見錯誤
(以為分解成功便代表問題條件良好)
在精確算術下,完成的 Cholesky 分解證明了正定性,但對條件數的大小毫無說明,正如對角例子所示。溢出、輸入不確定性和條件數須另行考慮。
常見錯誤
(判斷計算所得的非正主元)
浮點計算出現非正主元,可能由於不定性,也可能由於接近奇異時的捨入;單憑這現象不能證明是哪一種。要斷定 不定,需要更多證據,例如一個滿足 的明確向量。
練習與解答
快速檢查
(分解 ,並解 。)
解答 · 答案
第一列是 ,第二個對角元為 ,所以 。前代得 ,回代得 。相乘可驗證。
快速檢查
(對 ,確定何時存在實的正對角 Cholesky 因子。)
解答 · 答案
第一主元為 ,第二個被開方數為 ,所以恰在 時存在。 時矩陣奇異; 時二次型可取負值。由正定性定理也可得到同一結論。
快速檢查
(如果 中 是對角元符號不受限制的可逆下三角矩陣, 是否必為正定?此時 是否唯一?)
解答 · 答案
正定:非零 有 ,所以 。但不唯一,例如 。要求對角元為正才能選出唯一因子。
證明針對規定的矩陣類別及精確算術;它本身不提供有限精度誤差界、條件數、稀疏填充估計或不定矩陣的適用性。