1、(2. 1. 1 )TnX 二 ZX其中(2. 1.2 )1981年Cuppen提出一种求上述对称三对角矩阵几所有特征值和特征向量的分而治之方法(divide 一* and conquer method).其基本思想是先将对称三 对角 矩阵&分割为两个分别为k X k阶和(n - kp(2. 2. 1. 2)fk (Q 二 det (Tk -)10为Tk的特征多项式,则特征多项式及其导数计算公式如下(三项递归式):r foG)二 1, fl (Q=%tfi仏)=(% -Qfi4仏)Pi!仁(4), i =2,3,,n(221. 3r fo )二 1,时(二)=T(fi (Q =(% -Qfi:
2、仏)-巧仁(Q, i =2,3,,n(221.4 fOS)二 l,flG)二 0(221. 5 fi (Q = (W 几)fi :一2fi:仏)巧 fi: (4), i = 2, 3,,nf)= fnWf =fnO) f 二f; G),(22. 13)式两边都除以得f厂GJ得(221.6 )匕 1 (扌 L)=a 1 _ A几)二ctj _几 一 i 二 2, 3, , n=4仏)亠一尚和匚)15 “(22. 1.4)式和(22.1.5)式两边除以f仏)并注意下述关系可得下面的递归关系SOW (1)3(4)二帀”叽占 pi/仏)J =2, 3,n(2.2. 1. 7)j 仏)二0,勺仏)二0J
3、 彳 垄Fi (Q二y* (% -Q 九+1-j riTI(2.2. 1.8)分别对式和(2.2. 1.8)式进仏),i=2, 3,n I i (九)行简单的推导,我们可以得到下面两个关系式-需S需干我们称(2. 2. 1. 6) 式为改进的三项递归进的计算特征多项式一阶导数和二阶导数的计算公式式221. 7)式和(2. 2. 1. 8)式分 别为改,这些是我们在调用Laguerre迭代时所需要计算的根据文中知,除了个别极其特殊的情形,它们可以避免计算过程中出现的上溢或下溢现象 但是,值得注意的是,如果对于某个i(l勻V n)使得耳二0时,上述改进的各式就会出现中断现象为了保证排除中断 的发生
4、,在计算中作如下处理如果(1)=0,则令匕(扎)二Pigi二1,2,,n1 如果=0,则令En()J =这里E为机器精度上述处理相当于对8或a n引入一个小扰动I PiS或I 注2. 1:我们由三项递归式(2. 2. 1. 3)式经过改进得到(221. 6piTsl。式,在计算改进 的非线性三项递归式(2.2. 1. 6)式时,同时可以得到在某个给定值 A处,不大于该 固定值A的特征值的个数,即q(IX Q (对所有1兰i兰n)的个数.222 Laguerre迭代的性质对于不可约对称三对角矩阵Tn(如(2. 1. 1. 1)式),其特征多项式f 仏)=detQn -几 In), (2.221
5、)的所有根为互不相等的实根。设f (心的根为并令扎。二二和扎卄二。对X亡仏,AS, Laguerre迭代L+(x)和L_(x)分别定义如下Lx)二x+ i a (2. 222)/ f(x) , L m/ 小/ F (x) 2 z f (x) f (x) Vf(x) f(x)L- (x)二 X + 4 zooo I(q)J(nT)(n1) (3)n(d) f (x) Y f (x) (222.3)f(x)并且有下面的命题成立.命题2. 1对仏m, kmS m =0, 1,,n,则有下述结果成立:(D 几 m VL_(X)CXCL+(X)CAm+ ;(2)存在常数C+和c_使得当 x 趋于几 m+
6、时,有 L+ (X) -km + 兰 cjx -Am4t 3 ;当X趋于丸血时,有L_(X) m兰CX-珀1。根据命题2.1,如果令 Jk =L; (x) = L+(L+(L+(x)kIL (x),I xT 二 Ll(x)二L_(L_(则有(1) (2)(2. 224 )(2) (1)一y VY YVY+Y+ (2. 22. 4) 式说明当X忘仏m,)uJ时,L_(x)从X的左侧趋向于Am , L+(x)从X的右侧趋向于 文中指出只要X非常接近丸(或非常接近Am半),一般调用(2. 2. 2. 3)式(或(2. . 2. 2. 2)式)两!三次便可收敛于(或亦丿。2. 2. 3病态接近特征值及
7、改进的Laguerre迭代根据文献,当多项式有重根时Laguerre迭代只是线性收敛虽然不可约对称三对角矩阵的特征值为两两互不相同的实数,但是,它们中的某些特征值也可能非常 接近以致于在数值上无法区分,例如Wiikinson矩阵。当矩阵有一个由r个非 常接 近的特征值构成的束时,在计算中被看作为一个 r重特征值,在这种情形下,Laguerre迭代的收敛率仅为线性的。为了在上述情形一卜加速迭代Laguerre收敛,对Laguerre迭代(2. 2. 22)式和(2. 2. 23)式作重新定义,对正整数r ( 0r n ),定义1/(x)和1/(x)如下Lr+(x)二 X + d (2.2.3.
8、1 )(223. 2)Lr _(x)二 X + 4 (f x) (n 一 r i)( f x)2 n f (X)(_匚厂7)_ (n_ Dp)f (x) V r f (x) f (x)我们称(2. 2. 3. 1)式和(2. 2. 3. 2)式为改进的Laguerre迭代我们需要注意 的是: 当 r =1 时,(2. 2. 3. 1)式和(2. 2. 3. 2)式就分别是(2. 2. 2. 2)式和(2. 2. 2. 3)式因 此,我们在调用Laguerre迭代时,通常是先令r =1,然后计算r来调用(2. 2。3. 1)式或(2.2. 3. 2)式。由上面的两个式子,可以得到两个序列X(k;
9、 =LkJ X) =LrMLr4C LrX)北XkSLk_(X)=Lr_(LrLr_(X) T)当X”为f仏)的r重根时,如果X并且f (兀)在区间(X,X”)内无根,则序列X黑,k =1,2,-以三次收敛速度递增地收敛于 xj类似地有,如果Yx并且f仏) 在区间(x: x)内无根,则序列x (1, k二1,2,,以三次收敛速度递减地收敛于x*。数 值试验表明,即使在病态根束的情形下,(223.1)式和(223.2)式也能达到三次收敛对上述改进的Laguerre迭代1/ (x)和1/ (x),有下面定理:定理 2.2设禹V扎2成 An为多项式fGJ二det (几-几IQ的根,贝U对X - Cm
10、, /mG和任一正整数r c n,我们有如果-则 Am CX CL+(X)L2+(X)Lr+ (X)Am 十;f (X)(J如果-沏,则5 ) V丄(心宀,为了方便起见,记二亠和几卄二g。注2.2 :设仏口如十)为Laguerre迭代的初始点并用它逼近特征值 几m十,在某些 情形下,在离扎m+右边非常近的地方可能存在一组特征值,即 入m十V扎m七 0, j二1,2,,nT,若存在p j =0, 0 j nT,则原问题 可 以转化为两个低阶矩阵的特征值问题。3.1.1求IAST特征值的QL算法考虑IAST ( 3. 1. 1),如果矩阵阶数n为奇数,由于IAST的特征值为互为共扼的 纯虚数或零,
11、因此可以通过位移为零的QL迭代把Jn化为(3. 1. 1. 1)其中JnA为偶数阶矩阵,其特征值为互为共辘的纯虚数。不失一般性,我们以后不 妨假设矩阵的阶数n为偶数。令Jn二J,计算j的特征值的QL算法描述如下:计算J2 +肾1的第n列a (Js + pl: en =(0, 0,,Pn4, Pn20, Pl: -P计算Househoulder矩阵po使得PoQ. | a 6n,这里 Po = I 2wWT,其中 w =(0, 0,;,4 pnjh_22, 0,叮-p( -T 丁 /h2广邛nrpsz+ (障_Ph2邛2邛2+(障邛边7二茁- fnT-P2n J sign(i)二-signer
12、一 P _nj )计算J =PoTJPo,即0 -Pi0 *0*0*0*0然后利用一系列旋转变换把J化为新的 LAST具体地,注意J只是比原矩阵J在(n, n-3)和(n-3 , n)位置上多两个非零元素用旋 转矩阵(I n-4-s把P2R J P1P2的(n, n4)和5-4, n)位置上多两个非零元素,这时在(n, n5)和(n-5, n) 位置上多两个非零元素。类似地,通过旋转矩阵R,匕,,Pn-3,把J化为J二Pn-PJPJ JPlP2Pn,此时#为一个新的LASTo此时对哒行压缩。在对啲压缩 后的矩阵执行双位移QL算法,经过若干步上面的循环后,最终可以收敛于 J的标准型冏0 1、12
13、 二.一1 0 丿.3.1.2由LAST的叉积的压缩矩阵求其特征值的方法1971年,M. H. C. Paardekooper曾用于对称矩阵的Jacobi思想推广到反对称 矩阵 情形,给出了一种求反对称矩阵特征值得算法。 但他的算法仅考虑了反对称性,未利用其纯虚数特征值共辘成对的性质, 廉庆荣教授等利用这一性质,构造出矩阵阶数为n =2N的jjT (其中J为LAST )的压缩矩阵(N阶不可约对称三 对角矩 阵),简记 CIST (condense irreducible symme trie t ri di agonal mat rix) o 卜面的定理可以说明:CIST的特征值的开方是对LA
14、ST的特征值的虚部。有关算法是在构造出JjT的CIST后,采用对称QL算法(带W订kinson位移)求岀CIST的 特征值,然后在对其特征值开方求得LAST特征值的虚部。不失一般性,仍考虑形如(3.1.1 )式的n阶不可约反对称三对角矩阵J (不 妨设n =2N为偶数,n为奇数时,N二h/2)。令二胪二妬),J必为特殊的 五对 角对称矩阵:a * =肾,Ctnn = P:,ajj=Pj2+ Pj2, = 2-3 nP2j,j - P2J-1.N 出亠一 , Pj 二 0(其匕),为不可约对称三对角矩阵,T二&ij )迂R环何如 2jjj H pjHj, j =2, 3,,n -1, a*=0,其他.定理3. 1设J JF如(3. 121 )所示,(3. 1. 2. 1 )若选择排列阵P二(Pij) 才满足则P打” P二T,其中T和T均且 aj=a:i,2j, T=(%j 空 R邓且Gj =a2iA2j0 j )注3. 1当n =2N+1时,T为N +1阶,定理仍成立。本文仍采用文22中的叫法,称T和T为r的压缩矩阵,其元素可以从r中 直接得出,以T为例:fa -f5nN Gjj 邛:丄 + 時,j 二 1, 2,,N -1, L2N ?=-p2j J P2jj=l, 2; , N-l,心 j 卅,j Rj j 十二(3. 1.2.2 )严j二0,其他.F面的定理给出定理3. 1
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2