数值方法/插值

插值

多项式插值

插值是一种将离散数据点扩展到函数的方法。如果给定的数据点在$\mathbf {R} ^{2}$ 中，则多项式插值很常见。多项式插值背后的主要思想是，给定n+1个离散数据点，存在一个唯一的n阶多项式来拟合这些数据点。一般来说，低阶多项式是不可能的，高阶多项式是不唯一的。如果多项式$p(x)$ 定义为

$p(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}$

则可以用以下系统求解未知系数

${\begin{bmatrix}x_{0}^{n}&x_{0}^{n-1}&x_{0}^{n-2}&\ldots &x_{0}&1\\x_{1}^{n}&x_{1}^{n-1}&x_{1}^{n-2}&\ldots &x_{1}&1\\\vdots &\vdots &\vdots &&\vdots &\vdots \\x_{n}^{n}&x_{n}^{n-1}&x_{n}^{n-2}&\ldots &x_{n}&1\end{bmatrix}}{\begin{bmatrix}a_{n}\\a_{n-1}\\\vdots \\a_{0}\end{bmatrix}}={\begin{bmatrix}y_{0}\\y_{1}\\\vdots \\y_{n}\end{bmatrix}}.$

其中$x_{0}\ldots x_{n}$ 是给定的数据点。系统中的矩阵称为范德蒙矩阵。假设所有数据点都是不同的，则范德蒙矩阵是非奇异的，因此系统可以唯一地求解。

如果要插值的数据点的数量变大，多项式的次数也会变大，这可能会导致数据点之间出现振荡，并增加误差。对于大量数据点，建议使用其他方法。

径向基函数

科学和工程中的一个常见问题是多元插值一个函数f，它的值仅在有限的点集上已知。因此，令$\Omega \subset \mathbf {R} ^{d}$ 是一个开放的有限域。给定一组不同的点X和实数，任务是构造一个函数$s:\mathbf {R} ^{d}\rightarrow \mathbf {R}$，满足插值条件

$s(x_{i})=f_{i}$

在过去的几十年里，径向基函数插值方法在空间中X上的点分布不规则的问题中越来越受欢迎。在基本形式中，径向基函数插值选择一个固定的函数 $\phi :\mathbf {R_{+}} \rightarrow \mathbf {R}$ 并通过 $\phi$ 定义一个插值函数，其中系数 $c_{i}$ 是实数，对于 $\|\cdot \|$ 通常选择欧几里德范数，而 $\phi$ 是一个径向基函数。

我们可以看到，近似函数s 是径向对称函数的线性组合，每个函数都以一个确定的点 $x_{i}$ 为中心。点 $x_{i}$ 通常被称为 RBF 插值的中心 或配置点。这种方法可以追溯到 Hardy，他早在 1971 年就使用多二次 RBF 从一组分散的测量数据中重建地理表面。还要注意，中心 $x_{i}$ 可以位于域中的任意点，不需要网格。对于某些 RBF，指数收敛已经得到证明。径向基函数已成功应用于各种问题，例如计算机图形学、神经网络、通过配置方法求解微分方程以及许多其他问题。

其他流行的 $\phi$ 选择包括高斯函数和所谓的薄板样条，由 Duchon 在 1970 年代发明。薄板样条是通过求解变分问题得到的。薄板样条的优点是它们的条件数在缩放下保持不变。另一类函数是 Wendland 的紧支撑 RBF，它们与众不同，因为它们会导致稀疏插值矩阵，因此可以有效地求解生成的线性系统。然而，问题的条件数会随着中心的数量而恶化。当使用具有全局支持的 RBF 进行插值时，矩阵A 通常会随着中心的增加而变得病态。高斯函数、多二次函数和反多二次函数是无限平滑的，并涉及一个尺度或形状参数， $\epsilon$ > 0。\ref{fig:var-eps2} 显示了具有不同 $\epsilon$ 值的高斯 RBF。减小 $\epsilon$ 往往会使基函数变平。对于给定的函数，近似的质量可能很大程度上取决于此参数。特别地，增加 $\epsilon$ 会改善条件数（缩放后点的分离距离 $q_{X}:=min\,\,\Vert x_{j}-x_{k}\Vert$ 会增加）。

求解插值问题会导致以下线性方程组

$Ac=f$

其中 $a_{ij}=\phi (\|x_{i}-x_{j}\|),c=(c_{j})_{j=1,...,N},f=(f_{j})_{j=1,...,N}.$ 。因为只有点之间的距离出现在 *A* 中，所以解决该系统的努力与空间维度无关，这在更高维度插值时尤其重要。Franke 在 1982 年提出一个问题，即矩阵 *A* 是否非奇异，因此对于任何 *f* 的选择，都保证存在唯一的插值函数。几年后，Micchelli 和 Madych 及 Nelson 的结果独立证明了这一猜想对于许多有用的 RBF 都是成立的。唯一的条件是至少有两个中心，并且所有中心都是不同的。薄板样条是一个例外，对于非平凡的点分布，矩阵 *A* 可能为奇异。例如，如果点 $x_{2},...,x_{n}$ 分布在中心 $x_{1}$ 周围的单位球面上，那么第一行和第一列将包含零。解决这个问题的方法是将一个 *m* 度多项式 *p* ($m\geq 1$) 添加到插值函数中，这样插值函数就变成了

$s(x)=\sum _{j=1}^{N}c_{i}\phi (\|x-x_{j}\|)+p(x)$

并要求节点是 *不溶解的* ($\Pi _{d}^{m}$)，这意味着每个多项式 $p\in \Pi _{d}^{m}$ 都由它在 *X* 上的值决定。$p\in \Pi _{d}^{m}$ 表示 *n* 个变量中所有多项式到 *m* 次的集合，而 $p_{k}$ 是此空间的标准基多项式。如果所有点都不同，则点集对于 $\Pi _{0}^{d}$ 是不溶解的，如果并非所有点都排列在一条线上，则对于 $\Pi _{1}^{d}$ 是不溶解的。

现在的插值条件是

$\sum _{j=1}^{N}c_{j}\phi (\Vert x_{i}-x_{j}\Vert )+\sum _{j=1}^{l}d_{j}p_{j}(x_{i})=f_{i},\qquad i=1,...,N$

由于插值条件导致在N + l个未知数中存在N个方程，因此该系统是欠定的。 因此，施加额外的边条件，这些条件代表了多项式再生的性质。 这意味着，如果数据来自多项式 $p\in {\mathcal {P}}_{m}^{d}$，即$f_{i}=p(x_{i})$，那么插值函数s必须与p一致。 这些条件相当于

$\sum _{j=1}^{l}d_{j}p_{j}(x_{i})=0,\quad 1\leq i\leq l.$

为了找到c和d，我们需要求解线性方程组

$A\,c+P\,d=f,\qquad P^{T}c=0,$

其中$P_{ij}=p_{j}(x_{i})$，A的定义如上所述。 这些方程可以总结为

如果函数 $\phi$ 属于以下函数类别，则该系统有唯一的解。

定义 连续函数 $\Phi :\mathbf {R} ^{d}\rightarrow \mathbf {R}$ 被称为条件正定m阶，简称为 $\Phi \in CPDm$，如果对于 每个不同的点集 $X=\{x_{1},...,x_{N}\}\subset \Omega$ 和对于每个复数值集 $\{c_{1},...,c_{N}\}$，其中

$P\,\,c=\sum _{j=1}^{N}c_{j}p(x_{j})=0\qquad for\,all\,p\in \Pi _{m}^{d}$

二次形式

$c\,\,A\,\,c^{T}=\sum _{j=1}^{N}\sum _{k=1}^{N}c_{j}c_{k}\Phi (x_{j}-x_{k})\geq 0$

为正数。如果此外，$c\,\,A\,\,c^{T}=0$ 意味着 $c=0$，那么 $\phi$ 被称为严格的 m 阶 CPD。对于 $m=0$，$\Phi$ 被称为正定。

如果径向基函数 $\phi (\|x-y\|)=\Phi (x-y)$ 被称为条件正定，如果相应的多元函数 $\Phi$ 是条件正定的。

如果一个函数是正定的，那么相应的插值矩阵也是正定的。TPS 和 MQ 是条件正定函数，Gau、IMQ 和 Wen 是正定函数。

除了证明问题是适定的，还需要证明收敛性。然而，对于大多数 RBF，收敛性只在无限方形网格上的全局插值中得到保证。对于薄板样条函数，局部插值的收敛性证明也是已知的。

广义厄米特插值问题

插值问题也可以用点评估表示，即对函数 *f* 作用狄拉克 δ 函数。如果 ${\mathcal {S}}$ 是一个向量空间，那么对应于 *x* 的狄拉克 δ 函数 $\delta _{x}$ 定义为

$\delta _{x}(f)=f(x),\quad f\in {\mathcal {S}}$

数据通过以下方式生成

$f_{j}=\int f(x)\delta (x-x_{j})dx$

如前所述，设 $\{x_{1},...,x_{N}\}$ 为中心。更一般地说，数据可以由任何一组线性泛函 $\lambda _{1},...,\lambda _{N}$ 作用于某个函数 *f* 生成。为了避免冗余数据，这些分布需要相互独立。 $\lambda _{i}$ 不限于点评估，可以是任意线性泛函，包括微分和差分算子。这个问题包括 Hermite 函数和 ${\mathcal {E}}'$，即所有紧支撑分布的集合。对于一个分布 $\lambda \in {\mathcal {E}}'$，对应一个线性泛函，它通过分布的卷积作用于 $f\in {\mathcal {E}}$。它可以写成

$(\lambda ,f)=\int (\lambda *f)(x)dx=\int f(y)\lambda (x-y)dy$

现在，任务是在给定数据的情况下进行插值，$f_{i}=(\lambda _{i},f)$

使得 $s=\Phi *\lambda +p$ 满足

$(\lambda _{i},s)=f_{i},\quad for\,\,i=1,...,N$

这里，插值函数的形式为

$s(x)=\sum _{j=1}^{N}c_{j}\lambda _{j}^{y}\phi (\Vert x-y\Vert )+p(x)$

其中，$c_{j}$ 是适当的实系数，而 $\lambda _{j}^{y}$ 表示 $\lambda$ 作用于 $\phi$，将后者视为|y的函数。*

$\sum _{j=1}^{N}\lambda _{j}(p)\phi _{j}(x)=\lambda (p),\quad for\,all\,p\in {\mathcal {P}}_{m}^{d}$

插值矩阵 $A=(a)_{ij}$ 在 \ref{eq:rbf-lgs} 中的条目现在由以下公式给出：

$a_{ij}=\lambda ^{x}\lambda ^{y}\phi (\Vert x-y\Vert )$

如果线性泛函的数量等于中心的數量，并且 $\phi$ 属于条件正定函数类，则存在唯一解。