雷米茲演算法

雷米茲演算法，或稱雷米茲交換演演算法，由葉夫根尼·列維奇·雷米茲於1934年所發表。

雷米茲演算法為一尋找函式簡易近似之迭代演演算法，特別是定義於切比雪夫空間的函式效果最佳。

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

給定一子空間，其最佳近似多項式的定義為：可將此近似多項式與原始函式之最大絕對差異最小化者。

在這個情況下，可由equioscillation theorem使其解更精確

## 程序

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

- 解線性方程組

$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$。

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

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

### 初始化選擇

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

$$\lVert f - L_n(f)\rVert_\infty \le (1 + \lVert L_n\rVert_\infty) \inf_{p \in P_n} \lVert f - p\rVert$$

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

$$\lVert L_n\rVert_\infty = \overline{\Lambda}_n(T) = \max_{-1 \le x \le 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 \ne 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}{72 n^2}$ for $n \ge 1,$

而上界為

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

Lev Brutman 計算出對 $n \ge 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 \ge 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_1x + \ldots + b_nx^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_1x + ... + b_nx^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|\}$ 足夠小且不再遞減。

## 變異

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

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