對近似解提出另一種問題
假設計算得到的向量 用來求解 。前向誤差 需要知道精確解 。殘差 通常更容易計算,但其大小依賴單位和尺度。後向誤差提出的問題是:數據需要改變多少,才能讓 成為精確解?
定義 2.5.1
(範數意義的後向誤差)
先考慮實矩陣、歐氏(Euclidean)向量範數和其誘導矩陣範數。定義
這裏 與 都可以改變。如果其中一個恰為零,其相對界也強制對應擾動為零。
這個定義是給定近似向量和數據的性質,並不聲稱產生它的某個算法是穩定的。
精確的範數意義公式
定理 2.5.2
(範數意義後向誤差的精確公式)
令 。當 時,
若 ,則 且 或 ,所以 ;零擾動達到 。
證明
(殘差恆等式與秩一擾動)
擾動後方程精確成立等價於 。因此任何允許的擾動都滿足
這證明了下界。若 ,零擾動達到它。否則令 、。當 時,令 並取
秩一矩陣 的誘導 2-範數為一,而且 。當 時取 , 保持相同定義;此時 ,等式仍然成立。因此所有情況都能達到這個下確界。
證明透視
下界與構造是兩個獨立的部分
證明分成兩個獨立的部分。下界只用殘差恆等式 和三角不等式,所以對每個允許的擾動都成立。與之匹配的構造才是不顯然的一步:兩個擾動都取成與殘差方向 平行, 通過 起作用,使 且 。符號( 取 , 取 )使兩部分貢獻疊加成 而不是互相抵消,共同的 用盡了全部預算 。 的情形要單獨處理,因為此時 沒有定義;那時預算只有 。沒有這個構造,我們只知道 。
更嚴格的逐分量問題
範數意義的擾動可能在尺度差異很大的元素之間轉移數據。
定義 2.5.3
(逐分量後向誤差)
逐分量後向誤差 是使得存在 滿足 並且
的最小 。
定理 2.5.4
(逐分量後向誤差的精確公式)
記 。滿足條件的最小 是
其中將 項解釋為零。
證明
(逐行的殘差恆等式)
這個約定是自洽的: 蘊含 且每個 ,所以 。
殘差恆等式逐行給出 ,從而得到下界。對每個 的行,取
對於 的行,取零擾動。因為 ,這些選擇滿足 ,並在 時滿足逐分量界。因此公式給出精確最小值。這個模型保持 和 的零元素;不同的擾動模型可能產生不同的後向誤差。
例題 2.5.5
(同時計算兩個後向誤差)
設 、、。則 ,、、,所以 ,。逐分量公式中 ,故 。最優的逐分量擾動只改動第 行:、。驗算:,而第 行本來就精確。
例題 2.5.6
(零近似解)
設 、、。則 ,,所以 。 的構造取 、,得 :整個右端項都必須被去掉。逐分量地,,,兩個比值為 和 ,所以 。第二行 、,用到了 的約定。
範數意義誤差很小,某個分量仍可能很差
例題 2.5.7
(範數意義誤差很小而逐分量誤差很大)
取 ,令
精確解為 ,殘差為 。由於 、,
當 時,範數意義的後向誤差趨於零,但第二個方程的逐分量後向誤差為 100%,相對前向誤差仍然很大。 的 2-範數條件數為 ;該問題會放大小奇異值方向上的誤差(此處也是特徵值 的特徵向量方向)。
反例模式
殘差小並不決定前向精度
一個誘人的說法是:範數意義的後向誤差小,就保證相對前向誤差小。取上面的對角例子並令 。則 ,,但 。修正見下面的界:因子 乘在殘差上,所以要得出前向誤差的結論,除了 之外還需要 和精確解尺度的資訊。
當 非奇異時,基本恆等式 給出 。結合 ,還得到 。所以前向誤差結論會涉及條件性;這是獨立於兩個後向誤差公式的另一個界。實際浮點計算中,殘差本身也經過捨入;如果要對精確數據給出嚴格證書,也必須控制殘差的計算誤差。
常見錯誤
(範數意義的擾動不一定保持零元素)
範數意義的極小擾動是 ,這是一個一般為稠密的秩一矩陣。在對角例子中 、,所以 在 為零的 位置放入了非零元素。若零結構有實際意義, 就不是在度量合法的擾動;這正是 的作用。
常見錯誤
(殘差除以 b 的範數並不是後向誤差)
比值 只是單獨擾動 時最小的相對擾動。由於 也可以改變, 可以更小。取 、、,則 ,;但 ,,由 、 達到:此時 。
練習與解答
快速檢查
(對 、、,計算 和 。)
先求 。
解答 · 答案
,。又 ,所以 。每個 ,所以 。
快速檢查
(在上面的對角例子中,求逐分量公式的兩個分母 。)
使用 。
解答 · 答案
、;殘差分量為 和 ,因此最大比值為 。
快速檢查
(若 精確求解 ,兩個後向誤差分別是多少?)
此時 。
解答 · 答案
兩者都為零,由零擾動達到。
快速檢查
(為甚麼逐分量擾動模型保持 的零元素?)
看對 的約束。
解答 · 答案
約束 強制 時 。