基礎:演算法、近似與誤差

精度階

精度階描述當你把步長 h 變小時,一個近似的誤差縮小得多快——以大 O 符號的精度意義表達:誤差 = O(h^p) 意味著對小的 h,誤差被某個常數乘以 h^p 所界定。指數 p 就是階。一階方法(p = 1)的誤差大致與 h 成正比;二階方法(p = 2)的誤差與 h^2 成正比,下降得快得多。

階的實用威力在於它對加密的預測。用 O(h^p) 的方法,把步長減半會使誤差乘以 (1/2)^p:一階誤差減半、二階誤差降為 1/4、四階誤差降為 1/16。所以階告訴你額外工作的回報。前向差分 (f(x+h) - f(x))/h 是 O(h)、一階;中心差分 (f(x+h) - f(x-h))/(2h) 是 O(h^2)、二階;梯形法則是 O(h^2),辛普森法則是 O(h^4)。更高階的每步買到戲劇性更多的精度,雖然通常每步工作也更多。

要小心:O(h^p) 是關於 h 趨於 0 之極限的漸近陳述;它隱藏了常數,對大的 h 什麼也沒說,而在大 h 處一個名義上較低階的方法反而可能勝出。它也假設函數夠光滑——對不光滑的函數,四階方法會悄悄掉到較低的觀測階。實務上量測真實階的標準方法是精度階(收斂)研究:反覆把 h 減半,看相鄰誤差的比值,從它們下降得多快讀出 p。這與大 O 的另一種用途不同,後者衡量演算法的成本而非其誤差。

在 [0, pi] 上積分 sin(x):梯形法則(O(h^2))在 h 減半時給出誤差 8.2e-3 然後 2.1e-3(比值約 4 = 2^2),而辛普森法則(O(h^4))每次減半下降約 16 倍——指數被具現出來。

階 p = O(h^p) 中的指數;把 h 減半,誤差減為 1/2^p。

更高階不代表在每個 h 都更準——而是當 h 趨於 0 時改善得更快。大 O 隱藏了常數、忽略大 h、並假設光滑性;在粗糙資料上觀測到的階可能崩塌。

又称
order of approximationbig-O for errorO(h^p)收斂階(離散)近似階