插值法

2018.1.9 学习笔记
数学，数论

---

自己以前写的好naive啊QAQ丢个链接走人：
https://www.cnblogs.com/zwfymqz/p/10063039.html
https://blog.csdn.net/qq_35649707/article/details/78018944
不要看这篇了...

---

插值

引用青峰碧陋室
  在工程应用和科学研究中，经常要研究变量之间的关系$y=f(x)$。但对于函数$f(x)$，常常得不到一个具体的解析表达式，它可能是通过观测或实验得到的一组数据$(x,f(x))$，$x$为一向量;或则是解析表达式非常复杂，不便于计算和使用。因此我们需要寻找一个计算比较简单的函数$S(x)$近似代替$f(x)$，并使得$S(x)=f(x)$，这种方法就称为插值法。

常见的插值法有：
　　一维插值法：拉格朗日插值、牛顿插值、分段低次插值、埃尔米特差值、样条插值。
　　二维插值法：双线性插值、双二次插值。

拉格朗日插值

摘自Angel_Kitty、lgj's blog

拉格朗日多项式

  许多实际问题中都用函数来表示某种内在联系或规律，而不少函数都只能通过实验和观测来了解。如对实践中某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日（插值）多项式。
　　对于给定的$n+1$个点$(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)$，对应于它们的次数不超过n的拉格朗日多项式L只有一个。如果计入次数更高的多项式，则有无穷个，因为所有与L相差 $\lambda(x-x_0)(x-x_1)\cdots(x-x_n)$的多项式都满足条件。

定义

　　对某个多项式函数，已知有给定的$k+1$个取值点：$(x_0,y_0),(x_1,y_1),\cdots,(x_k,y_k)$，其中$x_j$对应着自变量的位置，而$y_j$对应着函数在这个位置的取值。
　　假设任意两个不同的$x_j$都互不相同，那么应用拉格朗日插值公式所得到的拉格朗日插值多项式为：

$$L(x)=\sum_{j=0}^{k}y_jl_j(x)$$
其中每个$l_j(x)$为拉格朗日基本多项式（或称插值基函数），其表达式为：
$$l_j(x)=\prod_{i=0,i\neq j}^{k}\frac{x-x_i}{x_j-x_i}=\frac{x-x_0}{x_j-x_0}\cdots\frac{x-x_{j-1}}{x_j-x_{j-1}}\frac{x-x_{j+1}}{x_j-x_{j+1}}\cdots\frac{x-x_k}{x_j-x_k}$$
　　拉格朗日基本多项式$l_j(x)$的特点是在$x_j$上取值为1，在其它的点$x_i,i\neq j$上取值为0。

应用

　　若给定$n$个互不相同的点$(x,y)$，则该$n-1$次多项式被唯一确定。利用拉格朗日插值，可以在$O(n)$的时间内计算出某一项的值，还可以在$O(n^2)$的时间内计算出给定的x所对应的y。

公式

　　若对于$n-1$次多项式，给定$n$个互不相同的点$(x,y)$，那么对于给定的$x$，
　　第$i$项的值为

$$l(i)=y_i\prod_{j=1,j\neq i}^{n}\frac{x-x_j}{x_i-x_j}$$
　　所对应的$y$为
$$\begin{aligned} y &=\sum_{i=1}^{n}l(i)\\ &=\sum_{i=1}^{n}y_i\prod_{j=1,j\neq i}{n}\frac{x-x_j}{x_i-x_j} \end{aligned}$$

Code

double Lagrange(double *x,double *y,double X)//x和y分别为x和f(x)的取值，X为要求的点，返回f(X) 
{
    double res=0,tmp;
    for(int i=1;i<=n;++i)
    {
        tmp=1;
        for(int j=1;j<=n;++j)
            if(i!=j) tmp=tmp*(X-x[i])/(x[i]-x[j]);
        res+=y[i]*tmp;
    }
    return res;
}

例子 && 证明：存在性与唯一性 && 几何性质

　　见blog。

优点与缺点

　　拉格朗日插值法的公式结构整齐紧凑，在理论分析中十分方便，然而在计算中，当插值点增加或减少一个时，所对应的基本多项式就需要全部重新计算，于是整个公式都会变化，非常繁琐。这时可用重心拉格朗日插值法或牛顿插值法来代替。此外，当插值点比较多的时候，拉格朗日插值多项式的次数可能会很高，因此具有数值不稳定的特点，也就是说尽管在已知的几个点取到给定数值，但在附近却会和“实际上”的值之间有很大偏差，这类现象也称为龙格现象，解决方法是分段用较低次数的插值多项式。

重心拉格朗日插值法

　　见blog...已弃疗

---

牛顿插值法（格雷戈里-牛顿公式）

牛顿插值原理、利用差分的牛顿插值、利用均差的牛顿插值。弃疗*2

定义

　　已知函数$f(x)$的$n+1$个互异节点$x_i$处的函数值$f(x_i)$，则其牛顿插值多项式可以写为：

$$N_n(x)=a_0+a_1(x-x_0)+\cdots+a_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})$$
　　其中，$a_k$为$f(x)$的k阶差商（也叫均差），可以表示如下：
$$a_k=f[x_0,x_1,\cdots,x_{k-1},x_k]$$
　　也可以由函数值$f(x_i)$线性表示为：
$$a_k=\sum_{i=0}^{n}\frac{f(x_i)}{(x_i-x_0)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_k)}$$

Code

double DifferenceQuotient(double *x,double *y,int k)//计算差商 
{
    double res=0,tmp;
    for(int i=1;i<=k;++i)
    {
        tmp=1;
        for(int j=1;j<=k;++j)
            if(i!=j) tmp/=(x[i]-x[j]);
        res+=y[i]*tmp;
    }
    return res;
}
double Newton(double *x,double *y,double X)
{
    double res=y[1],tmp=1;
    for(int i=2;i<=n;++i)
        tmp*=(X-x[i-1]), res+=DifferenceQuotient(x,y,i)*tmp;
    return res;
}

优点

　　当插值节点增加时，之前已计算的结果仍然能用，每增加一个节点，只要再增加一项即可，从而避免了重复计算。