雷米兹算法,或称雷米兹交换算法,由叶夫根尼·列维奇·雷米兹于1934年所发表。
雷米兹算法为一寻找函式简易近似之迭代算法,特别是定义于切比雪夫空间的函式效果最佳。
一个在切比雪夫空间的典型例子是 n 次项切比雪夫多项式的子空间,属于实数连续函式之向量空间,定义于 C[a, b] 区间。
给定一子空间,其最佳近似多项式的定义为:可将此近似多项式与原始函式之最大绝对差异最小化者。
在这个情况下,可由equioscillation theorem使其解更精确
算法的主要目的是从一个集合
得到一个可以逼近函数
的多项式。集合
由近似的区间上的
个取样点
组成,通常由Chebyshev多项式线性映射至该区间得到。算法步骤如下:
- 解线性方程组
(其中
),
- 未知数为
和
。
- 使用
作为多项式
的系数。
- 找出
的局部极大误差点,组成集合
。
- 若所有
都是相同大小,仅正负号不同的话,则
为极小化极大逼近多项式。否则的话,使用
取代
并重复上述步骤。
此结果称为极小化极大逼近算法的最佳逼近多项式。
由于切比雪夫节点在多项式插值理论中所扮演的角色,故通常选择其为初始近似的方法。由拉格朗日插值法 Ln(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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8494d63c0d249bc41b88423fc00aafb151609ecf)
其中节点 (t1, ..., tn + 1) 之拉格朗日插值法算子的常数为
![{\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a108ac745b822c419112d18a7c1fef461b995b40)
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})}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13ceae32ea6e00edc3c1b20219b19f28cc60ef84)
对提供次最佳之切比雪夫节点来说,其渐近线为
![{\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/623195986be2dae0f192a73a87cd1c8740426cbb)
(γ 为 欧拉-马歇罗尼常数),
for ![{\displaystyle n\geq 1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc38ec6af7dd11fdc9baa67365f23906d76da4bb)
而上界为
![{\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/392018b61323b6769528849fdd641f917bff25b1)
Lev Brutman 计算出对
的边界,而
为切比雪夫多项式之零点
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/646d942c1298201cb1ee7e58b66866994a065045)
Rüdiger Günttner由对
之较粗略的估算计算出
![{\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2f17e8c3d67e0d767dd891d277127defd87c6be0)
在此将提供先前简述步骤的详细内容,在这个章节令指数 i 从 0 跑到 n+1.
步骤 1: 给定
, 求 n+2 条等式之线性系统之解
(其中
),
- 对于未知的
和 E.
可以很清楚地观察到,在这个式子里
若要成立,只有在节点
为 排序 的情况下才能达到,无论是严格递增或递减。这样一来这个线性系统便有唯一解。(广为人知的,并非每个线性系统都可以求解)。
此外,求解之复杂度最少为
,而一个从函式库求解的标准计算器需要
的复杂度,在此有一简单证明:
计算前n+1个节点之
标准 n 阶插值
,
以及对于
之标准 n 阶插值
![{\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caea78d7ce133134d92dfda6abe756d3eadf1c1c)
至此,需要
次数值运算。
在
与
之间,多项式
有其 i-阶 零点zero between
and
,因此在
与
之间无任何零点,意即
与
正负号
相同。
线性组合
亦为一 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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a18b5de18b9f260be884f7d98f00ab45cadc643d)
选择任何 E ,对
,下列式子与上述等式相同:
![{\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3003073e90e2b99b7ae21c352c2b80045cfde0d3)
解 E 得:
![{\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+(-1)^{n}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d47a70c63e7f8f141291e02e94ec6e6349f5091)
如前述所提及,上式分母之两项有相同正负号,因此
![{\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b17906de89ced54aae1644876138412e295d6b9c)
是完整定义的。
给定 n+2 阶节点,其误差为正负轮流:
![{\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d81d3b394104d77f8917e35d68f3b11c7e677f5)
de La Vallée Poussin 理论说明在这种形况下,没有误差少于 E 之 n 次多项式存在。
步骤 2 把多项式表示由
转为
.
步骤 3 依照以下所述改善输入节点
的误差
。
在每个 P-领域,现在的节点
将被区域最大
取代,同样在每个 N-领域,
将被区域最小取代,
在这部分并不要求高精确律。
令
, 其大小
皆大于或等于 E。de La Vallée Poussin 理论及其证明也可以应用至
,
而使此 n 次多项式有最小可能误差的新下界为
。
步骤 4: 分别以
与
为新的上下界,此迭代算法的终止条件为:
重复上述步骤直到
足够小且不再递减。
有时候在最大绝对差异点的附近,会有复数个点同时被取代。
有时候相对误差会被用来衡量函式与其近似的差异,特别是在电脑上用浮点数做运算的函式。