基礎:演算法、近似與誤差
近似
近似是一個值或一個函數,用來代替真正的那個——當真正的那個無法精確計算、無法寫成封閉形式、或無法存進有限記憶體,但「夠接近」確實就夠好的時候。說 pi 約為 3.14159,或說曲線下的面積是幾個梯形之和,都是近似:不是真品,但接近它,而且接近的程度是你能控制的。
把一個猜測變成體面的近似,靠的是誤差的概念。真值 x 的近似 x~ 有絕對誤差 |x~ - x| 與相對誤差 |x~ - x| / |x|,而好的數值方法會附帶一種把它們變小的辦法(取更多項、用更小的步長 h、再做一次迭代),理想上還有一個界告訴你能變多小。誤差常以已知速率縮小,寫成 O(h^p):把 h 減半,誤差就減為 1/2^p。所以近似不是草率——它是刻意、量化地以精確換取可計算性。
近似是不可避免的,而非最後手段:幾乎沒有任何真實世界、甚至中等規模的數學問題,有可用的精確答案。這門功夫在於知道你犯的是哪一種誤差(截掉極限的截斷誤差、有限算術的捨入誤差、輸入不完美的資料誤差),並讓總誤差保持被理解。整個領域的口號是:沒有精確答案——只有一個受控、站得住腳的近似。
用泰勒多項式 1 + x + x^2/2 + x^3/6 取代 e^x,把 e^(0.1) 近似為 1.105166...;真值為 1.105170...,故絕對誤差約 4e-6——很小,而且若再加一項可預期會更小。
一個有限、可計算的替身,取代一個無窮過程,其誤差可按需縮小。
更小並非總是免費可得。把 h 取得極小以縮小截斷誤差,最終會讓捨入誤差變大——常存在一個最佳步長,而非任意小的步長。
又称
另见