数学建模竞赛知识点汇总（三）——插值算法
简介分类常见的插值算法
拉格朗日插值牛顿插值法埃尔米特插值三次样条插值 后续
简介 数模中，有时需要根据已知的函数点进行数据处理，但有时现有数据太少，就需要用插值方法，模拟产生一些新的、比较靠谱的数据来满足需求。构造函数，使过这些点，插值点处的函数值即为插值
分类多项式插值， P ( x ) P(x) P(x)是多项式
分段插值， P ( x ) P(x) P(x)是分段多项式
三角插值， P ( x ) P(x) P(x) 是三角多项式（此处不做讨论）
插值法定理： P ( x ) P(x) P(x)个互不相同的节点，满足插值条件的多项式存在且唯一
证：用了范德蒙行列式，具体步骤略
常见的插值算法 拉格朗日插值 对某个多项式函数，已知有给定的
k
+
1
k+1
k+1 个取值点：
(
x
0
,
y
0
)
,
…
,
(
x
k
,
y
k
)
left(x_{0}, y_{0}right), ldots,left(x_{k}, y_{k}right)
(x0,y0),…,(xk,yk) ，其中
x
j
x_{j}
xj 对应着自变量 的位置，而
y
j
y_{j}
yj 对应着函数在这个位置的取值。假设任意两个不同的
x
j
x_{j}
xj 都互不相同，那么应用拉格朗日 揷值公式所得到的拉格朗日揷值多项式为:
L
(
x
)
:
=
∑
j
=
0
k
y
j
ℓ
j
(
x
)
L(x):=sum_{j=0}^{k} y_{j} ell_{j}(x)
L(x):=j=0∑kyjℓj(x)
其中每个
ℓ
j
(
x
)
ell_{j}(x)
ℓj(x) 为拉格朗日基本多项式 (或称揷值基函数)，其表达式为:
ℓ
j
(
x
)
:
=
∏
i
=
0
,
i
≠
j
k
x
−
x
i
x
j
−
x
i
=
(
x
−
x
0
)
(
x
j
−
x
0
)
⋯
(
x
−
x
j
−
1
)
(
x
j
−
x
j
−
1
)
(
x
−
x
j
+
1
)
(
x
j
−
x
j
+
1
)
⋯
(
x
−
x
k
)
(
x
j
−
x
k
)
ell_{j}(x):=prod_{i=0, i neq j}^{k} frac{x-x_{i}}{x_{j}-x_{i}}=frac{left(x-x_{0}right)}{left(x_{j}-x_{0}right)} cdots frac{left(x-x_{j-1}right)}{left(x_{j}-x_{j-1}right)} frac{left(x-x_{j+1}right)}{left(x_{j}-x_{j+1}right)} cdots frac{left(x-x_{k}right)}{left(x_{j}-x_{k}right)}
ℓj(x):=i=0,i=j∏kxj−xix−xi=(xj−x0)(x−x0)⋯(xj−xj−1)(x−xj−1)(xj−xj+1)(x−xj+1)⋯(xj−xk)(x−xk)
拉格朗日基本多项式
ℓ
j
(
x
)
ell_{j}(x)
ℓj(x) 的特点是在
x
j
x_{j}
xj 上取值为 1 ，在其它的点
x
i
,
i
≠
j
x_{i}, i neq j
xi,i=j 上取值为 0 。
即：对于给定的
n
+
1
n+1
n+1 个点
(
x
0
,
y
0
)
,
(
x
1
,
y
1
)
,
…
,
(
x
n
,
y
n
)
left(x_{0}, y_{0}right),left(x_{1}, y_{1}right), ldots,left(x_{n}, y_{n}right)
(x0,y0),(x1,y1),…,(xn,yn) ，对应于它们的次数不超过
n
n
n 的拉格朗日 多项式
L
L
L 只有一个。
拉格朗日插值是一种多项式插值方法。但因为高次插值会产生龙格现象，两端波动非常大，所以不要轻易使用高次插值。
牛顿插值法差商：
函数
f
(
x
)
f(x)
f(x) 在两个互异点
x
i
,
x
j
x_{i}, x_{j}
xi,xj 处的一阶差商定义为:
f
[
x
i
,
x
j
]
=
f
(
x
i
)
−
f
(
x
j
)
x
i
−
x
j
(
i
≠
j
,
x
i
≠
x
j
)
fleft[x_{i}, x_{j}right]=frac{fleft(x_{i}right)-fleft(x_{j}right)}{x_{i}-x_{j}}left(i neq j, x_{i} neq x_{j}right)
f[xi,xj]=xi−xjf(xi)−f(xj)(i=j,xi=xj)
2阶差商:
f
[
x
i
,
x
j
,
x
k
]
=
f
[
x
i
,
x
j
]
−
f
[
x
j
,
x
k
]
x
i
−
x
k
(
i
≠
k
)
fleft[x_{i}, x_{j}, x_{k}right]=frac{fleft[x_{i}, x_{j}right]-fleft[x_{j}, x_{k}right]}{x_{i}-x_{k}}(i neq k)
f[xi,xj,xk]=xi−xkf[xi,xj]−f[xj,xk](i=k)
k
+
1
k+1
k+1 阶差商:
f
[
x
0
,
…
,
x
k
+
1
]
=
f
[
x
0
,
x
1
,
…
x
k
]
−
f
[
x
1
,
…
,
x
k
,
x
k
+
1
]
x
0
−
x
k
+
1
=
f
[
x
0
,
…
,
x
k
−
1
,
x
k
]
−
f
[
x
0
,
…
,
x
k
−
1
,
x
k
+
1
]
x
k
−
x
k
+
1
begin{gathered} fleft[x_{0}, ldots, x_{k+1}right]=frac{fleft[x_{0}, x_{1}, ldots x_{k}right]-fleft[x_{1}, ldots, x_{k}, x_{k+1}right]}{x_{0}-x_{k+1}} \ =frac{fleft[x_{0}, ldots, x_{k-1}, x_{k}right]-fleft[x_{0}, ldots, x_{k-1}, x_{k+1}right]}{x_{k}-x_{k+1}} end{gathered}
f[x0,…,xk+1]=x0−xk+1f[x0,x1,…xk]−f[x1,…,xk,xk+1]=xk−xk+1f[x0,…,xk−1,xk]−f[x0,…,xk−1,xk+1]
牛顿插值法：
f
(
x
)
=
f
(
x
0
)
+
f
[
x
0
,
x
1
]
(
x
−
x
0
)
+
f
[
x
0
,
x
1
,
x
2
]
(
x
−
x
0
)
(
x
−
x
1
)
+
⋯
+
f
[
x
0
,
x
1
,
⋯
,
x
n
−
2
,
x
n
−
1
]
(
x
−
x
0
)
(
x
−
x
1
)
⋯
(
x
−
x
n
−
3
)
(
x
−
x
n
−
2
)
+
f
[
x
0
,
x
1
,
⋯
,
x
n
−
1
,
x
n
]
(
x
−
x
0
)
(
x
−
x
1
)
⋯
(
x
−
x
n
−
2
)
(
x
−
x
n
−
1
)
begin{aligned} f(x)=& fleft(x_{0}right)+fleft[x_{0}, x_{1}right]left(x-x_{0}right) \ &+fleft[x_{0}, x_{1}, x_{2}right]left(x-x_{0}right)left(x-x_{1}right)+cdots \ &+fleft[x_{0}, x_{1}, cdots, x_{n-2}, x_{n-1}right]left(x-x_{0}right)left(x-x_{1}right) cdotsleft(x-x_{n-3}right)left(x-x_{n-2}right) \ &+fleft[x_{0}, x_{1}, cdots, x_{n-1}, x_{n}right]left(x-x_{0}right)left(x-x_{1}right) cdotsleft(x-x_{n-2}right)left(x-x_{n-1}right) end{aligned}
f(x)=f(x0)+f[x0,x1](x−x0)+f[x0,x1,x2](x−x0)(x−x1)+⋯+f[x0,x1,⋯,xn−2,xn−1](x−x0)(x−x1)⋯(x−xn−3)(x−xn−2)+f[x0,x1,⋯,xn−1,xn](x−x0)(x−x1)⋯(x−xn−2)(x−xn−1)
牛顿插值法具有继承性，但也存在龙格现象拉格朗日和牛顿都不能全面反映被插值函数的形态。
设函数
f
(
x
)
f(x)
f(x) 在区间
[
a
,
b
]
[a, b]
[a,b] 上有
n
+
1
mathrm{n}+1
n+1 个互异节点
a
=
x
0
<
x
1
<
x
2
<
…
<
x
n
=
b
quad boldsymbol{a}=boldsymbol{x}_{0}
可唯一确定一个次数不超过
2
n
+
1
2 n+1
2n+1 的多项式
H
2
n
+
1
(
x
)
=
H
(
x
)
H_{2 n+1}(x)=H(x)
H2n+1(x)=H(x) 满足:
H
(
x
j
)
=
y
j
,
H
′
(
x
j
)
=
m
j
(
j
=
0
,
1
,
⋯
n
)
.
Hleft(x_{j}right)=y_{j}, quad H^{prime}left(x_{j}right)=m_{j} quad(j=0,1, cdots n) .
H(xj)=yj,H′(xj)=mj(j=0,1,⋯n).
其余项为:
R
(
x
)
=
f
(
x
)
−
H
(
x
)
=
f
(
2
n
+
2
)
(
ξ
)
(
2
n
+
2
)
!
ω
2
n
+
2
(
x
)
R(x)=f(x)-H(x)=frac{f^{(2 n+2)}(xi)}{(2 n+2) !} omega_{2 n+2}(x)
R(x)=f(x)−H(x)=(2n+2)!f(2n+2)(ξ)ω2n+2(x)
埃尔米特插值不仅要求节点上的函数值相等，导数值也要相等，甚至要求高阶导数。
在实际应用中，往往使用分段三次埃尔米特插值。matlab有内置函数 p c h i p ( x , y , n e w x ) pchip(x, y, new_x) pchip(x,y,newx)。
三次样条插值把区间 [ a , b ] [a,b] [a,b]分成 n n n个区间 [ ( x 0 , x 1 ) , ( x 1 , x 2 ) , … , ( x n − 1 , x n ) ] left[left(x_{0}, x_{1}right),left(x_{1}, x_{2}right), ldots,left(x_{n-1}, x_{n}right)right] [(x0,x1),(x1,x2),…,(xn−1,xn)]共有n+1个点，其中两个端点 x 0 = a , x n = b x_{0}=a, x_{n}=b x0=a,xn=b。三次样条就是说每个小区间的曲线是一个三次方程，三次样条方程满足以下条件：
在每个分段小区间 [ x i , x i + 1 ] left[x_{i}, x_{i+1}right] [xi,xi+1]上， S ( x ) = S i ( x ) S(x)=S_{i}(x) S(x)=Si(x)都是一个三次方程
满足插值条件，即 S ( x i ) = y i ( i = 0 , 1 , … , n ) Sleft(x_{i}right)=y_{i} quad(i=0,1, ldots, n) S(xi)=yi(i=0,1,…,n)
曲线光滑，即 S ( x ) , S ′ ( x ) , S ′ ′ ( x ) S(x), quad S^{prime}(x), quad S^{prime prime}(x) S(x),S′(x),S′′(x)连续
则这个三次方程可以构造成如下形式：
y
=
a
i
+
b
i
x
+
c
i
x
2
+
d
i
x
3
y=a_{i}+b_{i} x+c_{i} x^{2}+d_{i} x^{3}
y=ai+bix+cix2+dix3
这种形式,我们称这个方程为三次样条函数
S
i
(
x
)
S_{i}(x)
Si(x)
喜欢的话可以关注一下我的公众号技术开发小圈，尤其是对深度学习以及计算机视觉有兴趣的朋友，我会把相关的源码以及更多资料发在上面，希望可以帮助到新入门的大家！
