正定性提供安全的代數主元
定義 2.4.1
(正定矩陣)
若對每個非零向量 皆有 ,則稱實對稱矩陣 為正定矩陣。
這類矩陣比一般可逆矩陣具有更多結構。其 Cholesky 分解將 寫成
其中 為對角線元素嚴格為正的下三角矩陣。這使我們可以透過兩次三角方程組求解來解 ,即 與 ,而無須計算 。
定義 2.4.2
(Schur 補)
設
是對稱分塊矩陣,其左上角分塊為純量 。 在 中的 Schur 補是矩陣 。
概念視角分析
Schur 補是對一個變量取最小值的結果
對固定的向量 ,函數 是首項係數為正的一元二次函數。它在 處取最小值,最小值為 。所以 就是對第一個變量取最小值消去之後剩下的二次型。這第二種描述解釋了為甚麼 會從 繼承正定性,也說明了下面證明中的試探向量從何而來。
定理 2.4.3
(Cholesky 分解)
每個實對稱正定矩陣都有唯一的分解 ,其中 為下三角矩陣且對角線元素為正。反之,任何此類乘積必為對稱正定矩陣。
證明
(對 Schur 補作歸納)
對維數使用歸納法。就第一個主元而言,由於 ,故 。記
直接相乘可知, 當且僅當
矩陣 稱為 的 Schur 補;由於 和 對稱, 亦是對稱的。對任意非零的 ,取 。則 ,且
因此 為正定矩陣,歸納假設便給出 。 的情形為 。
關於唯一性,第一個對角線元素必須為 ,而第一列其餘元素由 所確定。於是 Schur 補隨之固定,再由歸納法確定其餘的分塊。反之,若 的對角線元素為正,則 可逆,而對 ,有 。
證明透視
為甚麼每一步消去後正定性仍然保持
正定性必須在每一步消去後保持,這就是整個歸納的內容。第一個主元 之所以成立,只因為 正定,並且需要它才能除以 。不顯然的一步是試探向量 :它對給定的 選取使 最小的第一個座標,所以 就是該二次型對這個座標取最小值的結果。由於 時 , 的正定性便傳遞給 ,同一論證可用於更小的矩陣。僅有第一個主元為正並不能說明 的任何性質,下面的反例會顯示這點。唯一性是另一回事:每一步只有一個正的平方根可取,所以每個元素都被確定。
元素遞推公式
比較 的各元素,對 可得
定理證明了在精確運算下,每一步的被開方數皆為正。它並未說明任意對稱矩陣的被開方數都為正,亦未說明有限精度運算不會擾動一個非常小的被開方數。
例題 2.4.4
(一個二階方程組)
設
則 。要解 ,前代法得 及 ;回代法得 ,。驗算 即可確認這次具體的計算。
例題 2.4.5
(用遞推公式分解三階矩陣)
設 。遞推公式給出 、、;然後 、;最後 。所以 ,乘出 即回到 。對 ,前代法得 ,回代法得 、、。驗算:。
例題 2.4.6
(被開方數變成零的情形)
設 。遞推公式給出 、、。矩陣 的確滿足 ,但它的對角線元素不是正數, 是奇異的。事實上 只是半正定: 在 處為零。這時兩次三角方程組求解無法進行;在更大的矩陣中,下一列還會除以 。
反例模式
對稱性與正的首個主元不保證正定
對稱矩陣 可逆但不是正定矩陣。由於對每個 皆有 ,它不可能等於某個實矩陣 的 。第一個主元為正,並不能使 Schur 補為正:此處 Schur 補等於 。
常見錯誤
(對角線元素為正並不足夠)
對於對稱矩陣,對角線元素為正只是必要條件,因為 。矩陣 的對角線為 ,但 給出 。第一個主元之後的 Schur 補為 ,遞推公式會對負數開平方。
半正定矩陣可能有帶零對角線元素的奇異分解,但上述遞推公式可能出現除以零的情況;正定情形的定理並不涵蓋這種情況。在有限精度下,Cholesky 分解通常用於尺度良好的正定方程組,但要完整分析捨入誤差或條件數,則需要額外的假設。當 為病態矩陣時,分解成功本身並不保證 的相對誤差很小。
練習與解答
快速檢查
(求 的 Cholesky 因子。)
對各主元取平方根。
解答 · 答案
。
快速檢查
( 是否為正定矩陣?請在不計算其特徵值的情況下說明。)
試一個各分量符號相反的向量。
解答 · 答案
不是:取 ,。
快速檢查
(當 的對角線元素為正時,為何兩個三角方程組皆有唯一解?)
三角矩陣的行列式是甚麼?
解答 · 答案
對角線元素非零的三角矩陣可逆;前代法與回代法逐個確定各分量。
快速檢查
(若 且 可逆,為何 只有零解?)
計算 。
解答 · 答案
由 得 ,所以 。