雷米兹演算法

雷米兹演算法，或称雷米兹交换演算法，由叶夫根尼·列维奇·雷米兹于1934年所发表。雷米兹演算法为一寻找函式简易近似之迭代演算法，特别是定义于切比雪夫空间的函式效果最佳。

一个在切比雪夫空间的典型例子是 n 次项切比雪夫多项式的子空间，属于实数连续函式之向量空间，定义于 C[a, 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$ 并重复上述步骤。

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

初始化选择

由于切比雪夫节点在多项式插值理论中所扮演的角色，故通常选择其为初始近似的方法。由拉格朗日插值法 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$ 。