插值算法的介绍及其在数学建模中的应用

%本文根据清风数学建模课程插值算法及相关资料总结而成，仅供学习使用
%本文参考了（分段插值 - 百度文库），对介绍的顺序及内容进行了改进
%由于本文仅仅是简要介绍插值算法在建模中的应用，因此样条插值的可微性证明等各种复杂繁琐的部分在本文中不再引入
%本文仅介绍一维数据的插值，多维数据的插值方法与一维插值类似

一、插值的介绍及其作用

数模比赛中，常常需要根据已知的样本点进行数据的处理和分析，而有时候现有数据较少或数据不全，不足以支撑分析的进行，这时就需要使用插值法“模拟产生”一些新的但又比较靠谱的值来满足需求，这就是插值的作用。

%在直观上，插值就是找到一个连续函数使其经过每个样本点
%插值法还可用于短期的预测问题

（插值与拟合经常会被弄混，为了区分，这里简要介绍一下拟合：即找到一个函数，使得该函数在最小二乘的意义下与已知样本点的总体差别最小，该函数不一定要经过样本点。通常情况下，拟合要求已知样本点的数据较多，当数据较少时不适用）

二、插值法原理

三、插值法的分类

%注：下面的1、2、3、4 并非是并列关系，几个部分之间也有交叉，目的在于逐渐引出数学建模中最常用的两种插值方法：三次样条插值与三次埃尔米特插值。

1、普通多项式插值

多项式插值中，拉格朗日插值与牛顿插值是经典的插值方法，但它们存在明显的龙格现象（下面会解释龙格现象），且不能全面反映插值函数的特性（仅仅保证了插值多项式在插值节点处与被插函数有相等的函数值）。

然而在许多实际问题中，不仅要求插值函数与被插值函数在所有节点处有相同的函数值，它也需要在一个或全部节点上插值多项式与被插函数有相同的低阶甚至高阶的导数值。对于这些情况，拉格朗日插值和牛顿插值都不能满足。因此，数学建模中一般不使用这两种方法进行插值，这里也不再介绍这两种方法。

龙格现象（Runge phenomenon）: 1901年，Carl Runge 在他的关于高次多项式插值风险的研究中，发现高次插值函数可能会在两端处波动极大，产生明显的震荡，这种现象因此被称为龙格现象。所以在不熟悉曲线运动趋势的前提下，我们一般不轻易使用高次插值。

下面是对函数f(x)=\cfrac{1}{1+x^2}不同次数拉格朗日插值多项式的比较图，其中红线为函数本身图像。可以发现，n值越大，在两端的波动越大。

2、分段低次插值

为了解决高次多项式插值的龙格现象和提高精度（特别是样本点较多时），可以采用分段低次多项式插值，即：将大区间分为多个子区间，在每一个子区间上进行低次多项式插值，这种分段进行插值的思想在接下来也会派上用场。

虽然分段一次插值和二次插值在节点处连续，但在节点左右两侧的导数不一定相等，因此会出现尖点，不能满足许多情况下对函数光滑性的需要（比如船体、飞机等外形曲线设计的需要），接下来引入样条插值。

3、（三次）样条插值

为了满足对函数光滑性的需要，我们可以使用一种有弹性的长条（称之为样条），强迫它弯曲通过样本点。

弹性力学理论指出，样条的挠度曲线具有连续的二阶导数，并且在相邻定点之间为三次多项式，即为数学上的三次样条插值曲线。

三次样条插值的Matlab实现：（实现过程已经封装，会调用即可）

Matlab有内置的函数： p = spline (x,y, new_x)
其中，x是已知的样本点的横坐标；y是已知的样本点的纵坐标；new_x是要插入处对应的横坐标（下面三次埃尔米特插值函数参数意义与此相同）

4、分段三次埃尔米特（Hermite）插值

%虽然Hermite插值也是多项式插值，但其原理与拉格朗日插值、牛顿插值有根本的不同，并且应用广泛，因此单独介绍

为了满足插值问题的更高要求，即：不但要求在节点上的函数值相等，而且还要求对应的导数值也相等,甚至要求高阶导数也相等，满足这种要求的插值多项式就是埃尔米特插值多项式。

但直接使用Hermite插值得到的多项式次数较高，也存在着龙格现象，因此在实际应用中，往往使用分段三次 Hermite 插值。

分段三次埃尔米特插值的Matlab实现：

Matlab有内置的函数： p = pchip(x,y, new_x)

下面使用Matlab比较分段三次埃尔米特插值与三次样条插值的结果，以函数y=sin(x) 的插值为例：

x = ‐pi:pi; 
y = sin(x); 
new_x = ‐pi:0.1:pi; 
p1 = pchip(x,y,new_x); %分段三次埃尔米特插值 
p2 = spline(x,y,new_x);  %三次样条插值
plot(x,y,'o',new_x,p1,'r‐',new_x,p2,'b‐')
legend('样本点','三次埃尔米特插值','三次样条插值',‘Location’,‘SouthEast’) %标注显示在东南方