多项式插值课件.ppt

《多项式插值课件.ppt》由会员分享，可在线阅读，更多相关《多项式插值课件.ppt（82页珍藏版）》请在三一文库上搜索。

1、2.1 多项式插值,总结,2.1.4 Hermite插值多项式,2.1.3 均差和Newton插值多项式,2.1.2 Lagrange插值多项式,2.1.1 问题的提出,第二章 函数的插值,学习目标：掌握多项式插值的Lagrange插值公式、牛顿插值公式等，等距节点插值、差分、差商、重节点差商与埃米特插值。重点是多项式插值方法。,2.1.1 问题的提出 函数解析式未知,通过实验观测得到的一组数据, 即在某个区间a, b上给出一系列点的函数值 yi= f(xi) 或者给出函数表,y=f(x),求解：y = f (x) 在 a , b 上任一点处函数值的近似值？,根据 f (x)在n+1个已知点的

2、值，求一个足够光滑又比较简单的函数p(x)作为 f (x)的近似表达式，,插 值 法,然后计算 p(x)在a,b 上点x 处的函数值作为原来函数,f (x)在此点函数值的近似值。,代数多项式、三角多项式、有理函数或样条函数,解决思路,(1.2)式称为插值条件，,x2 xn b 点上的值 y0, y1, , yn . 若存在一简单 函数 p(x), 使得 p(xi) = yi i = 0, 1, 2, , n (1.2),1、定义,f ( x ) 称为被插函数，,a , b 称为插值区间， 称为插值节点 ，,求 p ( x ) 的方法就是插值法。,设函数 f (x) 在a , b上有定义，且已知

3、在 a x0 x1,成立,则称 p( x ) 为 f (x) 的插值函数。,近似计算f (x) 的值、零点、极值点、导数、积分，,插值点在插值区间内的称为内插, 否则称外插,插值函数p(x)在n+1个互异插值节点xi (i=0,1,n ) 处与f(xi)相等,在其它点 x 就用p(x)的值作为f(x) 的近似值。这一过程称为插值，点 x 称为插值点。 换句话说, 插值就是根据被插函数给出的函数表“插出”所要点的函数值。用p(x)的值作为f(x)的近似值,不仅希望p(x)能较好地逼近f(x),而且还希望它计算简单 。,最常用的插值函数是 ?,代数多项式,用代数多项式作插值函数的插值称为多项式插值

4、,本章主要讨论的内容,插值函数的类型有很多种,插值问题,插值法,插值函数,分段函数,三角多项式,本章先讨论插值问题，然后讨论数据拟合的有关问题。,拟合法就是考虑到数据不一定准确，不要求近似表达式 经过所有的点 ，而只要求在给定的 上误差 （i=0，1，n）按某种标准最小。若记 =( 1, 2 ,n )T ，就是要求向量的泛数| 最小。,1. 定义： 若p ( x ) 是次数不超过n 的实系数代数多项式, 即,则称p ( x)为n 次插值多项式。,相应的插值法称为多项式插值法。,常用次数小于（等于）n的实系数代数多项式集合Hn ：,Hn= pn(x)|pn( x)= a0 + a1 x + +

5、an x n，ai为实数,p ( x ) = a0 + a1 x + + an x n,f(x),p(x),从几何上看,曲线 P ( x) 近似 f ( x),研究问题：,（1）满足插值条件的P ( x) 是否存在唯一？,（2）若满足插值条件的P ( x) 存在，如何构造P ( x)？,（3）如何估计用P ( x)近似替代 f ( x) 产生的误差？,2、插值多项式的存在唯一性,设 pn( x )是 f (x) 的插值多项式，,Hn表示次数不超过n 的所有多项,且 pn( x ) Hn .,称插值多项式存在且唯一，就是指在,由(1.2)可得,(1.3),方程组(1.3)有唯一解,插值多项式的唯

6、一性,0 (xixj),定理1 满足条件 (1.2) 的插值多项式存在且唯一。,范德蒙行列式,a0, a1, a2, , an 存在唯一,p(xi) = yi i = 0, 1, 2, , n,Hn 中有且仅有一个 pn( x ) 满足插值条件(1.2)式。,式的集合。,上述的存在唯一性说明，满足插值条件的多项式存在，并且插值多项式与构造方法无关。然而，直接求解方程组(1.3)的方法，不但计算复杂，而且难于得到p(x)的简单表达式。下面，我们将给出不同形式的便于使用的插值多项式。,基本思想：在n次多项式空间Pn中找一组合适的基函数 0(x), 1(x), 3 (x),使,pn(x)=a0 0(

7、x) +a1 1(x) +an 3（x),不同的基函数的选取导致不同的插值方法,Lagrange插值,Newton插值,2.1.2 Lagrange插值多项式,求 n 次多项式 使得,先考察低次插值多项式。,1、线性插值当n=1时，要构造通过两点 (x0 , y0 )和(x1, y1 )的不超过1次的多项式L1(x)，使得,过两 点 (x0 , y0) 与 (x1, y1) 的直线,或,L1(x)是两个线性函数的线性组合,称为节点上线性插值基函数,节点上的线性 插值基函数：,满足,y 1 0 x0 x1 x,例1 已知 , , 求,解: 这里x0=100，y0=10，x1=121，y1=11,

8、 利用线性插值,- 过三点(xk-1, yk-1), (xk , yk) 与(xk+1, yk+1),2、抛物插值法 (n =2 时的二次插值),设插值节点为：xk-1, xk, xk+1 ,求二次插值多项式L2(x)，使得,L2( x j ) = y j , j = k-1, k, k+1 .,的几何意义,基函数法,先求 插值基函数l k-1(x), l k (x), l k+1(x) 二次函数,且在节点,的抛物线,满足：,求 lk-1(x):,再构造插值多项式,L2(x)是三个二次函数的线性组合,由,这种用插值基函数表示的方法容易推广到一般情形。,3、Lagrange 插值多项式(n次),

9、求通过n +1个节点的n 次插值多项式Ln(x)：,先求插值基函数 然后构造插值多项式,设Ln(x)满足插值条件：L n ( xj ) = y j ( j = 0, 1, , n ) .,定义 若n 次多项式 lk ( x ) (k = 0,1,n ) 在各节点,j , k = 0, 1 , n,上满足条件,则称这n +1个n 次多项式为这n +1个节点上的n 次插值基函数。,L2(x) = yk -1 lk 1(x) + yk lk (x) + yk +1 lk +1(x),（类似于前面讨论n =1, 2 时的情形）,先求 插值基函数,， k = 0, 1 , n .,k = 0, 1 ,

10、n .,再构造 插值多项式,（Ln(x)是n+1个插值基函数的线性组合）,定理（Lagrange）插值多项式,通常次数=n , 但特殊情形次数可n ,如：过三点的二次插值多项式,解 按拉格朗日方法，有：,显然，如此构造的L(x) 是不超过n次 多项式。当n=1时，称为线性插值。当n=2时，称为抛物线插值。,练习 给定数据表,求三次拉格朗日插值多项式L3(x).,设 为插值节点，n次多项式 满足条件 由此可得,称为lagrange插值基函数。引入记号 容易求得 于是，lk(x)可以写成,x0x1 xi xi+1 xn-1 xn,y=f(x),y=p(x),a,b,在插值区间a, b上用插值多项式

11、p(x)近似代替f(x), 除了在插值节点xi上没有误差外，在其它点上一般是存在误差的。,若记 R (x) = f(x) - p(x) , 则 R(x) 就是用 p(x) 近似代替 f(x) 时的截断误差, 或称插值余项. 我们可根据后面的定理来估计它的大小.,4 Lagrange插值多项式的截断误差,定理 设f(x)在a, b有n+1阶导数， x0, x1, xn 为 a, b上n+1个互异的节点, Ln(x)为满足 Ln(xi) = f(xi) (i=1,2, , n) 的n 次插值多项式，那么对于任何x a, b , (a,b), 有插值余项,其中,分析：,证,当t=x时，Rn（x）,当

12、t=x时，Rn（x）,由(1)、(2)知定理结论成立。 #,注意, 余项表达式仅当 存在时才能应用，且是唯一的。, 在( a , b ) 内的具体位置通常不能给出。, 若有 ,则截断误差限是, n次插值多项式对次数不高于n次的多项式完全精确。,若f(x)为次数不高于n次的多项式,从而Rn(x)=0.,则f(n+1)() =0, 线性插值：, n = 1, 2 时的插值余项 ：, 抛物线插值：,例 3 设f (x)=lnx,并以知f (x)的数据如表2-1。.,试用三次Lagrange插值 多项式 L3(x)来计算 ln(0.6)的近似值并估计 误差。,F(x)=lnx 函数图象,解 用 和 作

13、三次Lagrange插值多项式 L3(x) ，把x=0.6代入L3(x) 中，得 由于,利用余项估计式(2.1.11)可以得到 In(0.60)的真值为-0.510826，由此得出R3 (0.6)=-0.00085。这个例子说明，估计式(2.1.11)给出了一个较好的估计。,本课重点：,（1）插值多项式的存在唯一性 （2）拉格朗日插值多项式的构造(过程)以及误差估计（证明）。 （3）会利用线性和抛物线插值计算函数在某些点的近似值和误差。,拉格朗日插值采用插值基函数的线性组合来构造插值多项式,含义直观,形式对称,优点：,缺点：,计算量大,编程: 例题3,拉格朗日插值算法实现,2.1.3 均差和N

14、ewton插值多项式,Lagrange 插值虽然易算，但若要增加一个节点时，全部基函数 li(x) 都需要重新计算。,能否重新在Pn中寻找新的基函数 ？,希望每加一个节点时，只附加一项上去即可。,下面主要讨论, Newton插值多项式的构造 差商的定义及性质 差分的定义及性质 等距节点的Newton插值公式,由线性代数知,任何一个不高于n次的多项式, 都可以表示成函数,的线性组合, 也就是说, 可以把满足插值条件 p(xi)=yi (i=0,1,n)的n次插值多项式, 写成如下形式,其中ak (k=0,1,2,n)为待定系数,这种形式的插值多项式称为Newton插值多项式。我们把它记为Nn(x

15、)即,1. Newton插值多项式的构造,它满足 其中ak (k=0,1,2,n)为待定系数，形如上式的 插值多项式称为牛顿(Newton)插值多项式。,因此，每增加一个结点，Newton插值多项式只增加一项，克服了Lagrange插值的缺点。,自变量之差和因变量之差之比叫差商,2. 差商（均差的定义及性质）,即有定义：,定义 函数y= f(x)在区间xi ,xi+1上的平均变化率,称为f(x)关于xi , xi+1 的一阶差商,并记为fxi ,xi+1,m阶差商,二阶差商,f xi , xj , xk是指,fxi , xj , xk=,fxj , xk- fxi , xj ,xk- xi,一

16、般的,可定义区间xi, xi+1 , xi+n上的n阶差商为,差商的性质,差商表,计算顺序:即每次用前一列同行的差商与前一列上一行的差商再作差商。,例1 求 f(xi)= x3在节点 x=0, 2, 3, 5, 6上的各阶差商值 解: 计算得如下表,这个性质可用数学归纳法证明,性质1 函数 f(x) 的 n 阶差商 f x0, x1 , , xn 可由 函数值 f (x0), f (x1 ), , f (xn ) 的线性组 合表示, 且,fx0 , x1=,fx1 , x0,f(x1)- f(x0),x1 x0,性质2 差商具有对称性,即在k阶差商中 任意交换两个节点 和 的次序,其值不变。

17、例如,由差商定义及对称性，得,3 牛顿插值多项式的推导,将(b)式两边同乘以,(d)式两边同乘以,把所有式子相加,得,(c)式两边同乘以,记,- 牛顿插值多项式,- 牛顿插值余项,可得以下结论。,定理6,（牛顿插值多项式）,- 牛顿插值余项,已知 函数表,性质3 n阶差商 和n阶导数之间有下 列关系 这个性质可直接用罗尔（Rolle）定理证明,证明：余项,R(x) =f(x)- N(x),R(xi) =f(xi)- N(xi)=0 i=0,1, ,n,Rn(n)(x) =f (n)(x)- Nn(n)(x),=f (n)(x)- f(x0)+(x-x0) fx0, x1,+(x-x0)(x-x

18、1) fx0, x1 , x2,+(x-x0)(x-x1)(x-xn-1)fx0,x1,xn(n),=f (n)(x)- n! fx0,x1,xn,Rn(xi)=0 (i=0,1,n),Rn(i)=0 (i=0,1,n-1),Rn(n)()=0 (x0,x1,xn),Rn(n)()=0=f (n)()- n! fx0,x1,xn,即R(x)在x0,xn有n+1个零点，根据罗尔定理R(n)(x)在 x0,xn有1个零点，设为，即有 Rn(n)()=0,例3 设f(x)= ，并已知f(x)的数据如表2-3。,试用二次Newton插值 多项式 N2(x)计算f (2.15) 的近似值讨论其误差。,函

19、数f(x)= 的图象,利用Newton插值公式有 取x= 2.15得 注意到 可以得出,例4 已知函数f(x)的如下值:,求不超过3次的多项式P3(x)，使得满足插值条件：,其中，前三项是通过三个插值点的2次Newton插值N2(x),从而P3(x)满足三个函数的插值条件。是待定常数，由x1 =0处的导数值条件确定。,易知，其中的均差,例5 已知 f(x) = x7+ x4+ 3x+ 1 求 f 20, 21, 27 及 f 20, 21, 27, 28 分析：本题 f(x)是一个多项式, 故应利用差商的性质 解: 由差商与导数之间的关系,3 差分和等距节点插值公式,在实际计算中，经常遇到插值

20、节点等距分布的情形。引入差分作为工具，可使Newton插值公式得到简化。,并记,且,即,1、差分,记号, 向前差分算子；, 中心差分算子.,定义, 向后差分算子；,、向后、中心差分.,分别,（1） 差分及性质,二阶向前差分；,二阶向后差分；,利用一阶差分，可定义二阶差分为,一般地，可定义m 阶差分为, m 阶向前差分；, m阶向后差分；,若一阶中心差分,则二阶中心差分为,其中 为二项式展开系数。,（2） 对于 有,（2.1.23）,该式用数学归纳法证明。,下面利用差分构造等距节点插值公式。在Newton插值公式（2.1.15）中，用差分代替均差就可以得到等距节点插值公式。这里只推导常用的前插公

21、式和后插公式。,设 为已知，要计算x0附近点 处f(x)的近似值。插值节点应取 于是,此式可表示为,例 2.4 设x0=1.0,h=0.05,给出 在 处的函数值如表2-5的第3列，试用三次等距节点插值公式求f(1.01)和f(1.28)的近似值。,解 用Newton向前插值公式（2.1.25）来计算f(1.01)的近似值。先构造与均差表相似的差分表，见表2-5得上半部分。由t=(x-x0)/h=0.2的得,例 2.5 已知f(x)=sinx的数值如表2-6的第2列，分别用Newton向前、向后插值公式求sin0.57891的近似值。,解 作差分表如表2-6，使用Newton向前差分公式x0=

22、0.5,x1=0.6,x2=0.7,x=0.57891,h=0.1,则t=(x-x0)/h=0.7891,即sin0.578910.54714。误差为,若用Newton向后插值公式，则可取x0=0.4,x1=0.5,x2=0.6,x=0.57891, h=0.1,t=(x-x2)/h=-0.2109。于是,即sin0.578910.54707。误差为,2.1.4 Hermite插值多项式,这是一个次数不超过2n+1的多项式，有条件（2.1.30）知H2n+1(x)是满足插值条件（2.1.29）的Hermite 插值多项式。,仿照Lagrange 插值余项的证明方法，可得下面的余项定理 定理2.2 设 为a,b上相异节点， ,并且 f(2n+2)(x) 在(a,b)内存在，Hn+1(x)是满足插值条件（2.1.29）的插值多项式，则对任何xa,b,存在(a,b),使得,(2.1.34),相应的插值基函数为,例 2.6 设f(x)=lnx，给定f(1)=0, f(2)=0.693147, f(1)=1, f(2)=0.5。用三次Hermite插值多项式H3(x)计算f(1.5)的近似值。,解 记x0=1,x1=2, 利用(2.1.36)和(2.1.37)可得,