- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Aitken（埃特肯）算法 N 0,1,,k , p ( x) L( x) N 0,1,,k ( x)
N 0,1,,k 1, p ( x) N 0,1,,k ( x) x p xk
Neville（列维尔）算法
( x xk )
Ni ,i 1,,k ( x) L( x) Ni ,i 1,,k 1 ( x) Ni 1,i 2,k ( x) Ni ,i 1,,k 1 ( x) xk xi ( x xi )
( x0 , y0 ), ( x1 , y1 )
容易求出，该函数为：
x x0 x x1 y y0 y1 x0 x1 x1 x0
一般插值问题：求过n+1个点
( x0 , y0 ), ( x1 , y1 ),,( xn , yn )
的不超过n次多项式 Ln ( x )。
Ln ( x) yi li ( x )
例子：求方程 x3-2x-5=0 在(2 , 3)内的根 思路: 设 y = f(x) =x3-2x-5 ，其反函数为 x=f -1(y)，则 根为x* =f -1(0) 。先用3= f -1(16)， 2= f -1(-1)插值，得 N0,1 (y) ≈f -1(y), 计算N0,1 (0)= 2.058823, f(2.058823) = -0.39 ，以-0.39为新的节点，继续……
第三章 插值法
第一节 插值多项式的基本概念
假设已经获得n+1点上的函数值
f xi yi , i 0,1,, n,
即提供了一张数据表
x
y f x
x0
y0
x1
y1
x2
xn
y2
yn
如何利用这张表求 f (x) 在其他给定点上的合 理的近似值呢?
在实验数据的处理、难以计算的函数的逼近、 数值微积分等方面需要解决这样的问题，这是 数值逼近中的一个基本问题。一个自然的想法 是找一个简单易计算的函数(x)，使得
称为Newton形式的插值多项式。
差商概念：
设函数 f (x) ，定义函数在两个不同点的一阶差商为
f ( xi , x j )
f ( xi ) f ( x j ) xi x j
, ( xi x j , i j )
三个不同点的二阶差商为：
f ( xi , x j , xk )
例子：用0、90、180、270、360五个点作出sinx 牛顿插值多项式。 做差商表 0 90 180 0 1 0 0.01111 -0.01111 -1.235e-4
270
360
-1
0
-0.01111
0.01111
0
4.572e-7
0
1.235e-4 4.572e-7
差商的性质
差商的计算公式：
n ( x) ( x x0 ) ( x x1 ) ( x xm )
r0 r1
rm
r0 r1 rm n 1
在x0 , x1 ,, xm之间，与x有关
证明思路：构造辅助函数，用罗尔定理。
, P3 ( x1 ) y1, P3 ( x2 ) y2 P3 ( x0 ) y0 , P3( x0 ) y0
2
值得注意的是在较大区间上进行插值时，误差可能会 很大！另外，一般情况下，外推不如内插好！
第二节 Lagrange插值公式 插值条件是
( x0 , y0 ),( x1 , y1 ),,( xn , yn )
Lagrange插值实质上是求通过上面 n+1 个点的 n 次多项式。
一次插值： 问题为求一次多项式，即一次函数，过以下 两点：
( xi ) yi (i 0,1,, n)
将φ(x)作为 f (x) 在一定范围内的近似函数，对于 这个范围内的某个给定点a，取 f (a)≈ φ(a)。这种 近似方法称为插值法。φ(x)称为 f (x)的以{xi} (i=0,1,· · · ,n)为插值节点的插值函数。插值节点上 所给的函数值称为样本值。
例子：用0、30、45、60、90五个点作出sinx 牛顿插值多项式。 做差商表 0 30 45 60 90 0 0.5 0.7071 0.866 1 0.016667 0.013807 0.010595 0.0044658 -0.000063556 -0.00010707 -0.0001362 -0.0000007 -0.00000049
Aitken（埃特肯）算法
x0
x1 x2 x3
N0 N1 N2 N3
N 0,1 ( x) N0,2 ( x) N 0,1,2 ( x) N 0,3 ( x) N 0,1,3 ( x) N 0,1,2,3 ( x)
Neville（列维尔）算法
x0
x1 x2 x3
N0 N1 N2 N3
N 0,1 ( x) N1,2 ( x) N 0,1,2 ( x) N 2,3 ( x) N1,2,3 ( x) N 0,1,2,3 ( x)
差商的计算简表：
x0 f ( x0 ) x1 f ( x1 ) f ( x0 , x1 ) x2 f ( x2 ) f ( x1 , x2 ) f ( x0 , x1 , x2 ) x3 f ( x3 ) f ( x2 , x3 ) f ( x1 , x2 , x3 ) f ( x0 , x1 , x2 , x3 ) x4 f ( x4 ) f ( x3 , x4 ) f ( x2 , x3 , x4 ) f ( x1 , x2 , x3 , x4 ) f ( x0 , x1 , x2 , x3 , x4 )
求过n+1个点的不超过n次多项式的插值多项 式是唯一的。 插值公式的误差为：
f ( n1) ( x ) Rn ( x) f ( x) Ln ( x) ( x x0 )( x x1 )( x xn ) (n 1)!
M n1 max f ( n 1) ( x)
因式定理：多项式P(x)具有r 次因式 (x-a)r 的 充 要条件是 P(a) P(a) P( r1) (a) 0 最一般的插值条件： ( xi ) yi , ( xi ) yi,, ( ri 1) ( xi ) yi( ri 1) xi ri 是 r 重插值节点， r r n 1
φ(xi)=yi 称为插值条件。函数值待求的点称为插值 点。插值节点所界定的范围称为插值区间。如 果所给插值点位于插值区间之内，这种插值过程 称为内插，否则称为外插。 若用多项式来作为插值函数，则称其为插值 多项式。通常用 n 次多项式作为n+1个插值条件 的插值多项式。如果插值条件只是给出节点的函 数值，称为拉格朗日插值，如果既有函数值也有 节点处函数的导数值，称为埃尔米特插值。
f ( x) N n1 ( x) N n ( x) f ( x0 , x1,, xn , x)( x x0 )( x x1 )( x xn )
Rn ( x ) f ( x ) N n ( x ) f ( x0 , x1 ,, xn , x )( x x0 )( x x1 )( x xn )
f (xj ) f ( x0 , x1 ,, xk ) (xj ) j 0 k
k
( x j ) ( x j xi ) k ( x ) ( x xi ) , k
yi 16 -1 xi 3 2 Ni,i+1 (0) Ni,i+1,i+2 (0) Ni,i+1,i+2,i+3 (0) 23
2.096589 2.094529
2.095659 2.094554 2.094553
0.012 2.095659 1.51E-5 2.094553
第四节 牛顿插值 设插值点为 ( x0 , f0 ),( x1, f1 ),( x2 , f 2 ),,( xn , f n ) 插值多项式形如
N n ( x) c0 c1 ( x x0 ) c2 ( x x0 )( x x1 ) cn ( x x0 )( x x1 )( x xn1 )
在点
f ( xi , x j ) f ( x j , xk ) xi xk
x0 , x1 ,, xk , xk 1 处 K+1 阶差商为：
f ( x0 , x1 ,, xk ) f ( x1 , , xk , xk 1 ) f ( x0 , x1 ,, xk , xk 1 ) x0 xk 1
i 0
n
li ( x ) 称为Lagrange插值基函数，满足：
1 , i j li ( x j ) ij , ij 0 , i j
( x x0 )( x xi 1 )( x xi 1 )( x xn ) li ( x) ( xi x0 )( xi xi 1 )( xi xi 1 )( xi xn )
牛顿插值的截断误差：
N n1 ( x) N n ( x) f ( x0 , x1,, xn1 )( x x0 )( x x1 )( x xn )
f ( xn1 ) Nn1 ( xn1 ) Nn ( xn1 ) f ( x0 , x1 ,, xn1 )( xn1 x0 )( xn1 x1 ) ( xn1 xn )
0 1 m
定理：给定上述n+1个插值条件，则n次插值 多项式是存在唯一的。
设函数 y = f (x) 在闭区间 [a , b ]上有n + 1 阶导数， 满足前面的一般插值条件，且插值节点各不相同， 则插值截断误差为
1 ( n 1) Rn ( x) f ( x) Pn ( x) f ( ) n ( x) (n 1)!
