雷米茲演算法

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

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

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

## 程序

算法的主要目的是從一個集合 $X$ 得到一個可以逼近函數 $f$ 的多項式。集合 $X$ 由近似的區間上的 $n+2$ 個取樣點 $x_{1},x_{2},...,x_{n+2}$ 組成，通常由 Chebyshev 多項式線性映射至該區間得到。算法步驟如下：

1. 解線性方程組

　
: $b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (其中 $i=1,2,...n+2$ ),

　
: 未知數為 $b_{0},b_{1},...,b_{n}$ 和 $E$ 。

1. 使用 $b_{i}$ 作為多項式 $P_{n}$ 的係數。
2. 找出 $|P_{n}(x)-f(x)|$ 的局部極大誤差點，組成集合 $M$ 。
3. 若所有 $m\in M$ 都是相同大小，僅正負號不同的話，則 $P_{n}$ 為極小化極大逼近多項式。否則的話，使用 $M$ 取代 $X$ 並重複上述步驟。

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

### 初始化選擇

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

　
: $\lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert f-p\rVert $

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

　
: $\lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),$

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

　
: $\lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}(x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i})}}.$

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

　
: ${\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}$

(_γ_ 為 歐拉 - 馬歇羅尼常數)，

　
: $0<\alpha _{n}<{\frac {\pi }{72n^{2}}}$ for $n\geq 1,$

而上界為

　
: ${\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1$

Lev Brutman 計算出對 $n\geq 3$ 的邊界，而 ${\hat {T}}$ 為切比雪夫多項式之零點

　
: ${\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1}{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.$

Rüdiger Günttner 由對 $n\geq 40$ 之較粗略的估算計算出

　
: ${\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.$

## 細節討論

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

**步驟 1:** 給定 $x_{0},x_{1},...x_{n+1}$ , 求 _n_+2 條等式之線性系統之解

　
: $b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (其中 $i=0,1,...n+1$ ),

　
: 對於未知的 $b_{0},b_{1},...b_{n}$ 和 _E_.

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

計算前 _n_+1 個節點之 $f(x)$ 標準 _n_ 階插值 $p_{1}(x)$ ，
以及對於 $(-1)^{i}$ 之標準 _n_ 階插值 $p_{2}(x)$

　
: $p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.$

至此，需要 $O(n^{2})$ 次數值運算。

在 $x_{i-1}$ 與 $x_{i},\ i=1,...,n$ 之間，多項式 $p_{2}(x)$ 有其 _i_- 階 零點 zero between $x_{i-1}$ and $x_{i},\ i=1,...,n$ ，因此在 $x_{n}$ 與 $x_{n+1}$ 之間無任何零點，意即 $p_{2}(x_{n})$ 與 $p_{2}(x_{n+1})$ 正負號 $(-1)^{n}$ 相同。

線性組合 $p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E$ 亦為一 _n_ 次多項式

　
: $p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.$

選擇任何 _E_ ，對 $i=0,...,n$ ，下列式子與上述等式相同:

　
: $p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E$

解 _E_ 得:

　
: $E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.$

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

　
: $p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}$

是完整定義的。

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

　
: $p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.$

_de La Vallée Poussin_ 理論說明在這種形況下，沒有誤差少於 _E_ 之 _n_ 次多項式存在。

**步驟 2** 把多項式表示由 $b_{0}+b_{1}x+...+b_{n}x^{n}$ 轉為 $p(x)$ .

**步驟 3** 依照以下所述改善輸入節點 $x_{0},...,x_{n+1}$ 的誤差 $\pm E$ 。

在每個 P - 領域，現在的節點 $x_{i}$ 將被區域最大 ${\bar {x}}_{i}$ 取代，同樣在每個 N - 領域， $x_{i}$ 將被區域最小取代，
在這部分並不要求高精確律。

令 $z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})$ ， 其大小 $|z_{i}|$ 皆大於或等於 _E_。_de La Vallée Poussin_ 理論及其證明也可以應用至 $z_{0},...,z_{n+1}$ ，
而使此 _n_ 次多項式有最小可能誤差的新下界為 $\min\{|z_{i}|\}\geq E$ 。

 
**步驟 4:** 分別以 $\min \,\{|z_{i}|\}$ 與 $\max \,\{|z_{i}|\}$ 為新的上下界，此迭代演算法的終止條件為:
重複上述步驟直到 $\max\{|z_{i}|\}-\min\{|z_{i}|\}$ 足夠小且不再遞減。

## 變異

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

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

## 外部連結

* Intro to DSP
* Aarts, Ronald M.; Bond, Charles; Mendelsohn, Phil; and Weisstein, Eric W. Remez Algorithm. MathWorld.