§ 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
1 1 0 1 0
1 0
1 1 1 0
1 0
],,...,[ ],,...,[
],,...,[ ],...,,[ ],...,[
?
? ? ?
?
?
?
?
? ?
?
? ?
k k
k k k k
k
k k k
k
x x
x x x f x x x f
x x
x x x f x x x f x x f
(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 */
i i i f f f ? ? ? ? 1
i
k
i
k
i
k
i
k f f f f 1
1
1 1 ) ( ?
?
? ? ? ? ? ? ? ? ? ?
向后差分
/* backward
difference */ 1 1 1 ? ? ? ? ? ? ? ? i k i k i k f f f
i?1 i i f f f ? ? ?
中心差分
/* 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
j k n
j
k
n f
j
n f
0
) 1 ( ?
? ? ?
? ? ? ? n
j n j k
j n
k
n f
j
n f
0
) 1 (
!
)1),,, (1(
j
jnnn
j
n ??????
?
???
?
?其中 /* binomial coefficients */
? 函数值可由差分值算出,k j
n
j
k n f j
n f ? ?
?
? ?
0
? k
k
k h k
f x x f
! ],...,[
0
0
? ?
k
n
k
k n n n h k
f x x x f
! ],...,,[ 1
? ?
? ? k
k
k
h
f f 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 x f k
t h t x N x N k n
k
n n ? ? ? ? ?
?
),(,)),,, (1()!1( )()( 01)1( nnnn xxhntttnfxR ????? ?? ??
设 htxx
n ??
，则 ) ( ) 1 ( ) ( ) (
0
n
k
n
k
k
n n n x f k
t h t x N x N ? ? ? ? ? ? ?
?
注,一般当 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 1 3 ) ( ) ( ) ( ) ( ) (
? 0 i i i
x h x1 f ’ x h x f x P ?
h0(x) 有根 x1,x2,且 h0’(x1) = 0 ? x1 是重根。 ) ( ) ( ) ( 2
2
1 0 0 x x x x C x h ? ? ?
又, h0(x0) = 1 ? C0
)()(
)()()(
20
2
10
2
2
10
xxxx
xxxxxh
??
???
h2(x)
h1(x) 有根 x0,x2 ? ) )( )( ( ) ( 2 0 1 x x x x B Ax x h ? ? ? ?
由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。
与 h0(x) 完全类似。
(x) ? h1 有根 x0,x1,x2 ? ? h1 ) )( )( ( ) (
2 1 0 1 x x x x x x C x ? ? ? ? ?
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 ) ( ) ( ) (
? 0 i
i x h x h yi x H2n+1
? ? n
? 0 i
yi’
其中 hi(xj) = ?ij,hi’(xj) = 0,(xj) = 0,’(xj) = ?ij ? hi ? hi
hi(x) 有根 x0,…,xi,…,xn且都是 2重根 ? ? ) ( ) ( ) ( 2 x l B x A x h i i i i ? ?
?
? ?
??
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 ) ( ) ( i i li2(x) x x C x ? ?
? h
i 又, ’(xi) = 1 ? Ci = 1
? h
i ) ( x ) ( i li2(x) x x ? ?
设 ],[,.,, 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)的图像？ ?
x 0
-
- 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
1 1 0 1 0
1 0
1 1 1 0
1 0
],,...,[ ],,...,[
],,...,[ ],...,,[ ],...,[
?
? ? ?
?
?
?
?
? ?
?
? ?
k k
k k k k
k
k k k
k
x x
x x x f x x x f
x x
x x x f x x x f x x f
(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 */
i i i f f f ? ? ? ? 1
i
k
i
k
i
k
i
k f f f f 1
1
1 1 ) ( ?
?
? ? ? ? ? ? ? ? ? ?
向后差分
/* backward
difference */ 1 1 1 ? ? ? ? ? ? ? ? i k i k i k f f f
i?1 i i f f f ? ? ?
中心差分
/* 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
j k n
j
k
n f
j
n f
0
) 1 ( ?
? ? ?
? ? ? ? n
j n j k
j n
k
n f
j
n f
0
) 1 (
!
)1),,, (1(
j
jnnn
j
n ??????
?
???
?
?其中 /* binomial coefficients */
? 函数值可由差分值算出,k j
n
j
k n f j
n f ? ?
?
? ?
0
? k
k
k h k
f x x f
! ],...,[
0
0
? ?
k
n
k
k n n n h k
f x x x f
! ],...,,[ 1
? ?
? ? k
k
k
h
f f 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 x f k
t h t x N x N k n
k
n n ? ? ? ? ?
?
),(,)),,, (1()!1( )()( 01)1( nnnn xxhntttnfxR ????? ?? ??
设 htxx
n ??
，则 ) ( ) 1 ( ) ( ) (
0
n
k
n
k
k
n n n x f k
t h t x N x N ? ? ? ? ? ? ?
?
注,一般当 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 1 3 ) ( ) ( ) ( ) ( ) (
? 0 i i i
x h x1 f ’ x h x f x P ?
h0(x) 有根 x1,x2,且 h0’(x1) = 0 ? x1 是重根。 ) ( ) ( ) ( 2
2
1 0 0 x x x x C x h ? ? ?
又, h0(x0) = 1 ? C0
)()(
)()()(
20
2
10
2
2
10
xxxx
xxxxxh
??
???
h2(x)
h1(x) 有根 x0,x2 ? ) )( )( ( ) ( 2 0 1 x x x x B Ax x h ? ? ? ?
由余下条件 h1(x1) = 1 和 h1’(x1) = 0 可解。
与 h0(x) 完全类似。
(x) ? h1 有根 x0,x1,x2 ? ? h1 ) )( )( ( ) (
2 1 0 1 x x x x x x C x ? ? ? ? ?
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 ) ( ) ( ) (
? 0 i
i x h x h yi x H2n+1
? ? n
? 0 i
yi’
其中 hi(xj) = ?ij,hi’(xj) = 0,(xj) = 0,’(xj) = ?ij ? hi ? hi
hi(x) 有根 x0,…,xi,…,xn且都是 2重根 ? ? ) ( ) ( ) ( 2 x l B x A x h i i i i ? ?
?
? ?
??
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 ) ( ) ( i i li2(x) x x C x ? ?
? h
i 又, ’(xi) = 1 ? Ci = 1
? h
i ) ( x ) ( i li2(x) x x ? ?
设 ],[,.,, 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)的图像？ ?
x 0
-
- 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 …
