第四章插值 Interpolation @当精确函数y=)非常复杂或未知时,在 系列节点x…,x处测得函数值y=八x), yn=xn),由此构造一个简单易算的近似函 数g(x)≈f(x),满足条件g(x)=fx)(=0, n)。这里的g(x)称为八x)的插值函数。最常 用的插值函数是多项式 g(x)≈f(x)
第四章 插值 /* Interpolation */ 当精确函数 y = f(x) 非常复杂或未知时，在一 系列节点 x0 … xn 处测得函数值 y0 = f(x0 ), … yn = f(xn )，由此构造一个简单易算的近似函 数 g(x) f(x)，满足条件g(xi ) = f(xi ) (i = 0, … n)。这里的 g(x) 称为f(x) 的插值函数。最常 用的插值函数是多项式 …? x0 x1 x2 x x3 x4 g(x) f(x)
§1拉格朗日多项式 / Lagrange Polynomial 求n次多项式P( x)=a0+a1x+…+anxn 使得 Pn(x;)=y,i=0. 条件:无重合节点,即i≠jx≠x n 称为拉氏基函数 I* Lagrange BasIs*,a 满足条件lx)=an/ Kronecker Delta 可贴r1U烂心x~y 1两点的直线。 P1(x)=y+ (x-x0) xxi X" 十 X1- 1=21(x)y lo(x)
§1 拉格朗日多项式 /* Lagrange Polynomial */ Pn ( xi ) = yi , i = 0, ... , n 求 n 次多项式 使得 n Pn (x) = a0 + a1 x ++ an x 条件：无重合节点，即 i j xi x j n = 1 已知 x0 , x1 ; y0 , y1 ，求 P1 (x) = a0 + a1 x 使得 1 0 0 1 1 1 P ( x ) = y , P ( x ) = y 可见 P1 (x) 是过 ( x0 , y0 ) 和 ( x1 , y1 ) 两点的直线。 ( ) ( ) 0 1 0 1 0 1 0 x x x x y y P x y - - - = + 0 1 1 x x x x - - 1 0 0 x x x x - - = y0 + y1 l0 (x) l1 (x) = = 1 0 ( ) i i x yi l 称为拉氏基函数 /* Lagrange Basis */， 满足条件 l i (xj )=ij /* Kronecker Delta */
n≥1希里找到(x),i=0,…,n使得(x)=9;然后令 P2(x)=2l(x),则显然有Px)=y1 与节点有关,而与∫无关 agrange Polynomial l(x)= ix (x x x)mD(x)=∑1(x)
n 1 希望找到l i (x)，i = 0, …, n 使得 l i (xj )=ij ；然后令 = = n i n i i P x l x y 0 ( ) ( ) ，则显然有Pn (xi ) = yi 。 l i (x) 每个 l i 有 n 个根 x0 … xi … xn = = - - - = - n j j i li x Ci x x x xi x xn Ci x xj 0 ( ) ( 0 )...( )...( ) ( ) - = = j i i j i i i x x l x C ( ) 1 ( ) 1 = - - = n j j i i j j i x x x x l x 0 ( ) ( ) ( ) = = n i n i i L x l x y 0 ( ) ( ) Lagrange Polynomial 与节点 有关，而与 f 无关
定理(睢性满是P()=1,1=-,m的n阶插益 项式是唯一存在的。 证明:(p105-106利用 Vandermonde行列式论证) 反证:若不唯一,则除了Ln(x)外还有另一n阶多项 式Pn(x)满足P(x) 考察Q(x)=P(x)-L(x),则Qn的阶数(n 而Q有+1个不同的根x0…x 注:若不将多项式次数限制为n,则插值多项式不唯一 例如P(x)=L2(x)+p(x)(x-x)也是一个插值 多项式,其中p(x)可以是任意多项式
定理 (唯一性) 满足 的 n 阶插值多 项式是唯一存在的。 P(xi ) = yi , i = 0, ... , n 证明： ( p.105-106 利用Vandermonde 行列式论证) 反证：若不唯一，则除了Ln (x) 外还有另一 n 阶多项 式 Pn (x) 满足 Pn (xi ) = yi 。 考察 Qn (x) = Pn (x)- Ln (x) , 则 Qn 的阶数 n 而 Qn 有 n + 1 个不同的根 x0 … xn 注：若不将多项式次数限制为 n ，则插值多项式不唯一。 例如 也是一个插值 多项式，其中 可以是任意多项式。 = = + - n i P x Ln x p x x xi 0 ( ) ( ) ( ) ( ) p(x)
>插值余项/ Remainder? 设节点a≤x<x1<…<xn≤b,且f满足条件∫∈C"la, 在a,b内存在考察截断误差R(x)=f(x)-Ln(x) Rn(x)至少有m+1个根→R(x)=K(x)I(x-x) 注意这里是对t求导3()=Rn(t)-K(x)I(t-x) (x)有m+2个不同的根x….nx今p+(4)=0,5∈(a,b ft(5x)-Lm(5、)-(x)(n+1)!=Rm(5x)-k(x)(m+1! (n+1) ft(s (x) R, (x)= (n+1) (n+1)! (x-x;)
➢ 插值余项 /* Remainder */ 设节点 (n+1) f 在[a , b]内存在, 考察截断误差 R (x) f (x) L (x) n = - n f C [a,b] n a x x x b 0 1 n ，且 f 满足条件 , Rolle’s Theorem: 若 充分光滑， ，则 存在 使得 。 ( x) (x0 ) =(x1 ) = 0 ( , ) x0 x1 ( ) = 0 推广：若 (x0 ) =(x1 ) =(x2 ) = 0 ( , ), ( , ) 0 x0 x1 1 x1 x2 使得 ( 0 ) =( 1 ) = 0 ( , ) 0 1 使得 ( ) = 0 (x0 ) ==(xn ) = 0 存在 (a,b) 使得 ( ) 0 ( ) = n Rn (x) 至少有 n+1个根 = = - n i Rn x K x x xi 0 ( ) ( ) ( ) 任意固定 x xi (i = 0, …, n), 考察 = = - - n i xi t Rn t K x t 0 ( ) ( ) ( ) ( ) (x)有 n+2 个不同的根 x0 … xn x ( ) 0, ( , ) ( 1) x x a b n = + ( ) ( ) ( 1) ! ( 1) - + + R x K x n n n 注意这里是对 t 求导 - - + = + + ( ) ( ) ( )( 1) ! ( 1) ( 1) f L x K x n n x n n ( 1)! ( ) ( ) ( 1) + = + n f K x x n = + - + = n i i x n n x x n f R x 0 ( 1) ( ) ( 1)! ( ) ( )
注:⑦通常不能确定5,而是估计/(x)sMm, VxE(a,b) 将x-x|作为误差估计上限 当f(x)为任一个次数≤n的多项式时,f+)(x)≡0, 可知Rn(x)≡0,即插值多项式对于次数≤n的多项式 是精确的。 Quiz:给定x=i+1,i=0,1,2,3,4,5.下面哪个是lx)的图像?
注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。 1 ( 1) ( ) + + n f n x M = + - + n i i n x x n M 0 1 | | ( 1)! 当 f(x) 为任一个次数 n 的多项式时， , 可知 ，即插值多项式对于次数 n 的多项式 是精确的。 ( ) 0 ( 1) + f x n Rn (x) 0 Quiz:给定 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 A B C ✓
例:已知sm=2,4=23 兀√3 分别利用如mx的次、2次M图r插值计算sns 并估计误差。 50 解:n=1分别利用x,x1以及x1,x2计算 中利用xn=z,x1= 1(x)=x-z/4 丌/6 6 丌/6-丌/42丌/4-/6"√2 內插通常优于外推。选择 P()=smn5,5e(《3) 要计算的x所在的区间的 端点,插值效果较好。 sin50°=0.7660444. 外推/ extrapolation的差≈-0.01001 中利用x=,x2=sin50°0 38,0.005388/5z)∠0.0660 18 插/ interpolation+的实际误差≈0.00596
例：已知 2 3 3 , sin 2 1 4 , sin 2 1 6 sin = = = 分别利用 sin x 的1次、2次 Lagrange 插值计算 sin 50 并估计误差。 解： 0 x 1 x x2 18 5 500 = n = 1 分别利用x0 , x1 以及 x1 , x2 计算 4 , 6 0 1 利用 x = x = 2 1 / 4 / 6 / 6 2 1 / 6 / 4 / 4 ( ) 1 - - + - - = x x L x 这里 ) 3 , 6 ( ) sin , ( ) sin , ( (2) f x = x f x = - x x 而 ) 4 )( 6 ( 2 ! ( ) , ( ) 2 3 sin 2 1 (2) 1 = x - x - f R x x x ) 0.00762 18 5 0.01319 ( - 1 - R sin 50 = 0.7660444… ) 18 5 sin 50 (1 0 L 0.77614 外推 /* extrapolation */ 的实际误差 -0.01001 3 , 4 1 2 利用 x = x = sin 50 0.76008, 0.00660 18 ~ 5 0.00538 1 R 内插 /* interpolation */ 的实际误差 0.00596 内插通常优于外推。选择 要计算的 x 所在的区间的 端点，插值效果较好
2D2(x) (x一4)x-3 (x-5)(x- x-5)(x 3 -十 (一)(否一3)2(牙-)( √2(3-z)ξ- sin50≈L,(Sz 18 )≈0.76543 - cOS R2(x) 3 (x-( S coSE<V3 2 →0.0004<R2|5z<0.007 sin50°=0.7660444. 18 2次插值的实际误差≈000061 高次插值通常优于 低次插值 但绝对不是次数越 高就越好,嘿 嘿
n = 2 2 3 ( )( ) ( )( ) 2 1 ( )( ) ( )( ) 2 1 ( )( ) ( )( ) ( ) 3 6 3 4 6 4 4 6 4 3 6 3 6 4 6 3 4 3 2 - - - - + - - - - + - - - - = x x x x x x L x ) 18 5 sin 50 (2 0 L 0.76543 2 3 cos 2 1 ); 3 )( 4 )( 6 ( 3 ! cos ( ) 2 - - - - = x x R x x x x 0.00077 18 5 0.00044 2 R sin 50 = 0.7660444… 2次插值的实际误差 0.00061 高次插值通常优于 低次插值 但绝对不是次数越 高就越好，嘿 嘿……
§2牛顿插值/ Newton' iNterpolation Lng插值虽然易算,但若要增加一个节点时N 全部基函数(x)都需重新算过。 将Ln(x)改写成a+a(x-x0)+a2(x-xx-x)+ +an(x-x)(x-xn-1)的形式,希望每加一个节点时, 只附加一项上去即可。 差商(亦称均差)/ divided difference 1阶差商/the1st 几x;,x f(x)-f(x,) Ci-xi (≠,x≠x) divided difference of f w.r.t.x: andx.*/ fx;,;l-fr;, xkI fxi,x;, xkI ≠k)2阶差商
§2 牛顿插值 /* Newton’s Interpolation */ Lagrange 插值虽然易算，但若要增加一个节点时， 全部基函数 l i (x) 都需重新算过。 将 Ln (x) 改写成 ( ) ( )( ) ... a0 + a1 x - x0 + a2 x - x0 x - x1 + ( )...( ) + n - 0 - n-1 a x x x x 的形式，希望每加一个节点时， 只附加一项上去即可。 ? ? ? ? ➢ 差商(亦称均差) /* divided difference */ ( , ) ( ) ( ) [ , ] i j i j i j i j i j x x x x f x f x f x x - - = 1阶差商 /* the 1st divided difference of f w.r.t. xi and xj */ ( ) [ , ] [ , ] [ , , ] i k x x f x x f x x f x x x i k i j j k i j k - - = 2阶差商
(k+1)阶差商 ∫Lx ∫x0,x1,…,xk]-∫[x1,…,xk,xk+1 09··9~k+1 0=xk+1 ∫Lx0,…,xk-1,xkl-f{x0, k-19k+1 Ekk+ 事实上几xn,,x1=∑(x) i=00k+1 (x;) 其中o1(x)=∏(x-x),∞1(x)=∏(x-x) 差商的值与x;的顺序无关!
1 0 1 0 1 1 0 1 0 1 1 1 0 1 [ , ... , , ] [ , ... , , ] [ , , ... , ] [ , ... , , ] [ , ... , ] + - - + + + + - - = - - = k k k k k k k k k k k x x f x x x f x x x x x f x x x f x x x f x x (k+1)阶差商： = + = k i k i i k x f x f x x 0 1 0 ( ) ( ) [ , ... , ] 事实上 其中 ( ) ( ) , 0 1 = + = - k i k i x x x = + = - k j i j k xi xi x j 0 1 ( ) ( ) Warning: my head is exploding… What is the point of this formula? 差商的值与 xi 的顺序无关！