插值与拟合简介

---

1.插值方法

1.1 拉格朗日（Lagrange）多项式插值

  最基本，求一个至多n次多项式 φn(x)=a0+a1x+...+anxn​ ，使其在给定点处与f(x)同值，即满足插值条件 φn(xi)=f(xi)=yi(i=0,1,…,n)​ 。

  Lagrange插值公式如下：

Ln(x)=∑i=0nyi(∏j=0 j≠qinx−xjxi−xj)

1.2 牛顿（Newton）插值

  先介绍差商的概念：

一阶差商： f[xi,xj]=f(xi)−f(xj)xi−xj 二阶差商： f[xi,xj,xk]=f[xi,xj]−f[xj,xk]xi−xk k阶差商： f[x0,x1,…,xk]=f[x0,x1,…,xk−1]−f[x1,x2,…,xk]x0−xk

  那么，Newton插值公式如下：

Nn(x)=f(x0)+(x−x0)f[x0,x1]+...+(x−x0)(x−x1)..(x−xn−1)f[x0,x1,...,xn]   Newton插值的优点是 ：每增加一个节点，插值多项式只增加一项，即 Nn+1(x)=Nn(x)+(x−x0)...(x−xn)f[x0,x1,...,xn+1]   因而便于递推运算。而且Newton插值的计算量小于Lagrange插值。

  如果样本点的x之间是等距的，那么插值公式可用差分表示，这里不做介绍了。

1.3分段线性插值

  使用Lagrange插值法虽然随着节点个数的增加，Ln（x）的次数n变大，多数情况误差会变小。但是n增大时，Ln（x）的光滑性变坏，有时会出现很大的振荡。由于高次插值多项式的这些缺陷，促使人们转而寻求简单的低次多项式插值。

  分段线性插值，简单地说，就是将每两个相邻的节点用直线连起来，如此形成的一条折线就是分段线性插值函数。其可以表示为：

In(x)=∑i=0nyili(x)li(x)=⎧⎩⎨⎪⎪⎪⎪x−xi−1xi−xi−1,x∈[xi−1,xi](i=0时舍去)x−xi+1xi−xi+1,x∈[xi,xi+1](i=n时舍去)0,其它   分段线性插值具有良好的收敛性。当n越大时，分段越多，插值误差越小。

1.4埃尔米特(Hermite)插值

  如果对于插值函数，不仅要求它在节点处与函数同值，而且要求它与函数有相同的一阶、二阶甚至更高阶的导数值，这就是Hermite插值问题。这里我们讨论一阶导数值相等的情况，需要题目多给定各点的一阶导数值列表 y′

H(x)=∑i=0nhi[(xi−x)(2aiyi−y′i)+yi]其中hi=∏j=0,j≠in(x−xjxi−xj)2,ai=∑j=0,j≠in1xi−xj

1.5样条（Spline）插值

  许多工程技术中提出的计算问题对插值函数的光滑性有较高的要求，如飞机的机翼外形，内燃机的进、排气门的凸轮曲线，都要求曲线具有较高的光滑程度，不仅要连续，而且要有连续的曲率，这就导致了样条插值的产生。

  数学上将具有一定光滑性的分段多项式称为样条函数。具体说，对于给定区间[a,b]，和小区间[x0,x1],[x1,x2]….[xn-1,xn]，如果函数s(x)满足：（1）在每个小区间[xi,xi+1]上s(x)是k次多项式；（2）s(x)在[a,b]上具有k-1阶连续导数。 则称s(x)为k次样条函数，其图形称为k次样条曲线。

  在实际中最常用的是k=2和k=3的情况，即为二次样条函数和三次样条函数。

1.6B样条函数插值法

  实际的许多问题中，往往是既要求近似函数（曲线或曲面）有足够的光滑性，又要求与实际函数有相同的凹凸性，一般插值函数和样条函数都不具有这种性质。如果对一个特殊函数进行磨光处理生成磨光函数（多项式），则用磨光函数构造出样条函数作为插值函数，既有足够的光滑性，而且也具有较好的保凹凸性，因此磨光函数在一维插值（曲线）和二维插值（曲面）问题中有着广泛的应用。而B样条函数插值就是使用磨光函数的插值法。

1.7二维插值

  前面讲述的都是一维插值。若节点是二维的，插值函数就是二元函数，即曲面。二维插值常常运用于测绘区域，绘制等高线图等问题中。

2.拟合方法

  与插值问题不同，在拟合问题中不需要曲线一定经过给定的点。拟合问题的目标是寻求一个函数（曲线），使得该曲线在某种准则下与所有的数据点最为接近，即曲线拟合的最好（最小化损失函数）。

  曲线拟合的方法有很多，例如：

最小二乘法

局部加权回归

牛顿法

等等。。。 后面就涉及机器学习的部分了，不在此过多介绍。

3.最小二乘优化

  在无约束最优化问题中，有些重要的特殊情形，比如目标函数由若干个函数的平方和构成。这类函数一般可以写成：

F(x)=∑i=1mf2i(x),x∈Rn   其中 x=(x1,…,xn)T ，一般假设m>=n。我们把极小化这类函数的问题： minF(x)=∑i=1mf2i(x) 称为最小二乘优化问题。 在处理这类问题时，Matlab也提供了一些强大的函数，比如：lsqlin、lsqcurvefit、lsqnonlin、lsqnonneg，用法在这里不做具体介绍。

4.函数逼近

  曲线逼近是指，如果已知一个较为复杂的连续函数 y(x),x∈[a,b] ，要求选择一个比较简单的函数f(x)，在一定准则下最接近f(x)，就是所谓的函数逼近。

  函数逼近最简单的是使用多项式逼近函数，常用的多项式有勒让德（Legendre）多项式，第一类切比雪夫（Chebyshev）多项式，拉盖尔（Laguerre）多项式等等。