东北农业大学《数值分析》课件-第二章

东北农业大学

数值分析

第二章

第二章插值法

§1引言

§2拉格朗日插值公式

§3逐步线性插值§4牛顿(Newton)插值§5埃尔米特(Hermite)插值§6有理函数插值§1引言发展历史应用插值问题的提出插值问题所需研究的问题等距节点内插公式刘焯（隋公元544－610年）不等距节点内插公式张遂（唐公元683－727年）等距节点一般插值公式

Newton&Gregory(17世纪）非等距节点一般插值公式J.L.Lagrange(18世纪）发展历史应用对观测数据的处理函数的近似表示曲线曲面拟合导出其它数值方法的依据（如数值积分、数值微分、微分方程数值解等）以近似计算函数值为例来说明散点上的函数值，即已知函数表例：设在实际问题中，某些变量之间的函数关系是存在的，但通常不能用式子表示，只能由实验、观测得到在一系列离如何计算？我们希望寻求一个简单且易于计算的函数来近似，即，一般可选为多多项式、三角多项式、有理函数或样条函数等。有些函数虽有表达式，但较复杂，计算函数值不经济，这时也希望用简单的函数来逼近。插值问题的提出

已知函数在区间上有，求一个多定义，且已知，其中项式,使其满足即要求该多项式的函数曲线要经过

上已知的这n+1个点

同时在其它点上估计误差为

YX研究问题若满足条件的存在，又如何构造？满足插值条件的多项式是否存在，唯一？用近似代替的误差估计？§2拉格朗日插值插值多项式的存在唯一性

拉格朗日插值多项式插值基函数插值基函数的构造

n次拉格朗日型插值多项式截断误差数值实例拉格朗日插值多项式的优缺点插值多项式的存在唯一性Theorem.存在唯一的n

次多项式（1.1)满足条件证明：由(1.1)可得(1.2)（1.2）为一个你n＋1未知量的线性方程组，要证明插值多项式存在唯一，只要证明参数存在且唯一，即只要证明其系数行列式不为零即可。

方程组（1.2）的系数行列式为

此为范德蒙行列式。利用行列式性质可得系数行列式为

由于时，故所有因子，于是

即插值多项式存在唯一。

由方程组（1.2）求的系数，计算量大，且难于得到的简单表达式，下面通过找插值基函数的方法，可得到插值多项式的简单表达式。拉格朗日插值多项式1.插值基函数定义：若n次多项式在n+1个节点上满足条件则称这n+1个n次多项式为节点上的n次插值基函数。2.基函数的构造由上述定义，知存在常数，使得由，可以定出，进而得到：令则

于是可改写成

3.n次拉格朗日型插值多项式是n+1个n次插值基本多项式的线性组合，相应的组合系数是即是一个次数不超过n的多项式,且满足，。拉格朗日插值多项式的截断误差

若在[a,b]上用多项式来近似代替函数f(x),其截断误差记作，即也称为插值多项式的余项，关于插值余项估计，有以下定理：定理：设函数y=f(x)的n阶导数y=f(n)(x)在[a,b]上连续，y=f(n+1)(x)在(a,b)上存在，插值节点为a≤x0<x1<…<xn≤b,

是n次拉格朗日插值多项式，则对任意x[a,b]有：其中(a,b),

，证明：由插值多项式的定义，显然有构造辅助函数有。反复利用Rolle定理，存在(a,b),

使得g(n+1)()=0,即，结论成立。数值实例例．求过点(2,0)(4,3)(6,5)(8,4)(10,1)的拉格朗日型插值多项式。解：用4次插值多项式对5个点插值

于是有例.已知sin0.32=0.314567,sin0.34=0.333487,

sin0.36=0.352274,用Lagrange插值计算sin0.3367的值，并估计截断误差。解：f(x)=sinx,取于是有可以发现，结果有六位有效数字的sinx表完全一致。截断误差为其中故有Lagrange插值公式优缺点优点：结果清晰、紧凑，适用于作理论分析、应用；当节点个数有所变动，整个插值公式发生变化，在实际应用时不方便。§3逐步线性插值

抛物插值的逐步线性插值Aitken插值Neville算法数值实例小结1.抛物插值的逐步线性插值给定如下三个数据点逐步线性插值（Aitken插值）具体步骤如下：Step1.将分别对两点作线性插值，得step2.对两点作线性插值，得显然插值节点；插值节点；插值节点。2.n次Aitken插值设给定数据表

构造n次多项式，步骤如下：step1.将分别对作线性插值，得step2.将分别对作线性插值，得step3.将分别对作线性插值，得……stepn.对两点

作线性插值，得可列表如下(以四次Aitken插值为例）：四次插值三次插值二次插值一次插值3.Neville算法可列表如下(以四次插值为例）：一次插值二次插值三次插值四次插值构造n次多项式，步骤如下：step1.分别对与

两两作线性插值，得step2.分别对与两两作线性插值，得step3.分别对与两两作线性插值，得……stepn.对两点

线性插值，易证得4.数值实例例.已知列表函数x1234y0-5-63用求f(2.5)的近似值。解(1)用Aitken算法列表法求解其中(2)用Neville算法求解其中5.小结由上例可以看出，若需提高插值多项式的次数而增加新插值点时，只须增加一些线性插值项，且前面计算结果无需重算，故Aitken插值、Neville算法具有算法承袭性。另外，这两种算法对于求多项式在某点x处得值较有效，但不适合求多项式本身。§4Newton插值公式

差分及其性质差商及其性质Newton插值公式及误差估计拉格朗日插值与牛顿插值的比较等距节点的Newton向前插值公式等距节点的Newton向后插值公式1.差分及其性质

插值节点为等距节点：如右图所示h称为步长，函数在节点处的函数值为

1.1差分的概念一阶向前差分一阶向后差分一阶中心差分

n阶向前差分如同理可以定义。Δ称为向前差分算子，▽表示向后差分算子，表示中心差分算子，如果用函数表上的值，一阶中心差分应写成

除差分算子外，常用的算子符号还有：不变算子I:;移位算子E：由上面各种算子的定义可得算子间的关系：由可得1.2差分的性质（步长均为h）

性质1:各阶差分均可用函数值表示，如

性质2:可用各阶差分表示函数值。性质3:设是n次多项式，则有性质4:各种差分之间可以互化。如2.差商定义及其性质2.1差商的定义对于具有n+1个插值点的情况，可把插值多项式表示为其中为待定系数，可由插值条件

确定。

由得依次可得到。为写出系数的一般表达式，现引入差商（均差）定义。定义：称为函数关于节点的一阶差商，记为称为函数关于节点的二阶差商。递归地用k-1阶差商来定义k阶差商，称为关于k+1个节点的k阶差商。对于重节点，定义2.2差商（均差）的性质性质1

k阶差商可以表示成k+1个函数值的线性组合,即

可用归纳法证明。例:性质2差商与节点的排列顺序无关(差商的对称性)，即

性质3

若是的n次多项式,则一阶差商是的次多项式,二阶差商是的次多项式;一般地,函数的阶差商是的次多项式,而当时,阶差商为零。

证：若是的n

次多项式，则也是n

次多项式，且有，则可分解为其中为n-1次多项式，故有为n-1次多项式。性质4若，则性质5在等距插值的情况下,由定义可得出差分和差商有如下关系：利用差商的定义,可以用递推法来计算差商。差商表如下：

一阶差商

二阶差商

三阶差商

如要再增加一个节点,计算四阶差商时,只须表中再要增加一行即可。

3牛顿插值公式

根据差商定义，把看成上的一点，可得

只要把后一式代入前一式，得:

最后一项中,差商部分含有,为余项部分,记作

而前n+1项中,差商部分都不含有,因而前n+1项是关于的n次多项式,记作于是,上式记为这就是牛顿插值公式。由牛顿插值公式与（2.1）式比较知：易证牛顿插值公式插值节点。

例2:已知求满足以上插值条件的牛顿型插值多项式。解:12340-5-63一阶差商二阶差商三阶差商12340-5-63-5-19251由上述差商表对角线上取得的值则牛顿三次插值多项式为

4.拉格朗日插值与牛顿插值的比较

与均是n次多项式,且均满足插值条件:由插值多项式的唯一性,,因而,两个公式的余项是相等的,即则可知n阶差商与导数的关系如下：（2）当插值多项式从n-1次增加到n次时,拉格朗日型插值必须重新计算所有的基本插值多项式;而对于牛顿型插值,只需用表格再计算一个n阶差商,然后加上一项即可。（3）牛顿型插值余项公式对是由离散点给出或导数不存在时均适用。

5Newton向前插值公式将牛顿差商（均差）插值公式中各阶差商（均差）用相应差分代替，就可得到各种形式的等距结点插值公式。如果节点为，要计算附近点的函数的值，可令于是

把其代入牛顿插值公式，再利用差分与差商之间的关系，得牛顿向前插值公式其余项为：6Newton向后插值公式如果要计算附近点的函数的值，插值点应按的次序排列，可令，同理可得牛顿向后插值公式：

其余项为

向前、向后差分表

一阶差分

二阶差分三阶n阶差分差分

例已知函数的数值表：试作出的三次Newton向前向后插值公式，并计算、的近似值。解：由令0123121764构造差分表如下：有上表，得012312176411547143218牛顿三次向前、向后插值公式分别为得§5Hermite插值公式Hermite插值问题的提出三次Hermite插值插值基函数构造法

满足插值条件的牛顿插值法误差估计2n+1次Hermite插值多项式1.Hermite插值问题的提出由于理论与实践的需要，在构造插值函数时，不但要求在节点上函数值相等，而且还要求它的（高阶）导数值也相等（即要求在节点上具有一定的光滑度），使得插值函数与被插函数贴近程度更好，满足这种要求的插值多项式就是Hermite插值多项式，有时也称为具有重节点插值或切触插值。下面具体讨论三次情形。2.三次Hermite插值问题：求作三次多项式，使之满足：称之为两点三次Hermite插值问题，称满足插值条件（2.1）的为三次Hermite插值多项式。下面采用构造基函数及牛顿插值的方法来确定多项式。2.1基函数构造法构造基函数使之满足则即为所求。由插值条件，有由（2.3）可设再由（2.2）可求得同理可得特别的，在时，得到以区间端点为插值条件得三次Hermite插值多项式：其中2.2Newton插值法

满足插值条件（2.1）式得插值问题可视为重节点Newton插值问题，且则其中各阶差商可由定义直接求得，即2.3误差估计由Newton插值法，可直接得到三次Hermite

插值问题的截断误差为：于是有下述定理定理：设是以为插值节点的三次Hermite插值多项式，在内存在，其中是包含的任一区间，则对任意给定的，总存在依赖于的点，使3.2n+1次Hermite插值多项式

给定n+1个节点和相应的函数值和导数值：则可构造2n+1次Hermite插值多项式满足条件：1）是不超过2n+1次多项式；2）用类似于前面的方法在n+1个节点上构造2n+1次Hermite插值多项式为其中插值基函数（定义如前）为定理：设是以为插值节点的2n+1次Hermite插值多项式，在内存在，其中是包含节点的任一区间，则对任意给定的，总存在依赖于的点，使§6有理函数插值研究有理插值问题的理论背景有理函数插值的基本概念有理插值问题的提出研究的问题有理插值的存在性连分式插值连分式插值在图像处理中的应用1.研究有理插值问题的理论背景前面讨论了用多项式逼近函数，它是一种计算简便的逼近工具，但当函数在某点附近无界，或者当而趋于某一定值时，采用多项式插值是不恰当的，这是因为多项式不能反映在某点附近无界的函数性态，而当时，多项式的值总是趋于无穷，但有理分式函数，如却能刻划这些函数性态。2.有理函数插值2.1问题的提出设给定在m+n+1个互异节点上的值，所谓有理函数插值问题，即寻求有理分式函数使之满足条件2.2研究的问题

表面上有m+n+2个待定参数，，但实际上只有m+n+1个待定参数，故从插值条件（2.1）可得关于系数的m+n+1个方程组。下面必须研究三个问题：解的存在及唯一性；如何构造有理插值函数；误差估计问题。2.3有理分式函数的基本概念设有两个分式函数若存在一个非零常数a，使得则称与恒等，记为.若则称它们是等价的，记为（以后均视为同一函数）.有理插值问题的不一定总是存在的。例1.给定型值点，求形如的有理插值。解由插值条件，易求得取则得于是显然当时，有，而与是值为3的同一函数的两种不同表现形式。在几何上当时，是一条平行于x轴的直线，它不可能通过型值点，故它不是（2.1）的解。因此，满足插值条件（2.1）的是不存在的。定理1插值问题（2.1）若有解，则其解必唯一。证明：设有两个有理函数均满足插值条件(2.1),即由此可推出表明次数不超过m+n的多项式有1+m+n个互异零点。由代数基本定理，知由等价性定义知2.4有理插值的存在性定理2若（2.1）对应的齐次线性方程组有非平凡解存在，为使满足插值条件（2.1）的最简有理分式存在，必须且只须方程组（2.4）的任意非平凡解在约去一切公因子后得到的互质多项式仍是方程组（2.4）的解。3.连分式插值3.1连分式设和为两个复数列，称形如：的分式为连分式（Continuedfraction）,记做：

或，称为上式的第n

次渐近连分式(AsymptoticContinuedFractions)，或第n项截断连分式(TruncatedContinuedFractions)。连分式是一种有效的逼近工具。例如：由可得令第n项截断连分式为因此，可用下列连分式逼近函数：取时，得到的一组近似值而的Maclaurin展开式为取，函数的精确值为0.4，可以分别用来逼近，得下表：显然，收敛速度更快。因此，可得到结论：函数的连分式（非线性）展开与线性展开相比，有更好的逼近效果。n123450.480.480.36480.38710.38690.40220.38690.39960.40920.40013.2Thiele型连分式插值

定义3.2.1

称下述形式的连分式：

为Thiele型连分式.定义3.2.2

设是一实点集，函数在有定义，令

称为函数在处的i

阶逆差商。定理设其中为函数在处的k

阶逆差商,且则有证明：反复利用逆差商的定义知证毕。定义3.2.3如果连分式满足则称该连分式为函数的型Thiele插值连分式。例给定型值点求，使之满足条件解构造逆差商表：x-2-1012

y-2-1-101得xy一阶二阶三阶四阶-2-2012-2-1-101123/24/31491/31/4-12分段低次插值多项式插值的问题分段线性插值分段三次埃尔米特插值小结1.多项式插值的问题前面介绍了构造插值公式的方法，并分析了它们的余项。在实际应用插值函数作近似计算时，总希望插值公式余项的绝对值小一些，即使得逼近的精度好。从表达式看，似乎提高插值多项式的次数便可达到目的，但实际上并非如此。在插值过程中有两种误差：1）由插值函数替代被插函数所引起的截断误差；2）节点数据的误差。这种误差在插值过程中是否会被扩散或放大呢？这就是插值过程的稳定性问题。对任意的插值节点，当