§6-3 Newton插值 、线性 Newton插值 假设已知。=f(x)yn1=f(x1),求M1(x使得N(x0)=y0,N(x1)=n 令N1(x)=C0+C1(x-x) 由N1(x0)=yo得 由N1(x1)=y,得 yo+C1(x1-x0)=y1 由此有 yi-yo XI
§6-3 Newton插值 一、线性Newton插值 ( ) ( ) (1) ( ) ( ) , ( ) , ( ) ( ) ( ), ( ), ( ), ( ) , ( ) 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 x x x x y y N x y x x y y C y C x x y N x y C y N x y N x C C x x y f x y f x N x N x y N x y − − − = + − − = + − = = = = = + − = = = = 由此有 由 得 由 得 令 假设已知 求 使得
二、二次 Newton插值 假设已知y=f(x,y1=f(x1)y2=f(x2)求N2(x)使得N2(x)=y, N2(x1)=y2N2(x2)=y2 令N2(x)=C0+C1(x-x0)+C2(x-x0)(x-x1) 由M1(x0)=y,得 由N(x1)=y,得 yi-yo xI=xo 由N2(x2)=y2,得 y2-V yI-yO x2-x xI X-X 由此有
二、二次Newton插值 由此有 由 得 由 得 由 得 令 假设已知 求 使得 2 0 1 0 1 0 2 1 2 1 2 2 2 2 1 0 1 0 1 1 1 1 0 0 1 0 0 2 0 1 0 2 0 1 2 1 1 2 2 2 0 0 1 1 2 2 2 2 0 0 ( ) , ( ) , ( ) , ( ) ( ) ( )( ) ( ) , ( ) ( ), ( ), ( ) ( ), ( ) , x x x x y y x x y y C N x y x x y y C N x y C y N x y N x C C x x C x x x x N x y N x y y f x y f x y f x N x N x y − − − − − − = = − − = = = = = + − + − − = = = = = =
y2-y1 Ji-y N2(x)=y0+ yI-yO X-xo+ (x-x0(x-x1)(2) XI 三、n次 Newton插值 定义1.设f(x)在互异的节点x处的函数值为f, =0,1,…,n称 flx,,x, f-∫ 为(x)关于节点x,x,一阶差商(均差) fx,xg-fx ,x, I (≠j≠k) 为f(x)关于x,x,x的二阶差商
( ) ( ) ( )( ) (2) 0 1 2 0 1 0 1 0 2 1 2 1 1 0 1 0 1 0 2 0 x x x x x x x x y y x x y y x x x x y y N x y − − − − − − − − − + − − = + 三、n次Newton插值 称 定义1. i n f x x f i i 0,1, , ( ) , = 设 在互异的节点 处的函数值为 [ , ] (i j) x x f f f x x i j i j i j − − = 为 ( )关于节点 , 一阶差商(均差) i j f x x x ( ) [ , ] [ , ] [ , , ] i j k x x f x x f x x f x x x k j i k i j i j k − − = 为f (x)关于xi , xj , xk 的二阶差商
依此类推 f[xn,x1灯…x2]一fxx,…,x2,x] X 为/(x)关于节点x,x…,x,x的阶差商 显然 flo -f[x0,x1;…,x2,xk k-1 k
显然 [ , , , , ] 0 1 k 1 k f x x x x − k k k k k x x f x x x f x x x x − − = − − − 1 0 1 1 0 1 2 [ , ,, ] [ , ,, , ] 为f (x)关于节点xi 0 , xi 1 , , xi k−1 , xi k 的k阶差商 [ , , , , ] 0 1 k 1 k i i i i f x x x x − k k k k k i i i i i i i i i x x f x x x f x x x x − − = − − − 1 0 1 1 0 1 2 [ , ,, ] [ , ,, , ] 依此类推
差商的计算方法(差商表) xf(x)一阶差商二阶差商三阶差商 x x [x0,x f[ 01 X,,xX fl f(x2) x3 f(x3) 零阶差商
( ) ( ) ( ) ( ) ( ) 3 3 2 2 1 1 0 0 x f x x f x x f x x f x xk f xk 一阶差商 二阶差商 三阶差商 差商的计算方法(差商表): [ , ] 0 1 f x x [ , ] 1 2 f x x [ , ] 2 3 f x x [ , , ] 0 1 2 f x x x [ , , ] 1 2 3 f x x x [ , , , ] 0 1 2 3 f x x x x 零阶差商
性质1f(x)的阶差商八x0,x12…,xk212x可由函数值 f(x0),f(x)…,f(x)的线性组合表示,且 fl 0/41/fk-1k ∑ f(r,) (x1-x0)…(x1-x1-1)(x-x+1)…(x1-xk) 性质2差商具有对称性,即任意调换节点的次序,差商 的值不变 hu fLo,Mux2=flxox2ix=f2,Xxl 性质3当(x)在包含节点x,x1…,x的区间存在时 在xx1…,x之间必存在一点,使得
的线性组合表示 且 性质 的 阶差商 可由函数值 ( ), ( ), , ( ) , 1 ( ) [ , , , , ] 0 1 0 1 1 k k k f x f x f x f x k f x x x x − [ , , , , ] 0 1 k 1 k f x x x x − = − − − − + − = k i i i i i i i k i x x x x x x x x f x 0 0 1 1 ( ) ( )( ) ( ) ( ) 性质2 差商具有对称性,即任意调换节点的次序,差商 的值不变 [ , , ] 0 1 2 f x x x [ , , ] 0 2 1 = f x x x [ , , ] 2 1 0 如 = f x x x 3 ( ) , , , , 0 1 性质 当f （k ) x 在包含节点x x xk 的区间存在时 在x0 , x1 , , xk 之间必存在一点 ,使得
0/41 k 定理1假设已知y=f(x1)i=0,1,…,m;x互异 Nn(x)=C0+C1(x-x0)+…+Cn(x-x0)…(x-xn-1) 其中 fl Nn(x1)=f(x1)i=0,,…,n
[ , , , ] 0 1 k f x x x ! ( ) ( ) k f k = N x f x i n C f x x x N x C C x x C x x x x y f x i n x n i i i i n n n i i i ( ) ( ) 0,1, , [ , , , ] ( ) ( ) ( ) ( ) 1 ( ), 0,1, , ; 0 1 0 1 0 0 1 = = = = + − + + − − = = − 则 其中 定理 假设已知 互异
定义2称 Nn(x)=Co+C1(x-x0)+…+Cn(x-x0(x-x)…(x-x21) 0+∑几[x,x,…x(x-x) k=1 j=0 =C+∑[x,x,…,x(x) 为f(x)关于节点x的m次 Newton基本插值多项式 推论∩次牛顿插值公式的截断误差(余项)为 R,()=f(x)-Nn(x) n+ I(x-x) (n+1)! fn(2) (n+1) +1(
( ) ( ) ( )( ) ( ) n = 0 + 1 − 0 + + n − 0 − 1 − n−1 N x C C x x C x x x x x x = − = = + − n k k j k j C f x x x x x 1 1 0 0 0 1 [ , ,, ] ( ) 定义2 称 为f (x)关于节点 xi 的n次Newton基本插值多项式 = = + n k k k C f x x x x 1 0 0 1 [ , ,, ] ( ) 推论 n次牛顿插值公式的截断误差（余项）为 R (x) f (x) N (x) n = − n ( ) ( 1)! ( ) 1 ( 1) x n f n n + + + = = + − + = n i i n x x n f 0 ( 1) ( ) ( 1)! ()
例1作一不高于4阶的 Newton插值多项式,使得 N4(0)=1,N4(1)=1,N4(2)=2,N4(3)=3,N4(4)=3 解:作(传统)差商表 Z01234 01234 0.5 0.5 0.5 0 根据 Newton插值多项式定义有 (x)=co+c(x-x)+c2(x-x0)(x-x1) +c,(xXox-Xux-x +c4(x-x0)(x-x1)(x-x2)(x-x3) 1+0.5x(x-1)-0.5x(x-1)(x-2)
例1 作一不高于4阶的Newton插值多项式，使得 (0) 1, (1) 1, (2) 2, (3) 3, (4) 3. N4 = N4 = N4 = N4 = N4 = 解： 作（传统）差商表 i i i x y 0 0 1 1 1 1 2 2 2 3 3 3 4 4 3 0 1 1 0 0.5 0 -0.5 -0.5 -0.5 0 根据Newton插值多项式定义有： 1 0.5 ( 1) 0.5 ( 1)( 2) ( )( )( )( ) ( )( )( ) ( ) ( ) ( )( ) 4 0 1 2 3 3 0 1 2 4 0 1 0 2 0 1 = + − − − − + − − − − + − − − = + − + − − x x x x x c x x x x x x x x c x x x x x x N x c c x x c x x x x c0 c1 c2 c3 c4
四、 Newton基本插值公式的算法设计 输入插值多项式阶n,节点坐标及函数值x,y(i=0,1,…,n) 待插值点坐标z(=1,2,…,m) 输出Nn(=1),l=12…,m 步骤S1对=1,2,…,n;i=01…,n 置yao=y 计算 (y11-y-)/(x+-x) S2对l=1,2,…,m 计算 (=)=∑c(=1-x) i=0j=0
四、 Newton基本插值公式的算法设计 = − − = + − − + = − = = = − − = = = − = = = n i n i j n l i l j j j i j i j i j i j i i i n l l i i N z c z x l m C y y y y x x y y S j n i n j N z l m z l m n x y i n 0 1 0 0 1, 1 , 1 0 ( ) ( ) S2 1,2, , ( ) ( ) 1 1,2, , ; 0,1, , ( ), 1,2, , ( 1,2, , ). ; , ( 0,1, , ); 计算 对 计算 置 对 待插值点坐标 插值多项式阶 节点坐标及函数值 输入 输出 步骤