一类特殊子空间上调和 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],其思想是先执行 m(m≤N)步 Lanczos双对角化过程(7)-(8)得到 Pm和 Qm,然后计算在上的 2m个调和 Ritz值(由定理 1知,这些调和Ritz值正负成对),用最小的 k个正调和 Ritz值作为需要 k个最小奇异值的近似。由定理 4可知,Lanczos双对角化型方法可以通过解一个 (m+1)×m的小奇异值问题来实现,而如果忽略 ~A的特殊结构的话,则要解一个2m阶的广义特征值问题。因此前者不但比后者计算量和存储量都小,而且更稳定可靠。

用左、右调和 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()。现在,^ui,^vi要比 ~u,~v更精确,因此,可以利用 ^ui,^vi的信息构造更好的位移策略。定义精化调和 Ritz向量张成的子空间为 ^Ek=span…,),则 ^Ek比包含更丰富的需要的奇异组的信息,^Ek关于 Em的正交补空间比关于Em的正交补空间包含更丰富的不需要的奇异组的信息。由定理 3可知,在上的调和 Ritz值正负成对出现,而这些调和Ritz值中正的那些是A的不需要的奇异值的更好的近似,用其作为位移比“准确位移”要优越,称之为“精化调和位移”。

3 结 语

本文研究了增广矩阵在一类特殊子空间上的调和 Ritz对的性质,并将其用于计算部分最小奇异值的Lanczos双对角化型方法,把传统调和投影方法计算近似奇异值需要计算的广义特征值问题转化为阶数降低一半的奇异值问题,由此降低了计算量,提高了可靠性。

[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-),男,山东新泰人,讲师,博士,主要从事数值代数研究。