第六章插值/ nterpolation 当精确函数y=x)非常复杂或未知时,在 系列节点x…xn处测得函数值y=∫(xo), Jn=fxn),由此构造一个简单易算的近似函 数g(x)≈fx),满足条件g(x)=(x)(=0, n)。这里的g(x)称为f(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)=a+a1x+…+anx"使得 条件:无重合节点,即氵≠jx1≠x 称为拉氏基函数/ Lagrange Basis 得 满足条件l(x)=5 Kronecker Delta * 可见ru m两点的直线。 P1(x)=y0+ yIn (x-x0) X-x r- l()y 0
§1 拉格朗日多项式 /* Lagrange Polynomial */ Pn ( xi ) = yi , i = 0, ... , n 求 n 次多项式 Pn (x) = a0 a1 x an x n 使得 条件：无重合节点，即 i j xi x j n = 1 已知 x0 , x1 ; y0 , y1，求 P x a a x 1 0 1 ( ) = 使得 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 */， 满足条件 li(xj)=ij /* Kronecker Delta */
8 1 Lagrange Polynomial The mathematician S had to move to a new place His wife didnt trust him very much, so when they stood down on the street with all their things she asked him to watch their ten trunks, while she got a taxi. Some minutes later she returned. Said the husband: "I thought you said there were ten trunks, but Ive only counted to nine The wife said: "No, they're TEN! But i have counted them :0.1.2 n21希望找到(x),=0,…,n使得();然后令 P(x)=∑l(x)y,则显然有Pn(x)=y2 l(x)每△ ▲ 与节点有关,而与∫无关 Lagrange Polynomial (x2-x;) x-xi (x-x;) (x)=∑l(x)y
The mathematician S. had to move to a new place. His wife didn't trust him very much, so when they stood down on the street with all their things, she asked him to watch their ten trunks, while she got a taxi. Some minutes later she returned. Said the husband: "I thought you said there were ten trunks, but I've only counted to nine!" The wife said: "No, they're TEN!" "But I have counted them: 0, 1, 2, ..." §1 Lagrange Polynomial n 1 希望找到li(x)，i = 0, …, n 使得 li(xj)=ij ；然后令 = = n i n i i P x l x y 0 ( ) ( ) ，则显然有Pn (xi) = yi 。 li(x) 每个 li有 n 个根 x0 … xi … xn = = - - - = - n j j i i x Ci x x x xi x xn Ci x xj l 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 无关
8 1 Lagrange Polynomial 定理{(唯-性)满是P(x)=,1=0,m的m阶插值多 项式是唯一存在的。 证明:(p105-106利用 Vandermonde行列式论证) 反证:若不唯一,则除了L(x)外还有另一n阶多项 式Pn(x)满足Pn(x)=y 考察Q(x)=P(x)-Ln(x),则Qn的阶数n 而Qn有+1个不同的根x0…,xn 注:若不将多项式次数限制为n,则插值多项式不唯 例如P(x)=Ln(x)+p(x(x-x)也是一个插值 多项式,其中p(x)可以是任意多项式
§1 Lagrange Polynomial 定理 (唯一性) 满足 的 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 n i P x L x p x x x 0 ( ) ( ) ( ) ( ) p( x)
8 1 Lagrange Polynomial >插值余项/ Remainder 设节点a≤x<x<…<x≤b,且f满足条件∫eCn列l, 在a,b内存在考察截断误差R(x)=()-L) Rn(x)至少有+1个根→→R(x)=K(x)I(x-x) 注意这里是对t求导叫()=(0-()(=x) i=0 g(x)有+2个不同的根x…xnx今p"(5)=0,5 ∈(a (1(5x)-+(5)-K(x)(n+1)!=R(5)-k(x)(m+1! (n+1) ( K(x)= ( r,(x)= wIS ITe-x,) (n+1)! (n+1) i=0
§1 Lagrange Polynomial 插值余项 /* Remainder */ 设节点 (n1) 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) ( ) ( ) 0 x0 = x1 = ( , ) 0 1 x x ( ) = 0 推广：若(x0 ) =(x1 ) =(x2 ) = 0 ( , ), ( , ) 0 0 1 1 1 2 x x x x 使得 ( ) ( ) 0 0 = 1 = ( , ) 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) a b x x 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)! ( ) ( )
8 1 Lagrange Polynomial 注:一通常不能确定娠,而是估计/+"(x)sMn,Vxe(ab) 将(+1Ix-x1作为误差估计上限 可知R(x)=0,即插值多项式对于次数xn的多0, 当f(x)为任一个次数≤n的多项式时,f(+(x) 式是精确的。 Quiz:给定x=i+1,i=0,1,2,3,4,5.下面哪个是4x)的图像? B 0 456 0
§1 Lagrange Polynomial 注： 通常不能确定 x , 而是估计 , x(a,b) 将 作为误差估计上限。 1 ( 1) ( ) n n f 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
8 1 Lagrange Polynomial 例:已知sinz= 62,Snz=1 令,Sinz=√3 分别利用sinx的1次、2次 Lagrange插值计算sin50° 并估计误差。 5兀 50 解:n=1分别利用xx1以及x,x2计算 中利用xn=x,x1= x-z/4×1+x-/6x L1(x)=16-x/42x/4-x/6√2 内插通常优于外推。选择 2(4)=-sinl,5 6 要计算的x所在的区间的 端点,插值效果较好。 辅sin50°=07660444 外推/ extrapolation"的 差≈-001001 中利用x1=,x2=互sim5090),0.0081()0.060 内插/ interpolation+的实际误差≈0.00596
§1 Lagrange Polynomial 例：已知 2 3 3 , sin 2 1 4 , sin 2 1 6 sin = = = 分别利用 sin x 的1次、2次 Lagrange 插值计算 sin 50 并估计误差。 解： x0 1 x 2 x 18 5 50 0 = 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 所在的区间的 端点，插值效果较好
8 1 Lagrange Polynomial n=2 (x-)(x-3 14(x-5)(x-5) lx x一 L2(x) -产- (一)(一3)2(-5)(一3)"√2(3一5)(ξ一ξ)"2 sin50≈L2(2)≈0.76543 18 R2(x)= cos 5x(6 3! )x-4(x-3)2 <cos 5.<13 0.00044<R2 5元|<0.00077 sin50°=0.7660444. 18 2次插值的实际误差≈000061 HW:p.12-113 高次插值通常优于 #5,#7 低次插值 但绝对不是次数越 高就越好,嘿
§1 Lagrange Polynomial 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 高次插值通常优于 低次插值 但绝对不是次数越 高就越好，嘿 嘿…… HW: p.112-113 #5，#7
8 1 Lagrange Polynomial Lab 10. Lagrange polynomial Given a set of sample points (xo, f(xo),(u, f(xD),,(xn, f(xn))of a certain function f, use Lagrange polynomial to approximate function values at some given points Input There are several sets of inputs. For each set: The 1st line contains an integer 20>n>0 which is the degree of agrange polynomial. n=-l signals the end of file The 2nd line contains n+l distinct real numbers xo,x,,x The 3rd line contains n+l real numbers f(o), f(x,),,f(n) The last line of a test case consists of an integer m>0 and m real numbers a1,…,am· The numbers are separated by spaces and new lines
§1 Lagrange Polynomial Lab 10. Lagrange Polynomial Given a set of sample points of a certain function f , use Lagrange polynomial to approximate function values at some given points . Input There are several sets of inputs. For each set: The 1st line contains an integer 20 n 0 which is the degree of Lagrange polynomial. n = -1 signals the end of file. The 2nd line contains n+1 distinct real numbers . The 3rd line contains n+1 real numbers . The last line of a test case consists of an integer m > 0 and m real numbers . The numbers are separated by spaces and new lines. ( , ( )), ( , ( )), ..., ( , ( )) 0 0 1 1 n xn x f x x f x x f m a , ... , a 1 n x , x , ... , x 0 1 ( ), ( ), ... , ( ) 0 1 n f x f x f x m a , ... , a 1
8 1 Lagrange Polynomial Output(- represents a space) For each ai, you are supposed to print the function value at this point in the following format fprintf( outfile,"f(%6.3■=■%128en",a,f); The outputs of two test cases must be seperated by a blank line. Sample Input Sample Output 7 f(■0.740)■=■6.6873582le-001 0.5■0.7■09■1.1■1.3■1.5■1.7■1.9 f(■1600)■=■1.00341309e+000 0.48■0.64■0.78■0.89■0.96■1.00■0.99■0.95f(■0.550)■=■526938820e-001 5■0.74■1.6■0.55■1.2■1.85 f(■1.200)■=■929135742e001 f(■1850)■=■952078056001 0.0■10 0.0■1.0 f(■0.500)■=■5.0000001 1■0.5
§1 Lagrange Polynomial Output ( represents a space) For each ai , you are supposed to print the function value at this point in the following format: fprintf(outfile, "f(%6.3f)=%12.8e\n" , a, f ); The outputs of two test cases must be seperated by a blank line. Sample Input 7 0.50.70.91.11.31.51.71.9 0.480.640.780.890.961.000.990.95 50.741.60.551.21.85 1 0.01.0 0.01.0 10.5 –1 Sample Output f(0.740) =6.68735821e–001 f(1.600) =1.00341309e+000 f(0.550) =5.26938820e–001 f(1.200) =9.29135742e–001 f(1.850) =9.52078056e–001 f(0.500) =5.00000000e–001