牛顿插值.pptx

牛顿插值牛顿插值(NewtonsInterpolation)Lagrange插插值多多项式具有式具有结构构紧凑、便于凑、便于编程程计算等特点，但在算等特点，但在计算算过程中若需要改程中若需要改变节点点或增加或增加节点点时，全部基函数全部基函数li(x)都需要重新都需要重新计算，算，这在在实际计算中很不方便，算中很不方便，为了克服了克服这一缺点，一缺点，介介绍一种灵活增加一种灵活增加节点的插点的插值多多项式。式。问题：问题：能否重新在能否重新在 P Pn 中寻找新的中寻找新的基函数基函数？使得每加一个节点时使得每加一个节点时,只附加一项只附加一项上去上去,而不而不必重新计算全部基函数必重新计算全部基函数!本本讲主要内容主要内容:Newton插值多项式的构造插值多项式的构造 差商的定义及性质差商的定义及性质 差分的定义及性质差分的定义及性质 等距节点等距节点Newton插值公式插值公式 1,x x0,(x x0)(x x1),(x x0)(x x1)(x xn1)是否构成是否构成P Pn的一组基函数的一组基函数？Newton插值多项式的构造插值多项式的构造构成构成!理由如下理由如下所以这组函数是所以这组函数是线性无关线性无关的的,1,x x0,(x x0)(x x1),(x x0)(x x1)(x xn1)是是P Pn 的一组基函数的一组基函数.利用插值条件利用插值条件 Nn(xi)f(xi),(i 0,1,n)代入上式代入上式,得到关于得到关于 Ak (k 0,1,n)的线性代数方程组的线性代数方程组.做牛顿插值函数做牛顿插值函数当当 xi互异时互异时,系数矩阵非奇异系数矩阵非奇异,且容易求解且容易求解定义定义设实数数x0,x1,xn 互异互异,差商差商(亦称均差亦称均差divideddifference)（1）f(x)在在xi,xj 处的处的1阶差商阶差商：（2）f(x)在在xi,xj,xk 处的处的2阶差商阶差商:为了给出牛顿插值函数一个简单的表示为了给出牛顿插值函数一个简单的表示,讨论讨论一般地一般地,k 阶差商阶差商定义为定义为特别特别,f(x)在在xi 处的处的零阶差商零阶差商f xi规定为规定为f(xi).差商的性质差商的性质性质性质1(差商可表为函数值的组合差商可表为函数值的组合)性质1的证明如下:单击看性质单击看性质1的证明的证明!一般情况用归纳法证之.性质1表明：差商具有差商具有对称性称性.即即,差商差商的的值与与结点排列点排列顺序无关序无关.性质性质2(对称性对称性)性质性质3(差商与导数的关系差商与导数的关系)对k=0,1,n,我们有所以所以牛顿插值多项式系数牛顿插值多项式系数牛顿插值多项式系数牛顿插值多项式系数:Ak=f x0,x1,xk.Nn(x)Rn(x)进一步进一步,得到牛顿插值多项式系数得到牛顿插值多项式系数Ak=f x0,x1,xk.得到表达式得到表达式其中其中余项余项(5.7)F牛牛顿插插值多多项式式Nn(x)与与Lagrange插插值多多项式式Ln(x)都是都是过给定定节点点x0,x1,xn 的的n 次多次多项式式.F过n 1个点的个点的n 次多次多项式是式是唯一性的唯一性的,可知可知Nn(x)Ln(x)，F从而从而,它它们的余的余项也相同，即也相同，即其中 n+1(x)=(x x0)(x x1)(x x2)(x xn)定理定理5.1牛顿牛顿插值多项式的余项为插值多项式的余项为:Rn(x)f x0,x1,xn,x n+1(x).由此得到由此得到得颜庆津教材的定义得颜庆津教材的定义:注解注解:二种差商定义的等价性二种差商定义的等价性 牛顿插值公式牛顿插值公式利用差商可简单地表为利用差商可简单地表为因因此此,每每增增加加一一个个结结点点,Newton插插值值多多项项式式只只增增加一项加一项,克服了克服了Lagrange插值的缺点。插值的缺点。xkf(xk)1阶差商阶差商2阶差商阶差商n阶差商阶差商x0f x0 x1f x1 f x0,x1x2f x2f x1,x2f x0,x1,x2x3f x3f x2,x3f x1,x2,x3f x0,x1,x2,x3xnf xnf xn-1,xnf xn-2,xn-1,xnf xn-3,xn-2,xn-1,xnf x0,x1,xn差商表差商表例例1给定f(x)=lnx 的数据表1.构造差商表2.分别写出二次、四次Newton插值多项式解解:差商表差商表xi2.202.402.602.803.00f(xi)0.788460.875470.955511.029621.09861N2(x)=0.78846+0.43505(x 2.20)0.087375(x 2.20)(x 2.40)N4(x)=0.78846+0.43505(x 2.20）0.087375(x 2.20)(x 2.40)+0.0225(x 2.20)(x 2.40)(x 2.60)0.00755(x 2.20)(x 2.40)(x 2.60)(x 2.80)记记 n+1(x)(x x0)(x x1)(x x2)(x xn)例例2已知当已知当xi=1,2,3,4,5时，对应的函数值为时，对应的函数值为f(xi)=1,4,7,8,6，求四次，求四次Newton插值多项式。插值多项式。解解:差商表差商表xif(xi)一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商四阶差商四阶差商112433730481-1-1/356-2-3/2-1/61/24N N4 4(x x)=1 1+3(3(x x 1)1)+0(0(x x 1)(1)(x x 2)2)1/3(1/3(x x 1)1)(x x 2)(2)(x x 3)3)+1/241/24(x x 1)(1)(x x 2)(2)(x x 3)(3)(x x 4)4)练习：已知已知f(0)=1，f(1)=2，f(2)=4，求求f(x)的二次插的二次插值多多项式并求式并求f(1.5).答案：答案：（1）f(x)在点在点xi处步长为处步长为h 的的1阶差分阶差分：（2）f(x)在点在点xi处步长为处步长为h 的的2阶差分阶差分：差分与等距节点插值公式差分与等距节点插值公式 差分及其性质差分及其性质当插值节点为等距节点当插值节点为等距节点xi=x0+ih(i=0,1,2,n)时，时，称称h 为步长，此时均差及为步长，此时均差及Newton插值多项式均可简化插值多项式均可简化.定义定义向前差分：向前差分：设设f(xi)=fi一般地一般地,k阶差分阶差分定义为定义为特别特别,0f i=fi 规定为规定为f(x)在在xi 处的处的零阶差分。零阶差分。以上定义的各阶差分也统称为以上定义的各阶差分也统称为向前差分向前差分，符号，符号叫做叫做向前差分算子。向前差分算子。（1）f(x)在点在点xi处步长为处步长为h的的1阶向后差分阶向后差分：（2）f(x)在点在点xi处步长为处步长为h的的2阶向后差分阶向后差分：向后差分：向后差分：设设f(xi)=fi一般地一般地,k阶向后差分阶向后差分定义为定义为向前差分与向后差分的关系：向前差分与向后差分的关系：向前差分表向前差分表 优点：不优点：不需作除法需作除法运算运算 差商与差分的关系差商与差分的关系向前差分向前差分一般地有一般地有向后差分向后差分 差商、差商、差分与导数的关系差分与导数的关系:等距节点插值公式等距节点插值公式将牛顿插值多项式中各阶均差用相应差分代将牛顿插值多项式中各阶均差用相应差分代替，就可得到各种形式的等距节点插值公式替，就可得到各种形式的等距节点插值公式.这里只介绍常用的这里只介绍常用的前插前插与与后插后插公式公式.注：注：如果有节点如果有节点xi=x0+ih(i=0,1,2,n)，要计算要计算 x0附近的点附近的点x 的函数的函数f(x)的值，可令的值，可令x=x0+th(0t1)，于是，于是称为称为Newton向前插值公式，向前插值公式，其余项其余项注：注：如果要用函数表示如果要用函数表示xn附近的函数值附近的函数值f(x)，此时，此时应用牛顿插值公式，插值点应按应用牛顿插值公式，插值点应按xn,xn-1,x1,x0的的次序排列，作变换次序排列，作变换x=xn+th(-1t0)，得，得称为称为Newton向后插值公式向后插值公式，其余项其余项 注：注：实际使用时给定的函数表常常是等距节点的实际使用时给定的函数表常常是等距节点的情形，这时只需考察函数值之差情形，这时只需考察函数值之差。于是均差变成。于是均差变成了差分，相应的了差分，相应的Newton插值变成插值变成Newton前插与前插与后插公式，当插值节点后插公式，当插值节点ax0,x1,xnb 由小到由小到大排列得到的是前插公式，反之，插值点由大到大排列得到的是前插公式，反之，插值点由大到小排列得到的是后插公式，而利用插值计算小排列得到的是后插公式，而利用插值计算f(x)的值时如果只用到函数表中的部分值。那么计算的值时如果只用到函数表中的部分值。那么计算x0附近点附近点x的函数值就用前插公式，而计算的函数值就用前插公式，而计算xn附近附近的函数值的函数值f(x)，就用后插公式。，就用后插公式。利用插利用插值函数函数pn(x)来近似来近似计算被算被插函数插函数f(x)在区在区间a,b上任意点的函上任意点的函数数值,理理论说明高次插明高次插值不可取。不可取。插插值函数的近似精度函数的近似精度Newton插值和插值和Lagrange插值虽然插值虽然构造比较简单，但都存在插值曲线在构造比较简单，但都存在插值曲线在节点处有尖点，不光滑，插值多项式节点处有尖点，不光滑，插值多项式在节点处不可导等缺点。在节点处不可导等缺点。n7的插值多项式一般不用。的插值多项式一般不用。分分段段低低次次插插值值所谓分段低次插值，即用所谓分段低次插值，即用分段多项式分段多项式来代替单个多来代替单个多项式作插值。具体说，就是在实际进行插值时，先把整项式作插值。具体说，就是在实际进行插值时，先把整个插值区间分成若干小区间，然后在每个小区间上分别个插值区间分成若干小区间，然后在每个小区间上分别用用低次插值多项式低次插值多项式进行插值。进行插值。分段分段线性插值线性插值就是通过插值点用就是通过插值点用折线折线段连接起来逼段连接起来逼近近f(x)。分段插值具有公式简单，节省运算量，稳定性好，分段插值具有公式简单，节省运算量，稳定性好，收敛性有保证等优点，只要每一个收敛性有保证等优点，只要每一个小区间小区间的长度取得足的长度取得足够小，分段低次插值总能满足所要求的精度。由于分段够小，分段低次插值总能满足所要求的精度。由于分段低次插值多项式对函数通常有较好的逼近性态，因而近低次插值多项式对函数通常有较好的逼近性态，因而近年来有着十分广泛的应用。年来有着十分广泛的应用。分分段段线线性性插插值值xjxj-1xj+1x0 xn计算量与计算量与n n无关无关;n n越大，误差越小越大，误差越小.xy 分段线性插值分段线性插值分段线性插值分段线性插值/*piecewise linear interpolation*/在每个区间在每个区间上，用上，用1阶多项式阶多项式(直线直线)逼近逼近f(x):记记，易证：当，易证：当时，时，一致一致失去了原函数的光滑性，不适用于失去了原函数的光滑性，不适用于光滑性要求高的外形设计光滑性要求高的外形设计.xyO O第一种（网格节点）：第一种（网格节点）：5.1.2二元函数插值二元函数插值第二种（散乱节点）：第二种（散乱节点）：yx0 0注意：注意：最邻近插值一般不连续。具有连续性的最简单的插值是分片线性插值。最最 邻邻 近近 插插 值值x y(x1,y1)(x1,y2)(x2,y1)(x2,y2)O O二维或高维情形的最邻近插值，与被插值点最邻近的节点的函数值即为所求。分分 片片 线线 性性 插插 值值 xy (xi,yj)(xi,yj+1)(xi+1,yj)(xi+1,yj+1)O O二元函数插值：二元函数插值：设实值函数函数f(x,y)定定义在矩形区域在矩形区域D=a x b,c y d,插插插插值节值节点集点集点集点集:Z=(xi,yj)|a x0 x1xn b,c y0 y1ym d.取在取在Z上上线性无关的函数性无关的函数组 kr x,y|k=0,1,n;r=0,1,m.其中，其中，kr x,y 是次数关于是次数关于x 不高于不高于n 次、次、关于关于y 不高于不高于m 次的次的二元二元多多项式。式。在函数空在函数空间D D Span 00,0m,n0,nm 上上寻找二元插找二元插值多多项式式使其使其满足插足插值条件条件此此问题就是二元函数的代数插就是二元函数的代数插值问题。如同一元的情况如同一元的情况,满足插足插值条件条件(5.11)的二元的二元插插值函数是函数是唯一唯一存在存在的。的。Lagrange插值曲面插值曲面取插值基函数取插值基函数其中其中这样的这样的 kr x,y 满足满足因此因此,kr x,y 在点集在点集(xi,yj)上线性无关上线性无关,且易且易知知,满足插值条件满足插值条件(5.11)的插值多项式为的插值多项式为式式(5.13)叫做叫做Lagrange形式的插值曲面形式的插值曲面.近似式近似式(x,y)pnm(x,y)(5.14)叫做二元函数的叫做二元函数的Lagrange插值公式插值公式.式式(5.14)的的余项余项或或截断误差截断误差为为Rnm(x,y)(x,y)pnm(x,y)证明证明：Rnm(x,y)(x,y)pnm(x,y)(5.16)证明证明：Rnm(x,y)(x,y)pnm(x,y)例例2试利用利用f(x,y)的函数表的函数表建立建立x为二次、二次、y为一次的二元插一次的二元插值多多项式式p21(x,y)，用以，用以计算算f(0.3,0.8)的近似的近似值。fx y-1010.50.250.5110.430.871.73解：解：由由n=2，m=1的二元插值多项式的二元插值多项式(5.13)可得可得数学符号x0,x1,xn,y0,y1,ym,0 x,1x,nx k=0,1,n (x,y)pnm(x,y)