多維細(xì)分算法在仿射空間中的收斂性質(zhì)

謝華勇，程 麗

（1.麗水學(xué)院幼兒師范學(xué)院，浙江松陽(yáng)323400；麗水學(xué)院職業(yè)技術(shù)學(xué)院，浙江麗水323000）

細(xì)分算法是用迭代的方法來(lái)產(chǎn)生光滑的曲線和曲面，具有內(nèi)置多分辨率的結(jié)構(gòu)。細(xì)分算法由于本身本質(zhì)上的遞歸性、數(shù)值穩(wěn)定性和易于在計(jì)算機(jī)上實(shí)現(xiàn)，已成為目前最流行的一種以快速方式產(chǎn)生曲線和曲面的方法。

1 細(xì)分算法收斂的相關(guān)介紹

且對(duì)至少一個(gè)初始點(diǎn)集，f不恒等于0。

我們用H表示帽子函數(shù)，且當(dāng)x=（x1，…，xs）T∈Rs時(shí)，有ψ（x）=H（x1）…H（xs）。由vk（α）我們得到了一個(gè)“多邊形”顯然，因此細(xì)分算法收斂等價(jià)于函數(shù)fk的一致收斂。另一方面，不妨令a1（α）=a（α），通過(guò)面具迭代得我們來(lái)看一個(gè)特殊的函數(shù)δ- 函數(shù)：

一致收斂。本文中的細(xì)分算法收斂于φ，意味著式（2）收斂于φ。

文獻(xiàn)［1-6］研究了由有限面具所生成的細(xì)分算法收斂的充分必要條件。由面具所生成細(xì)分算法收斂的其中一個(gè)充要條件，可以利用聯(lián)合譜半徑來(lái)刻畫[3，7-8]，然而，有關(guān)聯(lián)合譜半徑的判斷是NP-Hard 問(wèn)題[9]；另一個(gè)判斷收斂的充要條件是求和法則，即：

這個(gè)條件很容易被驗(yàn)證。

研究由非負(fù)面具所生成的細(xì)分算法的許多問(wèn)題來(lái)自計(jì)算機(jī)幾何圖形設(shè)計(jì)，自從第一個(gè)B 樣條細(xì)分算法產(chǎn)生以來(lái)，人們對(duì)關(guān)于非負(fù)細(xì)分算法收斂性質(zhì)進(jìn)行了大量的研究。本文將研究由有限非負(fù)面具所生成的多維細(xì)分算法在仿射空間中收斂的必要條件。

2 相關(guān)引理

對(duì)面具｛a（ α）｝而言，如果α∈Γ（a）且，對(duì)任意的e∈Es有a（2β-α+e），則我們稱有限集合是容許集。

文獻(xiàn)［10］給出了由有限非負(fù)面具所生成的多維細(xì)分算法收斂的充要條件。

引理1[10]由支撐Ω 的有限非負(fù)面具｛a（α ）｝所生成的細(xì)分算法,滿足求和法則（3），則其收斂的充分必要條件是：對(duì)任意，對(duì)Γ（a）中任何非空合集T和T'，由以下包含關(guān)系

推出：T∩T'≠φ。

為了證明的方便，我們給出引理1 的逆否命題。

引理2 由支撐Ω 的非負(fù)面具｛a（α ）｝所生成的細(xì)分算法,滿足求和法則（3），則其發(fā)散的充分必要條件是：容許集Γ（a）中存在兩個(gè)互不相交的真子集T和T'以及一組（δ1，…，δk），其中δj∈Es，對(duì)某些k∈N和使得：

對(duì)給定的有限支撐上的面具｛a（α ）｝，我們定義集合A（λ）為：

集合A（λ）中元素的個(gè)數(shù)用來(lái)表示。由迭代公式和求和法則（3）可知，對(duì)每個(gè)λ∈Zs，在集合A（λ）中至少有一個(gè)元素，或者進(jìn)而，由求和法則（3）可推導(dǎo)出：當(dāng)m=1，2，…，對(duì)任意的λ∈Zs，有

（s-1）- 維面Ss-1是［Ω］ 的表面，當(dāng)0≤j≤s-1 時(shí)，j- 維面Sj是［Ω］ 中（j+1）維面Sj+1的表面。集合Ω∩（2Zs+δ）中元素的個(gè)數(shù)用來(lái)表示。

文獻(xiàn)［11］給出了細(xì)分算法收斂的必要條件，描述了面具支撐中點(diǎn)的性質(zhì)。

引理3[11]令｛a（α）∶α ∈Zs｝是Rs中的有限面具，假設(shè)由面具｛a（α ）｝所生成的細(xì)分算法收斂于一個(gè)連續(xù)函數(shù)φ。如果當(dāng)某些λ∈Zs時(shí)，，則A（λ）中只有一個(gè)元素a'屬于Ωα ［Ω ］，且滿足φ（α'）=1。進(jìn)而，當(dāng)0≤j＜s時(shí)，對(duì)多面體［Ω］ 的任意j- 維面Sj有

如果，這個(gè)面具｛a（α ）｝是非負(fù)的，則存在至多一個(gè)β∈Zs滿足φ（β）=1，且

為了證明的需要，我們介紹整數(shù)集合的可約和不可約等概念（參見(jiàn)［12］）。

定義1[12]設(shè)是有限集合，假設(shè)ψ 是一個(gè)可加映射，滿足：ψ（ ）= 和

如果存在∑的一個(gè)非空真子集I，滿足，則稱ψ 是可約的,否則，稱ψ 是不可約的。

和限制在冪集T上的可加映射是不可約的，則我們可以用與Ωk和λ 相應(yīng)的T來(lái)代替可加映射ψ。

3 主要結(jié)果

例1 由非負(fù)面具｛a（α ）｝所生成的二維細(xì)分算法，假設(shè)集合Ω∈Z2（見(jiàn)圖1）是其支撐，則［Ω］ ∩Zs與Ω 相同，支撐Ω 中共有8 個(gè)點(diǎn)：a1，a2，b1，b2，c1，c2，d1，d2，滿足：a1≡a2（mod2），b1≡b2（mod2），c1≡c2（mod2）和d1≡d2（mod2）。不失一般性，令a1=（0，0）T，a2=（0，2）T，b1=（1，0）T，b2=（1，3）T，c1=（1，1）T，c2=（1，3）T，d1=（0，1）T，d2=（0，3）T。此外，我們選擇T1=｛a1，a2，d1，d2｝和T2=｛b1，b2，c1，c2｝。因此T1∩T2= 。當(dāng)k=1 且λ=（0，0）T，我們得到

圖1

這意味著T1和T2滿足式（5）。因此，由引理2 可得，定義在上述支撐Ω 上的由非負(fù)面具所生成的細(xì)分算法是發(fā)散的。

根據(jù)引理3 和例1，我們給出本文的主要定理：在仿射空間中，由有限非負(fù)面具所生成的細(xì)分算法收斂時(shí)的必要條件。

設(shè)L是Rs中的仿射空間，我們用dimL來(lái)表示仿射空間L的維數(shù)。

定理1 設(shè)｛a（α ）｝是有限非負(fù)面具且Ω∈Z2是其支撐，假設(shè)相應(yīng)的細(xì)分算法收斂。如果存在兩個(gè)仿射空間L1和L2滿足0≤dimL1，dimL2≤s，使得

則L1∩L2≠ 且

我們知道細(xì)分算法收斂，則可推導(dǎo)出式（6），即：當(dāng)j=1，…，2 時(shí)，有

接下來(lái)，我們證明式（11）是正確的。易知L1∩L2又是一個(gè)仿射空間。取α∈L1∩L2∩Zs，那么對(duì)所有γ∈Ω，滿足γ≡α（mod2），必須屬于L1∩L2。由式（6）可得

證畢。