雷米茲演算法

雷米茲演算法，或稱雷米茲交換演算法，由葉夫根尼·列維奇·雷米茲於1934年所發表。
雷米茲演算法為一尋找函式簡易近似之迭代演算法，特別是定義於切比雪夫空間的函式效果最佳。

一個在切比雪夫空間的典型例子是 n 次項切比雪夫多项式的子空間，屬於實數連續函式之向量空間，定義於 C[a, b] 區間。

給定一子空間，其最佳近似多項式的定義為：可將此近似多項式與原始函式之最大絕對差異最小化者。
在這個情況下，可由equioscillation theorem使其解更精確

程序

算法的主要目的是从一个集合得到一个可以逼近函数的多项式。集合由近似的区间上的个取样点组成，通常由Chebyshev多项式线性映射至该区间得到。算法步骤如下：
 解线性方程组
 (其中 ),
未知数为  和 。
 使用  作為多項式  的係數。
 找出的局部极大误差点，组成集合。
 若所有  都是相同大小，仅正负号不同的话，则  为极小化极大逼近多项式。否则的话，使用取代并重复上述步骤。
此结果称为极小化极大逼近算法的最佳逼近多项式。
初始化選擇

由於切比雪夫節點在多項式插值理論中所扮演的角色，故通常選擇其為初始近似的方法。由拉格朗日插值法 Ln(f) 初始化一函式 f 之最佳化問題，可以證明此初始近似之邊界限制為:

其中節點 (t1, ..., tn + 1) 之拉格朗日插值法算子的常數為

T 為切比雪夫多項式的零點，而

對提供次最佳之切比雪夫節點來說，其漸近線為

(γ 為 欧拉-马歇罗尼常数)，

 for 

而上界為

Lev Brutman 計算出對  的邊界，而  為切比雪夫多項式之零點

Rüdiger Günttner由對  之較粗略的估算計算出

細節討論
在此將提供先前簡述步驟的詳細內容，在這個章節令指數 i 從 0 跑到 n+1.

步驟 1: 給定 , 求 n+2 條等式之線性系統之解
 (其中 ),
對於未知的  和 E.

可以很清楚地觀察到，在這個式子裡  若要成立，只有在節點  為 排序 的情況下才能達到，無論是嚴格遞增或遞減。這樣一來這個線性系統便有唯一解。(廣為人知的，並非每個線性系統都可以求解)。
此外，求解之複雜度最少為  ，而一個從函式庫求解的標準計算器需要  的複雜度，在此有一簡單證明:

計算前n+1個節點之  標準 n 階插值 ，
以及對於  之標準 n 階插值  

至此，需要  次數值運算。

在  與  之間，多項式  有其 i-階 零點zero between  and ，因此在  與 之間無任何零點，意即  與  正負號  相同。

線性組合  亦為一 n 次多項式

選擇任何 E ，對  ，下列式子與上述等式相同:

解 E 得:

如前述所提及，上式分母之兩項有相同正負號，因此

是完整定義的。

給定 n+2 階節點，其誤差為正負輪流:

de La Vallée Poussin 理論說明在這種形況下，沒有誤差少於 E 之 n 次多項式存在。

步驟 2 把多項式表示由 轉為 .

步驟 3 依照以下所述改善輸入節點  的誤差 。

在每個 P-領域，現在的節點  將被區域最大  取代，同樣在每個 N-領域，  將被區域最小取代，
在這部分並不要求高精確律。

令 ， 其大小  皆大於或等於 E。de La Vallée Poussin 理論及其證明也可以應用至 ，
而使此 n 次多項式有最小可能誤差的新下界為 。

步驟 4: 分別以  與  為新的上下界，此迭代演算法的終止條件為:
重複上述步驟直到  足夠小且不再遞減。

變異
有時候在最大絕對差異點的附近，會有複數個點同時被取代。

有時候相對誤差會被用來衡量函式與其近似的差異，特別是在電腦上用浮點數做運算的函式。

外部連結
Intro to DSP

Category:多項式
Category:逼近理论
Category:数值分析