條件數、穩定性與向後誤差分析
誤差放大(error amplification)
誤差未必甘於一直保持渺小。當計算一步步向前推進時,某一步誕生的微小誤差會被帶往後續步驟,有時縮小、有時持平、有時增長——一步接一步地相乘,直到主宰結果。誤差放大就是誤差在計算中傳播時的這種增長,而理解它何時、為何發生,是區分穩定與不穩定方法的核心。
誤差被放大有兩種截然不同的途徑,把它們分開至關重要。第一種是問題自身造成的:病態問題會一口氣以其條件數放大輸入誤差——對任何演算法都無可避免。第二種是演算法造成的:一連串運算可能把捨入誤差養大,而次序更好的計算本不會如此,這正是不穩定的特徵。一個好用的心智模型是「每步放大因子」:若每一步把誤差乘以因子 g,則 n 步之後誤差按 g^n 縮放。g 大於 1 就指數爆炸;g 至多為 1 則誤差受控。這正是分析迭代與時間步進格式所用的視角,其中穩定性取決於把放大因子的大小保持在不超過 1。
對這兩個來源誠實,能讓你不去追逐幻影。若誤差因問題病態而增長,再怎麼重排或加檢查都擋不住它——放大是內在的。若它因演算法調度運算不當而增長(抵消、把遞迴跑在不穩定的方向、顯式格式超出穩定極限),那麼重新表述計算就能馴服它。放大因子的形式化,正是把這種模糊的擔憂變成精確、可檢查之條件的工具。
計算 I_n = [0,1] 上 x^n e^(x-1) 的積分,其遞迴 I_n = 1 - n I_{n-1} 若向前跑,每一步把任何起始誤差乘以約 n,因此災難性地放大;把同一遞迴反向跑,每一步則把誤差除以 n,因而穩定。
同一個遞迴,相反的方向——一個放大誤差,另一個抑制它。
永遠要問是哪個來源在放大:是問題(條件性,演算法無法修)還是演算法(不穩定,可修)。它們需要相反的應對。
又稱
另見