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

牛大田

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

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

牛大田

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

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

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

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分別為對應(yīng)的左、右奇異向量。稱 (σi,ui,vi)是 A的奇異組。

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

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

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

1 主要結(jié)果

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

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

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

證明 由 φ∈Em知

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

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

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

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

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

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

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

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

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

并代入式(4)可得

因為A列滿秩,由奇異值的交錯性質(zhì)知,Bm非奇異,因此將式(10)兩邊消去BTm得

再代入式(9)可得

因為

2 重要應(yīng)用

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

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

m2ii

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

在實際計算中,由于存儲量和計算速度的限制,Lanczos雙對角化方法必須進(jìn)行重新啟動。隱式重新啟動策略[3-5]是目前最常用的策略,其成功與否的關(guān)鍵在于位移的選擇。“準(zhǔn)確位移”策略用那些不需要的m-k個調(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ù)成對出現(xiàn),而這些調(diào)和Ritz值中正的那些是A的不需要的奇異值的更好的近似,用其作為位移比“準(zhǔn)確位移”要優(yōu)越,稱之為“精化調(diào)和位移”。

3 結(jié) 語

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

[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

國家自然科學(xué)基金資助項目(10872045)。

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