3.3　插值与拟合的其他方法

Lagrange插值多项式结构对称，使用方便，但公式不具备递推性，当需要增加插值节点时，计算要全部重新进行。这时采用牛顿（Newton）插值公式具有一定的优势。

3.3.1　牛顿（Newton）插值

设在x0，x1，…，xn处，函数y=f（x）的取值分别为f（x0），f（x1），…，f（xn），设有

Nn（x0）=a0=f（x0）

Nn（x1）=a0+a1（x1-x0）=f（x1）

Nn（x2）=a0+a1（x2-x0）+a2（x2-x0）（x2-x1）=f（x2）

……

Nn（xn）=a0+a1（xn-x0）+…+an（xn-x0）（xn-x1）…（xn-xn-1）=f（xn）

这是关于未知数a0，a1，…，an的下三角形方程组，可以求得

a0=f（x0）

利用数学归纳法可以证明ak=f[x0，x1，…，xk]（k=1，2，…，n），则有

Nn（x）=f（x0）+f[x0，x1]（x-x0）+f[x0，x1，x2]（x-x0）（x-x1）+…+f[x0，x1，…，xn]（x-x0）（x-x1）…（x-xn-1）　　（3-11）

式（3-11）称为n次牛顿（Newton）插值公式。

【例3-4】利用牛顿插值法求解【例3-3】。

解：f[x0]=f（x）=5，，

根据差商的性质，

N2（x）=f（x0）+f[x0，x1]（x-x0）+f[x0，x1，x2]（x-x0）（x-x1）

=5+2（x-3）+（-1）（x-3）（x+1）=-x2+4x+2

3.3.2　曲线拟合的最小二乘法

最小二乘法应用广泛，其原理是建立某种误差的平方和，通过使误差平方和最小，求出问题的解。下面通过求解超定方程组，来说明最小二乘法的原理。

已知一超定方程组

2x1+4x2=1

3x1-5x2=3

x1+2x2=6

2x1+x2=7

用最小二乘法进行求解。

解：建立下面的误差方方程

Q=（2x1+4x2-1）2+（3x1-5x2-3）2+（x1+2x2-6）2+（x1+x2-7）2

通过将误差平方和Q对x1，x2求一阶导数，并令其为零，得到两个关于x1，x2的线性方程，通过求解该线性方程组，可得到超定方程的解。用Maple求解该问题，程序如下：

y1：=2x+4y-1；

y2：=3x-5y-3；

y3：=x+2y-6；

y4：=2x+y-7；

Q：=y12+y22+y32+y42；

x1：=diff（Q，x）；

x2：=diff（Q，y）

solve（{x1=0，x2=0}，[x，y]）

程序运行结果如下：

2x+4y-1

3x-5y-3

x+2y-6

2x+y-7

（2x+4y-1）2+（3x-5y-3）2+（x+2y-6）2+（2x+y-7）2

36x-6y-62

-6x+92y-16

最小二乘法数据拟合可叙述为，对于一组观测数据（xi，yi）（i=0，1，…，n），要求出自变量x与因变量y的函数关系y=p（x，a0，a1，…，am），其中ak（k=0，1，2，…，m）为待定参数，使给定点xi上的误差δi=f（xi）-yi的平方和最小，即

求一多项式　　p（x）=a0φ0（x）+a1φ1（x）+…+amφm（x），m<n　　（3-12）

为最小。这就是最小二乘逼近，得到的拟合曲线为 ，这种方法称为曲线拟合的最小二乘法。由极值必要条件，可得

根据带权值的内积定义，有

则式（3-14）可改写为

（φ0，φk）a0+（φ1，φk）a1+…+（φm，φk）am=（y，φk），k=0，1，…，m

这是关于参数a0，a1，…，am的线性方程组，用矩阵表示为

式（3-15）称为法方程。

记式（3-15）的解为，并代入式（3-12），从而得到最小二乘拟合曲线为