構(gòu)造多項(xiàng)式求解矩陣特征值問(wèn)題的方法

李 宏,雷秀仁,陳志寶

(華南理工大學(xué)數(shù)學(xué)系,廣東廣州 510640)

構(gòu)造多項(xiàng)式求解矩陣特征值問(wèn)題的方法

李 宏,雷秀仁*,陳志寶

(華南理工大學(xué)數(shù)學(xué)系,廣東廣州 510640)

提出了2種構(gòu)造多項(xiàng)式,通過(guò)求該多項(xiàng)式的根,獲得矩陣部分特征值的方法,數(shù)值算例比較了這2種方法,表明了這2種方法對(duì)于求解較小規(guī)模矩陣特征值的有效性和準(zhǔn)確性.

特征值問(wèn)題; 最小多項(xiàng)式; 殘差多項(xiàng)式; QR分解; 多項(xiàng)式求根

矩陣的特征值問(wèn)題無(wú)論在理論上還是在工程計(jì)算中都非常重要.前人進(jìn)行了深入的討論,得到了許多卓有成效的算法,除了經(jīng)典的Jacobi方法、QR方法[1-2]外,還有近幾十年來(lái)發(fā)展起來(lái)的子空間迭代法、Krylov方法[3-5]等等,在本質(zhì)上屬于變換法或迭代法.本文則利用線(xiàn)性方程組的解構(gòu)造向量r0的最小多項(xiàng)式,通過(guò)求解該多項(xiàng)式的根從而獲得矩陣的部分特征值的方法,另外,當(dāng)矩陣滿(mǎn)秩時(shí),利用GMRES算法中的殘差多項(xiàng)式可以得到向量r0的最小多項(xiàng)式的一個(gè)非常好的近似,數(shù)值算例表明了這2種方法對(duì)于求解較小規(guī)模矩陣特征值是非常有效和準(zhǔn)確的方法.

1 多項(xiàng)式的構(gòu)造

1.1通過(guò)求解線(xiàn)性方程組構(gòu)造多項(xiàng)式

為求得向量r0的最小多項(xiàng)式，文獻(xiàn)[1]給出了一種方法，稱(chēng)為Krylov方法，具體地說(shuō)是找到最小的正整數(shù)m，滿(mǎn)足r0,Ar0,…,Amr0線(xiàn)性相關(guān)，然后求解

[r0,Ar0,…,Amr0](x0,x1,…,xm-1,1)T=0,

(1)

最后得到r0的最小多項(xiàng)式

f(z)=x0+x1z+…+xm-1zm-1+zm.

(2)

當(dāng)矩陣A的階數(shù)較大時(shí)，向量組r0,Ar0,…,Amr0的線(xiàn)性相關(guān)性開(kāi)始變得模糊，并且Krylov矩陣[r0,Ar0,…,Anr0]不可避免的變得病態(tài)，即不容易確定r0的最小多項(xiàng)式次數(shù)和精確求解線(xiàn)性方程組(1)，因此我們?cè)噲D歸一化Krylov矩陣的列，以期降低其病態(tài)程度，然后對(duì)其做QR分解，以R的秩作為r0的最小多項(xiàng)式的次數(shù)并求解

(3)

最后得到r0的最小多項(xiàng)式

(4)

注記：A的特征向量的一種求法:記i為多項(xiàng)式f(z)的根,用z-i對(duì)f(z)做帶余除法(顯然這里余數(shù)為0)得到fi(z)=f(z)/(z-i),記fi(z)=bm-1×zm-1+bm-2zm-2+…+b0,則fi(A)r0=(r0,Ar0,…,Am-1r0)(b0,b1,…,bm-1)T,顯然fi(A)r0即為A的對(duì)應(yīng)特征值i的特征向量.

1.2直接利用GMRES殘差多項(xiàng)式

證明由向量的線(xiàn)性相關(guān)性可知,存在最小的正整數(shù)m(m≤n),滿(mǎn)足r0,Ar0,…,Amr0線(xiàn)性相關(guān),從而存在一組非零系數(shù)a0,a1,…,am,使得(a0+a1A+…+amAm)r0=0.若a0非零，則結(jié)論顯然成立;若a0為零，則r0的極小多項(xiàng)式變?yōu)閍1x+…+amxm,顯然該多項(xiàng)式有零根,即A有零特征值,這與條件A為滿(mǎn)秩矛盾，故結(jié)論成立.

(5)

(6)

其中

gm-1(x)=a0+a1x+…+am-1xm-1,

(7)

注意到GMRES中的Arnoldi迭代

(8)

(9)

Pm(x)=1-a0x-a1x2-…-am-1xm.

(10)

2 算法

利用1.1節(jié)的方法可以得到下述求解矩陣特征值和特征向量的算法1.

算法1

(2)對(duì)矩陣K做QR分解.

(3)若記R的秩為m,則求解線(xiàn)性方程組R(1∶m,1∶m)x=-R(1∶m,m+1).

(4)得到多項(xiàng)式f(z)的系數(shù),用代數(shù)的方法求該多項(xiàng)式的根作為A的特征值.

(5)用注記求對(duì)應(yīng)特征值的特征向量.

注明:上述算法中,R(1∶m,1∶m)表示R的前m行m列組成的矩陣,R(1∶m,m+1)表示R的第m+1列中的前m個(gè)元素組成的列向量,若步驟3中解得x=(x0,x1,…,xm-1)T.則

利用1.2節(jié)的GMRES殘差多項(xiàng)式，可以得到下述算法2.

算法2

(2)迭代，對(duì)k=1,2,…,m,計(jì)算

iv)qk+1=rk/hk+1,k,

v) 按照式(9)計(jì)算Cm的第k列.

3 數(shù)值試驗(yàn)

考察20階的對(duì)稱(chēng)矩陣

分別用Krylov方法[1]、算法1和算法2求A的特征值,其結(jié)果如表1所示.

表1 不同算法求得的特征值比較Table 1 Comparison of eigenvalue obtained by different algorithm

表1中Matlab指令求得的是精確特征值，從表中看出，Krylov方法只能求得18個(gè)特征值且與精確特征值存在較大誤差，算法1是在Krylov方法的基礎(chǔ)上改進(jìn)而來(lái)，能夠求出A的所有特征值且與精確特征值之間誤差明顯減小,算法2是利用GMRES方法中的殘差多項(xiàng)式作為向量r0的最小多項(xiàng)式，通過(guò)求解殘差多項(xiàng)式的根作為矩陣的特征值，用該方法求得的特征值與精確特征值之間的差別很小，較前2種方法更為精確.但是,算法1和算法2雖然能夠用來(lái)計(jì)算矩陣部分特征值，但受到較為嚴(yán)格的限制，對(duì)于算法1，正如文獻(xiàn)[1]提到的，只有當(dāng)特征值的分布滿(mǎn)足某種條件時(shí)才可能應(yīng)用到較大規(guī)模的矩陣中，否則，當(dāng)矩陣的階較高時(shí)，計(jì)算得到的特征值舍入誤差的影響而與實(shí)際特征值相差很大，對(duì)于算法2，矩陣必須為滿(mǎn)秩且受舍入誤差的影響，步驟2的迭代次數(shù)不能過(guò)大，即m不能取太大，否則步驟4的殘差檢驗(yàn)將難以滿(mǎn)足，這些因素直接制約了矩陣的階數(shù)不能太大，除非能夠找到一個(gè)很好的初始向量r0使得步驟2的迭代次數(shù)較少且殘差檢驗(yàn)也能夠滿(mǎn)足.

[1] WILKINSON J H.The algebraic eigenvalue problem[M].Oxford：Oxford University Press,1965:365-381.

[2] 曹志浩.數(shù)值線(xiàn)性代數(shù)[M].上海：復(fù)旦大學(xué)出版社，1996：175-215.

[3] 曲慶國(guó).對(duì)求解大型稀疏特征值問(wèn)題的子空間迭代法的研究[D].南京：南京航空航天大學(xué)，2005.

[4] SIMONCINI V,SZYLD D B.Recent computational developments in Krylov subspace methods for linear systems[J].Numerical Linear Algebra with Applications,2007,14：1-59.

[5] 戴華.求解大規(guī)模矩陣問(wèn)題的Krylov子空間方法[J].南京航空航天大學(xué)學(xué)報(bào)，2001，33(2)：139-145.

DAI Hua.Krylov subspace methods for solving large scale matrix problems[J].Journal of Nanjing University of Aeronautics & Astronautic,2001，33(2)：139-145.

[6] 全忠，向淑晃.基于GMRES的多項(xiàng)式預(yù)處理廣義極小殘差法[J].計(jì)算數(shù)學(xué),2006，28(4):365-376.

QUAN Zhong,XIANG Shuhuang.A GMRES based polynomial preconditioning algorithm[J].Mathematica Numerica Sinica,2006，28(4):365-376.

Keywords： eigenvalue problem; minimal polynomial; residual polynomial; QR decomposition; polynomial roots

【責(zé)任編輯 莊曉瓊】

METHODSFORSOLVINGEIGENVALUEPROBLEMSBYUSINGCONSTRUCTEDPOLYNOMIAL

LI Hong,LEI Xiuren*,CHEN Zhibao

(Department of Mathematics, South China University of Technology, Guangzhou 510640, China)

Two methods to construct a polynomial are first introduced,and then the roots of the polynomial are calculated in order to obtain some of the eigenvalues.These two methods are compared by numerical experiments which show that the methods are effective and accurate to solve the eigenvalues of smaller matrix.

2010-04-29

*通訊作者，maxlei@scut.edu.cn

1000-5463(2011)02-0043-03

O241.6

A