计算方法 第1章插值ppt课件

1、数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS第1章 插 值 实际中，f(x)多样，复杂，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数g(x)来逼近f(x)。 自然地，希望g(x)通过所有的离散点l 概念x0 x1x2x3x4xg(x) f(x)数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS定义： 为定义在区间 上的函数， 为区间上n+1个互不 相同的点

2、， 为给定的某一函数类。求 上的函数 满足)(xfba, 0niix)(xgnixfxgii, 0 , )()(问题l是否存在唯一l如何构造l误差估计数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS0000( )( )( )()()()()nniiinnig xaxaxg xfxaxax设那么00011000001111110011()()()()()()()()()()()()nnnnnnnnnnaxaxaxf xaxaxaxf xaxaxaxf x所以 有解，当且仅当系数行列式不为00 n

3、iia数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS存在唯一定理定理1.1 ： 为n1个节点， n+1维空间，则插值函数存在唯一，当且仅当 0niix,10nspan0)()()()(0000nnnnxxxx数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS 与基函数取法无关 与原函数f(x)无关被插函数） 基函数个数与点个数相同特点：特点：数 学 系University of Science

4、 and Technology of ChinaDEPARTMENT OF MATHEMATICS, 1)(2nnxxxspanx对应于对应于那么那么01100nijjinnnxxxxVandermonde行列式数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS多项式插值的Lagrange型l 如何找？在基函数上下功夫，取基函数为nniixl 0)(要求jijixlijji, 1,0)(那么)()()(0iniixfxlxg数 学 系University of Science and Techn

5、ology of ChinaDEPARTMENT OF MATHEMATICS求niixl0)(，易知：)()()()(110niiiixxxxxxxxaxl)()()(1110niiiiiiixxxxxxxxa011011()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxx0()()nniixxx记()() ()()niniixlxxxx数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl线性插值01011010)( , )(xxxxxlxxxxxl)()(

6、)()()(11001xlxfxlxfxL数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl二次插值1200102()()( ) ()()xxxxlxxxxx2001122( )() ( )() ( )() ( )L xf x lxf x l xf x lx0211012()()( )()()xxxxl xxxxx0122021()()( )()()xxxxlxxxxx数 学 系University of Science and Technology of ChinaDEPARTMENT OF

7、 MATHEMATICS)3 , 3(),1 , 2(),0 , 0(),2 , 1(例：)31)(21)(01()3)(2)(0()(0 xxxxl)23)(03)(13()2)(0)(1()(3xxxxl)32)(02)(12()3)(0)(1()(2xxxxl)30)(20)(10()3)(2)(1()(1xxxxl)(3)(1)(0)(2)(3210 xlxlxlxlxg数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS算法：fx=0.0for(i=0;i=n;i+) tmp=1.0;

8、for(j=0;ji;j+) tmp=tmp*(x-xj)/(xi-xj); for(j=i+1;j=n;j+) tmp=tmp*(x-xj)/(xi-xj); fx=fx+tmp*yi;return fx;011011()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxx数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS误差)()()(xLxfxRnn解：)()()(, 0 , 0)(, 0 , )()(0nnininixxxxxkxRnixRnixLxf求?

9、)(xk0)( and , 0, 0)()()()()()(?)(,0anixxtxtaktLtftakainn设易知数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS)(t有n+2个零点)!1()()( )!1)()()( 0)( , )1()1()1()1(nfaknakfnnnn)()()!1()()(0)1(nnnxxxxnfxR由a的任意性数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATIC

10、S例：知例：知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL这里这里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)

11、()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 0.010013,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。数 学 系Universi

12、ty of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSn = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.00061高次插值通常优于高次插值通常优于低次插值低次插值数 学 系University of Science and Technology

13、 of ChinaDEPARTMENT OF MATHEMATICS事后误差估计给定 10niix任取n+1个构造)(xLn)( 1, 1)( , 0 xLnixLninn如：另取那么)()()!1()()()()()()!1()()()(112)1(01)1(nnnnnnxxxxnfxLxfxxxxnfxLxf数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS近似)()(2)1(1)1(nnff那么)()()()()()()()()()()( 10001010110 xLxLxxxxxLxfx

14、LxxxxxLxxxxxfxxxxxLxfxLxfnnnnnnnnnnnn数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl Lagrange 插值的缺点插值的缺点无承袭性。增加一个节点，所有的基函数都要重新计算数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS为实数Newton型多项式插值型多项式插值,110nxxx,10nxxx且1()()() , 0,niniiNxNxf xin)()()

15、(011nnnxxxxaxq同样)()()( 10nnnxxxxaxq)()()(1xqxNxNnnn承袭性：承袭性：)()()(11xqxNxNnnn1nP数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS)()()()( 10010nnnxxxxaxxaaxN而且有：)()()()()()()()()()()()()()(1001021202202102101101000nnnnnnnnnnnxfxxxxaxxaaxNxfxxxxaxxaaxNxfxxaaxNxfaxN数 学 系Univer

16、sity of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS这样：)(00 xfa 01011)()(xxxfxfa10202122)()(1axxxfxfxxa30312323031()()11f xf xaaaxxxxxx数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS01010010110,)()(,xxxxfxxfxxfxxxfxfxxfkkkk称为k阶差商称为1阶差商定义：差商数 学 系University of S

17、cience and Technology of ChinaDEPARTMENT OF MATHEMATICS差商的一个性质：差商的一个性质： （用归纳法易证）（用归纳法易证） 对称性：对称性：,00kiikxxfxxf定义关键：找不同的元素相减作分母的任意排列是kiik,0,0数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS)(00 xfa ,)()(1001011xxfxxxfxfa,1 )()(101201021210202122xxxfxxfxxfxxaxxxfxfxxa由归纳：,0n

18、nxxfa数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSNewton插值构造)(,00 xfx)(,11xfx)(,22xfx)(,nnxfx,10 xxf,12xxf,1nnxxf,012xxxf,21nnnxxxf,0 xxfn1、先构造差商表数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 例子2点Newton型插值)()()()()(0010101xxxxxfxfxfxN2、利用差

19、商表的最外一行，构造插值多项式)()(,)(,)()(1000100nnnxxxxxxfxxxxfxfxN数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS差商表求值算法：for(i=1;i=i;j-) yj=(yj-yj-1)/(xj-xj-i);fx=yn;for(i=n;i=1;i-) fx=yi-1+(x-xi-1)yi-1;数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS问题：如果要做

20、到增加一个点，而尽可能减少重复计算，要如何改进前面的算法？数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 一些性质niniiiiiiinnnnxxxxxxxxxfxxfxxLxN01100)()()()(, )()( 的系数一样性质2数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS误差00100100 Newton( ) ( )( ), ()() ( )( )( )( ), ()()nii

21、nniinnnnnnnnxNxxaNtN tf xx a txtxNaf af aN af xx a axax另一方面设插值为则有为显然(1)0(),(1)!nnffxxan性质3(1)0( ) ( ) ( )()()(1)!nnnnfNxR xxxxxn同样的误差为数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS差商性质总结niniiiiiiinxxxxxxxxxfxxf01100)()()()(,00niinxxfxxf( )0( ),( )!nnff xxnnknkaxxfxPxfnkn

22、, 0,),()(0推论：若数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS011, mm kkfmkf x xxx若 则 PP证明作为作业数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS有关上机作业l 提交计算机作业的ftp是00，l 可以直接在“我的电脑里输入ftp00登录，l 也可以用flashfxp等客户端软件登录，登录不需要输入用户名密码，

23、匿名登录即可。l ftp的权限只能提交作业，而不能下载或删除作业，l 如果他们发现自己提交的作业有问题，直接重新提交一份即可。数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS有关上机作业2l 为了避免病毒起见，ftp我设置只能提交.rar, .zip, .7z三种压缩包格式，其余的文档类型不能提交，所以他们每个人的作业必须打包压缩后才能提交。l 每个人作业的文件名最好包含姓名和学号。数 学 系University of Science and Technology of ChinaDEPART

24、MENT OF MATHEMATICS有关上机作业3l 我在ftp里设置了“第一次作业”、“第二次作业等目录，每次作业放在相应的文件夹内。l 最好让所有同学不论是否是否已通过邮件发送前两次作业，都往ftp提交作业，邮件每天太多，比较容易漏看，ftp则一目了然，比较清楚。数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS1.4 Hermite插值 有时候，构造插值函数除了函数值的条件以外，还需要一定的连续性条件，如一阶导数值等，这种插值称为Hermite插值。( )00 ,( ),( ,( ),1

25、,), Hermitenkniiiiiiixf xxfxkk 定义：满足和条件的插值称为插值niiiniiiixfxxfxk00)( ,)(, 1和满足一阶导数条件为例，即每个点上还要以所有称为二重密切Hermite插值数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS例：设例：设 x0 x1 x2, 知知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求求多项式多项式 P(x) 满足满足 P(xi) = f (xi)，i = 0, 1, 2，且，且 P(x1) = f (x1)

26、, 并估计误差。并估计误差。模拟模拟 Lagrange 多项式的思想，设多项式的思想，设解：首先，解：首先，P 的阶数的阶数 = 3213)()()()()(0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且，且 h0(x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh 又又: h0(x0) = 1 C0 )()()()()(202102210 xxxxxxxxxh h2(x)与与h0(x) 完全类似。完全类似。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1数 学 系University

27、 of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSh1(x)有根有根 x0, x2 )()()(201xxxxBAxxh 由余下条件由余下条件 h1(x1) = 1 和和 h1(x1) = 0 可解。可解。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx h1又又: (x1) = 1 C1 可解。可解。),()()()()()(221033xxxxxxxKxPxfxR !4)()()4(xfxK 与与 Lagrange 分析分析完全类似完全类似数 学 系University of Sci

28、ence and Technology of ChinaDEPARTMENT OF MATHEMATICS)()( ,)()( )()()()(12000012xPxgxhxfxgxfxhxHnniiniiniiiniiin问题变为求函数设，ijjijijiijjixgxgxhxh)( 0)( , 0)( )( 同样： 仿照Lagrange插值的做法，首先确定多项式插值空间的维数，注意到，我们的条件共有2(n+1)个条件，所以，最高次数为2n+1l 对二重密切Hermite插值数 学 系University of Science and Technology of ChinaDEPARTMEN

29、T OF MATHEMATICS10000100001000010000nnnnxxxxgghh数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl 整个构造步骤如下：1、确定多项式的最高项次数，就是函数空间的维数2、假设一组基函数，列出插值多项式3、列出基函数满足的公式画表），求基函数称为构造基函数方法数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS误差分析类似Lagrange插值的分析方法0

30、00000110110(1)(1)0(1)0( )( )( ) ,( )( )( )()()( )( )( )( )()()( )( )( )(1)!( )( )(1)!nnnnnnkknkknkknkknnkknnR xf xH xxxR xR xk x xxxxtf tH tk x txtxfk x kknfR xkkn 易知，为若干重根记0110)()nkknxxxx数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS二重密切Hermite插值误差(22)220( )( )()()(22)!

31、nnfR xxxxxn数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS例：在例：在5, 5上考察上考察 的的Ln(x)。取。取211)(xxf),., 0(105niinxi -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点附近抖动端点附近抖动越大越大Ln(x) f (x) 是否次数越高越好呢？数 学 系University of Science and Technology of ChinaDEPARTMENT OF M

32、ATHEMATICSLab02 Lagrange插值插值21( ), 5,51f xxx 对函数构造插值，并求55max( )( )max()() ,5,0,10010iiixiif xp xf yp yyi 插值节点取为：105,0,1,ixi iNN (1)215cos,0,1,22iixiNN (2)对N=5，10，20，40比较以上两组节点的结果。Chebyshev点点数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSHome WorkP40 4,6数 学 系University of

33、Science and Technology of ChinaDEPARTMENT OF MATHEMATICS分段低阶插值lRunge现象现象例： 1 , 1 2511)(2xxxf等距节点构造10次Lagrange插值多项式)(10 xLx)()(10 xLxf-0.900.047061.57872-0.700.07547-0.22620-0.500.137930.25376-0.300.307690.235351901年，Runge等距高次插值，数值稳定性差，本身是病态的。数 学 系University of Science and Technology of ChinaDEPARTME

34、NT OF MATHEMATICSl分段线性插值每个小区间上，作线性插值,),()()(11111iiiiiiiiiiixxxxfxxxxxfxxxxxs, )()(1iiinxxxxSxp(1),)(baCxpn(2)(xpn在每个小区间上为一个不高于1次的多项式特性特性数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSl误差,1iixxx2121)2(22M )(!2)()()(iiiinxxxxxxfxpxf22212822M)()(hMxxMaxxpxfiinn可以看出nxfxpn),(

35、)(数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS收敛，可惜只一阶精度，不够光滑。类似，可以作二重密切Hermite插值关键： 分段、低阶插值数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS三次样条插值 分段低阶插值，收敛性好，但光滑性不够理想。在工业设计中，对曲线光滑性要求高，如：流线型 设想这样一曲线：插值，次数不高于3次，整个曲线2阶连续导数，称为三次样条函数插值。数 学 系Unive

36、rsity of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS每个小区间不高于3次，,)(123iiiiiiixxxdxcxbxaxS1, 0ni有4n个未知数，我们的已知条件如下：(0)(0)(0)(0)(0)(0)( )( )iiiiiiiiS xS xS xS xSxSxS xf x1, 1nini, 0 1, 1ni1, 1ni共3n-3+n+1=4n-2个条件数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICSlm关系式

37、关系式需要附加2个条件，通常在边界处给出设,)(,)()()(),()(,)(11111iiiiiiiiiiiiiiiiixxxmxSmxSxfxSxfxSmxS则所以，是3次二重Hermite插值，记iiixxh1数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS213211321221121( )2()()( )1 2()()()1 ()()1 ()()iiiiiiiiiiiiiiiiiiiS xhxxxxf xhhxxxxf xhxxxxmhxxxxmh数 学 系University of Science and Technology of ChinaDEPARTMENT OF MATHEMATICS131312126 ( )2() ( )6 2() ()1 6()2 1 6()2 iiiiiiiiiiiiiiiiiSxhxxf xhhxxf xhxxh mhxxh mh由)( )( 1