兩步漸進(jìn)迭代逼近法和收斂性

劉仲云，李杰

(長沙理工大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，湖南 長沙,410114)

曲線擬合是計算幾何中的基本問題[1]，為了使曲線擬合給定的有序點集，文獻(xiàn)[2]提出的標(biāo)準(zhǔn)曲線擬合方法通常需要求解線性系統(tǒng)[3]來計算其控制多邊形的頂點，文獻(xiàn)[4]指出，漸進(jìn)迭代逼近法(PIA)和加權(quán)漸進(jìn)迭代逼近法(WPIA)，能避免求解線性方程的麻煩，同時具有清晰的幾何意義和穩(wěn)定的收斂性，引起了人們的關(guān)注。為了進(jìn)一步豐富并得到收斂速度更快的漸進(jìn)迭代逼近法，本文研究了文獻(xiàn)[5-8]定義的Bernstein基的配置矩陣來擬合曲線的兩步漸進(jìn)迭代逼近法，進(jìn)一步證明了兩步漸進(jìn)迭代逼近法是對加權(quán)漸進(jìn)迭代逼近法的推廣。數(shù)值實驗表明，本文所得的兩步漸進(jìn)迭代逼近法具有更快的收斂速度。

(1)

然后得到第一條初始擬合曲線

(2)

(3)

(4)

設(shè)λn(B)是配置矩陣B的最小特征值，加權(quán)因子ω=2/[1+λn(B)]加權(quán)漸進(jìn)迭代逼近法比漸進(jìn)迭代逼近法具有更快的收斂速度。

漸進(jìn)迭代逼近法和加權(quán)漸進(jìn)迭代逼近法都是對當(dāng)前的控制多邊形進(jìn)行矯正。為了獲得更好的方法，利用當(dāng)前控制多邊形和上一層控制多邊形的控制點進(jìn)行新的矯正，得到下面的矯正格式

(5)

其中：α,β為加速度參數(shù)。

顯然，當(dāng)α=1,β=ω時方程(5)就退化為加權(quán)漸進(jìn)迭代逼近法。因此可以期望選取適當(dāng)?shù)摩?β方法比(4)有更好的收斂性。

1 兩步漸進(jìn)迭代逼近法

(6)

然后得到第一條初始擬合曲線

(7)

(8)

對應(yīng)的殘差向量為

(9)

其中：j=0,1,…,n，方程(9)對應(yīng)的矩陣形式為

Δ(k+1)=(αI-βB)Δ(k)+(1-α)Δ(k-1)

(10)

(11)

其中：k=0,1,…。

2 收斂性分析

本節(jié)討論兩步漸進(jìn)迭代逼近法的收斂性，在給出收斂性之前先引入以下引理，見文獻(xiàn)[3]。

1)λ0(B)=1, 0<λi(B)≤1,i=0,1,…,n;

2)0≤ρ(I-B)<1。

關(guān)于兩步漸進(jìn)迭代逼近法的收斂性，有如下定理。

1)兩步漸進(jìn)迭代逼近法收斂，當(dāng)且僅當(dāng)0<α<2, 0<β<2α;

2)H的譜半徑ρ(H)有最小值當(dāng)

其中：ρ0=[1-λn(B)]/[1+λn(B)]并且

證明：兩步漸進(jìn)迭代逼近法對于任何的初始控制點收斂，當(dāng)且僅當(dāng)ρ(H)<1，設(shè)(λ,x)是B對應(yīng)的特征值與特征向量，即Bx=λx則有

對于每一個λ都存在兩個對應(yīng)的特征值μi(i=1,2)滿足

其中：[x,y]=[εx,ηx],ε=1,η∈，將上式化簡得到μ2-(α-βλ)μ+(α-1)=0，從而|μ1μ2|=|α-1|<1, |μ1+μ2|<α, 所以0<α<2, 0<β<2α。

當(dāng)maxλn(B)<λ≤1, |α-βλ|最小時特征值μ0=max{|μ1|,|μ2|}取最小值即

α-β=βλn(B)-α,β=2α/[1+λn(B)]

當(dāng)v=(1-2λ)/[1+λn(B)]時得到α-βλ=αv，并且有

當(dāng)λn(B)<λ≤1時有-ρ0≤v≤ρ0，定義函數(shù)

發(fā)現(xiàn)f′(α)≤0，并且

αopt是方程(αρ0)2-4(α-1)=0最小的根，即αopt=2/[1+(1-ρ02)1/2], 證畢。

對于加權(quán)漸進(jìn)迭代逼近法，在文獻(xiàn)[5]中選擇最佳加權(quán)因子ω=2/[1+λnB], 從而有

推論3.1 對于任意的標(biāo)準(zhǔn)化全正基，兩步漸進(jìn)迭代逼近法比加權(quán)漸進(jìn)迭代逼近法具有更快的收斂速度。

證明：定義函數(shù)

g′(x)=-2/(1+x)2<0對于任意的x∈(0,1)恒成立，根據(jù)引理3.1，有0<λn(B)<1，因此

從而，證明了兩步漸進(jìn)迭代逼近法比加權(quán)漸進(jìn)迭代逼近法具有更快的收斂性。

3 數(shù)值實驗

在本節(jié)中，選取了常用的具有代表性的例子，來驗證兩步漸進(jìn)迭代逼近法的有效性。

例1 雙扭線[x(t),y(t)]=[cos(t),sin(t)cos(t)],t∈[-π/2,3π/2]

例2 螺旋線[x(t),y(t),z(t)]=[5cos(t),5sin(t),t],t∈[0,6π]

在數(shù)值實驗中，采用伯恩斯坦基來擬合雙扭線與螺旋線，利用兩步漸進(jìn)迭代逼近法求相應(yīng)的控制點。第k步迭代得到的曲線的擬合誤差為

在以上兩個例子中，考慮在文獻(xiàn)[5]定義的Bernstein基的配置矩陣。 在表1中列出了參數(shù)ω,α,β的最佳值。在表2、3中分別列出了兩種算法的計算結(jié)果，圖1中給出了加權(quán)漸進(jìn)迭代逼近法和兩步漸進(jìn)迭代逼近法的數(shù)值行為。

表1 雙扭線、螺旋線對應(yīng)的一些參數(shù)
Table 1 Certain parameters corresponding to twisted pair and helix

參數(shù)雙扭線n=10n=20螺旋線n=18n=28?1.999 32.000 02.000 02.000 0α1.800 01.800 01.900 01.900 0β0.300 00.300 00.300 00.300 0

表2 加權(quán)漸進(jìn)迭代逼近法與兩步漸進(jìn)迭代逼近法求解例1的數(shù)值結(jié)果
Table 2 Numerical results of Case 1 by WPIA and TWPIA

n加權(quán)漸進(jìn)迭代法ErrorITCPUtimes/s兩步漸進(jìn)迭代逼近法ErrorITCPUtimes/s109.866E-0713411.559E-027.778E-072339.814E-03209.975E-0713361.807E-029.442E-072351.199E-02

表3 加權(quán)漸進(jìn)迭代逼近法與兩步漸進(jìn)迭代逼近法求解例2的數(shù)值結(jié)果
Table 3 Numerical results of Case 2 by WPIA and TWPIA

n加權(quán)漸進(jìn)迭代法ErrorITCPUtimes/s兩步漸進(jìn)迭代逼近法ErrorITCPUtimes/s181.787E-03>5000>4.688E-029.993E-045241.506E-02289.996E-0644174.392E-029.180E-062661.174E-02

從表2、3和圖1中可以看出，當(dāng)達(dá)到相同的指定精度時，兩步漸進(jìn)迭代逼近法比加權(quán)漸進(jìn)迭代逼近法有更快的收斂速度和更高的計算效率。

(a)雙扭線，n=10 (b)螺旋線，n=18圖1 加權(quán)漸進(jìn)迭代逼近法與兩步漸進(jìn)迭代逼近法收斂性行為Fig.1 Convergence behaviors of WPIA and TWPIA