一個算出的向量可能幾乎滿足方程組,卻仍與精確解相距甚遠。這並不矛盾:矩陣可能把某個輸入方向上的大變化映成輸出的微小變化。殘差衡量方程的偏差;前向誤差衡量答案的偏差。後向誤差提出另一個有用問題:輸入資料需要改變多少,才能使算出的答案成為精確解?
本章使用實矩陣、歐氏向量範數 及其誘導矩陣範數,兩者使用同一符號。對矩陣 ,,因此 且 。擾動證明只需要這些範數估計。本章所有等式和界限均針對精確數量;浮點計算在求這些數量時可能引入額外捨入誤差。
殘差與前向誤差
定義 6.1.1
(殘差與前向誤差)
設 是非奇異實 矩陣,,且 。對給定的近似答案 ,定義殘差及前向誤差為
定理 6.1.2
(前向誤差的殘差界)
設 是非奇異實 矩陣,, 的殘差為 、前向誤差為 。則 。若 ,則還有 。
證明
(減去精確方程)
減去 得 ,所以 ,並有
若 ,則 。由 ,將上式相除得到
因此只有當條件數適中,小的相對殘差才能有效控制相對前向誤差。這是上界,並非預測誤差必定達到它。若 ,除以 或 的相對表達式沒有定義;絕對誤差不等式仍然成立。右端為零時精確解為零,但算出的向量未必是零。
範數意義下的後向誤差證明
定理 6.1.3
(計算解的範數後向誤差)
令 、、,並在 時令 。則 恰是使下列條件成立的最小 :存在 滿足 、 且 。
證明
(下界,以及達到下界的秩一擾動)
假設算出的答案要成為附近方程組 的解。令 、 和 。當 時,定義
這不只是方便的尺度。它恰好是使以下條件成立的最小 :存在擾動滿足 、 及 。後一等式等價於 。三角不等式給出 ,所以每個容許的 至少是 。
要證明反向界限,若 ,取
則 。秩至多為一的矩陣 的二範數是 :Cauchy–Schwarz 不等式給出上界,單位向量 達到該上界。因此 且 。若 而 ,則 ;取 、,便達到 。若 ,非奇異性給出 ,故 ;此時原方程已成立,取 。
證明透視
後向誤差證明的兩個部分
下界 只用到對 的三角不等式。關鍵一步是構造:所需的修正量 按 的比例分給 與 ,使兩個範數約束在同一個 下同時取等。選用秩一矩陣 ,是因為它把 恰好送到 的倍數,而且範數是完成此任務所需的最小者;由 Cauchy–Schwarz,其範數等於 。證明中除以 與 ,所以 與 要分開處理。下界與構造在 相遇,論證因而完結。
這是對兩個資料對象同時施加相對界限的範數式證明。它不自動等於只容許改變 時的最小擾動,也不是逐項誤差界限。若只容許改變 ,精確選擇是 ,其範數為 。當各個項目的尺度差異很大時,這個分別尤其重要。
概念視角幾何
後向誤差是擾動空間中的一個球
固定 ,考慮由擾動對到 的線性映射 。在水平 下容許的擾動對構成球 、;而 恰為擾動系統的精確解,當且僅當 。上述證明顯示,當 時, 把這個球映成以 為中心、半徑為 的閉歐氏球。因此 是使像球達到 的最小 :它是以 為單位所量度的 。
同時擾動矩陣與右端
定理 6.1.4
(同時擾動兩項資料的擾動界)
假設 且 。記 、、。若 ,則 非奇異,且
證明
(相減、估界,並吸收誤差項)
假設 ,且 滿足 。定義
假設 。此條件亦保證 非奇異:因為 ,而 使第二個因子可由收斂的 Neumann 級數求逆。這是充分條件,並非必要條件。
令 。從擾動後方程減去 ,得 。因此
把最後一項移到左邊,並除以 。因為 ,得
在所列充分條件下,分母為正。當分母接近零,界限會失去參考價值;這並不能證明實際誤差很大。若只改變 ,令 ,便得到較簡單的 界限。條件數描述數學問題的敏感度;後向誤差描述某個答案對附近資料的吻合程度。
如何理解誤差證明
上述範數式後向誤差構造容許同時改變 和 。下界與明確構造的擾動恰好相等,故證明了最優性。換一個問題,答案也會改變:例如要求 的某些項保持為零,或要求保留對稱性,都會限制容許的擾動。所構造的秩至多為一的矩陣未必滿足這兩種限制。稱某個誤差為小之前,應先說清楚容許甚麼改變。共同的相對容差把 和 視為兩個對象;它不表示每個元素的改變都不超過同一百分比。
即使不知道真解,這個證明仍可能有用。計算 只需原始資料和給定答案;計算 則需要精確解。等式 解釋兩者差別,但實際應用它可能和解原方程一樣困難。 的界限或估計可提供可用上界;結論的可靠程度也取決於該估計及殘差計算本身。
亦要留意縮放。若同時以同一非零純量乘 和 ,精確解及有定義的兩種相對量均不變。範數式後向誤差也不變,因為其分子與分母以相同比例縮放。但只縮放其中一個方程,即使解集不變,範數式量度也可能改變,因為縮放後各方程在範數中的權重不同。在涉及物理單位或行尺度差距很大的應用中,可能需要合適縮放或逐項分析;上述範數式證明不能替我們決定這個選擇。
擾動估計也是單向的。大的條件數表示某些方向可能敏感,並不迫使每個右端或每種擾動都達到最壞情況。同樣,若界限大於一,它仍可能正確,但實際資訊很少。檢查真實殘差及擾動方向,往往比只引用一個純量更有用。先前章節的奇異向量解釋可找出伸長最多和最少的方向,但上述不等式不要求計算這些向量。
正規方程、QR 與尚未證明的事項
對實滿列秩矩陣 , 的奇異值是 的奇異值平方,故 。若 是具有標準正交列的薄 QR 分解,對每個 都有 ,因此 和 有相同奇異值,。
這些都是精確的條件數恆等式。它們解釋為何明確形成正規矩陣可能令待解方程的條件變差;它們沒有證明每一種 QR 實作都後向穩定,也沒有量化其浮點誤差。這類結論需要指定算法及另外的捨入誤差分析。實際上,乘積 本身也要計算,故在求解之前其元素可能已有捨入誤差。我們不單憑條件數平方就預言普遍適用的數字損失。
例題
例題 6.1.5
(小殘差與顯著前向誤差)
取 、 及 。求精確解、相對殘差、相對前向誤差和範數式後向誤差。
解答。 精確解為 。殘差為 ,而 。所以
前者約為 ,後者約為 。此處 、 及 ,故殘差界限容許所見的誤差。由於 ,精確範數式後向誤差為
它約為 :儘管給定向量與原資料的精確答案相距甚遠,它是適當附近資料的精確解。小的第二奇異值解釋了放大現象。
例題 6.1.6
(擾動界限與兩種分解)
設 、、 及 。求擾動後的解,將實際相對誤差與界限比較,並比較正規方程及 QR 的相關條件數。
解答。 原解為 。 的第二個對角項是 ,故 。因此 。由範數得 、、 及 。界限為
確實大於實際相對誤差。此外, 的條件數為 400。精確 QR 分解 、 的 。這些精確比較沒有量度某個具體軟件實作的捨入誤差。
例題 6.1.7
(零候選解:邊界情形)
令 、、。精確解為 ,殘差 ,前向誤差 ,所以相對前向誤差為 。這裏 、、,故 。對 的構造取 、:確實 。由於 ,需要對 作百分之百的相對改變;對 和 作任何更小的相對改變,都不能使 成為精確解。
反例模式
相對殘差很小並不保證誤差很小
斷言:若 ,則相對前向誤差也小於 。這是假的。取 、、。精確解是 ,殘差為 ,所以 ;但 ,。修正後的說法是殘差界:,而 ,容許所觀察到的誤差。
常見錯誤與細節
常見錯誤
(把條件數界當作預測)
第二個例題中,界是 ,實際相對誤差是 。這個界是「至多」形式的保證,並非誤差的估計值; 很大也不表示每個右端項都會出現最壞情況。
常見錯誤
(除以零範數)
若 ,精確解為零,分母含 或 的相對量沒有定義,只剩絕對界 。同樣, 需要 ,而 須按上面的方式另行處理。
習題
快速檢查
(對 、、,求 與 ,並比較 與 。)
精確解很容易讀出。
解答 · 答案
精確解是 。於是 ,,所以 。又 、,故界 取等號。
快速檢查
(若只允許擾動 ,要使 成為 的精確解,最小的 是多少?)
解出 。
解答 · 答案
方程迫使 ,所以唯一的選擇,也就是最小的選擇,其範數為 。
快速檢查
(設 、、。擾動定理是否適用?它給出甚麼?)
先檢查 。
解答 · 答案
,所以 非奇異,界為 。