数值计算方法
第 4 章 插 值 法
4.4 Newton 插值法
武汉大学数学与统计学院
上一讲的简单回顾
● 插值多项式的存在惟一性,
满足插值条件
Pn(xi)=f(xi),( i=0,1,2,…,n)
n次插值多项式 Pn(x)=a0+a1x+a2x2+……+ anxn 存在而且惟一,
● 插值余项, Rn(x)= f(x)- Pn(x)=,
● Lagrange插值多项式
( 1 )
1
() ()
( 1 ) !
n
x
n
f wx
n
??
?? (,)x ab? ?
0
( ) ( ) ( )
n
n i i
i
L x f x l x
?
? ?
0 1 1
0 1 1
( ) ( ) ( ) ( )()
( ) ( ) ( ) ( )
i i n
i
i i i i i i n
x x x x x x x xlx
x x x x x x x x
??
??
? ? ? ??
? ? ? ?
其中,i =0,1,…,n
称为 Lagrange插值基函数
优点, 具有严格的规律性,便于记忆,
缺点, 不具有承袭性,即每当增加一个节点时,不仅要增加求
和的项数,而且以前的各项也必须重新计算,
为了克服这一缺点,本讲将建立具有承袭性的插值公式 —
Newton插值公式,
本讲主要内容,
● Newton插值多项式的构造
● 差商的定义及性质
● 差分的定义及性质
● 等距节点 Newton插值公式
一 基函数
问题 1 求作 n次多项式
使满足
()nNx
0 1 0 2 0 1
0 1 2 1
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
n
nn
N x c c x x c x x x x
c x x x x x x x x ?
? ? ? ? ? ? ?
? ? ? ? ?
( ) ( ),0,1,n i iN x f x i n??
(2)
为了使 的形式得到简化,引入如下记号()
nNx
0
11
0 1 1
( ) 1
( ) ( ) ( )
( ) ( ) ( ),1,2,
i i i
i
x
x x x x
x x x x x x i n
?
?? ??
?
?
??
? ? ? ? ?
(3)
(1)
定义 由式 (3)定义的 n+1个多项式
称为 Newton插值 的以 x0,,x1,…,xn为节点的 基函数,即
可以证明,这样选取的基函数是 线性无关 的,由此得
出的问题 4.1的解 便于求值,而且 新增加一个节点 xn+1时
只需加一个新项 即
而
01( ),( ),,( )nx x x? ? ?
0 0 1 1( ) ( ) ( ) ( )n n nN x c x c x c x? ? ?? ? ? ?
11()nncx???
11()nncx???
11 ()nncx???
1 0 0 1 1 1 1( ) ( ) ( ) ( ) ( )n n n n nN x c x c x c x c x? ? ? ?? ? ?? ? ? ? ?
1 ( ) ( ) ( )n n nx x x x??? ??
(4)
依据条件 (2),可以依次确定 系数 c0,c1,…,c n..例如,
取 x=x0,,得
取 x=x1,得
1 0 1 0
1
1 0 1 0
( ) ( ) ( )nN x c f x f xc
x x x x
????
??
0 0 0( ) ( )nc N x f x??
1 0 1 1 0 1( ) ( ) ( )nN x c c x x f x? ? ? ?
?
取 x=x2,得
0 1 2 0 2 2 0 2 1 2( ) ( ) ( ) ( )c c x x c x x x x f x? ? ? ? ? ?2()nNx ?
.
10
2 0 2 0
2 0 1 2 0 1 0
2
2 0 2 1 2 0 2 1
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( ) ( )
n
f x f x
f x f x x x
N x c c x x x x
c
x x x x x x x x
?
? ? ?
? ? ? ?
??
? ? ? ?
1 0 1 0
2 1 1 0 2 0
1 0 1 0
2 0 2 1
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
f x f x f x f x
f x f x x x x x
x x x x
x x x x
??
? ? ? ? ?
?
??
1021
20
2 1 1 0
( ) ( )( ) ( ) ()f x f xf x f x xx
x x x x
?? ??
? ? ???
????
为了得到计算系数 ci的一般方法,下面引进 差商的概念,
?
二 差商的定义
给定 [a,b]中互不相同的点 x0,x1,x2,…,以及 f(x)在这些点处相
应的函数值 f(x0),f(x1),f(x2),…,用记号
表示 f(x)在 x0及 x1两点的 一阶差商, 用记号
表示 f(x)在 x0,x1,x2三点的 二阶差商, 一般地,有了 k-1阶差商之后,
可以定义 f(x)在 x0,x1,..,xk的 k阶差商
01
01
01
( ) ( )[,] f x f xf x x
xx
??
?
0 1 1 2
0 1 2
02
[,] [,][,,] f x x f x xf x x x
xx
??
?
0 1 1 1 2
01
0
[,,,] [,,,][,,,] kk
k
k
f x x x f x x xf x x x
xx
? ??
?
三 Newton插值公式
由差商定义,有
f(x)= f[x0]+(x-x0)f[x,x0]
f[x,x0]= f[x0,x1]+(x-x1)f[x,x0,x1]
f[x,x0,x1]= f[x0,x1,x2]+(x-x2)f[x,x0,x1,x2]
………..
f[x,x0,… xn-1]= f[x0,…,xn]+(x-xn)f[x,x0,….,xn]
将以上各式，由下而上逐步代入，得到
f(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2]
+…+( x-x0)…( x-xn-1) f[x0,…,xn]
+(x-x0)…( x-xn-1)(x-xn)f[x,x0,… xn]
(5)
记
Nn(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2]
+…+( x-x0)…( x-xn-1) f[x0,…,xn] (6)
Rn(x)= (x-x0)…( x-xn) f[x,x0,…,xn]= f[x,x0,…,xn]wn+1(x) (7)
则 (5)可表示为
f(x)= Nn(x)+ Rn(x) (8)
显然,Nn(x)是次数不超过 n的多项式,且有
Rn(xi)= f[x,x0,…,xn]wn+1(xi)=0,i=0,1,…,n
即 Nn(xi)= f(xi),i=0,1,…,n
由此可知,如此构造的函数 Nn(x)就是问题 1的解,且
ci =f[x0,…,xi],i=0,1,…,n (9)
公式 (6)称为函数 f(x)在节点 x0,…,xn上的 n阶 Newton
插值公式,(7)式称为 Newton插值公式余项,即截断误差,注
意到,余项表达式 (7)只要求被插值函数 f(x)在插值区间 [a,b]
上连续,
由函数 f(x)的 插值多项式的惟一性,函数 f(x)的 Newton
插值多项式与 Lagrange插值多项式实为同一个多项式,即
Nn(x) ≡ Ln(x)
两者不过是表现形式不同而已,由此有, 若 f(x)∈C n+1[a,b],
则有
Rn(x)= f[x,x0,…,xn]wn+1(x)= ( 1 )
1
() ()
( 1 ) !
n
x
n
f wx
n
??
??
(,)x ab? ?
,
(10)
01 0 0 1 1
()[,,,]
( ) ( ) ( ) ( )
k i
k i i i i iii k
fxf x x x
x x x x x x x x? ??? ? ? ? ??
四 差商的性质
性质 1(差商与函数值的关系 )
证明：
性质 2(对称性 )
0101[,,,] [,,,]ki i ikf x x x f x x x?
其中 i0,…,ik是 0,1,… k的任排列,
证明, 由性质 1可知,
性质 3(差商与导数的关系 ) f(x)∈C k[a,b],
,
证明, 由式 (10)即得,
()
01 ()![,,,]
k
k f kf x x x ??? ?0 0m i n,iiik ikx m a x x? ?? ???
性质 4(多项式的差商 )设 f(x)为 n次多项式,则其一阶差商
是 x的 n-1次多项式
[ ] [ ][,] i
i i
f x f xf x x
xx
??
?
推论 n次多项式 pn(x)的 k阶差商 pn[x0,… xk],当 k≤n时
是 n-k次多项式,当 k>n时恒为 0
证明,
运用 Newton插值公式 (6)进行计算时,先计算 f(x)关于
节点 x0,…,xn的各阶差商,计算过程如下表所示,
.
xk f(xk) 一阶差商 二阶差商 三阶差商 n 阶差商
1
2
3
o
n
x
x
x
x
x
0
1
2
3
[]
[]
[]
[]
[]
n
fx
fx
fx
fx
fx
01
12
23
1
[,]
[,]
[,]
[,]
nn
f x x
f x x
f x x
f x x
?
0 1 2
1 2 3
21
[,,]
[,,]
[,,]
n n n
f x x x
f x x x
f x x x
??
0 1 2 3
3 2 1
[,,,]
[,,,]n n n n
f x x x x
f x x x x? ? ?
01[,,,]nf x x x
计算 Nn(x)时,常采用 秦九韶算法,即,
0 0 0 1 0 1 0 1 2
0 1 1 0 1
0 0 0 1 1 0 1 2
2 0 1 2 1 0 1
( ) ( ) ( ) [,] ( ) ( ) [,,]
( ) ( ) ( ) [,,,]
( ) ( ) ( [,] ( ) ( [,,]
( ) ( [,,,] ( ) [,,] ) ) )
n
nn
n n n n
N x f x x x f x x x x x x f x x x
x x x x x x f x x x
f x x x f x x x x f x x x
x x f x x x x x f x x x
?
? ? ?
? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
下面给出 Newton插值法的计算机 算法,开始时,f(k)存放函
数值 f(xk),运算完毕 f(k)存放 k阶差商 f[x0,…,xk]
Newton插值算法
(1) 输入, xi,fi;
(2) di=fi (i=0,1,…,n);
(3) 计算差商
对 i=1,2,…,n 做
(3.1) 对 j=i,i+1,…,n 做
fj=(dj-dj-1)/(xj-xj-i);
(3.2) 对 j=i,i+1,…,n 做 dj=fj;
(4) 计算插值 N(u)
(4.1)输入插值点 u;
(4.2) v=0;
(4.3) 对 i=n,n-1,…,1,0 做 v=v(u-xi)+fi;
(5) 输出 u,v.
五 等距节点的 Newton插值公式与差分
当插值节点 x0,…,xn为等距分布时,Newton插值公式
(6)可以简化,
设插值节点 xj=x0+jh,j=0,1,…,n ; h=(b-a)/n称为步长,且
x0=a,xn=b,令 x=x0+th,则当 x0≤x≤xn时,0≤t≤n,基函数
此时差商也可进一步化简,为此引进 差分的概念,
定义 称 △ f(xi)=f(xi+h)-f(xi)
和 ▽ f(xi)= f(xi)-f(xi-h)
分别 为函数 f(x)在点 xi处的 一阶向前差分 和 一阶向后差分,
0 1 1( ) ( ) ( ) ( )
( 1 ) ( 2 ) ( 1 )
ii
i
x x x x x x x
t t t t i h
? ?? ? ? ?
? ? ? ? ?
一般地,称 k阶差分的差分为 k+1阶差分,如二阶向前和向
后差分分别为
计算各阶差分可按如下差分表进行,
2
2
( ) ( ( ) ) ( ( ) ( ) )
( ) ( )
( 2 ) 2 ( ) ( )
( ) ( ( ) ) ( ( ) ( ) )
( ) ( )
( ) 2 ( ) ( 2 )
i i i i
ii
i i i
i i i i
ii
i i i
f x f x f x h f x
f x h f x
f x h f x h f x
f x f x f x f x h
f x f x h
f x f x h f x h
? ? ? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
23
00
1 1 0
2
2 2 1 0
23
3 3 2 1 0
23
1 2 3 0
n
i i i i i i
n
n n n n n
x f f f f f
xf
x f f
x f f f
x f f f f
x f f f f f
? ? ?
? ? ? ?
?
??
? ? ?
? ? ? ?
向前差分表
差分具有如下性质,,
性质 1(差分与函数值的关系 ) 各阶差分均可表示为函值
fj=f(xj)的线性组合,
性质 2(前差与后差的关系 ):
性质 3(多项式的差分 )若 f(x)∈P n(n次多项式类 ),则
00
( 1 ),( 1 )
!
! ( ) !
kk
k j j k k j j
i k i j k i k i j k
jj
j
k
f C f f C f
k
C
j k j
?
? ? ? ?
??
? ? ? ? ? ?
?
?
??
kki i kff ?? ? ?
,
( ) !,
0,
nk
kn
n
P k n
f x a h n k n
kn
????
?
? ? ??
?
??
其中
性质 4(差分与差商的关系 ):
性质 5(差分与导数的关系
利用这些性质,可将 Newton公式
Nn(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2]
+…+( x-x0)…( x-xn-1) f[x0,…,xn]
进一步简化
1
1
[,,,]
!
[,,,]
!
k
i
i i i k k
k
i
i i i k k
f
f x x x
kh
f
f x x x
kh
??
??
?
?
?
?
1
()
! [,,,]
( ),( )
kk
i i i i k
kk
i i k
f k h f x x x
h f x x??
??
?
??
? ? ?
0
2
0 0 0 0
( ) ( )
( 1 ) ( 1 ) ( 1 )
1 ! 2 ! !
nn
n
N x N x th
t t t t t t n
f f f f
n
??
? ? ? ?
? ? ? ? ? ? ? ?(11)
称公式 (11)为 Newton向前差分插值公式,其余项为
1 ( 1 )
0
0
( 1 ) ( )
( ) ( ) ( )
( 1 ) !
(,)
nn
nn
n
t t t n
R x R x th h f
n
xx
?
?
????? ? ?
?
?
(12)
如果将式 (6)改为按节点 xn,xn-1,…,x0的次序排列的 Newton插
值公式,即
1
1 1 1 0
( ) ( ) ( ) [,]
( ) ( ) ( ) [,,]
n n n n n
n n n n
N x f x x x f x x
x x x x x x f x x x
?
??
? ? ? ?
? ? ? ?
令 x=xn-th,则当 x0≤x≤xn时,0≤t≤n.利用差商与向后
差分的关系,式 (13)可简化为
22
( ) ( )
( 1 )
( 1 )
2!
( 1 ) ( ( 1 )
( 1 )
!
n n n
n n n
nn
n
N x N x th
tt
f t f f
t t t n
f
n
??
?
? ? ? ? ? ? ?
? ? ?
? ? ?
(13)
(14)
称式 (14)为 Newton向后差分插值公式,其余项为
( 1 )
11
0
()( ) ( ) ( 1 ) ( 1 ) ( )
( 1 ) !
n
nn
n n n
n
fR x R x th h t t t n
n
xx
?
?
?
??? ? ? ? ? ?
?
??
221 2 0,,,nnn n n n nf f f f f f??? ? ? ? ? ? ? ? ?
若要计算的插值点 x较靠近点 x0,则用向前插值公式 (4.8),
这时 t=(x-x0)/n的值较小,数值稳定性较好,反之,若 x靠近 xn,,,则
用向后插值公式 (14).
利用向前与向后差分的关系 (差分性质 2):
22
12
0
( 1 )
( ) ( ) ( 1 )
2!
( 1 ) ( 1 )
( 1 ),
!
n n n n n n
nn
tt
N x N x t h f t f f
t t t n
f
n
??
?
? ? ? ? ? ? ? ? ?
? ? ?
? ? ?
式 (14)可表示成
(15)
这样,计算靠近 x0或 xn的点的值时,都只需构造向前差分表
例 给定 f(x)在等距节点上的函数值表如下,
xi 0.4 0.6 0.8 1.0
f(xi) 1.5 1.8 2.2 2.8
分别用 Newton向前和向后差分公式,求 f(0.5)及 f(0.9)的近似值,
解 先构造向前差分表如下,
xi fi △ fi △ 2fi △ 3fi
0.4 1.5
0.6 1.8 0.3
0.8 2.2 0.4 0.1
1.0 2.8 0.6 0.2 0.1
x0=0.4,h=0.2,x3=1.0,由 (4.8)和 (4.12),分别用差分表中对角
线上的值和最后一行的值,得 Newton向前和向后插值公式如
下,
3
3
( 1 ) ( 1 ) ( 2)
( 0,4 0,2 ) 1,5 0,3 0,1 0,1
2 3!
( 1 ) ( 1 ) ( 2)
( 1 0,2 ) 2,8 0,6 0,2 0,1
2 3!
t t t t t
N t t
t t t t t
N t t
? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
(1)
(2)
当 x=0.5时,用公式 (1),这时 t=(x-x0)/h=0.5,将 t=0.5代入 (1),得
f (0.5)≈N3(0.5)=1.64375.
当 x=0.9时,用公式 (2),这时 t=(x3-x)/h=0.5,将 t=0.5代入 (2),得
f (0.9)≈N3(0.9)=2.46875.
课后练习题
P217,第 2题,第 4题,
P219,第 11题,
第 4 章 插 值 法
4.4 Newton 插值法
武汉大学数学与统计学院
上一讲的简单回顾
● 插值多项式的存在惟一性,
满足插值条件
Pn(xi)=f(xi),( i=0,1,2,…,n)
n次插值多项式 Pn(x)=a0+a1x+a2x2+……+ anxn 存在而且惟一,
● 插值余项, Rn(x)= f(x)- Pn(x)=,
● Lagrange插值多项式
( 1 )
1
() ()
( 1 ) !
n
x
n
f wx
n
??
?? (,)x ab? ?
0
( ) ( ) ( )
n
n i i
i
L x f x l x
?
? ?
0 1 1
0 1 1
( ) ( ) ( ) ( )()
( ) ( ) ( ) ( )
i i n
i
i i i i i i n
x x x x x x x xlx
x x x x x x x x
??
??
? ? ? ??
? ? ? ?
其中,i =0,1,…,n
称为 Lagrange插值基函数
优点, 具有严格的规律性,便于记忆,
缺点, 不具有承袭性,即每当增加一个节点时,不仅要增加求
和的项数,而且以前的各项也必须重新计算,
为了克服这一缺点,本讲将建立具有承袭性的插值公式 —
Newton插值公式,
本讲主要内容,
● Newton插值多项式的构造
● 差商的定义及性质
● 差分的定义及性质
● 等距节点 Newton插值公式
一 基函数
问题 1 求作 n次多项式
使满足
()nNx
0 1 0 2 0 1
0 1 2 1
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
n
nn
N x c c x x c x x x x
c x x x x x x x x ?
? ? ? ? ? ? ?
? ? ? ? ?
( ) ( ),0,1,n i iN x f x i n??
(2)
为了使 的形式得到简化,引入如下记号()
nNx
0
11
0 1 1
( ) 1
( ) ( ) ( )
( ) ( ) ( ),1,2,
i i i
i
x
x x x x
x x x x x x i n
?
?? ??
?
?
??
? ? ? ? ?
(3)
(1)
定义 由式 (3)定义的 n+1个多项式
称为 Newton插值 的以 x0,,x1,…,xn为节点的 基函数,即
可以证明,这样选取的基函数是 线性无关 的,由此得
出的问题 4.1的解 便于求值,而且 新增加一个节点 xn+1时
只需加一个新项 即
而
01( ),( ),,( )nx x x? ? ?
0 0 1 1( ) ( ) ( ) ( )n n nN x c x c x c x? ? ?? ? ? ?
11()nncx???
11()nncx???
11 ()nncx???
1 0 0 1 1 1 1( ) ( ) ( ) ( ) ( )n n n n nN x c x c x c x c x? ? ? ?? ? ?? ? ? ? ?
1 ( ) ( ) ( )n n nx x x x??? ??
(4)
依据条件 (2),可以依次确定 系数 c0,c1,…,c n..例如,
取 x=x0,,得
取 x=x1,得
1 0 1 0
1
1 0 1 0
( ) ( ) ( )nN x c f x f xc
x x x x
????
??
0 0 0( ) ( )nc N x f x??
1 0 1 1 0 1( ) ( ) ( )nN x c c x x f x? ? ? ?
?
取 x=x2,得
0 1 2 0 2 2 0 2 1 2( ) ( ) ( ) ( )c c x x c x x x x f x? ? ? ? ? ?2()nNx ?
.
10
2 0 2 0
2 0 1 2 0 1 0
2
2 0 2 1 2 0 2 1
( ) ( )
( ) ( ) ( )
( ) ( )
( ) ( ) ( ) ( )
n
f x f x
f x f x x x
N x c c x x x x
c
x x x x x x x x
?
? ? ?
? ? ? ?
??
? ? ? ?
1 0 1 0
2 1 1 0 2 0
1 0 1 0
2 0 2 1
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
f x f x f x f x
f x f x x x x x
x x x x
x x x x
??
? ? ? ? ?
?
??
1021
20
2 1 1 0
( ) ( )( ) ( ) ()f x f xf x f x xx
x x x x
?? ??
? ? ???
????
为了得到计算系数 ci的一般方法,下面引进 差商的概念,
?
二 差商的定义
给定 [a,b]中互不相同的点 x0,x1,x2,…,以及 f(x)在这些点处相
应的函数值 f(x0),f(x1),f(x2),…,用记号
表示 f(x)在 x0及 x1两点的 一阶差商, 用记号
表示 f(x)在 x0,x1,x2三点的 二阶差商, 一般地,有了 k-1阶差商之后,
可以定义 f(x)在 x0,x1,..,xk的 k阶差商
01
01
01
( ) ( )[,] f x f xf x x
xx
??
?
0 1 1 2
0 1 2
02
[,] [,][,,] f x x f x xf x x x
xx
??
?
0 1 1 1 2
01
0
[,,,] [,,,][,,,] kk
k
k
f x x x f x x xf x x x
xx
? ??
?
三 Newton插值公式
由差商定义,有
f(x)= f[x0]+(x-x0)f[x,x0]
f[x,x0]= f[x0,x1]+(x-x1)f[x,x0,x1]
f[x,x0,x1]= f[x0,x1,x2]+(x-x2)f[x,x0,x1,x2]
………..
f[x,x0,… xn-1]= f[x0,…,xn]+(x-xn)f[x,x0,….,xn]
将以上各式，由下而上逐步代入，得到
f(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2]
+…+( x-x0)…( x-xn-1) f[x0,…,xn]
+(x-x0)…( x-xn-1)(x-xn)f[x,x0,… xn]
(5)
记
Nn(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2]
+…+( x-x0)…( x-xn-1) f[x0,…,xn] (6)
Rn(x)= (x-x0)…( x-xn) f[x,x0,…,xn]= f[x,x0,…,xn]wn+1(x) (7)
则 (5)可表示为
f(x)= Nn(x)+ Rn(x) (8)
显然,Nn(x)是次数不超过 n的多项式,且有
Rn(xi)= f[x,x0,…,xn]wn+1(xi)=0,i=0,1,…,n
即 Nn(xi)= f(xi),i=0,1,…,n
由此可知,如此构造的函数 Nn(x)就是问题 1的解,且
ci =f[x0,…,xi],i=0,1,…,n (9)
公式 (6)称为函数 f(x)在节点 x0,…,xn上的 n阶 Newton
插值公式,(7)式称为 Newton插值公式余项,即截断误差,注
意到,余项表达式 (7)只要求被插值函数 f(x)在插值区间 [a,b]
上连续,
由函数 f(x)的 插值多项式的惟一性,函数 f(x)的 Newton
插值多项式与 Lagrange插值多项式实为同一个多项式,即
Nn(x) ≡ Ln(x)
两者不过是表现形式不同而已,由此有, 若 f(x)∈C n+1[a,b],
则有
Rn(x)= f[x,x0,…,xn]wn+1(x)= ( 1 )
1
() ()
( 1 ) !
n
x
n
f wx
n
??
??
(,)x ab? ?
,
(10)
01 0 0 1 1
()[,,,]
( ) ( ) ( ) ( )
k i
k i i i i iii k
fxf x x x
x x x x x x x x? ??? ? ? ? ??
四 差商的性质
性质 1(差商与函数值的关系 )
证明：
性质 2(对称性 )
0101[,,,] [,,,]ki i ikf x x x f x x x?
其中 i0,…,ik是 0,1,… k的任排列,
证明, 由性质 1可知,
性质 3(差商与导数的关系 ) f(x)∈C k[a,b],
,
证明, 由式 (10)即得,
()
01 ()![,,,]
k
k f kf x x x ??? ?0 0m i n,iiik ikx m a x x? ?? ???
性质 4(多项式的差商 )设 f(x)为 n次多项式,则其一阶差商
是 x的 n-1次多项式
[ ] [ ][,] i
i i
f x f xf x x
xx
??
?
推论 n次多项式 pn(x)的 k阶差商 pn[x0,… xk],当 k≤n时
是 n-k次多项式,当 k>n时恒为 0
证明,
运用 Newton插值公式 (6)进行计算时,先计算 f(x)关于
节点 x0,…,xn的各阶差商,计算过程如下表所示,
.
xk f(xk) 一阶差商 二阶差商 三阶差商 n 阶差商
1
2
3
o
n
x
x
x
x
x
0
1
2
3
[]
[]
[]
[]
[]
n
fx
fx
fx
fx
fx
01
12
23
1
[,]
[,]
[,]
[,]
nn
f x x
f x x
f x x
f x x
?
0 1 2
1 2 3
21
[,,]
[,,]
[,,]
n n n
f x x x
f x x x
f x x x
??
0 1 2 3
3 2 1
[,,,]
[,,,]n n n n
f x x x x
f x x x x? ? ?
01[,,,]nf x x x
计算 Nn(x)时,常采用 秦九韶算法,即,
0 0 0 1 0 1 0 1 2
0 1 1 0 1
0 0 0 1 1 0 1 2
2 0 1 2 1 0 1
( ) ( ) ( ) [,] ( ) ( ) [,,]
( ) ( ) ( ) [,,,]
( ) ( ) ( [,] ( ) ( [,,]
( ) ( [,,,] ( ) [,,] ) ) )
n
nn
n n n n
N x f x x x f x x x x x x f x x x
x x x x x x f x x x
f x x x f x x x x f x x x
x x f x x x x x f x x x
?
? ? ?
? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
下面给出 Newton插值法的计算机 算法,开始时,f(k)存放函
数值 f(xk),运算完毕 f(k)存放 k阶差商 f[x0,…,xk]
Newton插值算法
(1) 输入, xi,fi;
(2) di=fi (i=0,1,…,n);
(3) 计算差商
对 i=1,2,…,n 做
(3.1) 对 j=i,i+1,…,n 做
fj=(dj-dj-1)/(xj-xj-i);
(3.2) 对 j=i,i+1,…,n 做 dj=fj;
(4) 计算插值 N(u)
(4.1)输入插值点 u;
(4.2) v=0;
(4.3) 对 i=n,n-1,…,1,0 做 v=v(u-xi)+fi;
(5) 输出 u,v.
五 等距节点的 Newton插值公式与差分
当插值节点 x0,…,xn为等距分布时,Newton插值公式
(6)可以简化,
设插值节点 xj=x0+jh,j=0,1,…,n ; h=(b-a)/n称为步长,且
x0=a,xn=b,令 x=x0+th,则当 x0≤x≤xn时,0≤t≤n,基函数
此时差商也可进一步化简,为此引进 差分的概念,
定义 称 △ f(xi)=f(xi+h)-f(xi)
和 ▽ f(xi)= f(xi)-f(xi-h)
分别 为函数 f(x)在点 xi处的 一阶向前差分 和 一阶向后差分,
0 1 1( ) ( ) ( ) ( )
( 1 ) ( 2 ) ( 1 )
ii
i
x x x x x x x
t t t t i h
? ?? ? ? ?
? ? ? ? ?
一般地,称 k阶差分的差分为 k+1阶差分,如二阶向前和向
后差分分别为
计算各阶差分可按如下差分表进行,
2
2
( ) ( ( ) ) ( ( ) ( ) )
( ) ( )
( 2 ) 2 ( ) ( )
( ) ( ( ) ) ( ( ) ( ) )
( ) ( )
( ) 2 ( ) ( 2 )
i i i i
ii
i i i
i i i i
ii
i i i
f x f x f x h f x
f x h f x
f x h f x h f x
f x f x f x f x h
f x f x h
f x f x h f x h
? ? ? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ?
? ? ? ? ?
23
00
1 1 0
2
2 2 1 0
23
3 3 2 1 0
23
1 2 3 0
n
i i i i i i
n
n n n n n
x f f f f f
xf
x f f
x f f f
x f f f f
x f f f f f
? ? ?
? ? ? ?
?
??
? ? ?
? ? ? ?
向前差分表
差分具有如下性质,,
性质 1(差分与函数值的关系 ) 各阶差分均可表示为函值
fj=f(xj)的线性组合,
性质 2(前差与后差的关系 ):
性质 3(多项式的差分 )若 f(x)∈P n(n次多项式类 ),则
00
( 1 ),( 1 )
!
! ( ) !
kk
k j j k k j j
i k i j k i k i j k
jj
j
k
f C f f C f
k
C
j k j
?
? ? ? ?
??
? ? ? ? ? ?
?
?
??
kki i kff ?? ? ?
,
( ) !,
0,
nk
kn
n
P k n
f x a h n k n
kn
????
?
? ? ??
?
??
其中
性质 4(差分与差商的关系 ):
性质 5(差分与导数的关系
利用这些性质,可将 Newton公式
Nn(x)= f(x0)+(x-x0) f[x0,x1]+(x-x0)(x-x1) f[x0,x1,x2]
+…+( x-x0)…( x-xn-1) f[x0,…,xn]
进一步简化
1
1
[,,,]
!
[,,,]
!
k
i
i i i k k
k
i
i i i k k
f
f x x x
kh
f
f x x x
kh
??
??
?
?
?
?
1
()
! [,,,]
( ),( )
kk
i i i i k
kk
i i k
f k h f x x x
h f x x??
??
?
??
? ? ?
0
2
0 0 0 0
( ) ( )
( 1 ) ( 1 ) ( 1 )
1 ! 2 ! !
nn
n
N x N x th
t t t t t t n
f f f f
n
??
? ? ? ?
? ? ? ? ? ? ? ?(11)
称公式 (11)为 Newton向前差分插值公式,其余项为
1 ( 1 )
0
0
( 1 ) ( )
( ) ( ) ( )
( 1 ) !
(,)
nn
nn
n
t t t n
R x R x th h f
n
xx
?
?
????? ? ?
?
?
(12)
如果将式 (6)改为按节点 xn,xn-1,…,x0的次序排列的 Newton插
值公式,即
1
1 1 1 0
( ) ( ) ( ) [,]
( ) ( ) ( ) [,,]
n n n n n
n n n n
N x f x x x f x x
x x x x x x f x x x
?
??
? ? ? ?
? ? ? ?
令 x=xn-th,则当 x0≤x≤xn时,0≤t≤n.利用差商与向后
差分的关系,式 (13)可简化为
22
( ) ( )
( 1 )
( 1 )
2!
( 1 ) ( ( 1 )
( 1 )
!
n n n
n n n
nn
n
N x N x th
tt
f t f f
t t t n
f
n
??
?
? ? ? ? ? ? ?
? ? ?
? ? ?
(13)
(14)
称式 (14)为 Newton向后差分插值公式,其余项为
( 1 )
11
0
()( ) ( ) ( 1 ) ( 1 ) ( )
( 1 ) !
n
nn
n n n
n
fR x R x th h t t t n
n
xx
?
?
?
??? ? ? ? ? ?
?
??
221 2 0,,,nnn n n n nf f f f f f??? ? ? ? ? ? ? ? ?
若要计算的插值点 x较靠近点 x0,则用向前插值公式 (4.8),
这时 t=(x-x0)/n的值较小,数值稳定性较好,反之,若 x靠近 xn,,,则
用向后插值公式 (14).
利用向前与向后差分的关系 (差分性质 2):
22
12
0
( 1 )
( ) ( ) ( 1 )
2!
( 1 ) ( 1 )
( 1 ),
!
n n n n n n
nn
tt
N x N x t h f t f f
t t t n
f
n
??
?
? ? ? ? ? ? ? ? ?
? ? ?
? ? ?
式 (14)可表示成
(15)
这样,计算靠近 x0或 xn的点的值时,都只需构造向前差分表
例 给定 f(x)在等距节点上的函数值表如下,
xi 0.4 0.6 0.8 1.0
f(xi) 1.5 1.8 2.2 2.8
分别用 Newton向前和向后差分公式,求 f(0.5)及 f(0.9)的近似值,
解 先构造向前差分表如下,
xi fi △ fi △ 2fi △ 3fi
0.4 1.5
0.6 1.8 0.3
0.8 2.2 0.4 0.1
1.0 2.8 0.6 0.2 0.1
x0=0.4,h=0.2,x3=1.0,由 (4.8)和 (4.12),分别用差分表中对角
线上的值和最后一行的值,得 Newton向前和向后插值公式如
下,
3
3
( 1 ) ( 1 ) ( 2)
( 0,4 0,2 ) 1,5 0,3 0,1 0,1
2 3!
( 1 ) ( 1 ) ( 2)
( 1 0,2 ) 2,8 0,6 0,2 0,1
2 3!
t t t t t
N t t
t t t t t
N t t
? ? ?
? ? ? ? ? ? ?
? ? ?
? ? ? ? ? ? ?
(1)
(2)
当 x=0.5时,用公式 (1),这时 t=(x-x0)/h=0.5,将 t=0.5代入 (1),得
f (0.5)≈N3(0.5)=1.64375.
当 x=0.9时,用公式 (2),这时 t=(x3-x)/h=0.5,将 t=0.5代入 (2),得
f (0.9)≈N3(0.9)=2.46875.
课后练习题
P217,第 2题,第 4题,
P219,第 11题,
