線性系統的迭代法

迭代殘差

當你手上有 A x = b 的一個候選解 x,你會想問「它有多好?」。誠實的答案是把 x 與真解 x_star 相比,量出誤差 e = x - x_star。但你做不到——若你知道 x_star,就不必迭代了。殘差是退而求其次的選擇,而且它是你「能」算出來的:把你的 x 代回方程,看它差了多少。殘差是 r = b - A x,是剩餘、是方程未能平衡的量。

誤差與殘差被矩陣 A 綁在一起。因為 A x_star = b 恰好成立,相減得 r = b - A x = A x_star - A x = -A e,也就是 r = -A e,或 e = -A^{-1} r。所以「小殘差」只在 A^{-1} 不太大時才意味「小誤差」——精確地說,誤差最多可達 A 的條件數乘以(相對)殘差。對良態的 A,殘差是誤差的忠實替身;對病態的 A,極小的殘差可能藏著大誤差,因為除以一個近乎奇異的 A 會放大一切。殘差正是每個迭代法實際逼向零的對象,因為它是唯一可計算的進度量度。

實務上殘差身兼兩職。它是迭代的引擎——像共軛梯度法與 GMRES 這類方法,用當前殘差及其在 A 下的像來建構下一步——它也是停止判據的依據:當殘差範數 ||b - A x|| 縮得夠小(通常相對於 ||b||)時就收手。只要記得殘差的盲點:它證明 x 幾乎滿足方程(小的向後誤差),未必證明 x 接近真答案(小的向前誤差)。在病態問題上,這兩者大不相同。

若 ||b - A x|| / ||b|| = 10^{-8} 但 A 的條件數為 10^6,則 x 的相對誤差可大到 10^6 乘 10^{-8} = 10^{-2}——儘管殘差有八位數,誤差卻達百分之一。在良態的 A 上,殘差與誤差緊密同步。

殘差 r = -A e:小殘差只在 A 的條件數範圍內才意味小誤差。

小殘差不等於小誤差。它證明向後穩定(你的 x 解了一個鄰近的系統),但在病態矩陣上,真正的向前誤差可能大上一個條件數的倍數。永遠要對照條件數來解讀殘差。

又称
residual vectorr = b - A x殘差向量