链接
发表时间:1981年9月1日(Published 1 September 1981)
论文导读
这篇论文《Surfaces Generated by Moving Least Squares Methods》由P. Lancaster和K. Salkauskas撰写,发表于1981年,主要研究了 移动最小二乘法(Moving Least Squares, MLS) 在散乱数据平滑和插值中的应用,特别是在生成曲面方面的理论和方法。如果你觉得难以理解,这很正常,因为论文涉及较多数学理论和复杂的数学推导。以下是一些帮助你理解这篇论文的建议,以及对论文内容的简化解读:
1. 理解论文的主要内容
论文的核心目标
- 问题背景:在计算机视觉和三维重建中,我们经常需要从散乱的数据点(如三维点云)中重建出光滑的曲面。传统的插值和逼近方法在处理不规则分布的数据时效果不佳。
- 研究目标:提出一种基于移动最小二乘法的曲面生成方法,能够处理散乱数据,并生成光滑且具有特定可微性的曲面。
主要贡献
- 提出了移动最小二乘法(MLS)的数学框架,证明了其生成的插值函数的光滑性。
- 展示了MLS方法可以被视为一种投影方法,并讨论了其与有限元方法的结合。
- 提供了理论分析和数值实验,验证了方法的有效性。
2. 简化解读论文的关键部分
第1节:引言
- 核心观点:传统的插值方法(如多项式插值)在处理不规则分布的数据时效果不佳。MLS方法通过引入权重函数,能够在局部区域内进行最小二乘拟合,从而生成光滑的曲面。
- 关键问题:如何确保生成的曲面在数据点处插值,并且具有足够的光滑性?
第2节:非插值型移动最小二乘法
- 核心内容:介绍了MLS方法的基本原理。在每个点 $ z $ 处,通过最小化加权的局部误差来找到最佳的局部近似函数 $ L_f(z) $。这些局部近似函数组合起来形成全局近似函数 $ Gf(z) $。
- 关键公式:
- $ L_f(z) = \sum_{i=1}^n a_i(z) b_i(z) $:局部近似函数。
- $ Gf(z) = L_f(z) $:全局近似函数。
- 权重函数 $ W(z) $ 用于控制每个数据点对局部拟合的贡献。
第3节:局部近似的另一种表示
- 核心内容:通过正交化方法,将局部近似函数 $ L_f(z) $ 表示为一个基函数的线性组合,这有助于后续的理论分析。
- 关键结论:这种表示方法使得局部近似函数的计算更加高效,并且能够更好地分析其光滑性。
第4节:插值型移动最小二乘法
-
核心内容:通过引入权重函数的奇异性(如 $ w(z) = z - z_k ^{-a} $),确保生成的曲面在数据点处插值。 - 关键结论:生成的插值函数 $ Gf(z) $ 具有 $ C^m $ 的光滑性,其中 $ m $ 由基函数和权重函数的性质决定。
第5节:插值型移动最小二乘法作为一种投影方法
- 核心内容:证明了插值型MLS方法可以被视为从连续函数空间到光滑函数空间的投影算子 $ G $。
- 关键结论:投影算子 $ G $ 具有投影性质 $ G^2 = G $,并且生成的曲面在数据点处插值。
第6节:相关投影方法
- 核心内容:提出了一种更高效的计算方法,通过在数据点处求解 $ n-1 $ 个方程来生成插值曲面。
- 关键结论:这种方法在计算上更高效,但需要存储额外的数组。
第7节:权重函数的选择
- 核心内容:讨论了权重函数的选择对计算结果的影响,包括截断权重函数和奇异权重函数。
- 关键结论:权重函数的选择对生成的曲面的光滑性和计算效率有重要影响。
第8节:渐近行为
-
核心内容:分析了当 $ z $ 趋向于无穷大时,插值函数 $ Gf(z) $ 和 $ Pf(z) $ 的行为。 - 关键结论:如果使用多项式基函数,生成的曲面在数据点的凸包外可能会表现出多项式的不良行为。
第9节:复合方法
- 核心内容:讨论了将MLS方法与有限元方法结合的复合方法,以提高计算效率和曲面的光滑性。
- 关键结论:复合方法可以有效地生成光滑的曲面,但需要注意插值性质的保持。
3. 阅读建议
逐步阅读
- 先读引言和结论:了解论文的整体目标和主要贡献。
- 重点阅读关键章节:如第4节和第5节,这些部分包含了核心的理论分析和结论。
- 跳过复杂的数学推导:如果数学推导部分难以理解,可以先跳过,重点关注结果和结论。
结合实际例子
- 查看论文中的例子:如第5节和第9节中的数值实验,这些例子可以帮助你直观地理解方法的效果。
- 尝试实现简单的例子:如果可能,尝试用编程语言(如Python)实现论文中的简单例子,这有助于加深理解。
查阅相关资料
- 了解背景知识:如果对移动最小二乘法或相关数学概念不熟悉,可以查阅相关的教材或综述文章。
- 参考引用文献:论文中引用了许多相关工作,这些文献可能对你理解论文内容有所帮助。
4. 总结
这篇论文虽然数学理论较多,但其核心思想是通过移动最小二乘法生成光滑的曲面。如果你的研究涉及三维重建或曲面拟合,理解这篇论文将对你有很大帮助。希望上述解读和建议能帮助你更好地理解论文内容!
详细讲解
这篇论文《Surfaces Generated by Moving Least Squares Methods》由P. Lancaster和K. Salkauskas撰写,发表于1981年。论文主要研究了移动最小二乘法(MLS)在散乱数据插值和曲面生成中的应用。以下是对论文整体结构的详细分析,以及每一段落的主要内容和结论。
论文结构分析
1. 摘要(Abstract)
- 内容:简要介绍了移动最小二乘法(MLS)在散乱数据平滑和插值中的应用,特别强调了插值函数的光滑性分析和MLS过程作为投影方法的描述。
- 结论:论文提出了关于插值函数光滑性的定理,并通过一元和二元问题的例子进行了说明。
2. 引言(Introduction)
- 内容:讨论了多变量函数插值和逼近的现状,指出对于不规则分布的数据,现有的方法(如有限元方法)存在局限性。引出了移动最小二乘法(MLS)作为一种新的方法,并介绍了其在插值和光滑性方面的优势。
- 结论:MLS方法能够处理不规则分布的数据,并生成光滑的插值曲面。
3. 非插值型移动最小二乘法(Noninterpolating Moving Least Squares Methods)
- 内容:介绍了MLS方法的基本原理,包括局部近似函数$L_f$和全局近似函数$Gf$的定义。讨论了如何通过最小二乘法在每个点处找到最佳局部近似。
- 结论:$Gf$是一个全局近似函数,其光滑性取决于基函数和权重函数的选择。
4. 插值型移动最小二乘法(Interpolating Moving Least Squares Methods)
- 内容:通过引入权重函数的奇异性,确保$Gf$在数据点处插值。讨论了权重函数的选择对插值函数光滑性的影响。
- 结论:通过适当选择权重函数,$Gf$可以插值数据点,并且保持$C^m$光滑性。
5. 插值型移动最小二乘法作为一种投影方法(Interpolating Moving Least Squares as a Projection Method)
- 内容:证明了MLS方法可以被视为从连续函数空间到光滑函数空间的投影算子$G$。讨论了投影算子的性质,包括其插值性和光滑性。
- 结论:$G$是一个投影算子,将函数映射到一个$N$维光滑函数空间。
6. 一种相关的投影方法(A Related Projection Method)
- 内容:提出了一种更高效的投影方法$P$,通过在数据点处解$n-1$个方程来生成插值曲面。讨论了$P$的性质及其与$G$的关系。
- 结论:$P$是一个投影算子,与$G$具有类似的性质,但在计算上更高效。
7. 权重函数的选择(Choice of Weight Functions)
- 内容:讨论了权重函数的选择对计算结果的影响,包括截断权重函数和奇异权重函数。分析了权重函数的可微性对插值函数光滑性的影响。
- 结论:权重函数的选择对插值函数的光滑性和计算效率有重要影响。
8. 渐近行为(Asymptotic Behavior)
-
内容:分析了当$ z \to \infty$时,插值函数$Gf$和$Pf$的行为。讨论了多项式基函数在凸包外的外推行为。 - 结论:如果使用多项式基,外推可能会表现出多项式的不良行为。
9. 复合方法(Composite Methods)
- 内容:讨论了将MLS方法与有限元方法结合的复合方法,以提高计算效率和曲面的光滑性。分析了复合方法的插值性质。
- 结论:复合方法可以有效地生成光滑的曲面,但需要注意插值性质的保持。
10. 数值实验(Numerical Examples)
- 内容:通过一元和二元问题的例子,展示了MLS方法和复合方法的效果。讨论了不同参数选择对结果的影响。
- 结论:数值实验验证了MLS方法的有效性,特别是在处理不规则分布的数据时。
每一段落的主要内容和结论
引言部分
- 第一段:讨论了多变量函数插值和逼近的现状,指出现有方法在处理不规则分布数据时的局限性。
- 结论:需要一种新的方法来处理不规则数据。
- 第二段:引出了移动最小二乘法(MLS),并介绍了其在插值和光滑性方面的优势。
- 结论:MLS方法能够生成光滑的插值曲面。
非插值型移动最小二乘法
- 第一段:介绍了MLS方法的基本原理,包括局部近似函数$L_f$的定义。
- 结论:局部近似函数在每个点处通过最小二乘法找到最佳近似。
- 第二段:定义了全局近似函数$Gf$,并讨论了其光滑性。
- 结论:$Gf$的光滑性取决于基函数和权重函数的选择。
插值型移动最小二乘法
- 第一段:通过引入权重函数的奇异性,确保$Gf$在数据点处插值。
- 结论:权重函数的奇异性可以确保插值。
- 第二段:讨论了权重函数的选择对插值函数光滑性的影响。
- 结论:权重函数的选择对光滑性有重要影响。
投影方法
- 第一段:证明了MLS方法可以被视为投影算子$G$。
- 结论:$G$是一个投影算子,将函数映射到光滑函数空间。
- 第二段:讨论了投影算子的性质,包括其插值性和光滑性。
- 结论:$G$具有插值性和光滑性。
相关投影方法
- 第一段:提出了一种更高效的投影方法$P$。
- 结论:$P$在计算上更高效。
- 第二段:讨论了$P$的性质及其与$G$的关系。
- 结论:$P$和$G$具有类似的性质。
权重函数的选择
- 第一段:讨论了权重函数的选择对计算结果的影响。
- 结论:权重函数的选择对光滑性和效率有重要影响。
- 第二段:分析了权重函数的可微性对插值函数光滑性的影响。
- 结论:可微性影响插值函数的光滑性。
渐近行为
-
第一段:分析了当$ z \to \infty$时,插值函数的行为。 - 结论:外推可能会表现出多项式的不良行为。
复合方法
- 第一段:讨论了将MLS方法与有限元方法结合的复合方法。
- 结论:复合方法可以提高计算效率和光滑性。
- 第二段:分析了复合方法的插值性质。
- 结论:需要注意插值性质的保持。
数值实验
- 第一段:通过一元和二元问题的例子,展示了MLS方法的效果。
- 结论:数值实验验证了MLS方法的有效性。
- 第二段:讨论了不同参数选择对结果的影响。
- 结论:参数选择对结果有重要影响。
总结
这篇论文系统地介绍了移动最小二乘法(MLS)在散乱数据插值和曲面生成中的应用。论文的结构清晰,从引言到数值实验,逐步展示了MLS方法的理论基础、实现细节和实际效果。每一段落都围绕一个核心问题展开,通过数学分析和数值实验验证了方法的有效性。希望这些分析能帮助你更好地理解论文的整体结构和内容。
原文翻译
论文标题:移动最小二乘法生成的曲面
作者:P. Lancaster 和 K. Salkauskas
期刊:Mathematics of Computation
卷号:37, 期号:155
日期:1981年7月
摘要
本文对移动最小二乘法(MLS)进行了分析,用于平滑和插值散乱数据。特别地,文中证明了关于插值函数光滑性的定理,并将MLS过程描述为投影方法。文中还讨论了MLS投影算子与有限元方案投影算子的组合性质。分析过程中,通过一元和二元问题的例子进行了说明。
1. 引言
尽管基于有限信息对单变量函数进行插值和逼近的理论和实践已经较为成熟,但对于多变量函数,情况并非如此。当信息由矩形网格上的函数值组成时,可以使用基于单变量方案的张量积和混合插值方法。对于不规则分布的函数值数据,情况则更加复杂。有限元技术虽然有价值,但为了生成$C^1$插值函数,需要的不仅仅是函数值信息。此外,如果数据分布不规则,似乎只有三角形元素是可行的。由于最近快速高效三角化算法的发展,三角形元素的使用变得更加吸引人。然而,额外的节点信息(包括导数数据)必须以某种方式构造出来。最小二乘多项式逼近方法被广泛使用,当然,这种方法不期望生成插值函数。然而,正如McLain [7]、Gordon和Wixom [4]、Barnhill [1]以及最近的Lancaster [5]所展示的,最小二乘逼近思想可以通过引入移动最小二乘逼近的概念以及在这些逼近中使用的权重中的适当奇异性来生成插值函数。这种方法包括Shepard [11]的度量插值技术。到目前为止,关于移动最小二乘逼近和插值函数的理论还相对较少。本文以一种可以在内积空间背景下看待该方法的方式发展了这种方法。这导致了关于这类逼近函数的可微性类的定理,以及由这种方法定义的投影的其他一些性质。这些结果超出了Lancaster [5]所报告的结果。我们没有给出收敛理论;关注点集中在插值函数的几何性质上。文中证明了该方法确定了一个投影算子,记为$G$,从域$D$上的连续函数空间映射到$D$上的$m$次可微函数空间,其中$m$由方法的基和其他细节决定。还引入了一个与$G$相关的插值投影算子$P$,它可以减少计算工作量。后者的某些特定版本之前已在Kansas地质调查的SURFACE II程序中应用。在本文准备完成后,我们注意到了Franke和Nielson [3]的最新工作。在[3]中,投影算子$P$也被推导为$G$的替代,并且给出了一些实际计算的指导。为了隔离分析的某些特征,我们首先考虑不进行插值的移动最小二乘逼近方法。假设一个函数$f: D \rightarrow \mathbb{R}$需要被逼近,其在点$z_i \in D$,$i = 1, \dots, N$处的值$f_i$已知。假设域$D$是$\mathbb{R}^n$的一个简单连通子集$D$的闭包。为了便于表述,我们假设$n = 2$;然后很容易看出这些结果适用于任何变量数。基于已知的关于$f$的信息,开发一个近似函数$Gf$是下一节的主题。此后,为了确保插值条件$Gf(z_i) = f_i$,$i = 1, 2, \dots, N$,在权重函数中引入奇异性,并在第6节中考察了上述插值过程的变体。在第9节中,我们讨论了通过从局部最小二乘插值中生成节点数据以用于有限元方法的组合方法。由于引入的方法尚未经过系统研究,分析中用大量的一元和二元问题的例子进行了说明。这些图形旨在传达定性信息,其准确性有限。
2. 非插值型移动最小二乘法
给定一个函数$f$,如前一节所述,我们通过在每个点$z \in D$处形成一个局部近似函数$L_f$来确定一个全局近似函数$Gf$,该局部近似函数定义在某个基${\phi_i}{i=1}^n$,$n < N$以及局部$L^2$范数的基础上。结果表明$G\phi_i = \phi_i$(见第5节),因此自然地将常数函数包含在基中。如果基中只有常数函数,$Gf$是一个移动平均值,并且在第4节的插值表述中,$Gf$变成了Shepard插值函数[11]。我们假设基具有以下性质:
(i) $\phi_1 = 1$,
(ii) $\phi_i \in C^m(D)$,$i = 1, \dots, n$,
(iii) ${\phi_i}{i=1}^n$在$D$中给定的$N$个点的某个子集上是线性独立的。
现在,对于每个$z \in D$,找到系数$a_i(z)$,$i = 1, \dots, n$,使得函数
\(L_f(z) = \sum_{i=1}^n a_i(z) \phi_i(z)\)
在某种最小二乘意义上是$f$的最佳近似。然后定义,对于任何$z \in D$,
\(Gf(z) = L_f(z) = \sum_{i=1}^n a_i(z) \phi_i(z)。\)
我们将更具体地说明“最小二乘意义”,并证明$G$由(2.3)定义是良定义的。对于$f$由$L_f$逼近,我们使用一个由$f$依赖的内积诱导的加权离散$L^2$范数,其中波浪号表示,任何在给定点集$(z_i){i=1}^N$上不相等的两个函数将被视为等价的。用符号
\(u = (u(z_1), u(z_2), \dots, u(z_N))^T, \quad u \in C^0(D),\)
在$z$处的内积由
\((u, v)_z := u^T W(z) v, \quad \forall u, v \in C^0(D)。\)
我们取$W(z)$为一个$N \times N$对角矩阵,$W(z) = \text{diag}(w^{(1)}(z), \dots, w^{(N)}(z))$,对于每个$z \in D$,其对角元素为正(但见第7节)。相应的$f$-范数当然是
\(\|u\|_z = (u, u)_z^{1/2}。\)
现在,对于任何固定的$z \in D$,最佳逼近$L_f$(参见(2.2))到$f$从$\text{span}{\phi_i}{i=1}^n$在$z$-范数下满足
\((f - L_f, \phi_i)_z = 0, \quad i = 1, \dots, n,\)
这意味着系数$a_i(z)$满足正规方程
\(\sum_{i=1}^n a_i(z) \phi_i(z_j) w^{(j)}(z) = (f, \phi_i)_z, \quad i = 1, \dots, n。\)
用向量$a$表示,这些正规方程可以写成
\(B W(z) B^T a = B W(z) f,\)
其中$B$是一个$n \times N$矩阵,其第$j$行是$(\phi_i(z_j))^T = (\phi_1(z_j), \dots, \phi_n(z_j))$,$f = (f(z_1), \dots, f(z_N))^T$。向量$b_i$的独立性(由${\phi_i}{i=1}^n$的独立性以及$W(z)$的正定性得出)意味着$B W(z) B^T$是正定的。因此,系数$a_i(z)$在(2.2)中是唯一确定的,$G$由(2.3)定义是合理的。这个定义意味着,除非$W(z)$是一个常数矩阵,否则对于每个$z \in D$,必须确定一个新的向量$a(z)$。$f$可以用$z$替换,$Gf$被称为
由移动最小二乘法生成的$f$的近似。如果$W(z)$是常数,那么$Gf$是一个经典的、非移动的加权最小二乘逼近或回归函数。至于$Gf$的光滑性,很容易证明如果$\phi_i \in C^m(D)$,$i = 1, \dots, n$,并且$W$的(对角)元素$w^{(i)} \in C^k(D)$,$j = 1, \dots, N$,那么$Gf \in C^k(D)$,$k = \min{k, m}$。这立即从$B W B^T$在$D$的每一点的可逆性以及表示(2.3)得出。为了后续参考,我们更仔细地研究$n = 1$的情况。这里,$L_f$由$f$通过$i$-内积在$\phi_1$上的投影组成。因此
\(L_f = \frac{(f, \phi_1)_z}{(\phi_1, \phi_1)_z} \phi_1,\)
并且(参见(2.1)和(2.4))
\(L_f(z) = \sum_{i=1}^N f_i \frac{w^{(i)}(z)}{\sum_{j=1}^N w^{(j)}(z)}。\)
我们定义
\(v^{(i)}(z) = \frac{w^{(i)}(z)}{\sum_{j=1}^N w^{(j)}(z)}, \quad i = 1, \dots, N。\)
显然,$v^{(i)}(z)$满足$0 < v^{(i)}(z) < 1$且$\sum{i=1}^N v^{(i)}(z) = 1$。因此,对于每个$z$,$L_f(z) = Gf(z)$仅仅是给定$f$值的加权平均。在这种情况下,移动最小二乘法是一种移动加权平均法。因此,当$n = 1$时,
\(\min\{f_1, \dots, f_N\} \leq Gf(z) \leq \max\{f_1, \dots, f_N\}。\)
为了后续参考,我们定义
\(Sf = \sum_{i=1}^N f_i v^{(i)}(z)。\)
在第4节中,这将是Shepard插值函数[11]。
在前面的讨论中,我们已经看到了在权重函数中引入奇异性对Shepard插值函数$Sf$的影响。接下来,我们考虑这种奇异性对局部近似$L_f$和全局近似$Gf$的其他部分(参见(3.3)和(3.5))的影响。
如果$z \neq z_k$,那么在计算$L_f$和$Gf(z)$时不会涉及权重函数中的奇异性。因此,$L_f$和$Gf$在$D \setminus {z_i}_{i=1}^N$上是$C^m$光滑的,因为$\phi_i \in C^m(D)$。当$n > 1$时,权重函数中的奇异性会导致矩阵$B W B^T$中的某些系数在$z \to z_k$时趋于无穷大,这给分析由(2.3)定义的曲面的光滑性带来了困难。
接下来,我们展示如何通过将曲面表示为(3.5)的形式,得到一组没有这种奇异性系数的正规方程。根据第3节的符号,我们首先证明:
引理4.2:如果权重函数$w^{(i)}$如引理4.1中定义,且$\phi_i \in C^m(D)$,那么函数$\beta^{(i)}$和$g^{(i)}$(分别由(3.2)和(3.6)定义)属于$C^m(D)$。此外,对于每一个$h \in C^0(D)$,内积$(\beta^{(i)}(z; \cdot), h)$是$z$在$D$上的$C^\infty$函数。
证明:从(3.2)和引理4.1可知,$\beta^{(i)}(z; \cdot) \in C^m(D)$,对所有$z \in D$成立。同样,$g^{(i)} \in C^m(D)$。至于内积$(\beta^{(i)}(z; \cdot), h)$,唯一可能引起奇异性的是在数据点$z_k$的足够小的去心邻域内,由下式给出: \(w^{(k)}(z) \beta^{(i)}(z; z_k) h(z_k) = w^{(k)}(z) \left[ \phi_i(z_k) - \sum_{j=1}^N w^{(j)}(z) \phi_i(z_j) \right]。\) 由于$v^{(i)} \in C^\infty(D)$,且权重函数$w^{(i)} \in C^\infty(D)$,内积可以扩展为$z$在整个邻域上的$C^\infty$函数。$\blacksquare$
现在,局部近似$L_f$由正交性条件确定: \(\begin{aligned} (a) &\quad (f - L_f, \beta^{(1)}(z; \cdot))_z = 0, \\ (b) &\quad (f - L_f, \beta^{(i)}(z; \cdot))_z = 0, \quad i = 2, \dots, n。 \end{aligned}\) 然而,由于权重函数的奇异性,必须小心处理内积。假设 \(L_f = a_0 \beta^{(1)}(z; \cdot) + \sum_{i=2}^n a_{i-1} \beta^{(i)}(z; \cdot),\) 并且暂时简化符号,正交性条件可以写为: \(\begin{aligned} (a) &\quad a_0 (\beta^{(1)}, \beta^{(1)})_z + \sum_{i=2}^n a_{i-1} (\beta^{(i)}, \beta^{(1)})_z = (f, \beta^{(1)})_z, \\ (b) &\quad a_0 (\beta^{(1)}, \beta^{(i)})_z + \sum_{i=2}^n a_{i-1} (\beta^{(i)}, \beta^{(j)})_z = (f, \beta^{(j)})_z, \quad j = 2, \dots, n。 \end{aligned}\) 除了$(f, \beta^{(1)})z$在$z \to z_k$(数据点)时趋于无穷大外,所有其他内积在$D$上都是良定义的。然而,通过从(4.3)(b)中消去$a_0$,在$z_k$的足够小的去心邻域内,该系统等价于: \(\begin{aligned} (a) &\quad a_0 = (f, \beta^{(1)})_z, \\ (b) &\quad \sum_{i=2}^n a_{i-1} (\beta^{(i)}, \beta^{(j)})_z = (f - a_0 \beta^{(1)}, \beta^{(j)})_z, \quad j = 2, \dots, n。 \end{aligned}\) 根据引理4.1和4.2,(4.4)(b)的系数矩阵和右侧由$C^\infty$元素组成。该系数矩阵在整个$D$上是正定的,因此对于所有$z \in D$,存在唯一的$C^\infty$解$(a_1, \dots, a{n-1}) = a^T$。尽管$a_0$在$z = z_k$时趋于无穷大,但$a_0 \beta^{(1)}(z; \cdot) = Sf(z) \in C^\infty(D)$。根据(3.5)的符号,我们有:
定理4.1:设$\phi_i \in C^m(D)$,$i = 1, \dots, n$,且权重函数$w^{(i)}$如引理4.1中定义。那么局部近似$L_f$和全局插值函数$Gf$都属于$C^m(D)$,并且具有以下形式: \(\begin{aligned} L_f(z) &= Sf(z) + \sum_{i=2}^n a_{i-1}(z) \beta^{(i)}(z; z), \\ Gf(z) &= Sf(z) + \sum_{i=2}^n a_{i-1}(z) g^{(i)}(z), \end{aligned}\) 其中$\beta^{(i)}$和$g^{(i)}$分别由(3.2)和(3.6)定义,系数向量$a$满足 \(U(z) W(z) U^T(z) a = U(z) W(z) (f - Sf(z) \phi_1)。\)
5. 插值型移动最小二乘法作为一种投影方法
从前面各节的结果来看,显然$G$是从$C^0(D)$到$C^m(D)$的线性算子。因此,$Gf$可以用一组基函数$E^{(k)}$,$k = 1, \dots, N$表示,这些基函数具有以下性质: \(E^{(k)}(z_j) = \delta_{kj}, \quad j, k = 1, \dots, N,\) 并且 \(Gf = \sum_{k=1}^N f_k E^{(k)}。\) 任何$E^{(k)}$都可以通过将$G$应用于一个函数$e^{(k)}$得到,该函数定义在$D$上,满足$e^{(k)}(z_j) = \delta_{kj}$,$j, k = 1, \dots, N$。由于$Gf$在$D$上插值$f$且仅使用值$f_1, \dots, f_N$,因此$G^2 f = Gf$。因此,$G$是一个投影算子,从$C^0(D)$映射到一个$N$维线性空间$M = \text{span}{E^{(k)}}{k=1}^N \subset C^m(D)$。此外,可以很容易地看出$M \supseteq \text{span}{\phi_i}{i=1}^n$。因为对于$z \neq z_k$,我们可以使用正规方程(2.6)来确定系数向量$a$。设$f = \phi_k$,则有$f = B^T e^{(k)}$,即$B^T$的第$k$列。因此,(2.6)的唯一解为$a = e^{(k)}$,从而$G \phi_k = \phi_k$在$D \setminus {z_i}_{i=1}^N$上成立。根据连续性,这一结论可以扩展到整个$D$。
这些结果总结如下:
定理5.1:第4节中描述的插值方案确定了一个映射$G: C^0(D) \to C^m(D)$,这是一个投影算子,映射到$N$维空间$M = \text{span}{E^{(k)}}{k=1}^N \subset C^m(D)$。此外,$\text{span}{\phi_i}{i=1}^n$是$M$的一个$n$维子空间。
示例1:考虑将插值型移动最小二乘法(IMLS)应用于一个独立变量,并在抛物线弧上对称地放置四个插值点。选择的基函数为$b_i(x) = x^{i-1}$,$i = 1, 2, \dots, n$。在图5.1(a)和(b)中,分别展示了$n = 1, 2, 3$以及权重函数为负二次幂和负四次幂时(即$a = 2, 4$,如引理4.1所述)的插值结果。这些图形展示了在数据稀疏的局部极值附近,为了避免“凹陷”现象,需要包含完整的二次基。
图5.1 局部极值处的“凹陷”现象
(a) 负二次幂权重函数
(b) 负四次幂权重函数
示例2:将IMLS方法(一个独立变量)应用于图5.2(a)和(b)中所示的六个来自阶梯函数的数据点。权重函数和基函数$b_i(x)$的选择与示例1相同。为了比较,还展示了三次样条插值的结果。数据和拟合曲线关于坐标原点对称。
图5.2
(a) 负二次幂权重
(b) 负四次幂权重
示例3:再次考虑IMLS插值,一个独立变量。数据来自在区间$[-1, 1]$上均匀分布的11个点,计算$e^x$的值。基函数与示例1相同,使用负二次幂权重函数。我们在图5.3中绘制了误差曲线,即$e^x$减去插值结果。
图5.3 指数函数插值的误差
当$n = 1$(即Shepard插值)时,误差较大且呈振荡性质,这是“平坦斑点”现象的直接结果。当$n = 2$时,误差振荡性质仍然存在,但幅度减小;而当$n = 3$时,误差显著降低,振荡幅度约为$n = 1$时的十分之一。这些现象表明,增加基函数的阶数可以有效改善插值精度。
6. 一种相关的投影方法
显然,$Gf$在计算上并不方便,因为对于每个新的值$z$,都需要解一个新的方程组。以下方法在每个数据点$z_k$处仅需解$n-1$个方程(当$n > 2$时),并且对于该方法,定理4.2的类似结论也成立。定义算子$P: C^0(D) \to C^m(D)$如下: \(Pf(z) := \sum_{k=1}^N v^{(k)}(z) L_f(z_k)。\) 因此,隐式地形成了$N$个局部近似曲面$L_f(z_k)$,这些曲面属于$\text{span}{\phi_i(z_k)}{i=1}^n$,而$Pf(z)$是这些曲面的加权平均,使用归一化的权重函数$v^{(k)}(z)$。根据引理4.1和定理4.1,$Pf \in C^m(D)$。归一化权重函数$v^{(k)}(z)$的基性质(见引理4.1中的(i))表明$Pf(z_k) = L_f(z_k) = f_k$,$k = 1, \dots, N$。此外,对于任意可微函数$f$,有: \(\frac{\partial Pf(z)}{\partial x} = \sum_{k=1}^N \left[ v^{(k)}(z) \frac{\partial L_f(z_k)}{\partial x} + \frac{\partial v^{(k)}(z)}{\partial x} L_f(z_k) \right], \quad k = 1, \dots, N,\) 根据归一化权重函数的基性质和引理4.1的推论,可以得出$\nabla Pf(z_k) = \nabla L_f(z_k)$。由于$Pf$是插值的,并且仅使用值$f_k$,因此满足$P^2 f = Pf$,是一个投影算子。此外, \(P \phi_i = \sum_{k=1}^N v^{(k)}(z) L_{\phi_i}(z_k) = \phi_i, \quad k = 1, \dots, n,\) 因为$L_f(z_k) = f(z_k)$且$\sum{k=1}^N v^{(k)}(z) = 1$(引理4.1)。$P$是一个线性算子,且$Pf$,与$Gf$类似,可以表示为: \(Pf = \sum_{k=1}^N f_k F^{(k)},\) 其中$F^{(k)} = P e^{(k)}$,$e^{(k)}$如第5节所述。我们已经证明了:
定理6.1:在定理4.1的假设下,由(6.1)定义的插值方案确定了一个投影算子$P$,映射到$N$维子空间$N = \text{span}{E^{(k)}}{k=1}^N \subset C^m(D)$,且$\text{span}{\phi_i}{i=1}^n$是$N$的一个$n$维子空间。此外,对于$k = 1, \dots, N$,有$\nabla Gf(z_k) = \nabla Pf(z_k) = \nabla L_f(z_k)$。
最后,应当指出,如果在第2节的上下文中定义$Pf$,那么它就是$f$的移动最小二乘近似。关于数值例子的讨论推迟到第7节末尾。我们这里只指出,如果在远多于$N$个点处评估曲面$Gf$或$Pf$,那么投影算子$P$将更加经济。然而,额外的计算开销在于需要存储一个额外的$N \times (n-1)$数组(以保留(4.7)在$N$个数据点处的解)。
7. 权重函数的选择
在第4节中,我们对权重函数做出了特定的假设,以便能够简洁地表述结果。在实际数值计算中,可能会选择其他类型的权重函数。本节将讨论一些自然的选择。
首先,如果数据点数量$N$非常大,可能需要对权重函数进行截断,使得远处的点权重为零。这种截断需要以一种能够确保$Gf$的存在性并保持其连续性类别的方式来实现。为此,令$m^{(i)}(z)$,$i = 1, \dots, N$,是满足以下性质的函数:
(i) $m^{(i)}$的支撑集为$D_i$,其中$D_i$是简单连通且紧致的,$z_i \in D_i$,且对于$z \in D_i$,有$m^{(i)}(z) > 0$,并且$m^{(i)} \in C^0(D)$。
(ii) 对于任意$z \in D$,存在依赖于$z$的指标$i_1, \dots, i_k$,$k \geq n$,使得$z \in D_{i_1} \cap \dots \cap D_{i_k}$,并且$(z_{i_1}, \dots, z_{i_k})$包含一个子集,使得${\phi_i}_{i=1}^n$在其上线性独立。
对于非插值情况,可以选择$w^{(i)} = m^{(i)}$。那么根据(2.9),归一化的权重函数$v^{(i)}$属于$C^0(D)$且非负。尽管$W(z)$(见(2.6))可能包含一些零对角元素,但条件(ii)确保了正规方程系数矩阵的正定性,第2节和第3节的结论仍然有效。特别是,$Gf \in C^k(D)$,其中$k = \min{k, m}$。
在实际应用中,可以为每个$D_i$选择一个半径为$p$的开圆盘,中心位于$z_i$。那么只有满足$ | z - z_i | < p$的数据点才会进入$Gf(z)$的计算。显然,$p$必须足够大,以满足条件(7.1)。如果需要一个标准回归曲面,可以取$p$足够大,使得$D \subseteq D_i$,并且$w^{(i)} = 1$,$i = 1, \dots, N$。还可以根据需要让$p$依赖于$i$,以处理点密度在不同区域变化较大的问题。 |
如果需要在某个数据点$z_i$处进行插值,则需要引入一个合适的奇异权重。由于该过程是局部的,因此只需引入一个奇异权重即可。因此,作为引理4.1中选择的推广,一个合适的选择是: \(w^{(i)}(z) = m^{(i)}(z) |z - z_i|^{-a}, \quad a < 0 \text{ 且为偶数},\) 其中$m^{(i)}$满足(7.1)。需要检查当分母和分子中出现如(7.2)所示的奇异性时,$v^{(i)}$的可微性类别。这可以完成,并且发现$v^{(i)} \in C^k(D)$,$i = 1, \dots, N$,且$Sf \in C^k(D)$。正如在第4节中所见,正交化过程(见第3节)确保了在计算$Gf$时不存在奇异性。因此,定理4.1、4.2、5.1和6.1的结论仍然成立,只是由于$m^{(i)}$的可微性类别而略有修改。我们发现$L_f$、$Gf$和$Pf$属于$C^k(D)$,其中$k = \min{k, m}$。
在大多数应用中,方便将权重函数$w^{(i)}(z)$定义为标准权重函数$w(z)$的平移。当需要插值时,这个标准权重函数在原点处具有奇异性。然后,$w^{(i)}(z) = w(z - z_i)$,$i = 1, \dots, N$。这就是我们采用的方法。权重函数的选择如下: \(w(x) = \begin{cases} \cos^2\left(\frac{\pi}{2} \frac{|x|}{p}\right), & |x| < p, \\ 0, & |x| \geq p. \end{cases}\) 类似的权重函数也可以选择为: \(w(x) = \begin{cases} (1 - |x|/p)^2_+, & |x| < p, \\ 0, & |x| \geq p, \end{cases}\) 其中下标“+”表示当$(1 - |x|/p) < 0$时,将其截断为零。
示例5:在此,我们在节点$-1, -0.75, \dots, 1$上计算一些基函数。在每个案例中,使用权重函数(7.3),其中$p = 1$。两个Shepard基函数(即$n = 1$,适用于$G$和$P$投影器)如图7.1所示。由于权重函数被截断,基函数必须具有紧支撑。振幅衰减的速率是值得关注的,这受到$p$选择的影响。随着$p$的减小,振幅衰减会更快,但需注意,$p$的下限通常由$n$的选择决定。
图7.1 在9个数据点上,$p = 1$时的Shepard基函数
对于$G$投影器,当$n = 2$和$n = 3$时,这些图形几乎没有视觉变化。当$n = 2$时,基函数在远离数据值+1的节点一侧会有一点“超调”,负函数值的幅度略有增加;当$n = 3$时,这种效应比$n = 2$时更为明显。对于$P$投影器,当$n = 2$和$n = 3$时,图形几乎与$G$投影器相同,但当$n = 2$时,负函数值的幅度比$G$投影器更明显。
示例6:数据和基函数与示例2相同,权重函数使用(7.3),其中$p = 1$。在图7.2中,我们展示了$G$投影器在$n = 1, 2, 3$时的结果。这些结果应与图5.2(a)进行比较。$P$投影器给出了类似的结果。当$n = 3$时,无法将其与图7.2中的$n = 3$图形区分开来。当$n = 2$时,其最大值比$n = 3$时略高,位于$x = 0.3$到0.4之间。
图7.2 使用截断权重函数的$G$投影器(与图5.2(a)比较)
示例7:数据和基函数与示例3相同,考虑在$[-1, 1]$上对$e^x$进行近似。我们通过参考图5.3来定性描述数值结果。使用权重函数(7.3),其中$p = 1$,以及$G$和$P$投影器。当$n = 1$时,误差行为与图5.3中非常相似,因为“平坦斑点”现象仍然存在。误差的大小也类似,但略大一些。当$n = 2$时,误差的振荡性质相似,但幅度大约减半。当$n = 3$时,误差显著降低,比例约为十倍。这些评论适用于$G$投影器。$P$投影器的误差与$G$投影器相当,但通常更大,最多可达两倍。是否可以为这种现象找到理论解释,这将是一个有趣的研究方向。
8. 渐近行为
对于所有讨论过的权重函数,以下观察是有效的:如果定义对角矩阵$V = (\text{Tr} \, W)^{-1} W$,那么$\lim_{|z| \to \infty} V$存在;记作$V_0 = \text{diag}(v_0^{(1)}, \dots, v_0^{(N)})$。例如,对于引理4.1中的$W$,根据该引理的(iv)部分,有$V_0 = N^{-1} I$。对于足够大的$|z|$,可以将(2.6)的两边同时除以$\text{Tr} \, W$,得到: \(B V(z) B^T a = B V(z) f。\) 这些方程无论是否进行插值都成立。矩阵$B$与$z$无关;因此,$a$渐近于一个常数向量$a^{(0)}$。由此可知,$L_f \sim \sum_{i=1}^n a_i^{(0)} \phi_i$,进而$Gf \sim \sum_{k=1}^N a_k^{(0)} \phi_k$。另一方面,$Pf \sim \sum_{k=1}^N v_0^{(k)} L_f(z_k)$。这是一个在数据点处的局部近似$L_f(z_k)$的加权平均,因为$\sum_{k=1}^N v_0^{(k)} = 1$。因此,$Pf$也渐近于$\phi_i$,$i = 1, \dots, n$的线性组合。这些观察表明,如果使用多项式基,那么在数据点的凸包之外进行“外推”时,可能会表现出多项式的不良行为。
9. 复合方法
在数值实践中,投影算子$G$和$P$的计算成本非常高。因此,它们通常被用作两步过程的第一步,而实际上会限制直接计算$G$或$P$的量。一种常见的方法是确定一个规则网格的点,其凸包包含$D$,并使用关于$Gf$的信息(例如,在规则网格的点处的值及其一阶偏导数)来通过更熟悉的张量积或有限元方法生成光滑曲面。在规则网格上所需的这种导数信息需要像定理4.1这样的光滑性结果。如果在规则网格上的第二步插值是一个由投影算子$Q$确定的投影方法,那么从函数$f$的样本$f_1, \dots, f_N$生成的曲面是函数$QGf$的表示。然而,除非点$z_1, \dots, z_N$也是规则网格的顶点,否则$QGf$通常不会是$f$在这些点处的插值。在这种情况下,显然算子$QG$不会是一个投影算子。这个过程通常被称为“将数据移动到规则网格上”。
对于许多应用这些技术的研究者来说,插值性质的丧失被视为一个严重的缺点。一种越来越受欢迎的技术是首先基于顶点${z_i}_{i=1}^N$构建平面的三角剖分,然后在这些点处生成数据$f$,同时从$Gf$处采样导数数据,并使用这些信息逐个三角形地生成一个$C^1$曲面。这当然是一种“有限元”过程。再次,会有一个底层的有限元投影算子$Q$,但这次$QGf$将插值$f$。可以立即得出,复合算子$QG$确定了一个投影算子。然而,通常情况下,$QG \neq GQ$(见[6]以获取进一步讨论)。
考虑在一般三角剖分上选择一个合适的$C^1$有限元方案。数值经验表明,应避免计算$Gf$的二阶偏导数;参见[10]。一般来说,尽管$Gf$可能是$f$的一个良好近似,但随着导数阶数的增加,$Gf$的导数作为$f$的导数的近似质量会越来越差。因此,一个只使用节点处的函数值和一阶导数信息,并且具有$C^1$元素间连续性的有限元方案是可取的。这样的方案候选包括与Clough和Tocher [2]、Mansfield [8]以及Powell和Sabin [9]相关的方法。
示例8:数据和基函数与示例4相同。在图9.1(a)和(b)中,我们展示了由复合算子$QG$确定的曲面,该算子不是一个投影算子。投影算子$Q$由一个分段二次矩形单元定义,该单元只需要在矩形的顶点处对$Gf$进行函数和导数评估(该元素是基于Powell和Sabin [9]的三角形单元开发的,并在Ritchie [10]的工作中进行了详细描述)。首先,$Q$的平滑效果是显而易见的(与图5.6中的$Gf$进行比较),并且从图9.1(a)中的4×2矩形网格(45个节点值)到图9.1(b)中的8×4矩形网格(135个节点值)的分辨率提升也很明显。注意,对于这些特定示例,由于数据点的数量超过了生成$QPf$所需的$Pf$的采样数量,因此使用$Pf$而不是$Gf$是没有道理的。
图9.1(a)
由移动最小二乘投影算子与分段二次矩形单元有限元投影算子的复合,4×2矩形网格,45个节点值。
图9.1(b)
由移动最小二乘投影算子与分段二次矩形单元有限元投影算子的复合,8×4矩形网格,135个节点值。
评论