雷米兹算法

雷米兹算法，或称雷米兹交换算法，由叶夫根尼·列维奇·雷米兹于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₁, ..., 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.