插值算法

之后的建模学习可能不会再通过手打笔记来复习记录了，通过这种方式来学习建模的效率实在是太低了，但是这两天的收获依旧是很大的，发现了一些问题，以及对于markdown的进一步认识。

设函数y=(f(x)) 在区间[a,b]上有定义，且已知在点(aleq x_0leq x_1leqcdotsleq x_nleq b)上的值分别为：(y_0,y_1,cdots,y_n) ，若存在某一个简单函数(P(x))，使(P(x_i)=y_i)((i)=0,1,2,3,(cdots,n))，则称(P(x)为f(x))的插值函数，点(x_0,x_1,cdots,x_n)称为插值节点，包含插值节点的区间[a,b]称为插值区间，求插值函数(P(x))的方法称为插值法。

若(P(x))是次数不超过n的代数多项式，则称为多项式插值，即(P(x)=a_0+a_1x+cdots+a_nx^n)

可利用线性代数的范德蒙列行列式进行证明求解。

如果不限制多项式的次数，插值多项式并不唯一。
若(P(x))为分段多项式，就称为分段插值
若(P(x))为三角多项式，就称为三角插值。(三角插值一般需要用到傅里叶变换等复杂的数学工具)。

一般常用的为多项式插值和分段差值。

在数值分析中，拉格朗日插值法是以法国十八世纪数学家约瑟夫∙路易斯∙拉格朗日命名的一种多项式插值方法。在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。
通式为：

[w_{n+1}(x)=(x-x_0)(x-x_1)cdots(x-x_n)\ w_{n+1}'(x_k)=(x_k-x_0)cdots(x_k-x_{k-1})(x_k-x_{k+1})cdots(x_k-x_n) ]
[L_n(x)=sum_{k=0}^n y_kfrac{w_{n+1}(x)}{(x-x_k)w_{n+1}'(x_k)} ]
参照上述通式举例:

[三个点(x_0,y_0),(x_1,y_1),(x_2,y_2)\ f(x)=frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}y_0+frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}y_1+frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}y_2 ]

选取跟节点(x)最近的三个节点(x_{i-1},x_{i},x_{i+1})进行二次插值，即在每一个区间([x_{i-1},x_{i+1}])上，取：
[f(x)approx L_2(x)=sum_{k=i-1}^{i+1}[y_kprod_{j=i-1\j eq k}^{i+1}frac{(x-x_j)}{(x_k-x_j)}] ]
这种分段的低次插值称为分段二次插值。在几何上就是用分段抛物线代替(y=f(x))，故分段二次插值又称为分段抛物插值。

[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)+cdots\+f[x_0+x_1+cdots+x_{n-2}+x_{n-1}](x-x_0)(x-x_1)cdots(x-x_{n-3})(x-x_{n-2})\+f[x_0+x_1+cdots+x_{n-1}+x_n](x-x_0)(x-x_1)cdots(x-x_{n-2})(x-x_{n-1}) ]
其中(f[x_0,cdots,x_n])为差商，定义为：(f[x_0,x_k]=frac{f(x_k)-f(x_0)}{x_k-x_0})为函数(f(x))关于点(x_0,x_k)的一阶差商(亦称均差）。
K阶差商:

[f[x_0,cdots ,x_k]=frac{f[x_1,cdots ,x_{k-1},x_k]-f[x_0,cdots ,x_{k-1}]}{x_k-x_0} ]

与拉格朗日插值法相比，牛顿插值法的计算过程具有继承性。（牛顿插值法每次插值只和前n项的值有关，这样每次只要在原来的函数上添加新的项，就能够产生新的函数），但是牛顿插值也存在龙格现象的问题。(个人理解在某些方面二者就像是数组与链表的关系)。
这两种插值仅仅要求插值多项式在插值节点处与被插函数有相等的函数值，而这种插值多项式却不能全面反映被插值函数的性态。然而在许多实际问题中，不仅要求插值函数与被插值函数在所有节

点处有相同的函数值，它也需要在一个或全部节点上插值多项式与被插函数有相同的低阶甚至高阶的导数值。对于这些情况，拉格朗日插值和牛顿插值都不能满足。

要求：
- (phi(x_i)=y_i(i=0,1,cdots,n))
- (phi(x_i)'=y_i'(i=0,1,cdots,n))
- 保持插值曲线在节点处有切线(光滑)，使插值函数和被插值函数的密合程度更好。

本是青灯不归客，却因浊酒留风尘