拉格朗日插值和逐次线性插值

1、2. 5 Hermite插值多项式插值多项式2. 4 Newton插值多项式插值多项式2. 3 逐次线性插值法逐次线性插值法2. 2 Lagrange插值多项式插值多项式2.1 引言与问题特例引言与问题特例第二章第二章 插值法插值法2. 6 分段低次插值分段低次插值2. 7 三次样条插值三次样条插值2.1 引言与问题特例引言与问题特例例例2.1例例2.2问题问题插值插值-定义定义2.12. 2 Lagrange插值多项式插值多项式例例2.1 在统计中会遇到概率积分在统计中会遇到概率积分xtdtexf022)(的计算。为便于应用，有概率积分表的计算。为便于应用，有概率积分表2-1x0.5200.

2、5210.5220.524f (x)0.537 900.538 760.539 620.540 48求求 f (0.52136)或或f (0.52218). ( 数据表中没有）。数据表中没有）。解法：解法：用插值法求。用插值法求。2.1 引言与问题特例引言与问题特例例例2.2 由化学实验得到某种物质浓度由化学实验得到某种物质浓度yi与时间与时间ti的关系如表的关系如表2-2.ti0. 0 0.51.01.52.0yi0. 0 0.190.260.290.31求其它时间的物质浓度。求其它时间的物质浓度。解法：解法： 建立时间与物质浓度的简单数学模型，建立时间与物质浓度的简单数学模型，或或用插值法

3、用插值法 。 求求y = f (x) 在在 a , b 上的近似曲线？上的近似曲线？问题：问题：基于未知函数或复杂函数的某些已知信息，基于未知函数或复杂函数的某些已知信息，如何构造这些函数的近似表达式如何构造这些函数的近似表达式?x0 x1x2x3x4 xf(x) (x)曲线曲线 ( x) 近似近似 f ( x) 从代数上看，看从代数上看，看 (x)满足以下代数条件满足以下代数条件 (xi) = yi i = 0, 1, 2, , n这就是所谓的插值这就是所谓的插值然后计算然后计算 (x)在在a,b 上其它点上其它点x 处的函数值作为处的函数值作为原来函数原来函数 f (x)在此点函数值的近似

4、值。在此点函数值的近似值。代数多项式、三角多项式、有理函数或样条函数代数多项式、三角多项式、有理函数或样条函数 (2.1)式称为式称为插值条件插值条件，x2 xn b 点上的值点上的值 y0, y1, , yn . 若存在一简单若存在一简单 函数函数 (x), 使得使得 (xi) = yi i = 0, 1, 2, , n (2.1) 定义定义2.1f ( x ) 称为称为被插值函数被插值函数，a , b 称为称为插值区间插值区间， 称为称为插值节点插值节点 ， 求求 ( x ) 的方法就是的方法就是插值法插值法。设函数设函数 f (x) 在在a , b上有定义，且已知在上有定义，且已知在 a

5、 x0 x1成立成立, ,则称则称 ( x ) 为为 f (x) 的的插值函数插值函数。nxxx,10 近似计算近似计算 f (x) 的值、零点、极的值、零点、极值点、导数、积分，值点、导数、积分，插值点在插值区间内的称为插值点在插值区间内的称为内插内插, 否则称否则称外插外插. x0 x1x2x3x4f(x) (x)曲线曲线 ( x) 近似近似 f ( x) 研究问题：研究问题：（1）满足插值条件的）满足插值条件的 ( x) 是否是否存在唯一存在唯一？（2）若满足插值条件的）若满足插值条件的 ( x) 存在，存在，如何构造如何构造 ( x)？（3）如何）如何估计估计用用 ( x)近似替代近似

6、替代 f ( x) 产生的产生的误差误差？2.2 Lagrange2.2 Lagrange插值多项式插值多项式2.2.1 2.2.1 多项式插值问题多项式插值问题2.2.2 Lagrange2.2.2 Lagrange插值插值2.2.3 Lagrange2.2.3 Lagrange插值余项插值余项问题插值多项式的存在唯一性问题插值多项式的存在唯一性定理定理2.1 线性（一次）插值线性（一次）插值例例2.3 n次次Lagrange 插值多项式插值多项式n=2n=1n=2例例2.2*Lagrange插值多项式的另一种形式插值多项式的另一种形式定理定理2.2定理定理2.3 Lagrange插值算法实

7、现插值算法实现练习练习1-32.3 逐次线性插值法逐次线性插值法例例2.4算例算例1-22.2 Lagrange2.2 Lagrange插值多项式插值多项式2.2.1 2.2.1 多项式插值问题多项式插值问题用代数多项式作为插值函数的插值法称为用代数多项式作为插值函数的插值法称为多项式插值法。多项式插值法。可设可设 ( x ) = a0 + a1 x + a2x 2+ + ai x i + , 问题：问题：插值多项式插值多项式 ( x )是几次多项式？系数是几次多项式？系数ai=？插值多项式插值多项式 ( x )唯一吗？唯一吗？ 可设可设 ( x ) = a0 + a1 x + + an x

8、n要求插值多项式要求插值多项式 (x)，可以通过求，可以通过求n+1个方程的解个方程的解:naaa10得到。但这样做不但计算复杂，得到。但这样做不但计算复杂，而且难于得到而且难于得到 n(x)的简单表达式。的简单表达式。 确定多项式确定多项式 ( x )的次数的次数方法：待定系数法方法：待定系数法结论：结论：n+1个插值节点产生的插值多项式的次数不个插值节点产生的插值多项式的次数不超过超过n次次问题插值多项式的存在唯一性问题插值多项式的存在唯一性 设设 n( x )是是 f (x) 的插值多项式，的插值多项式，Hn表示次数不超过表示次数不超过n 的所有多项的所有多项且且 n( x ) Hn .

9、称插值多项式存在且唯一，就是指在称插值多项式存在且唯一，就是指在由由(2.1)可得可得 nnnnnnnnnyxaxaayxaxaayxaxaa101111000010(2.2) 方程组方程组(2.2)有唯一解有唯一解插值多项式的唯一性插值多项式的唯一性nnnnnnnnxxxxxxxxxxxxV21211020010111),( nijjixx0)(0 (xixj)定理定理2.1 满足条件满足条件 (2.1)的插值多项式存在且唯一。的插值多项式存在且唯一。范德蒙行列式范德蒙行列式a0, a1, a2, , an存在唯一存在唯一 (xi) = yi i = 0, 1, 2, , nHn 中有且仅有

10、一个中有且仅有一个 n( x ) 满足插值条件满足插值条件(2.1)式。式。式的集合。式的集合。n+1个节点互异当当n=1n=1时，要构造通过两点时，要构造通过两点 ( (x0 , y0 ) )和和( (x1, y1 )的不超过的不超过1 1次的多项式次的多项式 1(x)( (后面记后面记作作L1(x) ) )，使得，使得100111(),()L xy L xy2.2.2Lagrange插值插值y 0 x y = f (x)y = L1(x)x0 x1 y 0 x y = f (x)y = L1(x)x0 x1 称为线性（一次）插值称为线性（一次）插值100111( ),),)yL xxyx

11、yL x的几何意义就是通过两点（与（的直线，如图所示， （ ）的表达式可由几何意义直接给出：（两点式）（两点式）1010010( )()yyL xyxxxx（点斜式）（点斜式）011011010( )xxxxL xyyxxxx010110101)(xxxxyxxxxyxL 1010010( )()yyyLxxxxx或或10100110( ),( )xxxxl xl xxxxxL1(x)是两个线性函数是两个线性函数的线性组合的线性组合称为节点称为节点x0 0, ,x1 1上上线性插值基函数线性插值基函数11 10 0( )( )( )yyL xl xl x- 线性线性Lagrange插值多项式形

12、式插值多项式形式(2.3) y10 x0 x1 x l0(x) l1(x) 节点上的节点上的线性线性 插值基函数：插值基函数：满足满足 y10 x0 x1 x11 100( )( )( )yyL xl xl x10100110( ),( )xxxxl xl xxxxxx0 x1l0(x)10l1(x)01例例2.32.3 已知已知 , , ,10100 11121 115y解解: : 这里这里x0 0=100=100，y0 0=10=10，x1 1=121=121，y1 1=11, =11, 利用线利用线性插值性插值 1121100( )1011100121121100 xxL x1115(1

13、15)10.714yL利用线性插值求利用线性插值求1011(121)(100)2121xx y y=L2(x) y0 y1 y1 y=f(x) O x0 x1 x2 x 01222200112222,( ),) (0,1,2),( ),).( ,),(,)( ).iinx x xL xL xyiyL xxyx yxyL x下面讨论的情形。假定插值节点为要求二次插值多项式它满足（几何上就是通过三点（的抛物线。为了求出的表达式，可采用基函数方法 先求先求 插值基函数插值基函数 l 0(x), l1 (x), l 2(x) ,它们满足它们满足 (1) 都是二次函数；都是二次函数； (2) 在节点满足

14、在节点满足x0 x1x2l0(x)100l1(x)010l2(x)001y 1 0 xy 1 0 xy 1 0 xx0 x1 x2 先求先求 l0(x):012( )()(),l xA x xx x则可令待定系数待定系数x0 x1 x2x0 x1 x2 0200012()()( )()()x xx xl xxxxx-=-0211102()()( )()()xxxxl xxxxx-=-0122201()()( )()()x xx xl xxxxx-=-0102( )()0l xl x由由l0(x)满足的两个条件满足的两个条件类似地类似地,可得可得知知l0(x)中含有两个因子中含有两个因子(x-x

15、1 )( x-x2)，且是二次的，且是二次的00()1,l x再由再由l0(x)满足的条件满足的条件00121()()Axxxx可得即得即得所以有所以有 L2(x) = y0 l0 0(x) + y1 l1 (x) + y2 l2(x)例例2.2* 已知已知 , , ,10100 11121 115y解解: : 这里这里x0 0=100=100，y0 0=10=10，x1 1=121=121，y1 1=11, =11, x2 2=144=144，y2 2=12=12，利用抛物线插值公式，利用抛物线插值公式 利用抛物线插值求利用抛物线插值求144122115(121)(144)(100)(144

16、)(115)1011(100 121)(100 144)(121 100)(121 144)(100)(121)1210.72275(144 100)(144 121)xxxxxLxxn次次Lagrange 插值多项式插值多项式求通过求通过n +1个节点的个节点的n 次插值多项式次插值多项式Ln(x)：先求插值基函数先求插值基函数然后构造插值多项式然后构造插值多项式设设Ln(x)=满足插值条件：满足插值条件：L n ( xj ) = y j , j = 0, 1, , n定义定义2.2 若若n 次多项式次多项式 lk ( x ) (k = 0,1, ,n ) 在各节点在各节点,0,1)(iki

17、kxlkiiki, k = 0, 1 , , n (2.4)10 nxxx上满足条件上满足条件 则称这则称这n +1个个n 次多项式为这次多项式为这n +1个节点上的个节点上的n 次插次插值基函数值基函数。0 01 1( )( )( )n ny lxy l xy lx先求先求 插值基函数插值基函数)()( )()()()( )()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl ， k = 0, 1 , n ., )()( )()()(110nkkkxxxxxxxxAxl 令令k = 0, 1 , , n .)()( )()(1110nkkkkkkxxxxxxxxA

18、 得得, 1)( kkxl由由11 100( )( )( )yyL xl xl xL2(x) = y0 l0(x) + y1 l1(x) + y2 l2(x)（类似于前面讨论（类似于前面讨论n n =1, 2 =1, 2 时的情形）时的情形）(2.5)再构造再构造插值多项式插值多项式 （Ln(x)是是n+1个插值基函数的线性组合）个插值基函数的线性组合） nkkknxlxfxL0)()( ）定理定理2.2（Lagrange）插值多项式插值多项式, ),(),., 1, 0( ) )(,()(jixxnixfxxfyjiii 当当函函数数表表设设的的插插值值多多项项式式为为，则则满满足足插插值值

19、条条件件).1 , 0()()(nixfxLiin nkkknxlxfxL0)()( ）),.1, 0()(0nkxxxxxlnkjjjkjk 其其中中通常次数通常次数=n , 但特殊情形次数可但特殊情形次数可 x=0.4，0.5,0.7，0.8; y=-0.916291,-0.693147,-0.356675,-0.223144; lagrange(x,y,0.6)ans = -0.509 975 （精确解-0.510 826)11( )()nnjkkjkjjkxxy xyxx算例算例2给出函数为给出函数为f(x)=1/(1+x2) ，它在区间，它在区间-5，5上各导数存上各导数存在，但是在

20、此区间上取在，但是在此区间上取n个节点构造的个节点构造的Lagrange插值多项式插值多项式在全区间内并非都收敛的，而且分散得很厉害在全区间内并非都收敛的，而且分散得很厉害 。 x=-5:1:5; y=1./(1+x.2); x0=-5:0.1:5; y0=lagrange(x,y,x0); y1=1./(1+x0.2);绘制图形 plot(x0,y0,-r)插值曲线 hold on plot(x0,y1, -b)原曲线v为解决Rung问题，引入分段插值。 LagrangeLagrange插值插值采用插值基函数的线性组采用插值基函数的线性组合来构造插值多项式合来构造插值多项式含义直观含义直观形

21、式对称形式对称优点：优点：缺点：缺点：计算量大计算量大0120121,2,4,()8,()1,()5xxxf xf xf x求二次插值多项式。求二次插值多项式。 22(2)(4)(1)(4)(1)(2)( )815(12)(14)(2 1)(24)(4 1)(42)31621xxxxxxL xxx解解 按按Lagrange方法，有：方法，有：练习练习1 练习练习2 给定数据表给定数据表 xi 0 1 2 3 yi 0 1 5 14求三次求三次Lagrange插值多项式插值多项式L3(x).123)2)(1(14)1(12)3)(1(5)2()1(1)3)(2(10 xxxxxxxxx33012

22、33,( )0( ) 1( )5( ) 14( )nL xL xlxl xlxl x ：取由 ( )公式得解解 ).12)(1(616)132( 2 xxxxxx练习练习3 要制作三角函数要制作三角函数sin sin x的值表，已知表值有四位小数，的值表，已知表值有四位小数，要求用线性插值引起的截断误差不超过要求用线性插值引起的截断误差不超过表值的舍入误差表值的舍入误差，试，试确定其最大允许的步长。确定其最大允许的步长。解解 f(x)=sin x, 设设xi, xi为任意两个插值节点，最大允许步为任意两个插值节点，最大允许步长记为长记为 h = hi = xi xi，111111121124(

23、 )sin( )()()()()2!211()()()()22221()(),88110 ,0.02.82iiiiiiiiiiiiiiiifR xxxxxxxxxxxxxxxxxxxhxxxxhh2.3 逐次线性插值法逐次线性插值法 在许多情况下，当函数的高阶导数未知时，直接用插值余项公式在许多情况下，当函数的高阶导数未知时，直接用插值余项公式（2.102.10）来估计误差是困难的。下面以线性插值为例，介绍另一种估计）来估计误差是困难的。下面以线性插值为例，介绍另一种估计误差的方法。误差的方法。0120111221101101*1212212,()(0,1,2),( ),2.101()()()

24、.,21()()().,2ixxxxf xixxyf xyx xyyyLfxxxxxxyLfxxxxx x设且已知若将用两点作线性插值求得的近似值记为用两点作线性插值的求得 的近似值记为.则由余项公式（）有：02*11120( ),1 ( )()()2fxx xLLfxxxx假设在区间内变化不大，将上面两式相减即得近似：即可写成*111201( )()2()LLfxxxx*111002*111220( )( ) ( )()( )( ) *( )()L xL xR xxxxxL xL xRxxxxx由此可得此两式分别给出了此两式分别给出了L1(x)和和L1(x）作近作近似计算时的实用误似计算时的

25、实用误差估计式。而不需差估计式。而不需要计算高阶导数，要计算高阶导数，也不用顾忌插值区也不用顾忌插值区间上高阶导数的界。间上高阶导数的界。已知已知 f(0)=2，f(1)=3, f(2)=12利用利用Lagrange插值计算未知函数插值计算未知函数y=f (x)在在x=1.2078处处的函数值的函数值f (1.2078)，并估计误差，并估计误差.解：在区间解：在区间0,1上的上的1次次Lagrange插值多项式为插值多项式为110( )230 11 0 xxL x在区间在区间1,2上的上的1次次Lagrange插值多项式为插值多项式为*121( )3121 22 1xxL x例例2.5而而x=

26、1.20781,2*1(1.2078)(1.2078)4.8702fL*111(1.2078)(1.2078)*(1.2078)(1.20782)20 0.658 476 64LLR 基于以上分析，为更好的近似计算基于以上分析，为更好的近似计算f (x*)，可以，可以考虑把考虑把 ，即，即 *11( )( )L xR x*11111220( )( )()( )( )( )()L xL xf xL xR xL xxxxx2次的次的*11(1.2078)(1.2078)*(1.2078)4.87020.658 476 64 4.211 723 36fLR与利用抛物插值得到的近似值一致( )nLag

27、rangeLx用插值多项式计算函数近似值，如果精度不满足要求就需增加插值节点，原来算出的数据均不能利用了，必须重新计算， 上面的例题可以克服这一缺点，即使用逐次上面的例题可以克服这一缺点，即使用逐次线性插值方法求得高次插值。线性插值方法求得高次插值。2.2.3Aitken 逐次线性插值法逐次线性插值法0 ( ), ( ),0,1,2,.,( )( ),.iif xf xy inf xxf x对未知函数或复杂函数假设已知如下信息问题是利用以上信息计算在任何一点 处的函数值且近似误差不超过上限 0,1010011100,100100,202200,20020(1):1Lagrange, ;:1La

28、grange Ixxxxf xxf xf xf xIxf xxxxxIxxxf xf xIxf xxxxx计算：以 ， 为节点的 次插值公式，实际上是过，点的直线，采用点斜式计算：以 ， 为节点的 次插值公式,同理有计算时应尽量多地利用靠近计算时应尽量多地利用靠近x的节点信息，即先对所有节点重的节点信息，即先对所有节点重新排序，与新排序，与x接近的点排在前面，接下来计算接近的点排在前面，接下来计算f (x)的近似值。的近似值。计算过程如下计算过程如下 0,10,20,10,1,21120,1,200,1 20,10,1 20,10,20,1 20,11120,1 2, ,( )( )IxIxIxRxxxxRIxIxRxIxIxIxIxxxxxf xIxf x，（2）估计的误差为 若|停止计算.记即则得的近似值43210 xxxxx4433221100)()()()()(IxfIxfIxfIxfIxf0,10,20,1,20,30,1,30,1,2,30,40,1,40.1.2.40,1,2,3,4 IIIIIIIIII4321 0 xxxxxxxxxx 从表上看每增加一个节点就计算一行，斜线上是