§ 2 牛顿插值 /* Newton’s Interpolation */
Lagrange 插值虽然易算，但若要增加一个节点时，
全部基函数 li(x) 都需重新算过。
将 Ln(x) 改写成,..))(()( 102010 xxxxaxxaa
)),,,(( 10 nn xxxxa 的形式，希望每加一个节点时，
只附加一项 上去即可。
差商 (亦称均差 ) /* divided difference */
),()()(],[ ji
ji
ji
ji xxjixx
xfxfxxf
1阶差商 /* the 1st
divided difference of f
w.r.t,xi and xj */
)(],[],[],,[ kixx xxfxxfxxxf
ki
kjji
kji
2阶差商
§ 2 Newton’s Interpolation
1
11010
10
1110
10
],,...,[],,...,[
],,...,[],...,,[],...,[
kk
kkkk
k
kkk
k
xx
xxxfxxxf
xx
xxxfxxxfxxf
(k+1)阶差商：
k
i ik
i
k x
xfxxf
0 1
0 )(
)(],...,[
事实上其中
,)()(
0
1?
k
i
ik xxx
k
ij
j
jiik xxx
0
1 )()(?
Warning,my head is exploding…
What is the point of this formula?差商的值与 xi 的顺序无关！
§ 2 Newton’s Interpolation
牛顿插值 /* Newton’s Interpolation */
],[)()()( 000 xxfxxxfxf
],,[)(],[],[ 101100 xxxfxxxxfxxf
],...,,[)(],...,[],...,,[ 0010 nnnn xxxfxxxxfxxxf
)),,,((...))(()()( 10102010 nnn xxxxaxxxxaxxaaxN
1
2
… … … …
n?1
1 + (x? x0)? 2 + … … + ( x? x0)…( x? xn?1)? n?1
.,,))(](,,[)](,[)()( 102100100 xxxxxxxfxxxxfxfxf
)),,,(](,...,[ 100 nn xxxxxxf
))(),,,(](,.,,,,[ 100 nnn xxxxxxxxxf
Nn(x) R
n(x)
ai = f [ x0,…,xi ]
§ 2 Newton’s Interpolation
注,?由 唯一性可知 Nn(x)? Ln(x),只是算法不同，故其余项也相同，即
)(!)1( )()(],.,,,,[ 1
)1(
10 xn
fxxxxf
k
x
n
kn?
),(,! )(],...,[ m a xm i n)(0 xxkfxxf kk
实际计算过程为
f (x0)
f (x1)
f (x2)
…
f (xn?1)
f (xn)
f [x0,x1]
f [x1,x2]
… …
… …
f [xn?1,xn]
f [x0,x1,x2]
… …
… …
f [xn?2,xn?1,xn] f [x0,…,xn]
f (xn+1) f [xn,xn+1] f [xn?1,xn,xn+1] f [x1,…,xn+1] f [x0,…,xn+1]
HW,
p.112 #4
§ 2 Newton’s Interpolation
等距节点公式 /* Formulae with Equal Spacing */
向前差分
/* forward
difference */
iii fff1
i
k
i
k
i
k
i
k ffff 1
1
11 )(?
向后差分
/* backward
difference */ 111 ikikik fff
i?1ii fff
中心差分
/* centered
difference */
2121
11 ikikik fff
其中 )(
221 hii xff
当节点 等距 分布时,),.,,,0(0 nihixx i
More given on p.113-114.
§ 2 Newton’s Interpolation
差分的重要性质：
线性：例如
gbfaxgbxfa ))()((
若 f (x)是 m 次多项式，则 是 次多项式，而
)0()( mkxfk km?
)(0)( mkxfk
差分值可由函数值算出：
n
j
jkn
j
k
n f
j
nf
0
)1(?
n
j njk
jn
k
n f
j
nf
0
)1(
!
)1),,,(1(
j
jnnn
j
n
其中 /* binomial coefficients */
函数值可由差分值算出,kj
n
j
kn fj
nf
0
k
k
k hk
fxxf
!],...,[
0
0
k
n
k
knnn hk
fxxxf
!],...,,[ 1
k
k
k
h
ff 0)( )(
由 Rn 表达式
§ 2 Newton’s Interpolation
牛顿公式 )),,,(](,...,[...)](,[)()( 1000100 nnn xxxxxxfxxxxfxfxN
牛顿前差公式 /* Newton’s forward-difference formula */
牛顿后差公式 /* Newton’s backward-difference formula */
将节点顺序倒置：
)),,,(](,...,[...)](,[)()( 101 xxxxxxfxxxxfxfxN nnnnnnn
设 htxx
0
，则 )()()( 0
0
0 xfk
thtxNxN kn
k
nn
),(,)),,,(1()!1( )()( 01)1( nnnn xxhntttnfxR
设 htxx
n
，则 )()1()()(
0
n
k
n
k
k
nnn xfk
thtxNxN
注,一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为 表初公式 和 表末公式 。
§ 3 厄米插值 /* Hermite Interpolation */
不仅要求函数值重合，而且要求若干阶 导数 也重合。
即：要求插值函数? (x) 满足?(xi) = f (xi),?’ (xi) = f ’ (xi),
…,?(mi) (xi) = f (mi) (xi).
注,?N 个条件可以确定 阶多项式。N? 1
要求在 1个节点 x0 处直到 m0阶导数都重合的插值多项式即为 Taylor多项式
0
0 )(
!
)(...))(()()(
00 0
)(
000
mm xxm xfxxxfxfx
其余项为
)1(
0
0
)1(
0
0 )(
)!1(
)()()()(
mm xx
m
fxxfxR
一般只考虑 f 与 f ’的值。
§ 3 Hermite Interpolation
例,设 x0? x1? x2,已知 f(x0),f(x1),f(x2) 和 f ’(x1),求多项式 P(x)
满足 P(xi) = f (xi),i = 0,1,2,且 P’(x1) = f ’(x1),并估计误差。
模仿 Lagrange 多项式的思想，设解,首先,P的阶数 = 3
2 13 )()()()()(
0i ii
xhx1f ’xhxfxP?
h0(x) 有根 x1,x2,且 h0’(x1) = 0? x1 是重根。 )()()( 2
2
100 xxxxCxh
又,h0(x0) = 1? C0
)()(
)()()(
20
2
10
2
2
10
xxxx
xxxxxh
h2(x)
h1(x) 有根 x0,x2? ))()(()( 201 xxxxBAxxh
由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。
与 h0(x) 完全类似。
(x)?h1 有根 x0,x1,x2h1 ))()(()(
2101 xxxxxxCx
h1又,’(x1) = 1? C1 可解。
其中 hi(xj) =?ij,hi’(x1) = 0,(xi) = 0,’(x1) = 1?h1?h1
),())()(()()()( 221033 xxxxxxxKxPxfxR !4 )()( )4(fxK
与 Lagrange 分析完全类似
§ 3 Hermite Interpolation
一般地，已知 x0,…,xn 处有 y0,…,yn 和 y0’,…,yn’,求 H2n+1(x)
满足 H2n+1(xi) = yi,H’2n+1(xi) = yi’。
解,设 n i )()()(
0i
i xhxhyixH2n+1
n
0i
yi’
其中 hi(xj) =?ij,hi’(xj) = 0,(xj) = 0,’(xj) =?ij?hi?hi
hi(x) 有根 x0,…,xi,…,xn且都是 2重根 )()()( 2 xlBxAxh iiii
ij ji
j
i xx
xxxl
)(
)()(
由余下条件 hi(xi) = 1 和 hi’(xi) = 0 可解 Ai 和 Bi?
)()])((21[)( 2 xlxxxlxh iiiii
(x)?hi 有根 x0,…,xn,除了 xi外都是 2重根hi )()( ii li2(x)xxCx
h
i又,’(xi) = 1? Ci = 1
h
i )(x )( i li2(x)xx
设 ],[,.,,210 baCfbxxxa nn 则 2
0
)22(
)()!22( )()(
n
i
i
x
n
n xxn
fxR?
这样的 Hermite 插值唯一
§ 3 Hermite Interpolation
Quiz,给定 xi = i +1,i = 0,1,2,3,4,5,下面哪个是 h2(x)的图像？
x0
-
-1
0.5
1 2 3 4 5 6
y
x
y
0
-
-
-1
0.5
1 2 3 4 5 6
斜率 =1?
求 Hermite多项式的基本步骤：
写出相应于条件的 hi(x),hi(x) 的组合形式；?
对每一个 hi(x),hi(x) 找出尽可能多的条件给出的根；?
根据多项式的总阶数和根的个数写出表达式；
根据尚未利用的条件解出表达式中的待定系数；
最后完整写出 H(x)。
HW,p.120-121
#1,#2,#3
§ 4 分段低次插值 /* piecewise polynomial approximation */
Remember what I have said?
Increasing the degree of interpolating polynomial
will NOT guarantee a good result,
since high-degree polynomials are
oscillating.
例,在 [?5,5]上考察 的 Ln(x)。取
21
1)(
xxf ),.,,,0(105 niinx i
-5 -4 -3 -2 -1 0 1 2 3 4 5-0.5
0
0.5
1
1.5
2
2.5
n 越大，
端点附近抖动越大，称为
Runge 现象
Ln(x)? f (x)?
分段 低次 插值
§ 4 Piecewise Polynomial Approximation
分段线性插值 /* piecewise linear interpolation */
在每个区间 上，用 1阶多项式 (直线 ) 逼近 f (x):],[ 1?ii xx
11111 )()(
iii iiii i yxx
xxy
xx
xxxPxf ],[f o r
1 ii xxx
记,易证：当 时，||m a x
1 ii xxh 0?h )()(1 xfxP h?
一致失去了原函数的光滑性。
分段 Hermite插值 /* Hermite piecewise polynomials */
给定
nnn yyyyxx,...,;,...,;,...,000
在 上利用两点的 y 及 y’ 构造 3次 Hermite函数],[ 1?ii xx
导数一般不易得到。
How can we make a smooth
interpolation without asking
too much from f?
Headache …
Lagrange 插值虽然易算，但若要增加一个节点时，
全部基函数 li(x) 都需重新算过。
将 Ln(x) 改写成,..))(()( 102010 xxxxaxxaa
)),,,(( 10 nn xxxxa 的形式，希望每加一个节点时，
只附加一项 上去即可。
差商 (亦称均差 ) /* divided difference */
),()()(],[ ji
ji
ji
ji xxjixx
xfxfxxf
1阶差商 /* the 1st
divided difference of f
w.r.t,xi and xj */
)(],[],[],,[ kixx xxfxxfxxxf
ki
kjji
kji
2阶差商
§ 2 Newton’s Interpolation
1
11010
10
1110
10
],,...,[],,...,[
],,...,[],...,,[],...,[
kk
kkkk
k
kkk
k
xx
xxxfxxxf
xx
xxxfxxxfxxf
(k+1)阶差商：
k
i ik
i
k x
xfxxf
0 1
0 )(
)(],...,[
事实上其中
,)()(
0
1?
k
i
ik xxx
k
ij
j
jiik xxx
0
1 )()(?
Warning,my head is exploding…
What is the point of this formula?差商的值与 xi 的顺序无关！
§ 2 Newton’s Interpolation
牛顿插值 /* Newton’s Interpolation */
],[)()()( 000 xxfxxxfxf
],,[)(],[],[ 101100 xxxfxxxxfxxf
],...,,[)(],...,[],...,,[ 0010 nnnn xxxfxxxxfxxxf
)),,,((...))(()()( 10102010 nnn xxxxaxxxxaxxaaxN
1
2
… … … …
n?1
1 + (x? x0)? 2 + … … + ( x? x0)…( x? xn?1)? n?1
.,,))(](,,[)](,[)()( 102100100 xxxxxxxfxxxxfxfxf
)),,,(](,...,[ 100 nn xxxxxxf
))(),,,(](,.,,,,[ 100 nnn xxxxxxxxxf
Nn(x) R
n(x)
ai = f [ x0,…,xi ]
§ 2 Newton’s Interpolation
注,?由 唯一性可知 Nn(x)? Ln(x),只是算法不同，故其余项也相同，即
)(!)1( )()(],.,,,,[ 1
)1(
10 xn
fxxxxf
k
x
n
kn?
),(,! )(],...,[ m a xm i n)(0 xxkfxxf kk
实际计算过程为
f (x0)
f (x1)
f (x2)
…
f (xn?1)
f (xn)
f [x0,x1]
f [x1,x2]
… …
… …
f [xn?1,xn]
f [x0,x1,x2]
… …
… …
f [xn?2,xn?1,xn] f [x0,…,xn]
f (xn+1) f [xn,xn+1] f [xn?1,xn,xn+1] f [x1,…,xn+1] f [x0,…,xn+1]
HW,
p.112 #4
§ 2 Newton’s Interpolation
等距节点公式 /* Formulae with Equal Spacing */
向前差分
/* forward
difference */
iii fff1
i
k
i
k
i
k
i
k ffff 1
1
11 )(?
向后差分
/* backward
difference */ 111 ikikik fff
i?1ii fff
中心差分
/* centered
difference */
2121
11 ikikik fff
其中 )(
221 hii xff
当节点 等距 分布时,),.,,,0(0 nihixx i
More given on p.113-114.
§ 2 Newton’s Interpolation
差分的重要性质：
线性：例如
gbfaxgbxfa ))()((
若 f (x)是 m 次多项式，则 是 次多项式，而
)0()( mkxfk km?
)(0)( mkxfk
差分值可由函数值算出：
n
j
jkn
j
k
n f
j
nf
0
)1(?
n
j njk
jn
k
n f
j
nf
0
)1(
!
)1),,,(1(
j
jnnn
j
n
其中 /* binomial coefficients */
函数值可由差分值算出,kj
n
j
kn fj
nf
0
k
k
k hk
fxxf
!],...,[
0
0
k
n
k
knnn hk
fxxxf
!],...,,[ 1
k
k
k
h
ff 0)( )(
由 Rn 表达式
§ 2 Newton’s Interpolation
牛顿公式 )),,,(](,...,[...)](,[)()( 1000100 nnn xxxxxxfxxxxfxfxN
牛顿前差公式 /* Newton’s forward-difference formula */
牛顿后差公式 /* Newton’s backward-difference formula */
将节点顺序倒置：
)),,,(](,...,[...)](,[)()( 101 xxxxxxfxxxxfxfxN nnnnnnn
设 htxx
0
，则 )()()( 0
0
0 xfk
thtxNxN kn
k
nn
),(,)),,,(1()!1( )()( 01)1( nnnn xxhntttnfxR
设 htxx
n
，则 )()1()()(
0
n
k
n
k
k
nnn xfk
thtxNxN
注,一般当 x 靠近 x0 时用前插，靠近 xn 时用后插，故两种公式亦称为 表初公式 和 表末公式 。
§ 3 厄米插值 /* Hermite Interpolation */
不仅要求函数值重合，而且要求若干阶 导数 也重合。
即：要求插值函数? (x) 满足?(xi) = f (xi),?’ (xi) = f ’ (xi),
…,?(mi) (xi) = f (mi) (xi).
注,?N 个条件可以确定 阶多项式。N? 1
要求在 1个节点 x0 处直到 m0阶导数都重合的插值多项式即为 Taylor多项式
0
0 )(
!
)(...))(()()(
00 0
)(
000
mm xxm xfxxxfxfx
其余项为
)1(
0
0
)1(
0
0 )(
)!1(
)()()()(
mm xx
m
fxxfxR
一般只考虑 f 与 f ’的值。
§ 3 Hermite Interpolation
例,设 x0? x1? x2,已知 f(x0),f(x1),f(x2) 和 f ’(x1),求多项式 P(x)
满足 P(xi) = f (xi),i = 0,1,2,且 P’(x1) = f ’(x1),并估计误差。
模仿 Lagrange 多项式的思想，设解,首先,P的阶数 = 3
2 13 )()()()()(
0i ii
xhx1f ’xhxfxP?
h0(x) 有根 x1,x2,且 h0’(x1) = 0? x1 是重根。 )()()( 2
2
100 xxxxCxh
又,h0(x0) = 1? C0
)()(
)()()(
20
2
10
2
2
10
xxxx
xxxxxh
h2(x)
h1(x) 有根 x0,x2? ))()(()( 201 xxxxBAxxh
由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。
与 h0(x) 完全类似。
(x)?h1 有根 x0,x1,x2h1 ))()(()(
2101 xxxxxxCx
h1又,’(x1) = 1? C1 可解。
其中 hi(xj) =?ij,hi’(x1) = 0,(xi) = 0,’(x1) = 1?h1?h1
),())()(()()()( 221033 xxxxxxxKxPxfxR !4 )()( )4(fxK
与 Lagrange 分析完全类似
§ 3 Hermite Interpolation
一般地，已知 x0,…,xn 处有 y0,…,yn 和 y0’,…,yn’,求 H2n+1(x)
满足 H2n+1(xi) = yi,H’2n+1(xi) = yi’。
解,设 n i )()()(
0i
i xhxhyixH2n+1
n
0i
yi’
其中 hi(xj) =?ij,hi’(xj) = 0,(xj) = 0,’(xj) =?ij?hi?hi
hi(x) 有根 x0,…,xi,…,xn且都是 2重根 )()()( 2 xlBxAxh iiii
ij ji
j
i xx
xxxl
)(
)()(
由余下条件 hi(xi) = 1 和 hi’(xi) = 0 可解 Ai 和 Bi?
)()])((21[)( 2 xlxxxlxh iiiii
(x)?hi 有根 x0,…,xn,除了 xi外都是 2重根hi )()( ii li2(x)xxCx
h
i又,’(xi) = 1? Ci = 1
h
i )(x )( i li2(x)xx
设 ],[,.,,210 baCfbxxxa nn 则 2
0
)22(
)()!22( )()(
n
i
i
x
n
n xxn
fxR?
这样的 Hermite 插值唯一
§ 3 Hermite Interpolation
Quiz,给定 xi = i +1,i = 0,1,2,3,4,5,下面哪个是 h2(x)的图像？
x0
-
-1
0.5
1 2 3 4 5 6
y
x
y
0
-
-
-1
0.5
1 2 3 4 5 6
斜率 =1?
求 Hermite多项式的基本步骤：
写出相应于条件的 hi(x),hi(x) 的组合形式；?
对每一个 hi(x),hi(x) 找出尽可能多的条件给出的根；?
根据多项式的总阶数和根的个数写出表达式；
根据尚未利用的条件解出表达式中的待定系数；
最后完整写出 H(x)。
HW,p.120-121
#1,#2,#3
§ 4 分段低次插值 /* piecewise polynomial approximation */
Remember what I have said?
Increasing the degree of interpolating polynomial
will NOT guarantee a good result,
since high-degree polynomials are
oscillating.
例,在 [?5,5]上考察 的 Ln(x)。取
21
1)(
xxf ),.,,,0(105 niinx i
-5 -4 -3 -2 -1 0 1 2 3 4 5-0.5
0
0.5
1
1.5
2
2.5
n 越大，
端点附近抖动越大，称为
Runge 现象
Ln(x)? f (x)?
分段 低次 插值
§ 4 Piecewise Polynomial Approximation
分段线性插值 /* piecewise linear interpolation */
在每个区间 上，用 1阶多项式 (直线 ) 逼近 f (x):],[ 1?ii xx
11111 )()(
iii iiii i yxx
xxy
xx
xxxPxf ],[f o r
1 ii xxx
记,易证：当 时，||m a x
1 ii xxh 0?h )()(1 xfxP h?
一致失去了原函数的光滑性。
分段 Hermite插值 /* Hermite piecewise polynomials */
给定
nnn yyyyxx,...,;,...,;,...,000
在 上利用两点的 y 及 y’ 构造 3次 Hermite函数],[ 1?ii xx
导数一般不易得到。
How can we make a smooth
interpolation without asking
too much from f?
Headache …
