插值方法

最近看文献发现插值有很多用处，这篇博客是用来梳理和记录的。

1、插值方法原理详解【转】

转载于http://www.cnblogs.com/duye/p/8671820.html 

插值就是根据已知数据点（条件），来预测未知数据点值得方法。具体来说，假如有n个已知条件，就可以求一个n-1次的插值函数P（x），使得P（x）接近未知原函数f（x），并由插值函数预测出需要的未知点值。而又n个条件求n-1次P（x）的过程，实际上就是求n元一次线性方程组。

1）代数插值就是多项式插值，即所求插值函数为多项式函数。一般来说多项式插值就是求n-1个线性方程的解，拉格朗日插值即是基于此思想。

2）泰勒插值：

泰勒插值的条件就是已知0-n阶的导数，满足n阶可导这个条件实在是太苛刻，导致实际上泰勒插值并不常用。下面介绍拉格朗日插值与牛顿插值，这两种方法在本质上是相同的。

3）拉格朗日创造性的避开的方程组求解的复杂性，引入“基函数”这一概念，使得快速手工求解成为可能。

Definition：求作<=n 次多项式 p_n（x），使满足条件p_n（x_i）= y_i，i = 0，1，…，n.这就是所谓拉格朗日（ Lagrange）插值。

下面介绍基函数的一般形式：
对于要求的插值函数P（x），可以证明，均可以化简为以下形式：

给出基函数的一般形式为：

     此即著名的拉格朗日插值公式。

值得注意的是，拉格朗日插值的方法，在插值区间内插值的精度远远大于区间外的精度，故一般说，区间外，拉格朗日插值是不准确的。

4）牛顿插值本质上和朗格朗日插值无异，但为什么牛顿也要提出这么一种插值方法呢？这是因为，拉格朗日插值每增加一个新节点，都要重新计算，换言之，它不具备承袭性。牛顿经过严密的推导，总结了下列具有承袭性的插值方法。差商表如下：

差商具有许多优美的性质，如对称性等，这里不做更多说明。根据上述差商定义，自然得到下面的差商公式表：（即把差商定义式展开）

从而，把后一项不断的代入前一项，就得到：

把最后一项去掉，作为余项（因其含有未知的x），就得到牛顿差商公式：

可以证明，这是关于x的n次多项式。

5） 牛顿插值与拉格朗日插值的比较

设拉格朗日插值函数为P(x)，牛顿插值函数为N(x)，显然二者均满足：P(xi) = N(xi) = f(xi)；

由代数多项式插值的唯一性（本质都在解最开始提到的方程），显然有:P(x) = N(x);

因而，两个插值方法的余项也是相等的。这很有意思，两个余项风格迥异，形式完全不同，却证明了其相等。

当增加一个节点时，对于拉格朗日插值，必须摒弃前面的所有计算去重新计算，而牛顿插值公式却告诉我们，增加的节点只需要在其后再加一项。这种承袭性使得牛顿插值再某些情境下会比拉格朗日插值更加灵活易用。另外还需说明一点，计算余项时，牛顿插值公式余项由于不需要导数，故f(x)是由离散点或者导数不存在时仍然适用，这是拉格朗日余项计算所不能比拟的。

6）埃尔米特插值（Hermite）

有时候，我们不仅要求插值函数在给定节点上函数值重合，而且要求若干阶导数也重合；即：要求插值函数φ(x)满足：

7）分段差值：简而言之，分段差值就是对每一个分段区间（xi,xi+1）分别进行插值，则最后所得插值函数为一分段函数。

在[-5,5]上，对函数f(x) = 1/(1+x^2)进行多项式插值，随着次数的增高，可以看到虽然与原函数重合的点越来越多，可以在端点附近抖动越大，这称为Runge现象。如下图：

在这种原因下，诞生了更加常用的使用分段插值。

插值方法

原文：https://www.cnblogs.com/ytxwzqin/p/9539659.html