多維細分算法在仿射空間中的收斂性質

謝華勇，程 麗

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

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

1 細分算法收斂的相關介紹

且對至少一個初始點集，f不恒等于0。

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

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

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

這個條件很容易被驗證。

研究由非負面具所生成的細分算法的許多問題來自計算機幾何圖形設計，自從第一個B 樣條細分算法產生以來，人們對關于非負細分算法收斂性質進行了大量的研究。本文將研究由有限非負面具所生成的多維細分算法在仿射空間中收斂的必要條件。

2 相關引理

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

文獻［10］給出了由有限非負面具所生成的多維細分算法收斂的充要條件。

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

推出：T∩T'≠φ。

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

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

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

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

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

文獻［11］給出了細分算法收斂的必要條件，描述了面具支撐中點的性質。

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

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

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

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

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

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

3 主要結果

例1 由非負面具｛a（α ）｝所生成的二維細分算法，假設集合Ω∈Z2（見圖1）是其支撐，則［Ω］ ∩Zs與Ω 相同，支撐Ω 中共有8 個點：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= 。當k=1 且λ=（0，0）T，我們得到

圖1

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

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

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

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

則L1∩L2≠ 且

我們知道細分算法收斂，則可推導出式（6），即：當j=1，…，2 時，有

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

證畢。