Newton插值法流程图

牛顿插值法插值法是利用函数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<stdio.h>void main(){float x[11],y[11][11],xx,temp,newton;int i,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<n+1;i++){ printf("x%d=",i);scanf("%f",&x[i]);printf("y%d=",i);scanf("%f",&y[0][i]);}for(i=1;i<n+1;i++)for(j=i;j<n+1;j++){ if(i>1)y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-i]);elsey[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-1]);printf("%f\n",y[i][i]);}temp=1;newton=y[0][0];for(i=1;i<n+1;i++){ temp=temp*(xx-x[i-1]);newton=newton+y[i][i]*temp;}printf("求得的结果为:N(%.4f)=%9f\n",xx,newton);牛顿插值法Matlab程序function f = Newton(x,y,x0)syms t;if(length(x) == length(y))n = length(x);c(1:n) = 0.0;elsedisp(&apos;x和y的维数不相等！&apos;);return;endf = 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));endc(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,&apos;t&apos;,x0);elsef = collect(f); %将插值多项式展开f = vpa(f, 6);endend牛顿插值法摘要：值法利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。

牛顿和拉格朗日插值算法源代码及流程图-报告流程图找站长要//编译平台：2000＋vc6.0//实验一//作者：计算机科学与技术#include<stdio.h>#include<stdlib.h>#include<iostream.h>typedef struct data{float x;float y;}Data;//变量x和函数值y的结构Data d[20];//最多二十组数据float f(int s,int t)//牛顿插值法，用以返回插商{if(t==s+1)return (d[t].y-d[s].y)/(d[t].x-d[s].x);elsereturn (f(s+1,t)-f(s,t-1))/(d[t].x-d[s].x); }float Newton(float x,int count){int n;while(1){cout<<"请输入n值(即n次插值):";//获得插值次数cin>>n;if(n<=count-1)// 插值次数不得大于count－1次break;elsesystem("cls");}//初始化t，y，yt。

float t=1.0;float y=d[0].y;float yt=0.0;//计算y值for(int j=1;j<=n;j++){t=(x-d[j-1].x)*t;yt=f(0,j)*t;//cout<<f(0,j)<<endl;y=y+yt;}return y;}float lagrange(float x,int count){float y=0.0;for(int k=0;k<count;k++)//这儿默认为count－1次插值 {float p=1.0;//初始化pfor(int j=0;j<count;j++){//计算p的值if(k==j)continue;//判断是否为同一个数p=p*(x-d[j].x)/(d[k].x-d[j].x);}y=y+p*d[k].y;//求和}return y;//返回y的值}void main(){float x,y;int count;while(1){cout<<"请输入x[i],y[i]的组数，不得超过20组:";//要求用户输入数据组数cin>>count;if(count<=20)break;//检查输入的是否合法system("cls");}//获得各组数据for(int i=0;i<count;i++){cout<<"请输入第"<<i+1<<"组x的值:";cin>>d[i].x;cout<<"请输入第"<<i+1<<"组y的值:";cin>>d[i].y;system("cls");}cout<<"请输入x的值:";//获得变量x的值cin>>x;while(1){int choice=3;cout<<"请您选择使用哪种插值法计算："<<endl;cout<<" (0):退出"<<endl;cout<<" (1):Lagrange"<<endl;cout<<" (2):Newton"<<endl;cout<<"输入你的选择：";cin>>choice;//取得用户的选择项if(choice==2){cout<<"你选择了牛顿插值计算方法，其结果为：";y=Newton(x,count);break;//调用相应的处理函数}if(choice==1){cout<<"你选择了拉格朗日插值计算方法，其结果为："; y=lagrange(x,count);break;//调用相应的处理函数}if(choice==0)break;system("cls");cout<<"输入错误"<<endl;}cout<<x<<" , "<<y<<endl;//输出最终结果}。

2012-2013（1）专业课程实践论文牛顿插值公式王霄，0818180103，R数学08-1班插值法利用函数()x f 在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数()x f 的近似值。

如果这特定函数是多项式，就称它为插值多项式。

利用插值基函数很容易得到拉格朗日插值多项式，公式结构紧凑，在理论分析中甚为方便，但当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化， 这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值。

牛顿插值通过求各阶差商，递推得到的一个公式：[]()[]()()[]()()()x Rn x x x x x x f x x x x x x x f x x x x f x f x f n n +--++--+-+=-100102100100,, ,,,)()(牛顿（Newton ）插值法：若求i T 和1+i T 之间任一点T ，插值公式为：[]()[]()()[]()()100102100100,,,,,)(---++--+-+=n n x x x x x x f x x x x x x x f x x x x f x f T 式中，[]10,x x f ，[]210,,x x x f ， ，[]110,,,-n x x x f 是函数()x f 的1到第1-n 阶差商。

[]()()101010,x x x f x f x x f --=[][][]202110210,,,,x x x x f x x f x x x f --=[][][]1011021010,,,,,,,,,-----=n n n n x x x x x f x x x f x x x f可以看出，每一阶的差商都可以从它的前一阶差商推出。

按照此特点，选定牛顿插值的阶数3～4，然后计算各阶差商，按照插值公式计算插值点的值。

开始输入已知项项数n输入各已知项的值： i y i x _,_i j n i ><,[]()()kk k x x x f x f x x f --=000,输出newton令]0[,1diff newton tmp ==[]()[]()()[]()()100102100100,,,,,)(---++--+-+=n n x x x x x x f x x x x x x x f x x x x f x f T n i <结束#include<stdio.h>#define MAX 20typedef struct TPOINT{ double x;double y; }POINT;int main(){ int n,i,j;POINT points[MAX +1];double diff[MAX +1];double x,tmp,newton=0;printf("\n输入已知项项数n:");//n-1为插值次数scanf("%d",&n);printf("输入各已知项的值： (x_i,y_i)\n");for(i=0;i<n;i++)scanf("%lf%lf",&points[i].x,&points[i].y);printf("输入所要求解的x值:");scanf("%lf",&x);for(i=0;i<n;i++)diff[i]=points[i].y;for(i=0;i<n;i++){ for(j=n;j>i;j--){ diff[j]=(diff[j]-diff[j-1])/(points[j].x-points[j-1-i].x);} } tmp=1;newton=diff[0];for(i=0;i<n;i++){ tmp=tmp*(x-points[i].x);newton=newton+tmp*diff[i+1];}printf("f(%f)=%f\n",x,newton);return 0;}例1. 已知函数如下表：x10 11 12 13ln 2.3206 2.3979 2.4849 2.5649x求解Ln11.75的值。

Newton 插值的算法实现Lagrange 插值公式结构紧凑，便于理论分析。

利用插值基函数也容易到插值多项式的值。

Lagrange 插值公式的缺点是，当插值节点增加，或其位置变化时，全部插值基函数均要随之变化，从而整个插值公式的结构也发生变化，这在实际计算中是非常不利的。

下面引入的Newton 插值公式可以克服这个缺点。

1、问题描述当n=1时，由点斜式直线方程知，过两点00(,())x f x 和11(,())x f x 的直线方程为1010010()()()()().f x f x N x f x x x x x −=+−−若记 100110()()[,],f x f x f x x x x −=−则可把1()N x 写成10010()()[,]().N x f x f x x x x =+−显然，1()N x 就是一次Lagrange 插值多项式1()L x 。

由于1()y N x =表示通过两点00(,())x f x 和11(,())x f x 的直线，因此一次插值亦称为线性插值。

当n=2时，进而记120121*********[,][,]()()[,],[,,]f x x f x x f x f x f x x f x x x x x x x −−==−−类似地，构造不超过二次的多项式2001001201()()[,]()[,,]()().N x f x f x x x x f x x x x x x x =+−+−−容易检验，这样的2()N x 满足插值条件200211222()(),()(),()().N x f x N x f x N x f x ===因此，2()N x 就是二次Lagrange 插值多项式2()L x 。

二次插值的几何解释是，用通过三点00(,())x f x ，11(,())x f x ，22(,())x f x 的抛物线2()y N x =来近似所考察的曲线()y f x =，因此这类插值亦称为抛物线插值。

01,,n1,,n1,,)n x及数值分析各算法流程图一、插值1、 拉格朗日插值流程图：( 相应程序：lagrintp(x,y,xx))2,,n ,,j n 1,2,,n 1,,)n 2、 牛顿插值流程图(1)产生差商表的算法流程图(相应程序：divdiff(x,y))注：1、另一程序divdiff1(x,y)，输出的矩阵包含了节点向量。

而divdiff(x,y)不含节点向量。

2、另一程序tableofdd(x,y,m)，输出的是表格形式，添加了表头。

1,,),,n m 及1,,m (2)非等距节点的牛顿插值流程图(相应程序：newtint11(x,y,xx,m)) 、注：1、虽然程序newtint11(x,y,xx,m)考虑了多种情形，看上去很复杂，但基本流程结构还是如上图所示。

2、程序中调用的子程序是divdiff 。

若调用的子程序是divdiff1的话，流程图中的第三，第四，第五步要相应的改一下数字。

2,3,,1m +1,,j1,2,,n=1,2,,)n m 及(3)求差分表的流程图(相应程序：difference(y,m))注：1、difference 输出的是矩阵D 。

而另一程序tableofd(y,m)，输出的是带有表头的差分表。

n x m1,,),,1,,m注：1、程序newtforward1(x,y,xx,m))的结构与上述流程图一致，xx可以是数组。

2、另一程序newtforward(x,y,xx,m))先求出插值多项式，再求插值多项式在插值点的函数值。

基本结构还是和上面的流程图一样。

n x m1,,),,-x x1,,m注：1、程序newtbackward1(x,y,xx,m))的结构与上述流程图一致，xx可以是数组。

2、另一程序newtbackward(x,y,xx,m))先求出插值多项式，再求插值多项式在插值点的函数值。

基本结构还是和上面的流程图一样。

1,2,,n1,2,,n ,2,,)n x及3、Hermite 插值流程图(1) 已知条件中一阶导数的个数与插值节点的个数相等时的Hermite 插值流程图。

牛顿插值法插值法是利用函数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<stdio.h>void main(){float x[11],y[11][11],xx,temp,newton;int i,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<n+1;i++){ printf("x%d=",i);scanf("%f",&x[i]);printf("y%d=",i);scanf("%f",&y[0][i]);}for(i=1;i<n+1;i++)for(j=i;j<n+1;j++){ if(i>1)y[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-i]);elsey[i][j]=(y[i-1][j]-y[i-1][j-1])/(x[j]-x[j-1]);printf("%f\n",y[i][i]);}temp=1;newton=y[0][0];for(i=1;i<n+1;i++){ temp=temp*(xx-x[i-1]);newton=newton+y[i][i]*temp;}printf("求得的结果为:N(%.4f)=%9f\n",xx,newton);牛顿插值法Matlab程序function f = Newton(x,y,x0)syms t;if(length(x) == length(y))n = length(x);c(1:n) = 0.0;elsedisp(&apos;x和y的维数不相等！&apos;);return;endf = 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));endc(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,&apos;t&apos;,x0);elsef = collect(f); %将插值多项式展开f = vpa(f, 6);endend牛顿插值法摘要：值法利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。