跳转到内容

雷米兹算法

维基百科,自由的百科全书

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

一个在切比雪夫空间的典型例子是 n 次项切比雪夫多项式的子空间,属于实数连续函式之向量空间,定义于 C[a, b] 区间。

给定一子空间,其最佳近似多项式的定义为:可将此近似多项式与原始函式之最大绝对差异最小化者。 在这个情况下,可由equioscillation theorem使其解更精确

程序

[编辑]

算法的主要目的是从一个集合得到一个可以逼近函数的多项式。集合由近似的区间上的个取样点组成,通常由Chebyshev多项式线性映射至该区间得到。算法步骤如下:

  1. 解线性方程组
(其中 ),
未知数为
  1. 使用 作为多项式 的系数。
  2. 找出的局部极大误差点,组成集合
  3. 若所有 都是相同大小,仅正负号不同的话,则 为极小化极大逼近多项式。否则的话,使用取代并重复上述步骤。

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

初始化选择

[编辑]

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

其中节点 (t1, ..., tn + 1) 之拉格朗日插值法算子的常数为

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

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

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

for

而上界为

Lev Brutman 计算出对 的边界,而 为切比雪夫多项式之零点

Rüdiger Günttner由对 之较粗略的估算计算出

细节讨论

[编辑]

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

步骤 1: 给定 , 求 n+2 条等式之线性系统之解

(其中 ),
对于未知的 E.

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

计算前n+1个节点之 标准 n 阶插值 , 以及对于 之标准 n 阶插值

至此,需要 次数值运算。

之间,多项式 有其 i-阶 零点zero between and ,因此在 之间无任何零点,意即 正负号 相同。

线性组合 亦为一 n 次多项式

选择任何 E ,对 ,下列式子与上述等式相同:

E 得:

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

是完整定义的。

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

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

步骤 2 把多项式表示由 转为 .

步骤 3 依照以下所述改善输入节点 的误差

在每个 P-领域,现在的节点 将被区域最大 取代,同样在每个 N-领域, 将被区域最小取代, 在这部分并不要求高精确律。

, 其大小 皆大于或等于 Ede La Vallée Poussin 理论及其证明也可以应用至 , 而使此 n 次多项式有最小可能误差的新下界为


步骤 4: 分别以 为新的上下界,此迭代算法的终止条件为: 重复上述步骤直到 足够小且不再递减。

变异

[编辑]

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

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

外部链接

[编辑]