雷米兹算法

算法的主要目的是从一个集合${\displaystyle X}$ 得到一个可以逼近函数${\displaystyle f}$ 的多项式。集合${\displaystyle X}$ 由近似的区间上的${\displaystyle n+2}$ 个取样点${\displaystyle x_{1},x_{2},...,x_{n+2}}$ 组成，通常由Chebyshev多项式线性映射至该区间得到。算法步骤如下：

1. 解线性方程组

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

未知数为 ${\displaystyle b_{0},b_{1},...,b_{n}}$  和 ${\displaystyle E}$ 。

1. 使用 ${\displaystyle b_{i}}$  作为多项式 ${\displaystyle P_{n}}$  的系数。
2. 找出${\displaystyle |P_{n}(x)-f(x)|}$ 的局部极大误差点，组成集合${\displaystyle M}$ 。
3. 若所有 ${\displaystyle m\in M}$  都是相同大小，仅正负号不同的话，则 ${\displaystyle P_{n}}$  为极小化极大逼近多项式。否则的话，使用${\displaystyle M}$ 取代${\displaystyle X}$ 并重复上述步骤。

此结果称为极小化极大逼近算法的最佳逼近多项式。

初始化选择

由于切比雪夫节点在多项式插值理论中所扮演的角色，故通常选择其为初始近似的方法。由拉格朗日插值法 L_n(f) 初始化一函式 f 之最佳化问题，可以证明此初始近似之边界限制为:

${\displaystyle \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) 之拉格朗日插值法算子的常数为

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

T 为切比雪夫多项式的零点，而

${\displaystyle \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})}}.}$ 

对提供次最佳之切比雪夫节点来说，其渐近线为

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

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

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

而上界为

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

Lev Brutman 计算出对 ${\displaystyle n\geq 3}$  的边界，而 ${\displaystyle {\hat {T}}}$  为切比雪夫多项式之零点

${\displaystyle {\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由对 ${\displaystyle n\geq 40}$  之较粗略的估算计算出

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

在此将提供先前简述步骤的详细内容，在这个章节令指数 i 从 0 跑到 n+1.

步骤 1: 给定 ${\displaystyle x_{0},x_{1},...x_{n+1}}$ , 求 n+2 条等式之线性系统之解

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

对于未知的 ${\displaystyle b_{0},b_{1},...b_{n}}$  和 E.

可以很清楚地观察到，在这个式子里 ${\displaystyle (-1)^{i}E}$  若要成立，只有在节点 ${\displaystyle x_{0},...,x_{n+1}}$  为 排序 的情况下才能达到，无论是严格递增或递减。这样一来这个线性系统便有唯一解。(广为人知的，并非每个线性系统都可以求解)。 此外，求解之复杂度最少为 ${\displaystyle O(n^{2})}$  ，而一个从函式库求解的标准计算器需要 ${\displaystyle O(n^{3})}$  的复杂度，在此有一简单证明:

计算前n+1个节点之 ${\displaystyle f(x)}$  标准 n 阶插值 ${\displaystyle p_{1}(x)}$ ， 以及对于 ${\displaystyle (-1)^{i}}$  之标准 n 阶插值 ${\displaystyle p_{2}(x)}$ 

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

至此，需要 ${\displaystyle O(n^{2})}$  次数值运算。

在 ${\displaystyle x_{i-1}}$  与 ${\displaystyle x_{i},\ i=1,...,n}$  之间，多项式 ${\displaystyle p_{2}(x)}$  有其 i-阶 零点zero between ${\displaystyle x_{i-1}}$  and ${\displaystyle x_{i},\ i=1,...,n}$ ，因此在 ${\displaystyle x_{n}}$  与 ${\displaystyle x_{n+1}}$ 之间无任何零点，意即 ${\displaystyle p_{2}(x_{n})}$  与 ${\displaystyle p_{2}(x_{n+1})}$  正负号 ${\displaystyle (-1)^{n}}$  相同。

线性组合 ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$  亦为一 n 次多项式

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

选择任何 E ，对 ${\displaystyle i=0,...,n}$  ，下列式子与上述等式相同:

${\displaystyle 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 得:

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

如前述所提及，上式分母之两项有相同正负号，因此

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

是完整定义的。

给定 n+2 阶节点，其误差为正负轮流:

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

de La Vallée Poussin 理论说明在这种形况下，没有误差少于 E 之 n 次多项式存在。

步骤 2 把多项式表示由${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$  转为 ${\displaystyle p(x)}$ .

步骤 3 依照以下所述改善输入节点 ${\displaystyle x_{0},...,x_{n+1}}$  的误差 ${\displaystyle \pm E}$ 。

在每个 P-领域，现在的节点 ${\displaystyle x_{i}}$  将被区域最大 ${\displaystyle {\bar {x}}_{i}}$  取代，同样在每个 N-领域， ${\displaystyle x_{i}}$  将被区域最小取代， 在这部分并不要求高精确律。

令 ${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$ ， 其大小 ${\displaystyle |z_{i}|}$  皆大于或等于 E。de La Vallée Poussin 理论及其证明也可以应用至 ${\displaystyle z_{0},...,z_{n+1}}$ ， 而使此 n 次多项式有最小可能误差的新下界为 ${\displaystyle \min\{|z_{i}|\}\geq E}$ 。

步骤 4: 分别以 ${\displaystyle \min \,\{|z_{i}|\}}$  与 ${\displaystyle \max \,\{|z_{i}|\}}$  为新的上下界，此迭代算法的终止条件为: 重复上述步骤直到 ${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$  足够小且不再递减。

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

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

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