牛顿插值法

姓名： 邓力群 班级： 08信息与计算科学 学号： 2008101183 课题名称： 牛顿法—插值法

指导老师： 龚建华

2011年 6月 4日

牛顿法——牛顿插值法

摘要： 插值法利用函数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：输入节点（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//牛顿插值程序 //2004-10-23

#include #include #define n 6 void main() {

double x[n],f[n]; double q[n][n]; double temp,g,xx;

cout<<\"请输入(Xi,Fi):\"<cout<<\"请输入X\"<>x[i]>>f[i]; }

cout<<\"请输入插值点：\";

cin>>xx;

for(i = 0;ifor(int j = 1;j<=i;j++)

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

for(i = 0;ifor(int j = 0;j<=i;j++) {

cout<cout<temp = 1.00; g = q[0][0];

for(i = 1;itemp = temp*(xx-x[i-1]); g = g+q[i][i]*temp; }

cout<<\"F(\"<【程序测试】

牛顿插值法具体实例

设设在给定点x1处对函数进行二次逼近。二次逼近q如下定义：

q(x)f(x1)f'(xx1)12f''(x1)(xx1)2

k1令x2是使过程当xq0的点，并重复这个过程：

或者

'xxkf(x)f(x) k=0,1,2,该

k''k'k1xkf(x)k'''时停止，其中是一个很小的数。该方法只

能用于二次可微函数，

f(x)0

2（1）．取误差限0.01，从x=4开始，用牛顿法极小化f(x)=x由于f(x)2x2。应用牛顿迭代法，得迭代计算格式

2x

xk1xkxk22xk，（k= 0，1，2，……）取x0= 4为初值，

2xk2输入初始值x0:4

输入精确值accurate:0.01

x[1]=4.000000 f(x[1])=24.000000 x[2]=-1.000000 f(x[2])=-1.000000

443x3x,x0f(x)34 4x3x,x0例（2）取误差限0.01，从x=4开始，用牛顿法极小化

步骤：

（1） 选一个接近于x的真实根的近似根x1；

q(x)f(x1)（2） 通过求x2;

f'1(xx1)2f(x)(xx1)1''2令x2是使

q0的点

'（3） 并重复（2）过程：

x止

k1xkf(x)f(x) k=0,1,2,该过程当xk''k'k1xk或者

f(x)k'时停

（4） 一直求下去，直到接近真正的根。当两次求出的根之差停止

xk1xk就

xk1xk牛顿迭代公式是：输入初始值x0:4

输入精确值accurate:0.01

f(x)f(x)

k''k'x[1]=4.000000 f(x[1])=-512.000000 x[2]=2.800000 f(x[2])=-96.588800 x[3]=2.012500 f(x[3])=-16.607539 x[4]=1.507817 f(x[4])=-1.794416 x[5]=1.204385 f(x[5])=0.675821 x[6]=1.051791 f(x[6])=0.982773 x[7]=1.004643 f(x[7])=0.999870

例（3）取误差限0.01，从x=0.6开始,重做（2）。讨论用该方法会发生什么现象。

输入初始值x0:0.6 输入精确值accurate:0.01 输入初始值x0:0.6 输入精确值accurate:0.01

x[1]=0.600000 f(x[1])=0.475200 x[2]=-0.600000 f(x[2])=-0.475200

x[3]=-0.827608 f(x[3])=-0.860023 x[4]=-1.158643 f(x[4])=-0.815152 x[5]=-1.598022 f(x[5])=3.240444 x[6]=-2.122156 f(x[6])=22.616865

x[7]=-2.699757 f(x[7])=80.664133 x[8]=-3.308431 f(x[8])=214.573428 x[9]=-3.935325 f(x[9])=475.738982 x[10]=-4.573380 f(x[10])=929.789032 x[11]=-5.218623 f(x[11])=1656.580672 x[12]=-5.868713 f(x[12])=2750.195941 x[13]=-6.522204 f(x[13])=4318.940133 x[14]=-7.178162 f(x[14])=6485.341129 x[15]=-7.835963 f(x[15])=9386.149140 x[16]=-8.495174 f(x[16])=13172.336610 x[17]=-9.155487 f(x[17])=18009.098183 x[18]=-9.816676 f(x[18])=24075.850691 x[19]=-10.478573 f(x[19])=31566.233158 x[20]=-11.141050 f(x[20])=40688.106800 x[21]=-11.804007 f(x[21])=51663.555035 x[22]=-12.467368 f(x[22])=64728.883480 x[23]=-13.131069 f(x[23])=80134.619961 x[24]=-13.795062 f(x[24])=98145.514509

•••陷入死循环

附录

例题（1）程序

#include #include

double f(double x) {

return pow(x,2)+2*x; }

double g(double x) {

return 2*x+2; }

double h(double x) {

return 2; }

void main() {

int i,j;

double x0,accurate,x[1000],Abc; printf(\"输入初始值x0:\"); scanf(\"%lf\

printf(\"输入精确值accurate:\"); scanf(\"%lf\ i=1; x[0]=x0;

x[1]=x[0]-g(x0)/h(x0); Abc=x[i]-x[i-1]; if(fabs(Abc)>accurate) {

do {

x[i+1]=x[i]-g(x[i])/h(x[i]); i++;

Abc=x[i]-x[i-1];

}while(fabs(Abc)>accurate); }

for(j=0;jprintf(\"x[%d]=%lf f(x[%d])=%lf\\n \ } }

例题（2）程序

#include #include

double f(double x) {

if(x>0)

return 4*pow(x,3)-3*pow(x,4); if(x<0)

return 4*pow(x,3)+3*pow(x,4); }

double g(double x) {

if(x>0)

return 12*pow(x,2)-12*pow(x,3); if(x<0)

return 12*pow(x,3)+12*pow(x,3); }

double h(double x) {

if(x>0)

return 24*x-36*pow(x,2); if(x<0)

return 25*x+36*pow(x,3); }

void main() {

int i,j;

double x0,accurate,x[1000],Abc; printf(\"输入初始值x0:\"); scanf(\"%lf\

printf(\"输入精确值accurate:\"); scanf(\"%lf\ i=1; x[0]=x0;

x[1]=x[0]-g(x0)/h(x0); Abc=x[i]-x[i-1]; if(fabs(Abc)>accurate) {

do {

x[i+1]=x[i]-g(x[i])/h(x[i]); i++;

Abc=x[i]-x[i-1];

}while(i<100); }

for(j=0;jprintf(\"x[%d]=%lf f(x[%d])=%lf\\n \ } }

五. 参考文献

[1]龙熙华.数值分析[M].西安:陕西科学技术出版社,2000.20-22.

[2]《数值分析简明教程》-2 Editon -高等教育出版社 -page 136 -算法流程图 [3] 谭浩强 C程序设计[M] 清华大学出版社 1999年12月第2版 [4] 《数值计算方法》，冯天祥编着.四川科技出版社.2003 [5] 百度百科 牛顿迭代法

[6] 《数值计算方法》 杨一都编着. 高等教育出版社 2008.4