问题

一、拉格朗日插值基函数

• n=1时一次基函数
  
• 两点线性插值问题
  

• 问题：即已知函数 f(x)在点$x_0$和$x_1$点的函数值
  $y_0$=f($x_0$)，$y_1$=f($x_1$).
  求线性函数 $L_1$(x)=$a_0$+$a_1$x
  使满足条件：$L_1$($x_0$)=$y_0$,$L_1$($x_1$)=$y_1$

①：把x=$x_0$带入$L_1$(x)中，$L_1(x_0)$ = $y_0$ + 0 = $y_0$
②：把x=$x_1$带入$L_1$(x)中，$L_1$($x_1$) = $y_0$ + ($y_1$-$y_0$)($x_1$-$x_0$) / ($x_1$-$x_0$) = $y_0$ + $y_1$ - $y_0$ = $y_1$

则称$l_0$(x)叫做点$x_0$的一次插值基函数， $l_1$(x)叫
做点$x_1$的一次插值基函数

当x=$x_0$时，$l_0$=1; x=$x_1$时，$l_0$=0;
当x=$x_0$时，$l_1$=0; x=$x_1$时，$l_1$=1;

• n=2时二次基函数
  

二、拉格朗日插值多项式

对上述举例：

begin---------------------------------------------

• n=1时
  

①：把x=$x_0$带入$L_1$(x)中，L1(x0) = $y_0$ + 0 = $y_0$
②：把x=$x_1$带入$L_1$(x)中，L1(x1) = $y_0$ + ($y_1$-$y_0$)($x_1$-$x_0$) / ($x_1$-$x_0$) = $y_0$ + $y_1$ - $y_0$ = $y_1$
③：由此推广到$L_n$(x)的多项式,$L_n$($x_j$) = $y_j$ j=0,1,2,…,n

end-----------------------------------------------

再由插值多项式的唯一性: $P_n$( x) = $L_n$( x）

特别地:
当 n =1时又叫线性插值,其几何意义为过两点的直线.
当 n =2时又叫抛物（线）插值, 其几何意义为过三点的抛物线.

• 注意
  
  习题

三、n次Lagrange插值多项式余项

截断误差$R_n(x)$=f(x) -$L_n$(x)也称为n次Lagrange插值多项式的余项。

• 拉格朗日余项定理
  

${\omega }_n$${}_{+}$${}_1$($x$) = ($x$-$x_0$)($x$-$x_1$)($x$-$x_2$)…($x$-$x_n$)
由给定条件可知$R_n(x)$在节点$x_k$($k$=0,1,…,n)上为0，即 $R_n(x)$ = 0 ($k$=0,1,…,n)
插值节点$x_i$ 上误差等于零

• 截断误差限⭐（求误差会用到该公式）
  
• 结论例题⭐
  
  习题

习题

• 例题

• 例题

总结

• 拉格朗日插值的优缺点
  

首先知道插值算法是用来图像缩放的。（图片放大，像素点增多，如何处理放大的更多像素点上的值）

1. 引入

1.1 最邻近插值算法

思路：新位置就照搬旁边的元素。

A是原图像，B是新图像（更大的），图像就是像素值的矩阵。

B中的一个值(B${}_x$,B${}_y$)怎么求：

A${}_x$=B${}_x$（A的列数 / B的列数）
A${}_y$=B${}_y$（A的行数 / B的行数）
如果结果有小数，那就四舍五入。

用(A${}_x$,A${}_y$)的值填入(B${}_x$,B${}_y$)

1.2 双线性插值算法

思路：在两个向量上分别进行一次线性插值。

我惊了老师ppt跟本没有这东西，看不看都行，不过挺简单的也不用背。

简单说一下吧，就是上面那种方法A${}_x$，A${}_y$的结果可能是小数，那么小数部分不要四舍五入。

因为正方形总面积是1，可以作为概率比例，用每个小方块的面积*对角的点在矩阵A的值。

2. 拉格朗日插值法

拉格朗日插值，这个视频一共就四分钟，看看之后再看这本书上讲的内容。

2.1 公式

通用

这尽量不要背，还是根据上面那个视频理解。

拉格朗日插值基函数：

拉格朗日多项式：

线性插值

也是上面那个公式，只不过线性就是只有两个点(n=1)而已：

抛物线插值

三个点(n=2)啦：

看一下例5.1和例5.2，比较容易理解的。

2.2 余项

通过上面那个视频我们可以知道，只有在$x_i$处，才有$L_n(x_i)$=$f(x_i)$=$y$，其他位置，$L_n(x_i)$都只能看作我们的估计值，$L_n(x_i)$≠$f(x_i)$。

所以，插值余项$R_n(x)$=$f(x)$-$L_n(x)$表示在点x处产生的误差。

记住这个定理，其中拉格朗日和牛顿插值的余项$R_n(x)$都是这个：

3. 牛顿插值法

3.1 差商

记一下差商的计算方法：

一阶差商：

二阶：

通用：

这样，就可以求出来任意的差商了，差商计算路线如下：

但其实我们最终只用到斜线部分，其他只是用来辅助计算而已。零阶差商就是x对应的函数值。

3.2 牛顿插值

直接看最通用公式：

其中，$N_0^{}(x)$=$f(x_0)$

直接看一道例题，拉格朗日+牛顿全解决：
拉格朗日&牛顿

3.3 余项

同刚才

4.三次埃尔米特插值

这里需要会两种情况的分别两个解法，考试会对解法有要求。

首先说明，$H_3(x)$就代表三次埃尔米特插值。

4.1 齐次埃尔米特插值

齐次是什么意思呢？每一个x对应一个y，并且还一定对应一个y${}^{\prime }$(这里将这个值设为字母m)。

在三次、齐次埃尔米特插值时，只有两个x值。

构造三次埃尔米特插值$H_3(x)$，使$H(x_k)$=$y_k$,$H^{\prime }(x_k)$=$m_k$（k=0,1）

4.1.1 解法一、结合拉格朗日插值

我把这里的讲解分为三部分：

第一部分：如何构建

基于插值基函数（本章2.1），$H_3(x)$=${\alpha }_0(x)$$y_0$+${\alpha }_1(x)$$y_1$+${\beta }_0(x)$$m_0$+${\beta }_1(x)$$m_1$

还记得拉格朗日插值的那个视频吗，把插值基函数称作开关，我们现在就要用开关这个思想，${\alpha }_0(x)$、${\alpha }_1(x)$、${\beta }_0(x)$、${\beta }_1(x)$就是这个公式的四个开关，我们看公式：

可以求得，这样设计之后，$H_3(x_0)$=$y_0$，$H_3^{\prime }(x_0)$=$m_0$，$H_3(x_1)$=$y_1$，$H_3^{\prime }(x_0)$=$m_1$
结果皆大欢喜，但这是如何设计来的呢？

首先，在不求导时，$H_3(x)$=${\alpha }_0(x)$$y_0$+${\alpha }_1(x)$$y_1$+${\beta }_0(x)$$m_0$+${\beta }_1(x)$$m_1$。这里恒有β=0，那么$m_0$、$m_1$的开关就会关掉，那就只有${\alpha }_0(x)$$y_0$+${\alpha }_1(x)$$y_1$这部分，我们看到i=j时才有对应的α=1，那么就会将另一半的开关关掉，用$x_0$举例，即出现$H_3(x_0)$=${\alpha }_0(x_0)$$y_0$+${\alpha }_1(x_0)$$y_1$=1*$y_0$+0*$y_1$=$y_0$的结果。

同理，求导时，公式变为$H_3^{\prime }(x)$=${\alpha }_0^{\prime }(x)$$y_0$+${\alpha }_1^{\prime }(x)$$y_1$+${\beta }_0^{\prime }(x)$$m_0$+${\beta }_1^{\prime }(x)$$m_1$。这里同样有${\alpha }^{\prime }$恒等于0，所以只剩${\beta }_0^{\prime }(x)$$m_0$+${\beta }_1^{\prime }(x)$$m_1$这部分，还有${\beta }^{\prime }$在i=j时才=1的开关，即可得出最终结果。

第二部分：如何求解

这里也分成三部分：

（一）、二重零点

接下来有个重点，书上写的很不明确，为什么根据（5.4.1），${\alpha }_0(x_0)$必包含因子(x-x${}_1$)${}^2$，为什么说${\alpha }_0(x)$中x${}_1$时二重零点？

是这样，你看${\alpha }_0(x_1)$和${\alpha }_0^{\prime }(x_1)$是不是都=0，那一定是因为，${\alpha }_0$含有($x$-$x_1$)${}^2$这一项。因为这样，不仅在原函数$x$=$x_1$时为0，而且导数才一定会有($x$-$x_1$)这一项并且$x$=$x_1$时导数也为0。（再解释一下，($x$-$x_1$)${}^2$$f(x)$的导数为($x$-$x_1$)${}^2$$f^{\prime }(x)$+2($x$-$x_1$)*$f(x)$，能提出($x$-$x_1$)这一项）

（二）、构造式子

那么接下来就要理解这几个剩下的构造部分，先看定义：

平方那部分之前已经讲解完了，为什么会有剩下的构造，首先看${\alpha }_0$，我们看上一张图片，${\alpha }_0$需要满足四个条件：${\alpha }_0(x_1)$=0，${\alpha }_0(x_0)$=1，${\alpha }_0^{\prime }(x_1)$=0，${\alpha }_0^{\prime }(x_0)$=0

目前我们可以满足，${\alpha }_0(x_1)$=0和${\alpha }_0^{\prime }(x_1)$=0，但是如果没有后半部分，一定满足不了剩下两个条件（为什么满足可以看后面的求导，现在不用知道）。

同理，β需要有${\beta }_i(x_i)$=0，所以${\beta }_0$中要有($x$-$x_0$)这一项。

简单记忆一下，就是每个式子都要是三次项。

（三）、求解

看这个表吧，现在每个里面条件都用了三次了，还剩一个条件没用的(=1)，代入到式子中，就可以求出未知系数，最终结果是这样：

第三部分：插值余项

已经求完多项式了，但是还要算一下插值余项。

看一下得了。

4.2.2 解法二、结合牛顿插值

这个差商表和之前的很像，注意一下这一点就可：$z_1$相当于$x+▲x$，利用导数定义，得到：

$z_3$同理。

然后套这个公式就可以了（这个公式还挺好记忆的）：

插值余项
$R_3(x)$=$f[x,z_0,z_1,z_2,z_3]$$(x-x_0{)}^2$$(x-x_1{)}^2$

4.2非齐次埃尔米特插值

能截图就不打字好吧，三个x，三个y，只有一个m。

重大发现：ppt上没讲非齐次的解法一，那我必然是不写的，理解上我已经在齐次的解法一上讲的差不多了，想看可以看。

4.2.1解法二、结合牛顿插值

新的差商表（看一下哪和之前不一样了）

新的方程

插值余项（和之前的对比一下更好记哦）：
$R_3(x)$=$f[x,z_0,z_1,z_2,z_3]$$(x-x_0)$$(x-x_1{)}^2$$(x-x_2)$

引言

在学习线性回归模型的时候就会遇到基函数，可能我们会遇到多项式基函数、高斯基函数、sigmoid基函数，当然在高等数学和信号系统中还经常会碰到傅里叶基。有时候，不禁要问，这些基函数为什么这么设计？这些基函数的作用是什么？
后来发现基函数是核方法和字典训练的基础，于是乎，我逐渐有了一些例如特征转换和映射、字典元素的概念。不过还是对基函数与函数空间的关系、基函数的深层认识模棱两可。我希望能通过这篇文章，来探究这些东西。

基函数

在数学中，基函数是函数空间一组特殊的基的元素。对于函数空间中的连续函数都可以表示成一系列基函数的线性组合，就像是在向量空间中每个向量都可以表示成基向量的线性组合一样。
在数值分析和近似理论中，基函数也称为混合函数（blending function），因为其在插值（interpolation）的应用
。
举例：
多项式基：{1，t, t2}是实系数二次多项式集合的基，每一个形如a+bt+ct2的二次多项式都可以写成由基函数1、t、t^2组成的线性组合。另外，{(t-1)(t-2)/2, -t(t-2), t(t-1)/2}是二次多项式的另一组基，称为拉格朗日基（Lagrange basis）。
傅里叶基：余弦函数构成了平方可积函数的（正交）Schauder基。

说说径向基函数

径向基函数有个类似高斯函数的形状，我们可以看到下面的图像，不同的系数，有不同的函数图像：

下面的三组图像是三个径向基函数在不同的权重的线性组合下的曲线形态：

我们知道，线性回归模型可以看做是目标函数加入了高斯噪声模型，其概率模型形式为：

<a href="http://private.codecogs.com/eqnedit.php?latex=p(t|X,\delta2)=\frac{1}{(2\pi){N/2}|K|{1/2}}exp(-\frac{1}{2}tTK^{-1}t)" target="_blank">

p(t|X,\delta^2)=\frac{1}{(2\pi)^{N/2}|K|^{1/2}}exp(-\frac{1}{2}t^TK^{-1}t)

</a>
对于多维高斯模型的协方差矩阵，可以看做是数据构成的矩阵再加入一个噪声的方阵，当使用基函数的时候，协方差矩阵就变成了核矩阵再加上噪声的方阵。

<a href="http://private.codecogs.com/eqnedit.php?latex=K=\alpha&space;XXT&plus;\delta2I&space;\Rightarrow&space;K=\alpha&space;\Phi&space;\PhiT&space;&plus;&space;\delta2I" target="_blank">

K=\alpha XX^T+\delta^2I \Rightarrow K=\alpha \Phi \Phi^T + \delta^2I

</a>
下面是用多项式基函数和径向基函数分别构成的特征变换矩阵：

<a href="http://private.codecogs.com/eqnedit.php?latex=\Phi&space;=&space;\begin{bmatrix}&space;1&space;&&space;x_1&space;&&space;x_12&space;\&space;1&space;&&space;x_2&space;&&space;x_22&space;\&space;:&space;&&space;:&space;&&space;:&space;\&space;1&space;&&space;x_n&space;&&space;x_n^2&space;\end{bmatrix}" target="_blank">

\Phi = \begin{bmatrix} 1 & x_1 & x_1^2 \ 1 & x_2 & x_2^2 \ : & : & : \ 1 & x_n & x_n^2 \end{bmatrix}

</a>

<a href="http://private.codecogs.com/eqnedit.php?latex=\Phi&space;=&space;\begin{bmatrix}&space;exp(-2(x_1-1)2)&space;&&space;...&space;\&space;exp(-2(x_2-1)2)&space;&&space;...&space;\&space;:&space;&&space;:&space;\&space;exp(-2(x_n-1)^2)&space;&&space;...&space;\end{bmatrix}" target="_blank">

\Phi = \begin{bmatrix} exp(-2(x_1-1)^2) & ... \ exp(-2(x_2-1)^2) & ... \ : & : \ exp(-2(x_n-1)^2) & ... \end{bmatrix}

</a>

由于径向基函数是一种局部基函数(localized basis function)，那么距离基函数中心比较远的区域，数据项对方差的贡献将趋于零，只剩下噪声的贡献。因此，对于基函数所在的区域之外的区域进行外插的时候，模型对于它做出的预测会变得相当确定，这不是我们想要的结果，可以用高斯过程这种贝叶斯回归方法来避免，这也就引入了径向基核函数这种无限维的特征转换。
下面的特征变换是由三个不同参数的径向基函数组成的，这里看到协方差矩阵的图像中对角线区域，蓝色部分是由噪声贡献的，而红色区域是由基函数贡献的。

利用这种协方差矩阵，构成的多维高斯分布的抽样结果用图形给出：

径向基函数与插值

径向基函数可以看作是一个高维空间中的曲面拟合（逼近）问题，学习是为了在多维空间中寻找一个能够最佳匹配训练数据的曲面，然后来一批新的数据，用刚才训练的那个曲面来处理（比如分类、回归）。径向基函数的本质思想是反向传播学习算法应用递归技术，这种技术在统计学中被称为随机逼近。径向基函数就是在神经网络的隐单元里提供了提供了一个函数集，该函数集在输入模式（向量）扩展至隐空间时，为其构建了一个任意的“基”。这个函数集中的函数就被称为径向基函数。

径向基函数是一种精确插值器，其方法方法不同于全局和局部多项式插值器，它们都不是精确插值器（不要求表面穿过测量点）。径向基函数还可预测大于最大测量值和小于最小测量值的值。
径向基函数用于根据大量数据点生成平滑表面。这些函数可为平缓变化的表面生成很好的结果。但在表面值在短距离内出现剧烈变化和/或怀疑样本值很可能有测量误差或不确定性时，这些方法不适用。

径向基核函数

我们先看一下为什么说径向基核函数（高斯核函数）是无限维的特征转换吧。
将径向基核函数做泰勒展开形式如下：

<a href="http://private.codecogs.com/eqnedit.php?latex=k(x,x')=exp(-(x-x')2)=exp(-x2)exp(-x'2)exp(2xx')&space;=exp(-x2)exp(-x'2)[\sum_{i=0}{\infty&space;}\frac{(2xx')i}{i!}]&space;=\sum_{i=0}{\infty&space;}[exp(-x2)exp(-x'2)\sqrt{\frac{2i}{i!}}\sqrt{\frac{2i}{i!}}xix'i]&space;=\Phi(x)^T\Phi(x')" target="_blank">

k(x,x')=exp(-(x-x')^2)=exp(-x^2)exp(-x'^2)exp(2xx') =exp(-x^2)exp(-x'^2)[\sum_{i=0}^{\infty }\frac{(2xx')^i}{i!}] =\sum_{i=0}^{\infty }[exp(-x^2)exp(-x'^2)\sqrt{\frac{2^i}{i!}}\sqrt{\frac{2^i}{i!}}x^ix'^i] =\Phi(x)^T\Phi(x')

</a>
其对应的无限维的特征转换为：

<a href="http://private.codecogs.com/eqnedit.php?latex=\Phi(x)=exp(-x2)(1,\sqrt{\frac{2}{1!}}x,\sqrt{\frac{22}{2!}}x^2,...)" target="_blank">

\Phi(x)=exp(-x^2)(1,\sqrt{\frac{2}{1!}}x,\sqrt{\frac{2^2}{2!}}x^2,...)

</a>

我们看到了径向基核函数，是xi和xj数据之间欧氏距离的函数。
下面是核矩阵和抽样的图像：

从上图看到，径向基核函数以每个数据点为中心进行建模，在有数据的区域贡献随机变量的方差，而不再像用单一的径向基函数只在函数中心保有对方差的贡献。上图同样说明，相邻的数据有强相关性，而相离的数据没有什么相关性，即红色区域和蓝色区域说明的情况。
这是高斯过程模型的基础，相比贝叶斯线性模型而言，高斯过程不再对模型参数进行建模（通过对参数分布进行采样，再进行不同基函数模型的组合），而是直接对数据进行相应操作。

函数空间浅显解释

空间是数学抽象出来描述具有某些特殊性质和结构的集合。学过线性代数的人都知道线性空间，向量是线性空间的基本元素。空间中还有一个很重要的概念是基。为什么要有基？是为了更好的描述空间。比如说三维空间，这个空间里面的元素的个数是不可数的（也就是和自然数集找不到一一对应的关系），所以一一列出来是不可能的。数学家想出了一个很好的办法，用任意三个不共面向量的线性组合来表示这个空间中的任意一个元素。
有了上面的概念，我们可以理解函数空间就是满足一定性质和结构的函数集合，组成这个空间的元素都是满足一定条件的函数。所以，这个函数空间里面的所有元素都是函数，而且这个空间其实是无穷维的，基有无穷多个。
因为我是通信专业的，现在用傅里叶变换来理解一下函数空间。傅里叶变换就是给出了一组基，要求求出利用每个基线性组合成这一信号（函数）的组合系数，或者说是在这组基下的坐标。傅里叶变换的美妙之处就在于这组基取得实在是太好了。为什么呢？首先他们是正交的，更主要的是它还和自然界的情况有着微妙的联系。自然界中的水波、音波、电磁波等等，如果用数学抽象，显然是三角函数。在振荡电路、模拟通信等等领域中，使用三角函数形式的波形的好处也是非常多的。可以看到，傅里叶变换在一维信号处理领域获得了很大的成功。需要指出的是，傅里叶变换在二维信号处理领域，比如说在图像处理领域的缺点就很多了。直观上，图像的周期现象似乎不是那么明显。而且从一维情况转换到二维情况，复杂度成倍增加。

作者：JasonDing
转自链接：https://www.jianshu.com/p/5cc427f0df33