插值算法主要运用于在数学建模竞赛中，现有的数据极少，不足以支撑分析的进行，这时候就需要使用一些数学的方法
插值的作用，“模拟产生” 一些新的但又比较靠谱的值来满足需求
# 一维插值问题
# 问题如下：
已经有 n+1 个节点 (xi,yi)(i=0,1,...,n), 其中 xi 互不相同，不妨设 a <= x0 < x1 < ... < xn <= b , 求任一插值点 x * （不等于 xi）处的插值 y *
思路：构造 y=f (x), 使得 f (x) 过所有节点，即可得到 y *
# 插值法的概念
设函数 y=f (x) 在区间 [a,b] 上有定义，且已知在点 a<= x0 < x1 < ... < xn <= b 上的值分别为 y0 , y1 , ... , yn
若存在一简单函数 P (x) 使 P (xi) = yi ( i = 0 , 1 , 2 , ... , n ) 则称 P (x) 为 f (x) 的插值函数，点 x0,x1,...,xn 称为插值节点，包含插值节点的区间 [a,b] 称为插值区间
求插值函数 P (x) 的方法称为插值法
插值法是不唯一的
代数多项式：若 P (x) 是次数不超过 n 的代数多项式，即 P (x) = a0 + a1x + ... + anx^n
分段插值：若 P (x) 为分段多项式，就称为分段插值
三角插值：若 P (x) 为三角多项式，就称为三角插值（不予讨论）（一般要用到傅立叶变换等复杂的数学工具）
一般来讲三角插值适用于对周期函数的插值（三角函数嘛）
# 插值法原理
定理：设有 n+1 个互不相同的节点 (xi,yi)(i=0,1,2,...,n) 则存在唯一的多项式：
Ln (x) = a0 + a1x + ... + anx^n 使得 Ln (xj) = yj (j=0,1,2,...n)
证 构造方程组
「a0 + a1x0 + ... + anx0^n = y0
a0 + a1x1 + ... + anx1^n = y1
...
a0 + a1xn + ... + anxn^n = yn 」
图片：
# 拉格朗日插值法
在数值分析中，拉格朗日插值法是以法国十八世纪数学家约瑟夫・拉格朗日命名的一种多项式插值方法。如对实践中的某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日（插值）多项式。
对于两个点：(x0,y0) , (x1,y1)
f(x) = ( x - x1 ) y0 / ( x0 - x1 ) + ( x - x0 ) y1 / ( x1 - x0 )
对于三个点：(x0,y0),(x1,y1),(x2,y2)
f(x) = [ ( x - x1 ) ( x - x2 ) y0 ] / [ ( x0 - x1 ) ( x0 - x2 ) ]
- [ ( x - x0 ) ( x - x2 ) y1 ] / [ ( x1 - x0 ) ( x1 - x2 ) ]
- [ ( x - x0 ) ( x - x1 ) y2 ] / [ ( x2 - x0 ) ( x2 - x1 ) ]
我们可以归纳发现，这种式子如果取其中的一个 xi 取得的值必定是 yi，因为其它项为 0，对应的 xi 的 yi 的系数必定为 1![]()
然而我们实际情况中却不可能用拉格朗日插值法，他有很多问题
# 龙格现象
图片 1:
图片 2:
这引出了两个问题
- 插值多项式次数高，精度未必显著提高
- 插值多项式次数越高，摄入误差可能显著增大
我们可以得到，对于高次的多项式插值时，如果我们不确定曲线的类型，我们尽量不要使用
那么如何提高插值精度呢
采用分段线性插值
# 分段插值
# 分段线性插值
如果我们要在中间找一个值，我们找距离它最近的两点，两点之间连一条线段，直接在这条线段上找 x 对应的 y 值即可
这种插值是十分简单的，也是不精准的
# 分段二次插值
分段二次插值也是非常简单的，我们可以寻找距离这个插入点最近的三个点，三个点可以形成一个二次函数，同理可以直接取二次函数的值
分段二次插值又称为分段抛物线插值
