计算方法-插值a

1、第三章第三章 插值插值 /* Interpolation */当精确函数当精确函数 y = f(x) 非常复杂或未知时，在一非常复杂或未知时，在一系列节点系列节点 x0 xn 处测得函数值处测得函数值 y0 = f(x0), yn = f(xn)，由此构造一个简单易算的近似函，由此构造一个简单易算的近似函数数 g(x) f(x)，满足条件，满足条件g(xi) = f(xi) (i = 0, n)。这里的。这里的 g(x) 称为称为f(x) 的的插值函数插值函数。最常。最常用的插值函数是用的插值函数是 ?多项式多项式x0 x1x2x3x4xg(x) f(x)f(x)g(x) 已知函数已知函数y=

2、f(x)在区间在区间a, b内一系列点内一系列点xi上的函数值上的函数值f(xi)=yi, i=0,1,n，求一简单函数，求一简单函数P(x)，使满足条件，使满足条件P(xi)=yi, i=0,1,n， 称点称点xi为为插值节点插值节点/* interpolating points */ ，a, b为为插值区间插值区间/* interpolating region */ ，P(x)为为插值函数插值函数/* interpolatingfunction */ ，求，求P(x)的过程为的过程为函数插值函数插值/* function interpolating */ ，求，求P(x)的方法为的方法为插

3、值法插值法/* interpolation */ 。定义定义 由于代数多项式的结构简单，数值近似和理论分析都由于代数多项式的结构简单，数值近似和理论分析都方便，实用中常取代数多项式方便，实用中常取代数多项式作为插值函数，称其为作为插值函数，称其为n次插值多项式次插值多项式/* n-degree Interpolating polynomial */ ，求，求Pn(x)的过程也叫做的过程也叫做拉格朗日拉格朗日插值插值/* Lagrange Interpolation */ 。nnnxaxaxaaxP 2210)(点斜式点斜式3.1 拉格朗日插值拉格朗日插值 /* Lagrange Interpo

4、lation */niyxLiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxL10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1线性插值线性插值已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxL101)(使得使得111001)(,)(yxLyxL 可见可见 L1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)()(0010101xxxxyyyxL- - - - 101xxxx- - -010 xxxx- - -= y0 + y1l0(x)l1(x) 10)(iiiyxl称为称为拉

5、氏基函数拉氏基函数 /* Lagrange Basis */，满足条件满足条件 li(xj)= ij /* Kronecker Delta */n = 2抛物线插值抛物线插值已知已知 x0 , x1 , x2 ; y0 , y1 , y2 ，求，求L2(x)=a0+a1x + a2x2, 使使得得L2(xi)= yi , i=0,1,2.用基函数表示用基函数表示3.1 Lagrange Interpolation其中其中l0(x)、l1(x)、l2(x)为为二次式二次式，且满足以下条件，且满足以下条件2211002)()()()(yxlyxlyxlxL100010001 )(x, l)(x,

6、l)(xl)(x, l)(x, l)(xl)(x, l)(x, l)(xl221202211101201000li(xj)= ij)()(210 xxxxcxl- - - )(12010 xxxxc- - - )()()(2010210 xxxxxxxxxl- - - - - )()()( ,)()()(12021022101201xxxxxxxxxlxxxxxxxxxl- - - - - - - - - - yxxxxxxxxyxxxxxxxxyxxxxxxxxxL)()( )()()()()(120210121012002010212- The mathematician S. had t

7、o move to a new place. His wife didnt trust him very much, so when they stood down on the street with all their things, she asked him to watch their ten trunks, while she got a taxi. Some minutes later she returned. Said the husband: I thought you said there were ten trunks, but Ive only counted to

8、nine! The wife said: No, theyre TEN! But I have counted them: 0, 1, 2, . n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 niiinyxlxL0)()(，则显然有，则显然有Ln(xi) = yi 。li(x)每个每个 li 有有 n 个零点个零点 x0 xi xn - - - - - - njj i jiniiixxCxxxxxxCxl00)().().()( - - j i jiiiixxCxl)(11)( - - - njijjijixxxxxl0)()()(n

9、iiinyxlxL0)()(Lagrange Polynomial与与 有关，而与有关，而与 无关无关节点节点f3.1 Lagrange InterpolationQuiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 l2(x)的图像？的图像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 3.1 Lagrange Interpolation定理定理 (唯一性唯一性)

10、满足满足 的的 n 阶插值多阶插值多项式是唯一存在的。项式是唯一存在的。niyxLiin,., 0,)(证明：证明： 由插值条件可知，插值多项式由插值条件可知，插值多项式Ln(x)的系数的系数ai满足线性满足线性方程组方程组 nnnnnnnyyyaaaxxxxxx10101100111 nnnnnxxxxxxV1111100其系数行列式是其系数行列式是n+1阶阶范德蒙范德蒙(Vandermonde)行列式行列式 - - - - niijjixx010)(因为因为xixj，于是，于是V0，方程组的解存在且唯一，方程组的解存在且唯一 3.1 Lagrange Interpolation 插值余项插

11、值余项 /* Remainder */bxxxan 10 b a, )()!1()()()()(0)1(-nkknnnxxnfxLxfxR定理定理 设节点设节点 ，而，而f(x)在在a, b内有直到内有直到n+1阶导数，且已知阶导数，且已知f(xi)=yi, i=0, 1, , n, 则当则当xa,b成立成立Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广：推广：若若0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(

12、0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个根个根n+1 - - niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 - - - niixtxKtRnt0)()()()( (t)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(-nxKRxnn 注意这里是对注意这里是对 t 求导求导 - - - !)1)()()()1()1(nxKLfxnnxn !)1()()()1( nfxKxn - - niixnnxxnfxR0)1()(! ) 1()()( 3.

13、1 Lagrange Interpolation - - niixnnxxnfxR0) 1()(! ) 1()()( 注：注： 通常不能确定通常不能确定 , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf - - niinxxnM01|)!1(内插内插比比外推外推效果好。效果好。当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时，f(n+1)(x)=0 , 可知可知Rn(x)=0，即插值多项式对于次数，即插值多项式对于次数 n 的的多项式多项式是是精确精确的。的。3.1 Lagrange Interpolation例：

14、例：已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用216/4/6/214/6/4/)(1 - - - - - - xxxL),(,sin)(,sin)(46 - xxxfxxf而而| )( |)(!)()(,sin)(4642462221 - xxxxfxRfxxx0107701851.)( Rsin 50 = 0.7660444)1

15、85(50sin10 L0.77614外推外推 /* extrapolation */的实际误差的实际误差 - -0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 01851 R内插内插/* interpolation */ 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。3.1 Lagrange Interpolationn = 223)()(21)()(21)()()(4363463464363646342 -

16、- - - - - - - - - - - - - - xxxxxxxL)185(50sin20 L0.7654323cos; )3)(4)(6(!3cos)(2-xxxxxxR 0007701852.R sin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就越好，嘿嘿嘿3.1 Lagrange Interpolation 插值误差的实用估计法插值误差的实用估计法设设Ln(x) 和和Ln*(x)分别是以分别是以x0，x1,xn和和x1, x2,xn1为节

17、点的为节点的插值多项式。则插值多项式。则 )()!1()()()()()!1()()()(11)1(n0)1(-nkknnkknnxxnfxLxfxxnfxLxf 1nn xxxxx210Ln(x)L*n(x) 101n11xx)x(L)x(L)xx()xx()!n()(fnnn)n(- - - - - - )xx(xx)x(L)x(L)x(L)x(f)xx(xx)x(L)x(L)x(L)x(fnnnnnn101nn010n - - - - - - - - - - -Ln(x) 和和Ln*(x)只相只相差一个节点，可以差一个节点，可以设想设想f(n+1)() f(n+1) (*) 10111n

18、)xx)(xx()xx()!n()(f)x(L)x(Lnn)n(n- - - - - - 3.1 Lagrange Interpolation程序设计程序设计 f0,.,n ,i10 f output x, yx,input nii， - - - njijjijixxxxxl0)()()( niiinyxlxL0)()(1l,.,n ,j10 ?i j )xx/()xx(*lljij-iylff*)(3.1 Lagrange Interpolation When you start writing the program, you will find how easy it is to cal

19、culate the Lagrange polynomial.Oh yeah? What if I find the current interpolation not accurate enough? Then you might want to take more interpolating points into account.Right. Then all the Lagrange basis, li(x), will have to be re-calculated. Excellent point !We will come to discuss this problemnext

20、 time.3.1 Lagrange Interpolation3.1 Lagrange Interpolation81. 019. 32)1(19. 0)2(81. 02)2)(1()(2- - - - - - - - - - xxxxxxxxf因此，因此， f(x)f(x)的的零点零点为为x x1 1=-0.9, x=-0.9, x2 2=0.9;=0.9;04666. 1)(20 dxxf解解：由二次插值由二次插值例例(P.84 5.) 已知二次式已知二次式f(x)f(x)在在x=0,1,2x=0,1,2的值分别为的值分别为-0.81,0.19, -0.81,0.19, 3.19, 3.

21、19, 求求f(x)f(x)的零点、极值点、的零点、极值点、x=1x=1处导数和积分处导数和积分 20dxxf)(极值点极值点x=0;x=0;f f(1)=2 ;(1)=2 ;3.1 Lagrange Interpolation例例(P.84 6.) 设设x0,x1,xn是互不相同的节点，是互不相同的节点，li(x)是拉格朗日插值是拉格朗日插值基函数，求证：基函数，求证： 证明证明(1)：设：设f(x)=xk,k=0,1,2,n, 求求f(x)的次拉格朗日插值多的次拉格朗日插值多项式，得到项式，得到;,.,1 , 0 ,)( )1(0nkxxlxkniiki ;,.,1 , 0 , 0)( )

22、( )2(0nkxxxlkinii - - - - 1,)1(,.,2 , 1 , 00 , 1)0( )3(100nkxxxnkkxlnnkiniikniikiniiixxlxxlxfxf 00)()()()(3.1 Lagrange Interpolation例例(P.84 6.) 设设x0,x1,xn是互不相同的节点，是互不相同的节点，li(x)是拉格朗日插值是拉格朗日插值基函数，求证：基函数，求证： 证明证明(2)： - - - - - - nikjjkjiikiniixxjkxlxxxl000)()()( )( - - - - - - - - kjniijkjikjijkjinixlxxjkxlxxjk0000)()()()( - - - -kjniijijkxlxxjk00)()( - - - -kjjjkxxjk0)(0)( - -kxx