四点必要插值细分方案

文摘

我们提出一个有效和简单的算法来生成4n必要插值方案。我们的算法是基于三个简单的步骤:第二次分裂的差异,确定顶点的位置通过二分裂差异,和计算新的顶点。这是观察到四点n必要插值方案(即由完全不同的框架。,Lagrange interpolant and wavelet theory) can also be generated by the proposed algorithm. Furthermore, we have discussed continuity, Hölder regularity, degree of polynomial generation, polynomial reproduction, and approximation order of the schemes.

1。介绍

一般来说,细分方案可以分为两类:近似插值。插值曲线细分,新的顶点计算和添加到旧的多边形的每一次细分和极限曲线穿过所有的原始控制多边形的顶点。插值细分计划更有吸引力比近似方案计算机辅助几何设计,因为他们的插值性质。此外,插值细分更直观的用户。

插值细分的初步工作计划是由等级(1]。后来,Deslauriers和等级2]介绍了一个家庭的计划通过使用拉格朗日多项式被面具的大小和参数数量。在[3),直流发电机等人研究了一个家庭的插值方案四的面具的大小。随之,研究社区引入更高的参数数量计划(即感兴趣。、三元、四元必要),给更好的结果和更少的计算成本。丽安(4)构建的分必要对任何和分必要对任何奇怪插入的细分曲线设计方案通过使用小波理论。穆斯塔法和拉赫曼5提出了通用公式的面具分必要插值和逼近方案对于任何整数和。这些公式提供的面具高参数数量计划和推广低参数数量计划。穆斯塔法等。6)提出了一个显式公式的面具奇怪的点必要,对于任何奇数插值细分计划。

在[7),事实证明,大支持和更高的参数数量计划可能比小的支持和更低的参数数量比计划。虽然这些计划不是在实践中。有人建议,研究大支持和更高的参数数量计划可能继续下去。

多级方法非常方便构建细分计划。这个想法是不同的。莱恩和Riesenfeld8)提出了两种快速细分算法评价的b样条和伯恩斯坦曲线和表面。之后,他们表达了新想法,单一重复阶段控制点的数量翻了一番,只是把每个点两次,一个序列的平滑算子。卡特莫尔和克拉克(9)已经使用这种技术的原始描述的细分每个细化表达三个阶段。Zorin和施罗德10)考虑的建设越来越交替序列原始/双四边形剖分方案基于一个简单的平均方法。奥斯瓦尔德和施罗德11)使用相同的主题生成的家庭细分计划。

Augsdorfer et al。12)首先描述原4二进制细分方案,然后应用六个变化的方案通过优化当地的阶段以不同的方式,产生一些有趣的细分方案都是在原始的改进。我们概括相同的技术来构建四点的家庭必要插值细分计划。这是观察到四点必要引入插值方案(2,4)也可以由我们的通用技术,即使这些计划已经由不同的框架。

本文的组织结构如下:部分2提出了一些初步结果。部分3由多步算法生成4必要插值细分计划。两个方案的分析也是本节中给出。节4,持有人的规律性、多项式生成多项式复制品和近似秩序三元和四元细分方案的讨论。节中给出了数值例子和结论5。

2。预赛

一般的单变量的紧凑的形式必要细分方案年代(13]映射的多边形一个精致的多边形被定义为 在哪里集合的系数称为面具水平的改进。细分方案的一致收敛的必要条件(1), 细分方案是一致收敛如果任何初始数据,存在一个连续函数这样,闭区间,它满足 很明显,。

一个叫做Laurent多项式符号 面具的发挥着有效的作用来分析细分方案的收敛性和平滑度。从(2)和(4满足的Laurent多项式收敛细分计划 在哪里是根的团结。这个条件保障的存在相关的细分方案划分不同的原始控制点和一个关联的Laurent多项式的存在 细分方案与劳伦多项式有关计划与劳伦多项式通过下面的定理。

定理1(见[14])。让表示一个细分方案与劳伦多项式令人满意的(5)。那么存在一个细分计划随着房地产 在哪里和。此外,一致收敛当且仅当吗一致收敛到零函数初始数据,在这个意义上

上述定理表明,对于任何给定的计划的面具令人满意的(2),我们可以证明的一致收敛通过推导的面具和计算为,在那里是第一个整数的吗。如果这样的一个存在,那么一致收敛。因为有““规则计算值在下次改进的水平,所以我们定义标准 在哪里

定理2(见[13])。让细分方案的特点多项式,。如果细分方案相应的,多项式、一致收敛对于任何初始控制多边形。

推论3(见[13])。如果是一个细分方案的形式上面吗一致收敛到零函数初始数据,然后对于任何初始控制多边形。

上面的推论3表明,对于任何给定的必要细分方案,我们可以证明首先推导的面具然后计算为(是第一个整数的吗)。如果这样的一个存在,那么。

定义4(见[15])。对于任何细分方案我们表示相应的参数变化和附加数据为,的参数值

定理5(见[15])。一个收敛的细分方案再现了多项式的程度对参数化(12)当且仅当 在哪里,

定理6(见[16])。一个收敛的细分方案重新生成多项式(最多的一组多项式学位)有一个近似的顺序。

3所示。多步算法

我们构建4必要插值细分方案通过使用三步算法而不是使用拉格朗日多项式和小波理论,等等。这三个步骤如下。(我)计算第二次分裂的差异。

在每个老顶点计算第二均差;那是第二点分裂的区别吗和第二点分裂的区别吗(见图1): 在哪里。(2)利用分裂的差异确定顶点的位置。

在每一段分为必要细分计划在每个子分段优化水平。第一次插入点的位置和第二点位置并以同样的方式进行th点位置。通过划分不同和,我们计算的位置旧两个顶点之间th新插入点和通过 (3)计算新的顶点。

最后,我们计算新顶点的位置,,,通过使用,,,分别由 在哪里。通过求解上述方程组,我们得到新的顶点的位置,。

3.1。例子

四点三元插值方案。在三元细分方案每一部分在每个细分级别分为三个子分段。插入一个点的位置和另一个点的位置(见图2)。为在(14),我们得到第二次分裂的差异和在点和 为在(15),我们得到 通过使用(17),我们得到 为在(16),我们有 这意味着 通过使用(19),我们得到 现在4点三元计划可以写成 介绍了上述方案通过Deslauriers和等级2利用拉格朗日interpolant]在1989年。后来,这个方案也重建了(4利用小波理论)。

四点第四纪插值方案。在第四纪细分方案每段分为四个板块在每个细化联合体的水平。第一、第二和第三点是插入的位置,,分别为(见图3)。为在(14)- (16),我们得到以下四点第四纪插值方案Deslauriers和等级 这个方案也重建了(42009年)。

注7。用在(14)- (16),我们得到4点的面具必要插值方案由两个不同的框架,也就是说,拉格朗日插值(2和小波理论4]。在本文中,我们提出了替代方法完全不同于这些方法。在接下来的部分中,我们将讨论两个现有的方案也由我们的框架。

3.2。分析细分方案

这里我们提出四点三元和四元插值细分方案的分析。其他方案的分析可以以类似的方式完成。

3.2.1之上。4分析三元细分计划

劳伦的多项式计划(23)是 使用(11),和,我们得到 如果相对应的计划吗,然后由(10) 使用(9),(26)和(27),我们得到 如我们所见由定理,然后1该计划是。同样的,然后是必然的结果3该计划是。

注8。同样,我们可以证明第四纪四点细分计划。

4所示。属性细分方案

在本节中,我们显示如何限制曲线4三元和四点第四纪细分方案给最初的多项式响应数据。我们讨论持有人规律性,多项式的次数一代,多项式繁殖和近似方案的顺序(23)和(24)。

4.1。持有人的规律性

持有人规律是连续性的概念的扩展使任何计划的更多信息。一个函数定义的常规顺序和如果它是时间连续可微的,李普希茨的顺序 对所有和在和一个常数。

根据动力学和莱文(17]和Rioul [18),细分方案的持有人规律与象征可以以以下方式计算。让不失一般性,我们可以假设的非零系数,让,是矩阵的元素 则由持有人的规律性,在那里是联合矩阵的谱半径,,也就是说, 自由谱半径从下面是有界的,从上面的规范指标吗,,,然后

定理9。持有人规律计划(23)是。

证明。Laurent多项式(25计划(的)23)可以写成 在哪里 从(31日)和(34),,,,,和,从而,然后,,矩阵的元素吗 在哪里。这意味着 从(33)和(37)我们有 以来的最大特征值和max-norm指标,所以

定理10。持有人规律计划(24)是。

证明。劳伦的多项式计划(24)可以写成 在哪里 从(31日)和(40),,,,,和,从而,然后,,矩阵的元素吗 在哪里。这意味着 从(33)和(43)我们有 因此,最大特征值的max-norm指标,所以

备注11。人们普遍观察到,当我们的参数数量减少计划持有人指数增加。例如,现金男et al。19)已经证明持有人指数为二进制计划是2从上面定理,我们看到三元和四元计划持有人指数是1.8173和1.7077,分别。非常,霍尔德指数方法1大参数数量的计划。

4.2。多项式的一代

一代的细分方案最大程度的多项式,可以生成的方案,提供初始数据的正确选择。假设多项式的程度的初始数据和方案的象征 然后精制的极限曲线数据各级多项式的程度。条件是必要且充分的计划能够生成多项式的学位。

定理12。多项式的次数一代的计划(23)是。

证明。自从Laurent多项式计划(23)是 在哪里 然后生成多项式的次数。

定理13。多项式的次数一代的计划(24)是。

证明。自(Laurent多项式24)可以写成 在哪里 然后多项式次数代方案。

4.3。多项式繁殖和近似秩序

多项式复制属性有自己的重要性,随着多项式的繁殖特性在某种程度上意味着该计划近似的秩序。多项式繁殖程度需要生成多项式的学位。为此,多项式繁殖可以由初始数据采样从多项式函数。在视图中(15、多项式的繁殖特性提出方案后可以得到参数化在(12)。

定理14。一个收敛的细分方案(23再现了多项式的学位对参数化(12)当且仅当 为,和。

证明。通过一阶导数(25),用,我们得到 这意味着 所以从(12),该计划(23)原始参数化。为,,从(25),我们得到 同样的,对和(表示导数的顺序) 由(25),我们得到。也,这意味着。同样的,我们可以很容易地显示 这就完成了证明。

因为计划(23)再现了3次多项式,因此利用定理6,我们得到下面的定理。

定理15。四点三元插值方案(23)有一个近似的顺序。

下面的定理的证明类似于定理的证明14。

定理16。一个收敛的细分方案(24再现了多项式的学位对参数化(12)当且仅当 为,和。

再通过定理6,我们得到下面的定理。

定理17。四点第四纪插值方案(24)有一个近似的顺序。

评论18。考虑方案(即。,3分ternary and 4-point quaternary) are exactly the same as obtained by using imputation from Lagrange interpolation at four consecutive points [2];因此,三分三元和4季计划多项式繁殖程度3和近似属性是显而易见的(由裁判说)。这些计划也被生成的(4使用小波框架)算法,通过建设这些计划不继承这些属性,只是上面的理由包括定理。

5。数值例子和结论

六个例子描述显示四点2-ary的有用性,3-ary, 4-ary, 5-ary, 6-ary, 7-ary插值细分方案1细分层次图4。在这个图的控制多边形绘制虚线,而细分曲线由实线绘制。从图4,很明显,初始多边形迅速收敛到极限曲线增加细分方案的参数数量。

对于许多细分水平与这些方案的极限曲线必要计划大可能出现尖锐的奇异点在初始控制点方案相比小(由裁判也提到了)。但是,如果初始控制点来自噪声来源,必要计划大是更好的选择。该方案用小表现出过度拟合(见[7])。主要目的在第一级是提供给比较明显的视觉差异产生的精制多边形不同的方案。

在本文中,我们提出了一种多步算法生成4必要插值细分计划。我们还观察到四点必要计划由拉格朗日多项式和小波理论也可以提出了多步生成的算法。一些重要的属性如持有人规律性,多项式的次数一代,多项式的次数繁殖,还讨论了逼近阶。

确认

这项工作是支持的HEC巴基斯坦本土博士奖学金计划。作者要感谢裁判对他们有益的建议和意见,显示改善工作的方法。