一類特殊子空間上調和 Ritz對的性質及應用

牛大田

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

一類特殊子空間上調和 Ritz對的性質及應用

牛大田

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

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

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

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

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

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

因此,考慮 ~A的特征向量的特殊結構,本文首先討論了 ~A在子空間 Em上的調和 Ritz對的一些性質,其中

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

1 主要結果

定義 1[6]稱滿足關系

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

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

證明 由 φ∈Em知

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

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

定理 3 ~A在子空間 Em的正交補 E⊥上的調和 Ritz對也具有像定理 2那樣的正負成對性質。

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

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

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

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

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

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

并代入式(4)可得

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

再代入式(9)可得

因為

2 重要應用

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

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

m2ii

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

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

3 結 語

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

[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.

(責任編輯 鄒永紅)

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

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

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