1、第二章第二章 插值法插值法/* Interpolation */Interpolation_introduction1 引引 言言1.1.函数表达式过于复杂不便于计算函数表达式过于复杂不便于计算, , 而又需要计算许而又需要计算许多点处的函数值多点处的函数值2.2.仅有几个采样点处的函数值仅有几个采样点处的函数值, , 而又需要知道非采样而又需要知道非采样点处的函数值点处的函数值 v上述问题的一种上述问题的一种解决思路：解决思路：建立复杂函数或者未建立复杂函数或者未知函数的一个便于计算的近似表达式知函数的一个便于计算的近似表达式. .v解决方法解决方法插值法插值法 1. 1. 插值概念插值概念
2、求插值函数求插值函数 ( (x) )的问题的问题( (方法方法) )称为称为插值问题插值问题( (方法方法) )。2. 2. 几何意义、内插法、外插法几何意义、内插法、外插法内插外插niixM0maxniixm0min,Mmx,Mmxbutbax2 拉格朗日多项式拉格朗日多项式 /* Lagrange Polynomial */niyxPiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：无重合节点，即条件：无重合节点，即jixx ji l0(x)l1(x)2 Lagrange Polynomial多项式插值是数值分析的基本工具，常用来计算被插函数多
3、项式插值是数值分析的基本工具，常用来计算被插函数的近似的近似函数值函数值，零、极点零、极点，导数、积分导数、积分（第四章（第四章 数值积数值积分和数值微分），分和数值微分），解微分方程解微分方程（第五章）、（第五章）、积分方程积分方程x0 x1x2x3x4xPn(x) f(x)解 几何上看，即求几何上看，即求多项式曲线多项式曲线与与被插值函数曲线被插值函数曲线间满足：间满足：特点：插值曲线插值曲线Pn(x)过被插值曲线过被插值曲线f (x)的上给定的的上给定的n+1个点。个点。n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(y
4、xPyxP 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)()(0010101xxxxyyyxP- - - - 101xxxx- - -010 xxxx- - -= y0 + y1l0(x)l1(x) 10)(iiiyxl称为拉氏基函数称为拉氏基函数 满足条件满足条件 li(xj)= ij 2 Lagrange Polynomial 提问：上面所提的多项式提问：上面所提的多项式Pn(x)是否存在？是否存在？ 若存在，是否唯一？如何求？若存在，是否唯一？如何求？证明证明 插值条件插值条件(2.2)(2.2)等价于线性方程组等价于线性
5、方程组200021112111nnnnnnxxxxxxxxx定理定理1 1 满足插值条件满足插值条件(2.2)(2.2)的不超过的不超过n次的插值次的插值多项式多项式唯一存在。唯一存在。0()0jiij nxx -系数行列式（系数行列式（n+1+1阶范德蒙行列式）阶范德蒙行列式）由克莱默法则知，方程组有唯一解由克莱默法则知，方程组有唯一解20102000201121112012nnnnnnnnnnaa xa xa xyaa xa xa xyaa xa xa xy 01,.na aa2-1 插值多项式的存在唯一性插值多项式的存在唯一性 唯一性的另一证明唯一性的另一证明 满足满足 的的 n 阶插阶
6、插值多项式是唯一存在的。值多项式是唯一存在的。niyxPii,., 0,)( 证明证明 ( 前面已利用前面已利用Vandermonde 行列式论证行列式论证)反证：若不唯一，则除了反证：若不唯一，则除了Ln(x) 外还有另一外还有另一 n 阶多项阶多项式式 Pn(x) 满足满足 Pn(xi) = yi 。考察考察 则则 Qn 的阶数的阶数, )()()(xLxPxQnnn- - n而而 Qn 有有 个不同的根个不同的根n + 1x0 xn注：若不将多项式次数限制为注：若不将多项式次数限制为 n ，则插值多项式不唯一。，则插值多项式不唯一。例如例如 也是一个插值也是一个插值多项式，其中多项式，其
7、中 可以是任意多项式。可以是任意多项式。 - - niinxxxpxLxP0)()()()()(xp2 Lagrange PolynomialInterpolation polynomial 2-2 线性插值与抛物插值线性插值与抛物插值 x0 x1(x0 ,y0)(x1 ,y1)P1(x)f (x) 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的直线。两点的直线。)(001010 xxxxyyyy-直线方程为直线方程为:等价变形为等价变形为:10100101yxxxxyxxxxy-记为记为:)(1xL1. 线性插值线性插值引入记号引入记号:,)(10
8、10 xxxxxl-0101)(xxxxxl-则则:11001)()()(yxlyxlxL分析两个基函数有分析两个基函数有:0)(1)(1000 xlxl1011()0( )1l xl x对于三个点对于三个点,类似有类似有:2211002)()()()(yxlyxlyxlxL称为插值基函数称为插值基函数0)(0)(1)(201000 xlxlxl0)(1)(0)(211101xlxlxl1)(0)(0)(221202xlxlxlx0 x1x2P2(x) f(x)f(x)2. 抛物线抛物线(二次二次)插值插值 将以上思路推广到将以上思路推广到n+1个节点情形，即可得到类似的个节点情形，即可得到类
9、似的插值基函数和插值多项式表示形式。插值基函数和插值多项式表示形式。P2(x)xn 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li 有有 n 个根个根 x0 xi xn jiC0 - -nj i jxx)(- - - -inxxixxxxC0).().(ixl)( - - j i jxixiC)(1 iixl1)( - - - njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange Polynomial与节点有关，而与与节点有关，而与
10、f无关无关 niinxlxP0)()(yi 基函数法（基函数法（n=1情形的推广情形的推广）2 Lagrange Polynomial2-3 Lagrange插值多项式插值多项式 2-4 插值余项插值余项 /* Remainder */设节点设节点)1( nf在在a , b内存在内存在, 考察截断误差考察截断误差)()()(xLxfxRnn- - , baCfn bxxxan 10，且，且 f 满足条件满足条件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，则，则存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推广：推广：若若0)()()(210
11、 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 个根个根n+1 - - niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 - - - niixtxKtRnt0)()()()( (x)有有 n+2 个不同的根个不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(-nxKRxnn 注意这里是对注意这里是对 t 求导求导 - - - !)1)()()()1()1(nxKLfxnnxn
12、!)1()()()1( nfxKxn - - niixnnxxnfxR0)1()(! ) 1()()( 2 Lagrange Polynomial1 Lagrange Polynomial注：注： 通常不能确定通常不能确定 x , 而是估计而是估计 , x (a,b) 将将 作为误差估计上限。作为误差估计上限。1)1()( nnMxf - - niinxxnM01|)!1(当当 f(x) 为任一个次数为任一个次数 n 的的多项式多项式时，时， , 可知可知 ，即插值多项式对于次数，即插值多项式对于次数 n 的的多项多项式是式是精确精确的。的。0)()1( xfn0)( xRnQuiz: 给定给
13、定 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 1 Lagrange Polynomial例：例：已知已知233sin,214sin,216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500
14、 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)()(,23sin21)2(1 - - - xxfxRxx00762. 0)185(01319. 01- - - - Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的实际误差的实际误差 - -0.010010.010013,421 xx利用利用sin
15、50 0.76008, 00660. 018500538. 01 R内插内插 /* interpolation */ 的实际误差的实际误差 0.005960.00596内插通常优于外推。选择内插通常优于外推。选择要计算的要计算的 x 所在的区间的所在的区间的端点，插值效果较好。端点，插值效果较好。1 Lagrange Polynomialn = 223)()(21)()(21)()()(4363463464363646342 - - - - - - - - - - - - - - - xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2
16、- - - - - xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的实际误差次插值的实际误差 0.000610.00061高次插值通常优于高次插值通常优于低次插值低次插值但绝对不是次数越但绝对不是次数越高就越好，嘿高就越好，嘿嘿嘿 When you start writing the program, you will find how easy it is to calculate the Lagrange polynomial.Oh yeah? What if I find the current interpolation not
17、 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 time.1 Lagrange Polynomial练习：练习： 设设f(x)=x4,利用利用 Lagrange 插值写出以插值写出以-1,0,1,2为节点为节点 的
18、插值多项式。的插值多项式。 练习：练习：已知插值节点满足已知插值节点满足xi-xi-1=h,i=1,2,3, 证明三次插值证明三次插值多项式多项式L3(x)与被插函数与被插函数f(x)的差有如下关系：的差有如下关系：03034431max |( )( )|max |( )|24xx xxx xf xL xhfx -1 Lagrange Polynomial练习：练习：证明证明0010(1)( ),0,1,2,(2)()( )0,0,1,2,(3) ( )n+1( )() ( )()nkkiiinkiiinniiiiix l xxknxxl xknp xp xp x l xxx-是任一最高次项系
19、数为1的次多项式，则Interpolation_introduction问题的提出：问题的提出： 如果需要增加精度，一般采用增加插值节点来实如果需要增加精度，一般采用增加插值节点来实现。但是由于插值基函数的性质，使得计算新的插值现。但是由于插值基函数的性质，使得计算新的插值多项式时，原来的计算量不能很好地利用，造成计算多项式时，原来的计算量不能很好地利用，造成计算的浪费，为了克服这一缺点，我们将要介绍下面的逐的浪费，为了克服这一缺点，我们将要介绍下面的逐步线性插值和步线性插值和Newton插值。插值。3 逐次线性插值逐次线性插值 /* Lagrange Polynomial */3 逐次线性插
20、值法逐次线性插值法 /* Lagrange Polynomial */ 0,1010011100,100100,202200,200200,20,10,1 20,1121:1Lagrange,;:1LagrangeIxx xxf xx f xf xf xIxf xxxxxIxx xf xf xIxf xxxxxIxIxIxIxxxxx-，以 ，为节点的 次插值公式，实际上是过，点的直线，采用点斜式以 ，为节点的 次插值公式,同理有仿上，令易证 0,200,100,1 200,10010,100210,210,110,1 210,11110,111210,220,120,1 220,12210,
21、222210,1 20122IxIxIxIxxxIxf xxxIxIxIxIxxxIxf xxxIxIxIxIxxxIxf xxxIxx x x-，由插值公式的唯一性知，是以 ，, 为节点的 次Lagrange插值多项式。以此 0,12,0,110,10,111101kkkkkkkkkIxIxIxIxxxxxx xxk-，类推，是以 ，, , 为节点的 次Lagrange插值多项式。 10,10,110,12,11kkkkkkkkkkx xx xIxIxIxxxxx-，实际上实际上，是对两个低次插值的线性插值，这种通过低次插值再作是对两个低次插值的线性插值，这种通过低次插值再作线性插值生成高次
22、插值的方法称为线性插值生成高次插值的方法称为逐次线性插值逐次线性插值。 Aitken法法(按下表计算按下表计算) 0,12,0,110,10,1111kkkkkkkkIxIxIxIxxxxx-，线性插值基函数线性插值基函数 0,0,1,0,1,2,0,1,2,3,00110,10220,20,1,2 kkkkkkxf xIxIxIxIxxf xxf xIxx xxf xIxIx- 1330,30,1,30,1,2,32440,40,1,40,1,2,40,1,2,3,43 x xxf xIxIxIxx xxf xIxIxIxIxx x-0123 x xx xx xx x-增加增加如果精度不够，
23、增加节点如果精度不够，增加节点x4, ,同时表中增加一行，三同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。角形斜边上即为所要求的各次插值多项式。k1k0k2k3k4 Neville法法(按下表计算按下表计算) 1,1, ,11, ,11, ,1,200110,10221,20,1,2 kkkkkk kkk kkk kkxf xIxIxIxIxxf xxf xIxx xxf xIxIx- 0332,31,2,30,1,2,30443,42,3,40,1,2,40,1 x xxf xIxIxIxx xxf xIxIxIxI- ,2,3,401111 kkkkxx xx xx xx xx
24、 x-增加增加如果精度不够，增加节点如果精度不够，增加节点x4, ,同时表中增加一行，三角形斜边上同时表中增加一行，三角形斜边上即为所要求的各次插值多项式。即为所要求的各次插值多项式。k1k0k1k1k1 11,0,110,10,1100kkkkkkIxIxIxIxxxxx-，HW: 用类似于前面的方法用类似于前面的方法构造构造Neville计算公式计算公式注：注：Atkin方法和方法和Neville方法与方法与Lagrange公式相比，当公式相比，当需要增加节点时，很容易由低次插值构造高次插值，而需要增加节点时，很容易由低次插值构造高次插值，而Lagrange插值公式中，每个基函数都需要作适
25、当变化。插值公式中，每个基函数都需要作适当变化。误差估计：误差估计：由插值多项式的存在唯一性知，仍有由插值多项式的存在唯一性知，仍有 - - niixnnxxnfxR0)1()(! ) 1()()( 但这里可采用一种更简便的方法。当但这里可采用一种更简便的方法。当f (n+1)(x)在插在插值区间变化不大时，设值区间变化不大时，设f (n+1)(x)L，则有则有 0,110-10,12,0-2-!-!kkkkkkLf xIxx xx xkLf xIxx xx xx xk-， 10,110,12,0,1110,12,0,11 if kkkkkkkkkkxxf xIxIxIxxxIxIx-， 0,
26、11-10,12,-kkkkkf xIxx xf xIxx x-，根据前面的计算结果估计当根据前面的计算结果估计当前的误差：事后误差估计前的误差：事后误差估计（实用），前面给出的误差（实用），前面给出的误差估计（事先误差估计）不实估计（事先误差估计）不实用用4 牛顿插值牛顿插值 /* Newtons Interpolation */Lagrange 插值虽然易算，但若要增加一个节点时，插值虽然易算，但若要增加一个节点时，全部基函数全部基函数 li(x) 都需重新算过。公式不具有继承性，都需重新算过。公式不具有继承性，不利于编程。不利于编程。将将 Ln(x) 改写成改写成.)()(102010
27、- - - - - xxxxaxxaa).(10- - - - nnxxxxa的形式，希望加一个节点时，的形式，希望加一个节点时，只附加一项只附加一项上去即可。上去即可。? 差商差商( (亦称均差亦称均差) ) /* divided difference */),()()(,jijijijixxjixxxfxfxxf - - - 1阶差商阶差商 /* the 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji - - - 2阶差商阶差商f(x0)1010()()f xf xxx-2010201021
28、()()()()f xf xf xf xxxxxxx-1阶差商的几何阶差商的几何意义：弦截线意义：弦截线的斜率的斜率4 Newtons Interpolation4 Newtons Interpolation11101010111010,.,.,.,.,., - - - - - - - - - kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)阶差商阶差商： kiikikxxfxxf010)()(,., 事实上事实上其中其中,)()(01 - - kiikxxx - - kijjjiikxxx01)()( Warning: my head is explodingW
29、hat is the point of this formula?差商的值与差商的值与 xi 的顺序无关！的顺序无关！1.1.线性线性：1201020( )( )( ) , , ,kkkf xaf xbf xf xxaf xxbf xx2.2.差商差商可以表示为可以表示为函数值的线性组合函数值的线性组合：0000-111( )( ),.,( )kkiikiiiiiiiikkif xf xf xxxxxxxxxxx-,)()(01 - - kiikxxx - - kijjjiikxxx01)()( 3.3. 对称性：对称性：由由2 2知知，差商的值与节点的顺序无关！差商的值与节点的顺序无关！4.
30、4. 差商的另一种定义：由差商的另一种定义：由2，3及均差定义可得及均差定义可得10100 ,.,.,.,kkkkf xxf xxf xxxx-4 Newtons Interpolation4 Newtons Interpolation 牛顿插值牛顿插值 /* Newtons Interpolation */,)()()(000 xxfxxxfxf- - ,)(,101100 xxxfxxxxfxxf- - ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf- - - -).(.)()()(10102010- - - - - - - - - nnnxxxxaxxxxaxxaaxN
31、.)(,)(,)()(102100100 - - - - - xxxxxxxfxxxxfxfxf).(,.,100- - - - nnxxxxxxf)().(,.,100nnnxxxxxxxxxf- - - - - -Nn(x)n次多次多项式，满足：项式，满足： Nn(xi)= f(xi)Rn(x)插值余项，插值余项，满足满足Rn(xi)=0，i=0,n ai = f x0, , xi (1)(2)(n)(n)(n-1) (2) (1)4 Newtons Interpolation注：注： 由由唯一性可知唯一性可知 Nn(x) Ln(x)， 只是算法不同，表达只是算法不同，表达形式不同，故其余
32、项也相同，即形式不同，故其余项也相同，即(1)011() ,.,( )( )(1)!nxnnnff x xxxxn),(,!)(,.,maxmin)(0 xxkfxxfkk 实际计算过程为实际计算过程为f (x0)f (x1)f (x2)f (xn- -1)f (xn)f x0, x1f x1, x2 f xn- -1, xnf x0, x1 , x2 f xn- -2, xn- -1, xnf x0, , xn f (xn+1) f xn, xn+1 f xn- -1, xn, xn+1 f x1, , xn+1 f x0, , xn+1增加增加如果精度不够，增加节点如果精度不够，增加节点x
33、n+1, ,同时表中增加一行，三角形斜边同时表中增加一行，三角形斜边上即为所要求的各次项系数。上即为所要求的各次项系数。1 Lagrange Polynomial练习：练习： 设设f(x)=3x2+5 ,求求fx0,x1,x2 , fx0,x1,x2, x3练习：练习：74017018( )31,2 ,2 ,2 2 ,2 ,2 f xxxxff求及练习：练习：001 , ,1kkf x xxxmf x xxm-设是 的 次多项式，证明是次多项式4 Newtons Interpolation 等距节点公式等距节点公式 /* Formulae with Equal Spacing */向前差分向前
34、差分 /* forward difference */iiifff- - 1ikikikikffff1111)(- - - - - - - 向后差分向后差分 /* backward difference */111- - - - - - ikikikfffi- -1iifff- - 中心差分中心差分 /* centered difference */212111- - - - - - ikikikfff 其中其中)(221hiixff 当节点当节点等距等距分布时分布时:),.,0(0nihixxi fi= f(xi) 差分计算可通过构造差分表得到差分计算可通过构造差分表得到 234234500
35、00000234111111232222233 = kkkkkkkx f xfffffxffffffxfffffxffffxf23344455 ffxffxf增加增加 23450011122222333 = kkkkkkkkxf xffffffxfxffxfffxff233323444444423455555555 ffxfffffxffffff1112211112211122identity calculus translation calculus: -, kkkkkkkkkkIffEffE ffE ffEffE II EEE-：， 差分的重要性质：差分的重要性质： 线性：例如线性：例如g
36、bfaxgbxfa )()( 各阶差分可用函数值表示：各阶差分可用函数值表示：!)1).(1(jjnnnjn - - - 其中其中/* binomial coefficients */4 Newtons Interpolation0011nnnjjnnjkkkn kjjjnnfEIfEffjj- -1()0011nnnnjnjnnjkkkkj njjnnfIEfEffjj- - 函数值可用各阶差分表示：函数值可用各阶差分表示：0e.g. Ennnjn kkkkjnffIffj 差商与差分的关系差商与差分的关系：111121211222211-1,-,-,1,-22, 1,!11,!kkkkkk
37、kkkkkkkkkkkkkkkmkkkmkmmmkkkmkmkmmffff xxfxxxhf xxf xxfff xxxfxxhhgenerally we havef xxxfm hf xxxffm hm h- 若若 f (x)是是 n 次多项式，则次多项式，则 是是 次多次多项式，而项式，而 ( ) (0)mf xmnnm-( )0 ()mf xmn 差分与导数的关系差分与导数的关系( (由差分与差商、差商与导数的关系得由差分与差商、差商与导数的关系得）：）： ()1()1,!mmkkkmkmmmkmff xxxfmm hffh4 Newtons Interpolation等距节点牛顿公式等
38、距节点牛顿公式 牛顿前差公式牛顿前差公式 /* Newtons forward-difference formula */001100010010-12000001( )( )( ),01, , ,( )( -)1( )(),( -),( -)( -)1111( -1)2!( ),nnjjnnnjjnnnnnf xNxRxxxthtxxjhxxtj hxx xht ttnNxf xf xxx xf xxxx xx xfftft tft ttnnRxf x xxx- -01(1)( -)( -)1( )(1)!nnnnx xx xt ttnhfn-注：注：一般当一般当 x 靠近靠近 x0 时用前
39、插，靠近时用前插，靠近 xn 时用后插，故两时用后插，故两种公式亦称为种公式亦称为表初公式表初公式和和表末公式表末公式。 牛顿后差公式牛顿后差公式 /* Newtons forward-difference formula */nn110nnn 1nnn 10n12nnnnnnn 10, 10, , , ( )( -)1( )(),( -),( -)( -)1111( -1)2!( ),( -jjnnnjjnnxxthtxxjhxxtj hxx xht ttnNxf xf x xx xf x xxx xx xfftft tft ttnnR xf x x xxx x- - 节点倒排，n01(1)
40、( -)1( )(1)!nnx xt ttnhfn例：例：442 ,nnnnyyy若求及6 埃尔米特插值埃尔米特插值 /* Hermite Interpolation */不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f (xi), (mi) (xi) = f (mi) (xi).注：注： n+1 个条件可以确定指数不超过个条件可以确定指数不超过n次的多项式。次的多项式。要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插
41、值多项式即为值多项式即为Taylor多项式多项式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx- - - - 其余其余项为项为)1(00)1(00)()!1()()()()(-mmxxmfxxfxR 一般只考虑一般只考虑 f 与与f 的值。的值。埃尔米特插值埃尔米特插值3 Hermite Interpolation例：例：设设 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), 并估计误差。并估计误差
42、。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶数的阶数 = 3213)()()()()(0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh- - - 又又: h0(x0) = 1 C0 )()()()()(202102210 xxxxxxxxxh- - - - - h2(x)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh- - - 由余下条件由余下条件 h1(x1) = 1 和和 h1(x1) = 0 可解。可解。与与h0(
43、x) 完全类似。完全类似。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx- - - - h1又又: (x1) = 1 C1 可解。可解。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1),()()()()()(221033xxxxxxxKxPxfxR- - - - - - !4)()()4(xfxK 与与 Lagrange 分析完全类分析完全类似似3 Hermite Interpolation一般地，已知一般地，已知 x0 , , xn 处有处有 y0 , , yn 和和 y0 , , yn
44、，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：解：设设ni)()()(0iix x yixH2n+1n0iyi其中其中 i (xj) = ij , i (xj) = 0, (xj) = 0, (xj) = ij i i(x)有根有根 x0 , , xi , , xn且都是且都是2重根重根 - - - ijjijixxxxxl)()()(由余下条件由余下条件 i (xi) = 1 和和 i (xi) = 0 可解可解Ai 和和 Bi 2( )12 ()()( )iiiiixlxxxlx - - - (x) i 有根有根 x0 , , x
45、n, 除了除了xi 外都是外都是2重根重根 i)()(iili2(x)xxCx- - 又又 i (xi) = 1 Ci = 1 i)(x)(ili2(x)xx- - 这样的这样的Hermite 插值唯插值唯一一 i )()()(2xlBxAxiii i011011()()()()( ),0,1,2, .()()()()iiniiiiiiinxxxxxxxxl xinxxxxxxxx-n+1次次 2210( )12 ()()()( ).nniiiiiiiiHxl xxxyxxylx - - - - - 所以所以01()niijijj ilxxx - - 类似有：类似有：, 则则,.210baCf
46、bxxxann 2(22)210()( )().(22)!nnxniifRxxxn - 证明略证明略.3 Hermite InterpolationQuiz: 给定给定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪个是下面哪个是 i(x)的图像？的图像？x0-10.5123456yxy0-10.5123456斜率斜率=1 求求Hermite多项式的基本步骤：多项式的基本步骤： 写出相应于条件的写出相应于条件的 i(x)、 i(x) 的组合形式；的组合形式； 对每一个对每一个 i(x)、 i(x)找出尽可能多的条件给出的根；找出尽可能多的条件给出的根； 根据多项式的总
47、阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式； 根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数； 最后完整写出最后完整写出H2n+1(x)。注：待定系数法仍适用，但插值节点多注：待定系数法仍适用，但插值节点多时比较麻烦。时比较麻烦。1 1分析分析（方法（方法1 1）：）：)(,)(,)()(1021001002xxxxxxxfxxxxfxfxN-)()()()(21023xxxxxxkxNxH-kxfxH )()(003求得参数令)()(! 4)()()(2120)4(3xxxxxxfxHxf-误差：误差：#例例 2 2: :建立插值多项
48、式建立插值多项式)(3xH, ,使之满足插值条件使之满足插值条件 )()(2 , 1 , 0)()(0033xfxHixfxHii. 方法方法2 2：（用带有重节点的差商表：（用带有重节点的差商表）2100 xxxx)()()()(2100 xfxfxfxf,211000 xxfxxfxxf)(0 xf ,210100 xxxfxxxf,2100 xxxxf)()(, )(,)(,)()(10021000010000003xxxxxxxxxxfxxxxxxxfxxxxfxfxH-#00000112 , , , ,f x xf x xf x xf x x000001012,f x x xf x
49、x xf x x x0001,f x x x x240000000033000100001201( )(),(),(),(),() ()Hxf xf x xxxf x x xxxf x x x xxxf x x x x xxxxx-00012xxxxx00012()()()()()f xf xf xf xf x0()fx0012,f x x x x0()2!fx00012,f x x x x x7 分段低次插值分段低次插值 /* piecewise polynomial approximation */ 为了保证插值函数的逼近效果，需要较多的插值节，为了保证插值函数的逼近效果，需要较多的插值节
50、，导致较高的多项式次数。导致较高的多项式次数。 然而在实际应用中然而在实际应用中, , 很少采用高次插值很少采用高次插值: : 在两相邻插值节点间在两相邻插值节点间, , 插值函数未必能够很好地近似插值函数未必能够很好地近似被插值函数被插值函数; ; 对于等距节点的牛顿插值公式对于等距节点的牛顿插值公式, , 函数值的微小扰动可函数值的微小扰动可能引起高阶差分有很大的变化。能引起高阶差分有很大的变化。7-1 多项式插值的问题多项式插值的问题Remember what I have said? Increasing the degree of interpolating polynomial w
