数值分析常用的插值方法

.

数值分析

报告

.

班 级：

专 业：

流水号：

学 号：

姓 名：

.

常用的插值方法

序言

在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数

据点。插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状

况，估算出函数在其他点处的近似值。

早在6世纪，中国的刘焯已将等距二次插值用于天文计算。17世纪之后，牛顿、

拉格朗日分别讨论了等距和非等距的一般插值公式。在近代，插值法仍然是数据处

理和编制函数表的常用工具，又是数值积分、数值微分、非线性方程求根和微分方

程数值解法的重要基础，许多求解计算公式都是以插值为基础导出的。

插值问题的提法是：假定区间[a，b〕上的实值函数f（x）在该区间上 n＋1个

互不相同点x

0

，x

1

……x

n

处的值是f（x

0

），……f（x

n

），要求估算f（x）在[a，b〕中

某点的值。其做法是：在事先选定的一个由简单函数构成的有n＋1个参数C

0

，

C

1

，……C

n

的函数类Φ(C

0

，C

1

，……C

n

)中求出满足条件P（x

i

）＝f（x

i

）（i＝0，1，……

n）的函数P(x)，并以P(x)作为f(x)的估值。此处f（x）称为被插值函数，x

0

，x

1

，……xn

称为插值结(节)点，Φ(C

0

，C

1

，……C

n

)称为插值函数类，上面等式称为插值条件，Φ

（C

0

，……C

n

）中满足上式的函数称为插值函数，R（x）＝ f（x）－P（x）称为插

值余项。

.

.

求解这类问题，它有很多种插值法，其中以拉格朗日(Lagrange)插值和牛顿

(Newton)插值为代表的多项式插值最有特点，常用的插值还有Hermit插值，分段插

值和样条插值。

一．拉格朗日插值

1.问题提出：

已知函数

yf



x



在n+1个点

x

0

,x

1

,,x

n

上的函数值

y

0

,y

1

,,y

n

，求任意一点

x



的函数值

f



x





。

说明：函数

yf



x



可能是未知的；也可能是已知的，但它比较复杂，很难计

算其函数值

f



x





。

2.解决方法：

构造一个n次代数多项式函数

P

n



x



来替代未知（或复杂）函数

yf



x



，则





用

P

n



x



作为函数值

f



x



的近似值。

2

设

P

n



x



a

0

a

1

xa

2

xa

n

x

n

，构造

P

n



x



即是确定n+1个多项式的系数

a

0

,a

1

,a

2

,,a

n

。

3.构造

P

n



x



的依据：

当多项式函数

P

n



x



也同时过已知的n+1个点时，我们可以认为多项式函数

P

n



x



逼近于原来的函数

f



x



。根据这个条件，可以写出非齐次线性方程组：



a

0

a

1

x

0

a

2

x

0

2





2



a

0

a

1

x

1

a

2

x

1







2





a

0

a

1

x

n

a

2

x

n



其系数矩阵的行列式D为范德萌行列式：

a

n

x

0

n

y

0

a

n

x

1

n

y

1

a

n

x

n

n

y

n

D

1x

0

1x

1

1x

n

x

0

2

x

1

2

x

n

2

x

0

n

x

1

n

x

n

n



nij0





xx



ij

.

.

故当n+1个点的横坐标

x

0

,x

1

,,x

n

各不相同时，方程组系数矩阵的行列式D不等于

零，故方程组有唯一解。即有以下结论。

结论：当已知的n+1个点的横坐标

x

0

,x

1

,,x

n

各不相同时，则总能够构造唯一的n

次多项式函数

P

n



x



，使

P

n



x



也过这n+1个点。

4.几何意义

f(x)

P

5

(x)

5．举例：

已知函数

f



x



x

，求

f



115



。

分析：本题理解为，已知“复杂”函数

f



x



x

，当x=81,100,121,144时，其对

应的函数值为：y=9,10,11,12，当x=115时，求函数值

f



115



。

解：

（1）线性插值：过已知的（100,10）和（121,11）两个点，构造1次多项式函

数

P

1



x



，于是有

P

1



x





x121x100

1011

100121121100

则

f



115



P

1



115



10.772

。

（2）抛物插值：构造2次多项式函数

P

2



x



，使得它过已知的（100,10）、（121,11）

和（144,12）三个点。于是有2次拉格朗日插值多项式：

x121



x144



x100



x144



x100



x121



P

2



x



101112

100121100144121100121144144100144121



.

.

则有

f



115



P

2



115





10.72275550536420

6.拉格朗日n次插值多项式公式：

P

n



x







xx

1



xx

2





x

0

x

1



x

0

x

2





xx

0



xx

2







x

1

x

0



x

1

x

2









xx

n



y



x

0

x

n



0



xx

n



y



x

1

x

n



1



xx

0



xx

1



xx

n1



y



x

n

x

0



x

n

x

1



x

n

x

n1



n

l

n



x



y

n





l

k



x



y

k

k0

n

P

n



x



l

0



x



y

0

l

1



x



y

1



其中

l

k



x



称为基函数（k=0,1,….,n），每一个基函数都是关于x的n次多项式，

其表达式为：

l

k



x







j0

jk

n

xx

j

x

k

x

j

拉格朗日公式特点：

1．把每一点的纵坐标

y

k

单独组成一项；

2.每一项中的分子是关于x的n次多项式，分母是一个常数；

3.每一项的分子和分母的形式非常相似，不同的是：

分子是



x



，而分母是



x

k





f









n

P

n



x



f



x







xx

k



，



n1!



k0

n1

7.误差分析（拉格朗日余项定理）

其中



在

x

0

,x

1

,,x

n

,x

所界定的范围内。

针对以上例题的线性插值，有

.

.

f









P



115100



115121



1



115



f



115





2!

函数

f





x



在[100,115]区间绝对值的极大值为

f





100



2.510

4

，

则有：

P

1



115



f



115



0.011250.05

于是近似值

f



115



P

1



115



10.772

有三位有效数字。

针对以上例题的抛物线插值，有

f









P

2



115



f



115







115100



115121



115144



3!

函数

f





x



在[100,115]区间绝对值的极大值为

f





100



3.7510

6

，则有

P

2



115



f



115



0.00163125<0.005

于是近似值

f



115



P

2



115





10.72275550536420有四位有效数字。

8.拉格朗日插值公式的优点

公式有较强的规律性，容易编写程序利用计算机进行数值计算。

9. 拉格朗日插值通用程序

程序流程图如下：

.

.

开始

输入 n

x[i],y[i],（i=0,1,n）

t（即插值点x）

p＝0，k＝0

k<=n

n

yy

l＝1，j＝0

j

n

y

l＝l*(t-x[j])/(x[k]-x[j])

j=j+1

j=k+1

j<＝n

n

y

l＝l*(t-x[j])/(x[k]-x[j])

j=j+1

p=p+l*y[k]

k=k+1

输出p

结束

.

开始

输入 n

x[i],y[i],（i=0,1,n）

t（即插值点x）

p＝0，k＝0

k<=n

n

yy

计算l(k)

p=p+l*y[k]

k=k+1

输出p

结束

.

l＝1，j＝0

n

j

y

l＝l*(t-x[j])/(x[k]-x[j])

j=j+1

j=k+1

n

j<＝n

y

l＝l*(t-x[j])/(x[k]-x[j])

j=j+1

文件lagrange.m如下：

%拉格朗日插值

close all

n=input('已知的坐标点数n=?');

x=input('x1,x2,...,xn=?');

y=input('y1,y2,...,yn=?');

xx=input('插值点=？');

syms t %定义t为符号量

p=0;

for k=1:n

l=1;

for j=1:k-1

l=l*(t-x(j))/(x(k)-x(j));

end

for j=k+1:n

.

.

l=l*(t-x(j))/(x(k)-x(j));

end

p=p+l*y(k);

end

p=inline(p); %把符号算式p变为函数形式

fplot(p,[min(min(x),xx)-1,max(max(x),xx)+1]); %画多项式函数

hold on

p(xx)

plot(x,y,'o',xx,p(xx),'*');

在MATLAB命令窗口输入：

lagrange

然后有以下对话过程和结果，

已知的坐标点数n=?6

x1,x2,...,xn=?[1,3,5,7,9,11]

y1,y2,...,yn=?[-1,20,0,-1,12,3]

插值点=？8

ans =

5.670

有以下图形：

.

%显示插值点

%画已知点和插值点

.

二．牛顿插值

拉格朗日插值的缺点：无承袭性（继承性）

若算出3点的抛物插值精度不够，再进行4点的3次多项式插值时，必须从头

算起，前面算出的3点抛物插值的计算结果不能利用。

而泰勒插值却是具有承袭性的，如线性插值的结果不精确，那么再加上一项，

就变成了泰勒抛物插值，如：



泰勒1次插值：

P

1



x



f



x

0



f



x

0



xx

0



泰勒2次插值：

P

2



x



f



x

0



f





x

0



xx

0





而牛顿插值就是具有承袭性的插值公式

1.差商的概念

设n+1个点

x

0

,x

1

,,x

n

互不相等，则定义：

f





x

0



2



xx

0



。

2!

x

i

和

x

j



ij



两点的一阶差商为：

f





x

i

,x

j







f



x

i



f



x

j



x

i

x

j

f



x

i

,x

j



f



x

j

,x

k







x

i

,

x

j

,x

k

三点的二阶差商为：

f



x,x,x

ijk



x

i

x

k

f



x

i

,x

j

,x

k



f



x

j

,x

k

,x

l







x

i

,

x

j

,x

k

,x

l

四点的三阶差商为：

f



x,x,x,x

ijkl



x

i

x

l

.

.

……

n+1个点

x

0

,x

1

,,x

n

的n阶差商为：

f



x

0

,x

1

,,x

n





f



x

0

,x

1

,,x

n1



f



x

1

,x

2

,

x

0

x

n

,x

n



差商具有对称性：

f





x

i

,

x

j





f





x

j

,

x

i





；

f





x

i

,

x

j

,

x

k





f





x

j

,

x

i

,

x

k





2.牛顿插值解决的问题与拉格朗日插值解决的问题相同

只是表述 n次多项式

P

n



x



的公式不同。

3.牛顿插公式的推导

根据差商的概念，有：

f



x



f



x

0



f



x,x

0





xx

0



…………………

f



x,x

0



是

x,x

0

两点的一阶差商；

f



x,x

0



f



x

0

,x

1



f



x,x

0

,x

1





xx

1



……

f



x,x

0

,x

1



是

x,x

0

,x

1

三点的二阶差商；

……

f



x,x

0

,,x

n1



f



x

0

,x

1

,,x

n



f



x,x

0

,x

1

,,x

n





xx

n



把以上各式从后向前逐次代入，可以得到：

f



x



f



x

0



f



x

0

,x

1





xx

0



f



x

0

,x

1

,x

2





xx

0



xx

1





f



x

0

,x

1

,

f



x,x

0

,x

1

,



xx

n1



,x

n





xx

0



xx

1



xx

n



,x

n





xx

0



xx

1



f



x



P

n



x



R

n



x



其中

P

n



x



f



x

0



f



x

0

,x

1





xx

0



f



x

0

,x

1

,x

2





xx

0



xx

1





f



x

0

,x

1

,,x

n





xx

0



xx

1



xx

n1



R

n



x



f



x,x

0

,x

1

,,x

n





xx

0



xx

1



xx

n



以上

P

n



x



的表达式称为牛顿插值公式，可以证明，n次牛顿插值多项式与n

次拉格朗日插值多项式完全相同，只是表达形式不同。

故，拉格朗日余项定理与牛顿余项定理相同：

.

.

R

n



x



P

n



x



f



x



f



x,x

0

,x

1

,,x

n







xx

k



k0

n

f









n





xx

k



，





n1



!

k0

n1

其中



在

x

0

,x

1

,,x

n

,x

所界定的范围内。

则有公式：

f



x,x

0

,x

1

,

4.牛顿插值差商表

xi

x0

x1

x2

x3

…

xn-1

xn

5.举例

yi

y0

y1

y2

y3

…

yn-1

yn

,x

n





f



n1











n1



!

一阶差商

f[x0,x1]

f[x1,x2]

f[x2,x3]

二阶差商

f[x0,x1,x2]

f[x1,x2,x3]

…

n阶差商

*

1

(x-x0)

(x-x0)(x-x1)

(x-x0)…(x-x2)

f[xn-1,xn] f[xn-2,xn-1,xn]

f[x0,…,xn] (x-x0)…(x-xn-1)

已知函数f(x)当x=-2,-1,0,1,2时，其对应函数值为f(x)=13,-8,-1,4,1。求f(0.5)的值。

解：该题目与例1相比，就是多了一个点，所以和例1的差商表相比，只需多一列，

多一行：

xi yi 一阶差

商

-2

-1

0

1

2

13

-8

-1

4

1

-21

7

5

-3

二阶差

商

14

-1

-4

三阶差

商

-5

-1

四阶差

商

1

1

(x+2)

(x+2)(x+1)

(x+2)(x+1)x

(x+2)(x+1)x(x-1)

*

.

.

而5个点的4次牛顿插值多项式

P

4



x



是在

P

3



x



的基础上多增加1项：

P

4



x



1321



x2



14



x2



x1



5



x2



x1



x



x2



x1



x



x1



则

f



0.5



P

4



0.5



1321



0.52



14



0.52



0.51



5



0.52



0.51



0.5



0.52



0.51



0.5



0.5

2.6875

可以在MATLAB下运行程序newton02.m：

p4=inline('13-21*(x+2)+14*(x+2)*(x+1)-5*(x+2)*(x+1)*x+(x+2)*(x+1)*x*(x-1)');

fplot(p4,[-2.5,2.5],'r');

hold on

xi=[-2,-1,0,1,2];

yi=[13,-8,-1,4,1];

plot(xi,yi,

'*');

plot(0.5,p4(0.5),'o');

可以得到以下图形：

6.牛顿插值的优点

（1）具有承袭性质

（2）利用差商表，计算多点插值，比拉格朗日公式计算方便。

7.牛顿插值算法的通用程序

.

.

以下是程序流程图：

开始

输入 n

x[i],y[i],（i=0,1,n）

t（即插值点x）

f[i]=y[i],i=0,…,n

i=1

i<=n

n

yy

k=n

k>=i

n

y

f[k]=(f[k-1]-f[k])/

(x[k-i]-x[k])

k=k-1

i=i+1

1

MATLAB的通用程序newton.m为：

%牛顿插值

close all

n=input('已知的坐标点数n=?');

x=input('x1,x2,...,xn=?');

y=input('y1,y2,...,yn=?');

xx=input('插值点=？');

% 计算差商：f[x1,x2],f[x1,x2,x3],...,f[x1,x2,...,xn]

.

1

p=f[0],k=1

k<=n

n

y

l=1,j=0

j<＝k-1

n

y

l＝l*(t-x[j])

j=j+1

p＝p+f[k]*l

k=k+1

输出p

结束

.

f=y;

for i=1:n-1 % 计算第i阶差商

for k=n:-1:i+1

f(k)=(f(k)-f(k-1))/(x(k)-x(k-i));

end

end

syms t %定义t为符号量

p=f(1);

for k=2:n

l=1;

for j=1:k-1

l=l*(t-x(j));

end

p=p+l*f(k);

end

p=inline(p);

fplot(p,[min(min(x),xx)-1,max(max(x),xx)+1]);

hold on

p(xx)

plot(x,y,'o',xx,p(xx),'*');

在MATLAB命令窗口输入：

newton

然后有以下对话过程和结果，

已知的坐标点数n=?6

x1,x2,...,xn=?[1,3,5,7,9,11]

.

%把符号算式p变为函数形式

%画多项式函数

%显示插值点

%画已知点和插值点

.

y1,y2,...,yn=?[-1,20,0,-1,12,3]

插值点=？8

ans =

5.670

有以下图形：

三．总结和展望

插值与逼近都是指用某个简单的函数在满足一定条件下在某个范围内近似代替

另一个较复杂的函数或解析表达式未能给出的函数，以便于简化对后者的各种计算

或揭示后者的某些性质。

插值方法理论是近似计算和逼近函数的有效方法。此外，它也是数值微积分，

微分方程数值解等数值分析的基础。在图形处理等很多需要优化的实际中，也有着

很广泛的应用。我们期望在以后的生活中会更加熟练和更好的运用插值方法。

.

.

参考文献

［1］李庆扬,王能超,易大义. 数值分析[M]. :华中科技大学出版社,1982.

［2］吴才斌. 插值方法[J]. 湖北大学成人教育学院学报,1999,(5).

［3］徐萃薇,孙绳武. 计算方法引论[M]. :高等教育出版社,2002.

［4］林鹭. 拉格朗日插值多项式的一种并行算法[J]. 厦门大学学报:自然科学版,

2004,43(5):592-595.

［5］吴筑筑. 计算方法[M]. :清华大学出版社,2004:61-84.

［6］杨士俊,王兴华. Hermite 插值多项式的差商表示及其应用[J]. 高校应用数学学

报A 辑,2006,21(1):70-78.

［7］齐东旭,李华山.数据逼近的多结点样条技术[J].中国科学(E 辑),1999,29(4):

334-387.

［8］王仁宏. 数值逼近[M]. :高等教育出版社,1999.

［9］孙亮. 数值分析方法课程的特点与思想[J]. 工科数学,2002,18(1):84-86.

.