（计算数学专业论文）关于多元特征值问题的数值方法.pdf

关于多元特征值问题的数值方法 摘要 多元特征问题产生于多元统计中多组变量的典型相关分析。1 9 3 6 年， h o t e l f i n g 首先把线性相依性推广到两个随机向量的讨论中，提出了典型相关分 析，检测两组变量间整体相关关系。它的基本思想是根据两组指标的观测值研 究两组指标问的相关性，按其提出相关成分的大小依大到小将每组指标进行线 性组合，求它们之间的典型相关系数。根据相同原理研究多组变量之间的整体 相关性时，利用l a g r a n g e 乘数法，则导出多元特征值问题。 向后误差和条件数是数值代数的两个基本概念，前者反映了算法的向后 稳定性，后者刻画了问题的解关于原始数据小扰动的敏感性，而两者结合则可 以估计计算解的精度。关于多元特征值问题的敏度分析成果还不多，因此本文 主要研究了多元特征值及对应特征向量的敏度分析。在第二部分中我们首先 把矩阵的单特征值概念推广到多元特征值问题。然后，用隐函数理论证明了单 特征值及对应特征向量的解析性质，由此导出一阶展开式，并给出条件数的显 示表达式和扰动理论。最后，在第三部分我们对h o r s t 方法和p s o r 方法作了 数值改进，给出了一种初始迭代向量选择策略。数值试验表明此策略不仅改进 了h o r s t 算法和p s o r 方法的收敛速度，而且有助于两种算法都收敛到统计意 义下的全局最大值解。 关键词：多元特征值问题，单特征值，条件数，扰动上界，向后误差，h o r s t 方 法，p s o r 方法，极大解 t h en u m e r i c a lm e t h o d f o rt h em u l t i v a r i a t ee i g e n v a l u ep r o b l e m a b s t r a c t t h em u l t i v a r i a t ee i g e n v a l u ep r o b l e mh a si t so r i g i n si nt h ed e t e r m i n a t i o no f c a n o n i c a lc o r r e l a t i o nc o e f f i c i e n t sf o rm u l t i v a r i a t es t a t i s t i c s 。i t sh i s t o r yg o e sb a c k t ow h e nh o t e l l i n g ( 1 9 3 6 ) f i r s ts t u d i e dt h es o - c a l l e dm a x i m a lc o r r e l a t i o np r o b l e m ， w h i c hl a t e rw a sd e v e l o p e di n t ow h a ti sk n o w sa sc a n o n i c a lc o r r e l a t i o na n a l y s i s a p p l y i n gt h em e t h o do fl a g r a n g em u l t i p l i e r ss u c ha l lo p t i m i z a t i o np r o b l e mc a n b er e d u c e dt ot h em u l t i v a r i a t ee i g e n v a l u ep r o b l e m ( m e p ) p e r t u r b a t i o na n a l y s i sp l a y sa ni m p o r t a n tr o l ei nm o d e mn u m e r i c a ll i n e a r a l g e b r a b a c k w a r de r r o r sr e v e a lt h es t a b i l l t yo fan u m e r i c a lm e t h o d c o n d i t i o n n u m b e r se x p l a i nt h e s e n s i t i v i t yo ft h es o l u t i o no fap r o b l e mt ob a c k w a r de r r o r ，t h e p r o d u c to fc o n d i t i o nn u m b e rt i m e sb a c k w a r de r r o rp r o v i d e saf i r s to r d e re r r o r b o u n df o rt h ec o m p u t e ds o l u t i o n t oo u rk n o w l e d g e ，h o w e v e r ，t h ep e r t u r b a t i o n a n a l y s i sf o rt h em e pr e m a i n st ob es t u d i e d t h i sp a p e ri sm a i n l yd e v o t e dt o t h ep e r t u r b a t i o na n a l y s i sf o rt h em u l t i v a r i a t ee i g e n v a l u ep r o b l e m ( m e p ) i nt h e s e c o n dp a r t ，t h ec o n c e p to fs i m p l ee i g e n v a l u eo fam a t r i xi sg e n e r a l i z e dt ot h e m e p t h e n ，w es t u d yt h ef i r s to r d e rp e r t u r b a t i o ne x p a n s i o n so fas i m p l em u l - t i v a r i a t ee i g e n v a l u ea n dt h ec o r r e s p o n d i n ge i g e n v e c t o r c o n s e q u e n t l y , w ed e r i v e t h ee x p l i c i te x p r e s s i o n so fc o n d i t i o nn u m b e r s ，p e r t u r b a t i o nu p p e rb o u n d sa n d b a c k w a r de r r o r sf o rm u l t i v a r i a t ee i g e n p a i r s f i n a l l y , i nt h el a s tp a r t ，w es u g - g e s tas t r a t e g yo fc h o o s i n gt h es t a r t i n gp o i n tf o rh o r s t sm e t h o da n dt h ep s o r m e t h o d n u m e r i c a le x a m p l e sd e m o n s t r a t et h a tt h i ss t r a t e g yi sn a t u r a la n dw o r k w e l l k e y w o r d s ：m u l t i v a r i a t ee i g e n v a l u ep r o b l e m ，s i m p l ee i g e n v a l u e ，c o r l - d i t i o nn u m b e r ，p e r t u r b a t i o nb o u n d ，b a c k w a r de r r o r ，s t a r t i n gp o i n t ， h o r s t sm e t h o d ，p s o rm e t h o d 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名：存莲如签字日期：础年r 月知日学位论文作者签名：绐，恕如签字日期：础年r 月咖日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：茑乌，i 盈如导师签字： 、 ，中 签字日期：跏g 年s 月知日 勤瞰l 飘 签字日期州扮n 影日 第一章综述 设a 为n n 实对称正定矩阵，考虑a 的分块 a = a 1 l a 2 1 l a 1 2 a 勉 a t ，1 2 a 1 m a 2 m a 仇m ( 1 1 ) a 西r 唧吩， 吩= n j = 1 多元特征值问题( m e p ) 【2 】定义如下：求实数a l ，k 及向量z 舯使得 a z = a x ，人= d i a g a l 厶l ，一，入m k ，( 1 2 ) 厶。表示啦阶单位矩阵，向量z 具有相应的分块 z = 旧，z 翻t ，戤黔， ( 1 3 ) 0 黾1 1 2 = 1 ，i = 1 ，2 ，m 在文献 1 6 j 中，此问题也被称为多参数特征值问题。 多元特征问题产生于多元统计中多组变量的典型相关分析 8 ，9 ，1 l 】1 9 3 6 年， h o t e l l i n g 首先把线性相依性推广到两个随机向量之间的相关关系的讨论中，提 出了典型相关分析，检测两组变量间整体相关关系。它的基本思想如下：为研究 两组交量z = 扛l ，研) 和y = ( y l ，y 2 ，骆) 之间的相关性，利用主成分思想， 分别在两组变量中选取若干变量组成有代表性的综合指标，每一综合指标都是 原变量的一个线性组合，通过研究这两组综合指标之间的相关关系，来代替这 两组变量间的相关关系，这些综合指标即为典型变量。其实施步骤是：首先在 每组变量中指出变量的线性组合作为有代表性的综合指标钍i ，玩，即 i t l 2o q i x i + 0 4 2 x 2 + + 口舻f 三a 7 z l - 地= b i l y l + b i 2 y 2 + + 瓯口玑三b y 关于多元特征值问题的数值方法 我们可以只考虑方差为1 的z ，y 的线性函数口乞与6 ，y ，使它们的具有最大相关 性，即达到最大的相关系数，然后再在每组变量中指出第二对线性组合，使其 分别与第一对线性组合不相关，而第二对本身具有最大相关性，如此继续下 去。典型变量是根据它们的相关系数由大到小逐对提取，直到两组变量之间的 相关被分解完毕为止。用此分析方法通常研究变量之间的整体相关性，但忽略 了变量间内部的差异。为了解决这个问题，v a nd eg e e r 2 1 1 提出了m a x b e t 方 法，并把它用于检测多组变量之间的最大相关性。设置( i = 1 ，2 ，m ) 为m 组 变量指标的观测值即墨是n 佻阶实矩阵，则x = i x l ，x n l 为n 死实矩 阵。设u = 陋 ，乱三】t 为啦维子向量牡组成的扎维列向量，那么m a x b e t 算法 就是在满足约束条件：u t u t = l ，i = 1 ，2 ，m 下求函数f ( u ) = 牡r x r x u 的 最大值。令a = x t x ，利用l a g - r a n g e 乘数法，此极值问题即可导出多元特征值 问题( m e p ) ( 1 2 ) 。同时，我们注意到，不少文章都提出了新的分析变量间相 关性的方法并把其推广到m 3 的情形，比如，针对广义的m a x b e t 问题，t e n b e r g e 1 9 1 提出了一种单调收敛的算法。其它的方法和实例可以参考下述文献及 其索引h a n a l i 和k i e r s 6 1 ，h o r s t 8 和h a n a f i 和t e nb e r g e 7 】。 为了求解多元特征值问题，h o r s t 8 最早引入了幂法。胡德煜【1 0 对h o r s t 方 法予以补正并给出了收敛性分析。基于h o r s t 方法，v a nd eg e e r 2 1 1 提出 了m a x b e t 算法。h a n a f i 和t e nb e r g e 7 给出了在m = 2 的情形下m a x b e t 方 法收敛到全局最大解的充分必要条件。孙继广【1 6 】把s o r 的加速思想与h o r s t 方 法相结合，提出了p o w e r - s u c c e s s i v eo v e r r e l a x a t i o n ( p s o r ) 迭代方法，并论证 了其收敛性。c h u 和w a t t e r s o n 2 1 应用度理论证明了下述重要理论结果：在典 型情形下，多元特征值系统( 1 2 ) 恰有丌2 啦组解，并且如果m e p 只有有限组解 则h o r s t 方法必收敛。关于多元特征值问题下述几种特殊情形已有有效的算法： ( 1 ) m - - 1 a 此时m e p 转化为普通的对称特征值问题，已有很多有效方法见【4 】 ( 2 ) m = 2 ，如= k ，歹= 1 ，2 作a 1 2 的s v d 分解：a 1 2 = u r v r ，设 y l = 沪z l ，驰= v t x 2 ，则 、l j ， 讥抛 o 山 厶o h = 、l 玑抛 2 k k 垆 一 za =a 关于多元特征值问题的数值方法 a x ：a x 骨 l 乡2 【丸- 1 肌 i 1y l = ( a 2 1 ) 沈， 则通过一些运算可知：入1 1 = 入2 一l ，从而入1 = 入2 。故入l = 千莎+ 1 ，盯为a 1 2 的 奇异值，z l 为对应的左奇异向量，z 2 为对应的右奇异向量。这样可以通过a z 2 的s v d 分解求解多元特征值及对应的特征向量。这是h o r s t ( 1 9 6 1 年) 提出的直 接法。而且m 们( ，a x ) = 2 ( 1 + lj a m l l 2 ) 可用于检验是否求得“最大化解 。 ( 3 ) m = 2 的一般情形。 h a n a t i 和t e nb e r g e 7 给出了m e p 的解为m a x b e t 的全局最大解的充分 必要条件，该条件易于检验。且 7 1 中还处理了下述问题：如果m e p 的解 入，t ) 非m a x b e t 的基本解，则可以在解向量u 的基础上获得更好的迭代起点以寻找整 体解。 ( 4 ) m - - - n 。 每组变量中只含1 个变量，此时易得出所有解z = ( x l ，) t ，= 千l ，j = l ，2 ，n ，因此= ( 括n1a j 七x k ) x j ，u = 1 ，2 ，n ) 每个巧有2 种 取值法，故共有2 n 组解，统计上要求的是：l 的最大值。 对于仇 2 的一般情形，仅有c h u 和w a t t e r s o n 2 】给出关于m e p 的代数理 论分析并且c h u 和w a t t e r s o n ( 1 9 9 3 ) 提供了一个例子表明：h o r s t 方法的收敛 结果依赖于初始迭代向量的选择，很有可能得不到统计意义下的最大解。孙继 广【1 6 】提供的实例表明p s o r ：y 法的收敛速度优于h o r s t 方法，但两种方法的收 敛速度和收敛结果都强烈的依赖初始迭代向量的选择，可能会收敛到局部极大 值点。从统计应用背景考虑，我们期望得到m e p 的全局最大值解，然而如何选 择合适的初始迭代向量目前尚没有结论。本文给出了种初始迭代向量的选择 策略，数值试验表明此策略不仅提高了h o r s t 方法和p - s o r 方法的收敛速度，而 且有助于两种方法收敛到统计意义下的“全局最大值解 。 当然，对于多元特征值问题，仍有许多其它方向的话题值得我们深入的研 究。 扰动分析是现代数值线性代数中的一个重要的研究方向。向后误差和条件 数是数值代数中的两个基本概念，前者由w i l k i n s o n 于上世纪6 0 年代提出并研 究，主要用于分析数值算法的向后稳定性：后者刻画了问题的解关于原始数据 小扰动的敏感性；两者结合可用于分析计算解的精度：在一阶近似下，有 近似解的误差条件数向后误差。 3 关于多元特征值问题的数值方法 扰动分析理论研究已取得了大批重要的结果 1 5 ，1 8 】。关于矩阵对的典型相 关性，g o l u b 和z h a f 5 】利用矩阵对的广义奇异值分解已给出了详细的扰动分析理 论结果。但对于m 2 的一般情形，至今还没有扰动分析理论成果。本文的主要 目的就是给出多元特征值及其对应特征向量的敏度分析。首先，我们把矩阵的 单特征值概念推广到多元特征值问题。然后，用隐函数理论证明了单特征值及 对应特征向量的解析性质，由此导出一阶展开式，并给出条件数的显示表达式 和扰动上界。 4 第二章多元特征值问题的敏度分析 在统计分析中，扰动分析也被称之为敏度分析，例如，在文献【1 】中给出了 线性回归模型的敏度分析，而在文献 1 2 】中给出了主成分分析方法的敏度分 析。g o l u b 和z h a 在 5 】中利用广义奇异值分解原理给出了矩阵对之间典型相关 性的敏度分析的理论结果。这一部分，我们主要给出多元特征值问题的敏度分 析，首先，我们给出单特征值的概念。 2 1单特征值及对应特征向量的一阶展式 设入= ( a 1 ，入仇) 是4 的多元特征值，z = p ，z 黝? 为对应的特征向 量，即入和z 满足( 1 2 ) 。由于巧胂，f 1 巧1 1 2 = 1 ，因而有正交阵轨r 吩唧使 得 q 知= 【1 ，0 ，o 】丁u = 1 1 2 ，m ) 记q = 阮，x j l ， 及 a a ：= x a ：= x t 。t n 入l 厶l 一1 k 厶。一1 ( 2 1 ) ( 2 2 ) 注：如果某个码= 1 ，则认为天中对应的毛一l 项及( 2 1 ) 中含玛的项不存 在。 首先，我i f 弓l 入下述定义 定义2 i ：如果a a 一天非奇异，则称入为a 的( 对应划分( 1 1 ) ) 的一个单特征 值。 注：如果m = 1 ，则多元特征值化为普通特征值，不难知道，此时定义2 1 与 已有单特征值的定义一致。 关于多元特征值问题的数值方法 本节以下设a 为a 的单多元特征值，z = 陋 ，z ；，z 翱t 为对应的特征向 量。考虑a 的扰动 a ( t ) = a + t e ， ( 2 3 ) 这里t 为实参数，e 为n 阶实对称矩阵。考虑a ( 亡) 对应的多元特征值系统 其中 a ( t ) a ( t ) = z l ( 亡) z 2 ( t ) z 仇( t ) a l ( 亡) z l ( 亡) a 2 ( t ) z 2 c t ) 入仍( t ) z 仍( t ) a n ( t ) a l ：( t ) a 1 m ( t ) a 2 1 0 ) a 2 2 ) a 2 m ) ； 。 i a m l ( ) 2 ( 亡) a 一( t ) ( 2 4 ) ( 2 5 ) m 如( t ) r 唧唧，唧= 仃，巧( 亡) r 唧， l i x j ( t ) 1 1 2 = 1 ， 歹= 1 ，2 ，m j = l 令 f c y ，弘，t ，= a c t ， ： 一 舶归巨： 那么， ( i ) 显见，f ( y ，p ，t ) 2 乏g ( u ，p ，t ) 都是关于芗，p ，t 的多项式，因而是解析函数。 c n ，o f ，蓁 l 。v ，p 。，；。喾，a 。，= = a adetd e t 一繁z ， ( i i ) 瑟il = 0 叫l ， ，6 啦jl ( v ，p 。t ) = ( 喾，a 0 ) 。 j 关于多垂壁堑垡间壁塑墼笪立鎏 一一 其中b ( z ) = 注意 其中 1 l 舯x m l j d e t 三二声一0 z = c 一1 ，m d e tr 1 a b 扛- ，a t k a 碾 l 1 b ( z ) ? kl j q t b ( x ) 0 p e i l ) fq 。 b ( z ) 1i o j l 【 q 仇 1 kl j 其中q = 【q l q m e 肿i 中* 乩夸一，m ( 2 6 ) ( 2 7 ) 现 l ； ， rj 、i ， 0 b r 1q 且r i i i 一一 并 1j k 0 o 2 2 姚o 峨k p。l = 1il_ilj 0 k p 0 7 q p。l1j p o 8 a 广一 a b pl1j 0 k r q o p 么r l 墨 秀 关于多元特征值问题的数值方法 其中 笼 = 孵c 4 叫酽，尬2 呐矗 由此可得 a e t a - # 一矧- d e t ( a a - k 川 应用隐函数定理，有下述 定理2 1 ：对于给定的实对称矩阵e ，存在正数6 0 ，使得 ， 这里，a l ，q 2 ，为正参数，其适当选择可以带来方便。例如： 取0 f 1 = q 2 = f = 1 ，上述定义的条件数为绝对条件数 ( 2 1 6 ) 取q l i i j , 1 1 2 ，锄= 俪， 专= i i a l l 2 ，上述定义的条件数为相对条件 数 由定理2 1 ，给出，c ( a ) 与，c 0 ) 的显示表达式。 定理2 3 k ( 入) = i 1 “k ，z 1 2 1 1 2 证明 同理可得 k ( a ) = 溉s u ：p g 紫) 2 。腮 紫) = i f 邂f 去l l 厶，历2 】p q t e x l l 2 ) = i 1 | i ，k ，乃2 | 1 2 口 定理2 4 ， k ( z ) = 壶i i m 易l l l 2 从定理2 3 和定理2 4 ，我们看出k ( a ) 和k ( z ) 都与虼1 有关。 推论2 5 k ( 入) 2 言铮砰a 巧奶2 o ( i ，歹= l ，2 ，m ) 证明 k ( 入) = i 1 错互2 = 。 兮饥2 = 0 ( s e e ( 2 1 4 ) ) 砰如巧= 0 ( i ，歹= 1 ，2 ，m ) 口 1 0 ( 2 ，1 7 ) ( 2 1 8 ) 关于多元特征值问题的数值方法 虽然矩阵x ，不能唯一取定，但是易知k ( a ) 和k ( z ) 与玛的选择无关。 注：对于实对称矩阵，w e y l 定理( 【1 8 ，t h e o r e m3 6 】) 保证了所有特征值都是 良态的，但除了平凡情形( 例如a 严格对角占优且对角元彼此很好分离) 外，很 难确定哪类对称阵其特征向量一定是良态的。 对于矩阵奇异值问题有类似结论。由m i r s k y 定理( 1 8 ，t h e o r e m3 1 0 】) 可知 矩阵的奇异值都是良态的，但除了平凡情形外，很难确定哪类矩阵其奇异向量 一定都是良态的。 如果m = 1 ，m e p 转化为对称特征值问题。如果m = 2 且a l l = 厶。，以毖= 厶，m e p 转化为奇异值问题。对于这两种特殊情形，我们知道所有的特征值都 是良态的，尽管特征向量可能是病态的。 结合( 2 1 4 ) 与( 2 1 7 ) ，( 2 1 8 ) 不难看出，对一般的m 和a ，k ( a ) 和k 扛) 都 与m 荔1 有关，这是m e p 的特性之一。如果z 是病态的，则一般而言，入也是 病态的，这与仇= 1 ，及m = 2 且a 1 1 = 厶，a 沈= 厶。的情形明显不同，这是难 以确认哪类a 其对应的m e p 一定良态的重要原因。 2 3扰动理论 这- - , b 节我们分析多元特征对的代数扰动理论。首先我们考虑多元特征对 的扰动上界。 2 3 1 扰动上界 设a 扰动后变为a + a ，考虑非线性系统 i ( a + a ) + z ) = ( a + a ) ( z + z ) ， l ii | 巧+ 巧旧= 1 ( j = 1 ，2 ，仇) 记 一临今一矧一1 1 2 设a 满足 r i i a i l 2 ， d 兰m i n l l a i i f ， 赳 定理2 8 ：如果n ( a 一天) 2 的一般情形，我们很难决定哪类多元特征值问题是良态的，哪类是 病态的。我们观察一个简单的实例，设a = d i a g ( a n ，a 2 2 ) ，那么a 的多元特征 值为a = ( a l ，a 2 ) ，这里a l 和a 2 分别是a 1 1 与a 2 2 的特征值。则所对应的特征向 量可以如下决定 a n x , = a l x , ，a 2 2 x 2 = a 2 x 2 ，1 1 - 1 1 1 2 = 1 1 - - 1 1 2 = 1 如果a 1 1 有很靠近a 1 的特征值，那么对a 1 1 作很小的扰动就会引起z 1 很大的变 化【1 5 1 ，如第三部分的实例3 3 所示。 这个实例说明，如果a 存在很靠近特征值入其它特征值，那么a 和其对应的 特征向量z 对a 的扰动非常敏感，也就是说，( a ，z ) 是病态的。 关于多元特征值问题还存在许多代数理论问题值得深入的研究，比如从数 学角度出发如何决定哪类多元特征值问题是良态就是一个重要但很有难度的问 题。 多元特征值问题的敏度分析具有很重要的实际背景。正如h a n a f i 和t e n b e r g ef 7 】所提到的，多元特征值问题产生于m a x b e t 问题。设y = 陬，玩】是m 组 变量，记x = 阢，】是y 的观测值矩阵。m a x b e t 闯题就是求使线性组 合k 鼢( t = 1 ，仇) 之间达到最大相关性的x i 的值。由h o r s t 算法即知x i 就是多 元特征值问题的解。如果z 是病态的，那么某些线性组合翰就不是合理选择。 也就是说，对x 作小扰动可能使某些戤产生大的误差。 1 6 第三章初始迭代向量选择策略 3 1引言 m a x b e t 是求解广义典型相关分析的一种方法。设五为n n l 实矩阵， 銎。m = n ，则x = 阻，】为n 礼实矩阵设z = p ，z 黝t 是 由h 1 个啦维子向量鼢组成的1 1 维列向量，那么m a x b e t 方法就是在满足约束条 件z 瓤= 1 ，t = l ，2 ，m 下求函数f ( x ) = x t x t x x 的最大值。记a = 一x ，利用l a g r a , n g e ! 乘数法，m a x b e t 方法转化为多元特征值问题m e p ( 1 2 ) ，见 文献【2 ，i 6 。通常情况下，多元特征值问题有多个解，但从实际统计背景考 虑，我们最期望求得全局最大值解。h o r s t 算法( 在【7 ，2 1 】中也称为m a x b e t 算法) 已被胡 1 0 1 ，t e nb e r g ef 1 9 1 ，c h u 和w a t t e r s o n 2 】证明是收敛的，但不能保证 总能收敛到全局最大值解。c h u 和w a t t e r s o n 2 】举出的实例表明h o r s t 方法收 敛到局部最大值解是有可能得。h a n a f i 和t e nb e r g e 【7 1 给出了两条收敛到全 局最大值解的判别准则。s u n 【1 6 】把s o r 加速思想和h o r s t 算法结合起来，提出 了p s o r ( p o w e rs u c c e s s i v eo v e r r e l a x a t i o n ) 方法并证明了收敛性。s u n i 6 通 过数值试验表明p s o r 方法的收敛速度优于h o r s t 算法而且这两种方法的收敛 速度和收敛结果都强依赖于初始迭代向量的选择。因此，如何选择一个合适的 初始迭代向量是值得深入研究的。 3 2选择策略 设a 为n n 实对称正定矩阵且按照( 1 1 ) 分块，贝l j m a x b e t 方法就是求函数 ，( z ) = x ：r a x ，z = 盈彳，z 三j r ，z 双，t ( 3 1 ) 在条件z 甄= 1g = 1 ，m ) 下的最大值。 蒿怒a 诌的c h o l e s k y 分解：a 珏= r 磁。令 a o2 e 1 l 仇1 e 1 m 舢 ( 3 2 ) 关于多元特征值问题的数值方法 要! l j h o r s t 方法和p s o r 方法的初始迭代向量选择如下： 求a 的最大特征值所对应的特征向量2 = 陋 ，碍】t ，令z ( 。) = k ( o 矽，茁5 = ) ? 】t ， 这里 牡 乒篡 3 ， 鲰r 唧为 己，三l j ，氍1 j ，三 j 】t 对应最大奇异值的右奇异向量。 关于此策略的代数理论分析还有待于进一步研究，下面我们通过数值实例 来说明此镱略的有效性。 3 3 数值试验 所有的数值试验是基于m a t l a b6 5 完成的。在叙述计算实例之前， 首先对选择p s o r 方法中的超松弛因子组 越力) 的方案作一说明。在实际计算 时， 叫5 p ) 最简单的取法，是对所有i = l ，2 ，m ，p = 0 ，1 ，2 ，取叫= 叫。 另一种取法如下 岳7 ，q o - - 0 5 , 7 0 8 , 筝冀 4 ， 除了实例3 4 ，下述的实例中的 伽) 都根据( 3 4 ) 来选择。取控制精度e = 1 0 一， 当( ) 一0 n - 1 ) 1 1 2 墨1 0 6 时终止迭代。 例3 i - 此例取自c h u 和w a t t e r s o n 【2 】中： a = 4 3 2 9 9 2 3 2 3 0 1 3 7 1 1 0 0 0 8 4 0 7 4 1 4 2 3 2 3 0 3 1 1 8 1 1 0 9 5 9 0 1 2 8 5 0 0 7 2 7 1 3 7 1 1 1 0 9 5 9 6 4 9 2 0 1 9 8 8 3 0 1 8 7 8 0 0 0 8 4 0 1 2 8 5 1 9 8 8 3 2 4 5 9 1 1 8 4 6 3 0 7 4 1 4 0 0 7 2 7 一o 1 8 7 8 1 8 4 6 3 5 8 8 7 5 m = 2 ，n 1 = 2 ，n 2 = 3 。c h u 和w a t t e r s o n 2 j 说明当随机选择初始迭代 向量，大约有6 0 初始值使h o r s t 算法收敛到全局最大值解。使用p s o r 方 法来计算此例得到类似的结果，计算结果见表3 1 。表3 1 中n o i 初始迭代 向量z ( o ) = f 0 9 7 7 7 ，0 2 0 9 8 ，0 5 0 6 6 ，0 5 0 6 9 ，0 6 9 1 5 t ，n o i i 初始迭代向量z ( o ) = 1 8 关于多元特征值问题的数值方法 表3 1 ：迭代次数 nh 0 r s tm e t h o dp s o rm e t h o d p ( ) ) = m a x z ( ) t 4 。( ) n o i5 73 41 4 7 3 0 2 0 0 4 n o i i 7 63 81 4 1 0 1 3 8 4 8 n o i i i4 72 51 4 7 3 0 2 0 0 4 nh o r s tm e t h o d p s o rm e t h o dp ( z ( ) ) = m a xx ( ) r a 互( ) n o i 7 51 57 4 6 9 4 6 2 3 n o i i1 0 22 27 4 6 9 4 6 2 3 n o i i i9 01 87 4 6 9 4 6 2 3 n o 3 0 1 3 7 4 6 9 4 6 2 3 【o 7 9 1 4 ，0 6 11 4 ， 0 4 7 5 3 ，0 2 5 1 7 ，- 0 8 4 3 1 r ，而n o 。i i i 初始向量根据( 3 ，3 ) 选择。 例3 2 - 此例取s u n 1 6 】中： 其中 a 1 2 = a = 陲 0。；6132360。10。459901 5 705 2 1 i i a 1 2 a a s j 1 3a 2 3 a 磊 厶 0 1 9 5 0 4 5 9 0 2 3 8 l o 7 0 9o 0 5 0 o 。0 0 2 l a 2 3 = 10 0 3 9 0 5 3 20 1 9 0 i 【o 0 6 7 o 2 5 8o 2 9 9 j 计算结果见表3 2 ，其中n o i 初始迭代向量z ( 0 = z 笋= z 字= 去 1 ，1 ，1 】t ，n o i i 初 始迭代向量z 2 d ) = 【1 ，0 ，o 】? ，i o ) = 【o ，一1 ，0 1 t ，z 箩= 击 1 ，0 ，一1 】t ，而n o i i i 初始 向量根据( 3 3 ) 选择。 由表3 1 和表3 2 的结果看出，使用迭代策略( 3 3 ) 后，两种的方法迭代次数都 减少了而且收敛到全局最大值解。 1 9 1lliil-lll-j 9 9 6 5 2 2 0 1 4 0 o 0 6 5 8 2 3 4 6 0 0 0 0 o -。l = 3 1 a 焉| 关于多元特征值问题的数值方法 其中 例3 3 ：多元特征值问题( 1 2 ) q b a 取值如下： a l l 2 a 1 2 a 1 3 a 2 2 ：= a 船 a 3 3 = 钆钆 拈【能a t , 麓a a 船2 3 7 4 4 7 05 3 3 8 7 4 8 9 0 6l 一5 3 3 8 71 3 8 9 0 5 4 5 7 0 4 i ， - 4 8 9 0 64 5 7 0 48 8 4 8 6 l j 1 0 。0 9 0 32 2 4 4 63 6 4 2 1 l - - 1 4 2 6 30 5 2 3 01 8 0 2 0 l ， - - 0 1 5 2 3 - - 0 3 1 4 3 - - 1 6 2 8 8l j 1 0 1 7 5 2 0 0 2 4 61 7 4 3 75 8 0 2 8 l - 3 7 3 9 23 5 6 9 6- - 1 9 9 3 6 - - 8 。1 6 5 0f ， - - 1 3 2 5 00 4 0 1 2- - 2 。7 7 3 0 2 6 1 5 2i 4 4 6 5 3- - 4 2 4 4 2 - - 5 9 2 7 1 i 一4 2 4 4 22 5 9 5 3 2 6 8 7 4 7 f ， l - - 5 9 2 7 1 6 8 7 4 7 1 2 3 4 9 4 i j 1 3 8 0 4 9 - 3 9 6 3 1 5 1 4 4 50 4 0 1 0l - 4 8 9 5 2 - 0 8 5 0 83 9 0 4 5- - 4 8 5 2 6l ， 2 8 8 4 83 0 6 6 43 8 2 4 70 7 8 3 4 1 j 1 1 7 6 0 95 7 0 3 57 7 4 1 1 6 0 9 6 3 5 7 0 3 5 1 2 4 5 1 2- - 1 1 9 2 8 44 7 2 8 9 7 7 4 1 1 - - 1 1 9 2 8 41 6 8 2 8 75 8 4 4 6 6 0 9 6 34 7 2 8 95 8 4 4 6 1 1 6 4 0 3 应用h o r s t 算法，计算结果见表3 3 。其中n o i 初始迭代向量为 z ( 0 = 卜0 1 9 6 0 ，0 7 6 1 8 ，一0 6 1 7 5 t ，z 笋= 0 9 9 6 7 ，一0 0 6 2 3 ，0 0 5 2 0 t ，毋= f 0 7 8 5 7 ，0 0 4 3 7 ，- - 0 0 7 0 4 ，- 0 6 1 3 0 ? ，n o i i 初始迭代向量为 z ( 0 ) = - o 3 1 9 8 ，一0 8 1 6 0 ，0 4 8 1 5 t ，z 笋= 【0 8 2 8 1 ，一0 3 0 4 0 ，0 4 7 1 1 t ，毋= 【- 0 1 5 0 7 ，0 4 0 5 5 ，- - 0 5 2 2 5 ，- 0 7 3 4 8 t ，n o i i i 初始迭代向量为 _。o。l。l，。，。l i_。l r。l p。i 关于多元特征值问题的数值方法 2 ( o )n z 【) z 写) a ( ) p ( z ( ) = m a x z ( ) t i x ( ) 0 6 3 9 30 4 8 2 10 4 8 9 62 5 4 3 2 9 - 0 6 1 0 20 4 0 9 2 0 4 4 3 5 2 8 8 6 7 9 n o i3 2o 4 6 8 00 7 7 4 70 5 ( 培74 1 7 4 1 79 6 0 4 2 4 9 略 0 5 5 6 7 0 5 7 8 9 0 1 2 7 00 3 9 6 1 2 3 0 8 9 5 o 6 2 0 9 8 6 40 5 2 7 93 3 3 2 5 2 n o n2 30 5 2 8 9- o 1 0 4 2- 0 7 3 7 94 1 2 3 0 89 7 6 4 5 5 2 9 l 0 1 4 0 9 - o 2 9 3 3 0 5 5 1 9 0 2 3 7 52 4 7 5 2 1 o 8 6 4 80 5 1 9 8 o 6 3 8 8 3 0 7 4 8 7 n o i3 6o 如7 50 6 5 2 0- 0 7 2 3 53 8 2 3 1 69 3 7 3 2 3 6 3 2 0 1 0 9 9 0 3 7 4 6 - 0 0 1 6 70 5 3 3 8 2 5 8 7 8 4 o 8 4 6 5o 9 9 5 8o 2 7 4 63 3 9 5 6 0 n o 2 5o 3 7 8 20 0 9 o 4 2 3 34 3 8 5 1 81 0 3 6 8 6 2 9 8 3 0 6 7 8 5 z ，) = 0 7 8 0 4 ，一0 3 5 0 7 ，一0 5 1 7 8 1 t ，z 笋= - 0 1 9 4 3 ，一0 9 6 8 8 ，一0 1 5 3 7 t ，z 字= 【0 0 7 7 8 ，0 2 0 6 7 ，0 9 4 7 7 ，- 0 2 3 0 4 1 r ，而n o i v 初始迭代向量根据( 3 3 ) 选择 由表3 3 可以看出，m e p 可能存在多个局部极大值点。我们随机产生初始 向量后，使用h o r s t 算法计算本例，结果是，大约只有1 3 的初始向量收敛到全 局最大值解。而使用我们给出的选择策略( 3 3 ) ，h o r s t 算法能够稳健的收敛到全 局最大值解。使用p s o r 方法计算本例，得到类似的结果。 例3 4 ：多元特征值问题( 1 2 ) 中a 取值如下：a = 这里a l l = 222 2 54 2 45 a n 00 0 a 2 2 a 2 a 0 a 磊a 3 3 ，a 2 2 = 2 ，a 2 3 = c 一1 ，叫，a = 三1 1 使用h o r s t 方法和p s o r 方法计算本例，结果表明当取 z ( o ) = - 0 6 9 1 7 7 5 ，0