插值的意思就是，通过已有的x和y构造函数，然后求F(x*) 即可得到Y*。
在实际建模过程中，常有多项式插值、分段插值、三角插值。
我们来看插值法的原理：如下图所示，只要n+1个节点互异，满足方程的的多项式是唯一存在的。
 

 
 
 
接下来介绍常用的插值方法，拉克朗日插值法
 
 
具体证明过程单独看一下搜索一下资料看吧，这里主要记录一下。
 
但是出现拉格朗日插值法会出现龙格现象(Runge phenomenon)
 
所以我们采用常采用的是分段线性插值法
 
 
另外牛顿插值法是优化 拉格朗日插值法计算的一种插值方法
 
 
在许多实际问题中，不仅要求插值函数与被插值函数在所有节点处有相同的函数值，它也需要在一个或全部节点上插值多项式与被插函数有相同的导数值。
 
 
所以，我们需要学习埃尔米特插值
 
 
缺点
 
 
在matlab中 埃尔米特插值法有内置函数
 
p = pchip(x,y,new_x)
 
这里我们学习一下plot函数的用法
 
plot(x,y,'o',new_x,p,'r-')
线方式： 实线-  点线:  虚点线-.  波折线--
点方式： 圆点.  加号+  星号*  x形x  小圆o
颜色：y黄  r红  g绿  k黑  m紫 c青
 
 
三次样条插值方法
 
 
 
 
N维数据插值interpn
 
 

插值法
 
插值法主要解决的问题就是，用一个多项式函数来逼近原函数，或者用多项式函数来拟合离散数据，在计算机图形的处理中，插值法应用广泛
 
插值法基本的有两种，拉格朗日插值法和牛顿插值法
 
还有一种要求更为严格的差值方法赫米特（Hiemite）插值法
 
 
 
插值法用多项式来逼近原函数，可以证明给定N个插值节点，只能构造唯一的，最高次不高于n的差值多项式
 
一般我们可以使用待定系数法，列出若干个方程，来求解系数，得到差值多项式。
 
 
 
拉格朗日插值法则构造一个差值基函数，保证这一部分在X取X0的时候等于1，在其他的时候等于0，不让其他的点干扰
 
基本形式为
 
插值基函数为
 
牛顿插值法则是引入差商的概念
 
 
 
 
关于差商的计算，我们可以使用递推的方式
 
 
最后牛顿插值法的基本形式为
 
 
 
 
拉格朗日插值法不具有承袭性，当增加了一个新的插值节点，我们需要全部重新计算
 
而牛顿插值法，改进了这一点，以上情况出现时，只需要在后面增加多一项即可。
 
 
 
拉格朗日插值法
 
double Lagrange(double *p,int n,double x)
{//P是插值节点数组，n是插值节点格式，x是自变量的取值
    int i,j,k;
    double numerator,denominator,ans;
    ans=0;//numerator分子，denominator分母
    for(k=0;k<n;k++)
    {
        numerator=1;
        denominator=1;
        for(i=0;i<n;i++)
        {
            if(i!=k)
            {
                numerator*=(x-(*(p+i*2)));
                denominator*=( (*(p+k*2)) - (*(p+i*2)) );
            }//求插值基函数值
            else
                continue;
        }//End for-i
        ans=ans+( (numerator/denominator) * (*(p+k*2+1)) );//插值基函数*函数值Yi
    }//End for-k
    return ans;
}
 
牛顿插值法
 
double Newton(double *p,int n,double x)
{//P是插值节点数组，n是插值节点格式，x是自变量的取值
    int i,j,k;
    double numerator,denominator,ans=0;
    double *np=(double *)malloc(n*sizeof(double));//用以保存差商
    //使用滚动数组保存插值，节约存储空间
    double ny=(x-(*p));//x-x0
    for(i=0;i<n;i++)//差商数组初始化
        *(np+i)= *(p+i*2+1);
    ans=(*(np+n-1));//一阶差商即为函数值
    for(k=1;k<n;k++)
    {
        for(i=n-1;i>=k;i--)
        {//从后往前求差商，保存在np数组内
            numerator=( *(np+i-1) ) - ( *(np+i));
            denominator=( *(p+(i-k)*2)) - ( *(p+i*2) );
            *(np+i)=(numerator/denominator);
        }//End for-i
        ans+=(*(np+n-1))*ny;
        ny*=(x-(*(p+k*2) ));//累乘(x-xi)的结果
    }//End for-k
    return ans;
}
 
 
 
Hiemite插值法
 
赫米特插值法在前两种插值法的基础上，不仅要求在插值节点处函数值相同，而且导数值也相同，比较常见的就是二点三次插值，即给定两个插值节点和函数值和一个点的导数值
 
基本形式为
 
 
 
赫米特插值法
 
double Hiemite(double *p,int n,double x)
{//p表示插值节点，n表示插值节点个数，x是自变量的取值
 //p是一个三维数组，第一维为X，第二维度为y，第三维度为导数值y′
    int i,j,k;
    double ans=0;
    double numerator,denominator;//前者为分子，后者为分母
    double *lx=(double *)malloc(n*sizeof(double));//记录插值基函数的平方
    double *ax=(double *)malloc(n*sizeof(double));//记录系数α
    double *bx=(double *)malloc(n*sizeof(double));//记录系数β
    for(k=0;k<n;k++)
    {
        numerator=1;    denominator=1;
        for(i=0;i<n;i++)
        {
            if(i!=k){
                numerator*=(x- (*(p+i*3)));
                denominator*=(*(p+k*3) - *(p+i*3));
            }//End if
        }//End for-i
        *(lx+k)=(numerator)/(denominator);
        *(lx+k)=pow( (*(lx+k)) ,2);//求插值基函数的平方

        *(ax+k)=1-2*( (x-(*(p+k*3))) / (*(p+k*3) - *(p+((k+1)%2)*3) ) );
        *(bx+k)=(x-( *(p+k*3) ));
        ans+=(*(p+k*3+1)) * (*(ax+k)) * (*(lx+k));//Yi*αi*Li^2
        ans+=(*(p+k*3+2)) * (*(bx+k)) * (*(lx+k));//Y′i*βi*Li^2
    }//End for-k
    return ans;
}
 
 
 
最小二乘法
 
二乘法是为了在一系列离散点中找到一条曲线，最好地拟合这些点
 
为了达到最好的拟合效果，我们使其曲线的残差平方和最小
 
 
 
 
最小二乘法
 
double Fitting(double *p,int n)
{
    int i,j,k;
    double b,a;
    double ans[4]={0};
    double *m=(double *)malloc(2*3*sizeof(double));

    for(i=0;i<n;i++){//用X,Y,x*x,x*y的累加和
        ans[0]+=(*(p+i*2));//保存Xi求和结果
        ans[1]+=(*(p+i*2+1));//保存Yi求和结果
        ans[2]+=( (*(p+i*2)) * (*(p+i*2)) );//保存Xi*Xi求和结果
        ans[3]+=( (*(p+i*2)) * (*(p+i*2+1)) );//保存Xi*Yi求和结果
    }//End for-i
    *(m+0)=n;   *(m+1)=ans[0];   *(m+2)=ans[1];//第一个方程组的系数
    *(m+3)=ans[0];  *(m+4)=ans[2];  *(m+5)=ans[3];//第二个方程组的系数
    //以下过程模拟解方程的过程
    for(i=0;i<3;i++){//i循环两个方程组的三个系数
        *(m+i)/=n;//第一个方程组左右两边除以N
        *(m+i+3)-=( ans[0] * ( *(m+i) ) );//模拟第一个方程组乘以Xi的累加和后消去a的过程
    }

    b= ( *(m+5) )/( *(m+4) );//a消去以后直接求b
    a= ( (*(m+2))-( b*(*(m+1))) ) /(*m);//带入第一个方程组中求出a
    printf("b=%lf a=%lf\n",b,a);
    printf("线性拟合的结果为Y=%lfX",b);
    a<0?printf("%lf\n",a):printf("+%lf\n",a);
}
 
 

引言
 
我们首先理解下插值法主要用来做什么事：插值法就是利用已知的点建立合适的插值函数 $f(x)$ ,未知点 $x_i$ 由插值函数 $f(x)$ 可以求出函数值 $f(x_i)$，用求得的$(x_i,f(x_i))$近似代替未知点。
 
对于平面上相异（无两点在一条直线上）的 $n$ 个点，我们必定可以找到一个 $n-1$ 次多项式 $y=a_0+a_{1}x+a_2{x}^2+...a_{n-1}{x}^{n-1}$ ，使这个多项式函数经过这些点。拉格朗日插值法和牛顿插值法所要做的就是求得这个多项式函数。只是求得多项式的方式有些不同，下面详细介绍。
 
拉格朗日插值法
 
已知$n$ 个点的坐标 $(x_1,y_1),(x_2,y_2),(x_3,y_3)....(x_n,y_n)$，求得一个$n-1$ 次多项式 过这些点。
假设$n-1$ 次多项式为：$y=a_0+a_{1}x+a_2{x}^2+...a_{n-1}{x}^{n-1}$
将n个点代入多项式得：$$y_1=a_0+a_1{x}_1+a_2{x}_1^2+...a_{n-1}{x}_1^{n-1}$$$$y_2=a_0+a_1{x}_2+a_2{x}_2^2+...a_{n-1}{x}_2^{n-1}$$ $$.....$$$$y_n=a_0+a_1{x}_n+a_2{x}_n^2+...a_{n-1}{x}_n^{n-1}$$
易解出拉格朗日插值多项式为：$$L(x)=y_1\frac{(x-x_2)(x-x_3)...(x-x_n)}{(x_1-x_2)(x_1-x_3)...(x_1-x_n)}+y_2\frac{(x-x_1)(x-x_3)...(x-x_n)}{(x_2-x_1)(x_2-x_3)...(x_2-x_n)}$$$$...+y_n\frac{(x-x_1)(x-x_2)...(x-x_{n-1})}{(x_n-x_1)(x_n-x_2)...(x_n-x_{n-1})}$$
上式也可以写为：
 $$L(x)=\sum _{i=1}^n{y}_i\prod _{j=1,j≠i}^n\frac{x-x_j}{x_i-x_j}$$
 
拉格朗日插值公式在理论分析理解上很容易理解，但是若插值节点发生改变时，插值公式随之就要重新计算生成，在实际计算中会占用大量的计算量。e.g. 现在有n个节点生成的插值公式，这里第 n+1 个节点也要加入进去，若使用拉格朗日插值法，之前的n个节点生成的插值公式则要完全调整废弃，重新生成含 n+1 个节点插值公式，这样就带来很大的计算量。正常的想法是，当一个节点要加入，我们只需在原来的插值公式上稍加修改就可以得到新的插值公式，牛顿法的出现正是克服这个问题，当插值节点发生增加，新的插值公式基于原来的公式很容易就得到。
 
牛顿插值法
 
要理解牛顿插值法首先理解一些概念：
 
差商：
 
设函数 $f(x)$ ，已知其$n$个插值节点为$(x_1,y_1),(x_2,y_2),(x_3,y_3)....(x_n,y_n)$，我们定义：
 
一阶差商
 
二阶差商
 
$n$阶差商
 
 其中$\bigwedge$是省略的意思￣□￣｜｜。
 
由以上定义我们的到 差商表 如下：
 
 基于差商的牛顿插值公式：
 
根据差商的定义，我们可以得到下面公式：
 
 
我们可以从后往前不断地代入消去得到：
 
 这时候上式有两部分组成， （不含未知x的）牛顿插值逼近函数$P(x)$、（含未知x的）误差函数$R(x)$也称为余项 把 $R(x)$ 去掉，就得到牛顿插值公式：
 
 
拉格朗日、牛顿插值法小结
 
motivation： 将缺失的函数值对应的点 $x$ 代入多项式得到缺失值的近似值$f(x)$。
 
牛顿插值法和拉格朗日插值法两者都是多项式插值法。从本质上说，两者给出的结果是一样的（相同的次数，相同的系数多项式），只不过表示的形式不同。牛顿插值法与拉格朗日插值法相比具有承袭性和易于变动的特点。

 线性插值法
 
 
 
 
 
线性插值法(linear interpolation)
 
 
 
     
 
      
 目录
 
      [隐藏]
     
 
     
1 什么是线性插值法[1]
2 如何进行线性插值
3 线性插值近似法
4 线性插值法的计算实例[2]
5 参考文献
 
 
 

   [
  编辑]
 
 
 

   
  
 什么是线性插值法[1]
 
 
 
 
　　线性插值法是指使用连接两个已知量的直线来确定在这两个已知量之间的一个未知量的值的方法。
 
 

   [
  编辑]
 
 
 

   
  
 如何进行线性插值
 
 
 
 
　　假设我们已知坐标(x0,y0)与(x1,y1),要得到[x0,x1]区间内某一位置x在直线上的值。根据图中所示，我们得到两点式直线方程：
 
 
　　
 
 
 
 
　　假设方程两边的值为α，那么这个值就是插值系数—从x0到x的距离与从x0到x1距离的比值。由于x值已知，所以可以从公式得到α的值
 
 
　　
 
 
　　同样，
 
 
　　
 
 
　　这样，在代数上就可以表示成为：
 
 
　　y = (1 − α)y0 + αy1
 
 
　　或者，
 
 
　　y = y0 + α(y1 − y0)
 
 
　　这样通过α就可以直接得到 y。实际上，即使x不在x0到x1之间并且α也不是介于0到1之间，这个公式也是成立的。在这种情况下，这种方法叫作线性外插—参见 外插值。
 
 
　　已知y求x的过程与以上过程相同，只是x与y要进行交换。
 
 

   [
  编辑]
 
 
 

   
  
 线性插值近似法
 
 
 
 
　　线性插值经常用于已知函数f在两点的值要近似获得其它点数值的方法，这种近似方法的误线定义为
 
 
　　RT = f(x) − ρ(x)
 
 
　　其中ρ表示上面定义的线性插值多项式
 
 
　　
 
 
　　根据罗尔定理，我们可以证明：如果f有两个连续导数，那么误差范围是
 
 
　　
 
 
　　正如所看到的，函数上两点之间的近似随着所近似的函数的二阶导数的增大而逐渐变差。从直观上来看也是这样：函数的曲率越大，简单线性插值近似的误差也越大。
 
 

   [
  编辑]
 
 
 

   
  
 线性插值法的计算实例[2]
 
 
 
 
　　线性插值法是认为现象的变化发展是线性的、均匀的，所以可利用两点式的直线方程式进行线性插值。
 　　两点式的直线方程式为： 
 
  　　即　　
  
  
 
　　式中　　X0,Y0,X1,Y1——已知的统计数据；
 
 
　　　　　　X——X0,X1之间的任何数据；
 
 
　　　　　　Y——与X对应的插值数据。
 
 
　　例 某地区居民货币收入和消费支出情况如表1所示。试推算该地区居民收入为19．5亿元时，其相应的消费支出是多少?
 
  
  
表1 居民货币收入和消费支出资料(单位：亿元)
 
  
 顺序
 货币收入(x)
 消费支出(y)
 0
 18．2
 15．8
 1
 19．8
 17．2
 
  
 
　　解　　
 
 
　　　　
 
 
　　　　 = 16.9
 
 
　　所以，当该地区居民收入是19．5亿元时，其消费支出是16．9亿元。
 
 
　　由于线性插值法只利用两点的对应值宋推算两点之间的对应值，而两点对应值本身往往受到各种偶然因素的影响，所以线性插值结果可能误差较大。