上式称为n次Lagrange插值多项式，由方程（3）解的唯一性，n?1个节点的n次Lagrange插值多项式存在唯一。
1.1.3 用Matlab作Lagrange插值
Matlab中没有现成的Lagrange插值函数，必须编写一个M文件实现Lagrange插值。
设n个节点数据以数组x0,y0输入（注意Matlat的数组下标从1开始），m个插值点以数组x输入，输出数组y为m个插值。编写一个名为lagrange.m的M文件： function y=lagrange(x0,y0,x); n=length(x0);m=length(x); for i=1:m z=x(i); s=0.0; for k=1:n p=1.0; for j=1:n if j~=k
p=p*(z-x0(j))/(x0(k)-x0(j)); end end
s=p*y0(k)+s; end
y(i)=s; end
1.2 牛顿（Newton）插值
在导出Newton公式前，先介绍公式表示中所需要用到的差商、差分的概念及性质。
1.2.1 差商
定义 设有函数f(x),x0,x1,x2,?为一系列互不相等的点，称
f(xi)?f(xj)xi?xj即
(i?j)为f(x)关于点xi,xj一阶差商（也称均差）记为f[xi,xj]，
f[xi,xj]?f(xi)?f(xj)xi?xj
称一阶差商的差商
f[xi,xj]?f[xj,xk]xi?xk为f(x)关于点xi,xj,xk的二阶差商，记为f[xi,xj,xk]。一般地，称 f[x0,x1,?,xk?1]?f[x1,x2,?,xk]
x0?xk为f(x)关于点x0,x1,?,xk的k阶差商，记为
f[x0,x1,?,xk?1]?f[x1,x2,?,xk]f[x0,x1,?,xk]?
x0?xk容易证明，差商具有下述性质： f[xi,xj]?f[xj,xi]
f[xi,xj,xk]?f[xi,xk,xj]?f[xj,xi,xk]
1.2.2 Newton插值公式 线性插值公式可表成
?1(x)?f(x0)?(x?x0)f[x0,x1]
称为一次Newton插值多项式。一般地，由各阶差商的定义，依次可得
f(x)?f(x0)?(x?x0)f[x,x0]
f[x,x0]?f[x0,x1]?(x?x1)f[x,x0,x1]
f[x,x0,x1]?f[x0,x1,x2]?(x?x2)f[x,x0,x1,x2]
??
f[x,x0,?,xn?1]?f[x0,x1,?,xn]?(x?xn)f[x,x0,?,xn]
将以上各式分别乘以1,(x?x0),(x?x0)(x?x1),?,(x?x0)(x?x1)?(x?xn?1)，然后相加并消去两边相等的部分，即得
f(x)?f(x0)?(x?x0)f[x0,x1]?? ?(x?x0)(x?x1)?(x?xn?1)f[x0,x1,?,xn] ?(x?x0)(x?x1)?(x?xn)f[x,x0,x1,?,xn]记
Nn(x)?f(x0)?(x?x0)f[x0,x1]?? ?(x?x0)(x?x1)?(x?xn?1)f[x0,x1,?,xn]Rn(x)?(x?x0)(x?x1)?(x?xn)f[x,x0,x1,?,xn]
??n?1(x)f[x,x0,x1,?,xn]显然，Nn(x)是至多n次的多项式，且满足插值条件，因而它是f(x)的n次插值多项式。这种形式的插值多项式称为Newton插值多项式。Rn(x)称为Newton插值
余项。
Newton插值的优点是：每增加一个节点，插值多项式只增加一项，即
Nn?1(x)?Nn(x)?(x?x0)?(x?xn)f[x0,x1,?,xn?1]
因而便于递推运算。而且Newton插值的计算量小于Lagrange插值。
由插值多项式的唯一性可知，Newton插值余项与Lagrange余项也是相等的，即
Rn(x)??n?1(x)f[x,x0,x1,?,xn]f(n?1)(?)??n?1(x)(n?1)!由此可得差商与导数的关系
??(a,b)
f(n)(?)f[x0,x1,?,xn]?
n!其中??(?,?),??min{xi},??max{xi}。
0?i?n0?i?n1.2.3 差分
当节点等距时，即相邻两个节点之差（称为步长）为常数，Newton插值公式的形式会更简单。此时关于节点间函数的平均变化率（差商）可用函数值之差（差分）来表示。
定义 设有等距节点xk?x0?kh(k?0,1,?,n)，步长h为常数，fk?f(xk)。称相邻两个节点xk,xk?1处的函数值的增量fk?1?fk(k?0,1,?,n?1)为函数f(x)在点xk处以h为步长的一阶差分，记为?fk，即
?fk?fk?1?fk(k?0,1,?,n)
(k?0,1,?,n?2)
类似地，定义差分的差分为高阶差分。如二阶差分为
?2fk??fk?1??fk一般地，m阶差分为 ?mfk??m?1fk?1??m?1fk(k?2,3,?)，
上面定义的各阶差分又称为向前差分。常用的差分还有两种： ?fk?fk?fk?1
称为f(x)在xk处以h为步长的向后差分；
h?h???2?2???称为f(x)在xk处以h为步长的中心差分。一般地，m阶向后差分与m阶中心差分公
?fk?f?xk???f?xk??
式为
?mfk??m?1fk??m?1fk?1
?mfk??m?1f1k?2??m?1fk?12
差分具有以下性质：
（i）各阶差分均可表成函数值的线性组合，例如
?m??fk??(?1)j??j?? fk?m?j
j?0??m?m?m?fk??(?1)j??j?? fk?j
j?0??mm（ii）各种差分之间可以互化。向后差分与中心差分化成向前差分的公式如下：
?mfk??mfk?m
?mfk??mfm?m2
1.2.4 等距节点插值公式
如果插值节点是等距的，则插值公式可用差分表示。设已知节点xk?x0?kh(k?0,1,2,?,n)，则有
Nn(x)?f(x0)?f[x0,x1](x?x0)???f[x0,x1,?,xn](x?x0)(x?x1)?(x?xn?1)
?f0?nf0 ?f0?(x?x0)???(x?x0)(x?x1)?(x?xn?1)nhn!h若令x?x0?th，则上式又可变形为
t(t?1)?(t?n?1)nNn(x0?th)?f0?t?f0????f0
n!上式称为Newton向前插值公式。
1.3 分段线性插值
1.3.1 插值多项式的振荡
用Lagrange插值多项式Ln(x)近似f(x)(a?x?b)，虽然随着节点个数的增加，
Ln(x)的次数n变大，多数情况下误差|Rn(x)|会变小。但是n增大时，Ln(x)的光
滑性变坏，有时会出现很大的振荡。理论上，当n??，在[a,b]内并不能保证Ln(x)处处收敛于f(x)。Runge给出了一个有名的例子：
1,x?[?5,5] 1?x2对于较大的|x|，随着n的增大，Ln(x)振荡越来越大，事实上可以证明，仅当|x|?3.63时，才有limLn(x)?f(x)，而在此区间外，Ln(x)是发散的。
f(x)?n??高次插值多项式的这些缺陷，促使人们转而寻求简单的低次多项式插值。 1.3.2 分段线性插值
简单地说，将每两个相邻的节点用直线连起来，如此形成的一条折线就是分段线性插值函数，记作In(x)，它满足In(xi)?yi，且In(x)在每个小区间[xi,xi?1]上是线性函数(i?0,1,?,n)。
In(x)可以表示为
In(x)??yili(x)
i?0n?x?xi?1?x?x, x?[xi?1,xi] (i?0时舍去）i?1?i?x?xi?1li(x)??， x?[xi,xi?1] （i?n时舍去）
?xi?xi?1?0， 其它??In(x)有良好的收敛性，即对于x?[a,b]有，
n??limIn(x)?f(x)。
用In(x)计算x点的插值时，只用到x左右的两个节点，计算量与节点个数n无关。但n越大，分段越多，插值误差越小。实际上用函数表作插值计算时，分段线性