雷米茲演算法

雷米茲演算法，或稱雷米茲交換演算法，由葉夫根尼·列維奇·雷米茲於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 之最佳化問題，可以證明此初始近似之邊界限制為:

$\Vert f-L_n(f){\Vert }_{\mathrm{\infty }}\le (1+\Vert L_n{\Vert }_{\mathrm{\infty }})\underset{p\in P_n}{\inf }\Vert f-p\Vert$

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

$\Vert L_n{\Vert }_{\mathrm{\infty }}={\bar{\mathrm{\Lambda }}}_n(T)=\underset{-1\le x\le 1}{\max }{\lambda }_n(T;x),$

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

${\lambda }_n(T;x)=\sum _{j=1}^{n+1}|l_j(x)|,l_j(x)=\prod _{\stackrel{i=1}{i\ne j}}^{n+1}\frac{(x-t_i)}{(t_j-t_i)}.$

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

${\bar{\mathrm{\Lambda }}}_n(T)=\frac{2}{\pi }\log (n+1)+\frac{2}{\pi }(\gamma +\log \frac{8}{\pi })+{\alpha }_{n+1}$

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

$0<{\alpha }_n<\frac{\pi }{72n^2}$ for $n\ge 1,$

而上界為

${\bar{\mathrm{\Lambda }}}_n(T)\le \frac{2}{\pi }\log (n+1)+1$

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

${\bar{\mathrm{\Lambda }}}_n(\hat{T})-{\underset{\_}{\mathrm{\Lambda }}}_n(\hat{T})<{\bar{\mathrm{\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\ge 40$ 之較粗略的估算計算出

${\bar{\mathrm{\Lambda }}}_n(\hat{T})-{\underset{\_}{\mathrm{\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,\dots ,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+\dots +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$ 將被區域最大 ${\overline{x}}_i$ 取代，同樣在每個 N-領域， $x_i$ 將被區域最小取代， 在這部分並不要求高精確律。

令 $z_i:=p({\overline{x}}_i)-f({\overline{x}}_i)$， 其大小 $|z_i|$ 皆大於或等於 E。de La Vallée Poussin 理論及其證明也可以應用至 $z_0,...,z_{n+1}$， 而使此 n 次多項式有最小可能誤差的新下界為 $\min \{|z_i|\}\ge E$。

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

變異

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

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

外部連結

• Intro to DSP
• Template:MathWorld