技术背景

2024年诺贝尔物理学奖和化学奖的揭幕,正式宣告了科学界对AI时代的认可,人工智能正在全方位的改变人类社会各种场景的互作模式,而数据拟合以及误差与算力的控制,则是大多数人工智能工作者所关注的重点。与数据拟合的思想不同的是,传统的数值计算中人们更倾向于使用多项式进行精确的参数计算,这种方法叫做插值。当然,插值算法的精确是相对于边界条件而言的,随着点数的变化,不同的插值算法有不同的余项。现在在模型训练中,因为数据点本身就是有误差的,所以强行使用插值算法会导致过拟合的现象。只有在一些传统的对精度要求较高的计算场景中,保留了插值算法的应用。

线性插值

给定两个点:
\((x_1,y_1),(x_2,y_2)\)
,其插值出来的线性函数为:

\[f(x)=\frac{y_2-y_1}{x_2-x_1}x+y_1-\frac{y_2-y_1}{x_2-x_1}x_1=\frac{y_2-y_1}{x_2-x_1}x+y_2-\frac{y_2-y_1}{x_2-x_1}x_2
\]

稍微改写一下形式有:

\[f(x)=\left(\frac{x_2-x}{x_2-x_1}\right)y_1+\left(\frac{x-x_1}{x_2-x_1}\right)y_2
\]

可以得到
\(f(x_1)=y_1,f(x_2)=y_2\)

二次插值

给定三个点:
\((x_1,y_1),(x_2,y_2),(x_3,y_3)\)
,假设其插值函数为:
\(f(x)=ax^2+bx+c\)
,那么可以根据三个点联立方程组,写成矩阵形式就是:

\[\left(
\begin{matrix}
x_1^2&&x_1&&1\\
x_2^2&&x_2&&1\\
x_3^2&&x_3&&1
\end{matrix}
\right)\left(
\begin{matrix}
a\\b\\c
\end{matrix}
\right)=\left(
\begin{matrix}
y_1\\y_2\\y_3
\end{matrix}
\right)
\]

所以求解系数
\(a,b,c\)
变成了一个矩阵求逆问题,可以手动做一个初等变换:

\[\begin{align*}
\left(
\begin{matrix}
x_1^2&&x_1&&1&&1&&0&&0\\
x_2^2&&x_2&&1&&0&&1&&0\\
x_3^2&&x_3&&1&&0&&0&&1
\end{matrix}
\right)&\rightarrow
\left(
\begin{matrix}
1&&\frac{1}{x_1}&&\frac{1}{x_1^2}&&\frac{1}{x_1^2}&&0&&0\\
1&&\frac{1}{x_2}&&\frac{1}{x_2^2}&&0&&\frac{1}{x_2^2}&&0\\
1&&\frac{1}{x_3}&&\frac{1}{x_3^2}&&0&&0&&\frac{1}{x_3^2}
\end{matrix}
\right)\\
&\rightarrow
\left(
\begin{matrix}
1&&\frac{1}{x_1}&&\frac{1}{x_1^2}&&\frac{1}{x_1^2}&&0&&0\\
0&&\frac{x_1-x_2}{x_1x_2}&&\frac{x_1^2-x_2^2}{x_1^2x_2^2}&&-\frac{1}{x_1^2}&&\frac{1}{x_2^2}&&0\\
0&&\frac{x_1-x_3}{x_1x_3}&&\frac{x_1^2-x_3^2}{x_1^2x_3^2}&&-\frac{1}{x_1^2}&&0&&\frac{1}{x_3^2}
\end{matrix}
\right)\\
&\rightarrow
\left(
\begin{matrix}
1&&\frac{1}{x_1}&&\frac{1}{x_1^2}&&\frac{1}{x_1^2}&&0&&0\\
0&&\frac{x_1-x_2}{x_1x_2}&&\frac{x_1^2-x_2^2}{x_1^2x_2^2}&&-\frac{1}{x_1^2}&&\frac{1}{x_2^2}&&0\\
0&&\frac{x_1-x_2}{x_1x_2}&&\frac{(x_1+x_3)(x_1-x_2)}{x_1^2x_2x_3}&&-\frac{x_3(x_1-x_2)}{x_1^2x_2(x_1-x_3)}&&0&&\frac{x_1-x_2}{x_2x_3(x_1-x_3)}
\end{matrix}
\right)\\
&\rightarrow
\left(
\begin{matrix}
1&&\frac{1}{x_1}&&\frac{1}{x_1^2}&&\frac{1}{x_1^2}&&0&&0\\
0&&\frac{x_1-x_2}{x_1x_2}&&\frac{x_1^2-x_2^2}{x_1^2x_2^2}&&-\frac{1}{x_1^2}&&\frac{1}{x_2^2}&&0\\
0&&0&&\frac{(x_1-x_2)(x_2-x_3)}{x_1x_2^2x_3}&&\frac{x_2-x_3}{x_1x_2(x_1-x_3)}&&-\frac{1}{x_2^2}&&\frac{x_1-x_2}{x_2x_3(x_1-x_3)}
\end{matrix}
\right)\\
&\rightarrow
\left(
\begin{matrix}
1&&\frac{1}{x_1}&&\frac{1}{x_1^2}&&\frac{1}{x_1^2}&&0&&0\\
0&&1&&\frac{x_1+x_2}{x_1x_2}&&-\frac{x_2}{x_1(x_1-x_2)}&&\frac{x_1}{x_2(x_1-x_2)}&&0\\
0&&0&&1&&\frac{x_2x_3}{(x_1-x_2)(x_1-x_3)}&&-\frac{x_1x_3}{(x_1-x_2)(x_2-x_3)}&&\frac{x_1x_2}{(x_1-x_3)(x_2-x_3)}
\end{matrix}
\right)\\
&\rightarrow
\left(
\begin{matrix}
1&&\frac{1}{x_1}&&\frac{1}{x_1^2}&&\frac{1}{x_1^2}&&0&&0\\
0&&1&&0&&-\frac{x_2+x_3}{(x_1-x_2)(x_1-x_3)}&&\frac{x_1+x_3}{(x_1-x_2)(x_2-x_3)}&&-\frac{x_1+x_2}{(x_1-x_3)(x_2-x_3)}\\
0&&0&&1&&\frac{x_2x_3}{(x_1-x_2)(x_1-x_3)}&&-\frac{x_1x_3}{(x_1-x_2)(x_2-x_3)}&&\frac{x_1x_2}{(x_1-x_3)(x_2-x_3)}
\end{matrix}
\right)\\
&\rightarrow
\left(
\begin{matrix}
1&&0&&0&&\frac{1}{(x_1-x_2)(x_1-x_3)}&&\frac{-1}{(x_1-x_2)(x_2-x_3)}&&\frac{1}{(x_1-x_3)(x_2-x_3)}\\
0&&1&&0&&-\frac{x_2+x_3}{(x_1-x_2)(x_1-x_3)}&&\frac{x_1+x_3}{(x_1-x_2)(x_2-x_3)}&&-\frac{x_1+x_2}{(x_1-x_3)(x_2-x_3)}\\
0&&0&&1&&\frac{x_2x_3}{(x_1-x_2)(x_1-x_3)}&&-\frac{x_1x_3}{(x_1-x_2)(x_2-x_3)}&&\frac{x_1x_2}{(x_1-x_3)(x_2-x_3)}
\end{matrix}
\right)
\end{align*}
\]

也就是说,最终的逆矩阵为:

\[\left(
\begin{matrix}
\frac{1}{(x_1-x_2)(x_1-x_3)}&&\frac{-1}{(x_1-x_2)(x_2-x_3)}&&\frac{1}{(x_1-x_3)(x_2-x_3)}\\
-\frac{x_2+x_3}{(x_1-x_2)(x_1-x_3)}&&\frac{x_1+x_3}{(x_1-x_2)(x_2-x_3)}&&-\frac{x_1+x_2}{(x_1-x_3)(x_2-x_3)}\\
\frac{x_2x_3}{(x_1-x_2)(x_1-x_3)}&&-\frac{x_1x_3}{(x_1-x_2)(x_2-x_3)}&&\frac{x_1x_2}{(x_1-x_3)(x_2-x_3)}
\end{matrix}
\right)
\]

可以验证:

\[\left(
\begin{matrix}
x_1^2&&x_1&&1\\
x_2^2&&x_2&&1\\
x_3^2&&x_3&&1
\end{matrix}
\right)
\left(
\begin{matrix}
\frac{1}{(x_1-x_2)(x_1-x_3)}&&\frac{-1}{(x_1-x_2)(x_2-x_3)}&&\frac{1}{(x_1-x_3)(x_2-x_3)}\\
-\frac{x_2+x_3}{(x_1-x_2)(x_1-x_3)}&&\frac{x_1+x_3}{(x_1-x_2)(x_2-x_3)}&&-\frac{x_1+x_2}{(x_1-x_3)(x_2-x_3)}\\
\frac{x_2x_3}{(x_1-x_2)(x_1-x_3)}&&-\frac{x_1x_3}{(x_1-x_2)(x_2-x_3)}&&\frac{x_1x_2}{(x_1-x_3)(x_2-x_3)}
\end{matrix}
\right)
=
\left(
\begin{matrix}
1&&0&&0\\
0&&1&&0\\
0&&0&&1
\end{matrix}
\right)
\]

有了逆矩阵,就可以计算参数数值
\(a,b,c\)
,那么这里我们直接写出函数形式:

\[f(x)=\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}y_1+\frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)}y_2+\frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}y_3
\]

拉格朗日插值法

观察前面线性插值和二次插值的函数规律,可以给出一个推广形式:

\[f(x)=\sum_{i=1}^{N}c_i(x,x_1,x_2,...,x_N)y_N
\]

其中系数函数
\(c_i(x,x_1,x_2,...,x_N)=\prod_{j=1}^{i-1}\frac{x-x_j}{x_i-x_j}\prod_{k=i+1}^{N}\frac{x-x_k}{x_i-x_k}\)
。可以给出
\(N\)
个数据点的
\(N-1\)
次插值函数解析式,这就是拉格朗日插值法,满足
\(f(x_i)=y_i\)
的约束条件。

牛顿插值法

如果把线性插值中的函数表达式再修改一下形式,变成:

\[f(x)=y_1+\frac{y_2-y_1}{x_2-x_1}(x-x_1)
\]

类似的,二阶插值函数可以改成如下形式:

\[f(x)=y_1+\frac{y_2-y_1}{x_2-x_1}(x-x_1)+\frac{\frac{y_3-y_2}{x_3-x_2}-\frac{y_2-y_1}{x_2-x_1}}{x_3-x_1}(x-x_1)(x-x_2)
\]

如果定义一个一阶差商为:

\[g(x_i,x_{i+1})=\frac{y_{i+1}-y_i}{x_{i+1}-x_i}
\]

其含义为
\((x_i,x_{i+1})\)
区间内的平均变化率。有了一阶差商的定义,就可以递归的定义二阶差商:

\[g(x_i,x_{i+1},x_{i+2})=\frac{g(x_{i+1},x_{i+2})-g(x_{i},x_{i+1})}{x_{i+2}-x_i}
\]

以及
\(m\)
阶的差商:

\[g(x_i,x_{i+1},x_{i+2},...,x_{i+m})=\frac{g(x_{i+1},x_{i+2},...,x_{i+m})-g(x_{i},x_{i+1},...,x_{i+m-1})}{x_{i+m}-x_i}
\]

则可以写出牛顿插值的函数形式为:

\[f(x)=y_1+\sum_{i=1}^{N-1}g(x_1,...,x_{i+1})\prod_{j=1}^{i}(x-x_j)
\]

插值形式对比

拉格朗日插值算法和牛顿插值算法,插值的阶数是一致的,同样的点数插值出来的多项式也是唯一的,换句话说两个方法插值出来的函数其实是等价的。那么两个插值算法的优劣势在哪里?我们考虑这么一种情况,原本有
\(N\)
个数据点需要插值,此时如果再引入一个新的数据点,总点数变成了
\(N+1\)
。此时如果使用的是拉格朗日插值法,那么就需要我们把所有的系数全都再算一遍。而如果使用的是牛顿插值法,那么我们发现前面的
\(N\)
个系数是不需要发生变化的,我们只需要再计算一个新的系数即可,极大程度上的减少了点数更新所带来的参数计算量。但也并不是说拉格朗日插值没有用武之地,在现如今的张量计算时代,拉格朗日插值法的每一项系数都是同Shape的张量操作,反而是牛顿插值的递归形式在张量计算中会有一些麻烦。

总结概要

本文通过线性插值和二次插值的形式,介绍了拉格朗日插值算法以及牛顿插值算法的基本形式。两种插值算法的最终函数形式是一致的,但是在不同场景下的参数求解计算量是不一致的,需要根据自己的应用场景选择更加合适的插值算法。

版权声明

本文首发链接为:
https://www.cnblogs.com/dechinphy/p/lg-interp.html

作者ID:DechinPhy

更多原著文章:
https://www.cnblogs.com/dechinphy/

请博主喝咖啡:
https://www.cnblogs.com/dechinphy/gallery/image/379634.html

标签: none

添加新评论