為何利用矩陣的結構?
在方程組 中,三對角矩陣只把每個未知數與相鄰的未知數連起來。例如自然三次樣條的曲率方程便有這個結構。一般消元法仍然適用,但儲存全部 個元素會掩蓋其特點:在精確算術下,消去一行只會改動下一行。因此只需儲存和處理三條對角線。
以 表示第 行的下對角元素(), 表示對角元素, 表示上對角元素()。方程為
首行及末行不存在的項應省略。以下假設 。推導使用精確算術;主元非零只保證公式有意義,並不自動保證浮點運算準確。
逐個消去相鄰未知數
令 、。對 ,只要 ,便定義
變換後第 行是 ,末行沒有上對角項。若每個 均非零,反向代入得到
每步只需固定數目的算術運算。若矩陣不變而右端改變,可保留乘數與主元,只重新計算 並反向代入。下面的命題把變換後各行的形狀與運算次數說得精確。
命題 3.3.1
(消元不會離開三條對角線)
設 為三對角矩陣,且 均非零。依次處理第 行後,變換後方程組的第 行為 (末行沒有 項),而且三條對角線以外沒有元素變成非零。若再有 ,則分解、前向掃描與反向代入合共恰好需要 次算術運算,數據只佔 儲存空間。
證明
(對已處理的行作歸納)
當 時,結論就是首條方程,其中 、。假設結論對第 行成立。該行只在第 列含有 ,而尚未改動的第 行在第 列含有 。從第 行減去第 行的 倍,消去第 列的元素,把 換成 、把 換成 ;第 列不受影響,因為第 行在該列沒有元素。其他各行均未改動。由此第 行具有所述形狀,而且從不產生帶外元素。
至於運算次數: 個消元步驟中,每步以一次除法求 ,以一次乘法和一次減法求 ,求 亦然,共五次運算。反向代入求 用一次除法,其餘 個未知數各用一次乘法、一次減法和一次除法。總數為 。需要儲存的只有向量 及算出的 。
同一計算也可以看成矩陣分解;軟件正是以這種形式儲存它。
概念視角結構
消元即兩個雙對角矩陣的乘積
設 為單位下雙對角矩陣,下對角元素為 ;設 為上雙對角矩陣,對角元素為 ,上對角元素為 。展開乘積得
所以 。求 的前向掃描正是解 ,反向代入則是解 。因此對新右端重用分解,就是解兩個雙對角方程組;又因 ,有 。
定理 3.3.2
(主元何時存在?)
設 為左上角 主子矩陣,,。若 均非零,則直至 的消元主元均有定義,且 。若再有 ,所有主元均非零,算法給出唯一解。實對稱正定矩陣必定滿足這些條件。
證明
(行列式遞推與遺傳的正定性)
沿三對角行列式的末行展開,對 有 ,而 。除以 後由歸納法得 。主元非零時,行運算可逆,而最後的三角系統有唯一解。若 對稱正定,每個 也正定:把 的非零向量補零後運用正定的定義。由譜定理,每個 的行列式為正,因此所有主元均存在且為正。
證明透視
每個行列式假設用在哪裏
關鍵一步是看出主元遞推與行列式遞推是同一條三項關係:若 ,則
假設 只用了一次:令 非零,使第 步可以除以它。因此分解需要的是 ,而 只在反向代入的第一個除法 中用到。各式相乘後逐項相消,得 。在正定的情況,唯一額外的想法是:把二次型限制在只有前 個座標非零的向量上,就得到 的二次型,所以每個左上角子塊同時繼承了正定性。
對稱性提供更多結構。令 ,設 的對角線為一、下對角線為 。當之前的主元均非零,且 時,遞推式等價於
若矩陣對稱正定,所有 。因此亦可寫成 ,其中下雙對角矩陣 。主元為正是由正定性證出的性質;對一般對稱矩陣不能先行假設。
完整算例
例題 3.3.3
(三個相互耦合的未知數)
求解
主元為 、、。乘數為 、,所以 、、。反向代入得 、、。直接相乘可驗證 。
矩陣正定,因為對非零 ,
所以計算前已知主元必為正。若換一個 ,三個主元和兩個乘數可重用:它們只取決於 。
例題 3.3.4
(同一矩陣的 因子)
上例的矩陣是對稱的,。由乘數得 、,由主元得 。逐個元素展開 :
結果正是 。再作檢查:,與左上角主子行列式 、、 及 一致。
例題 3.3.5
(邊界情況:主元都有定義,但末主元為零)
取 。這裏 ,定理說 有定義;事實上 、。分解 存在,其中 、,但反向代入在第一步 便失敗。若 ,變換後末方程為 ,有無窮多個解;若 ,末方程為 ,無解。定理中的條件 正是用來排除這種情況。
結構不能保證甚麼?
反例模式
非奇異矩陣的首個主元也可能為零
三對角矩陣 的行列式為 ,因此任何右端均有唯一解;然而 ,上述遞推無法開始。交換兩行可以繼續消元。在更大的三對角系統中,行選主元可能造成額外填入,必須用能處理填入的算法。非奇異本身不足以保證不選主元的消元法可行。
常見錯誤
(對稱不等於主元為正)
遞推式 看似會令主元保持為正,其實不然。對 ,得 、。分解 存在,但 有負元素,所以 及雙對角因子 都不是實矩陣。主元為正以至 都由正定性推出,而正定性必須另行驗證。
即使所有精確主元存在,極小主元仍可能放大捨入誤差。正定性保證精確算術中主元不為零,卻不保證條件數小。例如 在 時正定,但當 ,其二範數條件數為 。因此解讀小殘差時,最好同時考慮條件數。線性成本只說明運算量,不是準確度證書;溢出、下溢、輸入誤差和算術捨入仍須考慮。
練習與解答
快速檢查
(對角線為 ,上下對角線均為 。求 主元,並不只依賴計算結果解釋它們為何為正。)
把二次型寫成平方和。
解答 · 答案
、、。二次型等於 ,非零 時為正。正定性因此保證主元為正。
快速檢查
(重用第一個算例中的分解,改以 求解。)
只需重做求 的前向掃描和反向代入。
解答 · 答案
由 、,新變換右端為 。反向代入得 、、。與 相乘可得 。
快速檢查
(有學生認為每個非奇異三對角矩陣的左上角主子行列式均非零。指出錯誤,並說明以上哪個較強條件足夠。)
參看上一節的反例。
解答 · 答案
反例中的交換矩陣行列式是 ,但第一個主子行列式為零。非奇異只說明 。對稱正定則足夠,因為每個左上角主子矩陣也正定,行列式為正。