《数值逼近》第三章 多项式插值方法

解先造好下列的差商表 一阶差商 二阶差商 三阶差商 2356 然后从上表顶部对角线上取得的值∫(x0f(x0,x1)f(x,x12x2),f(x0,x1,x2,x3)代 入公式(2.2),便可得到要求的多项式 P3(x)=5-3(x-2)+÷(x-2)x-3)-(x-2x-3)(x-5) §3.插值余项 设Pn(x)是在点x0,x1,…x处关于f(x)的插值多项式。我们希望知道 x≠x4(k=0,…,n)时,f(x)与pn(x)的偏差,意指此方法所固有的误差,而忽 略在计算Pn(x)时造成的舍入误差。通常,舍入误差与在逼近中的固有误差相比 是小的。按习惯,称 E(; x)=f(x)-p,(x) 为插值误差(插值余项)。下面定理给出了E(f;x)的表达式 定理1若∫(x)于包含着插值结点x,x1,…xn的区间[a,b]上n+1次可微,则 对任意x∈[ab],有与x有关的§存在(a<§b),使得 EC; x)=f(x)-P,(x) f(n(5) (n+1)! 其中o(x)=(x-x0Xx-x1)…(x-xn)。 证明今取一点x∈[a,b],显然当x=x0,x1…,xn时,(31)式是自然满足的

解 先造好下列的差商表： x y 一阶差商 二阶差商 三阶差商 6 5 3 2 4 3 2 5 1 2 1 − 3 6 1 6 7 4 1 − 然后从上表顶部对角线上取得的值 ( ), ( , ), ( , , ), ( , , , ) 0 0 1 0 1 2 0 1 2 3 f x f x x f x x x f x x x x 代 入公式 (2.2) ，便可得到要求的多项式： ( 2)( 3)( 5). 4 1 ( 2)( 3) 6 7 ( ) 5 3( 2) p3 x = − x − + x − x − − x − x − x − §３．插值余项 设 p (x) n 是在点 n x , x , , x 0 1  处关于 f (x) 的插值多项式。我们希望知道 x x (k 0,1, ,n)  k =  时， f (x) 与 p (x) n 的偏差，意指此方法所固有的误差，而忽 略在计算 p (x) n 时造成的舍入误差。通常，舍入误差与在逼近中的固有误差相比 是小的。按习惯，称 E( f ; x) f (x) p (x) = − n 为插值误差（插值余项）。下面定理给出了 E( f ; x) 的表达式。 定理 1 若 f (x) 于包含着插值结点 n x , x , , x 0 1  的区间 [a,b] 上 n +1 次可微，则 对任意 x [a,b] ，有与 x 有关的ξ存在（a<ξ<b）,使得 ( ), ( 1)! ( ) ( ; ) ( ) ( ) ( 1) ξ ω + + = − = n n f n x E f x f x p x （3.1） 其中 ( ) ( )( ) ( ) 0 1 n ω x = x − x x − x  x − x 。 证明 今取一点 x [a,b] ，显然当 n x x , x , , x = 0 1  时，(3.1)式是自然满足的

以下设x不是插值结点x,x1…xn,作辅助函数 F(x)=(2)-p(2)-)((x)-p(x) (32) 显然F(-)于[ab上n+1次可微,并且F(x)=0,F(x,)=0(=0…,n)。因为 xx0,x1…,xn各不相同,由 Rolle i引理知F"(-)于(a,b)内至少有n+1个不同的根。 依此类推,最后知F((z)于(a,b)内至少有一个根ξ,亦即由(32成式应有 F((5)=fm x)((x)-pn(x)=0。 由此,便得到了公式(3.1)。证毕 通常我们并不知道(31)式中的§(一旦知道了§,就知道了精确的误差),尽管 如此,我们还是能从(31)式得到有用的信息。例如,若f(x)在ab]上有上界 Mn1,亦即 Mn+=sup//m(x) 则由(31)式立刻得到 E(x)≤"1(x-x0x-x1)…(x-xn)a≤x≤b。 (n+1) 设已知y=f(x,X=O1,…m),并且m>>n+1。如所知,为了构造一个 n次插值多项式,只需要n+1个插值结点。因此自然提出这样的问题:在所有的 已知点(x,xX=01,…,m)的横坐标x,x,…x(x≠x,x≠门中,如何选取插 值结点x,x1…,x使得 为此,只须从x2x1…xm中选择使差

以下设 x 不是插值结点 n x , x , , x 0 1  ，作辅助函数 ( ( ) ( )) ( ) ( ) ( ) ( ) ( ) f x p x x z F z f z p z = − n − − n ω ω 。 （3.2） 显然 F(z) 于 [a,b] 上 n +1 次可微，并且 F(x) 0, F(x ) 0( j 0,1, ,n) = j = =  。因为 n x, x , x , , x 0 1  各不相同，由 Rolle 引理知 F'(z) 于 (a,b) 内至少有 n +1 个不同的根。 依此类推，最后知 ( ) ( 1) F z n+ 于 (a,b) 内至少有一个根ξ，亦即由(3.2)式应有 ( ( ) ( )) 0 ( ) ( 1)! ( ) ( ) ( 1) ( 1) − = + = − + + f x p x x n F f n n n ω ξ ξ 。 由此，便得到了公式(3.1)。证毕。 通常我们并不知道(3.1)式中的ξ（一旦知道了ξ，就知道了精确的误差），尽管 如此，我们还是能从(3.1)式得到有用的信息。例如，若 ( ) [ , ] ( 1) f x a b n+ 在 上有上界 M n+1 ，亦即 ( ) ( 1) M 1 sup f x n a x b n +   + = ， 则由(3.1)式立刻得到 x x x x x x a x b n M E f x n n − − −   +  + ( )( ) ( ), ( 1)! ( ; ) 0 1 1  。 (3.3) 设已知 y f (x )( j 0,1, ,m) i = j =  ，并且 m  n +1 。如所知，为了构造一个 n 次插值多项式，只需要 n +1 个插值结点。因此自然提出这样的问题：在所有的 已知点 (x , x )( j 0,1, ,m) i j =  的横坐标 , , , ( , ) 0 1 x x x x x x j  m i  j  中，如何选取插 值结点 n x , x , , x 0 1  使得 ( ) x - x min . ω x = x − x0 x − x1  n = (3.4) 为此，只须从 m x , x , , x 0 1  中选择使差 x x ( j 0,1, ,m) − j = 

取最小值的x作为第一个插值结点x。然后,在剩下的m个点中再选择使得 xx1为最小的点作为第二个插值结点x。如此等等,直到选出x为止。显然, 这样选取的x,x1,…x满足(34)的要求。 关于在整个插值区间上的余项极小化问题,与第二章中 Tchebyshev最小零 偏差多项式直接相关。事实上,由(3.3)式,为使插至余项在整个区间上尽可能地 小的“最佳”插值结点组,应该取为该区间上最小零偏差多项式的零点。 以下给出插值余项的 Peano估计。它是意大利数学家 G Peano在1913年给出 的 令[a,b是有限区间,m≥1是整数。若f(x),f(x)…,fm(x)在[a,b]上连续, 而(x)在ab上分段连续且(x)≤Mm,则说函数∫(x)属于函数类 w (Mn,a, b) 例1令∫(x)=[ab]=[-1。容易验证∫(x)∈W1(1-1)l 例2令[a,b]=[-11及 f(x)= 3x2x≥0, 3x2x≤0 则 6xx≥ 0, 6xx≤0. 6x<0 因此,f(x)∈W(6,-1,1),同时f(x)∈W2(6,-11) 令x和是实数,k≥0是整数。二个变量x和t的函数(x-1)定义如下 j(x-1),x≥

取最小值的 j x 作为第一个插值结点 0 x 。然后，在剩下的 m 个点中再选择使得 j x − x 为最小的点作为第二个插值结点 1 x 。如此等等，直到选出 n x 为止。显然， 这样选取的 n x , x , , x 0 1  满足(3.4)的要求。 关于在整个插值区间上的余项极小化问题，与第二章中 Tchebyshev 最小零 偏差多项式直接相关。事实上，由(3.3)式，为使插至余项在整个区间上尽可能地 小的“最佳”插值结点组，应该取为该区间上最小零偏差多项式的零点。 以下给出插值余项的 Peano 估计。它是意大利数学家 G.Peano 在 1913 年给出 的。 令 [a,b] 是有限区间， m 1 是整数。若 ( ), ( ), , ( ) (1) ( ) f x f x f x  m 在 [a,b] 上连续， 而 ( ) [ , ] ( ) f x a b m 在 上 分段 连续 且 m m f (x)  M ( ) ， 则 说函 数 f (x) 属 于 函数 类 W (M ;a,b) m m . 例1 令 f (x) = x ,[a,b] = [−1,1] 。容易验证 ( ) (1; 1,1) 1 f x W − 。 例2 令 [a,b] = [−1,1] 及    −   = 3 0, 3 0, ( ) 2 2 x x x x f x 则    −   = 6 0, 6 0, ( ) (1) x x x x f x    −   = 6 0. 6 0, ( ) (2) x x f x 因此， ( ) (6; 1,1) 1 f x W − ，同时 ( ) (6; 1,1). 2 f x W − 令 x和t 是实数， k  0 是整数。二个变量 x和t 的函数 k x t − + ( ) 定义如下     −  − + = 0, . ( ) , , ( ) x t x t x t x t k k

若t为固定常数,则(x-1)就是x的截断多项式。对于k=02,截断多项式的图形 如下 图3.1) (x-1)4 (x-t)4 (x-1)4 图3.1 当x固定时,(x-1)是t的函数,请读者绘出它的图形(k=0,1,2) 我们用[ab来记包含着点α,x0,x1…xn的最小区间。E(fa)仍表插值误差, 亦即E(/a)=(a)-p,(a)其中pn(x)为函数(x)在结点x,x,…,x,上的n次插 值多项式 定理2设m是正整数(1≤m≤n+1),则当f(x)属于Wm(Mn;a,b)时,存在一个仅 依赖于m,a,x0,x1…,xn的函数Kn(1) Km(o E(x-1)x;a) (m-1) m-∑14(a)x-1)) (36)使得 EU; a)=Km(t)f(m)(t)dt (3.7) 证明依假设条件,可以将f(x)展成 Taylor级数 f(x)=om-(x)+R(x) 其中 Qn1(x)=f(a)+(x-a)(a)+…+ (x-a)°rm)(a)

若 t 为固定常数，则 x t x ( − ) k +就是 的截断多项式。对于 k = 0,1,2, 截断多项式的图形 如下 (图 3.1)： 当 x 固定时， k x t − + ( ) 是 t 的函数，请读者绘出它的图形( k = 0,1,2 ). 我们用 [a,b] 来记包含着点 n x , x , , x α， 0 1  的最小区间。 E( f ;a) 仍表插值误差， 亦即 E( f ;a) f (a) p (a),  − n 其中 p (x) f (x) n 为函数 在结点 n x , x , , x 0 1  上的 n 次插 值多项式。 定理 2 设 m 是正整数( 1 m  n +1 ),则当 f (x) 属于 W (M ;a,b) m m 时，存在一个仅 依赖于 n m,a x , x , , x ， 0 1  的函数 K (t) m ： (( ) ( )( ) ), ( 1)! 1 (( ) ; ) ( 1)! 1 ( ) 0 1 1 1 = − + − + − + − − − − = − − = n k m k k m m m a t l a x t m E x t a m K t (3.6) 使得 ( ; ) ( ) ( ) . ( ) E f a K t f t dt m b a =  m (3.7) 证明 依假设条件，可以将 f (x) 展成 Taylor 级数： ( ) ( ) ( ) 1 f x Q x R x = m− + m 其中 ( ), ( 1)! ( ) ( ) ( ) ( ) '( ) ( 1) 1 1 f a m x a Q x f a x a f a m m m − − − − − = + − ++