数值分析第二章第二节

1、上一页上一页下一页下一页湘潭大学数学与计算科学学院12 2 Lagrange插值插值 一、问题的提法一、问题的提法 二、适定性和二、适定性和Lagrange插值公式插值公式 三、三、Neville插值公式插值公式 四、四、Newton插值公式插值公式 上一页上一页下一页下一页湘潭大学数学与计算科学学院2一、问题的提法一、问题的提法(),0,1, ,iif xyin已知：已知：( )f x1 n 的的个样本值个样本值01,nx xx设设彼此互异彼此互异, ,01nnaa xa x 记所有次数不超过记所有次数不超过n的代数多项式的代数多项式.nP的全体为的全体为上一页上一页下一页下一页湘潭大学数学

2、与计算科学学院3插值问题插值问题： 求求,nnPp 满足满足(),0,1, .niipxyin 00,x y ,iix y ,nnxy( )f x( )npx01,nxxx称称为为被插函数被插函数，为为n次次多项式插值函数多项式插值函数，为为插值节点插值节点，的的Lagrange插值问题插值问题 并称并称而上述而上述问题问题被称为被称为 01,nxxx关于节点关于节点上一页上一页下一页下一页湘潭大学数学与计算科学学院4二、适定性和二、适定性和Lagrange插值公式插值公式 定理定理 2.1 2.1 插值问题的解是插值问题的解是存在且唯一存在且唯一的的. . 证明：（证明：（构造性构造性证明）

3、证明）（1 1）存在性）存在性 首先构造特殊插值多项式首先构造特殊插值多项式,)(niPxl , 1, 0)(,kikixlkiki ., 1 , 0,nki 克罗内克尔克罗内克尔( (Kronecker) )符号符号. .:,ki (2.1) 上一页上一页下一页下一页湘潭大学数学与计算科学学院5 , 1, 0)(,kikixlkiki ., 1 , 0,nki (2.1) (2.1) 所以所以 1)( iixl又由又由即即011( )()()()()iiinl xc xxxxxxxx1011()()()()iiiiiincxxxxxxxx解得解得)()()()()()()(11101110n

4、iiiiiiiniiixxxxxxxxxxxxxxxxxxxxxl 可以验证可以验证0( )( )nnjjjL xy lx 满足插值条件满足插值条件. .上一页上一页下一页下一页湘潭大学数学与计算科学学院6(2) (2) 唯一性唯一性设设n次多项式次多项式( )( )nnL xQx和和()()()0,1,2,niiniL xf xQxin( ):( )( ),nnnG xL xQxP令令()()()0,0,1,.ininiG xL xQxin则则均为插值问题的解均为插值问题的解, ,即即由高等代数基本知识知，由高等代数基本知识知，若一个若一个n次代数多项式至少次代数多项式至少存在存在n+1+1

5、个根，则它个根，则它一定恒为零一定恒为零. . ( )0,( )( ).nnG xL xQx故故即即唯一性得证唯一性得证. . 上一页上一页下一页下一页湘潭大学数学与计算科学学院7称称为为f(x)的的n次多项式插值的次多项式插值的 Lagrange 公式公式也称为也称为Lagrange 插值多项式插值多项式. . 0( )( )(2.5)nni iiL xy l x 称称为为n次多项式插值问题的次多项式插值问题的基函数基函数( (Lagrange 因子因子) )( )( )()( )niinixl xxxx其中其中0( )().nnjjxxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院

6、8例例 当当n=1时，线性插值公式时，线性插值公式11001()( )()xxL xyxx 0110()()xxyxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院9当当n=2时，抛物插值公式时，抛物插值公式12200102()()( )()()xxxxL xyxxxx 0211012()()()()xxxxyxxxx0122021()()()()xxxxyxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院1010010, 12111, 14412, 125例例1 1 已知已知线性插值和抛物插值公式求线性插值和抛物插值公式求的近似值的近似值. . 试分别用试分别用01121,14

7、4,xx0111,12,yy解解 （1 1）选取）选取利用线性插值公式，利用线性插值公式，011010110()()( )()()xxxxL xyyxxxx 1144( )11121144xL x 可得可得 12112,144121x 于是于是 1125(125)L 11.17391. 上一页上一页下一页下一页湘潭大学数学与计算科学学院11012100,121,144,xxx01210,11,12,yyy解解 （2 2）选取）选取利用抛物插值公式，利用抛物插值公式，可得可得 0212201010210120122021()()()()( )()()()()()() ()()xxxxxxxxL

8、xyyxxxxxxxxxxxxyxxxx 2(121)(144)( )10(100121) (100144)xxL x(100)(144)11(121100) (121144)xx(100)(121)12,(144100) (144121)xx于是于是 2125(125)L 11.18107. 上一页上一页下一页下一页湘潭大学数学与计算科学学院12注意：注意：12511.1803398 可见线性插值公式所得近似值有可见线性插值公式所得近似值有3 3位位有效数字有效数字 抛物插值公式所得近似值有抛物插值公式所得近似值有4 4位位有效数字有效数字 Lagrange插值公式的优缺点：插值公式的优缺点

9、：优点：形式简洁优点：形式简洁 便于理论分析和许多数值计算公式的推导便于理论分析和许多数值计算公式的推导缺点：没有承袭性缺点：没有承袭性 即当增加新的节点时即当增加新的节点时 所有所有Lagrange因子必须重新计算因子必须重新计算上一页上一页下一页下一页湘潭大学数学与计算科学学院13malagr.m用途：拉格朗日插值法求解格式：yy=malagr(x,y,xx)， x是节点向量， y是节点对应的函数值向量， xx是插值点(可以是多个)， yy返回插值结果拉格朗日插值法拉格朗日插值法Matlab程序程序 上一页上一页下一页下一页湘潭大学数学与计算科学学院14上一页上一页下一页下一页湘潭大学数学

10、与计算科学学院15三、三、 Newton插值公式插值公式 Lagrange 插值虽然易算，但若要增加一个节点时插值虽然易算，但若要增加一个节点时全部基函数全部基函数li(x)都需重新算过。都需重新算过。将将Ln(x)改写成改写成01()()nnc xxxx 的形式，希望每加一个节点时，的形式，希望每加一个节点时，只附加一项只附加一项上去即可。上去即可。? ? ? ? ?010201()()()cc xxcxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院1600( )().p xf x ( )f x首先考察首先考察的几种低次的几种低次Newton插值公式的建立过程插值公式的建立过程下面

11、分别考察一次和二次插值多项式情形下面分别考察一次和二次插值多项式情形. . 0 x的的零次插值多项式零次插值多项式显然显然关于节点关于节点01,x x1( ),p x(1) 关于节点关于节点的一次插值多项式的一次插值多项式根据承袭性的要求，可将其待定为根据承袭性的要求，可将其待定为 10( )( )( ),p xp xq x1,qP 1( )p x由由的定义知的定义知0()0,q x 且满足且满足故可令故可令 10( )().q xc xx上一页上一页下一页下一页湘潭大学数学与计算科学学院17利用利用111()(),p xf x 可求得可求得 10110()().f xf xcxx (2.9)

12、012,x x x2( ),px(2) 关于节点关于节点的二次插值多项式的二次插值多项式可将其待定为可将其待定为 21( )( )( ),p xp xq x2,qP 其中其中01()()0,q xq x 且满足且满足故可令故可令 201( )()().q xcxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院18120120()()(),p xf xc xx222()(),p xf x 利用利用以及以及可求得可求得 21222021()()()()f xp xcxxxx 201202021()()()()()f xf xc xxxxxx 102020102021()()()()()()

13、()f xf xf xf xxxxxxxxx 21201( )( )()()p xp xcxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院19102020102021()()()()()()()f xf xf xf xxxxxxxxx 12102002011201()()()()()()()()()f xf xf xf xf xxxxf xxxxxx 202110202101()()(1)()()()()xxf xf xxxxxxfxxfx 212110201210()()()()xxf xf xxxxxxxxfxf 上一页上一页下一页下一页湘潭大学数学与计算科学学院20102121

14、1020()()()(),f xf xf xf xxxxxxx (2.10)212110201210()()()()xxf xf xxxxxxxxfxf 上一页上一页下一页下一页湘潭大学数学与计算科学学院2101,ixxx按照上述规律，按照上述规律，( )f x关于节点关于节点( ),ip x的的i次插值多项式次插值多项式可以待定成可以待定成 1011( )( )()()(), iiiip xpxc xxxxxx1, .in (2.11)为了给出一般待定系数为了给出一般待定系数ic的计算公式，的计算公式，我们需要引入差商的概念我们需要引入差商的概念 上一页上一页下一页下一页湘潭大学数学与计算科

15、学学院22定义定义1 称称100110( )(),f xf xf x xxx为为 f (x)在在x0、x1点的点的一阶差商一阶差商. .120101220 ,f x xf x xf x x xxx称为函数称为函数f (x)在在x0、x1 、x2 点的点的二阶差商二阶差商. .差商的定义差商的定义一阶差商的差商一阶差商的差商上一页上一页下一页下一页湘潭大学数学与计算科学学院23一般地，一般地，n1阶差商的差商阶差商的差商11021010 , , , ,nnnnnnf xxxf xxxf x xxxx 称为称为f (x)在在x0 , x1 , , xn点的点的 n 阶差商阶差商。差商的计算步骤与结

16、果可列成差商表，如下差商的计算步骤与结果可列成差商表，如下上一页上一页下一页下一页湘潭大学数学与计算科学学院24xk函数值函数值一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商. x0 x1 x2 x3 . f (x0) f (x1) f (x2) f (x3) . f x0 , x1 f x1 , x2 f x2 , x3 . f x0, x1, x2 f x1, x2, x3 . f x0, x1, x2 , x3 .表表2-2上一页上一页下一页下一页湘潭大学数学与计算科学学院25010011( ) , ,()()()()nknkkkkkkknfxfx xxxxxxxxxx这一性质可以用数

17、学归纳法证明。例如这一性质可以用数学归纳法证明。例如性质性质1 1 差商可以表示为函数值的线性组合，即差商可以表示为函数值的线性组合，即差商的性质差商的性质: : 100101100110( )()()( ),f xf xf xf xf x xxxxxxx101012202, ,f x xf x xf x x xxx12101011002221()( )()()f xf xxf xf xxxxxxxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院26性质性质1 1表明差商与节点的表明差商与节点的排列次序排列次序无关无关，即，即 f x0 , x1 , x2 , ., xn=性质性质2

18、2 (对称性对称性)f x1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn , x0 20210111012102()()( )(f xf xxxf xf xxxxxxxxx012010210122120()( )()()()()()()()f xf xf xxxxxxxxxxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院27 性质性质3 3 若若f(x)在在a,b上存在上存在n阶导数阶导数, , 且节点且节点x0, ,x1 , xn a,b, ,则则至少存在至少存在一点一点 a, b 满足下式满足下式!)(,)(10nfxxxfnn 解解 f (8)(

19、x)=- -68 !, f 1,2, ,9=- -6, f (9)(x)=0, f 1,2, ,10=0.例例1 1 f (x)=- -6x8+7x5- -10, ,求求f 1,2, ,9及及f 1,2, ,10.上一页上一页下一页下一页湘潭大学数学与计算科学学院28Newton插值多项式插值多项式首先考察首先考察待定常数待定常数(1,2, )ic in 与与差商差商之间的关系之间的关系. .由由和和可知可知 1021211020()()()(),f xf xf xf xxxxxxx 21222021()()()()f xp xcxxxx (2.10)10110()().f xf xcxx (

20、2.9)上一页上一页下一页下一页湘潭大学数学与计算科学学院29101, cf x x 2012 ,cf x x x (2.14)对于一般的对于一般的(3,4, ),jcjn 利用归纳法可以证得利用归纳法可以证得 0,.jjcf xx (2.15)事实上事实上，由，由差商差商的定义可知：的定义可知：000( )(),)(,f xf xxf xxx001110,(), , ,f xf x xxfxxxxx012220011,() , ,f x x xxxff x x xx x x x 10001,() ,. ,nnnnf x xf x xxxxf x xxx 依次将后一式代入前一式，最后得：依次将

21、后一式代入前一式，最后得：上一页上一页下一页下一页湘潭大学数学与计算科学学院300010( )(),()f xf xf x xxx01011,()()(),nnf x xxxxxxxx 01201,()()f x x xxxxx 0101 ,()(),()nnf x x xxxxxxxx( )( ).nnxRNx0010( )(),()nNxf xf x xxx 01011,()()(),nnf x xxxxxxxx 其中：其中： 0101( ) ,()()().nnnR xf x x xxxxxxxx上一页上一页下一页下一页湘潭大学数学与计算科学学院3101,nx xx( )f x因此因此

22、关于节点关于节点的的n次插值多项式可以写成次插值多项式可以写成 0010( )(),()nNxf xf x xxx (2.16)称称(2.16)为为Newton插值公式插值公式，称为称为n次次Newton插值多项式。插值多项式。 ( )nNx相应的相应的01011,()()(),nnf x xxxxxxxx 容易验证容易验证 满足满足插值条件插值条件。( )nNx上一页上一页下一页下一页湘潭大学数学与计算科学学院32所以由插值多项式的所以由插值多项式的唯一性唯一性知知, , Ln(x) Nn(x)由于由于Newton插值多项式插值多项式Nn(x)与与Lagrange插值多项式插值多项式Ln(x

23、)只是只是Lagrange插值问题解的插值问题解的两种表示形式两种表示形式， 通过比较通过比较(2.5)和和(2.16)关于关于nx的系数可知的系数可知 00011(),.()()()()nknkkkkkkknf xf xxxxxxxxxx 这就证明了差商这就证明了差商性质性质1. . 上一页上一页下一页下一页湘潭大学数学与计算科学学院330010( )(),()nNxf xf x xxx 01011,()()(),nnf x xxxxxxxx 011100111()()()()()( )()()()()()niinniiiiiiiiinxxxxxxxxxxL xyxxxxxxxxxx 上一页

24、上一页下一页下一页湘潭大学数学与计算科学学院34xk f(xk)一阶差商一阶差商 二阶差商二阶差商三阶差商三阶差商 四阶差商四阶差商0.400.550.650.800.900.410750.578150.696750.888111.026521.116001.186001.275731.384100.280000.358930.433480.197330.213000.03134例例2 已知已知f(x)=shx的数表的数表,求二次牛顿插值多项式求二次牛顿插值多项式,并由并由 此计算此计算f(0.596)的近似值的近似值。 2( )0.410751.11600(0.40)N xx 解解 由上表可得过前三点的由上表可得过前三点的2次次Newton插值多项式插值多项式为为0.28000(0.40)(0.55)xx上一页上一页下一页下一页湘潭大学数学与计算科学学院35632010. 0)596. 0()596. 0(2 Nf又又0123,0.19733f x x xx 可得过前四点的可得过前四点的3次次Newton插值多项式插值多项式32( )( )0.19733(0.40)(0.55)(0.65)NxNxxxx故故3(0.596)(0.596)0.6319145fN故故2( )0.410751.11600(0.