数值分析 第二章 代数插值.pdf

郑州大学硕士研究生课程（2011-2012学年第一学期）

数值分析
NumericalAnalysis
第二章
代数插值
第二章代数插值

§2.1代数插值问题[问题提出]
§2.2代数插值多项式的存在唯一性[可解性]
§2.3拉格朗日插值方法[解决方法和理论分析]
§2.4牛顿(Newton)插值[算法实现]
§2.5分段线性插值
§2.6Hermite插值
§2.7样条插值计算机数值算法
设计思路

2/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.1代数插值问题

例2.1.1设计某工件的外形，要求其轮廓线是光

滑的，且必须过n+1个互异的点(xi,yi)(i=0,1,…,n).
轮廓线应如何设计呢？
y=p(x)
y=f(x)

3/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.1代数插值问题

解：满足要求的轮廓线不妨取为n次多项式Pn(x).设

nn−1
Pxnnn()=+axa−110x+++"axa(2.1)

这里Pn(x)是光滑的，并设它满足

Pxni()=yi(i=0,1,"n)(2.2)
将(2.1)带入(2.2)可得下面线性代数方程组

4/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.1代数插值问题

nn−1
⎧axnn010++……++=a−xax1000ay
⎪
⎪axnn++……++=ax−1axay
⎨nn111−1101(2.3)
⎪……
⎪nn−1
⎩axnn++……++=an−110xnaxnayn
则(2.3)的系数行列式为范德蒙德行列式
2n
1xx00…x0
2nni−1
1xx11…x1
Vxx==−≠∏∏(ij)0(2.4)
……ij==10
2n
1xxnn…xn

因xi≠xj（i≠j），故V≠0.从而方程组(2.3)的解存在唯一.

求出未知量a0,…,an代入(2.1)即得所求轮廓线.■

5/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.1代数插值问题

代数插值问题：设函数y=f(x)定义在区间[a,b]上，而

x0,x1,…,xn是在[a,b]上取定的n+1个互异节点,且在这些点

处的函数值为yi=f(xi),i=0,1,…n.

求一个次数不超过n次的多项式Pn(x)，使它满足

Pxni()=yi(i=0,1,"n)(2.5)

则称Pn(x)为f(x)的n次代数插值多项式.求满足以上条件多项

式Pn(x)的问题叫做代数插值问题.称x0,x1,…,xn为插值节点，
[a,b]为插值区间，（2.5）为插值条件.

6/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.2代数插值多项式的存在唯一性
代数插值
问题是否
可解？

2
J0x
0.3
0.3
0.2
0.2HL
0.1
0.1
x5101520
5101520-0.1
-0.1
-0.2
-0.2

7/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.2代数插值多项式的存在唯一性

多项式
局部近似
以直代曲
以简代繁

多项式
整体近似
以直代曲

8/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.2代数插值多项式的存在唯一性

定理2.2.1n次代数插值问题的解是存在且惟一的.

证：因为x0,x1,…,xn是在[a,b]上取定的n+1个互异节点,
由例2.1.1中分析过程可知，代数方程组的解存在唯一，从

而满足插值条件(2.5)的n次代数插值多项式Pn(x)也是存
在唯一的.

9/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
§2.3代数插值多项式的存在唯一性

目标：
设计计算量小、实现简单的计算
机算法，根据输入的n+1个点生
产n次代数插值多项式.

约瑟夫.路易斯.拉格朗日
评价：（1735~1813）
采用例2.1.1中的待定系数法求n次代
数插值多项式不符合目标.
拉格朗日提出直接构造多项式的方法.

10/168郑州大学2011-2012学年硕士研究生课程数值分析NumericalAnalysis
线性插值（n=1)
§2.3拉格朗日插值方法

给定两个互异点(x0，y0)，(x1，y1），确定一

次插值多项式P1(x)的问题，称为线性插值问题.

xx−1xx−0
Px10()=+yy1(2.6)
xx01−