逼近理论

數學中的逼近理论是如何將一函數用較簡單的函數來找到最佳逼近，且所產生的误差可以有量化的表征（英语：Characterization (mathematics)），以上提及的「最佳」及「較簡單」的實際意義都會隨著應用而不同。

數學中有一個相關性很高的主題，是用廣義傅立葉級數（英语：generalized Fourier series）進行函數逼近，也就是用以正交多項式為基礎的級數來進行逼近。

計算機科學中有一個問題和逼近理论有關，就是在數學函式庫中如何用計算機或計算器可以執行的功能（例如乘法和加法）儘可能的逼近某一數學函數^[1]，一般會用多項式或有理函數（二多項式的商）來進行。

逼近理论的目標是儘可能地逼近實際的函數，一般精度會接近電腦浮點運算的精度，一般會用高次的多項式，以及（或者）縮小多項式逼近函數的區間。縮小區間可以針對要逼近的函數，利用許多不同的係數及增益來達到。現在的數學函式庫會將區間劃分為許多的小區間，每個區間搭配一個次數不高的多項式。

紅色是log(x)及最佳多項式的誤差，藍色是log(x)和Chebyshev逼近的誤差，x範圍都在[2, 4]區間內，縱軸的格線為10^−5。最佳多項式的最大誤差為6.07 x 10^−5

紅色是exp(x)及最佳多項式的誤差，藍色是exp(x)和Chebyshev逼近的誤差，x範圍都在[−1, 1]區間內，縱軸的格線為10^−4。最佳多項式的最大誤差為5.47 x 10^−4.

最佳多項式

只要選定了多項式的次數及逼近的範圍，就可以用以使最壞情形誤差最小化的原則，來選擇逼近多項式，其目的為最小化${\displaystyle \mid P(x)-f(x)\mid }$ 的絕對值，其中P(x)為逼近多項式，而f(x)為實際的函數。對於一個良態的函數，存在一個N次的多項式，使誤差曲線的大小在${\displaystyle +\varepsilon }$ 和${\displaystyle -\varepsilon }$ 之間震盪至多N+2次，其最壞情形的誤差為${\displaystyle \varepsilon }$ 。一個N次的多項式可以內插曲線中的N+1個點。當然也有可能製造一些極端的函數，使得滿足上述條件的多項式不存在，但在實務上很少需要為這様的函數進行逼近。

例如右圖中的紅線就是用N = 4情形下用多項式逼近log(x)及exp(x)的誤差。誤差在${\displaystyle +\varepsilon }$ 和${\displaystyle -\varepsilon }$ 之間震盪。每一個例子中的極端有N+2個，也就是6個。極值出現在區間的端點，也就是圖的最左邊及最右邊。

切比雪夫近似

 

前六个第一类切比雪夫多项式的图像，其中-1¼<x<1¼, -1¼<y<1¼

切比雪夫近似是利用將函數展開為由切比雪夫多项式組成的各項，依需要的逼近程度決定展開的項次，可以得到很接近多項式的結果。此作法類似進行函數的傅立葉分析，只是用切比雪夫多项式代替分析中用到的三角函數。

若計算一函數切比雪夫展開的係數：

${\displaystyle f(x)\sim \sum _{i=0}^{\infty }c_{i}T_{i}(x)}$ 

只展開到${\displaystyle T_{N}}$ 項為止，可以得到一個逼近f(x)的N次多項式。

對於一個有快速收斂幂級數的函數而言，若展開到一定項次後截止不再展開，截止產生的誤差接近截止後的第一項，因此誤差可以由截止後的第一項代表。若是用切比雪夫多项式展開，也會有一様的結果。若切比雪夫展開只展開到${\displaystyle T_{N}}$ ，後面截止，其誤差會接近${\displaystyle T_{N+1}}$ 的整數倍。切比雪夫多项式的特點是在[−1, 1]區間以內．其數值會在+1和−1之間震盪。${\displaystyle T_{N+1}}$ 有N+2個極點。因此f(x)和切比雪夫展開的誤差接近一個有N+2個極點的函數，因此為近似最佳的N次多項式^[2]。

在上面中，可以看到藍色線（切比雪夫近似的誤差）有時比紅色線（最佳多項式的誤差）接近x軸，但有時藍色線反而離x軸較遠，因此切比雪夫近似和最佳多項式畢竟還是有差異。不過exp函數是快速收斂的函數，切比雪夫近似的誤差會比log函數要好。

切比雪夫近似是數值積分方法Clenshaw–Curtis正交法（英语：Clenshaw–Curtis quadrature）的基礎。

雷米兹演算法

雷米兹演算法是在1934年由蘇俄數學家雷米兹（英语：Evgeny Yakovlevich Remez）提出的演算法^[3]。可用來產生在一定區間內逼近函數f(x)的最佳多項式P(x)。雷米兹演算法是一種迭代式的演算法，最後會收斂到使誤差函數N+2個極值的多項式。

雷米兹演算法是用以下的事實為基礎：可以在有N+2個測試點的情形下，創建一個N次多項式，其誤差函數在0附近震盪。

假設N+2個測試點${\displaystyle x_{1}}$ , ${\displaystyle x_{2}}$ , ... ${\displaystyle x_{N+2}}$ （其中${\displaystyle x_{1}}$ 和${\displaystyle x_{N+2}}$ 假設是區間的二個端點），需求解以下的多項式：

${\displaystyle P(x_{1})-f(x_{1})=+\varepsilon \,}$ 

${\displaystyle P(x_{2})-f(x_{2})=-\varepsilon \,}$ 

${\displaystyle P(x_{3})-f(x_{3})=+\varepsilon \,}$ 

${\displaystyle \vdots }$ 

${\displaystyle P(x_{N+2})-f(x_{N+2})=\pm \varepsilon .\,}$ 

等式右側的正負號交替出現。因此可以得到下式：

${\displaystyle P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\dots +P_{N}x_{1}^{N}-f(x_{1})=+\varepsilon \,}$ 

${\displaystyle P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})=-\varepsilon \,}$ 

${\displaystyle \vdots }$ 

既然${\displaystyle x_{1}}$ , ..., ${\displaystyle x_{N+2}}$ 給定，其各次方的幂次也是已知，而${\displaystyle f(x_{1})}$ , ..., ${\displaystyle f(x_{N+2})}$ 也是已知。上式就變成由N+2的線性方程組成的聯立方程．有N+2個變數，分別是${\displaystyle P_{0}}$ , ${\displaystyle P_{1}}$ , ..., ${\displaystyle P_{N}}$ 及${\displaystyle \varepsilon }$ 。可以解出上式的多項式P及誤差${\displaystyle \varepsilon }$ 。

下圖產生一個在[−1, 1]區間內逼近${\displaystyle e^{x}}$ 的四階多項式，六個測試點為 −1, −0.7, −0.1, +0.4, +0.9和1。在圖中將二端點以外的測試點標示綠色，其誤差${\displaystyle \varepsilon }$ 為 is 4.43 x 10⁻⁴。

 

要產生在[−1, 1]區間內逼近${\displaystyle e^{x}}$ 的四階多項式，依雷米兹演算法的第一步計算逼近多項式的誤差。垂直的一格為10⁻⁴

注意到上圖在六個測試點上的誤差的確是${\displaystyle \pm \varepsilon }$ ，但極值不是在測試點上。若極值在測試點上（P(x)-f(x)在測試點上有最大值或最小值），在此這個區間的誤差都不會超過${\displaystyle \pm \varepsilon }$ ，此多項式即為最佳多項式。

雷米兹演算法的第二步就是將測試點移到誤差函數有最大值或最小值，例如上圖中−0.1的測試點需移到−0.28。移動的方式可以進行一輪牛頓法，來取新的測試點位置，由於知道P(x)−f(x)的一階及二階導數，因此可以大略計算測試點要移到哪裡才能使誤差函數的微分為零。計算多項式P(x)的一階及二階導數並不困難，但雷米兹演算法需要可以計算f(x)的一階及二階導數，而且需要很高的精度，其精度需求要比雷米兹演算法輸出期望的精度要高。

在移動測試點後，會產生新的線性聯立方程，求解後得到新的多項式，再利用牛頓法去找下一組測試點……，一直到結果收斂到需要的精度為止。雷米兹演算法收斂速度很快，對於良態的函數，雷米兹演算法是二次收斂，若測試點是在正確位置的${\displaystyle 10^{-15}}$ 誤差範圍內，下次測試點是在正確位置的${\displaystyle 10^{-30}}$ 誤差範圍內。

使用雷米兹演算法時，一般會選切比雪夫多項式${\displaystyle T_{N+1}}$ 的零點為初始測試點，因為最後的誤差函數會類似切比雪夫多項式。

相關條目

• 切比雪夫多项式
• 廣義傅立葉級數（英语：generalized Fourier series）
• 正交多項式
• 正交基
• 傅里叶级数
• 邵德尔基（英语：Schauder basis）
• 帕德逼近
• 函數逼近（英语：Function approximation）
• 樣條函數

参考文献

1. M. J. D. Powell. . Cambridge University Press. 1981: p.3 [2013-07-22]. ISBN 0521295149. （原始内容存档于2016-03-10）.  引文格式1维护：冗余文本 (link)
2. 冯有前. 数值分析. 清华大学出版社有限公司. 2005: p.89. ISBN 9787810824958.  引文格式1维护：冗余文本 (link)
3. E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
   "Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
   "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934).