数值分析及计算方法 第一章 插值法

1、 本章内容 1.1 Lagrange插值多项式 1.2 Newton插值多项式 1.3 分段低次插值第一章第一章 插值法插值法/* Interpolation Method */Start from here 实际问题中，某些变量之间的函数关系是存在的，只能由实际问题中，某些变量之间的函数关系是存在的，只能由测量或实验得到一系列的离散点上的函数值：测量或实验得到一系列的离散点上的函数值：，nnyyyyyxxxxx210210问题的提出问题的提出( )yf x ？（1）有的函数没有表达式，只是一种表格函数，而我们需要的有的函数没有表达式，只是一种表格函数，而我们需要的函数值可能不在该表格中。函数

2、值可能不在该表格中。（2）如果函数表达式本身比较复杂，计算量会很大；如果函数表达式本身比较复杂，计算量会很大； 对于这两种情况，我们都需要寻找一个计算方便且表达简单对于这两种情况，我们都需要寻找一个计算方便且表达简单的函数的函数 来近似代替来近似代替 ，求求 的方法称为的方法称为插值法插值法。 P x( )f x P x( )( )( )P xf xP x以以近近似似，以以代代替替的性质近似代替的性质近似代替 性质性质 fx一、插值法基本思想一、插值法基本思想( )1f xn Def4.1 已Def4.1 已知知y=在y=在个互异节点上的值，若存在一个个互异节点上的值，若存在一个( ),()(

3、)0 1 2,iiiP xP xf xyin ， ，简单函数简单函数()()()()iiiP xfxxfxP xy 插值节点；插值节点；为为 的插值函数；的插值函数；被插函数被插函数插值条件插值条件求求 的方法称为的方法称为插值法插值法。()P xx0 x1x2x3x4xP(x) f(x)( )yP x ( )yf x 几何意义：几何意义：x注：注：简单函数简单函数常指：多项式函数、分段多项式函数、有理函数；常指：多项式函数、分段多项式函数、有理函数； 相应插值法称为：相应插值法称为：代数插值代数插值法、法、分段插值分段插值、有理函数插值有理函数插值；特别特别： 所求所求 是过两点的直线是过两

4、点的直线线性插值线性插值 所求所求 是过三点的二次曲线是过三点的二次曲线抛物插值抛物插值 12( )2( )1nPnPxx ， ，我们主要介绍我们主要介绍代数插值代数插值（插值函数为（插值函数为多项式多项式 的插值），的插值），相应的相应的 称为称为插值多项式插值多项式。( )nPx( )nPx二、插值多项式二、插值多项式( )npx的存在唯一性的存在唯一性证明：证明：01220001201002111122nnnnnnnnnnxxxyxxxyaaxaaaaaaaaa xya x ，只要证得只要证得 存在唯一即可，由存在唯一即可，由ia()njjpxy Th4.1 0120121()()0 1

5、( )nnjjjnnnxxxnpxyf xjnnpxaa xa xa x 已已知知， ， 是是， ， 的的 次次是是存存在在且且唯唯一一的的；个互异节点，则满足插值个互异节点，则满足插值多项式多项式条件条件0()0ijj i nxx 200021112111nnnnnnxxxxxxAxxx注：注：若若不限定次数不限定次数，则插值多项式，则插值多项式不唯一不唯一；如：如：若若 满足插值条件，则满足插值条件，则 亦满足亦满足0( )( )()nnniipxpxxx 法则，法则，n+1个插值条件唯一确定一个个插值条件唯一确定一个n次次插值多项式。插值多项式。Cramer由由Vandermond行列式

6、行列式一、一、Lagrange插值多项式插值多项式 由由Th4.1Th4.1知，知， )(xpn中系数的计算只需求解一个中系数的计算只需求解一个 1n 元方元方 程组，程组，待定系数法计算复杂待定系数法计算复杂，且难以得到，且难以得到 式；下面来介绍式；下面来介绍构造法构造法。)(xpn的简单表达的简单表达的构造的构造 )(xpn1.2 Lagrange插值多项式插值多项式/* Lagrange Polynomial */niyxPiin,., 0,)( 求求 n 次多项式次多项式 使得使得nnnxaxaaxP 10)(条件：条件：无重合节点，即无重合节点，即jixx ji n = 1已知已知

7、 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP 可见可见 P1(x) 是过是过 ( x0 , y0 ) 和和 ( x1, y1 ) 两点的两点的直线直线。)()(0010101xxxxyyyxP 101xxxx 010 xxxx = y0 + y1l0(x)l1(x) 10)(iiiyxl10()ijijijl xij 1 1、基本插值多项式、基本插值多项式: :Lagrange插值多项式插值多项式0()niinil x yLx njijjijixxxxxl0)()()(与与 有关有关，而与而与 无关无关插值基函数插值基函数/ /

8、基本插值多项式基本插值多项式n 1希望找到希望找到n次次多项式多项式li(x)，i = 0, , n 使得使得 li(xj)= ij；然后令然后令 niiinyxlxP0)()(，则显然有，则显然有Pn(xi) = yi 。li(x)每个每个 li(x) 有有 n 个根个根 x0 xi-1 、 xi+1 xn j i jiiiixxCxl)(11)(n n次次Lagrange 插值插值多项式多项式节点节点y0110( )()()()()()niiiinijjj il xC xxxxxxxxCxx 01110111()()()()()( )()()()()()iiniiiiiiiinxxxxxx

9、xxxxl xxxxxxxxxxx 2 2、插值余项、插值余项-( )( )( )nnRxf xLx(1)1)1101( )( )( )(1)( )()(!( )()()()()( )()nnnnnnnfxa bfRxxnxxxxxxa ba bf xL xxx ， ， ，中中。其其Th4.2设设 个节点个节点 若若 在在 连续，连续， 在在 内存在，则内存在，则 1n ( )( )nixa bfxa b ， ，插值多项式的余项插值多项式的余项证明：证明：011()()()00( )( )()()( )( )nnnjjnjjnnRxf xLxjnxRxRxK xKxxxxxxxx ，是是；的零

10、点的零点设设引入引入辅助函数辅助函数 则则1( )( )( )( )nntRK xtt ，至少有至少有 个互异零点：个互异零点：( ) t 2n 01nx xxx， ， ，。，；即；即至少有一个零点至少有一个零点个零点；个零点；至少有至少有；个互异零点个互异零点至少有至少有同理：同理：；个互异零点个互异零点至少有至少有由由)()!1()()()!1()()(0)!1()()()!1()()()()()()()()(1)()(1)(1)1()1()1()1()1(1)1()1()1(xnfxRnfxKnxKfnxKRxKRbatntntntThRollennnnnnnnnnnnn 0( )1(

11、)1nkkf xlx ，；若若 则则若若 本身是次数本身是次数不超过不超过n的多项式，的多项式，则，则， 即即0( )0( )( )nnkknkf xLxRxlx y ，；2( )f x 通常是次数为通常是次数为n的多项式，特殊情形下可能的多项式，特殊情形下可能小于小于n,如如过三点的过三点的 若三点共线，则若三点共线，则 是一条直线是一条直线(一次一次)3( )nLx 2( )L x2( )yL x (111)1( )( )(1)(1)!nnnnnMRxxnfNotexM 若若，；则有余项则有余项(1)1( )( )( )(1)!nnnfRxxn 例例1：已知已知233sin,214sin,

12、216sin 分别利用分别利用 sin x 的的1次、次、2次次 Lagrange 插值计算插值计算 sin 50 并估计误差。并估计误差。 解：解：0 x1x2x185500 n = 1分别利用分别利用x0, x1 以及以及 x1, x2 计算计算4,610 xx利用利用1/4/6/6/411( )22/4/6xL xx 这里这里26 4423132( )( )sin ,( )sin ,( , )( , )sinsinf xx f ，而而21264( )( )( )()()!fR xxx 15()0.0107718R sin 50 = 0.7660444)185(50sin10 L0.776

13、143,421 xx利用利用sin 50 0.76008, 113/3/4/4/3( )23/42/Lxxx 21243( )( )( )()()!fR xxx 150.0066018R 内插内插通常优于通常优于外推外推。选择。选择要计算的要计算的 x 在区间的内部，在区间的内部，插值效果较好。插值效果较好。二次二次插值比插值比一次一次插插值精度高值精度高n = 24363646463464363234()()()()()()()()()()113( )()222(xxxxxL xx )185(50sin20 L0.765433264336433( )cos( )()()()()( )()!;

14、Rxxxxxfxx 250.0007718R 但绝对不是次数越但绝对不是次数越高就越好高就越好36 32(,)cos ，Lagrange插值多项式的缺点：插值多项式的缺点：基函数计算复杂；且已得的基函数计算复杂；且已得的 无用，需重新算过；无用，需重新算过； ( )nLx对于计算对于计算 1( )nLx 高次插值精度未必高；高次插值精度未必高；RungeRunge现象现象1( )( )nnLxLx ，比较比较n-1次及次及n次插值多项式次插值多项式若非常接近，则以若非常接近，则以n次插值次插值否则增加节点计算否则增加节点计算( )( )nLxfx ，1( )nLx 。通常方法：实用通常方法：实

15、用后验估计后验估计不知道选择多少个插值节点为宜；不知道选择多少个插值节点为宜； 本节内容提要本节内容提要 基本思想基本思想 NewtonNewton插值多项式的构造插值多项式的构造 均差均差( (差商差商) ) 定义、计算、性质定义、计算、性质 NewtonNewton插值多项式的误差插值多项式的误差差分及等距节点插值公式差分及等距节点插值公式1.3 Newton插值多项式插值多项式/* Newtons Interpolation */一、一、基本思想基本思想 缺点：缺点：增加节点时，需要计算增加节点时，需要计算 ，而已得的，而已得的 不能被利用；不能被利用； ( )nLx1( )nLx 为此

16、我们考虑对为此我们考虑对LagrangeLagrange插值多项式插值多项式进行进行改写改写； 由唯一性，仅是由唯一性，仅是形式上形式上的变化的变化 已知已知n+1个互异插值节点个互异插值节点 由插值多项由插值多项式的存在唯一性，可以构造式的存在唯一性，可以构造Lagrange插值多项式：插值多项式：01nxxx， ， ， ，00( )( )( )nninkkkkikii kxxLxlx ylxxx ，；期望期望： 的计算只需要对的计算只需要对 作一个简单的修正作一个简单的修正.( )nLx1( )nLx 1011( )( )()()()nnnnnLxLxxxxxxaax ， 待待定定；考虑考

17、虑1( )( )( )nnh xLxLx 是次数是次数 的多项式，且有的多项式，且有( )h xn 1()(0)()2101jnjnjjhxLnxLx ， ，；011( )()()()nnh xxxxxxxa ，由新增节点可以计算出由新增节点可以计算出 从而从而1( )( )nnLxLx ；na ，1011()()()()()()nnnnnnnnnnnxLxLxxxxxxxfaxx 取取，110110011001100()() ()()()()()()()()()nnknknnnnknnnniniiinnnikkikii knnnniniiif xlxf xLxLxaxxxxxxf xxxf

18、xxxxx 111000110000100()()()()()()()()()()()(nnknnkninkkiiii knnknnknikiiiinknnkkiknknkkiikf xf xxxxf xaxxxxxf xf xxxxxf xx ；此公式仍然比较麻烦！此公式仍然比较麻烦！ 二、二、差商（均差）差商（均差）1 1、定义定义：称称 为为 关于节点关于节点 的的一阶差商一阶差商/均差均差记作记作 表示表示 在区间在区间 上的变化率。上的变化率。()()jijif xf xxx ( )f xijxx，ijf xx，( )f xijxx，称一阶差商称一阶差商 的差商为的差商为 关于节关于

19、节点点 的的二阶差商二阶差商，记作：，记作：ijjkf xxf xx，( )f xijkxxx， ，jkijijkkif xxf xxf xxxxx ， ，；注：注：为统一记号，规定：为统一记号，规定： ()iifxf x ；称为零阶差商称为零阶差商类比：类比：导数：导数：差商（均差）：差商（均差）：0000( )()()limxxf xf xfxxx ；()()jiijjif xf xf xxxx ，；12011010nnnnfxxxfxxxfxxxxx ， ， ， ， ， ， ，；一般地，称一般地，称n-1阶差商的差商为阶差商的差商为n阶差商阶差商，有：，有： 实际计算过程为（实际计算过程

20、为（建立差商表建立差商表）f x0, x1f x1, x2 f xn 1, xnf x0, x1 , x2 f xn 2, xn 1, xnf x0, , xn xn+1 f (xn+1) f xn, xn+1 f xn 1, xn, xn+1 f x1, , xn+1 f x0, , xn+1f (x0)f (x1)f (x2)f (xn 1)f (xn)x0 x1x2xn 1xn零阶差商零阶差商 一阶差商一阶差商 二阶差商二阶差商 n阶差商阶差商2 2、差商的计算差商的计算1421406171kkxf x一一二二三三四四-3-1/21/205/61/4-1/6-7/60-1/121/180

21、例例1 1： 12467()41011kkxf x已已知知：， 列列出出差差商商表表；解：解：可见，求各阶均差是方便的，且可见，求各阶均差是方便的，且 001f xf xx， ，012f xxx， ，位于差商表的对角线上。位于差商表的对角线上。3 3、差商性质差商性质 /* Property of divided difference */n阶差商可以表示为阶差商可以表示为 的线性组合的线性组合()kf x性质性质1 1111000()()()()(,.,).nkkkkkkkknnf xxxxxxxxxf x xx 证明：证明： 数学归纳法数学归纳法100101100110()()()(),f

22、 xf xf xf xf xxxxxxxx n=1；，；，时成立，即时成立，即设设 11111210010)()()()(mkmkiiikkmmkmkiiikkmxxxfxxxfxxxfxxxfmn)()()()(11001111010110121110 mkmkiiikkmkmkiiikkmmmmmxxxfxxxfxxxxxxxfxxxfxxxfmn，时，有：时，有：则则)()()()()()()()(1100101111101 miimkmkiiikkmkiiikkmiimmmxxxfxxxfxxxfxxxfxx01111011001100()()()()()()()()mmkmmmkim

23、ikiiiii kmkmkkiii kf xxxf xf xf xxxxxxx 得证。得证。性质性质2 差商具有对称性，即差商具有对称性，即 的值与节点的值与节点 的顺序无关。的顺序无关。01,nf xxxix由性质由性质1 1易知：调换两个节点的位置，相当于右端易知：调换两个节点的位置，相当于右端改变求改变求和次序。和次序。性质性质4 4 0100( )( ) , ,.,!(min,.,max,.,)nnnnff x xxnxxxx n阶差商和阶差商和n阶导数之间存在如下关系：阶导数之间存在如下关系：性质性质3n 次多项式次多项式的的 k 阶差商阶差商 当当 时是时是 n-k 次多项式，而当

24、次多项式，而当 kn 时其值时其值恒等于零。恒等于零。011 ,kf x xxx kn 用用fx,x0,xl=xm验证即可验证即可。，；即即，至至少少有有一一个个零零点点个个互互异异零零点点；至至少少有有个个互互异异零零点点；至至少少有有个个互互异异零零点点，由由有有；即即：，由由于于，；令令，其其中中；)(!)(0!)()()(0)()()(1)()(1)(100)()()()()()()()()(10)()()()()(10110010banfaxxxfanfLfRbaxRnxRnxRThRollenxRnkxRxLxfxRxxxfaxxxxxxaxxaaxLnnnnnnnnnnnnnkn

25、nnnnnnn 证明：证明：三、三、NewtonNewton插值多项式插值多项式/* Newtons Interpolation */1 1、定义：、定义：,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf ).(.)()()(10102010 nnnxxxxaxxxxaxxaaxN12 n 11+ (x x0) 2+ + (x x0)(x xn 1) n 1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100

26、nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi 4( )(1)(1)(2)(1)(2)(45436760118)(1)(2)(4)(60)Nxxxxxxxxxxx ；例例2： 解：解： 12467()410114kkxf xNewton给定数据：，求次插值多项式；先求差商表（上例已求出），先求差商表（上例已求出），4 4次牛顿插次牛顿插值多项式为：值多项式为：2、余项余项： (1)1( )( )( )( )(1)!nnnff xNxxn ；带余项的带余项的Newton插值公式插值公式 ；，的的任任意意性性，可可得得：由由；，从从而而：其其中中；，则则有有：，增增

27、加加节节点点，；得得，已已知知互互异异节节点点)()()()()()()()()()()()()(1101101110110 xxxxxfxNxfxxxxxxfxNxfxfxNxxxxxfxNxNxbaxxNxxxnnnnnnnnnnnnn 证明：证明：；，阶连续导，则：阶连续导，则：上有上有，在在若若)(!)1()()()(!)1()(1)(1)1()1(10 xnfxNxfnfxxxxfnbaxfnnnnn 比较可知，比较可知， 与与 的确只是形式上的不同，的确只是形式上的不同，Newton插值多项式便于计算，而插值多项式便于计算，而Lagrange插值插值多项式多用于理论推导。多项式多用

28、于理论推导。 注注： ( )nNx( )nLx性质性质2 2例：例：习题习题4-8设设 互不相同，证明互不相同，证明并写出并写出 的的n次次Newton插值多项式。插值多项式。01011 2()kkiif xxxknax ， ， ， ， ；011( )nf xa xxxax ，且且 ， ， ， ，( )f x证明证明( (归纳法归纳法) ) 010121111()1()mmiimmiif xxxaxf xxxax ， ， ，；， ， ，；设设 时成立，即时成立，即km 011()()axax ；1010111xxaxax010101()()1f xkf xxf xxx ，11010111()(

29、)()mmmiiiixxaxax 10101011111()(1()mimmmiiixxaaxaxaxx 01112101101mmmmf xxxf xxkmxf xxxxx ，有有：， ， ， ， ， ，得证。得证。( )f x001001011( )()()()()nnnNxf xf xxxxf xxxxxxxxx ， ， ，0001101011()()()()()()(nnxxxxxaxaxaxaxaxaxxxx ；的的n次次Newton插值多项式插值多项式 本节内容提要本节内容提要|基本概念 有限差(向前差分、向后差分、中心差分)|差分的计算 |差分的性质等距节点插值公式 1.4 差分

30、与等距节点插值公式差分与等距节点插值公式 /* Interpolation Formulae with Equal Spacing */ 上节谈论了节点任意分布的上节谈论了节点任意分布的Newton插值公式，实际应插值公式，实际应用时常碰到等距节点的情形，即：用时常碰到等距节点的情形，即： hnjjhxxj，2100 步长步长 此时公式可进一步简化，同时可以避开除法运算，此时公式可进一步简化，同时可以避开除法运算，引入差分的概念。引入差分的概念。 前前 言言称称为为 在在 处以处以h为步长的二阶向前差分，简称二阶差分为步长的二阶向前差分，简称二阶差分1211221()()2jjjjjjjjjj

31、ffffffffff ( )jf xx设等距节点设等距节点 处的函数值处的函数值为为 称称 处以处以h为步长的一阶向前差分，简称一阶差分，记作：为步长的一阶向前差分，简称一阶差分，记作： ()，jjf xf 00 1 2， ，jxxjh jn jf 一、差分一、差分1 1、定义：、定义：11( )() (为 在jjjjjffff xf xxx 注：注： 类似可以定义：类似可以定义：一般地，称一般地，称 为为 处以处以h为步长的为步长的m阶向前差分，简称阶向前差分，简称m阶差分。阶差分。111( )mmmjjjjf xxfff 在在1111211211()()()()jjjjjjjjjjjjmm

32、jmjjff xf xffffffffffff ；一阶后差：一阶后差：二阶后差：二阶后差：m阶后差：阶后差：前差、后差、中心差前差、后差、中心差 统称为统称为有限差有限差； 有限差算子有限差算子 ， 1122211111122()()22jjjjjjmmjjjjjjmjhhff xf xffffffffff ；一阶中心差：一阶中心差：二阶中心差：二阶中心差：m阶中心差：阶中心差：000()()()jjjjjjf xf xffxff ； 为统一记，规定零阶有限差为：为统一记，规定零阶有限差为： 2 2、差分的计算（以前差为例）、差分的计算（以前差为例）4433322222131211104030

33、2000432fxffxfffxffffxfffffxfffffxkkkkkk 列差分表列差分表例：例： 解：解：列出差分表；列出差分表；，已知：已知：27181163)(43210kkxfx2340316211318427kkkkkkxfffff 35792220003 3、性质性质 归纳法证明归纳法证明 利用利用函数值函数值表示高阶表示高阶有限差有限差：； nijininiinjinijnhinxfCfCf00)()1()1( 利用利用各阶差分各阶差分表示表示函数值函数值：； nijiinnijiinjjnxfCfCnhxff00)()( 差商差商与与差分差分之间的关系：之间的关系： 1!

34、kiiii kkffxxxkh ， ，；，成立；，成立；，时，有：时，有：则当则当；，；，时结论成立，时结论成立，设设；，时，时，1010101101211011210100010110!)1()1(!1!)2()()(1)1( kkkkkkkknkkkkkkhkfhkhkffxxxxxfxxxfxxxfknhkfxxxfhkfxxxfknhfxxxfxfxxfn证明：证明： 将将Newton插值公式中各阶差商用相应差分代替，可插值公式中各阶差商用相应差分代替，可得各种形式的等距节点插值多项式，以下介绍常用得各种形式的等距节点插值多项式，以下介绍常用Newton前插与后插公式。前插与后插公式。

35、记节点记节点则则000 1 2jjnxxjhxxth ， ， ；令令，0101()()( )(1)()nnnjjnjxxtxt ttn hj h ；二、等距节点插值公式二、等距节点插值公式001001011( )()()()()nnnNxf xf xxxxf xxxxxxxxx ， ， ，；由由Newton插值公式：插值公式：NewtonNewton前插公式前插公式上述公式中用上述公式中用差分差分代替代替差商差商001,!,kkkff xxxk h 010100()()!nkknkikkNxthfhtifk h 00111()()!knkfft ttkk 2000011211.!.!nffft

36、t tft ttnn 例例： 解解：304560()kkxf x已已知知：，1 12 23 32 22 22 2求二次牛顿前求二次牛顿前插公式插公式2130224523602kkkkxfff 12121322 132 212取差分表第一行数据，取差分表第一行数据，得得Newton前插公式：前插公式：20200(3015 )(1)2!fNtfftt t 1112132 21224(1)tt t 前前插插公公式式；求求，已已知知：Newtonxfxkk27181163)(43210例：例： 解：解：2340316211318427kkkkkkxfffff 3579222000取差分表第一行数据，得

37、取差分表第一行数据，得Newton前插公式：前插公式：230040040( )(1)(1)(2)2!3!(1)(2)(3)4!ffNtfftt tt ttft ttt (3)31tt t ； 牛顿牛顿向后插值向后插值公式公式 /* Newtons backward-difference formula */当插值点当插值点 位于插值区间右端点位于插值区间右端点 附近时附近时 nxx10nxxtht 令令将节点顺序将节点顺序倒置倒置：).(,.,.)(,)()(101xxxxxxfxxxxfxfxNnnnnnnn 上述公式中用上述公式中用差分差分代替代替差商差商0110,!kkkkyf xxx

38、xk h ()n ixxti h 22011112.!nnnnyyyy tt tt tt nn 110()()!knkkn knnnkkiyNxthyhtik h 111()()!knn knkyyt ttkk 称之为牛顿称之为牛顿向后插值向后插值公式公式注：注：一般当一般当 x 靠近靠近 x0 时用前插公式，靠近时用前插公式，靠近 xn 时用后插公式，故时用后插公式，故两种公式亦称为两种公式亦称为表初公式表初公式和和表末公式表末公式。插值插值余项余项1111111()()( ) ()()()!( )nnnnnnt nfRfht ttnnCfh 注注：若插值点位于节点中部，则可利用中心差分构造

39、：若插值点位于节点中部，则可利用中心差分构造 StirlingStirling插值插值、BesselBessel插值插值等；等； 用于用于高精度要求高精度要求的函数插值，现已少用！的函数插值，现已少用！ 例例 给定给定f(x)在等距节点上的函数值表如下在等距节点上的函数值表如下: xi 0.4 0.6 0.8 1.0 f(xi) 1.5 1.8 2.2 2.8分别用分别用Newton向前和向后差分公式求向前和向后差分公式求f(0.5)及及f(0.9)的近似值的近似值 解解 先构造向前差分表如下先构造向前差分表如下: xi fi fi 2 2fi 3 3fi 0.4 1.5 0.6 1.8 0.

40、3 0.8 2.2 0.4 0.1 1.0 2.8 0.6 0.2 0.1 x0=0.4, h=0.2, x3=1.0. 分别用差分表中分别用差分表中对角线上对角线上的值的值和和最后一行最后一行的值的值,得得Newton向前和向后插值公式如下向前和向后插值公式如下:33(1)(1)(2)(0.40.2 )1.50.30.10.123!(1)(1)(2)(1 0.2 )2.80.60.20.123!t tt ttNttt tt ttNtt(1) (2)当当 x=0.5时时, ,用公式用公式(1),(1),这时这时t=(x-x0)/h=0.5. 将将t=0.5代代入入(1),(1),得得 f (0

41、.5)N3(0.5)=1.64375.当当x=0.9时时, , 用公式用公式(2), (2), 这时这时t=(x3-x)/h=0.5. 将将t=0.5代入代入(2), (2), 得得 f (0.9)N3(0.9)=2.46875. go 分段分段 本节内容提要本节内容提要|Hermite插值 方法概述、几何意义、误差估计1.5 埃尔米特插值埃尔米特插值/* Hermite Interpolation */不仅要求函数值重合，而且要求若干阶不仅要求函数值重合，而且要求若干阶导数导数也重合。也重合。即：要求插值函数即：要求插值函数 (x) 满足满足 (xi) = f (xi), (xi) = f

42、(xi), (mi) (xi) = f (mi) (xi).注：注： N 个条件可以确定个条件可以确定 阶多项式。阶多项式。N 1要求在要求在1个节点个节点 x0 处直到处直到m0 阶导数都重合的插阶导数都重合的插值多项式即为值多项式即为Taylor多项式多项式00)(!)(.)()()(000)(000mmxxmxfxxxfxfx 其余项为其余项为)1(00)1(00)()!1()()()()(mmxxmfxxfxR 一般只考虑一般只考虑 f 与与f 的值。的值。例：例：设设 x0 x1 x2, 已知已知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多项式求多项式 P(x

43、) 满足满足 P(xi) = f (xi)，i = 0, 1, 2，且且 P(x1) = f (x1), 并估计误差。并估计误差。模仿模仿 Lagrange 多项式的思想，设多项式的思想，设解：解：首先，首先，P 的阶数的阶数 = 3 213)()()()()( 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

44、由余下条件由余下条件 h1(x1) = 1 和和 h1(x1) = 0 可解。可解。与与h0(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 分析分析完全类似完全类似一般地，已知一般地，已知 x0 , , xn 处有处有 y0 , , yn 和和 y0 ,

45、 , yn ，求，求 H2n+1(x) 满足满足 H2n+1(xi) = yi ， H2n+1(xi) = yi。解：解：设设 ni)()()( 0iixhxhyixH2n+1 n 0iyi其中其中 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij hi hihi(x)有根有根 x0 , , xi , , xn且都是且都是2重根重根 )()()(2xlBxAxhiiii ijjijixxxxxl)()()(由余下条件由余下条件 hi(xi) = 1 和和 hi(xi) = 0 可解可解Ai 和和 Bi )()(21 )(2xlxxxlxhiiiii (

46、x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxCx hi又又: (xi) = 1 Ci = 1 hi)(x)(ili2(x)xx 设设,.210baCfbxxxann 则则20)22()()!22()()( niixnnxxnfxR x0 x1x2x3x4xH9(x) f(x) 9( )yH x ( )yf x 全导数的全导数的Hermite插值多项式的插值多项式的几何意义几何意义如如n=1时时Hermite插值多项式插值多项式 为为3( )Hx220011301010110102201001101101 21 2( )( )(

47、 )( )()( )()xxx xx xxxH xf xf xxxxxxxxxx xx xf xx xf x x xxxxx 求求Hermite多项式的基本步骤：多项式的基本步骤： 写出相应于条件的写出相应于条件的hi(x)、 hi(x) 的组合形式；的组合形式； 对每一个对每一个hi(x)、 hi(x) 找出尽可能多的条件给出的根；找出尽可能多的条件给出的根； 根据多项式的总阶数和根的个数写出表达式；根据多项式的总阶数和根的个数写出表达式； 根据尚未利用的条件解出表达式中的待定系数；根据尚未利用的条件解出表达式中的待定系数； 最后完整写出最后完整写出H(x)。 余项余项： (22)2211(

48、 )( )( )( )(22)!；nnnff xHxxn 带余项的带余项的HermiteHermite插值公式插值公式 例例已知已知 且在且在 处有处有求一个次数不超过求一个次数不超过3的多项式的多项式 111()0 1 2()iif xyixfxm ，33( )iiP xP xy ，31110 1 2()()Pximfx ，且且。021201021012012210120()()()()()()()()()()( )()( )()xxxxxxxxxxxxxxxxxxxxxxlxxlxxlx ，；32001122( )( )( )( )( )P xL xlx ylx ylx y 求求；令令；其

49、其中中解解3232( )( )( )( )( )( )Q xPP xL xQxxL x 令令，那那么么是是012( )()()()AQ xA xxxxxx 令令， 待待定定；至少至少3次多项式，次多项式， 三个零点，那么三个零点，那么012xxx且且有有，1021201010210121021012120212()()()()()()()()xxxxxyyxxxxxxxxxxyA xxxxmxxxxA ？32012( )( )()()()P xL xA xxxxxx 代代入入可可得得：；312111()()()PxLxQ xm 由导数插值条件由导数插值条件余项，记余项，记 的单根，的单根，的二

50、重根，的二重根，302( )( )( )( )R xf xP xxxR x ，是是1( )xR x是是2012( )( )()() ()( )R xK xxxxxxxK x 令令，待待定定；2012( )( )( )()() ()RK xxxtttttx 令令( ) t 021()xxxx，二二重重 ；在插值区间内有在插值区间内有5个零点个零点由由RolleTH ， 在区间内至少存在一个零在区间内至少存在一个零点点(4)( ) t ，4441( )( )( ) 4!0( )( )4!fK xK xf （ ）（ ）（ ），则有则有42012( )( )()() ()4!fR xxxxxxx （）

51、。 本节内容提要本节内容提要|分段线性插值 方法概述、几何意义、误差估计|分段二次插值 几何直观、方法概述、误差估计三次样条插值简介 1.3 分段低次插值分段低次插值/* piecewise Interpolation */1111()( )( )( )( )( )()!nnnnfRxf xL xxn 1 1、从插值余项角度分析、从插值余项角度分析随着节点个数增加到随着节点个数增加到某个值某个值，误差反而会增加。，误差反而会增加。一、高次插值评述一、高次插值评述 为了提高为了提高插值精度插值精度，一般来说应该，一般来说应该增加增加插值节点的个数，插值节点的个数，这从插值余项的表达式也可以看出，

52、但不能简单地这样认为，这从插值余项的表达式也可以看出，但不能简单地这样认为，原因是原因是前提条件是前提条件是 有有足够阶连续导数足够阶连续导数(即函数足够光滑即函数足够光滑)，但随着节点个数的增加，这个条件一般很难成立但随着节点个数的增加，这个条件一般很难成立。( )f x注意下面图中注意下面图中曲线曲线的变化情况！的变化情况！例：例： 在在 5, 5上考察上考察 的的Ln(x)。取。取211( )f xx 1050(,., )ixi inn -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端点端点附近变化附近变化越大，称为越

53、大，称为Runge 现象现象Ln(x) f (x) 2n ( )yf x 5n 10n RungeRunge现象现象：注：注：高次插值可能出现：在插值区间高次插值可能出现：在插值区间中部误差较小中部误差较小， 而在而在端点附近误差较大端点附近误差较大的情形。的情形。RungeRunge现象现象RungeRunge现象说明并非节点越多（插值多项式次数现象说明并非节点越多（插值多项式次数越高），误差越小；越高），误差越小； 。不总收敛到不总收敛到)()(xfxPn高次插值的缺点高次插值的缺点RungeRunge现象的存在；现象的存在；克服方法克服方法分段低次插值分段低次插值；分段插值的构造方法分段

54、插值的构造方法将将插值区间插值区间划分为若干个小区间（通常取划分为若干个小区间（通常取等距划分等距划分）abix1ix 采用采用低次低次插值插值( )iP x在区间在区间 上得到上得到分段函数分段函数 , a b00111211( ),( ),( )( ),nnnp xxx xp xxx xxpxxxx ( )f x 11,111( )01iiiiiiiiix xx xLxyyxxxinx ，；1 0011 11211111( )( )( )( )( )( )nnnLxxxxLxxxxL xLxfxLxxxx ，令令，那那么么，一、分段线性插值一、分段线性插值/* piecewise line

55、ar interpolation */ 1 1、方法概述：、方法概述：在每个区间在每个区间 上，用上，用1次多项式次多项式 (直线直线) 逼近逼近 f (x):1,iix x 01naxxxb ，101maxiiiii nhxxhh 令令，分段分段线性线性插值插值函数函数2 2、几何意义：、几何意义： 分段线性插值从整体上看，逼近效果是较好的，但失分段线性插值从整体上看，逼近效果是较好的，但失去了原函数的去了原函数的光滑性光滑性。3 3、误差估计：、误差估计：111()( )( )()()2!iiiiiiiff xLxxxxxx x ，由由于于，122max()(88iiixx xiihfxh

56、f 1221(01()()(1)(1)iiiiiiiiixxt htxxhxxxxt thtt h ，那那么么， 211()()1(1)014)4iiixxhttxtx 易易知知，那那么么11021201max( )( )max()80( )( )max( )(08)ii niiia xnbf xLxhff xLfxxhh ， 只依赖于二阶导函数的界只依赖于二阶导函数的界 )()(2有有界界，前前提提：xfbaCxf 1 1、几何直观：、几何直观： 二、分段二次插值二、分段二次插值/* Piecewise Square Interpolation */ 分段抛物线弧段近似分段抛物线弧段近似 (

57、 )f x在每个区间在每个区间 上，用上，用2次多次多项式项式 (抛物线抛物线) 逼近逼近 f (x)。222(0 11)kkxxkm ， ，2 0022 2242222( )( )( )( )nnnSxxxxSxxxxSxSxxxx ，令令；，012naxxxbnm ，2 22221212222( )( )( )( )kkkkkkkSxlx ylx ylx y ，2 2、方法概述：、方法概述：2222 0022 22432222131( )( )( )()21)( )(nnnnnnnnnxxSxSxxxxSxxxnxxSxSxxSxmxxxx ，在在，上上作作二二次次插插值值，令令，；，分段

58、分段二次插值二次插值函数函数3 3、误差估计：、误差估计：2222 22212233222()( )( )()()()3!()6maxax(m)6kkkxxxkkkkkkkkkkkhff xSxxxxxxxfxhxhxfhh ，其其中中， 3( )f xCa b 前前提提：，22 23( )( )max( )( )max60 (0)( )axbkkf xSxf xhfxhxS ，。 收敛性好，计算简单；亦可根据其具体情况收敛性好，计算简单；亦可根据其具体情况 在不在不同区间上采用不同次数的插值公式；同区间上采用不同次数的插值公式； 分段函数虽然在节点处连续但未必可导，因而分段函数虽然在节点处连

59、续但未必可导，因而 光光滑度较差滑度较差。克服方法克服方法 三次样条插值三次样条插值优点优点缺点缺点 分段插值存在着一个缺点分段插值存在着一个缺点, ,就是会导致插值函数在就是会导致插值函数在子区间的端点子区间的端点( (衔接处衔接处) )不光滑不光滑, ,即导数不连续即导数不连续, ,对于一些实对于一些实际问题际问题, ,不但要求一阶导数连续不但要求一阶导数连续, ,而且要求二阶导数连续。而且要求二阶导数连续。为了满足这些要求为了满足这些要求, ,人们引入了人们引入了样条插值样条插值的概念。的概念。 1.5 样条插值函数样条插值函数所谓所谓“样条样条”(SPLINE)是工程绘图中的一种工具是

60、工程绘图中的一种工具, ,它是有它是有弹性的细长木条弹性的细长木条, ,绘图时绘图时, ,用细木条连接相近的几个结点用细木条连接相近的几个结点, ,然后再进行拼接然后再进行拼接, ,连接全部结点连接全部结点, ,使之成为一条光滑曲线使之成为一条光滑曲线, ,且在结点处具有连续的曲率。样条函数就是对这样的曲且在结点处具有连续的曲率。样条函数就是对这样的曲线进行数学模拟得到的。它除了要求给出各个结点处的线进行数学模拟得到的。它除了要求给出各个结点处的函数值外函数值外, ,只需提供两个边界点处导数信息只需提供两个边界点处导数信息, ,便可满足对光便可满足对光滑性的不同要求。滑性的不同要求。一、样条函