牛顿插值法

牛顿插值法

采购质量-田蓉

2023年2月20日发(作者：手链的编法)

实用文档

标准文案

牛顿插值法

插值法是利用函数f(x)在某区间中若干点的函数值，作出适当的特定函数，

在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f(x)的近

似值。如果这特定函数是多项式，就称它为插值多项式。当插值节点增减时全部

插值基函数均要随之变化，这在实际计算中很不方便。为了克服这一缺点，提出

了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式：

f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0

)...(x-xn-1)+Rn(x)。

插值函数

插值函数的概念及相关性质[1]

定义：设连续函数y-f(x)在区间[a,b]上有定义，已知在n+1个互异的点

x0,x1,…xn上取值分别为y0,y1,…yn（设a≤x1≤x2……≤xn≤b)。若在函

数类中存在以简单函数P(x)，使得P(xi)=yi,则称P(x)为f(x)的插值函数.

称x1,x2,…xn为插值节点，称[a,b]为插值区间。

定理：n次代数插值问题的解存在且唯一。

实用文档

标准文案

牛顿插值法C程序

程序框图#include

voidmain()

{

floatx[11],y[11][11],xx,temp,newton;

inti,j,n;

printf("Newton插值:n请输入要运算的值:x=");

scanf("%f",&xx);

printf("请输入插值的次数(n<11):n=");

scanf("%d",&n);

printf("请输入%d组值:n",n+1);

for(i=0;i

{printf("x%d=",i);

scanf("%f",&x[i]);

printf("y%d=",i);

scanf("%f",&y[0][i]);

实用文档

标准文案

}

for(i=1;i

for(j=i;j

{if(i>1)

y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-

x[j-i]);

else

y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-1]);

printf("%fn",y[i][i]);

}

temp=1;newton=y[0][0];

for(i=1;i

{temp=temp*(xx-x[i-1]);

newton=newton+y[i][i]*temp;

}

printf("求得的结果为:N(%.4f)=%9fn",xx,newton);

牛顿插值法Matlab程序

functionf=Newton(x,y,x0)

symst;

if(length(x)==length(y))

n=length(x);

c(1:n)=0.0;

else

实用文档

标准文案

disp('x和y的维数不相等！');

return;

end

f=y(1);

y1=0;

l=1;

for(i=1:n-1)

for(j=i+1:n)

y1(j)=(y(j)-y(i))/(x(j)-x(i));

end

c(i)=y1(i+1);

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

f=f+c(i)*l;

simplify(f);

y=y1;

if(i==n-1)

if(nargin==3)

f=subs(f,'t',x0);

else

f=collect(f);%

将插值多项式展开

f=vpa(f,6);

end

end

实用文档

标准文案

牛顿插值法

摘要：值法利用函数f(x)在某区间中若干点的函数值，作出适

当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函

数的值作为函数f(x)的近似值。如果这特定函数是多项式，就称它为

插值多项式。利用插值基函数很容易得到拉格朗日插值多项式，公式

结构紧凑，在理论分析中甚为方便，但当插值节点增减时全部插值基

函数均要随之变化，整个公式也将发生变化，这在实际计算中是很

不方便的，为了克服这一缺点，提出了牛顿插值。

牛顿插值通过求各阶差商，递推得到的一个公式：

f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x

0)...(x-xn-1)+Rn(x)

关键词：牛顿插值法流程图程序实现

一、插值法的由来

在许多实际问题及科学研究中，因素之间往往存在着函数关系，

然而，这种关系经常很难有明显的解析表达，通常只是由观察与测试

得到一些离散数值。有时，即使给出了解析表达式，却由于表达式过

于复杂，不仅使用不便，而且不易于进行计算与理论分析。解决这类

问题的方法有两种：一种是插值法,另一种是拟合法。插值法是一种

古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在

实用文档

标准文案

研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微

积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机软

件中，许多库函数，如等的计算实际上归结于它的逼近函数的计算。

逼近函数一般为只含有算术运算的简单函数，如多项式、有理分式（即

多项式的商）。在工程实际问题当中，我们也经常会碰到诸如此类的

函数值计算问题。被计算的函数有时不容易直接计算，如表达式过于

复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或

者导数值信息等。因此，我们希望能用一个“简单函数”逼近被计算

函数，然后用该简单函数的函数值近似替代被计算函数的函数值。这

种方法就叫插值逼近或者插值法。

逐次线性插值法优点是能够最有效地计算任何给定点的函数值，

而不需要写出各步用到的插值多项式的表达式。但如果解决某个问题

时需要插值多项式的表达式，那么，它的这个优点就成了它的缺点了。

能不能根据插值条件构造一个插值多项式，它既有具体的表达式，又

很容易用它计算任何点的函数值呢？牛顿插值法能作到这一点。

二、牛顿插值法的概念

牛顿插值多项式的表达式

设

)())(())(()(

110102010xxxxxxcxxxxcxxccNnnn



问题是如何根据插值条件



y

xN

i

in



,i=0,1,2n

来计算待定系数

ccccn



210

,,

？

实用文档

标准文案

由

)()(

0

0

0x

y

xNf

n



知，

)(

0

0

0x

y

cf

。

由

)()(

1

1

1x

y

xNf

n



知

y

xxcc

1

0110

)(

因而



xx

xx

xx

xx

yy

cf

ff

10

01

01

01

01

1

,

)()(















，

其中



xxf

10

,

称为函数f(x)在

xx10

,

点的一阶商。

由

)()(

2

2

2x

y

xNf

n



知

y

xxxxcxxcc

2

120220110

))(()(

因而

实用文档

标准文案





],,[

)(

],[],[

)(

],[

))((

)](,[)](,[

))((

)](,[

))((

)](,[

210

02

1021

02

10

12

12

1202

02100110

12

1202

0210

0112

1202

0210

02

2

xxx

xx

xxxx

xx

xx

xx

yy

xxxx

xxxxxxxx

yy

xxxx

xxxx

yyyy

xxxx

xxxx

yy

c

f

ff

f

ff

f

f





































其中

],,[

210xxxf

称为函数f(x)在

xxx210

,,

点的二阶差商。实际上，它

是一阶差商的差商。一般地，如果已知一阶差商

],[],,[

11xxxxiiii

ff

，

那么就可以计算二

阶差商

xx

xxxx

xxx

ii

iiii

iii

ff

f

11

11

11_

],[],[

],,[











类似于上述过程不断地推导下去，可得

],,,[

)(

],,[],[

],,,,,[

)(

],,,[],,,[

],,,,[

)(

],,[],,[

210

0

121021

4

43210

04

32104321

4

3210

03

210321

3

xxxx

xx

xxxxxxx

c

xxxxx

xx

xxxxxxxx

c

xxxx

xx

xxxxxx

c

n

n

nnf

ff

f

ff

f

ff





























其中，

],,,,[

3210xxxxf],,,,,[

43210xxxxxf],,,,,,[

543210xxxxxxf分别称为函数

f(x)在相应点处的三阶差商，四阶差商和n阶差商。实际上，

实用文档

标准文案

ccccn



210

,,

的计算可通过以下简易地构造函数的差商来完成。

x0cxf

00

)(

x1

)(

1xfcxxf

110

],[

x2

)(

2xf],[

21xxfcxxxf

2210

],,[

x3

)(

3xf],[

32xxf

],

1

[

3

2

,

x

x

xfcxxxxf

33210

],,,[

x4

)(

4xf],[

43xxf],,[

432xxxf

],,

1

[

43

2

,

xx

x

xfcxxxxxf

443210

],,,,[

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

按上述方式构造插值多项式的方法叫做牛顿插值法。根据插值多项式

的惟一性知，其截断误差与拉格朗日插值法相同，

即：

)()(

)!1(

1π1

)1(x

nn

n

n

f

R







但也可以表示成差商形式。这是因为以

xxxxn



210

,,

为节点的多项式

)(],[)()(

1

1101xxxxNNn

nnn

fxx









从而

)(],[)()()(

1

1

1101111xxxxxNxNxn

n

nnnnnn

ff







实用文档

标准文案

于是

)(xNn的截断误差可表为

)(],,,[)(

1

110

xfx

n

n

nxxxx

R





顺便指出，因为牛顿插值多项式具有性质：

)())(](,[)()(

121101xxxxxxxxxNNnnnn

fxx





所以，类似于逐次线性插值法，也可以把上述和式中的第二项

)())(](,[

12110xxxxxxxxxnn

f





看成是估计

)(

1

xNn的一种实用误差估计式。

与差商概念密切联系的另一个概念是差分，它是指在等距节点上函数

值的差。所谓等距节点，是指对给定的常数h（称为步长），节点

)2,1,0(,

0

niihxxi



称

f

xx

k

ii

ff



)()(

1为

xi处的一阶向前差

分；

称

f

xx

i

ii

ff



)()(

1

为

xi处的一阶向后差分；

称

f

xx

i

h

i

h

i

ff)1()(

22

为

xi处的中心差分。一阶差分的差分称为二阶差分，

即

fff

iii





2

1

称为

xi处的二阶向前差分。

一般地，m阶向前和向后差分可定义如下：















































3,2

,

,

1

1

1

1

1

1

m

m

m

ff

f

ff

f

i

m

i

m

i

i

m

i

m

i

实用文档

标准文案

三、牛顿插值法的实现

1、【算法】

步骤1：输入节点（xj，yj），精度



，计值点xx，f0p，1T，1i；

步骤2：对k=1，2，……，i依次计算k阶均差

f[xi-k,xi-k+1,…,xi]=(f[xi-k+1,…,xi]-f[xi-k,…,xi])/(xi-xi-k)

步骤3：（1）、若|f[x1,…,xi]-f[x0,…,xi-1]|<



，则p为最终结果Ni-1(x)，

余项Ri-1=f[x0,…,xi](xx-xi-1)T。

（2）、否则(xx-xi-1)*TT，p+f[x0,…,xi]*Tp，转步骤4。

步骤4：若i

实用文档

标准文案

2、【流程图】

i+1



i

YES

NO

开始

输出，xx，n及（x

j

，y

j

）

f

0

g

0

，f

i



q

0

k=1，2，……，i

（q

k-1

－g

k-1

）（x

i

－x

i-k

）q

k

k

|g

i-1

-q

i-1

|<

q

i

(x

i

-x

i-1

)TR

输出p，r，i

STOP1

(x

i

-x

i-1

)TT

p+q

i

*Tp

k=1，2，……，i

实用文档

标准文案

YES

i+1i

NO

q

k

g

k

k

k

q

i

(xx-x

n-1

)*TR

输出P，R，n

STOP2

实用文档

标准文案

3、【程序清单】#include"stdio.h"

#definen4//牛顿插值的次数

voidmain()

{

floata[n+1][n+2]={0},s=0,t=1,x;

inti,j;

printf("请输入xi及yi的值//要求先输入xi再输入yi然后输入下一组

n");

for(i=0;i

for(j=0;j<2;j++)

scanf("%f",&a[i][j]);

for(j=1;j

for(i=j;i

a[i][j+1]=(a[i][j]-a[i-1][j])/(a[i][0]-a[i-j][0]);

printf("输出xi，yi及各阶均差n");

for(i=0;i

{

for(j=0;j

printf("%6.5f",a[i][j]);

printf("n");

}

实用文档

标准文案

printf("输出牛顿插值表达式n");

printf("N%d(x)=",n);

for(i=0;i

{

printf("%6.5f",a[i][i+1]);

for(j=0;j

printf("(x-%3.2f)",a[j][0]);

if(i==n)

break;

printf("+");

}

printf("n");

printf("输入插值点x=");

scanf("%f",&x);

for(i=0;i

{

for(j=0;j

t*=(x-a[j][0]);s+=a[i][i+1]*t;

}printf("N%d(%4.3f)=%6.5fn",n,x,s);}

4.【程序实现】

实用文档

标准文案

实用文档

标准文案

参考文献:

,sFaires,NumericalAnalysis

(SeventhEdition),.,2001.

2.蔡大用，白峰杉.高等数值分析.清华大学出版社，北京，1998.

3.邓建中，刘之行.计算方法（第二版）.西安交通大学出版社，2001.

4.韩旭里.数值分析.中南大学出版社，2003.

实用文档

标准文案

致谢

本文得以顺利完成，非常感谢我的指导教师。从论文的选题直到论文的

最终完成，他都给予我尽心尽力的指导。老师严谨的治学态度深深地影响着我，

对我今后的学习，工作，生活必将产生影响。借此机会，特向老师表示最诚挚的

感谢。

感谢南昌工程学院理学系的所有领导和老师。他们严谨的学风，渊博的知识，

诲人不倦的品格一直感染和激励着我不断上进，使我大学四年的时光充实而有意

义，“自强不息，格物致知”，在这里我所学到的一切，必将使我受益终生。

在本论文的写作中，我也参照了大量的著作和文章，许多学者的科研成果及

写作思路给了我很大的启发，在此向这些学者们表示由衷的感谢，感谢我的家人，

同学，朋友对我的大力支持，他们的无私奉献，关爱和支持使我能够继续去追求

自己的人生理想和目标。感谢所有关心，帮助和支持我的人。