计算机科学

首页 > 计算机科学

逼近理论

2018-09-06 14:25:52     所属分类:数值分析

数学中的逼近理论是如何将一函数用较简单的函数来找到最佳逼近,且所产生的误差可以有量化的表征英语Characterization (mathematics),以上提及的“最佳”及“较简单”的实际意义都会随着应用而不同。

数学中有一个相关性很高的主题,是用广义傅立叶级数英语generalized Fourier series进行函数逼近,也就是用以正交多项式为基础的级数来进行逼近。

计算机科学中有一个问题和逼近理论有关,就是在数学函式库中如何用计算机或计算器可以执行的功能(例如乘法和加法)尽可能的逼近某一数学函数[1],一般会用多项式或有理函数(二多项式的商)来进行。

逼近理论的目标是尽可能的逼近实际的函数,一般精度会接近电脑浮点运算的精度,一般会用高次的多项式,以及(或者)缩小多项式逼近函数的区间。缩小区间可以针对要逼近的函数,利用许多不同的系数及增益来达到。现在的数学函式库会将区间划分为许多的小区间,每个区间搭配一个次数不高的多项式。

红色是log(x)及最佳多项式的误差,蓝色是log(x)和Chebyshev逼近的误差,x范围都在2, 4区间内,纵轴的格线为10−5。最佳多项式的最大误差为6.07 x 10−5
红色是exp(x)及最佳多项式的误差,蓝色是exp(x)和Chebyshev逼近的误差,x范围都在−1, 1区间内,纵轴的格线为10−4。最佳多项式的最大误差为5.47 x 10−4.

目录

  • 1 最佳多项式
  • 2 切比雪夫近似
  • 3 雷米兹算法
  • 4 相关条目
  • 5 参考文献

最佳多项式

只要选定了多项式的次数及逼近的范围,就可以用以使最坏情形误差最小化的原则,来选择逼近多项式,其目的为最小化的绝对值,其中P(x)为逼近多项式,而f(x)为实际的函数。对于一个良态的函数,存在一个N次的多项式,使误差曲线的大小在之间震荡至多N+2次,其最坏情形的误差为。一个N次的多项式可以内插曲线中的N+1个点。当然也有可能制造一些极端的函数,使得满足上述条件的多项式不存在,但在实务上很少需要为这様的函数进行逼近。

例如右图中的红线就是用N = 4情形下用多项式逼近log(x)及exp(x)的误差。误差在之间震荡。每一个例子中的极端有N+2个,也就是6个。极值出现在区间的端点,也就是图的最左边及最右边。

切比雪夫近似

前六个第一类切比雪夫多项式的图像,其中-1¼<x<1¼, -1¼<y<1¼

切比雪夫近似是利用将函数展开为由切比雪夫多项式组成的各项,依需要的逼近程度决定展开的项次,可以得到很接近多项式的结果。此作法类似进行函数的傅立叶分析,只是用切比雪夫多项式代替分析中用到的三角函数。

若计算一函数切比雪夫展开的系数:

只展开到项为止,可以得到一个逼近f(x)的N次多项式。

对于一个有快速收敛幂级数的函数而言,若展开到一定项次后截止不再展开,截止产生的误差接近截止后的第一项,因此误差可以由截止后的第一项代表。若是用切比雪夫多项式展开,也会有一様的结果。若切比雪夫展开只展开到,后面截止,其误差会接近的整数倍。切比雪夫多项式的特点是在−1, 1区间以内.其数值会在+1和−1之间震荡。N+2个极点。因此f(x)和切比雪夫展开的误差接近一个有N+2个极点的函数,因此为近似最佳的N次多项式[2]

在上面中,可以看到蓝色线(切比雪夫近似的误差)有时比红色线(最佳多项式的误差)接近x轴,但有时蓝色线反而离x轴较远,因此切比雪夫近似和最佳多项式毕竟还是有差异。不过exp函数是快速收敛的函数,切比雪夫近似的误差会比log函数要好。

切比雪夫近似是数值积分方法Clenshaw–Curtis正交法英语Clenshaw–Curtis quadrature的基础。

雷米兹算法

雷米兹算法是在1934年由苏俄数学家雷米兹英语Evgeny Yakovlevich Remez提出的算法[3]。可用来产生在一定区间内逼近函数f(x)的最佳多项式P(x)。雷米兹算法是一种迭代式的算法,最后会收敛到使误差函数N+2个极值的多项式。

雷米兹算法是用以下的事实为基础:可以在有N+2个测试点的情形下,创建一个N次多项式,其误差函数在0附近震荡。

假设N+2个测试点, , ... (其中假设是区间的二个端点),需求解以下的多项式:

等式右侧的正负号交替出现。因此可以得到下式:

既然, ..., 给定,其各次方的幂次也是已知,而, ..., 也是已知。上式就变成由N+2的线性方程组成的联立方程.有N+2个变数,分别是, , ..., 。可以解出上式的多项式P及误差

下图产生一个在−1, 1区间内逼近的四阶多项式,六个测试点为 −1, −0.7, −0.1, +0.4, +0.9和1。在图中将二端点以外的测试点标示绿色,其误差为 is 4.43 x 10−4

要产生在−1, 1区间内逼近的四阶多项式,依雷米兹算法的第一步计算逼近多项式的误差。垂直的一格为10−4

注意到上图在六个测试点上的误差的确是,但极值不是在测试点上。若极值在测试点上(P(x)-f(x)在测试点上有最大值或最小值),在此这个区间的误差都不会超过,此多项式即为最佳多项式。

雷米兹算法的第二步就是将测试点移到误差函数有最大值或最小值,例如上图中−0.1的测试点需移到−0.28。移动的方式可以进行一轮牛顿法,来取新的测试点位置,由于知道P(x)−f(x)的一阶及二阶导数,因此可以大略计算测试点要移到哪里才能使误差函数的微分为零。计算多项式P(x)的一阶及二阶导数并不困难,但雷米兹算法需要可以计算f(x)的一阶及二阶导数,而且需要很高的精度,其精度需求要比雷米兹算法输出期望的精度要高。

在移动测试点后,会产生新的线性联立方程,求解后得到新的多项式,再利用牛顿法去找下一组测试点……,一直到结果收敛到需要的精度为止。雷米兹算法收敛速度很快,对于良态的函数,雷米兹算法是二次收敛,若测试点是在正确位置的误差范围内,下次测试点是在正确位置的误差范围内。

使用雷米兹算法时,一般会选切比雪夫多项式的零点为初始测试点,因为最后的误差函数会类似切比雪夫多项式。

相关条目

  • 切比雪夫多项式
  • 广义傅立叶级数英语generalized Fourier series
  • 正交多项式
  • 正交基
  • 傅里叶级数
  • 邵德尔基英语Schauder basis
  • 帕德逼近
  • 函数逼近英语Function approximation
  • 样条函数

参考文献

  1. ^ M. J. D. Powell. Approximation Theory and Methods. Cambridge University Press. 1981: p.3. ISBN 0521295149. 
  2. ^ 冯有前. 数值分析. 清华大学出版社有限公司. 2005: p.89. ISBN 9787810824958. 
  3. ^ E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
    "Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
    "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934).
版权声明:本文由北城百科网创作,转载请联系管理获取授权,未经容许转载必究。https://www.beichengjiu.com/computerscience/340761.html

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
支付宝扫一扫赏金或者微信支付5毛钱,阅读全文

打开微信扫一扫,即可进行阅读全文哦


相关推荐