第二章 插值方法 /* Interpolation */
引言表示两个变量x,y内在关系一般由函数式y=f(x)表达但在实际问题中 有两种情况
1 由实验观测而得的一组离散数据(函数表) 显然这种函数关系式y=f(x)存在且连续 但未知
2 函数解析表达式已知 但计算复杂 不便使用 通常也函数表 如 y=sin(x),y=lg(x)
有时要求不在表上的函数值 怎么办引言
y
0
y
1
… y
n
x
0
x
1
… x
n
y
x
已知 f(x)的的函数表办法是 根据所给的y=f(x)的函数表构造一个简单的连续函数g(x)近似代替f(x)
Def g(x)为逼近函数 f(x)为被逼近函数近似代替即逼近的方法有很多种 通常是 插值方法求g(x)使 g(x
i
) =y
i
i=0,1,2,3 …n.
Def g(x)为f(x)的插值函数 f(x)为被插值函数引言构造g(x)的方法 有一 逼近 方逼近 数据
简单函数g(x) 用 算计算的函数如 有 函数( 式函数) 多 式 多 式
g(x)为多 式时 插值方法 为代数多 式插值 插值数g(x)为插值多 式
章 要 多 式插值的 方法
在实 中 用很
Def n+1个?x
1
,x
2
,…,x
n
为插值￠?
￡所在?￥[a,b]为插值?￥ (2.2)式为插值?§
Problem I 已知y=f(x)的函数表
…
2
n
n
01 2 n
=a +a x+a x + +a x (P(x) 2.1)
…
ni i
P (x )=y i=0,1,,n (2.2)
y
0
y
1
… y
n
x
0
x
1
… x
n
y
x
插值?￥
插值?§
且x
i
(i=0,1,…,n)两两
x
i
[a,b]
求currency1数不'“n的多 式使得
x
0
x
1
x
2
x
3
x
4
x
f(x) ≈P
n
(x)
多 式插值问题的fi
多 式P
n
(x) ￡fl,给–的y=f(x)的
n+1个?(x
i
,y
i
) i=0,1,2,…,n.
插值多 式的?一?
· Problem I中的P
n
(x)是?存在 存在是一 如?求显然 关?是求P
n
(x) 的系数a
0
,a
1
,…,a
n
.
– 2.1 在n+1个 的插值x
1
,x
2
,…,x
n
上?”插值?§
(2.2)的currency1数不'“n的代数多 式P
n
(x)存在且?一
…
ni i
P (x )=y i=0,1,,n (2.2)
…
2
n
n
01 2 n
=a +a x+a x + +a x (P(x) 2.1)
析 为求
要?…插值?§
– 2.1的‰
‰ 由插值?§ 有
…
…
"
…
2n
n0 0 10 20 n0 0
2n
n1 0 11 21 n1 1
2n
nn 0 1n 2n nn n
P(x )=a +ax +ax + +ax =y
P(x)=a +ax +ax + +ax =y
P(x)=a +ax +ax + +ax =y
关 未知量 的
currency1?方`组
…
01 n
a,a,,a
(2.3)
￡系数′?的?ˉ式为
…
…
…
…
2n
00 0
2n
11 1
2n
nn n
1x x x
1x x x
1x x x
(,)
ij
ijxx≠≠∵
∴
∴
…
01 n
a,a,,a
方`组(2.3)的解 存在且?一插值多 式 存在且?一
…
n01 n
=V(x,x,,x )
∏∏
ni-1
ij
i=1 j=0
=(x-x)
≠ 0
˙ ˙ 给–f(x)的函数表 求f(x)的currency1数不'“3的插值多 式
-7 7 4 35
-1 1 2 5
y
x
=
1
2
3
0
a1-1 1 -1 -7
a11 1 1 7
a12 4 8 -4
a1 5 25 125 35
解 ¨P
3
(x)=a
0
+a
1
x+a
2
x
2
+a
3
x
3
解方`组得 a
0
=10,a
1
=5,a
2
=-10,a
3
=2
即P
3
(x)=10+5x-10x
2
+2x
3
n=20,在 10
8
currency1/ 的计算?上计算
2.2 Lagrange 插值—— ˇ插值
析,两?(x
0
,y
0
),(x
1
,y
1
)— y=P
1
(x)—— ˇ插值
10
00
10
-
(- )
-
yy
yy xx
xx
=
y
0
y
1
x
0
x
1
y
x
Problem 2.1 已知函数y=f(x)的函数表求currency1数不'“1的多 式P
1
(x)=a
0
+a
1
x
”插值?§ P
1
(x
0
)=y
0
,P
1
(x
1
)=y
1
l
0
(x) l
1
(x)
Σ
=
=
1
0
)(
i
ii
yxl
01
01
01 10
--
(),()
--
xxxx
lx lx
xx xx
==
为 ˇ插值 函数而P
1
(x)是 的?组
01
() () 1lx lx+=
00 01
10 11
() 1,() 0
() 0,() 1
lx lx
lx lx
==
1
,0,1
0
ij ij
ij
lx ij
ij
δ
=
== =
≠
δ
ij
/* Kronecker Delta */
解 由? 式方`
00
10 1 0
10 10
--
() -
--
xx xx
yPx y y y
xx xx
==+
01
10
01 10
--
()
--
xxxx
Px y y
xx xx
=+
ˇ插值解 已知(x
0
,y
0
)= (2.71,0.4330),(x
1
,y
1
)=(2.72,0.4364)
用?插值
1
x -2.72 x -2.71
P (x)= *0.4330+ *0.4346
2.71-2.72 2.72-2.71
2.2已知lg2.71=0.4330,lg2.72=0.4364.求y=lg2.718.
析 ·y=lgx,给 两?(2.71,0.4330)=(x
0
,y
0
),
(2.72,0.4364)=(x
1
,y
1
)
为求lg2.718构造简单的插值多 式—为lgx的近似
∴≈
1
lg2.718 P (2.718)=0.43428
=0.16x -0.0006
∴≈
1
lgx P (x)
2.2.2 插值
用?插值法·函数y=f(x)?
逼近时 即用 y=P
1
(x)代替fl
y=f(x)
y
x
0
x
1
x
显然 插值?￥ fl [x
0
,x
1
] 变
时?插值的?很
为 a这种? 用简单的fl ( )
近似代替复杂fl y=f(x) 二currency1多 式函数的fl
为 所 构造插值函数P
2
(x) 即n=2
插值
Problem2.2 已知y=f(x)的函数表 x
0
,x
1
,x
2
为 ￠? 求一个currency1数不'“2的多 式
P
2
(x)=a
0
+a
1
x+a
2
x
2
P
2
(x
0
)=y
0
,P
2
(x
1
)=y
1
,P
2
(x
2
)=y
2
y
0
y
1
y
2
x
0
x
1
x
2
y
x
fi P
2
(x)为,?(x
0
,y
0
),(x
1
,y
1
),(x
2
,y
2
)的
方法 函数法 构造 函数l
0
(x),l
1
(x),l
2
(x) 个二currency1式使P
2
(x)= y
0
l
0
(x)+y
1
l
1
(x)+y
2
l
2
(x)?”插值?§
(),0,1,2lx ij
ij ij
δ= =
()1,()0,()0
00 01 02
()0,()1,()0
10 11 12
( ) 0,( ) 0,( ) 1
20 21 22
lx lx lx
lx lx lx
lx lx lx
= = =
= = =
= = =
$%%%%%%&%%%%%%’
插值求二currency1多 式l
0
(x) l
0
(x
0
)=1 l
0
(x
1
)=0 l
0
(x
2
)=0
<=> l
0
(x) C(x-x
1
)(x-x
2
)求C=?
法求得 l
1
(x) l
2
(x) 即 插值的插值 函数如o
由l
0
(x
0
)=1 得 C(x
0
-x
1
)(x
0
-x
2
)=1
C=1/(x
0
-x
1
)(x
0
-x
2
)
插值问题Problem 2.2的解
02 0112
20 1 2
0102 1012 20 21
(- )(- ) (- )(- )(- )(- )
()
(-)(-) (-)(-) (-)(-)
xx xx xx xxxx xx
Px y y y
xxxx xxxx xxxx
=++
12
0
0102
(- )(- )
()
(-)(-)
xx xx
lx
xxxx
=
()
2
(- )(- ) (- )(- )(- )(- )
02 0112
,(),
1
(-)(-) (-)(-) (-)(-)
0102 1012 2021
lx
xx xx xx xxxx xx
ll
xxxx xxxx xxxx
==(x) =
0
2.2.3 Lagrange插值 式
函数法 求n+1个ncurrency1多 式 l
0
(x),l
1
(x),…,l
n
(x) 使
P
n
(x)=y
0
l
0
(x)+y
1
l
1
(x)+…+y
n
l
n
(x).
P
n
(x)”插值?§ P
n
(x
j
)=y
j
j=0,1,2,3,…,n
即y
0
l
0
(x
j
)+y
1
l
1
(x
j
)+…+yjlj(xj) …+y
n
l
n
(x
j
) = y
j
Problem2.3 已知y=f(x)在两两 ￠?x
0
,x
1
,…,x
n
的函数值
y
1
,y
2
,…,y
n
,求ncurrency1多 式 P
n
(x)=a
0
+a
1
x+a
2
x
2
+…+a
n
x
n
”插值?§P
n
(x
j
)=y
j
,j=0,1,2,3,…,n
()0,()0,,,()0
01
0,1
(
,2
)1
,,
lx lx lx
jj njj
jn
lx
j
= =, =
=
=
$%%%%%%%%%%&%%%%%%%%%%’
1
(),0,1,2,,
0
j
lx j n
kj kj
j
κ
δκ
κ
=
== =?
≠
Lagrange插值 式
l
k
(x
0
)=0,…,l
k
(x
k-1
)=0,l
k
(x
k+1
)=0,…,l
k
(x
n
)=0
即l
k
(x)有n个0?x
0
,x
1
,…,x
k-1
,x
k+1
,…,x
n
l
k
(x)=C(x-x
0
)…(x-x
k-1
)(x-x
k+1
)…(x-x
n
) l
k
(x
k
)=1
C(x
k
-x
0
)…(x
k
-x
k-1
)(x
k
-x
k+1
)…(x
k
-x
n
)=1
1
C∴
((
k0 kk-1kk+1 kn
=
(x - x ) (x - x )(x - x ) (x - x )
≠
∴=
∏
n
j
0kk n
k
j=0,j k
k0 kk-1kk+1 kn kj
x-x
(x-x ) (x-x )(x-x ) (x-x )
l(x)=
(x - x ) (x - x )(x - x ) (x - x ) x - x
≠
∴
∑∑∏
nnn
j
nkkk
k=0 k=0 j=0,j k
k j
x-x
P (x)= y l (x)= y ( )
x-x
上式即为Lagrange插值多 式
Lagrange插值 式 n=1 n=2时 是 ˇ插值
插值 式
￠?有关 而 f 关
2.2.4 插值? /* Remainder */
函数y=f(x) ￡ Lagrange插值多 式P
n
(x)
(1) P
n
(x
i
)= f(x
i
) =y
i
,i=0,1,2,…,n
(2) 而· 插值?￥[a,b]内插值￠?x
i
(i=1,2,…,n) 的?x,
一般P
n
(x) f(x) 存在?
Def,Rn(x)=f(x)-Pn(x)为Pn(x)的? 插值?
1 => Rn(x
i
)=0,i=0,1,2,…,n
(2) =>?x x
i
,可能 Rn(x) 0,
用Lagrange插值 式Pn(x) 计算? 是 要
Rn(x)是?”?a
Rn(x)=
¨￠?
)1( +n
f
在[a,b]内存在,
() () ()Rx fx Px
nn
=?
],[ baCf
n
∈
bxxxa
n
≤<<<≤ (
10
且f?”?§,
Rolle’s Theorem,?
存在 使得
)(x?
0)()(
10
== xx
),(
10
xx∈ξ
0)( =
′′′
ξ?
0)()()(
210
=== xxx
),(),,(
211100
xxxx ∈∈ ξξ
使得
0)()(
10
=
′′′
=
′′′
ξ?ξ? ),(
10
ξξξ∈
使得
0)( =
′′′′′′
ξ?
0)()(
0
===
n
xx (
存在
),( ba∈ξ
使得
0)(
)(
=ξ?
n
R
n
(x) 至少有有个根个根n+1
Π
=
=
n
i
in
xxxKxR
0
)()()(
任?固–x ≠x
i
(i = 0,…,n),
Π
=
=
n
i
i
xtxKt
R
n
t
0
)()()(
)(
(t)有n+2个不?的根x
0
… x
n
x ),(,0)(
)1(
ba
xx
n
∈=
+
ξξ?
!)1()()(
)1(
+?
+
nxKR
x
n
n
ξ
注?这里是·t 求导
=+
++
!)1)(()()(
)1()1(
nxK
P
f
x
n
nx
n
ξξ
!)1(
)(
)(
)1(
+
=
+
n
f
xK
x
n
ξ
∏
=
+
+
=
n
i
i
x
n
n
xx
n
f
xR
0
)1(
)(
!)1(
)(
)(
ξ
插值?
– ˙ ¨函数y=f(x)的n阶导数y=f
(n)
(x)在[a,b]上连续
y=f
(n+1)
(x)在(a,b)上存在 插值为a x
0
<x
1
<…<x
n
b,
P
n
(x)是f(x)的ncurrency1拉格朗日插值多 式 ·任?x∈[a,b]有
(1)
1
() () ()
(1)!
n
nn
Rx f x
n
ξω
+
=
+
01
() (- )(- ) (- )
nn
xxxxx xxω =……
￡中ξ∈(a,b),ξ依赖 x
注 !通常不能确–ξ,而是估计,?x∈(a,b)
将 —为?估计上限
1
)1(
)(
+
+
≤
n
n
Mxf
∏
=
+
+
n
i
i
n
xx
n
M
0
1
||
)!1(
! f(x) 为任一个currency1数≤n的多 式时,
知 即插值多 式· currency1数≤n 的的多 多
式是精确的 f(x) 1 P
n
(x) = f(x) 1 即
0)(
)1(
≡
+
xf
n
0)( ≡xR
n
() () () 1
01
lx lx lx
n
++?+≡
( - 2.72)( - 2.73) ( - 2.71)( - 2.72)
( ) *0.4330 *0.4346
2
(2.71- 2.72)(2.71- 2.73) (2.72 - 2.71)(2.72 - 2.73)
( - 2.71)( - 2.72)
*0 4362
(2.73 - 2.71)(2.73- 2.71)
xx xx
Px
xx
=+
+?
解
0.4330 0.4346 0.4362
2.71 2.72 2.73
y=lgx
x
2.3 已知y=lg(x)的函数表如右 求
lg2.718并估计￡?
(3)
201202
()
() (- )(- )(- ) [,]
3!
f
Rx xx xx xx xx
ξ
ξ=∈∵
2
( ) lg '"( ) max '"( ) 0.043642
3
2.71 2.73
ln 10
fx x f x f x
x
x
=? =? =
≤≤
∵
0.043642
-9
(2.718) (2.718 - 2.71)(2.718 - 2.72)(2.718 - 2.73) 1.39654 10
2
6
R ≤=×
2
13038 - 7092.08 96459.032xx=+
lg 2.718 (2.718) 0.48
2
P∴≈ =
HW,
p.50 #3,6
Newton插值——引言
1.已知y=f(x)的n+1个 ￠?x
0
<x
1
<x
2
<…<x
n
及￡上的函数值y
i
=f(x
i
),i=0,1,2,…,n,用 函数法求 ￡上的Lagrange
值多 式,P
n
(x)=y
0
l
0
(x)+y
1
l
1
(x)+…+y
n
l
n
(x)
￡中 函数为:
0-11
0-11
(- ) (- )(- ) (- )
()
(-)(- )(- )(-)
ii n
i
iiiiiin
xx xx xx xx
lx
xx xx xx xx
+
+
=
((
(1)
0
()
() ()- () ( - ) (,)
(1)!
n
n
nn k
k
f
Rx f xPx xx ab
n
ξ
ξ
+
=
== ∈
+
∏
2.?f(x)有 到n+1阶导数 ￡插值? 为
,i=0,1,2,…,n
Lagrange 插值虽然易算 但?要增加一个￠?时全部 函数l
i
(x) 都?重新计计算算 ——不具有承袭?
Newton插值——具有承袭?
2.3.1 函数
Problem 2.4 已知y=f(x)的n+1个 ￠?x
0
,x
1
,x
2
,…,x
n
及函数值f(x
i
),i=0,1,2,…,n,求—ncurrency1多 式N
n
(x):
010201 01 1
() (-) (-)(-) (-)(-)(- )
nn
Nx C Cxx Cxx xx Cxx xx xx
=+ + ++((
N
n
(x)是1,(x-x
0
),(x-x
0
)(x-x
1
),…,(x-x
0
)(x-x
1
)…(x-x
n
)的?组
是n+1个特殊的 函数 用如o递 关系–fi
且?”插值?§:
( ) ( ) 0,1,2,,
ni i
Nx f xi n= =
() 1
0
() ( - ) ()
-1 -1
(2.9)
( - )( - ) ( - )
01 -1
1,2,,
x
xxx x
iii
xx xx xx
i
in
Φ=
Φ= Φ
=…
=…
–fi2.1 由(2.9)–fi的n+1个多 式 为Newton插值
x
0
,x
1
,…,x
n
为￠?的 函数
ΦΦ Φ…
n001 nn
N (x) = C (x)+C (x)+ +C (x)
求求系数系数已知 函数 求N
n
(x)=>求系数C
0
,C
1
,C
2
,…,C
n
在 式中 取x=x
0
有 N
n
(x
0
)= C
0
而N
n
(x
0
)=f(x
0
) C
0
=f(x
0
)
ff
∴
10
1
10
(x )- (x )
C=
x-x
为 易 计算C
0
,C
1
,C
2
,…,C
n
引?商
010201 01 1
() (-) (-)(-) (-)(-)(- )
nn
Nx C Cxx Cxx xx Cxx xx xx
=+ + ++((
( ) ( ) 0,1,2,,
ni i
Nx f xi n
= =
$%%%%%&%%%%%’
在 式中 取x=x
1
有 N
n
(x
1
)= C
0
+C
1
(x
1
-x
0
) 而N
n
(x
1
)=f(x
1
)
1021
220
21 10
f(x )- f(x )f(x )-f(x )
C =[ - ]/(x - x )
x-x x-x
有
2.3.2?商 /* divided difference */
¨函数f(x)在n+1个相 的? 上的函数值 为
…
01 n
x,x,,x
…
01 n
f(x ),f(x ),,f(x )
1.一阶?商 为为f(x)关 ￠? 的一阶?
商 记为,/* the 1st divided difference*/
01
01
f(x ) - f(x )
x-x
01
x,x
01
f[x,x ]
2.二阶?商
为f(x)关 ￠? 的二阶?商.
=
01 12
02
012
f[x,x ]-f[x,x ]
x-x
f[x,x,x ]
012
x,x,x
注,(1) 的fi
f[x
0
,x
1
]为弦AB的 率.
(2) 显然 f[x
0
,x
1
]=f[x
1
,x
0
]
y
0 x
0
x
1
x
A
B
3,k阶?商,f(x)在 ￠?x
0
,x
1
,…,x
k
处的k阶?商为
f[x
0
,x
1
,…,x
k-1
,x
k
]={f[x
0
,x
1
,…,x
k-1
]-f[x
1
,…,x
k-1
,x
k
]}/(x
0
-x
k
)
一般记忆为 f[A,B,C]={f[A,B]-f[B,C]}/(A-C)
商表计算?商 ˉ表如o
…
…
…
…
…
…
…
f[x
0
,x
1
,x
2
,x
3
]
阶?商
…
f[x
1
,x
2
,x
3
]
f[x
0
,x
1
,x
2
]
二阶?商
…
f[x
2
,x
3
]
f[x
1
,x
2
]
f[x
0
,x
1
]
一阶?商
…
f(x
3
)
f(x
2
)
f(x
1
)
f(x
0
)
f(x
i
)
…
x
3
x
2
x
1
x
0
x
1
计算?商
f(x) = x
已知 在￠?
x=1,4,9的函数值为试构造?商表
1 2 3
1 4 9
f(x)
x
f[x
0
,x
1
,x
2
]=(1/5-1/3)/(9-1)
=-1/60
f[x
1
,x
2
]=(3-2)/(9-4)
=1/5
39
f[x
0
,x
1
]=(2-1)/(4-1)
=1/3
24
11
二阶?商一阶?商
f(x
k
)x
k
解
2.3.3?商?质
1,n阶?商 表示成n+1个函数值的?组,即
)
∑
…
……
n
k
01 n
k=0
k0 kk-1kk+1 kn
f(x
f[x,x,,x ]=
(x -x ) (x -x )(x -x ) (x -x )
:
0 12
012
0102 1012 2021
f(x ) f(x ) f(x )
f[x,x,x ]= ++
(x - x )(x - x ) (x - x )(x - x ) (x - x )(x - x )
2,(·?),?商 ￠?的顺序 关?
012 102 021
f[x,x,x ]= f[x,x,x ]= = f[x,x,x ]
3,?f(x)是x的ncurrency1多 式,一阶?商f[x,x
0
]是x的n-1currency1多 式,
二阶?商f[x,x
0
,x
1
]是x的n-2currency1多 式;
一般 函数f(x)的k阶?商f[x,x
0
,…,x
k-1
]是x的n-k(k n)currency1多 式而k>n时 k阶?商为零 自学?质的‰
2.3.4 Newton插值 式
x
0
,x
1
,…,x
n
为[a,b]中 ￠? 且x是[a,b]中一?
0
0
0
f(x)- f(x )
f[x,x ]=
x-x
=>
000
f(x) = f(x )+f[x,x ](x,-x ) (1 )式
001
01
1
f[x,x ]- f[x,x ]
f[x,x,x ]=
x-x
001 011
f[x,x ]=f[x,x ]+f[x,x,x ] (x- x ) (2 )式=>
0n-101n
0n
n
f[x,x,,x ]- f[x,x,,x ]
f[x,x,,x ]=
x-x
……
…
………
0n-1 01n 0n n
f[x,x,,x ]=f[x,x,,x ]+f[x,x,,x ](x- x ) (n-1 )式=>
牛顿插值 /* Newton’s Interpolation */
],[)()()(
000
xxfxxxfxf?+=
],,[)(],[],[
101100
xxxfxxxxfxxf?+=
],...,,[)(],...,[],...,,[
0010 nnnn
xxxfxxxxfxxxf?+=
( ) ( - ) ( - )( - ),.,( - )...( - )
01 0 2 0 1 0 -1
N x c cxx c xx xx c xx xx
nnn
=+ + ++
1
2
…………
n?1
1
+ (x?x
0
) ×
2
+ … … + (x?x
0
)…(x?x
n?1
) ×
n?1
...))(](,,[)](,[)()(
102100100
++?+= xxxxxxxfxxxxfxfxf
))...(](,...,[
100?
+
nn
xxxxxxf
))()...(](,...,,[
100 nnn
xxxxxxxxxf+
N
n
(x)
R
n
(x)
c
i
= f [ x
0
,…,x
i
]
Newton插值 式
f(x)=N
n
(x)+R
n
(x),
由 R
n
(x
i
)=0 i=0,1,2,…,n
N
n
(x
i
)=f(x
i
) i=0,1,2,…,n
从而N
n
(x)为?”插值?§的currency1数不'“n的多 式
N
n
(x)即为Problem2.4的解
–fi N
n
(x)为y=f(x)在￠?x
0
,x
1
,…,x
n
上的n阶Newton插值
式
R
n
(x)=f(x)-N
n
(x)=f[x
0
,x
1
,…,x
n
,x](x-x
0
)(x-x
1
)…(x-x
n
)为￡插值
001
( ) [,,...,]( )...( )( )
nnnn
Rx fxx xxx xx xx
=?
Newton插值 式
10101
() [,,]( )( )Rx fxxxxxxx=
n=1时
10010
() ( ) [,]( )Nx fx fxx xx=+?
n=2时
20010012 0 1
() ( ) [,]( ) [,,]( )( )Nx f fxxfxxx xx xx xxx?+?=+?
1012012
( ) [,,,]( )( )( )Rx fxxxx x x x x x x=
:已知f(x)在六个?的函数值如o表 用牛顿型插值多
式求f(0.596) 的近似值,并估计￡?
4
( ) 0.41075 1.11600( 0.4) 0.28000( 0.4)( 0.55)
0.19733( 0.4)( 0.55)( 0.65) 0.3134( 0.4)( 0.55)( 0.65)( 0.80)
Nx x x x
xxx xxxx
=+?+
++
4
(0.596) (0.596) 0.63195fN≈=
401234 04
44
| (0.596) | | [,,,,,0.596](0.596 ) (0.596 ) |
0.33215 10 0.5 10
Rfxxx x x
=
≈ × < ×
Newton插值 式注? 1.在给–￠?x
0
,x
1
,…,x
n
上的Newton插值 式N
n
(x)
Lagrange插值 式P
n
(x)都?”插值?§
N
n
(x
i
)=P
n
(x
i
)=f(x
i
) i=0,1,2,…,n
由插值多 式的?一? P
n
(x)=N
n
(x)
2.由1知P
n
(x) N
n
(x)有相?的?,
(1)
0
()
() () () ()
(1)!
() () [,,..,] ()
n
nn
nn
f
Rx fx Px x
n
f xRx f xx x x
ξ
ω
ω
+
=?=
+
=?=
– 2.3在￠?x
0
,x
1
,…,x
n
所阶–的范围范围ф
内存在一? 使得
≤≤ ≤≤
ii
0in 0in
[min x,max x ]
()
01
()
[,,,]
!
n
n
f
fxx x
n
ξ
…=
HW,
p.50 #13
2.4 低currency1插值 /* piecewise polynomial approximation */
多 式插值
· y=f(x) a x b
给–插值x
0
,x
1
,…,x
n
构造插值多 式P
n
(x) 为使P
n
(x)更好地逼近f(x)一般使:
￠?￥距 a=>￠?多(n ) =>插值多 式P
n
(x)的currency1数很高(高currency1插值)
高currency1插值使P
n
(x)在 多?上 f(x)相等,但在插值￠?,
如? 是?插值多 式P
n
(x)的currency1数越高越好
Increasing the degree of interpolating polynomial
will NOT guarantee a good result,
since high-degree polynomials are
oscillating.
在[?5,5]上 的P
n
(x) 取
2
1
1
)(
x
xf
+
=
),...,0(
10
5 nii
n
x
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 现象
P
n
(x) →f (x)
×
低currency1插值
2.4 低currency1插值 /* piecewise polynomial approximation */
插值思想 将一个?￥ 成?干a?￥,在每个a?￥上?低
currency1插值,将产生的多 式装配成整个?￥上的一个 kcurrency1
式.￡步骤为:
(1) ·[a,b]— 划,a=x
0
<x
1
<…<x
n
=b
(2) 在每个a?￥[x
i
,x
i+1
]上构造低currency1插值多 式P
i
(x)
(3) 将P
i
(x),i=0,1,…n-1拼接为[a,b]上的 多 式g(x)—为f(x)
的插值函数 即 g(x)=P
i
(x) x [x
i
,x
i+1
]
一般使 P
i
(x)都为kcurrency1式,此时的g(x)记为S
k
(x),￡为 kcurrency1
式(即在 划 的每个a?￥[x
i
,x
i+1
]上 S
k
(x)都为kcurrency1式)
插值
ˇ插值——用折 逼近fl f(x)
Problem2.5 ·y=f(x) x [a,b]–fi?￥有 划
:a=x
0
<x
1
<x
2
<……x
n
=b 且已知y
i
=f(x
i
) i=0,1,…,n
求具有 划 的 一currency1式S
1
(x),使:S
1
(x
i
)= y
i
,i=0,1,2,…,n.
求S
1
(x)在a [x
i
,x
i+1
]上的表达式 拼装即成
],[for
1+
∈
ii
xxx
1
11
11
() ()
ii
ii
ii i i
xx xx
fx Sx y y
xx x x
+
+
++
≈= +
1
''
[,
()
|() ()| ( )( ),(,)
2
]
ii
ii ii
f
fx Sx xxxx
x
x
xx
x
ξ
ξ
+
+
+
∈
= ∈
!
插值?
111
1
''
[,
()
|() ()| ( )( ),(,)
2
]
ii
ii ii
f
fx Sx xxxx
x
x
xx
x
ξ
ξ
+
+
+
∈
= ∈
!
1
''
[,] [,]
'' ''
|()| |()| |()|,
m maax x
ii
xabxxx
fxf Mfxξ
+
∈∈
≤ =≤
1
1
22 22
11
[,] 0
1 1
|( )( )| ( ) ( )
444 4
max max
ii
ii i
n
ii
xx
i
x i
xxxx x h hx h
+
++
∈ =
=?=≤ =
– 2.4 ¨ f(x) c
2
[a,b],a<x
0
<x
1
<…<x
n
=b,且 f(x
i
) 已知,i=0,1,…,n,S
1
(x)为问题2.5的解,x [a,b] 时
|f(x)-S
1
(x)| Mh
2
/8
￡中M=max|f”(x)| x [a,b],h=max{h
i
,i=0,…n-1}
因而S
1
(x)在[a,b]上一 收 到f(x)
要构造·数表log
10
x 10 X<100 怎 步 h,能使
一currency1插值具有六 有 数
解
'' ''
10 10
22
10 100
11
(log ) | (log ) |
ln10 10 ln10
max
x
xMx
x
≤≤
=? ∴ = =∵
2
10 1
1
|log ( )|
8
xSx Mh∴? ≤
0.01h∴ =
1 log
10
x<2 要使? 具有六 有 数
限 =0.5 10
-5
HW,
p.51 #17
2
2
11
810ln10
h=?
2
0.959705 10h
≤ ×
5
1
10
2
≤×
引言表示两个变量x,y内在关系一般由函数式y=f(x)表达但在实际问题中 有两种情况
1 由实验观测而得的一组离散数据(函数表) 显然这种函数关系式y=f(x)存在且连续 但未知
2 函数解析表达式已知 但计算复杂 不便使用 通常也函数表 如 y=sin(x),y=lg(x)
有时要求不在表上的函数值 怎么办引言
y
0
y
1
… y
n
x
0
x
1
… x
n
y
x
已知 f(x)的的函数表办法是 根据所给的y=f(x)的函数表构造一个简单的连续函数g(x)近似代替f(x)
Def g(x)为逼近函数 f(x)为被逼近函数近似代替即逼近的方法有很多种 通常是 插值方法求g(x)使 g(x
i
) =y
i
i=0,1,2,3 …n.
Def g(x)为f(x)的插值函数 f(x)为被插值函数引言构造g(x)的方法 有一 逼近 方逼近 数据
简单函数g(x) 用 算计算的函数如 有 函数( 式函数) 多 式 多 式
g(x)为多 式时 插值方法 为代数多 式插值 插值数g(x)为插值多 式
章 要 多 式插值的 方法
在实 中 用很
Def n+1个?x
1
,x
2
,…,x
n
为插值￠?
￡所在?￥[a,b]为插值?￥ (2.2)式为插值?§
Problem I 已知y=f(x)的函数表
…
2
n
n
01 2 n
=a +a x+a x + +a x (P(x) 2.1)
…
ni i
P (x )=y i=0,1,,n (2.2)
y
0
y
1
… y
n
x
0
x
1
… x
n
y
x
插值?￥
插值?§
且x
i
(i=0,1,…,n)两两
x
i
[a,b]
求currency1数不'“n的多 式使得
x
0
x
1
x
2
x
3
x
4
x
f(x) ≈P
n
(x)
多 式插值问题的fi
多 式P
n
(x) ￡fl,给–的y=f(x)的
n+1个?(x
i
,y
i
) i=0,1,2,…,n.
插值多 式的?一?
· Problem I中的P
n
(x)是?存在 存在是一 如?求显然 关?是求P
n
(x) 的系数a
0
,a
1
,…,a
n
.
– 2.1 在n+1个 的插值x
1
,x
2
,…,x
n
上?”插值?§
(2.2)的currency1数不'“n的代数多 式P
n
(x)存在且?一
…
ni i
P (x )=y i=0,1,,n (2.2)
…
2
n
n
01 2 n
=a +a x+a x + +a x (P(x) 2.1)
析 为求
要?…插值?§
– 2.1的‰
‰ 由插值?§ 有
…
…
"
…
2n
n0 0 10 20 n0 0
2n
n1 0 11 21 n1 1
2n
nn 0 1n 2n nn n
P(x )=a +ax +ax + +ax =y
P(x)=a +ax +ax + +ax =y
P(x)=a +ax +ax + +ax =y
关 未知量 的
currency1?方`组
…
01 n
a,a,,a
(2.3)
￡系数′?的?ˉ式为
…
…
…
…
2n
00 0
2n
11 1
2n
nn n
1x x x
1x x x
1x x x
(,)
ij
ijxx≠≠∵
∴
∴
…
01 n
a,a,,a
方`组(2.3)的解 存在且?一插值多 式 存在且?一
…
n01 n
=V(x,x,,x )
∏∏
ni-1
ij
i=1 j=0
=(x-x)
≠ 0
˙ ˙ 给–f(x)的函数表 求f(x)的currency1数不'“3的插值多 式
-7 7 4 35
-1 1 2 5
y
x
=
1
2
3
0
a1-1 1 -1 -7
a11 1 1 7
a12 4 8 -4
a1 5 25 125 35
解 ¨P
3
(x)=a
0
+a
1
x+a
2
x
2
+a
3
x
3
解方`组得 a
0
=10,a
1
=5,a
2
=-10,a
3
=2
即P
3
(x)=10+5x-10x
2
+2x
3
n=20,在 10
8
currency1/ 的计算?上计算
2.2 Lagrange 插值—— ˇ插值
析,两?(x
0
,y
0
),(x
1
,y
1
)— y=P
1
(x)—— ˇ插值
10
00
10
-
(- )
-
yy
yy xx
xx
=
y
0
y
1
x
0
x
1
y
x
Problem 2.1 已知函数y=f(x)的函数表求currency1数不'“1的多 式P
1
(x)=a
0
+a
1
x
”插值?§ P
1
(x
0
)=y
0
,P
1
(x
1
)=y
1
l
0
(x) l
1
(x)
Σ
=
=
1
0
)(
i
ii
yxl
01
01
01 10
--
(),()
--
xxxx
lx lx
xx xx
==
为 ˇ插值 函数而P
1
(x)是 的?组
01
() () 1lx lx+=
00 01
10 11
() 1,() 0
() 0,() 1
lx lx
lx lx
==
1
,0,1
0
ij ij
ij
lx ij
ij
δ
=
== =
≠
δ
ij
/* Kronecker Delta */
解 由? 式方`
00
10 1 0
10 10
--
() -
--
xx xx
yPx y y y
xx xx
==+
01
10
01 10
--
()
--
xxxx
Px y y
xx xx
=+
ˇ插值解 已知(x
0
,y
0
)= (2.71,0.4330),(x
1
,y
1
)=(2.72,0.4364)
用?插值
1
x -2.72 x -2.71
P (x)= *0.4330+ *0.4346
2.71-2.72 2.72-2.71
2.2已知lg2.71=0.4330,lg2.72=0.4364.求y=lg2.718.
析 ·y=lgx,给 两?(2.71,0.4330)=(x
0
,y
0
),
(2.72,0.4364)=(x
1
,y
1
)
为求lg2.718构造简单的插值多 式—为lgx的近似
∴≈
1
lg2.718 P (2.718)=0.43428
=0.16x -0.0006
∴≈
1
lgx P (x)
2.2.2 插值
用?插值法·函数y=f(x)?
逼近时 即用 y=P
1
(x)代替fl
y=f(x)
y
x
0
x
1
x
显然 插值?￥ fl [x
0
,x
1
] 变
时?插值的?很
为 a这种? 用简单的fl ( )
近似代替复杂fl y=f(x) 二currency1多 式函数的fl
为 所 构造插值函数P
2
(x) 即n=2
插值
Problem2.2 已知y=f(x)的函数表 x
0
,x
1
,x
2
为 ￠? 求一个currency1数不'“2的多 式
P
2
(x)=a
0
+a
1
x+a
2
x
2
P
2
(x
0
)=y
0
,P
2
(x
1
)=y
1
,P
2
(x
2
)=y
2
y
0
y
1
y
2
x
0
x
1
x
2
y
x
fi P
2
(x)为,?(x
0
,y
0
),(x
1
,y
1
),(x
2
,y
2
)的
方法 函数法 构造 函数l
0
(x),l
1
(x),l
2
(x) 个二currency1式使P
2
(x)= y
0
l
0
(x)+y
1
l
1
(x)+y
2
l
2
(x)?”插值?§
(),0,1,2lx ij
ij ij
δ= =
()1,()0,()0
00 01 02
()0,()1,()0
10 11 12
( ) 0,( ) 0,( ) 1
20 21 22
lx lx lx
lx lx lx
lx lx lx
= = =
= = =
= = =
$%%%%%%&%%%%%%’
插值求二currency1多 式l
0
(x) l
0
(x
0
)=1 l
0
(x
1
)=0 l
0
(x
2
)=0
<=> l
0
(x) C(x-x
1
)(x-x
2
)求C=?
法求得 l
1
(x) l
2
(x) 即 插值的插值 函数如o
由l
0
(x
0
)=1 得 C(x
0
-x
1
)(x
0
-x
2
)=1
C=1/(x
0
-x
1
)(x
0
-x
2
)
插值问题Problem 2.2的解
02 0112
20 1 2
0102 1012 20 21
(- )(- ) (- )(- )(- )(- )
()
(-)(-) (-)(-) (-)(-)
xx xx xx xxxx xx
Px y y y
xxxx xxxx xxxx
=++
12
0
0102
(- )(- )
()
(-)(-)
xx xx
lx
xxxx
=
()
2
(- )(- ) (- )(- )(- )(- )
02 0112
,(),
1
(-)(-) (-)(-) (-)(-)
0102 1012 2021
lx
xx xx xx xxxx xx
ll
xxxx xxxx xxxx
==(x) =
0
2.2.3 Lagrange插值 式
函数法 求n+1个ncurrency1多 式 l
0
(x),l
1
(x),…,l
n
(x) 使
P
n
(x)=y
0
l
0
(x)+y
1
l
1
(x)+…+y
n
l
n
(x).
P
n
(x)”插值?§ P
n
(x
j
)=y
j
j=0,1,2,3,…,n
即y
0
l
0
(x
j
)+y
1
l
1
(x
j
)+…+yjlj(xj) …+y
n
l
n
(x
j
) = y
j
Problem2.3 已知y=f(x)在两两 ￠?x
0
,x
1
,…,x
n
的函数值
y
1
,y
2
,…,y
n
,求ncurrency1多 式 P
n
(x)=a
0
+a
1
x+a
2
x
2
+…+a
n
x
n
”插值?§P
n
(x
j
)=y
j
,j=0,1,2,3,…,n
()0,()0,,,()0
01
0,1
(
,2
)1
,,
lx lx lx
jj njj
jn
lx
j
= =, =
=
=
$%%%%%%%%%%&%%%%%%%%%%’
1
(),0,1,2,,
0
j
lx j n
kj kj
j
κ
δκ
κ
=
== =?
≠
Lagrange插值 式
l
k
(x
0
)=0,…,l
k
(x
k-1
)=0,l
k
(x
k+1
)=0,…,l
k
(x
n
)=0
即l
k
(x)有n个0?x
0
,x
1
,…,x
k-1
,x
k+1
,…,x
n
l
k
(x)=C(x-x
0
)…(x-x
k-1
)(x-x
k+1
)…(x-x
n
) l
k
(x
k
)=1
C(x
k
-x
0
)…(x
k
-x
k-1
)(x
k
-x
k+1
)…(x
k
-x
n
)=1
1
C∴
((
k0 kk-1kk+1 kn
=
(x - x ) (x - x )(x - x ) (x - x )
≠
∴=
∏
n
j
0kk n
k
j=0,j k
k0 kk-1kk+1 kn kj
x-x
(x-x ) (x-x )(x-x ) (x-x )
l(x)=
(x - x ) (x - x )(x - x ) (x - x ) x - x
≠
∴
∑∑∏
nnn
j
nkkk
k=0 k=0 j=0,j k
k j
x-x
P (x)= y l (x)= y ( )
x-x
上式即为Lagrange插值多 式
Lagrange插值 式 n=1 n=2时 是 ˇ插值
插值 式
￠?有关 而 f 关
2.2.4 插值? /* Remainder */
函数y=f(x) ￡ Lagrange插值多 式P
n
(x)
(1) P
n
(x
i
)= f(x
i
) =y
i
,i=0,1,2,…,n
(2) 而· 插值?￥[a,b]内插值￠?x
i
(i=1,2,…,n) 的?x,
一般P
n
(x) f(x) 存在?
Def,Rn(x)=f(x)-Pn(x)为Pn(x)的? 插值?
1 => Rn(x
i
)=0,i=0,1,2,…,n
(2) =>?x x
i
,可能 Rn(x) 0,
用Lagrange插值 式Pn(x) 计算? 是 要
Rn(x)是?”?a
Rn(x)=
¨￠?
)1( +n
f
在[a,b]内存在,
() () ()Rx fx Px
nn
=?
],[ baCf
n
∈
bxxxa
n
≤<<<≤ (
10
且f?”?§,
Rolle’s Theorem,?
存在 使得
)(x?
0)()(
10
== xx
),(
10
xx∈ξ
0)( =
′′′
ξ?
0)()()(
210
=== xxx
),(),,(
211100
xxxx ∈∈ ξξ
使得
0)()(
10
=
′′′
=
′′′
ξ?ξ? ),(
10
ξξξ∈
使得
0)( =
′′′′′′
ξ?
0)()(
0
===
n
xx (
存在
),( ba∈ξ
使得
0)(
)(
=ξ?
n
R
n
(x) 至少有有个根个根n+1
Π
=
=
n
i
in
xxxKxR
0
)()()(
任?固–x ≠x
i
(i = 0,…,n),
Π
=
=
n
i
i
xtxKt
R
n
t
0
)()()(
)(
(t)有n+2个不?的根x
0
… x
n
x ),(,0)(
)1(
ba
xx
n
∈=
+
ξξ?
!)1()()(
)1(
+?
+
nxKR
x
n
n
ξ
注?这里是·t 求导
=+
++
!)1)(()()(
)1()1(
nxK
P
f
x
n
nx
n
ξξ
!)1(
)(
)(
)1(
+
=
+
n
f
xK
x
n
ξ
∏
=
+
+
=
n
i
i
x
n
n
xx
n
f
xR
0
)1(
)(
!)1(
)(
)(
ξ
插值?
– ˙ ¨函数y=f(x)的n阶导数y=f
(n)
(x)在[a,b]上连续
y=f
(n+1)
(x)在(a,b)上存在 插值为a x
0
<x
1
<…<x
n
b,
P
n
(x)是f(x)的ncurrency1拉格朗日插值多 式 ·任?x∈[a,b]有
(1)
1
() () ()
(1)!
n
nn
Rx f x
n
ξω
+
=
+
01
() (- )(- ) (- )
nn
xxxxx xxω =……
￡中ξ∈(a,b),ξ依赖 x
注 !通常不能确–ξ,而是估计,?x∈(a,b)
将 —为?估计上限
1
)1(
)(
+
+
≤
n
n
Mxf
∏
=
+
+
n
i
i
n
xx
n
M
0
1
||
)!1(
! f(x) 为任一个currency1数≤n的多 式时,
知 即插值多 式· currency1数≤n 的的多 多
式是精确的 f(x) 1 P
n
(x) = f(x) 1 即
0)(
)1(
≡
+
xf
n
0)( ≡xR
n
() () () 1
01
lx lx lx
n
++?+≡
( - 2.72)( - 2.73) ( - 2.71)( - 2.72)
( ) *0.4330 *0.4346
2
(2.71- 2.72)(2.71- 2.73) (2.72 - 2.71)(2.72 - 2.73)
( - 2.71)( - 2.72)
*0 4362
(2.73 - 2.71)(2.73- 2.71)
xx xx
Px
xx
=+
+?
解
0.4330 0.4346 0.4362
2.71 2.72 2.73
y=lgx
x
2.3 已知y=lg(x)的函数表如右 求
lg2.718并估计￡?
(3)
201202
()
() (- )(- )(- ) [,]
3!
f
Rx xx xx xx xx
ξ
ξ=∈∵
2
( ) lg '"( ) max '"( ) 0.043642
3
2.71 2.73
ln 10
fx x f x f x
x
x
=? =? =
≤≤
∵
0.043642
-9
(2.718) (2.718 - 2.71)(2.718 - 2.72)(2.718 - 2.73) 1.39654 10
2
6
R ≤=×
2
13038 - 7092.08 96459.032xx=+
lg 2.718 (2.718) 0.48
2
P∴≈ =
HW,
p.50 #3,6
Newton插值——引言
1.已知y=f(x)的n+1个 ￠?x
0
<x
1
<x
2
<…<x
n
及￡上的函数值y
i
=f(x
i
),i=0,1,2,…,n,用 函数法求 ￡上的Lagrange
值多 式,P
n
(x)=y
0
l
0
(x)+y
1
l
1
(x)+…+y
n
l
n
(x)
￡中 函数为:
0-11
0-11
(- ) (- )(- ) (- )
()
(-)(- )(- )(-)
ii n
i
iiiiiin
xx xx xx xx
lx
xx xx xx xx
+
+
=
((
(1)
0
()
() ()- () ( - ) (,)
(1)!
n
n
nn k
k
f
Rx f xPx xx ab
n
ξ
ξ
+
=
== ∈
+
∏
2.?f(x)有 到n+1阶导数 ￡插值? 为
,i=0,1,2,…,n
Lagrange 插值虽然易算 但?要增加一个￠?时全部 函数l
i
(x) 都?重新计计算算 ——不具有承袭?
Newton插值——具有承袭?
2.3.1 函数
Problem 2.4 已知y=f(x)的n+1个 ￠?x
0
,x
1
,x
2
,…,x
n
及函数值f(x
i
),i=0,1,2,…,n,求—ncurrency1多 式N
n
(x):
010201 01 1
() (-) (-)(-) (-)(-)(- )
nn
Nx C Cxx Cxx xx Cxx xx xx
=+ + ++((
N
n
(x)是1,(x-x
0
),(x-x
0
)(x-x
1
),…,(x-x
0
)(x-x
1
)…(x-x
n
)的?组
是n+1个特殊的 函数 用如o递 关系–fi
且?”插值?§:
( ) ( ) 0,1,2,,
ni i
Nx f xi n= =
() 1
0
() ( - ) ()
-1 -1
(2.9)
( - )( - ) ( - )
01 -1
1,2,,
x
xxx x
iii
xx xx xx
i
in
Φ=
Φ= Φ
=…
=…
–fi2.1 由(2.9)–fi的n+1个多 式 为Newton插值
x
0
,x
1
,…,x
n
为￠?的 函数
ΦΦ Φ…
n001 nn
N (x) = C (x)+C (x)+ +C (x)
求求系数系数已知 函数 求N
n
(x)=>求系数C
0
,C
1
,C
2
,…,C
n
在 式中 取x=x
0
有 N
n
(x
0
)= C
0
而N
n
(x
0
)=f(x
0
) C
0
=f(x
0
)
ff
∴
10
1
10
(x )- (x )
C=
x-x
为 易 计算C
0
,C
1
,C
2
,…,C
n
引?商
010201 01 1
() (-) (-)(-) (-)(-)(- )
nn
Nx C Cxx Cxx xx Cxx xx xx
=+ + ++((
( ) ( ) 0,1,2,,
ni i
Nx f xi n
= =
$%%%%%&%%%%%’
在 式中 取x=x
1
有 N
n
(x
1
)= C
0
+C
1
(x
1
-x
0
) 而N
n
(x
1
)=f(x
1
)
1021
220
21 10
f(x )- f(x )f(x )-f(x )
C =[ - ]/(x - x )
x-x x-x
有
2.3.2?商 /* divided difference */
¨函数f(x)在n+1个相 的? 上的函数值 为
…
01 n
x,x,,x
…
01 n
f(x ),f(x ),,f(x )
1.一阶?商 为为f(x)关 ￠? 的一阶?
商 记为,/* the 1st divided difference*/
01
01
f(x ) - f(x )
x-x
01
x,x
01
f[x,x ]
2.二阶?商
为f(x)关 ￠? 的二阶?商.
=
01 12
02
012
f[x,x ]-f[x,x ]
x-x
f[x,x,x ]
012
x,x,x
注,(1) 的fi
f[x
0
,x
1
]为弦AB的 率.
(2) 显然 f[x
0
,x
1
]=f[x
1
,x
0
]
y
0 x
0
x
1
x
A
B
3,k阶?商,f(x)在 ￠?x
0
,x
1
,…,x
k
处的k阶?商为
f[x
0
,x
1
,…,x
k-1
,x
k
]={f[x
0
,x
1
,…,x
k-1
]-f[x
1
,…,x
k-1
,x
k
]}/(x
0
-x
k
)
一般记忆为 f[A,B,C]={f[A,B]-f[B,C]}/(A-C)
商表计算?商 ˉ表如o
…
…
…
…
…
…
…
f[x
0
,x
1
,x
2
,x
3
]
阶?商
…
f[x
1
,x
2
,x
3
]
f[x
0
,x
1
,x
2
]
二阶?商
…
f[x
2
,x
3
]
f[x
1
,x
2
]
f[x
0
,x
1
]
一阶?商
…
f(x
3
)
f(x
2
)
f(x
1
)
f(x
0
)
f(x
i
)
…
x
3
x
2
x
1
x
0
x
1
计算?商
f(x) = x
已知 在￠?
x=1,4,9的函数值为试构造?商表
1 2 3
1 4 9
f(x)
x
f[x
0
,x
1
,x
2
]=(1/5-1/3)/(9-1)
=-1/60
f[x
1
,x
2
]=(3-2)/(9-4)
=1/5
39
f[x
0
,x
1
]=(2-1)/(4-1)
=1/3
24
11
二阶?商一阶?商
f(x
k
)x
k
解
2.3.3?商?质
1,n阶?商 表示成n+1个函数值的?组,即
)
∑
…
……
n
k
01 n
k=0
k0 kk-1kk+1 kn
f(x
f[x,x,,x ]=
(x -x ) (x -x )(x -x ) (x -x )
:
0 12
012
0102 1012 2021
f(x ) f(x ) f(x )
f[x,x,x ]= ++
(x - x )(x - x ) (x - x )(x - x ) (x - x )(x - x )
2,(·?),?商 ￠?的顺序 关?
012 102 021
f[x,x,x ]= f[x,x,x ]= = f[x,x,x ]
3,?f(x)是x的ncurrency1多 式,一阶?商f[x,x
0
]是x的n-1currency1多 式,
二阶?商f[x,x
0
,x
1
]是x的n-2currency1多 式;
一般 函数f(x)的k阶?商f[x,x
0
,…,x
k-1
]是x的n-k(k n)currency1多 式而k>n时 k阶?商为零 自学?质的‰
2.3.4 Newton插值 式
x
0
,x
1
,…,x
n
为[a,b]中 ￠? 且x是[a,b]中一?
0
0
0
f(x)- f(x )
f[x,x ]=
x-x
=>
000
f(x) = f(x )+f[x,x ](x,-x ) (1 )式
001
01
1
f[x,x ]- f[x,x ]
f[x,x,x ]=
x-x
001 011
f[x,x ]=f[x,x ]+f[x,x,x ] (x- x ) (2 )式=>
0n-101n
0n
n
f[x,x,,x ]- f[x,x,,x ]
f[x,x,,x ]=
x-x
……
…
………
0n-1 01n 0n n
f[x,x,,x ]=f[x,x,,x ]+f[x,x,,x ](x- x ) (n-1 )式=>
牛顿插值 /* Newton’s Interpolation */
],[)()()(
000
xxfxxxfxf?+=
],,[)(],[],[
101100
xxxfxxxxfxxf?+=
],...,,[)(],...,[],...,,[
0010 nnnn
xxxfxxxxfxxxf?+=
( ) ( - ) ( - )( - ),.,( - )...( - )
01 0 2 0 1 0 -1
N x c cxx c xx xx c xx xx
nnn
=+ + ++
1
2
…………
n?1
1
+ (x?x
0
) ×
2
+ … … + (x?x
0
)…(x?x
n?1
) ×
n?1
...))(](,,[)](,[)()(
102100100
++?+= xxxxxxxfxxxxfxfxf
))...(](,...,[
100?
+
nn
xxxxxxf
))()...(](,...,,[
100 nnn
xxxxxxxxxf+
N
n
(x)
R
n
(x)
c
i
= f [ x
0
,…,x
i
]
Newton插值 式
f(x)=N
n
(x)+R
n
(x),
由 R
n
(x
i
)=0 i=0,1,2,…,n
N
n
(x
i
)=f(x
i
) i=0,1,2,…,n
从而N
n
(x)为?”插值?§的currency1数不'“n的多 式
N
n
(x)即为Problem2.4的解
–fi N
n
(x)为y=f(x)在￠?x
0
,x
1
,…,x
n
上的n阶Newton插值
式
R
n
(x)=f(x)-N
n
(x)=f[x
0
,x
1
,…,x
n
,x](x-x
0
)(x-x
1
)…(x-x
n
)为￡插值
001
( ) [,,...,]( )...( )( )
nnnn
Rx fxx xxx xx xx
=?
Newton插值 式
10101
() [,,]( )( )Rx fxxxxxxx=
n=1时
10010
() ( ) [,]( )Nx fx fxx xx=+?
n=2时
20010012 0 1
() ( ) [,]( ) [,,]( )( )Nx f fxxfxxx xx xx xxx?+?=+?
1012012
( ) [,,,]( )( )( )Rx fxxxx x x x x x x=
:已知f(x)在六个?的函数值如o表 用牛顿型插值多
式求f(0.596) 的近似值,并估计￡?
4
( ) 0.41075 1.11600( 0.4) 0.28000( 0.4)( 0.55)
0.19733( 0.4)( 0.55)( 0.65) 0.3134( 0.4)( 0.55)( 0.65)( 0.80)
Nx x x x
xxx xxxx
=+?+
++
4
(0.596) (0.596) 0.63195fN≈=
401234 04
44
| (0.596) | | [,,,,,0.596](0.596 ) (0.596 ) |
0.33215 10 0.5 10
Rfxxx x x
=
≈ × < ×
Newton插值 式注? 1.在给–￠?x
0
,x
1
,…,x
n
上的Newton插值 式N
n
(x)
Lagrange插值 式P
n
(x)都?”插值?§
N
n
(x
i
)=P
n
(x
i
)=f(x
i
) i=0,1,2,…,n
由插值多 式的?一? P
n
(x)=N
n
(x)
2.由1知P
n
(x) N
n
(x)有相?的?,
(1)
0
()
() () () ()
(1)!
() () [,,..,] ()
n
nn
nn
f
Rx fx Px x
n
f xRx f xx x x
ξ
ω
ω
+
=?=
+
=?=
– 2.3在￠?x
0
,x
1
,…,x
n
所阶–的范围范围ф
内存在一? 使得
≤≤ ≤≤
ii
0in 0in
[min x,max x ]
()
01
()
[,,,]
!
n
n
f
fxx x
n
ξ
…=
HW,
p.50 #13
2.4 低currency1插值 /* piecewise polynomial approximation */
多 式插值
· y=f(x) a x b
给–插值x
0
,x
1
,…,x
n
构造插值多 式P
n
(x) 为使P
n
(x)更好地逼近f(x)一般使:
￠?￥距 a=>￠?多(n ) =>插值多 式P
n
(x)的currency1数很高(高currency1插值)
高currency1插值使P
n
(x)在 多?上 f(x)相等,但在插值￠?,
如? 是?插值多 式P
n
(x)的currency1数越高越好
Increasing the degree of interpolating polynomial
will NOT guarantee a good result,
since high-degree polynomials are
oscillating.
在[?5,5]上 的P
n
(x) 取
2
1
1
)(
x
xf
+
=
),...,0(
10
5 nii
n
x
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 现象
P
n
(x) →f (x)
×
低currency1插值
2.4 低currency1插值 /* piecewise polynomial approximation */
插值思想 将一个?￥ 成?干a?￥,在每个a?￥上?低
currency1插值,将产生的多 式装配成整个?￥上的一个 kcurrency1
式.￡步骤为:
(1) ·[a,b]— 划,a=x
0
<x
1
<…<x
n
=b
(2) 在每个a?￥[x
i
,x
i+1
]上构造低currency1插值多 式P
i
(x)
(3) 将P
i
(x),i=0,1,…n-1拼接为[a,b]上的 多 式g(x)—为f(x)
的插值函数 即 g(x)=P
i
(x) x [x
i
,x
i+1
]
一般使 P
i
(x)都为kcurrency1式,此时的g(x)记为S
k
(x),￡为 kcurrency1
式(即在 划 的每个a?￥[x
i
,x
i+1
]上 S
k
(x)都为kcurrency1式)
插值
ˇ插值——用折 逼近fl f(x)
Problem2.5 ·y=f(x) x [a,b]–fi?￥有 划
:a=x
0
<x
1
<x
2
<……x
n
=b 且已知y
i
=f(x
i
) i=0,1,…,n
求具有 划 的 一currency1式S
1
(x),使:S
1
(x
i
)= y
i
,i=0,1,2,…,n.
求S
1
(x)在a [x
i
,x
i+1
]上的表达式 拼装即成
],[for
1+
∈
ii
xxx
1
11
11
() ()
ii
ii
ii i i
xx xx
fx Sx y y
xx x x
+
+
++
≈= +
1
''
[,
()
|() ()| ( )( ),(,)
2
]
ii
ii ii
f
fx Sx xxxx
x
x
xx
x
ξ
ξ
+
+
+
∈
= ∈
!
插值?
111
1
''
[,
()
|() ()| ( )( ),(,)
2
]
ii
ii ii
f
fx Sx xxxx
x
x
xx
x
ξ
ξ
+
+
+
∈
= ∈
!
1
''
[,] [,]
'' ''
|()| |()| |()|,
m maax x
ii
xabxxx
fxf Mfxξ
+
∈∈
≤ =≤
1
1
22 22
11
[,] 0
1 1
|( )( )| ( ) ( )
444 4
max max
ii
ii i
n
ii
xx
i
x i
xxxx x h hx h
+
++
∈ =
=?=≤ =
– 2.4 ¨ f(x) c
2
[a,b],a<x
0
<x
1
<…<x
n
=b,且 f(x
i
) 已知,i=0,1,…,n,S
1
(x)为问题2.5的解,x [a,b] 时
|f(x)-S
1
(x)| Mh
2
/8
￡中M=max|f”(x)| x [a,b],h=max{h
i
,i=0,…n-1}
因而S
1
(x)在[a,b]上一 收 到f(x)
要构造·数表log
10
x 10 X<100 怎 步 h,能使
一currency1插值具有六 有 数
解
'' ''
10 10
22
10 100
11
(log ) | (log ) |
ln10 10 ln10
max
x
xMx
x
≤≤
=? ∴ = =∵
2
10 1
1
|log ( )|
8
xSx Mh∴? ≤
0.01h∴ =
1 log
10
x<2 要使? 具有六 有 数
限 =0.5 10
-5
HW,
p.51 #17
2
2
11
810ln10
h=?
2
0.959705 10h
≤ ×
5
1
10
2
≤×
