牛大田

(大連民族學(xué)院理學(xué)院,遼寧大連 116605)

一類特殊子空間上調(diào)和 Ritz對(duì)的性質(zhì)及應(yīng)用

牛大田

(大連民族學(xué)院理學(xué)院,遼寧大連 116605)

討論了增廣矩陣在一類特殊子空間上的調(diào)和 Ritz對(duì)的一些性質(zhì),并且結(jié)合 Lanczos雙對(duì)角化過(guò)程,研究了如何可靠且有效地計(jì)算部分最小的近似奇異值、近似奇異向量以及精化調(diào)和位移等問(wèn)題。

增廣矩陣;奇異值;奇異向量;子空間;調(diào)和 Ritz對(duì);Lanczos雙對(duì)角化過(guò)程;位移

A∈RM×N(不失一般性,假設(shè)M≥N,否則處理轉(zhuǎn)置矩陣AT)的奇異值分解定義為

式中,U=(u1,u2,…,uM),V=(v1,v2,…,vn)分別為M和N階正交矩陣,Σ =diag(σ1,σ2,…,σN)。稱σi為矩陣 A的奇異值,ui和 vi分別為對(duì)應(yīng)的左、右奇異向量。稱 (σi,ui,vi)是 A的奇異組。

在很多實(shí)際應(yīng)用中需要計(jì)算矩陣的幾個(gè)最小奇異組,比如整體最小二乘問(wèn)題、信號(hào)與圖像處理、模式識(shí)別、信息檢索,等等。Lanczos雙對(duì)角化型方法是計(jì)算部分最小奇異組的最常用方法[1-5]。該類方法在數(shù)學(xué)上等價(jià)于處理下面的增廣矩陣A~的特征值恰好為 ±σi,i=1,2,…,N和M-N個(gè)零,±σi對(duì)應(yīng)的特征向量分別為 (和,零特征值對(duì)應(yīng)的特征向量都具有 (uT,0)T的形式,其中 u和 u1,u2,…,uN正交。

因此,考慮 ~A的特征向量的特殊結(jié)構(gòu),本文首先討論了 ~A在子空間 Em上的調(diào)和 Ritz對(duì)的一些性質(zhì),其中

Pm∈RM×m,Qm∈RN×m均為列標(biāo)準(zhǔn)正交矩陣。利用這些性質(zhì),證明:若 Pm和 Qm由 Lanczos雙對(duì)角化過(guò)程得到,則只需要計(jì)算一個(gè)(m+1)×m階矩陣的奇異值分解就可以得到最小奇異值的近似,而如果忽略 ~A和 Em的特殊結(jié)構(gòu),直接采用標(biāo)準(zhǔn)的調(diào)和投影方法的話,則需要計(jì)算一個(gè)2m階的廣義特征值問(wèn)題,因此相對(duì)的代價(jià)要大些。進(jìn)一步,本文還討論了如何可靠、有效地計(jì)算精化調(diào)和位移問(wèn)題。

1 主要結(jié)果

定義 1[6]稱滿足關(guān)系

的(θ,φ)為 ~A在子空間 E上的調(diào)和 Ritz對(duì),簡(jiǎn)稱(θ,φ)為 ~A的調(diào)和 Ritz對(duì)。

定理 1 ~A在子空間 E上的調(diào)和 Ritz對(duì)問(wèn)題等價(jià)于下面的 2m階矩陣廣義特征值問(wèn)題:

證明 由 φ∈Em知

由式 (6)很容易就能推導(dǎo)出式(4)成立。

證明 很容易驗(yàn)證若 (θ,((Pmx)T,(Qmy)T)T滿足式 (6),則 (-θ,((Pmx)T,-(Qmy)T)T也滿足式(6),因此,定理得證。

定理 3 ~A在子空間 Em的正交補(bǔ) E⊥上的調(diào)和 Ritz對(duì)也具有像定理 2那樣的正負(fù)成對(duì)性質(zhì)。

證明 令 (Pm,P⊥),(Qm,Q⊥)均為正交矩陣,則

其形式與 E完全類似。后面的證明過(guò)程與定理 1和定理 2的證明過(guò)程完全相同,故此不再重復(fù)。

定義 2 A關(guān)于初始向量 q1∈RN的 m步 Lanczos雙對(duì)角化過(guò)程的矩陣表示為

式中,Bm為 m階上雙對(duì)角矩陣,‖qm+1‖2=1且

定理4 若式(2)中的 Pm和Qm由Lanczos雙對(duì)角化過(guò)程的式(7)和式(8)生成,A在子空間 Em上的調(diào)和 Ritz對(duì)為 (θ,((Pmx)T,(Qmy)T)T,則θ, x分別為的奇異值和右奇異向量,且 y= θB-1mx。

證明 由式(7)和式(8)可得

并代入式(4)可得

因?yàn)锳列滿秩,由奇異值的交錯(cuò)性質(zhì)知,Bm非奇異,因此將式(10)兩邊消去BTm得

再代入式(9)可得

因?yàn)?/p>

2 重要應(yīng)用

如前所述,我們要計(jì)算矩陣 A的部分最小奇異值。目前最常用的方法是 Lanczos雙對(duì)角化型方法[1-5],其思想是先執(zhí)行 m(m≤N)步 Lanczos雙對(duì)角化過(guò)程(7)-(8)得到 Pm和 Qm,然后計(jì)算在上的 2m個(gè)調(diào)和 Ritz值(由定理 1知,這些調(diào)和Ritz值正負(fù)成對(duì)),用最小的 k個(gè)正調(diào)和 Ritz值作為需要 k個(gè)最小奇異值的近似。由定理 4可知,Lanczos雙對(duì)角化型方法可以通過(guò)解一個(gè) (m+1)×m的小奇異值問(wèn)題來(lái)實(shí)現(xiàn),而如果忽略 ~A的特殊結(jié)構(gòu)的話,則要解一個(gè)2m階的廣義特征值問(wèn)題。因此前者不但比后者計(jì)算量和存儲(chǔ)量都小,而且更穩(wěn)定可靠。

用左、右調(diào)和 Ritz向量來(lái)作為奇異向量的近似可能不收斂或收斂很慢,我們可以保留原來(lái)的近似奇異值,而近似奇異向量用新的稱之為精化左、右調(diào)和 Ritz向量的 ^ui=Pm^x/‖^x‖2和 ^vi= Qy^/‖y^‖來(lái)替代,其中 (T為

m2ii

的最小奇異值對(duì)應(yīng)的右奇異向量。^ui,^vi要比 ~ui,更精確[3-4]。

在實(shí)際計(jì)算中,由于存儲(chǔ)量和計(jì)算速度的限制,Lanczos雙對(duì)角化方法必須進(jìn)行重新啟動(dòng)。隱式重新啟動(dòng)策略[3-5]是目前最常用的策略,其成功與否的關(guān)鍵在于位移的選擇。“準(zhǔn)確位移”策略用那些不需要的m-k個(gè)調(diào)和Ritz值作為位移,它們是在關(guān)于 E的正交補(bǔ)m上的調(diào)和 Ritz值,其中 ~Uk=Pm(~u1,…~uk),~Vk=Pm()。現(xiàn)在,^ui,^vi要比 ~u,~v更精確,因此,可以利用 ^ui,^vi的信息構(gòu)造更好的位移策略。定義精化調(diào)和 Ritz向量張成的子空間為 ^Ek=span…,),則 ^Ek比包含更豐富的需要的奇異組的信息,^Ek關(guān)于 Em的正交補(bǔ)空間比關(guān)于Em的正交補(bǔ)空間包含更豐富的不需要的奇異組的信息。由定理 3可知,在上的調(diào)和 Ritz值正負(fù)成對(duì)出現(xiàn),而這些調(diào)和Ritz值中正的那些是A的不需要的奇異值的更好的近似,用其作為位移比“準(zhǔn)確位移”要優(yōu)越,稱之為“精化調(diào)和位移”。

3 結(jié) 語(yǔ)

本文研究了增廣矩陣在一類特殊子空間上的調(diào)和 Ritz對(duì)的性質(zhì),并將其用于計(jì)算部分最小奇異值的Lanczos雙對(duì)角化型方法,把傳統(tǒng)調(diào)和投影方法計(jì)算近似奇異值需要計(jì)算的廣義特征值問(wèn)題轉(zhuǎn)化為階數(shù)降低一半的奇異值問(wèn)題,由此降低了計(jì)算量,提高了可靠性。

[1]BAGLAMA J,REICHEL L.Augmented implicitly restarted Lanczos bidiagonalization methods[J].Siam J. Sci.Comp.,2005,27:19-42.

[2]HOCHSTENBACH.M E.Har monic and refined extraction method for the singular value problem,with applications in least squares problems[J].B IT,2004,44: 721-754.

[3]J IA,ZHONGX IAO,N IU Datian.An implicitly restarted refined bidiagonalizationLanczosmethod for computing a partial singular value decomposition[J].Siam J.Matrix Anal.Appl.,2003,25:246-265.

[4]J IA ZHongxiao,N IU Datian.A refined har monic Lanczos bidiagonalization method and an implicitly restarted algorithm for computing the smallest singular triplets of large matrix[J].Siam J.Sci.Comp.,2010,32:714 -744.

[5]KOK IOPOULOU E,BEKAS C,GALLOPOULOS E. Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization[J].Appl.Numer. Math.,2004,49:39-61.

[6]J IA ZHongxiao.The refined harmonic Arnoldi method and an implicitly restarted refined algorithm for computing interior eigenpairs of large matrices[J].Appl.Numer.Math.,2002,42:489-512.

(責(zé)任編輯 鄒永紅)

Properties and Application of Harmon ic Ritz Pa irs in a Special Kind of Subspaces

NIU Da-tian
(College of Science,Dalian NationalitiesUniversity,Dalian Liaoning 116605,China)

This paper presents some properties of harmonic Ritz pairs of an augmented matrix with respect to a special kind of subspaces.We also discussed how to compute some s mallest approximate singular values,approx imate singular vectors,and refined har monic shifts reliably and efficiently in combination with the Lanczos bidiagonalization process.

augmented matrix;singular value;singular vector;subspace;harmonic Ritz pair; Lanczos bidiagonalization process;shift

book=9,ebook=249

O241

A

1009-315X(2010)05-0443-03

2010-06-11

國(guó)家自然科學(xué)基金資助項(xiàng)目(10872045)。

牛大田 (1975-),男,山東新泰人,講師,博士,主要從事數(shù)值代數(shù)研究。