函数插值 | 彩潭有鲤的札记

type

status

date

slug

summary

Lagrange多项式法

Lagrange多项式法使用一个次多项式来拟合上述的个点，且可以得出唯一的结果

证明：

对于点集，找到一次多项式使得等价于方程组：

展开之，可使其变为一个系数矩阵是范德蒙矩阵的关于多项式系数向量的线性方程组，且范德蒙矩阵在互不相同时满秩，因此多项式系数向量存在且唯一。

Lagrange多项式的求解

可以直接通过列方程组求解，但涉及到次方运算，会得到一个范氏矩阵，而它往往是病态的，故考虑使用其它的方法求解

事实上凡是要解方程求Lagrange多项式的，都会面临病态的问题，因此从方程形式上来考察它。

Lagrange多项式可以认为是一组线性无关的基线性组合而成的，因此可以构造另外一组与其同构的基来解决这一问题，构造这样的一组基底：

这组基满足一个特殊的性质：对于点集中的若干离散，当且仅当时为1，否则为0

故可以构造插值函数如下：

容易得知上述的函数满足Lagrange插值的基本假设

误差估计

设置有若干节点是上的个互异节点，若待拟合函数在上阶可导，即，若用Lagrange多项式拟合，则其插值余项（截断误差）可以表述为：

其中，

使用微分中值定理即可证明：

由定义，，再由Lagrange多项式的基本假设，有

故可以等价地将转写为，其中，是某未知的多项式。

构造辅助函数：

观察到上述的函数有个零点：，事先约定这些零点都在的解析域上（否则Lagrange多项式将失去意义）

对自变量反复应用罗尔中值定理次，则存在某一点，使得：

故得到，

而，是一个次多项式，在次求导后变为0，故

若记，则Lagrange插值法的截断误差，这体现了对误差的一种控制.

Newton插值法

基于上面的Lagrange插值法具有一明显的弊端：一旦点集发生改变，各个基均需要进行修改，故我们希望找到另外一组基，使得即使点集发生了增减，也只需简单地增加或删除一项即可

差商

阶差商：

差商有以下性质：

阶差商可表示为的线性组合：

差商有对称性

Newton插值

最初，点集中只有，因此给出插值式来拟合之

随后加入了点，此时插值公式需要额外满足，根据Newton插值的思想，通过为附加一项来达成此目的：

故一定满足：

故可以提出满足上述条件的较为简单形式：，代入解出

此时插值公式变为

继续加入点，此时插值公式需要额外满足，故仍使用上述的方式：

同理，设置，解出

这个形式不够简洁，经过简单的数学变换之后（均差(差商)的轮换对称性），可以化为

它有着某种对称性：定义，则可以转写为：

这样的形式仍符合着某种更"高级"的对称性，故将记为，表示先求"较为低级的"两个和，再将其作差，与外层的两个值之差相除。这样，递归地提出了均差(差商)的概念：

，" "可以为空且可以相同(即本式支持三个及以上项目)

容易证明，均差具有轮换对称性，即只要参数的组合一致，参数的排列与均差的值无关.

故Newton插值法可以直观地表述为：

分析地描述为：

Newton插值的截断误差

在非节点的任意点上，Newton插值的截断误差可以表述为：

而不可直接求知，因此采用一巧妙的解法：以点为第个节点构造一新的Newton插值式，而此式可以精确反映的值，则易知其差值：

即为Newton插值的截断误差。而对于一个点系的插值式是唯一的，因此结合Lagrange插值法可以导出：

其中在点集连成的开区域内部，即

注：实际上，用Newton插值法和用Lagrange插值法得到的同次插值多项式是完全相同的，因此截断误差也是完全一致的，这是因为插值多项式具有唯一性。

Lagrange插值与Newton插值的对比

对于Lagrange插值公式：

一点零次插值：

两点一次插值：

三点两次插值：

以此类推，可以得到：

其中：

显然，有：

因此，二者的插值余项也完全相同，即：

等距均差和等距节点的Newton插值

如果上述过程中的节点都是等距的，即，则均差可以改写为如下的形式：

其中被称为阶差分，根据差分与均差在内容上的一致性，可以递归地描述差分：

即可重新以差分来改写节点等距情况下的Newton插值式：

直观地表述为

在某些情况，会使用类似于等差数列的形式表示：，这时可以使用作自变量，将上述的式子再度改写：

直观地表述为

这一式子被称为向前插值公式。代入求值时应注意自变量是，若输入的是则需相应的线性转化.

同理，若将表示为，也可以得出类似的结果：

直观地表述为

前述的两种插值法，都构造了一个函数，使得至少在各个节点处与潜在的函数同值。但如果想要通过插值函数来刻画更加深刻的性质，如一阶导数，那么前述的两种插值方法将难以胜任。

Hermite插值

试图找到某插值函数使得在个点的点集上，有：

直观地，在中蕴含了更多的信息，这样一来就可能需要更多的自由度来承载这些信息，当然只有个约束条件，因此天然地，Hermite插值不可以也不会超过次

基函数构造法

与在Lagrange插值法中作的工作相似，我们同样希望找到一组基，使得它满足这一问题中的要求：

首先找到某一类函数，使得对于样本点集中的点有：

同时满足：它的一阶导数在样本点集上恒为0：

这样即可使用来控制插值函数的函数值而不影响其导数.

同样地，试图找到，使得对于样本点集中的点有：

同时，它的原值应当在样本点集上恒为0：

这样即可使用来控制插值函数的一阶导数而不影响其原值.

幸运的是，数学家们创造性地发现了这组基的形式：

其中，是关于的Lagrange基：

因此，在该方法中，每一个点-导数三元组生成一项

由此可给出Hermite插值表达式：

Hermite插值法拥有误差表达式

这样的“函数值-导数”分别控制的方法有着更广阔的应用空间，如给出点集中部分拥有导函数值而其余没有，而这种形式的问题需要构造额外的基函数(如使用原基函数则待定参数数量过多)，而构造这一基函数的过程需要较强的分析要求，故不建议使用基函数构造法.

对于上述这种“不完全”的情况，误差表达式会有所变化，但总得来说，如果给出了组原值条件，其中有组限制了导数值(不妨设它们就是第个)，则误差可以表示为

待定系数法

这种方法直接将显式地假设出来，再代入点集解方程组。严格地来讲这种算法不能称之为方法，但在数据量较小时很好用

降阶法

而面对稍多的数据时，待定系数法就不那么好用了，因此我们试图通过某种方式来减少需要处理的自由度数：

先通过前述的插值法求出仅在原函数值上提供保证的插值函数：

明显地，Hermite插值函数与存在如下的关系：

由于是阶多项式，是阶多项式，故是阶多项式，故是阶多项式.

此时再利用对待定系数直球求解即可

样条插值法

样条

对于一水平弹性木条，在若干点处施加垂直于其的外力，产生弯矩，由Euler–Bernoulli梁方程，每两点之间的弯矩与材料杨氏模量、产生的惯性矩与产生曲线的曲率有如下关系：

一般的梁难以发生大的弯曲，故接近于0，有：

而每两点之间没有额外的力，故产生的弯矩是线性的，故是一分段一次函数，故可以得知是一拥有连续二阶导数的分段三次函数.

样条插值

因此设置第点和第点之间的函数表达式是，总共有段曲线，产生个自由度，接下来数数我们有什么条件：

插值条件，在时，个

插值条件中有个被两段曲线共用，属自由度的冗余，消除个自由度(称为函数值连续条件)

一阶导数连续，在个共用点上，个

二阶导数连续，在个共用点上，个

如此，拥有个条件，明显不能解决个自由度的问题.

可以通过某些人为的限定来为其附加2个限定条件，而最佳的方式就是将其附加在未被连续性约束的两个边界点上.

常用的方式有：

令，此时与工程中使用的样条之情况(边界弯矩为0)符合，称为自然三次样条

用自然三次样条为例，指出如何求解样条：

首先假定任意第段函数均有参数列表，我们采取较为巧妙的"自底向上"方式以降低计算难度：

在每一段上，的二阶导数均是线性函数，易知在每一段上：

为简化表达，约定新符号，使用之前在“力学背景”中提到的弯矩来代表：

为利用函数值条件，对上式执行两次积分，并适当调整积分常数的位置，得到：

代入条件，解出上述积分常数：

有了这一方程，就只需求解出各个弯矩，即可得解.

还有一个未用的条件，即个导数的连续性条件：

对上述方程左右求导并令，有

上述方程被称为三弯矩方程，其中。令它是自然样条，即，得到一方程组（为简化表达，记，）：

使用前述的"追赶法"解决之，即可得到样条插值函数.