《计算机网络课件数值分析 chapter5》由会员分享，可在线阅读，更多相关《计算机网络课件数值分析 chapter5（30页珍藏版）》请在金锄头文库上搜索。
1、第5章插值方法第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值令n+1= (x x0)(x x1)(x xn).定义n + 1个Lagrange插值基函数：i = 0,1,2, ,n,li(x)=(x x0)(x xi1)(x xi+1)(x xn)(xi x0)(xi xi1)(xi xi+1)(xi xn)=n+1(x)(x xi)0n+1(xi).容易验证li(xk) =(0,k , i1,k = i(i,k = 0,1, ,n).第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值定义Lagrange多项式Ln(x) =nXi=0f(xi)li(x).于
2、是Ln(xk) = f(xk),k = 0,1,2, ,n.li(x)是n次多项式，因此Ln(x)是n多项式。由n次插值多项式的唯一性可得Lagrange插值多项式Ln(x)就是所求的插值多项式.第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值线性插值: n = 1的情况。两个基函数为l0(x) =x x1x0 x1,l1(x) =x x0x1 x0.Lagrange插值多项式为L1(x) = f(x0)l0(x) + f(x1)l1(x).第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值抛物线插值: n = 3的情况。三个基函数为l0(x) =(x x1)
3、(x x2)(x0 x1)(x0 x2),l1(x) =(x x0)(x x2)(x1 x0)(x1 x2),l2(x) =(x x0)(x x1)(x2 x0)(x2 x1),Lagrange插值多项式为L1(x) = f(x0)l0(x) + f(x1)l1(x) + f(x2)l2(x).第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值练练练习习习 给定数据表xi0123f(xi)01514求三次拉格朗日插值多项式L3(x).解：L3(x)=0 l0(x) + 1 l1(x) + 5 l2(x) + 14 l3(x)=0 + 1x(x 2)(x 3)1 (1) (2)+
4、 5x(x 1)(x 3)2 1 (1)+ 14x(x 1)(x 2)3 2 1=x(2x2+ 3x + 1)6=16x(x + 1)(2x + 1).第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值Lagrange插值的Matlab程序：function yi=Lagrange(x,y,xi)m=length(x); n=length(y); p=length(xi);if m=n error( x must have the same length as y); ends=0;for k=1:nt=ones(1,p);for j=1:nif j=kt=t.*(xi-x(j
5、)/(x(k)-x(j);endends=s+t*y(k);endyi=s;第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值定义Lagrange插值余项或截断误差项为Rn(x) = f(x) Ln(x).定定定理理理5.2 如果f(x)在a,b上有n阶连续导数，f(n+1)(x)在(a,b)内存在，x0,x1, ,xn是a,b 上的互异节点，则Rn(x) = f(x) Ln(x) =f(n+1)()(n + 1)!n+1(x),其中 = (x) (a,b).第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值证明 因为f(xi) = Ln(xi),i = 0,
6、,n,所以Rn(xi) = 0,i = 0, ,n,Rn(x) = K(x)(x x0)(x xn) = K(x)n+1(x).令(t) = f(t) Ln(t) K(x)(t x0)(t xn).于是(xi) = 0,i = 0, ,n,(x) = 0.(t)有n + 2个零点，由Roll定理可得，存在 = (x) (a,b), 使得(n+1)() = 0, 即(n+1)() = f(n+1)() K(x)(n + 1)! = 0.第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值定定定理理理5.3 如果f(n+1)(x)在(a,b)内有界，即存在常数Mn+1 0使得|f(n
7、+1)(x)| Mn+1,x (a,b),则|Rn(x)| Mn+1(n + 1)!|n+1(x)|.若f(n+1)(x)在a,b连续，可取Mn+1= maxxa,b|f(n+1)(x)|.第第第5章章章插插插值值值方方方法法法5.2 Lagrange插值推推推论论论 令M2= maxxa,b|f00(x)|, 则过点(x0,f(x0),(x1,f(x1)的线性插值余项为R1(x) =f00()2!(x x0)(x x1).由于在x0,x1上，|(x x0)(x x1)|在x =x0+ x12上达到最大值，于是|R1(x)| M28(x1 x0)2.Lagrange 插值的缺点: 增加一个节点
8、，所有的基函数都要重新计算.第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值假设Nn(x)是节点x0,x1, ,xn的n次插值多项式，Nn+1(x)是节点x0,x1, ,xn,xn+1的n + 1次插值多项式。令Qn+1(x) = Nn+1(x) Nn(x).如果Nn(x)已知，为求得Nn+1(x)我们希望求出Qn+1(x). 由Nn(xi) = Nn+1(xi) = f(xi),i = 0, ,n,可得Qn+1(x) = an+1(x x0)(x xn).同理Nn(x) = Nn1(x) + Qn(x),其中Qn(x) = an(x x0)(x xn1).第第第5章章章插
9、插插值值值方方方法法法5.3 差商与Newton插值于是，Nn(x) = a0+a1(xx0)+a2(xx0)(xx1)+an(xx0)(xxn1).而且Nn(x0)=a0= f(x0),Nn(x1)=a0+ a1(x1 x0) = f(x1),Nn(x2)=a0+ a1(x2 x0) + a2(x2 x0)(x2 x1) = f(x2),.Nn(xn)=a0+ a1(xn x0) + + an(xn x0)(xn xn1) = f(xn).第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值于是，a0=f(x0),a1=f(x1) f(x0)x1 x0,a2=1x2 x1 f
10、(x2) f(x0)x2 x0 a1!,a3=1x3 x2 f(x3) f(x0)x3 x0 a1!1x1 x0 a2!.第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值定义一阶差商fx0,x1 =f(x1) f(x0)x1 x0.定义k阶差商fx0, ,xk =fx1, ,xk fx0, ,xk1xk x0.第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值差商的基本性质:(1) 差商可以表示为函数值的线性组合，即fx0, ,xk =kXj=0f(xj)(xj x0)(xj xj1)(xj xj+1)(xj xn).(2) 差商与节点顺序无关，即fx0,
11、 ,xk = fxi0, ,xik,其中i0, ,ik是0,1, ,k的任意排列。第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值由归纳可得，a0=f(x0),a1=f(x1) f(x0)x1 x0= fx0,x1,a2=1x2 x1 f(x2) f(x0)x2 x0 a1!=1x2 x1(fx2,x0 fx1,x0) = fx2,x1,x0 = fx0,x1,x2,.an=fx0, ,xn.于是可得到Newton插值公式Nn(x) = f(x0)+fx0,x1(xx0)+fx0, ,xn(xx0)(xxn1).第第第5章章章插插插值值值方方方法法法5.3 差商与Newto
12、n插值由差商的定义可得f(x)=f(x0) + (x x0)fx,x0,fx,x0=fx0,x1 + (x x1)fx,x0,x1,fx,x0,x1=fx0,x1,x2 + (x x2)fx,x0,x1,x2,.fx,x0, ,xn1=fx0, ,xn + (x xn)fx,x0, ,xn.于是f(x)=f(x0) + (x x0)fx0,x1 + (x x0)(x x1)fx0,x1,x2+ + (x x0)(x x1)(x xn1)fx0,x1, ,xn+(x x0)(x x1)(x xn)fx,x0,x1, ,xn=Nn(x) + (x x0)(x x1)(x xn)fx,x0,x1,
13、,xn.第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值由插值多项式的唯一性和Lagrange插值多项式的余项表达式可得f(n+1)()(n + 1)!n+1(x) = fx,x0,x1, ,xnn+1(x).因此，fx,x0,x1, ,xn =f(n+1)()(n + 1)!.因此可得差商与导数的关系fx0,x1, ,xn =f(n)()n!.第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值差商表(xk,f(xk)一阶差商二阶差商三阶差商四阶差商(x0,f(x0)(x1,f(x1)fx0,x1(x2,f(x2)fx1,x2fx0,x1,x2(x3,f(
14、x3)fx2,x3fx1,x2,x3fx0,x1,x2,x3(x4,f(x4)fx3,x4fx2,x3,x4fx1,x2,x3,x4fx0,x1,x2,x3,x4第第第5章章章插插插值值值方方方法法法5.3 差商与Newton插值练练练习习习 给定数据表xi12345f(xi)14786求其差商表.解：k(xk,f(xk)一阶差商二阶差商三阶差商四阶差商0(1,1)1(2,4)32(3,7)303(4,8)111/34(5,6)23/21/61/24第第第5章章章插插插值值值方方方法法法5.4 Hermite插值Hermite插值要求在节点上函数值相等，并且节点上函数的导数值相等：已知f(xi
15、)和f0(xi), i = 0,1,2, ,n, 求一个次数不超过2n + 1的多项式H2n+1(x)满足H2n+1(xi) = f(xi),H02n+1(xi) = f0(xi),i = 0,1, ,n.第第第5章章章插插插值值值方方方法法法5.4 Hermite插值三次Hermite插值：已知y0= f(x0),y1= f(x1),y00= f0(x0),y01= f0(x1), 求一个三次的多项式H3(x)满足H3(x0) = y0,H03(x0) = y00,H3(x1) = y1,H03(x1) = y01.定义4个三次基函数0(x) = 1 + 2x x0x1 x0! x x1x0
16、 x1!2,0(x) = (x x0) x x1x0 x1!2,1(x) = 1 + 2x x1x0 x1! x x0x1 x0!2,1(x) = (x x1) x x0x1 x0!2.第第第5章章章插插插值值值方方方法法法5.4 Hermite插值可以验证这4个基函数满足i(xj) =(0,i , j,1,i = j,0i(xj) = 0,i,j = 0,1,0i(xj) =(0,i , j,1,i = j,i(xj) = 0,i,j = 0,1.因此，三次Hermite插值多项式为H3(x) = y00(x) + y11(x) + y000(x) + y011(x).可以证明余项为R3(x
17、) = f(x) H3(x) =f(4)()4!(x x0)2(x x1)2, (x0,x1).第第第5章章章插插插值值值方方方法法法5.5 分段低次插值高次插值的龙格(Runge)现象：插值节点越多，插值多项式次数越高，并不保证插值多项式跟被插值函数越来越近。分段线性插值：已知节点a = x0 x1 xn= b上的函数值yi= f(xi),i = 0,1,2, ,n, 求一分段插值函数P(x)使得(1) P(x) Ca,b;(2) P(xi) = yi, i = 0,1,2, ,n;(3) 在每个子区间xi,xi+1上，P(x)是线性函数。第第第5章章章插插插值值值方方方法法法5.5 分段低
18、次插值由定义可知，在每个子区间xi,xi+1上，P(x) =x xi+1xi xi+1yi+x xixi+1 xiyi+1,xi x xi+1.定义基函数: i = 1,2, ,n 1,l0(x) =(xx1x0x1,x0 x x1,0,x x0,x1,li(x) =xxi1xixi1,xi1 x xi,xxi+1xixi+1,xi x xi+1,0,x xi1,xi+1,ln(x) =(xxn1xnxn1,xn1 x xn,0,x xn1,xn,于是P(x) =nXi=0yili(x).第第第5章章章插插插值值值方方方法法法5.5 分段低次插值定义hi= xi+1 xi, h = max0i
19、n1hi. 可以证明maxaxb|f(x) P(x)| h28maxaxb|f00(x)|.于是，当f00(x)在a,b上连续时，P(x)一致收敛到f(x).分段线性插值的缺点：P(x)的导数不连续。第第第5章章章插插插值值值方方方法法法5.5 分段低次插值分段三次Hermite插值：已知节点a = x0 x1 xn= b上的函数值yi= f(xi)和导数值y0i= f0(xi), i = 0,1,2, ,n, 求一分段插值函数H3(x)使得(1) H3(x) C1a,b;(2) H3(xi) = yi, H03(xi) = y0i, i = 0,1,2, ,n;(3) 在每个子区间xi,xi
20、+1上，H3(x)是三次多项式函数。第第第5章章章插插插值值值方方方法法法5.5 分段低次插值定义基函数: i = 0,1,2, ,n,i(x) =?1 + 2xxixi1xi?xxi1xixi1?2,xi1 x xi,?1 + 2xxixi+1xi?xxi+1xixi+1?2,xi x xi+1,0,x xi1,xi+1,i(x) =(x xi)?xxi1xixi1?2,xi1 x xi,(x xi)?xxi+1xixi+1?2,xi x xi+1,0,x xi1,xi+1.注意，在0(x),0(x)的定义中要舍去第一部分，在n(x),n(x)的定义中要舍去第二部分。第第第5章章章插插插值值值方方方法法法5.5 分段低次插值于是H3(x) =nXi=0yii(x) + y0ii(x).定义hi= xi+1 xi, h = max0in1hi. 可以证明maxaxb|f(x) H3(x)| h4384maxaxb|f(4)(x)|.于是，当f(4)(x)在a,b上连续时，H3(x)一致收敛到f(x).第第第5章章章插插插值值值方方方法法法
