一類有效序列的構(gòu)造

陳艷妮，劉 琴，薛春梅，張 鄴

(陜西師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，陜西 西安 710119)

在科學(xué)計算與工程應(yīng)用中，偏微分方程的差分、有限元方法的離散求解、約束優(yōu)化問題、計算流體力學(xué)和圖像處理問題等，均可轉(zhuǎn)化為大規(guī)模稀疏線性方程組的求解。求解線性方程組一般有直接法和迭代法兩種方法。直接法是通過有限步的四則運算得到方程組的解，常用的有高斯消元法和三角分解法等。直接法在求解過程中會產(chǎn)生大量的非零元素，從而導(dǎo)致存儲量和計算量較大，主要用于低階稠密性線性方程組的求解。而對于大型稀疏線性方程組，迭代法速度快、計算量小，并且能夠得到較高精度解，是求解大型線性方程組的主要計算方法。

20世紀(jì)初，波蘭數(shù)學(xué)家Kaczmarz[1]利用矩陣分解提出了求解線性系統(tǒng)的迭代方法，即Kaczmarz方法。隨后，Gordon等[2]將Kaczamarz方法應(yīng)用到醫(yī)學(xué)成像領(lǐng)域，利用代數(shù)迭代重建技術(shù)重建圖像，由此人類歷史上第一臺計算機(jī)斷層掃描成像(Computer Tomography，CT)裝置產(chǎn)生，現(xiàn)已成為現(xiàn)代醫(yī)療機(jī)構(gòu)無損檢查的重要手段。CT圖像重建技術(shù)主要包括反投影方法、代數(shù)迭代方法和基于統(tǒng)計模型的方法等3大類。反投影方法中濾波反投影重建(Filter Back Projection，F(xiàn)BP)算法最為典型。代數(shù)迭代方法主要有應(yīng)用代數(shù)重建技術(shù)(Algebraic Reconstruction Technique，ART)和聯(lián)合迭代重建技術(shù)(Simultaneous Iterative Reconstruction Technique，SIRT)等?；诮y(tǒng)計模型的方法主要包括貝葉斯方法和最大熵方法等。相對于FBP算法，ART的優(yōu)勢是將先驗知識，即已知的約束條件納入重建過程相對容易。ART和SIRT因其優(yōu)越的抗干擾性能和數(shù)據(jù)缺失情況下的良好的成像能力，引起了CT成像領(lǐng)域?qū)W者的廣泛重視[3-4]。

Kaczmarz算法作為一種重要的代數(shù)重建技術(shù)，是利用交替投影的方法進(jìn)行迭代，算法簡單且運行速度快，已被廣泛應(yīng)用到圖像重構(gòu)、數(shù)字信號處理、神經(jīng)網(wǎng)絡(luò)和并行計算等信息科學(xué)領(lǐng)域的實際問題中[5-7]。文獻(xiàn)[8]給出了基于Kaczmarz的隨機(jī)化方法求解不含噪的超定線性系統(tǒng)的方法，并證明了該方法的指數(shù)收斂率。Needell等[9]引入加權(quán)的統(tǒng)計梯度下降方法，建立了一種改進(jìn)的Kaczmarz算法，提高了算法的收斂性。但是，對于Kaczmarz算法的理論分析，尤其是算法的收斂性分析的理論結(jié)果很少。

基于Kaczmarz方法求解線性系統(tǒng)的理論，擬從向量序列的有效性角度分析Kaczmarz算法收斂的性態(tài)。通過向希爾伯特空間的一組正規(guī)正交基中添加有限個單位向量，探討所得新向量序列的有效性問題。利用算子理論工具，通過求解一類與Kaczmarz算法有效性等價的算子方程，給出此類序列有效的等價刻畫，進(jìn)而得到一類有效序列的構(gòu)造方法。

1 預(yù)備知識

其中，k+1=i(modn)。如果A是滿秩的，則有

該算法是一種求解超定線性系統(tǒng)Ax=b的經(jīng)典方法之一,其收斂性得到了一定的證明[10]。

1977年，McCormick[11]將Kaczmarz算法推廣到解無限維的線性方程組Ax=b，其中，x,b∈l2，l2表示平方可和的復(fù)序列所構(gòu)成的希爾伯特空間。需要指出的是，在無限維Kaczmarz算法中，相應(yīng)的線性方程組的系數(shù)矩陣不具有收斂性，因此需要引入新的研究工具和方法對其收斂性能進(jìn)行討論。

x0=〈x,e0〉e0
xn=xn-1+〈x-xn-1,en〉en,n≥1

(1)

(2)

基于該結(jié)論，文獻(xiàn)[16]中研究了有效序列的一些擾動問題，得到的部分結(jié)果如下。

h0,e0,e1,e2,…,en,…

是有效的。

e0,e1,e2,…,en0-1,h0,en0,en0+1,…

2 一類有效序列的構(gòu)造

定理2與定理3討論了向正規(guī)正交基中添加一個單位向量后所得向量序列的有效性問題，給出了充分必要條件。受此啟發(fā)，一個自然的問題是，向正規(guī)正交基中添加兩個或任意有限個單位向量后所得向量序列在什么情況下是有效的？在此，將對這一問題開展研究。

e0,e1,…,en1-1,f,en1,en1+1,…,en2-1,e,en2,en2+1,…

設(shè)Qn=1-en?en(?n∈)為{en}⊥上的投影，P1、P2和P3分別為和上的正交投影。于是有P1+P2+P3=1且

1-P1=Qn1-1…Q1Q0
1-P2=Qn2-1…Qn1+1Qn1
1-P3=Qn2+2Qn2+1Qn2

(1-P3)(1-e?e)(1-P2)(1-f?f)(1-P1)=0

令

W=(1-P3)(1-e?e)(1-P2)(1-f?f)(1-P1)

討論算子方程W=0的解。

設(shè)P∈B(H)為正交投影，x∈H，若x∈P(H)為單位向量，則x?x、1-x?x、P和1-P等4個投影兩兩可換。

為敘述方便，用x∈P表示x∈P(H)。

定理4設(shè)e和f為Hilbert空間H中的單位向量，P1、P2和P3∈B(H)為正交投影且滿足P1+P2+P3=1，則算子方程

W=(1-P3)(1-e?e)(1-P2)(1-f?f)(1-P1)=0

當(dāng)且僅當(dāng)以下6個條件之一成立，即

(i)e∈P1,f∈P2+P3+e?e

(ii)e∈P1+P2,f∈P1

(iii)e∈P1+P2,f∈P2+P3

(iv)e∈P3,f∈P2+P3

(v)f∈P3,e∈P1+P2+f?f

(vi)e,f∈P1+P3，

P1(1-e?e)(1-f?f)P3=0

證明可以驗證條件(i)至條件(vi)任一成立都蘊含W=0。下證必要性，設(shè)W=0，則

0=P2WP2=P2(1-e?e)(1-P2)(1-f?f)P2=
P2(e?e)(1-P2)(f?f)P2=〈f,(1-P2)e〉P2e?P2f

從而〈f,(1-P2)e〉=0或者P2e=0或者P2f=0。下面對此3種情形分別討論。

情形1設(shè)〈f,(1-P2)e〉=0。此時，

e?e(1-P2)f?f=〈(1-P2)f,e〉e?f=0

因為

0=W=
(1-P3)(1-e?e)(1-P2)(1-f?f)(1-P1)=
(1-P3)[(1-P2)-(1-P2)f?f-e?(1-P2)e+
e?e(1-P2)f?f](1-P1)=
(1-P3)[(1-P2)-(1-P2)f?f-e?
(1-P2)e](1-P1)=
[P1-P1f?f-(1-P3e?(1-P2)e)](1-P1)=
[-P1f?(1-P1)f-(1-P3)e?P3e]

所以

P1f?(1-P1)f+(1-P3)e?P3e=0

即

P1f?P2f+P1f?P3f+
P1e?P3e+P2e?P3e=0

(3)

對式(3)左乘P2以及右乘P2，可得與式(3)同解的方程組

(4)

由方程組(4)可知以下4個條件之一成立，即

(a1)P2e=P1f=0,P1(f?f+e?e)P3=0

(a2)P2e=P2f=0,P1(f?f+e?e)P3=0

(a3)P3e=P1f=0,P1(f?f+e?e)P3=0

(a4)P3e=P2f=0,P1(f?f+e?e)P3=0

顯然，(a1)蘊含著P2e=P1f=P1e=0或者P2e=P1f=P3e=0，則定理4中條件(iv)或者條件(iii)成立。(a2)蘊含著條件(vi)成立，這是因為此時P2e=P2f=0，結(jié)合情形1的前提假設(shè)〈f,(1-P2)e〉=0可得e⊥f，于是不難看出P1(f?f+e?e)P3=0。當(dāng)且僅當(dāng)P1(1-e?e)(1-f?f)P3=0。(a3)蘊含著P3e=P1f=0，從而定理4中的條件(iii)成立。(a4)蘊含著P3e=P2f=P1f=0或者P3e=P2f=P3f=0，從而定理4中的條件(iii)或者條件(ii)成立。

情形2設(shè)P2e=0。此時

(1-e?e)(1-P2)=(1-P2)(1-e?e)

并且

0=W=(1-P3)(1-e?e)(1-P2)(1-f?f)(1-P1)=
(1-P3)(1-P2)(1-e?e)(1-f?f)(1-P1)=
P1(1-e?e)(1-f?f)(1-P1)

(5)

對式(5)分別右乘P2以及P3，則可得

P1(1-e?e)(1-f?f)P2=0

(6)

以及

P1(1-e?e)(1-f?f)P3=0

(7)

由式(6)可得

0=P1(1-e?e)(1-f?f)P2=
P1(1-e?e)P2-P1(1-e?e)(f?f)P2

于是

0=P1(1-e?e)P2=
P1(1-e?e)(f?f)P2=[P1(1-e?e)]f?P2f

從而[P1(1-e?e)]f=0或者P2f=0。結(jié)合式(7)以及情形2的前提假設(shè)P2e=0可知，算子方程W=0蘊含著以下兩個條件之一成立，即

(b1)

P2e=P1(1-e?e)(1-f?f)P3=
P1(1-e?e)f=0

(b2)

P2e=P1(1-e?e)(1-f?f)P3=P2f=0

由條件(b1)可得

0=P1(1-e?e)(1-f?f)P3=
P1(1-e?e)P3-P1(1-e?e)(f?f)P3

注意到在條件(b1)中P1(1-e?e)f=0，所以

0=P1(1-e?e)P3=-P1e?P3e

因此，條件(b1)蘊含著

P2e=P1e=P1(1-e?e)f=0

或者

P2e=P3e=P1(1-e?e)f=0

即

P2e=P1e=P1f=0

或者

P2e=P3e=(P1-e?e)f=0

從而定理4中的條件(iv)或者條件(i)成立；條件(b2)蘊含著e、f∈P1+P3，且

P1(1-e?e)(1-f?f)P3=0

從而定理4中條件(vi)成立。

情形3設(shè)P2f=0。情形3與情形2的證明類似。此時

(1-f?f)(1-P2)=(1-P2)(1-f?f)

于是有

0=W=
(1-P3)(1-e?e)(1-P2)(1-f?f)(1-P1)=
(1-P3)(1-e?e)(1-f?f)(1-P2)(1-P1)=
(1-P3)(1-e?e)(1-f?f)P3

(8)

對式(8)先后左乘P2以及P1，則可得

P2(1-e?e)(1-f?f)P3=0

(9)

以及

P1(1-e?e)(1-f?f)P3=0

(10)

由式(9)可知，

0=P2(1-e?e)(1-f?f)P3=
P2(1-f?f)P3-P2(e?e)(1-f?f)P3

于是

0=P2(1-f?f)P3=P2(e?e)(1-f?f)P3=
P2e?[P3(1-f?f)e

從而P2e=0或者[P3(1-f?f)e=0。結(jié)合式(10)以及情形3的前提假設(shè)P2f=0可知，算子方程W=0蘊含著以下兩個條件之一成立，即

(c1)

P2f=P1(1-e?e)(1-f?f)P3=
P3(1-f?f)e=0

(c2)

P2f=P1(1-e?e)(1-f?f)P3=P2e=0

由條件(c1)可知，

0=P1(1-e?e)(1-f?f)P3=
P1(1-f?f)P3-P1(e?e)(1-f?f)P3

注意到條件(c1)中P3(1-f?f)e=0，所以

0=P1(1-f?f)P3=P1f?P3f

因此，條件(c1)蘊含著

P2f=P1f=P3(1-f?f)e=0

或者

P2f=P3f=P3(1-f?f)e=0

即

P2f=P1f=(P3-f?f)e=0

或者

P2f=P3f=P3e=0

從而定理4中的條件(v)或者條件(ii)成立。條件(c2)蘊含著e,f∈P1+P3，且

P1(1-e?e)(1-f?f)P3=0

從而定理4中的條件(vi)成立。證畢。

在定理4中，如果取f=e,或者等價的f=λe，λ為模1的復(fù)數(shù)，則可得以下定理。

定理5設(shè)‖e‖=1，P1、P2和P3為正交投影且滿足P1+P2+P3=1，則算子方程

(1-P3)(1-e?e)(1-P2)(1-e?e)(1-P1)=0

當(dāng)且僅當(dāng)e∈Pi0，其中i0∈{1,2,3}。

證明當(dāng)f=e時，應(yīng)用定理4，可知定理4結(jié)論中的條件(i)與(ii)蘊含著e∈P1，條件(iii)蘊含著e∈P2，條件(iv)與(v)蘊含著e∈P3。當(dāng)f=e時，條件(vi)變?yōu)?/p>

e∈P1+P3,P1(1-e?e)(1-e?e)P3=0

從而

0=P1(1-e?e)(1-e?e)P3=
P1(1-e?e)P3=-P1e?P3e

于是P1e=0或者P3e=0。再由e∈P1+P3知，e∈P3或者e∈P1。證畢。

由定理5可知，對任意的模為1的復(fù)數(shù)λ，序列

e0,e1,…,en1-1,λe,en1,en1+1,…,en2-1,e,en2,…

Ei=(1-P1)(1-e?e)(1-P2)(1-e?e)…
(1-Pi-1)(1-e?e)(1-Pi)

(11)

引理1設(shè)n≥2，則

〈Ene,e〉=-c1(c2+1)…(cn-1+1)cn

證明應(yīng)用數(shù)學(xué)歸納法證明。當(dāng)n=2時，

〈E2e,e〉=〈(1-P1)(1-e?e)(1-P2)e,e〉=
〈(1-P1)(1-e?e)e,e〉-〈(1-P1)(1-e?e)P2e,e〉=
〈(1-P1)(e?e)P2e,e〉-〈(1-P1)P2e,e〉=
〈P2e,e〉+〈P2e,e〉〈(1-P1)e,e〉=
-c2+c2(1-c1)=-c1c2

所以引理結(jié)論成立。

設(shè)當(dāng)n=k-1時結(jié)論成立，則

〈Ek-1e,e〉=-c1(c2+1)…(ck-2+1)ck-1

當(dāng)n=k時，有

〈Eke,e〉=
〈(1-P1)…(1-Pk-1)(1-e?e)(1-Pk)e,e〉=
〈(1-P1)…(1-Pk-1)(1-e?e)e,e〉-
〈(1-P1)…(1-Pk-1)(1-e?e)Pke,e〉=
0-〈(1-P1)…(1-Pk-1)Pke,e〉+
〈(1-P1)…(1-Pk-1)(e?e)Pke,e〉=
ck〈(1-P1)…(1-Pk-1)e,e〉-
〈(1-P1)…(1-Pk-2)(1-e?e)Pke,e〉=
ck〈(1-P1)…(1-Pk-1e,e)〉+
〈(1-P1)…(1-Pk-2)(1-e?e)(1-Pk)e,e〉=
ck(-c1(c2+1)…(ck-2+1)ck-1)+
(-c1(c2+1)…(ck-2+1)ck)=
-c1(c2+1)…(ck-1+1)ck

因此，當(dāng)n=k時結(jié)論也成立。證畢。

由引理1立即可得下面的推論。

推論1設(shè)n≥2，En由式(11)所給出，則〈Ene,e〉當(dāng)且僅當(dāng)P1e=0或者Pne=0。

En=(1-P1)(1-e?e)(1-P2)(1-e?e)…

(1-Pn-1)(1-e?e)(1-Pn)=0

的充要條件是存在i0∈{1,2,…,n}使得e∈Pi0。

證明顯然?i0∈{1,2,…,n},e∈Pi0都蘊含著En=0。下面用數(shù)學(xué)歸納法證明必要性。

Ek=(1-P1)(1-e?e)(1-P2)(1-e?e)…

(1-e?e)(1-Pk)=0

當(dāng)且僅當(dāng)存在i0∈{1,2,…,k}使得e∈Pi0。

當(dāng)n=k+1時，有

Ek+1=(1-P1)(1-e?e)(1-P2)(1-e?e)…

(1-e?e)(1-Pk+1)=0

記

Ek=(1-P2)(1-e?e)(1-P3)(1-e?e)…

(1-e?e)(1-Pk)=0

因此

0=P2Ek+1Pk=
P2(1-P1)(1-e?e)(1-P2)(1-e?e)…
(1-e?e)(1-Pk+1)Pk=
P2(1-e?e)(1-P2)(1-e?e)…(1-Pk)(1-e?e)Pk=
P2(e?e)(1-P2)(1-e?e)…(1-Pk)(e?e)Pk=
P2(e?e)Fk(e?e)Pk=〈Fke,e〉P2e?Pke

從而〈Fke,e〉=0或者P2e=0或者Pke=0。

若〈Fke,e〉=0，即

〈Fke,e〉=〈[(1-P2)(1-e?e)(1-P3)(1-e?e)…
(1-e?e)(1-Pk)]e,e〉=0

結(jié)合推論1可知，P2e=0或者Pke=0，因此Ek+1=0蘊含著P2e=0或者Pke=0。

情形1設(shè)P2e=0。此時

(1-P2)(1-e?e)=(1-e?e)(1-P2)

于是

0=Ek+1=
(1-P1)(1-e?e)(1-P2)(1-e?e)…
(1-e?e)(1-Pk+1)=
(1-P1)(1-P2)(1-e?e)(1-e?e)…
(1-e?e)(1-Pk+1)=
[1-(P1+P2)](1-e?e)(1-e?e)(1-P3)…
(1-e?e)(1-Pk+1)=
[1-(P1+P2)](1-e?e)(1-P3)…(1-e?e)(1-Pk+1)

注意到{P1+P2,P3,…,Pk+1}為k個投影，并且(P1+P2)+P3+…+Pk+1=1，則由歸納假設(shè)可知，e∈P1+P2或者e∈Pi0，i0∈{3,4,…,k+1}。因為情形1的假設(shè)是P2e=0，所以

e∈P1+P2?e∈P1

因此，若P1e=0，則Ek+1=0蘊含著存在i0≤n使得e∈Pi0。

情形2設(shè)Pke=0。與情形1類似，可證定理結(jié)論成立。證畢。

由定理1及定理6立即可得以下結(jié)論。

e0,…,ek1-1,e,eki,…,ek2-1,e,ek2,…,ekn-1,e,ekn,…

3 結(jié)語

使得Kaczmarz算法收斂的單位向量序列被稱為有效序列，希爾伯特空間的正規(guī)正交基是平凡的有效序列。通過研究正規(guī)正交基的有效擾動，即向一組正規(guī)正交基中添加一些單位向量，探討所得新序列的有效性問題。最終通過求解一類與Kaczmarz算法有效性等價的算子方程，得到了一類非平凡的有效序列的構(gòu)造方法。但是文中構(gòu)造較為特殊，在今后進(jìn)一步的工作中，將解決更一般的有效序列的有效擾動問題，即向有效序列中添加一些單位向量后所得新序列在什么情況下仍然是有效的，這對Kaczmarz算法有著重要意義。