最近在做心电相关的项目，由于单片机的处理能力有限，在接收心电信号之后需要对数据进行压缩（其实是取一些特征点），然后后期再进行显示。但是在手持ARM上进行显示的时候，通过这些残缺的数据绘出心电图形是很困难的，这就要进行插值处理，所以进行了一些插值算法相关的研究，常用的插值算法是拉格郎日插值和牛顿插值算法，切比雪夫插值算法。
拉格郎日的原理，下面这篇帖子写的比较好，感兴趣可以看一下，对于应用型达人来讲，不必对原理过于纠结。
复杂的公式：
其中每个
为拉格朗日基本多项式（或称插值基函数），其表达式为：
拉格朗日基本多项式
的特点是在
上取值为1，在其它的点
上取值为0。
//arrX[N],arrY[N]分别存放的是已知插值节点(Xi,Yi)中的Xi,Yi,参数n为已知插值节点的个数,而参数x为待求解的插值节点的横坐标值float Lagrange(float arrX[],float arrY[],int n, float x){ float yResult = 0.0; float LValue[80]; int k,m; float temp1,temp2; for(k=0;k
f(X1) = 1；
f(X1,X2) = (f(X2)- f(X1))/( X2- X1) = 1/2
f(X2,X3) = 2. 计算同上，虽然这不是有效系数，但是在进一步求系数的时候会用到。
f(X1,X2,X3) = (f(X2, X3)- f(X2, X3))/( X3- X1) = 1/2
所以，f(X) = 1+1/2*(X-0)+1/2(X-0)(X-2)
这就是理论学习中牛顿插值算法所谓的差商原理。
这一步数学计算的目的可以加深大脑对计算过程的理解，推荐演算一遍。
下面是程序实现，仅仅有理论是不够的，还得写出代码。
首先，我们需要两个数组，X[3],Y[3],分别存放3个横坐标和对应的纵坐标值。
X[3] = {0,2,3}, Y[3] = {1,2,4}.
关键的问题还是求系数，作者给我们提供的思路是使用二维数组来存放，我推演一遍。二维数组a[i][j]的大小根据自己的需要来定。
先给出结果：
当j=0的时候，a[i][0] = Y[i].
当i>=1,j>=1的时候，a[i][j] = (a[i][j-1]-a[i-1][j-1])/(X[i]-X[i-j])
自己归纳一下就可以得到上面的结论。
a[0][0] = Y[0] = 1;
a[1][0] = Y[1] = 2; a[1][1] = (a[1][0]-a[0][0])/(X[1]-X[0]) = (2-1)/(2-0) = 1/2
a[2][0] = Y[2] = 4; a[2][1] = (a[2][0]-a[1][0])/(X[2]-X[1]) = (4-2)/(3-2) = 2
a[2][2] = (a[2][1]-a[1][1])/(X[2]-X[0]) = (2-1/2)/3 = 1/2
所以，f(X) = 1+1/2*(X-0)+1/2(X-0)(X-2)
有效的系数全部存在了a[i][i]（i=j的时候）中。
有了上面的二维数组，就可以很容易的实现牛顿插值算法了。
牛顿代码实现：
插值系数计算：//求得系数，length为已知的插值点个数 for(i=0;i
三. 切比雪夫插值
切比雪夫插值的提出是为了改善插值在差值区间上的最大误差控制
关键：切比雪夫插值节点的选取
对于一个插值区间 [a, b], 如果要在这个插值区间上选取n个点作为插值基点,使得上面的最大误差
最小，则基点的选法如下:
对于 i = 1, 2, ...., n. 下面的不等式在区间 [a, b] 上满足
切比雪夫的实现就是在牛顿插值中选取合适的基点，并且要用到cos函数。这个算法感兴趣的可以自己研究一下。