- 插值算法的概念
- 一维插值问题
- 一般插值多项式的原理
- 拉格朗日插值法
- 牛顿插值法
- 埃尔米特插值法
- 分段 三次埃尔米特插值和分段三次样条插值（常用，附代码）
一、插值算法的概念
数学建模比赛中，常常需要根据已知的函数点进行数据、模型的处理和分析，而有的时候现有的数据是极少的，不足以支撑分析的进行，这时候就需要使用一些数学的方法，“模拟产生”一些新的但又比较靠谱的值来满足需求，这就是插值的作用。
二、一维插值问题
已知有
n
+
1
n+1
n
+
1
个节点
（
x
i
,
y
i
）
(
i
=
0
,
1
,
…
，
n
)
\text{（}x_i,y_i\text{）}\left( i=0,1,…\text{，}n \right)
（
x
i
,
y
i
）
(
i
=
0
,
1
,
…
，
n
)
其中
x
i
x_i
x
i
互不相同，不妨假设
a
=
x
0
<
x
1
<
…
<
x
n
=
b
a=x_0<x_1<…<x_n=b
a
=
x
0
<
x
1
<
…
<
x
n
=
b
,求任一插值点
x
∗
(
≠
x
i
)
x^*(\ne x_i)
x
∗
(
=
x
i
)
处的插值
y
i
y_i
y
i
思路：构造函数
y
=
f
(
x
)
y=f\left( x \right)
y
=
f
(
x
)
,使得
f
(
x
)
f\left( x \right)
f
(
x
)
过所有结点，求
f
(
x
∗
)
f\left( x^* \right)
f
(
x
∗
)
即可得到
y
∗
y^*
y
∗
三、一般多项式的插值原理
定理：设有
n
+
1
n+1
n
+
1
个互不相同的结点
(
x
i
,
y
j
)
(
i
=
0
,
1
,
2
,
…
，
n
)
\left( x_i,y_j \right) \left( i=0,1,2,…\text{，}n \right)
(
x
i
,
y
j
)
(
i
=
0
,
1
,
2
,
…
，
n
)
,则存在唯一的多项式：
使得：
L
n
(
x
j
)
=
y
j
(
j
=
0
,
1
,
2
,
…
，
n
)
L_n\left( x_j \right) =y_{j\,\,}\,\, \left( j=0,1,2,…\text{，}n \right)
L
n
(
x
j
)
=
y
j
(
j
=
0
,
1
,
2
,
…
，
n
)
注意：
-
只要
n+
1
n+1
n
+
1
个结点互异，满足上述插值条件的多项式是唯一存在的。 - 如果不限制多项式的系数，插值多项式并不唯一。
四、拉格朗日插值法
在数值分析中，拉格朗日插值法是以法国十八世纪数学家约瑟夫.路易斯.拉格朗日命名的一种多项式插值方法。在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好可以在各个观测的点取到观测到的值。
-
两个点：
(x
0
,
y
0
)
,
(
x
1
,
y
1
)
\left( x_0,y_0 \right) ,\left( x_1,y_1 \right)
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
-
三个点:
(x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
\left( x_0,y_0 \right) ,\left( x_1,y_1 \right) ,\left( x_2,y_2 \right)
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
-
四个点：
(x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
(
x
3
,
y
3
)
\left( x_0,y_0 \right) ,\left( x_1,y_1 \right) ,\left( x_2,y_2 \right) ,\left( x_3,y_3 \right)
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
(
x
3
,
y
3
)
拉格朗日插值多项式中特别的函数：
由上述公式可得拉格朗日插值多项式为：
拉格朗日插值的缺点：高次插值会产生龙格现象，即在两端处波动极大，产生明显的震荡。在不熟悉曲线的运动趋势的前提下，不要轻易使用高次插值。
五、牛顿插值法
差商的定义：称
f
[
x
0
,
x
k
]
=
f
(
x
k
)
−
f
(
x
0
)
x
k
−
x
0
f\left[ x_0,x_k \right] =\frac{f\left( x_k \right) -f\left( x_0 \right)}{x_k-x_0}
f
[
x
0
,
x
k
]
=
x
k
−
x
0
f
(
x
k
)
−
f
(
x
0
)
为函数
f
(
x
)
f\left( x \right)
f
(
x
)
关于点
x
0
,
x
1
x_0,x_1
x
0
,
x
1
的一阶差商，也可以成为均差。
二阶差商：
f
[
x
0
,
x
1
,
x
2
]
=
f
[
x
1
,
x
2
]
−
f
[
x
0
,
x
1
]
x
2
−
x
0
f\left[ x_0,x_1,x_2 \right] =\frac{f\left[ x_1,x_2 \right] -f\left[ x_0,x_1 \right]}{x_2-x_0}
f
[
x
0
,
x
1
,
x
2
]
=
x
2
−
x
0
f
[
x
1
,
x
2
]
−
f
[
x
0
,
x
1
]
具体牛顿插值的多项式如下：
牛顿插值与拉格朗日插值比较
- 与拉格朗日插值法相比，牛顿插值法的计算过程具有继承性（牛顿插值法每次插值只和前n项的值有关，这样每次只要在原来函数上添加新的项，就能够产生新的插值函数），但牛顿插值也存在龙格现象。
- 这两种插值方法仅仅要求插值多项式在插值结点处与被插函数有相同的函数值，而这种插值多项式却不能全面反映被插函数的特性。在许多的实际问题中，不仅要求插值函数与被插函数在所有结点处有相同的函数值，它也需要在一个或者全部结点上插值多项式与被插函数具有相同的低阶甚至是高阶的倒数值。对于这样的要求，这两种插值方法都不能满足。
六、埃尔米特插值
这种插值方法不但要求节点上的函数值相等，而且要求对应的导数值也相等，甚至要求高阶导数也相等，满足这种要求的插值多项式就是埃尔米特插值多项式。
具体原理：
设函数
f
(
x
)
f\left( x \right)
f
(
x
)
在区间[a,b]上有n+1个互异节点
a
=
x
0
<
x
1
<
…
<
x
n
=
b
a=x_0<x_1<…<x_n=b
a
=
x
0
<
x
1
<
…
<
x
n
=
b
,定义在[a,b]上函数
f
(
x
)
f\left( x \right)
f
(
x
)
在节点上满足：
可唯一确定一个次数不超过2n+1的多项式
H
2
n
+
1
(
x
)
=
H
(
x
)
H_{2n+1}\left( x \right) =H\left( x \right)
H
2
n
+
1
(
x
)
=
H
(
x
)
满足：
其余项为：
七、分段三次埃尔米特插值和分段三次样条插值
分段三次埃尔米特插值
：直接使用埃尔米特插值得到的多项式次数较高，也存在龙格现象，因此在实际应用中，往往使用分段三次埃尔米特插值多项式（PCHIP）
MATLAB有内置函数
p = pchip(x,y,new_x)
x是已知的样本点的横坐标，y是已知样本点的纵坐标，new_x是要插入处对应的横坐标
一个实例，代码如下：
% 分段三次埃尔米特插值
x = -pi:pi; y = sin(x);
new_x = -pi:0.1:pi;
p = pchip(x,y,new_x);
figure(1); % 在同一个脚本文件里面，要想画多个图，需要给每个图编号，否则只会显示最后一个图哦~
plot(x, y, 'o', new_x, p, 'r-')
% plot函数用法:
% plot(x1,y1,x2,y2)
% 线方式： - 实线 :点线 -. 虚点线 - - 波折线
% 点方式： . 圆点 +加号 * 星号 x x形 o 小圆
% 颜色： y黄； r红； g绿； b蓝； w白； k黑； m紫； c青
代码运行结果如下：
分段三次样条插值
：设
y
=
f
(
x
)
y=f\left( x \right)
y
=
f
(
x
)
在点
x
0
,
x
1
,
x
2
,
…
，
x
n
x_0,x_1,x_2,…，x_n
x
0
,
x
1
,
x
2
,
…
，
x
n
的值为
y
0
,
y
1
,
y
2
,
…
，
y
n
y_0,y_1,y_2,…，y_n
y
0
,
y
1
,
y
2
,
…
，
y
n
，若函数
S
(
x
)
S\left( x \right)
S
(
x
)
满足下列条件
-
S(
x
i
)
=
f
(
x
i
)
=
y
i
,
i
=
0
,
1
,
2
,
…
,
n
S\left( x_i \right) =f\left( x_i \right) =y_i,i=0,1,2,…,n
S
(
x
i
)
=
f
(
x
i
)
=
y
i
,
i
=
0
,
1
,
2
,
…
,
n
-
在每一个子区间
[x
i
,
x
i
+
1
]
(
i
=
0
,
1
,
2
,
…
,
n
−
1
)
\left[ x_i,x_{i+1} \right] \left( i=0,1,2,…,n-1 \right)
[
x
i
,
x
i
+
1
]
(
i
=
0
,
1
,
2
,
…
,
n
−
1
)
上
S(
x
)
S\left( x \right)
S
(
x
)
是三次多项式 -
S(
x
)
S\left( x \right)
S
(
x
)
在[a,b]上二阶连续可微
则称
S
(
x
)
S\left( x \right)
S
(
x
)
为函数
f
(
x
)
f\left( x \right)
f
(
x
)
的三次样条插值函数。
三次样条插值函数实例：
MATLAB有内置函数：
p = spline(x,y,new_x)
x是已知的样本点的横坐标，y是已知样本点的纵坐标，new_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); %三次样条插值
figure(2);
plot(x,y,'o',new_x,p1,'r-',new_x,p2,'b-')
legend('样本点','三次埃尔米特插值','三次样条插值','Location','SouthEast') %标注显示在东南方向
% 说明：
% LEGEND(string1,string2,string3, …)
% 分别将字符串1、字符串2、字符串3……标注到图中，每个字符串对应的图标为画图时的图标。
% ‘Location’用来指定标注显示的位置
分析生成结果：可以看出，三次样条生成的曲线更加光滑。在实际建模中，由于我们不知道数据的生成过程，因此两种插值都可以使用。
注意点
：
- 上面学习的这些插值算法可用于短期预测。
- 在实际建模过程中，尽量不要使用插值算法来预测，如果要进行预测，可以选择下面更新的拟合算法或者一些专门用来预测的算法，这些都可以在接下来的更新中学习到。
更多有关于插值法的经典获奖论文，关注公众号，回复，“插值算法”，即可免费领取！！！
