跳至內容

雷米茲演算法

維基百科,自由的百科全書

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

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

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

程序

算法的主要目的是從一個集合得到一個可以逼近函數的多項式。集合由近似的區間上的個取樣點組成,通常由Chebyshev多項式線性映射至該區間得到。算法步驟如下:

  1. 解線性方程組
(其中 ),
未知數為
  1. 使用 作為多項式 的系數。
  2. 找出的局部極大誤差點,組成集合
  3. 若所有 都是相同大小,僅正負號不同的話,則 為極小化極大逼近多項式。否則的話,使用取代並重複上述步驟。

此結果稱為極小化極大逼近算法的最佳逼近多項式。

初始化選擇

由於切比雪夫節點在多項式插值理論中所扮演的角色,故通常選擇其為初始近似的方法。由拉格朗日插值法 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 理論說明在這種形況下,沒有誤差少於 En 次多項式存在。

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

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

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

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


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

變異

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

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

外部連結