向後穩定演算法(backward-stable algorithm)
想像你雇了一位快遞。你不能要求他把東西送到你指定的、精確到毫米的 GPS 座標——世界沒那麼精確。但你可以要求他送到一個「就你自己地址裡的雜訊而言,與你本意之處無法區分」的點。向後穩定演算法就是這位理想的快遞:它回傳的是某個「與你所問僅有可忽略差異」之問題的精確解。這是數值計算的黃金標準——而且很重要的是,這通常已是你能期望的最好結果。
形式上,計算 y = f(x) 的演算法若對每個輸入 x,其算出的 y-hat 都等於某個小擾動 delta-x 下的精確值 f(x + delta-x),且 ||delta-x|| / ||x|| 為單位捨入(雙精度約 10^-16)等級,則稱為向後穩定。它不保證「你那個問題」的正確答案;它保證的是「與你所問僅在捨入距離內」之問題的正確答案。許多主力演算法都有此性質:帶部分樞紐選擇的高斯消去法、用豪斯霍爾德轉換做的 QR 分解、以及 LAPACK 的標準求解器,全都是向後穩定的。
人們常忽略的部分:向後穩定「不」代表向前誤差小。結合主法則,向後穩定演算法保證向前誤差為(條件數乘以單位捨入)等級。所以在良態問題上你會得到漂亮且準確的答案,但在病態問題上,同一個向後穩定演算法卻給出很大的向前誤差——這不是演算法的缺陷,而是問題的條件性顯露出來。因此向後穩定才是你該對方法提出的正確要求:它已經做到了演算法所能做的一切。
用帶部分樞紐選擇的 LU 求解 A x = b 是向後穩定的:算出的 x-hat 恰好解出 (A + delta-A) x-hat = b 且 ||delta-A||/||A|| ~ 10^-16。若 kappa(A) ~ 10^10,向前誤差約為 10^-6——六位好數字——即使方法本身毫無差錯。
穩定性已達成;損失的位數記在條件性帳上,而非演算法。
向後穩定不是準確的同義詞。它是方法所能給的最強保證;最終的準確度仍取決於問題的條件數。