看似安全的主元並非全部
高斯(Gauss)消去法把方程組化為三角形式。在精確算術中這是等價變換,但電腦運算會捨入;中間數值的大小會影響捨入的作用。部分選主元在目前的列中選絕對值最大的元素作主元,並把其所在行交換至主元位置。這控制了消去乘數,卻不能保證後續所有元素都小。另一方面,殘差小本身亦不能保證近似解的誤差小;這是另一個問題。
本文設 非奇異,。討論誤差時,向量用歐氏(Euclidean)範數,矩陣用其誘導範數。除非特別說明,以下消去及殘差等式均在精確算術下成立。
乘數與中間數值增長
第 步選主元並交換行後,以 表示當前元素,並做更新
初始矩陣記作 ;公式右側的第 步元素是交換行之後的值。非奇異性保證每一步有非零主元:否則剩餘子矩陣的主元列全為零,它便是奇異的,原矩陣亦隨之奇異。由主元的選法,。若有平手,可按指定規則選行。
定義 1.4.1
(增長因子)
令 。消去過程的增長因子 ,是所有活動子矩陣 (,包括原矩陣)中元素的最大絕對值除以 。特別地,。
只用乘數的界,便可估計增長因子。
命題 1.4.2
(最壞情況的增長上界)
對非奇異 ,精確算術下的部分選主元高斯消去法的增長因子滿足 。
證明
(每一步至多使最大元素加倍)
設 是第 步開始時活動子矩陣中最大的絕對值,故 。交換行不改變它;對每個更新的元素,三角不等式及 給出
故 ,歸納得 。最多有 次更新;已放進 的元素也曾是較早步驟的活動元素,因而同受此界限制。這是最壞情況上界,並非說每個矩陣都達到它。
證明透視
因子二從哪裏來?
證明只追蹤一個數,即活動元素的最大絕對值 ,並只在一處用到部分選主元:,這是因為交換行後主元是該列中絕對值最大的元素。交換行本身無害,因為它只排列元素而不改變 。
關鍵一步是用兩個舊元素 與 去界每個新元素,而兩者都不超過 。沒有任何東西迫使減法出現抵消,兩個絕對值可以相加,因子二完全來自這裏。每一步從活動子矩陣中去掉一行一列,而 的每個元素在被固定時都曾是活動元素,所以歸納經 步後完成。論證從未利用抵消,因此只有特殊矩陣才會達到此界;下面的三階例子正好達到。
一個完整的增長例子
例題 1.4.3
(三階方程組的主元增長)
平手時選最先出現的行。取
第一列三個元素的絕對值都是一,故不交換行,兩個乘數都是 。把第一行分別加到第二、三行,得
第二步又是平手;將第二行加到第三行,得到
原矩陣最大絕對值為 ,過程中最大值為 ,所以 。 的對角元素非零,也證明矩陣非奇異。乘數有界並沒有阻止增長。
例題 1.4.4
(捨入算術中為何需要交換行)
解 ,其精確解為 、。採用把每個結果捨入至三位有效數字的十進制算術。
不交換行時,乘數為 ,第二條方程變成 。 與 都捨入為 ,所以 ,再得 。增長因子是 ,計算所得的 完全錯誤。
採用部分選主元時,兩行先交換,乘數為 。新的第二條方程是 ;兩邊都捨入為 ,所以 ,。兩個分量在所保留的位數內都正確,而 。這裏不交換行的消去是合法的,因為首元素非零;失敗來自巨大的中間元素與捨入的結合。
常見錯誤
(忘記對右端項作排列)
部分選主元分解的是 ,而不是 ,所以前代必須使用 。取 、,交換行後 、。用 求得 ,它滿足 。若改為解 ,得到 ,而 。
殘差、後向誤差與前向誤差
對近似解 ,令 ;真解 的前向誤差為 。由 和非奇異性,。因此,絕對殘差給出的絕對誤差上界還需乘上 。除以 與 的大小,便得到相對形式。
命題 1.4.5
(相對前向誤差的殘差界)
若 ,則 ,而且
證明
(兩條範數不等式)
由 得 。由 得 ,所以 且 。兩條不等式相乘即得所求上界。
條件數大會使此上界不精細;它不代表每個右端向量都必定造成大誤差。
例題 1.4.6
(條件良好而殘差非零的系統)
設 、 和 。則 ,。相對前向誤差為 ,相對殘差則為 。由於 ,上界給出 。這裏殘差雖然非零,但條件數不大,使上界具有參考價值。兩個相對量使用不同分母,不一定相等。
另一個有用的解讀是:殘差量度 須改變多少,才能使 成為精確解。
命題 1.4.7
(矩陣擾動的後向誤差)
設 ,只擾動 而固定 。則
而且最小值由 達到。
證明
(由秩一矩陣達到的下界)
限制條件就是 ,因此 ,即 。秩一矩陣 滿足 ;對每個 ,由 Cauchy–Schwarz 不等式,,在 時取等號。所以其範數恰為 ;再除以 即得公式。
這是只容許擾動 的後向誤差;它不容許同時擾動 ,數值上也不同於相對殘差。
常見錯誤
(相對殘差不是後向誤差)
與 只在 時相等。在上面條件良好的例子中,;而 、,後向誤差約為 。報告時要說明指的是哪一個;兩者都不是前向誤差。
反例模式
殘差小可以掩蓋大誤差
取 、,則 。若 ,殘差是 ,但相對前向誤差為 。此問題病態:。小殘差說明它是相近問題的精確解,並不自動確保它準確解出原問題。
浮點運算中,殘差本身也可能經過捨入,消去過程的增長可能放大所造成的擾動。上述精確上界只談中間元素,並非完整的浮點後向穩定性定理。可靠的數值判斷還須考慮精度、所計算的殘差和條件數估計。
練習與解答
快速檢查
(對 作部分選主元消去。寫出行交換、 和增長因子。)
選主元前先看第一列。
解答 · 答案
第一列是 ,部分選主元交換第一、二行,得 。乘數為 ,所以 。最大絕對值始終為 ,故 。
快速檢查
(設 ,其中 ,,。求相對殘差及相對前向誤差,並討論 的情況。)
真解可以直接讀出。
解答 · 答案
殘差為 ,真解為 。相對殘差為 ,相對前向誤差為 。前者趨向零,後者保持不變,這與 一致。
快速檢查
(設 、、。求使 成為精確解的最小譜範數擾動,並求其相對範數。)
使用後向誤差命題中的秩一矩陣。
解答 · 答案
此時 。秩一構造給出 ,它把 映到 。其譜範數為 ,而 ;上述命題證明它最小。真解為 ,故相對前向誤差為 ,不同於相對後向誤差 :兩者衡量不同對象的變化,分母也不同。