逼近理論

逼近理論是將如何將一函數用較簡單的函數來找到最佳逼近，且所產生的誤差可以有量化的表徵，以上提及的“最佳”及“較簡單”的實際意義都會隨着應用而不同 ^[1]  。

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

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

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

只要選定了多項式的次數及逼近的範圍，就可以用以使最壞情形誤差最小化的原則，來選擇逼近多項式，其目的為最小化

的絕對值，其中P(x)為逼近多項式，而f(x)為實際的函數。對於一個良態的函數，存在一個N次的多項式，使誤差曲線的大小在

和

之間震盪至多N+2次，其最壞情形的誤差為

。一個N次的多項式可以內插曲線中的N+1個點。當然也有可能製造一些極端的函數，使得滿足上述條件的多項式不存在，但在實務上很少需要為這様的函數進行逼近 ^[2]  。

例如下圖中的紅線就是用N=4情形下用多項式逼近log(x)及exp(x)的誤差。誤差在

和

之間震盪。每一個例子中的極端有N+2個，也就是6個。極值出現在區間的端點，也就是圖的最左邊及最右邊。

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

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

若計算一函數切比雪夫展開的係數 ^[3]  ：

只展開到

項為止，可以得到一個逼近f(x)的N次多項式。

對於一個有快速收斂冪級數的函數而言，若展開到一定項次後截止不再展開，截止產生的誤差接近截止後的第一項，因此誤差可以由截止後的第一項代表。若是用切比雪夫多項式展開，也會有一様的結果。若切比雪夫展開只展開到

，後面截止，其誤差會接近

的整數倍。切比雪夫多項式的特點是在[−1, 1]區間以內．其數值會在+1和−1之間震盪。

有N+2個極點。因此f(x)和切比雪夫展開的誤差接近一個有N+2個極點的函數，因此為近似最佳的N次多項式。

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

切比雪夫近似是數值積分方法Clenshaw–Curtis正交法的基礎。

雷米茲算法是在1934年由蘇俄數學家雷米茲提出的算法。可用來產生在一定區間內逼近函數f(x)的最佳多項式P(x)。雷米茲算法是一種迭代式的算法，最後會收斂到使誤差函數N+2個極值的多項式。

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

假設N+2個測試點

（其中

和

假設是區間的二個端點），需求解以下的多項式：

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

既然

給定，其各次方的冪次也是已知，而

也是已知。上式就變成由N+2的線性方程組成的聯立方程．有N+2個變數，分別是

,

, ...,

及

。可以解出上式的多項式P及誤差

。

下圖產生一個在[−1, 1]區間內逼近

的四階多項式，六個測試點為 −1, −0.7, −0.1, +0.4, +0.9和1。在圖中將二端點以外的測試點標示綠色，其誤差

為4.43 x 10。

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

注意到上圖在六個測試點上的誤差的確是

，但極值不是在測試點上。若極值在測試點上(P(x)-f(x)在測試點上有最大值或最小值），在此這個區間的誤差都不會超過

，此多項式即為最佳多項式。

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

在移動測試點後，會產生新的線性聯立方程，求解後得到新的多項式，再利用牛頓法去找下一組測試點……，一直到結果收斂到需要的精度為止。雷米茲算法收斂速度很快，對於良態的函數，雷米茲算法是二次收斂，若測試點是在正確位置的

誤差範圍內，下次測試點是在正確位置的

誤差範圍內。

使用雷米茲算法時，一般會選切比雪夫多項式

的零點為初始測試點，因為最後的誤差函數會類似切比雪夫多項式。