插值法(拉格朗日插值).ppt

问题的提出 拉格朗日插值 牛顿插值 埃尔米特插值 曲线拟合的最小二乘法 第三章 插值法 /* Interpolation */ 1问题的提出 函数 y = f(x) 1） 解析式未知； 2）虽有解析式但表达式较复杂， 通过实验计算得到的一组数据，即在某个区间 a,b上给出一系列点的函数值 yi=f(xi)， x x0 x1 x2 xn y=f(x) y0 y1 y2 yn 3）列表函数 问题：无法求出不在表中的点的函数值，也不能 进一步研究函数的其他性质，如函数的积分和导 数等。因此需寻找 y = f(x)的近似函数 p(x),但要求 p(xi) = f(xi) 。 插值问题 已知精确函数 y = f(x) 在一系列节点 x0 xn 处测得函数值 y0 = f(x0), yn = f(xn)，由此构 造一个简单易算的近似函数 p(x) f(x)，满足 条件 p(xi) = f(xi) (i = 0, n)。这里的 p(x) 称 为 f(x) 的 插值函数 。最常用的插值函数是 ? 多项式 x0 x1 x2 x3 x4 x p(x) f(x) 1.1Taylor插值 函数 y = f(x)在点 x0处展开有 Taylor 多项式 : 200000 )(!2 )()()()( xxxfxxxfxfxp n n n xxn xf )(! )(. 00 )( 可见 : Pn(k)(x0)= f (k)(x0) k=0,1,n 因此 , Pn(x)在点 x0邻近会很好的逼近 f(x). Taylor展开方法就是一种插值方法 . 泰勒插值要求提供 f(x) 在点 x0处的各阶导数 ,这仅 仅适用于 f(x) 相当简单的情况 . 设函数 y = f(x)在区间 a,b上有定义，且给 出一系列点上的函数值 yi=f(xi) (i=0,1,2,n)， 求作 n次 多项式 pn(x) 使得 pn (xi)= yi (i=0,1,2,n) 函数 pn (x)为 f(x)的 插值函数 ；称 x0,x1, xn称为 插值节点 或简称节点。插值节点所界的区间 a,b 称为 插值区间 。 pn (xi)= yi 称为 插值条件 。 构造的 n次多项式可表示为 : Pn(x)= a0 + a1x + a2x2+ anxn 1.2 Lagrange插值 定理 (插值多项式的 存在唯一性 ) 满足 的 n 阶插值多项式是唯一存在的。 niyxP ii ,.,0,)( 证明： ( 利用 Vandermonde 行列式 论证 ) n n nnn n n n n yxaxaa yxaxaa yxaxaa . . . . 10 11110 00010 这是一个关于 a0 , a1 , a n 的 n+1元线性方程组 ,其系 数行列式 : 1 01 10 )(), . . .,( i j ji n i nn xxxxxV 由于 i j时 , xi xj ,因此 ,即方程组有 唯一解 . 0),.,( 10 nn xxxV 2 拉格朗日插值公式 n i y x P i i n , . , 0 , ) ( 求 n 次多项式 使得 n nn xaxaaxP 10)( 条件： 无重合节点，即 ji xx ji n = 1 已知 x0 , x1 ; y0 , y1 ，求 xaaxP 101 )( 使得 1 1 1 0 0 1 ) ( , ) ( y x P y x P 可见 P1(x) 是过 ( x0 , y0 ) 和 ( x1, y1 ) 两点的直线。 ) ( ) ( 0 0 1 0 1 0 1 x x x x y y y x P 1 0 1 x x x x 0 1 0 x x x x = y 0 + y1 l0(x) l1(x) 1 0 ) ( i i i y x l 称为 拉氏基函数 直线方程的两点式： 线性插值 1 01 0 0 10 1 1 )( yxx xxyxx xxxL l0(x) l1(x) 1 0 ) ( i i i y x l L1(x) 抛物插值 2 1202 10 1 2101 20 0 2010 21 2 )( )( )( )( )( )( )( y xxxx xxxxy xxxx xxxxy xxxx xxxx xL l0(x) l1(x) l2(x) n 1 li(x) 每个 li 有 n 个根 x0 xi xn n j j i j i n i i i x x C x x x x x x C x l 0 0 ) ( ) ).( ).( ( ) ( j i j i i i i x x C x l ) ( 1 1 ) ( n j ij ji j i xx xxxl 0 )( )()( n i iin yxlxL 0 )()( N次拉格朗日 插值多项式 与 有关，而与 无关 节点 f 希望找到 li(x)， i = 0, , n 使得 li(xj)= ；然后令 n i i i n y x l x P 0 ) ( ) ( ，则显然有 Pn(xi) = yi 。 0 1 ji ji n次多项式 插值余项 /* Remainder */ 设节点 )1( nf 在 a , b内存在 , 考察截断误差 )()()( xLxfxR nn , baCf nbxxxa n 10 ，且 f 满足条件 , 用简单的插值函数 L n(x)代替原复杂函数 f(x),其 精度取决于截断误差 ,即插值余项 . )()()()!1( )()( 210 )1( n n n xxxxxxxxn fxR 即 n i i n n xxn fxR 0 )1( )(!)1( )()( , ba其中 拉格朗日余项定理 注： 通常不能确定 , 而是估计 , x(a,b) 将 作为误差估计上限。 1)1( )( nn Mxf n i in xxn M 0 1 |)!1( 当 f(x) 为任一个次数 n 的 多项式 时， , 可知 ，即插值多项式对于次数 n 的 多项 式是 精确 的。 0)()1( xf n 0)( xR n 例： 已知 2 33s i n,214s i n,216s i n 分别利用 sin x 的 1次、 2次 Lagrange 插值计算 sin 50 并估计误差。 解： 0 x 1x 2x 18550 0 n = 1 分别利用 x0, x1 以及 x1, x2 计算 4,6 10 xx利用 216/4/ 6/214/6/ 4/)(1 xxxL 这里 ) 3,6(,s i n)(,s i n)( )2( xxxfxxf 而 )4)(6(!2 )()(,2 3s i n21 )2(1 xxfxR xx 00 76 2.0)185(01 31 9.0 1 R sin 50 = 0.7660444 ) 18 5 ( 50 sin 1 0 L 0.77614 外推 /* extrapolation */ 的实际误差 0.01001 3,4 21 xx 利用 sin 50 0.76008, 0 0 6 6 0.0 1850 0 5 3 8.0 1 R 内插 /* interpolation */ 的实际误差 0.00596 内插通常优于外推。选择 要计算的 x 所在的区间的 端点，插值效果较好。 n = 2 2 3 )( )( 2 1 )( )( 21)( )()( 4363 46 3464 36 3646 342 xxxxxxxL ) 18 5 ( 50 sin 2 0 L 0.76543 2 3c o s21;)3)(4)(6(!3 c o s)( 2 xx xxxxR 0 0 0 7 7.01850 0 0 4 4.0 2 R sin 50 = 0.7660444 2次插值的实际误差 0.00061 高次插值通常优于 低次插值 但绝对不是次数越 高就越好，嘿 嘿 i n i n j ij ji j n yxx xxxL )( )()( 0 0 拉格朗日插值多项式编程容易，只需双重循环 如果发现当前的插值方法不够精确，就要增 加插值点的个数，则拉格朗日插值基函数 li(x) 都将重新计算。 牛顿插值法将讨论该问题 。 例：已知数据表 x k 10 11 12 13 f(xk) 2.302 6 2.397 9 2.484 9 2.564 9 试用二次插值计算 f(11.75)(计算过程保留 4位小 数 ) 解：因为 11.75更接近 12， 故应取 11， 12， 13三点作二次 插值 先作插值基函数 已知 x0=11,y0=2.397 9， x1=12,y0=2.484 9 ， x2=13,y2=2.564 9 2 )13)(12( )( )()( 2010 210 xx xxxx xxxxxl 1 )13)(11( )( )()( 2101 20 1 xx xxxx xxxxxl 2 )12)(11( )( )()( 1202 102 xx xxxx xxxxxl 2(x)= 9484.21 )13)(11(9397.2 2 )13)(12( xxxx 9564.22 )12)(11( xx f(11.75) 2(11.75)= 9484.21 )135.11)(1175.11(9397.22 )1375.11)(1275.11( 8 2.4 639564.22 )1275.11)(1175.11( 例 已知 x=1,4,9的平方根值，用拉格朗日插值公式求 71/2 解： x0=1, x1=4, x2=9 f(x0)=1, f(x1)=2, f(x2)=3 L2(7) = (14)(19) (74)(79) * 1 + (41)(49) (71)(79) * 2 + (91)(94) (71)(74) * 3 = 2.7 (x0 x1)(x0 x2) (xx1)(xx2) f(x 0) + (x 1x0)(x1x2) (xx0)(xx2) f(x 1) + (x 2x0)(x2x1) (xx0)(xx1) f(x 2) L2(x) =