雷米兹算法

雷米兹算法，或称雷米兹交换算法，由叶夫根尼·列维奇·雷米兹于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|\}$ 足够小且不再递减。

## 变异

有时候在最大绝对差异点的附近，会有复数个点同时被取代。

有时候相对误差会被用来衡量函式与其近似的差异，特别是在电脑上用浮点数做运算的函式。