（电路与系统专业论文）对称矩阵特征值分解的硬件实现研究.pdf

浙江大学硕i 二学位论文 摘要 矩阵特征值分解被应用于科研和工程的很多领域，如主成分分析算法、人 工视觉等因此，对矩阵特征值分解的硬件实现进行研究，寻找一种较好的硬 件实现策略具有十分重要的意义。 在现有的矩阵特征值分解算法中，乘幂法适合于求解稀疏矩阵的主特征值， 反幂法适合于知道矩阵特征值求解相应特征向量的情况，而作为乘幂法推广的 子空间迭代法非常适合于求解大型稀疏矩阵的特征值。对于对称矩阵，有三种 方法可以求解其特征值：j a c o b i 旋转法、单侧旋转法和q r 方法。j a c o b i 旋转法 在利用矩阵的正交变换对矩阵进行对角化求取矩阵特征值，并且在求解特征值 的同时可以很方便的利用正交变换求解出特征值对应的特征向量。单侧旋转法 是j a c o b i 方法的变形，它只利用单侧旋转来先求取矩阵特征值的平方，再求取 矩阵的特征值。q r 方法是基于q r 分解的一种求取矩阵特征值的方法，它将 矩阵通过分解变成一个上三角矩阵，然后求解其特征值。 对于j a c o b i 算法的硬件实现，论文经过分析总结提出了两种大的结构：串 行计算机构和并行计算结构。串行计算结构又根据具体计算过程的不同分成了 两种方法，一种方法是先寻找矩阵非对角元素的最大元，然后对其相应的行列 进行j a c o b i 旋转；另一种方法是通过遍历的方法来对矩阵的行列依次进行j a c o b i 旋转。并行计算结构是一种阵列型的结构，它由对角线处理单元和非对角线处 理单元通过一定的连接组成，每个处理单元处理四个矩阵元素，在一次处理后 跟相邻的单元进行数据交换进行新的一次计算。 c o r d i c 算法将一个向量b ，y 】旋转矽角度分解成连续的 + a r c t a n 2 一( 汪0 ，1 ，6 ) 角度的旋转。利用它可以将每次j a c o b i 运算转换成只有加 法和移位的多次迭代运算和一个比例因子的缩放运算。它非常适合应用于对 j a c o b i 算法的硬件实现。 论文通过c o r d i c 迭代来实现j a c o b i 算法的两种计算结构，利用 v e r i l o g h d l 来进行硬件实现描述，然后对设计进行了验证和数据采集，通过几 种结构的性能对比，确定并行计算结构为最佳实现方案。 关键词：对称矩阵，特征值计算，j a c o b i 算法，c o r d i c ，硬件实现 浙江大学硕l - 学位论文 a b s t r a c t e i g e n v a l u ed e c o m p o s i t i o no fm a t r i xi ss i g n i f i c a n tf o rm a n ya r e a si nb o t h s c i e n c er e s e a r c ha n de n g i n e e r i n g ，s u c ha sp r i n c i p a lc o m p o n e n ta n a l y s i s ，a r t i f i c i a l v i s i o na n ds oo n s o ，i t sv e r y i m p o r t a n tt h a tr e s e a r c h i n gt h e h a r d w a r e i m p l e m e n t a t i o no ft h ee i g e n v a l u ed e c o m p o s i t i o na n df i n d i n gab e r e rh a r d w a r e i m p l e m e n t a t i o n i np r e s e n ta l g o r i t h m so fm a t r i xe i g e n v a l u ed e c o m p o s i t i o n ，t h ep o w e rm e t h o di s v e r ys u i t a b l ef o rs p a r s em a t r i xa n di n v e r s ep o w e rm e t h o di su s e dt oc a l c u l a t et h e e i g e n v e c t o ri ft h ee i g e n v a l u eo ft h em a t r i xi sc a l c u l a t e d ，w h i l es u b s p a c ei t e r a t i o n m e t h o di sv e r ys u i t a b l ef o rc a l c u l a t et h ee i g e n v a l u eo fl a r g es p a r s em a t r i c e sa st h e e x t e n do fp o w e rm e t h o d f o rs y m m e t r i cm a t r i c e s ，t h e r ea r et h r e em e t h o d st o c a l c u l a t et h e i re i g e n v a l u e ，j a c o b ir o t a t i o nm e t h o d ，o n e s i d er o t a t i o nm e t h o da n dq r m e t h o d j a c o b ir o t a t i o nm e t h o du s e st h em a t r i xo r t h o g o n a lt r a n s f o r m a t i o nt o d i a g o n a l i z et h em a t r i xt oc a l c u l a t et h ee i g e n v a l u e ，w h a t sm o r ei t sv e r yc o n v e n i e n t t o g e tt h ee i g e n v e c t o ro ft h ec o r r e s p o n d i n ge i g e n v a l u e t h eo n e s i d er o t a t i o n m e t h o di st h ee x t e n do ft h ej a c o b im e t h o d ，i to n l yu s e st h eo n e - s i d er o t a t i o nt o c a l c u l a t et h es q u a r eo ft h ee i g e n v a l u ea n dt h e ng e tt h ee i g e n v a l u e t h eq rm e t h o d i sb a s e do nq rd e c o m p o s i t i o na n di t d e c o m p o s e st h em a t r i xt oau p p e rt r i a n g u l a r m a t r i x ，t h e nc a l c u l a t et h ee i g e n v a l u eo ft h em a t r i x f o rt h eh a r d w a r ei m p l e m e n t a t i o no fj a c o b ia l g o r i t h m ，t w oa r c h i t e c t u r e sa r e d e m o n s t r a t e da f t e ra n a l y s i s ：s e r i a lc o m p u t i n ga r c h i t e c t u r ea n dp a r a l l e lc o m p u t i n g a r c h i t e c t u r e s e r i a lc o m p u t i n ga r c h i t e c t u r ei sd i v i d e dt ot w ow a y s ，f i r s tw a y ：f i n d i n g t h em a xe l e m e n to ft h en o n d i a g o n a le l e m e n t so ft h em a t r i xa n dt h e np u t t i n gj a c o b i r o t a t i o nt ot h ec o r r e s p o n d i n gr o w sa n dc o l u m n s ，s e c o n dw a y p u t st h ej a c o b ir o t a t i o n t ot h er o w sa n dc o l u m n si nt u r na c c o r d i n gt ot h ea l lo v e rm e t h o d t h ep a r a l l e l c o m p u t i n ga r c h i t e c t u r e i sa na r r a ya r c h i t e c t u r e ，i ti sc o n s i s t e dw i t h d i a g o n a l p r o c e s s i n gu n i t sa n dn o n - d i a g o n a lp r o c e s s i n gu n i t s ，o n ep r o c e s s i n gu n i tp r o c e s sf o u r m a t r i xe l e m e n t sa n de x c h a n g ei t sd a t aw i t ht h en e i g h b o r p r o c e s s i n gu n i t s t h ec o r d i ca l g o r i t h mi su s e dt ot r a n s f o r mt h e 秒a n g e lr o t a t i o no ft h e v e c t o r x ，y 】t os u c c e s s i v e + a r c t a n2 叫( 江o ，1 ，6 ) a n g e lr o t a t i o n t h e n o n e j a c o b ir o t a t i o ni st r a n s f o r m e dt ot h ei t e r a t i o n so fo n l ya d d i n ga n ds h i f t i n gf l o w e db y as c a l i n g i ti sv e r ys u i t a b l ef o rt h eh a r d w a r ei m p l e m e n t a t i o no ft h ej a c o b i a l g o r i t h m t w oc o m p u t i n ga r c h i t e c t u r e sw e r ei m p l e m e n t e db yv e r i l o gh d lw i t hu s i n g i i 浙江大学硕 ：学位论文 c o r d i ca l g o r i t h m t h ep e r f o r m a n c eo ft h e s em e t h o d sw e r ec o m p a r e da f t e r v e r i f i c a t i o na n dd a t ac o l l e c t i o n a n df i n a l l y , t h ep a r a l l e lm e t h o di sp r o v e dt h eb e s t m e t h o dt oi m p l e m e n tt h ej a c o b ia l g o r i t h m k e y w o r d s ：s y m m e t r i cm a t r i x ，e i g e n v a l u ec a l c u l a t i o n ，j a c o b ia l g o r i t h m ，c o r d i c ， h a r d w a r ei m p l e m e n t a t i o n 。1 1 1 。 浙江人学硕l j 学化论文 插图清单 图3 - l 方法1 的基本实现结构2 7 图3 - 2 方法ic o m p u t et 模块结构2 8 图3 - 3 方法1 c o m p u t es ，c 模块结构一2 8 图3 4 方法i c o m p u t eo f f - d i a g o n a l 模块结构2 8 图3 - 5 方法1 c o m p u t ed i a g o n a l 模块结构2 9 图3 - 6 方法l 运算部分结构的流水级划分3 1 图3 - 7 处理单元p 的对角式的输入和输出一3 2 图3 - 8 各个处理单元间的对角连接关系， n - - 8 ，一3 3 图3 9 处理单元的距离3 5 图3 1 0 典型的对角和非对角处理单元的输入和输出3 5 图3 - 1 1 处理单元内部工作说明3 6 图3 - 1 2 适用于对称矩阵的处理单元阵列3 7 图4 - lj a c o b i 串行计算方法1 系统状态转换图4 0 图4 - 2 矩阵特征值计算的硬件结构4 l 图4 1 3c o r d i cd 的内部结构4 3 图4 4c o r d i cn d 的内部结构一4 3 图4 - 5 方法1 经过改进后的实现结构4 4 图4 - 6c o n t r o l u n i t 的状态转换图4 5 图4 - 7 方法2 的硬件实现结构4 6 图粕方法2 的硬件实现结构的状态转换图4 7 图佃改进后的处理单元接口示意图4 8 图4 - 1 0 改进后的处理单元连接图，n = 8 4 9 图4 - 1 1p l 的实现结构5 0 图4 - 1 2 ( f 1 ) 的实现结构5 0 图4 - 1 4 非对角处理单元实现结构图5 2 一v l 浙江人学硕i j 学位论文 表清单 表格4 - 1c o r d i c 迭代次数b 与对应的l ( b 4 2 表格4 - 2 实验用到的数据5 3 表格4 - 3 计算得到的矩阵特征值5 3 表格不同方案的实现性能比较5 4 表格4 5 不同方案的性能参数5 4 一v 1 l 一 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得浙江太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期：2 0 0 8 年月 日 学位论文版权使用授权书 本学位论文作者完全了解逝江太堂有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堑塑太堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：年月日 导师签名： 签字日期：年月日 致谢 时光荏苒，岁月如梭。转眼间在浙大六年的时光即将结束。承蒙师长六年来 的殷勤的教诲和关怀、同学们朋友们六年来热心的照顾和关心，我在学业上为人 上都取得了长足的进步。 在此衷心感谢我的导师沈海斌老师，两年多来，沈老师以丰富的学识和超前 的理念，给予我学习和生活上的关怀和鼓励。不仅指导了我本科的毕业设计，而 且本次毕业设计的选题、收集材料、日常讨论到最后定稿，都包含了他的大量帮 助和指导。 还要感谢实验室的严晓浪老师、吴晓波老师、王国雄老师和史峥老师，感谢 你们对我本科四年的教诲和关怀；感谢罗晓华老师，怀念我们一起踢球的快乐； 感谢竺红卫老师在学业上的指导。 在此特别感谢侯咏佳同学，你给了我的毕业设计很多建设性的建议和实际的 帮助；还要感谢实验室同期毕业的李刘林，王嗣平、胡欣幸、周功待、刘洪庆、 金轶安、杨宇、朱禹、张倩、梁田、张昀等同学，感谢你们两年来对我生活和学 习上的照顾；感谢即将毕业的陈华锋师兄、楼斌师兄，感谢还在实验室深造的周 喜川、曹葵康、董文箫师兄，感谢你们平时对我项目和学习上的指导和帮助；还 感谢研究所的其他同学，名字不一一列举，与他们一起度过了很多美好的时光； 你们的友谊是我一生的财富。 感谢浙江大学超大规模集成电路研究所，宽松的环境使我能够安心投入到学 习和工作当中去。还要感谢浙江大学，从2 0 0 2 年1 0 月本科入学到2 0 0 8 年7 月 硕士研究生毕业也有近六年光阴，从紫金港校区到玉泉校区，优雅的学习环境让 我度过了人生中的一段美好而难忘的时光。 感谢我的父亲和母亲多年来对我默默的支持和悉心的照顾，没有你们，就没 有我的今天；感谢我的姐姐给了我很多生活上的照顾和人生的启示；你们是我内 心深处永远的港湾。还要感谢我的女友给我的无私的关怀、细心的照顾和默默的 支持。 最后再次感谢所有关心我支持我的人! 袁生光 2 0 0 8 年6 月于浙大求是园 浙江人学硕 j 学位论文 第1 章绪论 1 1 研究背景 随着社会信息化的发展，人们所要面对和处理的信息越来越多，信息与信 息之间的相关性变得越来越复杂，如何通过有效的手段来理清各种各样数据之 间的关系、使之简化为较少的较简单的数据来分析称为很多统计工作研究的重 点。 在处理有很多方面指标数据的问题时，我们常常会遇到影响此问题的很多 变量，这些变量多且又有一定的相关性，因此我们希望从中综合出一些主要的 指标，这些指标所包含的信息量又很多。这些特点，使我们在研究复杂的问题 时，容易抓住主要矛盾。 那么怎样找到这些综合指标呢? 主成分分析【1 1 ( p c a ：p r i n c i p a lc o m p o n e n t a n a l y s i s ) 可以帮助我们来完成这个工作。主成分分析通过对一组变量的几个线 性组合来解释这组变量的方差和协方差结构，以达到数据的压缩和数据的解释 的目的。 若有一些指标x ，墨，取综合指标即它们的线性组合f ，当然有很多， 我们希望线性组合f 包含很多的信息，即v a r ( f ) 最大，这样得到f 记为曩，然 后再找互， e 与最无关，以此类推，我们找到了一组综合变量巧，e ，吒， 这组变量基本包含了原来变量的所有信息，称为主成分。 1 2 主成分分析的数学模型、几何解释和推导过程 主成分分析的数学模型、几何解释和推导过程【2 】如下： 1 、数学模型 浙江大学硕一l j 学位论文 设样本资料阵为： 综合指标为 州讪如喝，仨： 鼻2q 1 + 口2 l x 2 + + 口p l x p ： 匕= a l m x l + c t 2 x 2 + + ，o 简写为 e = q f 五+ a 2 ，x 2 + + 口x p ， ( f = l ，聊) 并取订i ：+ + = l 要求( 1 ) z ，f j 不相关。( 2 ) 互是x i ，k 的线性函数中方差最大的， 依此类推。 2 、 主成分的几何意义： 设有n 个样品，每个样品有两个观测变量五，x 2 二维平面的散点图。n 个 样本点，无论沿着x l 轴方向还是x 2 轴方向，都有较大的离散性，其离散程度 可以用置或置的方差表示。 当只考虑一个时，原始数据中的信息将会有较大的损失。若将坐标轴旋转 一下：互= 五c o s o + x 2s i n oe = x is i n 0 + x 2c o s 0 即f ，e = x t c 。s o + x z s i n o l ( x ) ：u x l e = 以ls i n 0 + 五2c o s o j c x , 且有u u = ，即u 是正交距阵，则n 个样品在互轴的离散程度最大( 方 差最大) ，变量互代表了原始数据的绝大部分信息，即使不考虑e ，信息损失 一2 一 浙江人学硕i ：学位论文 _ 一一 也不多。而且e 、e 不相关。只考虑e 时，二维降为一维。 3 主成分的推导。 那么如何求主成分呢? 根绝线性代数里面的定理l ：若a 是p 阶买对称阵， 一定可以找到正交阵u ，使u a u = 以曙( a ，五，以) ，其中 ，五，t 是a 的 特征根；和定理2 ：若上述a 的特征根所对应的单位特征向量为1 2 1 , 屹，z ，p ， 记u = ( ，砧：，甜p ) ，则不同特征根对应的特征向量正交，即甜：“= o 。 记x ：( 五，恐，x p ) ，设，= q 而+ + 口，x p = 口x ，找到系数口( a a = 1 ) ，使 v a r ( f ) 最，即v a r ( f ) = v a r ( a x ) = 口v a t ( x ) = a 口最大。 根据定理：设的特征根为 五以 0 ，对应的标准正交基为 ，1 2 ，“p 。 则v a “f ) ：丑，口；，记e = x ， 历与巧无关，e 2 x 舅为第一 主成a ，e 黼二主成分q 黼旌成分。称刍黼一主成分 的贡献率。 若m 个主成分的累计贡献 率超过8 5 ，那我们认为前m 个主成分基本包含了原来指标信息。 设有n 个样品，p 个指标，得到的原始资料矩阵为x = 三：j j 二 ，记 一3 一 率献贡汁累的分成主 个m前为 五一五 ，丛p瑚 称 浙江人学硕l ：学位论文 s 5 击喜c 和盹一_ ) i = 去喜2 ，p 州，勺2 南 其中s 是样本协方差阵，为总体协方差阵的无偏估计。r 是样本相关矩 阵，为总体相关矩阵的估计，为了避免指标的差异和量纲的不同，较合理的做 法是用r 代替。 1 3 国内外研究现状 目前，关于矩阵特征值分解硬件实现的研究集中在对j a c o b i 算法的并行处 理研究上【2 1 ，标准的矩阵特征分解算法在文献 3 1 q h 被提及，而文献【4 】和文献【5 】 分别对其进行了实现。但是，由于由于并行计算的兴起，所以人们将注意力开 始转向如何通过并行的方法求取矩阵的特征值。文献 6 】提出了采用脉动阵列的 结构实现矩阵的特征值求解，并给出了每个处理单元的结构和工作过程，文献【7 】 给出了阵列结构的改进方法，并提出了在f p g a 上的实现方案。c o r i d c 算法 1 8 】非常适合应用于矩阵特征值计算，文献【9 提出了应用矩阵特征值分解的 c o r d i c 算法的实现，文献【1 0 】给出了如何优化c o r d i c 算法的实现，而文献 【l l 】提出了在线c o r i d c 算法，文献 1 2 】提出了c o r i d c 算法中如何使用常数来 进行缩放运算。结合c o r d i c 算法，文献 1 3 提出了j a c o b i 算法的一种实现结 构，而文献【1 4 】在此基础上提出了j a c o b i 算法在f p g a 上的实现结构，并给出 了性能的分析和评估。更近一步，文献 1 5 1 和 1 6 1 分别提出了近似j a c o b i 算法来 减小j a c o b i 算法的计算量，文献 1 7 1 还提出了近似j a c o b i 算法和c o r d i c 算法 的结合，文献 18 】提出了应用可以应用于于任意矩阵的近似j a c o b i 算法。文献 【1 9 】提出了一种在f p g a 上的近似j a c o b i 算法的实现方案。 1 4 研究内容和选题意义 1 本文研究内容： 从上述对p c a 的描述中可以看出，如何求取矩阵的特征值是整个主成分 分析算法的关键。并且在很多科研和工程领域都要用到矩阵特征值分解，比如 人工视觉、数字信号处理等。 对一个矩阵a r ”( i n n ) 特征值( 又叫奇异值) 分解( s v d ：s i n g u l a rv a l u e - 4 - - 浙江人学硕l ：学位论文 d e c o m p o s i t i o n ) 2 0 定义是由下面式子给出的： a ：u yv 7 ( 1 1 ) 这里u r ” 、v r “” 都是 正 交矩阵 ， = d i a g ( a 。，吒) r m 。n ，q 吒0 。q 被称为是矩阵a 的特征值，u 和v 的列被称为是矩阵a 的左特征向量和右特征向量。 本文通过对现有矩阵特征值分解算法的研究和分析，选出一种适合于p c a 计算和硬件实现的算法：j a c o b i 算法【2 1 1 结合c o r d i c t 2 2 1 旋转来进行矩阵特征值 计算，然后对其串行处理和并行处理两种不同体系结构进行了硬件实现，通过 比较其在相同计算精度控制下处理的速度和占用的面积的比较，结合制定的权 衡方案来选出一种较好的实现结构。 2 本文选题意义： 矩阵特征分解中在p c a 过程中具有十分重要的意义，起到核心作用。其性 能的优劣直接影响整个p c a 的性能。所以，研究分析来选取一种比较适合于硬 件实现的矩阵特征分解算法，并找到其较好性能的设计就可以使整个p c a 过程 得到性能上的提升。 用硬件实现时，面积、速度、精度三个参数相互制约，如果能找到一个算 法结构，在满足应用要求的情况下，尽量减少实现的面积、提高速度和精度， 这样可以降低硬件成本，提高p c a 计算的性能。 1 5 论文章节安排 全文共分为六章，各章节的规划如下： 第一章介绍了主成分分析的基本原理，提出了本研究的应用场合和应用背 景，陈述本研究的研究内容和选题意义。 第二章介绍了现有常见的矩阵特征分解算法的原理，并对每种算法的计算 过程和计算性能做了一些分析，提出了每种算法适合的应用场所和应用环境。 第三章先对j a c o b i 算法进行了介绍，然后提出了两种计算结构，并提出了 两种结构的几种实现方案，接着介绍了j a c o b i 硬件实现的时候常用的c o r d i c 算法。 一气一 浙江人学硕一l 二学位论文 第四章结合c o r d i c 算法提出了上一章的应用j a c o b i 算法提取矩阵特征值 的几种方案的硬件实现结构，并对几种实现结构的性能做了对比和分析，选出 了最佳的实现结构。 第五章给出了论文的总结，和对对称矩阵特征分解的硬件实现的进一步设 想。 一6 一 浙江大学硕上学位论文 第2 章矩阵特征值分解算法 2 1 矩阵特征值基本理论 设a 为刀阶方阵，a - - ( a 口) r ，若x 尺”( x o ) ，有数旯使a x = 2 x 则称 兄为爿的特征值，x 为相应于五的特征向量。因此，特征值问题可以归结为求a ， 满足妒( 五) = d e t ( a 一甜) = 0 。称缈( 名) 为么的特征多项式，它是关于旯的以次代 数方程。 这里先介绍一些关于矩阵的特征值的一些代数理论：1 设矩阵a ，b e r 一柳，若有可逆阵p ，使b ：尸- 1 a p 则称么与召相似。2 若矩阵a ，b e r 珂瑚且相似， 则( 1 ) 彳与b 的特征值完全相同；( 2 ) 若x 是b 的特征向量，则p x 便为么的 特征向量。3 设彳猷嗍具有完全的特征向量系，即存在刀个线性无关的特征向 量构成的一组基底，则经相似变换可化么为对角阵，即有可逆阵p ，使 p a p ：d ：其中以为彳的特征值，p 的各列为相应于丑的特征向 量。彳e rn x l l 五l ，厶为4 的特征值，则( 1 ) 么的迹数等于特征值之积，即 护( 彳) 兰= 乃( 2 ) 么的行列式值等于全体特征值之积，即d e t ( a ) = a 1 乃。 i = li = l 4 设彳欲开柳为对称矩阵，其特征值五l ；t 2 厶，则( 1 ) 对任彳酿月，x 0 ， 厶器洲2 悱嘧等( 3 ) 丑= 学篱。5 黝扩删( 1 ) a 的每一个特征值必属于下述某个圆盘之中，k a i i l k i ，i = 1 ，2 ，刀上式 ，= l j 翻 表示以o i i 为中心，以半径为k i 的复平面上的刀个圆盘。( 2 ) 如果矩阵a 的 = ! j i 朋个圆盘组成的并集s ( 连通的) 与其余刀一埘个圆盘不连接，则s 内恰包含m 个么的特征值。 下面几节来求解矩阵特征值的几种基本方法。 一7 一 浙江人学硕 ：学位论文 2 2 乘幂法与反幂法 在有些工程应用中，只需求解矩阵的按模最大或前几个按模最大特征值及 相应的特征向量问题，或称为求主特征值问题。对这些问题，采用乘幂法和反 幂法能够达到很好的效果。 2 2 1 乘幂法 乘幂法【矧的计算公式为： 设么酿刀柳，取初始向量o ) e rn ，令1 ) = 彳石( o ) ，x ( 2 ) = 彳，一般有 x ( 2 ) ：础f ( 七一1 )( 2 1 ) 形成迭代向量序列 x ( k ) 。由递推公式( 2 1 ) ，有 x = a ( a x ( 一2 ) = 彳2 1 ( 2 2 ) = a k x ( o ) 这表明d 是用彳的k 次幂左乘x ( o 得到的，因此称此方法为乘幂法，( 2 。1 ) 或( 2 2 ) 式称为乘幂公式， x ( 旬) 称为迭代序列。 下面对乘幂过程进行分析，即讨论当后一时， x ( d ) 与矩阵a 的主特征值 及相应特征向量的关系。 设a = 0 小朋有完全的特征向量系，且力l ，屯，厶为彳的刀个特征值，满 足 i i i 如i i 丸i 1 ，l ， v 2 ，v n 为相应的特征向量且线性无关，从而构成上的一组基底。 对任取初始向量o ) r 一，可由这组基底展开表示为 x ( o ) = 嘶l + v 2 + + 屹 ：窆吼 他3 j = l 其中o t l ，眈，c r n 为展开系数。将o ) 的展开式( 2 3 ) 代入乘幂公式( 2 2 ) 中，得 一8 一 浙江人学顾l j 学位论文 有 此时 x 仕) - 彳q ，= a j ( 4 k v j )z 一 jj 3 = 1j = l 利用 a k l ，_ ，= 乃v j ( 2 4 ) 式为 x 似) = 哆穆v = l ( 2 4 ) ( 2 5 ) 下面分两种情况讨论： 1 如果彳有唯一的主特征值，即i i i 如l ，设旯l 0 ，且由( 2 5 ) 式， 其中气= 酬t = 2 妒于洳驴2 m 故当七充分姚删， x 仲) 前，1 ( 2 6 ) 对f = 1 ，2 ，n ，若( a i r l ) ，0 ，考虑相邻迭代向量的对应分量比值， 掣掣! 蛐l 五 x r 。前( 口1 1 ，1 ) j 1 即对i = 1 ，刀 2 鳃带= 五 ( 2 7 ) ( 2 8 ) 这表明主特征值也可由( 2 7 ) 或( 2 8 ) 式得到。 由于迭代序列劫，当k 充分大时，( 2 6 ) 式成立，与v 1 只相差一个常 数因子，故可取动作为相应于主特征值五l 的特征向量的近似值。 i 迭代序列七的收敛速度取决于l 车l 的大小。 1 1i 2 如果a 的主特征值不唯一，且i 五i = l 如l i 五l 可分三种情况讨论： 一9 一 p 、 - 一 ，一 口 。戽私 + h h 口 一一 前 前 = = 似 x 浙江人学硕， ：学位论文 a ) 五i = 如；b ) 名i = 屯；c ) = 名2 a ) 当兄l = 如时，么的主特征值为二重根，根据( 2 4 ) 式 当k 充分小时， + a 2 v 2 + j = 3 + 1 2 + 唧) 矧膏v 1 由于i 砉i t ：t ，= = 3 ，c k o , 贝u x 钟( 口l v l + 口2 v 2 ) 对i = 1 ，2 ，行，如果( 口1 1 ，l + 口2 1 ，2 ) l ；c o ，则 ( 主特征值) 且x 七) 收敛到相应于五l ( _ 屯) 的特征向量的近似值。 这种重主特征值的情况，可推广到a 的，重主特征值的情况，即当 = 五= = 4 且 i 乃“j 时，上述讨论的结论仍然成立。 b ) 当名l = 屯时，彳的主特征值为相反数，( 2 5 ) 式为 x 似= 前v l + 口2 篇v 2 + 当七充分大时， = 硝1 ，l + ( 一1 ) 。口2 前 ， 斗”舳奶 ，# 3 = ( 口l v l + ( 一1 ) 吃，2 + & ) j 见k j 1 yj 盼1 和小3 ，4 ，- - , r , 8 k o , 则 x 。名( 口l v i + ( 一1 ) 2 0 t 2 v 2 ) ( 2 9 ) 由于( 2 9 ) 式中出现因子( 1 ) 七，则当七变化时，出现振荡、摆动现象， 不收敛，利用( 1 ) 七的特点，连续迭代两步，得 一l o h h 口 哟 一 一心 前 前 = i i 似 x 丑 坐 暑一 矿 矽。 口 同 口 ，分厶 2 浙江大学硕j j 学位论文 x “1 珥+ 2 ( ，l + ( 一1 ) “2 口2 v 2 ) = 硝“2 ( 1 ，l + ( 一1 ) 6 t 2 v 2 ) 从而，对i = 1 ，2 ，疗，若( 口i ，l + ( 一1 ) 口2 2 ) ，o ，则 开方之后，便得到a 的以上主特征值五l ，a 2 = 五1 为计算相应于旯l ，屯的特征向量，采取组合方式， x + _ x 七2 名m ) t z l v l = c i ，l x “n 一五x ( 一1 ) “12 雹“1 v 2 = 四y 2 可见础v 。，q v ：分别为相应于丑与如的特征向量。 c ) 当 = 五z 时，a 的主特征值为共轭复根。 因彳为实矩阵，j ：彳，于是由 有 a v l = v l a v l = a v l = 五v i 即一v i = ，2 ( 1 ，l 与v 2 为互为共轭向量) 。 设五= p e 坩，五= p e 卅，对任取x o 尺月，展开式( 5 7 ) 可为 x ( m = o r l v l + 一c t l ；l + 将( 2 1 3 ) 式代入( 2 5 ) 式， q j x = q 前v l + 云l 壁；l + a j 穆1 ， = a l p k e i k 8 v 1 同理，当k 充分大时 x 七p 七( 口l v l e 脚+ 一t z i ；l 口删) 1 1 一 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 砰 坐 量一 芦 矿 七 、，-、 乃一p ，l 口 。声 p + 2 矿 p 3 腑 = 一 ， p 七 p 一口+ 浙江人学硕l ：学位论文 对歹= 1 ，2 ，n ，设复数表示 ( 口i v l ) = 0 e 衄，( 口。v 。) j = 0 e 一印 则( 2 1 4 ) 式的复数表示可为 工( s e 即“口+ s e 一州一) 连续迭代，得 l z 2 p ，= c o s ( o + k o ) x “2 p “1 r je o s ( o + ( k + 1 ) 0 ) ( 2 1 5 ) l x + 2 2 户+ 2 ，：fc o s ( 伊+ ( 后+ 2 ) 秒) 利用三角函数运算性质及五l 、屯的复数表示，不难验证。 x + 2 - ( 4 + 五) x + 1 + 五苟o 令 p = - ( a - i - 如) ，q = 如 解方程( = 1 ，2 ，珂) x + 2 + + 弘= o 求出口q 后，再解出主特征值五l ，如，得 ( 2 1 6 ) ( 2 1 7 ) 同样，采取组合方式求相应于名。、如的特征向量。由于 x ( 川) 一如x ( 七) 彳( 一如) 口l ，l = c ：v 1 ( 2 1 9 ) x ( + n 一 x ( 。) 篇( 五一 ) 口2 v 2 = c ；，2 ( 2 2 0 ) 则可分别取( 2 1 9 ) 、( 2 2 0 ) 左端的组合表达式作为相应于名l 、如的特征向 量的近似值。 通过以上分析，可以得出以下结论： 设4 柳有完全特征向量系，若允l ，如，厶为么的力个特征值且满足 川i 如l i 丸l ，对任取初始向量o ，对乘幂公式x 川= 血”确定的迭 一12 一 厨丽 l p 一2 p 一2 一 浙江大学硕+ t ：学位论文 代序列 ，有下述结论： ( 1 ) 当i i l 如l 时，对f = 1 ，2 ，胛2 翌专万= ，收敛速度取决于 ( 七+ ，= l 鲁i 1 的程度， l 五i 时， a ) 若五l = 如，则主特征值五l 及相应特征向量的求法同( 1 ) ； b ) 若 = 五2 ，则连续迭代两次，计算出x ( k + 1 ) ，x ( k + 2 ) ，然后对j = 1 ，2 ，n 解方程 矿+ 2 + 彤+ 私。= o 求出p 、q 后，由公式 仁詈+ ，阿仁詈一，丽 解出主特征值兄、如。此时收敛速度取决于，= l 鲁i 1 的程度。向量 石( “n 一厶x ( n 、x ( 川) 一无x ( t ) 分别为相应于丑，如的特征向量的近似值。 c 啪t 一屯巾乩2 ，叫骢等收敛速度取决协阱1 的 程度。向量x “1 + 如x 、x ( k + 1 ) 一 x 七) 分别为主特征值旯l 、如相应的特征向量 的近似值。 从分析乘幂过程可见，乘幂法可以用于求矩阵按绝对值最大的一个或几4 - 特征值及相应的特征向量，当比值，= l 鲁l i 如i i i 时， - 1 4 - 浙江火学硕i j 学位论文 乘幂法的收敛速度由，= 斟决定，l 收敛得快。因此为提高收敛速度或改 善，1 的状况，可以采取原点移位的方法【2 5 1 ，改变原矩阵a 的状态。 取凡( 常数) ，用矩阵b = 爿一来代替a 进行乘幂迭代。设雎( 卢1 ，2 ， 力) 为矩阵b 的特征值，则b 与a 特征值之间应有关系式： 鸬= 丑一九( f = 1 ，2 ，疗) 且若v ，是a 相应于 的特征向量，则亦是触的特征值，即对i = 1 ，2 ，以 b v ，= ( a a o i ) v ，= a v f 一九，f = ( 丑一九) ，f 因此，对任取| o ) ，关于矩阵b 的乘幂公式( 2 2 ) 可为 x 七= b x o = ( 么一气工o 叫卜刊补 = c 一厶，。i 口i v l + 口，。2 五j 一- 厶厶， 2 _ 为加快收敛速度，适当选择参数凡，使 颤，c，冠。，：=：ms，a；x。i2 j 。, j 一- 五| 达到最小值。如当五( i = 1 ，2