Ch2(2)牛顿插值法

牛顿插值法例题求解【原创版】目录1.牛顿插值法简介2.牛顿插值法的基本原理3.牛顿插值法的例题解析4.牛顿插值法的优缺点5.总结正文一、牛顿插值法简介牛顿插值法是一种常用的数学插值方法，主要用于根据已知的函数值预测未知函数值。

牛顿插值法的基本原理是通过求解各阶差分来逼近未知函数值。

这种方法在增加插值节点时具有较好的计算稳定性，因此在实际应用中具有较高的价值。

二、牛顿插值法的基本原理牛顿插值法的基本思想是利用差商的概念，将函数在某区间中若干点的函数值用适当的特定函数表示。

通过求解各阶差分，可以得到这个特定函数的系数，从而得到插值多项式。

在给定的插值节点上，这个插值多项式可以取到已知的函数值，而在其他点上，则可以用这个多项式作为函数的近似值。

具体来说，牛顿插值法的求解过程分为以下几个步骤：1.设定插值多项式的形式，例如拉格朗日插值多项式、牛顿插值多项式等。

2.根据已知的函数值和插值节点，求解插值多项式的系数。

3.将求解得到的系数代入插值多项式，得到插值函数。

4.在给定的插值节点上，求解插值函数的值，作为预测的未知函数值。

三、牛顿插值法的例题解析假设我们有三个样本点：（1，-2），（2，-1），（3，2），我们希望通过这三个点求解一个二次函数。

我们可以用牛顿插值法来解决这个问题。

首先，我们设定插值多项式的形式为 y = ax^2 + bx + c。

然后，将三个样本点带入该方程，得到以下三个方程：- -2 = a(1)^2 + b(1) + c- -1 = a(2)^2 + b(2) + c- 2 = a(3)^2 + b(3) + c解这个方程组，我们可以得到 a = 1/2，b = 5/2，c = -3/2。

因此，我们得到插值函数为 y = 1/2x^2 + 5/2x - 3/2。

将x=1, 2, 3 代入该函数，我们可以得到 y=-2, -1, 2，与给定的样本点相符，说明我们的插值结果是正确的。

牛顿插值法插值法是利用函数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)的近似值。

牛顿插值法的原理和推导过程一、引言在科学计算和数值分析中，插值法是一种重要的数学工具，它可以通过已知的离散数据点来估计未知点的值。

在众多插值法中，牛顿插值法以其形式简洁、计算方便而广受欢迎。

本文将对牛顿插值法的原理和推导过程进行详细阐述。

二、牛顿插值法的基本原理牛顿插值法是一种多项式插值方法，它的基本思想是通过构造一个n次多项式Pn(x)，使得该多项式在给定的n+1个插值节点上与被插值函数f(x)具有相同的函数值。

这样，在插值节点之间，我们可以用Pn(x)来近似代替f(x)。

三、牛顿插值法的推导过程差商与差分为了构造插值多项式，首先需要引入差商的概念。

设f[xi,xj]表示函数f(x)在点xi 和xj上的一阶差商，其计算公式为：f[xi,xj] = (f(xj) - f(xi)) / (xj - xi)类似地，可以定义二阶、三阶乃至n阶差商。

n阶差商f[x0,x1,...,xn]表示函数f(x)在点x0,x1,...,xn上的差商，可以通过低一阶的差商递归计算得到。

差分是差商的另一种表现形式，它与差商之间有一一对应的关系。

在实际计算中，差分往往比差商更方便。

牛顿插值多项式的构造有了差商的概念，我们就可以构造牛顿插值多项式了。

设n次牛顿插值多项式为：Pn(x) = f(x0) + fx0,x1 + fx0,x1,x2(x-x1) + ... + fx0,x1,...,xn(x-x1)...(x-xn-1)其中，f[x0,x1,...,xk]表示k阶差商。

可以看出，Pn(x)是一个形式简洁的多项式，其各项系数即为各阶差商。

为了证明Pn(x)满足插值条件，即Pn(xi) = f(xi) (i=0,1,...,n)，我们可以将xi代入Pn(x)中，逐项验证。

由于差商的性质，当x取xi时，高于i阶的差商项都将为0，因此Pn(xi) = f(xi)。

牛顿插值法的计算步骤（1）根据给定的插值节点，计算各阶差商；（2）根据牛顿插值多项式的公式，构造插值多项式Pn(x)；（3）将需要插值的点代入Pn(x)，得到插值结果。

Ch2. 插值法§1. 插值问题引例 矿井中某处的瓦斯浓度y 与该处距地面的距离x 有关，现用仪器测得从地面到井下500米每隔50米的瓦斯浓度数据(,)(0,1,2,,10)= i i x y i ，根据这些数据完成下列工作：(1)寻找一个函数，要求从此函数中可近似求得从地面到井下500米之间任意一点处的瓦斯浓度；(2)估计井下600米处的瓦斯浓度。

第一个问题可归结为“已知函数在n x x x ,,,10⋅⋅⋅处的值，求函数在区间[]n x x ,0内其它点处的值”，这种问题适宜用插值方法解决。

但对第二个问题不宜用插值方法，因为600米已超出所给数据范围，用插值函数外推插值区间外的数据会产生较大的误差。

解决第二个问题的常用方法是，根据地面到井下500处的数据求出瓦斯浓度与地面到井下距离之间的函数关系)(x f ，由)(x f 求井下600米处的瓦斯浓度。

定义 设)(x f y =在[]b a ,中1+n 个点n x x x <⋅⋅⋅<<10处的值)(i i x f y =为已知，现根据上述数据构造一个简单函数)(x p ，使i i y x p =)(，这种问题称为插值问题。

i x x p x f ),(),(,i i y x p =)(分别称为被插值函数、插值函数、插值节点和插值条件。

若)(x p 为多项式，则此问题称为多项式插值或代数插值。

定理1 在插值节点n x x x ,,,10⋅⋅⋅处，取给定值n y y y ,,,10⋅⋅⋅，且次数不高于n 的插值多项式是存在且唯一的。

证 令n n x a x a a x p +⋅⋅⋅++=10)(，则根据插值条件i i y x p =)(有下列等式：⎪⎪⎩⎪⎪⎨⎧=+⋅⋅⋅++=⋅⋅⋅⋅⋅⋅=+⋅⋅⋅++==+⋅⋅⋅++=n n n n n n nn nn yx a x a a x p y x a x a a x p y x a x a a x p 10111101000100)()()( （关于i a 的1+n 阶线性方程组）， 其系数行列式是范德蒙（V andermonde ）行列式()011111100≠-=⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=∏≥>≥j i n j innnnn x xx x x x x x D 。

牛顿差值法牛顿差值法（Newton’s Difference Method）是一种在数值分析中广泛应用的二次多项式拟合方法和根求解方法。

该方法引入了多项式中的牛顿多项式（Newton Polynomial）。

牛顿多项式将一组数据的多项式拟合能力极大地提升，从而使得求解方程的精度和速度都更加有效。

牛顿差值法又称为牛顿插值法，最早可以追溯到17世纪法国数学家叶塞立雅（Isaac Newton）提出的，叶塞立雅是一位非常伟大的数学家，他发明了多种重要的数学方法，而牛顿差值法是他的最重要的发现之一。

牛顿的思想是从一组已知的点的函数值拟合出一个多项式，其中的每个点都被精确的表示。

牛顿差值法是一种称为牛顿形式的特殊牛顿多项式的拟合方法，这种多项式简单并产生了一系列的非线性多项式公式，它将一组数据的拟合能力极大地提升，从而求解方程的精度和速度都更加有效。

牛顿差值法通常是基于插值函数的形式。

基于此函数形式，其计算（或估计）插值点的值时，都是使用已知的点的函数值的线性组合。

如一次多项式的形式为p_0+p_1x+p_2x^2，则给定点(x_0,f(x_0))...(x_n,f(x_n))，组合函数值f(x)即为f(x)= a_0 f (x_0)+a_1 f (x_1)...+a_n f (x_n).牛顿差值法中，系数a_0,a_1...a_n是拟合多项式系数，可以通过求解方程组来求解。

需要注意的是，牛顿差值法更能反映函数在点之间变化，它同样可用于插补曲线，主要用于拟合数据点，求解方程，以及求解极值点，等等。

由于牛顿多项式的拟合能力较强，牛顿差值法的估计和求解过程都比较精确，在实际应用中拥有良好的精度与准确性。

它常常被用于求解和拟合数据，尤其是函数的拟合，是一种经常应用的方法之一。

拉格朗日插值法牛顿插值法
摘要：
1.插值法的概念和作用
2.拉格朗日插值法原理和应用
3.牛顿插值法原理和应用
4.两种插值法的优缺点比较
正文：
一、插值法的概念和作用
插值法是一种数学方法，通过已知的数据点来预测未知数据点的一种技术。

在科学计算和工程应用中，常常需要根据有限个已知数据点，来估计某个函数在其他点上的值。

插值法正是为了解决这个问题而诞生的。

二、拉格朗日插值法原理和应用
拉格朗日插值法是一种基于拉格朗日基函数的插值方法。

它的基本原理是：在给定的区间[a, b] 上，选取一个基函数，然后通过求解一组线性方程，得到基函数在各数据点上的值，最后用这些值来近似函数在待求点上的值。

拉格朗日插值法广泛应用于数值分析、工程计算等领域。

三、牛顿插值法原理和应用
牛顿插值法，又称为牛顿前向差分法，是一种基于差分的插值方法。

它的基本原理是：通过对已知数据点的函数值进行差分，然后使用牛顿迭代公式来求解差分后的函数在待求点上的值。

牛顿插值法具有较高的精度，适用于各种函数，特别是对于单调函数和多项式函数，效果尤为显著。

四、两种插值法的优缺点比较
拉格朗日插值法和牛顿插值法各有优缺点。

拉格朗日插值法的优点是适用范围广，可以插值任意类型的函数，但计算过程较为复杂；牛顿插值法的优点是计算简便，精度高，但对于非线性函数或多峰函数，效果可能不佳。

因此，在实际应用中，需要根据具体情况选择合适的插值方法。

牛顿向前插值公式牛顿向前插值公式是数值分析中一个挺有意思的工具。

咱先来说说啥是牛顿向前插值公式哈。

简单来讲，它就是一种通过已知的一些数据点，来推测中间或者其他未知点数值的方法。

比如说，咱们知道了几个不同时间点的气温，就可以用这个公式猜猜其他时间的气温大概是多少。

我记得之前有一次带学生们做实验，就是用这个公式来估算物体下落的位置。

当时给了他们几个不同时刻物体下落的高度数据，让他们用牛顿向前插值公式去算某个特定时刻物体大概在什么位置。

这可把孩子们难坏了，一个个抓耳挠腮的。

有的孩子直接被那些复杂的算式给弄晕了，一会儿忘了这个系数，一会儿又算错了那个差值。

但是也有几个聪明的小家伙，慢慢地理清了思路，一步一步地算出来了。

其实牛顿向前插值公式的原理也不太难理解。

它是通过构建一系列的差商，然后把这些差商组合起来形成一个多项式。

这个多项式就能够近似地表示数据之间的关系。

比如说，咱们有一组数据点 (x₀, y₀), (x₁, y₁), (x₂, y₂) ...... 先算出一阶差商，就是 (y₁ - y₀) / (x₁ - x₀) ；然后再算二阶差商，依此类推。

在实际应用中，牛顿向前插值公式可有用啦。

像在金融领域，预测股票价格的走势；在工程中，估计某个零件在不同条件下的性能；在科学研究里，推测实验数据的变化趋势等等。

不过，用这个公式的时候可得小心，数据点的选取很关键。

如果数据本身就不太规律，或者误差比较大，那算出来的结果可能就不太准了。

就像那次实验，有的小组因为数据测量的时候不够精确，导致最后用公式算出来的结果和实际情况相差挺多。

学习牛顿向前插值公式，不能光是死记硬背那些公式和步骤，得真正理解它背后的思想。

多做几道题，多动手算一算，才能真正掌握。

总之，牛顿向前插值公式虽然有点小复杂，但掌握好了，那可是解决很多实际问题的一把好手。

希望同学们在学习的过程中，不要被它吓住，多琢磨琢磨，一定能搞明白的！。

牛顿插值算法流程下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。

文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor. I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!牛顿插值算法的流程大致如下1. **准备数据**：收集已知点的坐标和函数值。

牛顿插值公式
牛顿插值公式是一种用于近似拟合多元函数或曲线的数学工具，它也是数值分析中常用的技术之一。

提出者是英国科学家牛顿，用于17世纪插补曲线的插值数学表达式，是最早的插值法之一。

其基本
原理是在所有已知点之间拟合出一个梯形多项式，以获得更多未知点的函数值。

牛顿插值公式的核心是一种构造插值多项式的定理，即牛顿第二种插值定理，它表明，如果有n+1个已知点，当插入的连续函数的阶数不大于n时，这n+1个点可以用n阶多项式，经由特定的条件构造出来。

根据牛顿插值公式，按照特定的条件，可以构造出一个连续函数的插值多项式，这个插值多项式可以用来拟合多元函数或曲线，此方法的优点是可以计算出比原函数更多的未知点的函数值。

牛顿插值公式的实现方法有两种：一种是正向实现，一种是反向实现。

正向实现方法，即先利用牛顿插值公式计算出插值多项式的系数，然后根据插值多项式给定的指定点获得这些点的函数值。

反向实现方法，即先使用牛顿插值公式计算出已知点的函数值，然后根据已知点的函数值求出插值多项式的系数。

牛顿插值公式具有许多优点，它可以计算出比原函数更多的未知点的函数值，这样拟合的曲线比较平滑，准确性更高。

同时，牛顿插值公式的实现过程只需要进行几次矩阵的乘法及加法，算法的效率比
较高。

因此，牛顿插值公式在实际中得到了广泛的应用。

它可以用来拟合未知点的函数值、实验结果的拟合、做算法的实型仿真等等，是数值分析中不可多得的重要工具。

总之，牛顿插值公式不仅可以满足多元函数或曲线的近似拟合，而且它的实现过程也比较简单，容易理解，效率也比较高，所以得到了广泛的应用。

牛顿差值法的原理及应用1. 牛顿差值法的原理牛顿差值法（Newton’s Divided-Difference Interpolation）是一种用于数据插值的数值方法，它是由英国科学家牛顿（Isaac Newton）在17世纪提出的。

牛顿差值法的原理基于以下两个关键思想： 1. 任意n个数据点可以通过一个n-1次多项式来精确插值。

2. 使用差商（divided differences）的概念，可以通过递推公式迭代计算差商及插值多项式的系数。

具体而言，牛顿差值法将数据点(x i,y i)表示为自变量的函数y=f(x)中的零次差商f[x i]，一次差商f[x i,x i+1]等等。

插值多项式的形式如下：$$P(x) = f[x_0] + (x-x_0)f[x_0,x_1] + (x-x_0)(x-x_1)f[x_0,x_1,x_2] + \\ldots$$其中$f[x_0,x_1,\\ldots,x_n]$表示n阶差商。

通过递推公式计算差商，可以得到插值多项式。

2. 牛顿差值法的应用牛顿差值法在科学计算和工程领域有着广泛的应用。

下面列举了几个常见的应用场景：2.1 数据插值牛顿差值法最常见的应用就是对已知数据点进行插值，以估计在数据点之间的未知位置上的函数值。

通过插值多项式可以方便地计算未知位置的函数值，从而填补数据的缺失部分。

2.2 数值积分牛顿差值法在数值积分中也有出色表现。

通过构造插值多项式，可以近似计算函数在一段区间上的积分值。

这在实际问题中经常出现，特别是当无法解析求解积分时，牛顿差值法提供了一种有效的数值积分方法。

2.3 信号处理在信号处理中，牛顿差值法可以用于信号重构和信号平滑。

通过已知的零次差商和一次差商来恢复原始信号，并进行信号降噪和平滑处理。

这在图像处理和音频处理等领域中非常有用。

2.4 绘图插值对于绘制曲线的问题，牛顿差值法可以通过已知数据点插值计算出曲线上的其他点，从而绘制平滑的曲线。

牛顿插值法(算法)Newton Interpolation牛顿插值算法是根据n + 1个点x0, x1, ... x n(x0 < x1 < ... x n)与函数値f(x0), f(x1) , ... , f(x n)求出n次多項式p(x)。

再通过次多項式p(x)求出任意的点x所对应的f(x)的算法。

１．求n阶差分商f[x0, x1, ... x n]。

使用递归调用。

#define N 20typedef struct TagXYVALUE{double x;double y;} XYVALUE;XYVALUE val[N+1];//階差分商(Divided Differences)double f(int n0, int ni){if (n0 == ni)return val[n0].y;if (n0 + 1== ni)return (val[ni].y - val[n0].y) / (val[ni].x - val[n0].x);elsereturn (f(n0+1, ni) - f(n0, ni-1)) / (val[ni].x - val[n0].x);}２．牛顿插值算法的主程序，求p(x)的程序。

ndouble NewtonInterpolation(double x){double t = 1.0;double ft;double p = val[0].y; //P(0) = f[0]for(int i = 1; i <= N; i++){t = t * (x - val[i-1].x);ft = f(0, i) * t;p = p + ft;}return p;}３．测试。

用正弦波的20个采样点，还原出正弦波曲线。

计算速度很慢，需要改进程序。

void CNewtonInterpolationTestView::OnDraw(CDC* pDC){for (int i = 0; i <= N; i ++){val[i].x = i * 15 * atan(1.0) / 45.0 * 2;val[i].y = sin(val[i].x);pDC->Rectangle((int)(val[i].x*20)- 2, 150-(int)(val[i].y*50)- 2,(int)(val[i].x*20)+2,150-(int)(val[i].y*50)+2);}for (int j = 0; j <= N*15; j += 5){double x = j * atan(1.0) / 45.0 * 2;double y = NewtonInterpolation(x);pDC->SetPixel((int)(x*20)-2, 150-(int)(y*50)-2, 0x000000ff);}}４．n阶差分商的计算方法的改善。

牛顿插值法摘要：值法利用函数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)关键词：牛顿插值法流程图程序实现一、插值法的由来在许多实际问题及科学研究中，因素之间往往存在着函数关系，然而，这种关系经常很难有明显的解析表达，通常只是由观察与测试得到一些离散数值。

有时，即使给出了解析表达式，却由于表达式过于复杂，不仅使用不便，而且不易于进行计算与理论分析。

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

插值法是一种古老的数学方法，它来自生产实践，早在一千多年前，我国科学家在研究历法上就应用了线性插值与二次插值，但它的基本理论却是在微积分产生之后才逐渐完善的，其应用也日益增多，特别是在计算机软件中，许多库函数，如等的计算实际上归结于它的逼近函数的计算。

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

在工程实际问题当中，我们也经常会碰到诸如此类的函数值计算问题。

被计算的函数有时不容易直接计算，如表达式过于复杂或者只能通过某种手段获取该函数在某些点处的函数值信息或者导数值信息等。

因此，我们希望能用一个“简单函数”逼近被计算函数，然后用该简单函数的函数值近似替代被计算函数的函数值。

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

逐次线性插值法优点是能够最有效地计算任何给定点的函数值，而不需要写出各步用到的插值多项式的表达式。

牛顿插值法(1)牛顿真是牛，拉格朗日插值法只能算是数学意义上的插值，从插值基函数的巧妙选取，已经构造性的证明了插值法的存在性和惟一性，但是从实现的角度看并不很好，而牛顿很好的解决了这个问题。

牛顿插值是基于下面这些的公式：f[x0,x1,...xk]=(f[x1,...xk]-f[x0,...xk-1])/(xk-x0)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)前两个是均差的递推关系式，而后一个就是牛顿插值公式，其中N(x)=f(x)-Rn(x)，即目标多项式，Rn(x)是n阶插值余项，我们就是用N(x)去近似f(x)。

可以构造这样一个均方差表：xk f(xk) 一阶均差二阶均差 ...x0 f(x0)x1 f(x1) f[x0,x1]x2 f(x2) f[x1,x2] f[x0,x1,x2]...如果有n个点插值，表会有(n*n)/2+n个表项，如果直接编程会有O(n*n)的空间复杂度，编程时做个简单的改进，不难发现在这个表中只有部分数据有用，对角线（斜行）它们是目标值，用来表示多项式的，左边的两纵行（实际上只需要x一行）以及最底下的一行，表示当前插值的状态。

经过改进后只需要O(n)的空间复杂度。

两个过程：1，新增加一个点时的更新。

只须更新最底下一行数据，其递推关系由均差公式给出，最后算出高一队的均差值，需时O(n)2，插入点完成后如何计算多项式在另外给定点的值N(x)。

由牛顿插值公式，最终的表达式为：N(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0)...(x-xn-1)如果直接将它展开，再算实在麻烦，实际上大可不必这样做，还记得多项式求值的秦九韶算法吗？将多项式‘叠’起来，从内层括号往外一层层拨开，n次多项多的计算，只需要做n次乘法，同样的思想，将上式改写成：N(x)=f[x0]+(x-x0){f[x0,x1]+(x-x1){f[x0,x1,x2]+(x-x2){...{f[x0,...xn-1]+(x-xn-1)f[x0, (x)n]}...}就可以同样简单的计算了，时间复杂度O(n)综合起来的性能：对于n个点的插值，产生多项式的时间复杂度是O(n*n)，最终进行一个点的计算的时间复杂度是O(n)。