（应用数学专业论文）求解矩阵特征值问题的一种新算法——非线性算法.pdf

中南大学硕士毕业论文 前言 特征值问题的解法长期以来对我有一种特殊的魅力，因为它充分 显示出所谓经典数学与实用数值分析之间的差异。随着电子计算机的 普及以及电子技术的迅猛发展，矩阵特征值特征向量的计算越来越被 从事计算数学的人们所关注。因为无论是数学领域，还是其它领域， 比如计算化学、计算物理、控制论、信息论等领域，都离不开特征值 问题的求解。可以说，特征值问题成了数值分析的核心与出发点。自 眦s o n 于1 9 6 5 年发表名著代数特征值问题以来，在这方面已 经进行了大量的工作，并取得了重大的进展。在e i s p a c k 程序包中， 包含有许多经典的方法，其广泛使用的效果在提高不同应用领域里的 算法水平有着重要意义。科学家和工程师们可以量体裁衣地按照他们 各自特有的需要组装出更为复杂的软件工具。这就激励者人们去写出 结构优良、适用范围广、精确度高的算法。这篇文章就是在这样的背 景下产生的。 该文详尽论述了非线性算法的收敛性，并行性及其适用范围，并 与j a c o b i n 算法、q r 算法进行了比较。必须指出，由于作者水平和 时间的关系，该算法在许多方面还有待进一步改善，譬如求复特征值 的问题，程序的健壮性等等。 论文摘要 特征值问题的提出，看似一个简单的问题，其实不然。尽管其基 本理论多年来已成为人们所熟知，然而欲快速有效地求其解，就会遇 到各种挑战性问题。 本文在前人的基础上，提出了一种新的特征值问题的算法，为了 叙述方便，不妨称之为非线性算法。这种方法是把特征值问题转化为 非线性方程组进行求解。先用牛顿迭代法求得特征向量，然后代入方 程求特征值。为了加快牛顿迭代收敛速度，本文提出了利用同伦方法 进行特征值跟踪。这个方法解决了牛顿迭代初值难选的问题，从而使 得算法能有效地运行。本文对非线性算法与经典j a c o b i 方法以及q r 方法进行了比较，从例子中不难看出，非线性算法在具体运用中是很 有效的。此外，该算法的最大特点是：它很容易并行实现。然而，如 果特征值是虚值的话，牛顿迭代不收敛，因此该算法只能求出矩阵的 实特征值及其对应的特征向量。本文第三章分析了算法的收敛性及其 稳定性，第四章讨论了算法的并行性及如何实现。第五章给出了一些 数值例子，从这些例子不难看出非线性算法的许多特点。论文的第六 章对j a c o b i 、q r 、非线性算法进行了比较，从中可以看出，非线性 算法的运算量为0 ( n 4 ) 。但由于它是完全并行的，而且在工程计算中 的n 一般小于等于1 0 ，因此在计算机技术高度发展的今天，该算法 是完全可行的。 关键词特征值、特征向量、同伦、并行算法、n e 吼o n 迭代 中南大学磺士毕业论文 e i _ 删鹏p f o b l 鼬1 0 0 l 【s 嬲a 幽n p k 蚰e i i l 血砖i t i s n o t e i 铲蚋 l u cp i d l se l 锄e n l a r yt h o 既i c sh a w ? b e 钮戤h o w i 。d g c db yp 一c ， b u tw h e n 铷k l l l 撕n gc i g c 缸v a l u es p d l ya n dd 南c t 吣w eo 位n 咖m o n tw i t l lm a n yc h a l l e n g 耐q u e s 虹o n s t h i sp a p e rp r e s e n t san e wm c t h o df b rs o l 访n ge i g e n p a i r so nm eb 懿i s o f 也ep i o n e e f i n gw o r 玉澍m a tw ec a l l “n o n l i n fa l g o 劬mf o r 咖啪i - e n t h em 劬o dc o n v e f t se i g e n 讪ep i d l ，l 锄i n _ t 0 埘跚1 1 i = 嗽fd l u 撕o n s o n e i no r d l 盯t 0i n l p 删v en e w 咖妯粥面o nc v t 硼；蛐c er 咖，i ti n h o d u c e s h o m o t 叩yi d e 盼a n du l j l i z i n gh o m m o p yc u r v e s 订撇se i g e n v a l s i n i t s o l v e st 1 1 ep h 锄o f n e w t o n 札e m 虹s t a 山g 词u c ，t h em c t h o dc a nb e c l l _ t c de 往b c t i v e l yt h e p l p e rc c 唧4 姐f e sn o m i n 谨i ra k o r i i h mw i t l lj a c o b i 粗d q r w e 咖s t h a t t h e m e t h o d i s v e 可9 0 0 d 舶m t l l e e 瑚m p k s i n a d d i t i o n ，t h ea 1 9 0 她h 船t l l e 鲥l v j i n t a g eo f w 池gi n 群寸k l h o 啪啦b 嘲雠n e l 嘶n 蛔抵咀i sn o t 湖、，搿伊si nm c o f i m a g ce i g v a l u e t h em c m 甜咖o n l ye v a l u em 硫sr e me i g 锄砌u e s p a p e fd i s c u 渊幽蛐删锄施曲删 c h 叩哳a 舶1 y s 恤e n v e l g e v e n c e 锄ds t i b i l 时o ft h e 如o r 础啦t h c 鼬c h a p t e r 蛐a l y st h ep 鲫m e lo f t h ea 1 9 0 r i t h m 蛐dh o w 协砌i z e t h e 鼬c h a 廊rp s 伽腮m en u m e r i a le 眦p l c ，丘d mw h i c hw ec a n 中南大学硕士毕业论文 f l n dm o r et r a i t s t h es i x mc h a p t e ro f m ep 印e rc o m p a r en o n l i n e a ra l g o r i t h mw i t hj a c o b ia n dq r f r o mt h e s ew ef i n dm a tt h ec a c u l a t i n gq u a n t i 哆 i so ( n 4 ) b u t ，b e c a u s ei tc a n p 啪l l e lm n n i n gc o m p l e t e l ya n dg e n e r a l l yn 10w h e nc a l c u l a t i n gi ne n g i n e e r ，l e a l g o r i t l l mi s f e a s i b l ec o 瑚【p l e t e l y t o d a yw h e nc o m p u t e rt e c h n i q u ei sd e v e l o p e d1 a r g e l y k e y w o r de i g e n v a l u e 、e i g e n v e c t o r 、h o m o t o p y 、p a r a l l e la l g o r i m m 、 n e 、v t o ni t e r a t i o n 中南大学硬士毕业论文：求解矩阵特征值闩寇的一种新算法一非线性算法 第一章特征值问题与非线性算法 特征值问题的提出，出现在5 0 年代后期。由于计算机的出现与计 算机技术的发展，使得人们进行繁重的复杂计算成为可能。从此人们 便开始考虑利用计算机计算特征值和特征向量。在这方面，j h 砌蝤n s o n ，g w s t e w e m ，g b m o l e r ，b n p a r l e t t 等为此作出了重要 贡献。 1 1 特征值问题在工程领域中的应用 计算矩阵特征值特征向量的问题涉及许多领域，最早出现于近似 求解各种物理系统的“稳恒运动”或“微小”运动之中。 下面考虑一根长度为f 的等截面均匀弦，两端被固定并且沿轴上 绷紧，一端置于原点o ，另一端置于横坐标l 处。在长度为出的元 素上该弦受到垂直方向的力z m ) 出的作用( r 为弦的张力) 。我们要研 究在垂直平面上的“微小”运动，即寻求一个定义在o s x z ，f o 上 的函数”o ，它表示在横坐标x 处于时刻t 时的弦的垂直变形。可 以证明，函数甜应该满足以下的偏微分方程： 专窑一襄c 咖m m 。 川一。 其中c = 形( p 是弦的线密度) 。它称为一维波动方程。 在没有外力作用时( ，卸) ，可以求弦的稳恒运动。一般地，一维波 中南大学硕士毕业论文：求解矩阵特征值问题的一种新算法一非线性算法 动方程可以变为： 。一( 对“o ： 球( ，一( o c 这化为函数 和v 的两个微分方程： 一m 弋工) = 五搿( 工) ，一v 。( f ) = 知2 1 ，( f ) ， 五是待定系数。由于 碳o ，垆坝| l f ) = o ，对一切f ， 故问题归结为求实数a 与不恒等于零的函数“，使得 i 一越。( x ) = 五牡( x ) ，0 工z i m ( o ) = 甜( d = o 这就构成一个二阶导算子的特征值问题。 在信号处理的许多应用中，有用的许多信息必须从一个在宽带噪 声中观测的低秩向量过程抽取。数据矩阵的协方差矩阵的特征值分解 可以用来揭开隐藏的低秩信号。特别地，利用特征值的大小，我们可 以将协方差矩阵的几何子空间即特征子空间分为信号子空间和噪声 子空间两部分。所谓的特征子空间法就是用信号或噪声子空间进行低 秩信息的提取。 最近十几年，特征子空间方法广泛应用于高分辨率谱估计和 a r m a 建模，谐波恢复、传感器阵列处理、系统辨识、信号增强， 甚至于滤波器设计和模式识别等许多问题中。 在现代控制论中，系统的稳定性问题也离不开矩阵特征值问题的 讨论。 中南大学硬士毕业论文：求解矩阵特征值闩题的一种新算法一非线性算法 1 2 矩阵特征问题的算法概述 矩阵的特征值问题，不管在理论上还是在工程计算中，都是一个 十分重要的问题。长期以来，人们对这个问题的研究一直没有停止过。 至今为止，已出现了许许多多各有特色的求解矩阵特征值问题的方 法，如经典的l u 分解、j a b i 方法、q r 或双重步q r 方法、二 分多分( b s m s ) 法、分治法、同伦连续法、迭代法等等。 二分多分法是当前最常用的求解实对称矩阵的并行方法、这个 算法也可解h e 砌血i 粕矩阵特征值问题、实对称矩阵和h c 砌施粕矩阵 的广义特征值问题，更适应于解实对称三对角线特征值问题。 设4 是实对称三对角线矩阵， q6 2 6 2口26 3 “一，。6 月 6 。口。 4 的五矩阵4 一五i 的各级前主子式为鼎五) ，f = 1 ，2 一，则有州工) 具 有s t l l 咖序列性质，即序列的相邻项符号不同数等于a 的小于五的特 征值个数。在实际计算中，通常将以五) 改用序列 献f ) ： 口l ( 互) i 口1 - 五， 似工) = = ( 即五) _ 6 产雏1 ( 五) ，卢2 ，珂。 在这个序列 “i ) ( f = 2 ，功中，负数项的个数等于4 的小于2 的 值的个数。二分法的思想就是对于某个区间k 6 】，计算区间中点 中南大学磺士毕业论文：求解矩阵特征值问题的一种新算法章线性算法 卢! 芸上的序列似d ，由“j f ) 的负数项个数确定特征值的分布情况。 二 通过逐步计算可得到只含一个特征值的区间【c i 田，再将区间二等分， 逐次计算| | 次，就可确定特征值的精度g 。其中仁【l o 以皇) 】。 口 实对称矩阵的特征值问题可以先用h o u s e h o l d 盯变换、g i v 曲s 交 换把它转化为实对称三对角线矩阵的特征值问题。 分治法是一个较新的适应于并行运算的矩阵特征值问题的算法。 许多经验表明，分治法在共享存储机上的功效比二分多分法还好。 分治法的思想是把要求的特征值问题的矩阵4 分解成两个新的简单 的矩阵，然后分别对这两个简单矩阵求特征值，从而构成一个比原问 题容易解的特征值问题。容易求解的原因是给出了较好的近似值估计 并且矩阵有特殊的形状。 设实对称三对角矩阵 q6 2 6 2色6 3 6 吒一1 6 。 “口。 可以把r 化为产( 互疋 + 趔。 一般来说，五、正是把丁对半分得来的。设矗的阶为刀。，疋的阶 为，m l ，6 = 6 l ，z 是一个向量扛，其中第栉l 、地个元素为l 。 中南大学硬士毕业论文：求群矩阵特征值问题的一种新算法一非线性算法 假设五、是的特征值问题已知，即有正交矩阵q - 、q 2 使五、易化为 对角形矩阵d l 、d 2 ， q l 瓦q l i d i ，q 2 z 硷2 t ) 2 ， 于是 产( q 1 幺) c ( d 1 见) + 2 砂) ( q 1q ) 7 其中 尸辩7q ， 圳胛。 现在，原问题a = 五工转化为一个对角形矩阵的秩l 修改的特征值问 题。注意到 胪( d l 。： 的元素硅与特征值五i 存在互相分离的特性，因此西是五，的十分好的 近似。利用这个特性和矩阵的特点，已经得到了各种有效的算法。 同伦连续法是解矩阵特征值问题的一个新的并行解法。它的思想 是：设矩阵a 的特征值问题为 构造同伦 4 ( ，户( 卜n d 丘4 ，挺【o ，l 】， d 是选定的初始矩阵，通常d 为4 的对角线元素构成的矩阵。考虑 矩阵等式 矾删d 莩h 擎 _ 掣z 中南大学碗士毕业论文： 求解矩阵特征值闩韪的一种新算法一非线性算法 对，微分月丑f 即，有 f 名( ) ，一爿( f ) o 丫x ( f ) 1 ：f 似一d ) j c o ) 1 lx 7 8 )o 人三0 ) ji o j 从户o 到户l 解方程，就可求4 的特征值。 实用的同伦连续法除了要化矩阵为三对角线矩阵外，常常要结合 分治法、二分法多分法，以至于l a g u e r r e 迭代法。这个算法的优点 是它是完全并行的。 经典的j 栅城法是解对称矩阵特征值问题的一个稳定算法，而且 精度高，特征向量正交性有保证。但是它有两个主要缺点，第一是收 敛慢，第二是串行运算。现在已经有加速算法与并行的算法。 从矩阵a 刊1 出发，j 枷法是构造一系列“初等”正交矩阵 ( q 。h l ，以使得对称矩阵序列 a k + 1 5 q 1 a i q t = ( o ，q ：o 。归( o o ：o 。) ，量l ， 收敛于矩阵d i a g ( 五。) ，q f o ，o ：q 。收敛于一个正交矩阵，它的列向 量构成特征向量的标准正交集。 迭代法是用于解决特别大的矩阵特征值问题所用的方法。典型的 算法有l 舢【c z o s 法、g g 法、d a v i d s o n 法、同时幂代法、r a y l i l ；h 商 逆迭代法等等。这种方法是只用矩阵与向量相乘运算而不作矩阵变 换。目前的迭代法只是解大到无法处理的巨大问题时才不得已而采 用。主要原因是：并行设计十分困难，粒度细。 中南大学馥士毕业论文；求解矩阵特征德问置的一种新算法一非线1 生算法 1 3 非线性舞法的特点与瑾论意义 特 芷值问题，就是确定2 的值，使得胛个未知量的方程组 么舻舨 ( 击) 有非零解。显然，潜x 是方程的锯，则对任一值| | ，奴也是方穰( ) 的解。霾瑟瑟蠖翟- 磊| ) 酶获等予( 玲1 ) ，对疲予置麴将缝蠢量霹数差一 个常数因子，可以选取这个常数因子，使得特征向量具有所需要的数 筐特性。 非线性算法是利用非线性方程组求解矩阵特征值特征向量。它把 矩阵特摄 妻问题转优力方程缱，因此它不网予以往馁 露一萃申方法，默 某种意义上说，这也是求解特征值问题在理论上的突破。 非线性算法的最大优点是官嫂窑易实现并行运算。因为求躲爿 线 性方程组对，要计算j a b i 矩阵，这个工作量是菲常大的，特别是当 矩阵的维数相当大时，所以在窳际计算中可以利用拟牛顿迭代法代替 一， 牛顿迭栈法。为了加快收敛速度，嚣线性算法弓l 入了同伦思想。设 爿2 ( 口n ) 矗“”，4k2 d + 以e0 蜒如l ( 扣1 0 ，n ) ，4 n 刊，分另u 求出各 鑫酶黪徭蠢量特缝篷，跟踪霞稔夔线，囊霹褥到么憋特薤毽将德商 量。 中南大学硪士毕业论文：求解矩阵特征值问题的一种新算法一非线性算法 第二章求解特征值问题的非线性方法 上一章已就特征值问题的各种方法进行了概括；在这些方法中； 我们不能说哪种方法最好，因为它们都是对某一类矩阵的相当好的算 法。这一章将对非线性算法进行详细地介绍。 2 1基本定理 由于舍入误差的影响以及特征值算法是迭代的但必须是有限步 结果的缘故，因此首先提出有用的扰动理论，用它来指导以后各节中 对特征值求解方法的讨论。 引理2 1( g 衙s h g o 咖圆盘定理) 若x - _ 4 x = d j a 甙矾。，伽并 且f 的对角元全为零，则五) u 备d f ，其中 # 耻 艇c l i 予硎i i ) 。 证明假设五五0 ) ，不失一般性又假设互产西a = 1 问，由 于( n 五i ) 十f 是奇异阵，于是对某个| | ，l j | 力，就有 蚓陋柚俐：砉j 必 这就意味着五瑰。 引理2 2 ( s c h u r 分解) 若4 c “，则存在酉矩阵q c “使得 q ( 卜t = 讲- 中南大学硬士毕业论文： 求解矩阵特征值闷题的一种新算法一非线性算法 其中胪d i 咄五l ，互。) ，而c ”“是严格上三角阵。而且可以选择 q 使得特征值量r 沿对角线按任一给走的次序出现。 证明当以= 1 时，结论显然成立。假定结论对小于或等于珈l 阶 的矩阵都成立，若4 x = 五x ，其中x 0 。则存在酉矩阵u 使得 幽h ： 其中c 是一个( 加1 ) ( 挣1 ) 矩阵，由归纳法，存在酉阵u 使得) h c u 是上三角阵，于是，若删i a g ( 1 ，u ) ，则q 鸭q 必为上三角阵。 下面的两个引理说明了矩阵的特征值是怎样受小扰动影响的。 引理2 _ 3 ( b a u 小f i k e ) 若卢是爿崾c ”“的一个特征值，并且 x - 1 似_ d = d 蜮丑l ，2 。) ，贝0 m i n i 工。i r p 0 ) 目j l p a 其刊m 表示任何一个h o i d e r 范数。 证明只需考虑声芒五口) 的情况。 若1 口十吕f i 是奇异阵，则i + ( d i ) 1 ( x - 1 互) 亦然。于是 l f k n p i ) - l ( x _ 慨) 峙 f 阁u 固u p f l k m i nl 五- p f ， 因此定理得证。 借助于s c h u r 分解可得到类似的结果： 引理2 4令蝴d = 肼_ 是a c “”的s c h u r 分解，若 脚十毋并且p 是使肭：o 的最小正整数，则m i n i 五p l 蔓m a ) 【 口，口 ， 中南大学硬士毕业论文：求解矩阵特征值闩题的一种新算法一非线性算法 其中口= 悃i ：芝o o ： h 当4 为非正规阵时，引理2 3 ，引理2 1 4 都表明特征值潜在的敏 感性。也就是说，若r ：或i | 7 i 大的话，则彳的小变化就可能导致 特征值大的变化。 定理2 1 设4 气口g ) 尺一，4 。2 阱以只o l ，2 脓，脚，l ， 2 ，n ，n l 伪，其中 o i ，f 。p = j o 气q 2 & 口m 气口2 1 0 吒。 矗，气吒2 o 则当心4 时，4 。的所有盖尔圆不相交。 其中s 2 警+ 2 ，- 2 n l 驭 i 呜l ，d b m i l l k 一l a 蛊等” 证明根据c k r s h g o r i n 圆盘定理即可得出 定理中的s 取r 警+ 2 时，结论仍然成立。 定理2 2 设4 是h 锄慨矩阵，九f 入似o ) 且九l 巩k ， m a l ) 且p l 宏，则i k - j ki q 勿。 证明取s ：r 兰鲁笋+ 2 ，故有刊酬。立+ t d ，从而 i i 1 4 0 | l i = i l f l p | i a 口= 0 p i i 。：q 1 2 8 。2 d 宅嘧 根据引理2 3 及引理2 2 ，有 i k 刖l 阻，4 0 | i 。q 哆吐证毕 o l d 中南大学硬士毕业论文：求解矩阵特征值闩题的一种新算法一非线性算法 2 2 构造非线性方程组求特征值特征向量 菲线性方法的思想是：将特征值问题转化为非线性方程组的求解。 若五五) ，则称满足 4 x = 2 x 的非零向量x c “为特征向量。一个特征向量确定一个关于左乘4 不 变的一维子空间。更一般的说，称具有 x s j a x s 性质的子空间s c 为不变子空间。 设s 是矩阵彳的一个不变子空间，x s ，那么可以经过适当的变 下面考虑如何构造非线性方程组求解特征值特征向量。 龇，对应于丑的特征舱酽 ( 第潲量为d ，则有： a x 。= 五函，( 2 1 ) 它的第f 个方程 “ “ 。+ 口，+ 2 丑， ( 2 2 ) 当房i 时，第j 个方程 口，+ 。扫+ 2 五， ( 2 3 ) 为且里分个第 中“r 0舯j 1 oo 到得而换 中南大学磺士毕业论文：隶解矩阵特征值日题的一种新算法一菲线性算法 由( 2 2 ) 、( 2 3 ) 可以得到： 口f + a 。b + = k + b + b k ， 一p枷一p d h 户l ，2 ，卜l ，什1 ，玛( 2 4 ) 所以，正2 口d 寸+ k 一+ 艺+ + k h 产p=pl 一+ 1 口，+ 曼。，+ 艺。十杰。】= o ， 卢1 ，2 ，f 一1 ，( 2 5 ) p - 1p = ，“p 气+ 1 兀= 口。，z + k 一+ 芝+ 芝。，+ 奎口，h p _ 1p = “1 纠“ l lh 一k ，+ x ，+ + 】2 0 ， 户什1 ，拧( 2 6 ) p dp 斗“p - j + l 设方程( 2 5 ) 、( 2 ，6 ) 中j ，的系数为b ，则它的j a c 0 k 矩阵 j 2 ( q h ) ( 。4 1 ) ， 由牛顿迭代法可得到 其中 f 勉d 毛+ 饥，( ，= m ) l 口矾而一口h ，( ，掰) f = 忧，五t ，五1 ，磊) 7 。 我们知道，当j ( x ) 。1 存在和选取合适的初值时，n e w 幻迭代 至少二阶收敛。 下面来考虑初始值x 的选取。 由定理2 5 知，4 0 - d ，小一，对给定的矗，可以得到n h 个矩 阵厶，4 l ，a n 。而a 。的特征向量为 中南大学硬士毕业论文：求解矩阵特征值闩最的一种新算法一非线性算法 叫一旧 l l u j 弘 u j 以y ( 0 ) 作为迭代初值，应用非线性法于矩阵a ，求出y ( 1 ) 。 由两点插值法：盟一必，求得y a = 2 y y ( 0 ) 。 屯一而而一 对于七3 ，则利用三点插值法。 插值基函数： 砸，2 芸鹅“睁等蓑焉，特等蓑焉， 作线性组合： o 矗o ) + v 1 o ) + 一坳) 便可求得 y 恤) = ：3 y ( h ) 一3 y “2 + 3 y ( ”) ，膏3 ， 从而最后求y 。 以v 2 ) 、f 3 ) 、严作为牛顿迭代的初值，便可4 1 、4 2 、 氐( 即4 ) 的特征向量，继而求出特征值。 1 4 中南大学硬士毕业论文：求解矩阵特征值闩题的一种新算法一非线性算法 x 。) 2 3 算法描述与程序 根据前面的讨论，可以得到非线性算法，描述如下； 求初值算法1 ：( n e v 呦n 迭代求4 。的特征向量y = ( 】【。，x ：， 步b 给出计算精度q ，迭代初值为y ( 0 ) 2 巨1 牝计算譬忆肛c 矿呲r 2 m 觚l ， 赤m i n k 一l 步3 ：假设己进行了j | 次迭代，己求出x ，计算f ( x2 ) 、j ( x 。) ， 设b 。= f 。( x 。) 因为计算j 。( x 。) 的工作量非常大，下面讨论如何用差商代替偏导 j ( x 户 戮( x ) 舌k ， 囝( x ) 良 识o ) 融 瓠( x ) 出。 欲( 工) 敬 筑( 工) 纸 利用差商代替偏导数，即 璺盟。互! 主! ：! 二五! 兰竺! 钙 矗 其中| l l 足够小，且 z ( _ ) = z ( ，x j _ l m ，x j + x j “，啪) 。 一魄一魄；一舐 中南大学硬士毕业论文：求解矩阵特征值问题的一种新算法一非线性算法 步4 ：解线性方程组j 。( x 。) x - - b 。，得到x ，x m = x + x ： 利用全主元消去法解线性方程组。 设在第七步中( 拓l ，2 ，功，从所剩的( 一一j + d 2 个中选出的最大元 素为，即 i f - m a 】【 in 孑1 | | t ，j e 把主行即第行与第1 i 行交换，主列即第五列与第j | 列交换，然 后再按顺序消去法消元。 步5 ：若i f ( x “) 忙q ，则置f = x m ，打印x ，否则鼢1 斗七，x 聃_ x 。，f ( x “) 寸f ( x ) ，转2 ； 这里的范数忙 i 可以是任一种范数。为了简便计算，我们采用。o 范 数。 步6 ：结束。 算法2 ：( 利用插值法求y ) 步1 ：计算n = 1 伪； 步2 ：由y 0 】、y ( 1 ) ，根据两点插值法求y o ) = 2 y o ) 一y ( 0 ) ； 步3 ：当3 量n 时，y 忙) _ 3 y ) 3 y 耻_ 2 + 3 y 。 算法3 ：( 迭代求彳的特征值特征向量) 步1 ：给出计算精度毛，迭代初值为y ； 步2 ：假设已进行了| | 次迭代，已求出x ，计算f ( x ) 、j ( x ) ， 记b t 2t l x j ； 中南大学磺士毕业论文：求解矩阵特征值i 刚匮的一种新算法非线性算法 步3 ：解线性方程组j ( 妒) x 一b 。，得到x ： 步4 ：求x “= x + x 及f ( x “) ； 步5 ：若l i f ( x ) 忙毛，则置x = x h ，打印妒、i i f ( f ) l l 及| | x 否则五十1 寸七，x m 斗x ，f ( x m ) 斗f ( x ) ，转2 ： 步6 ：结束。 算法3 中j ( x ) 的计算以及线性方程组 j ( x ) x = b t 的解与算法1 相同。 从a 。开始，跟踪同伦曲线，一直到压- ，便可得到a 的特征值和 特征向量。根据特征值的同伦曲线光滑与否，可以判断4 是否有虚 特征值。若特征值的同伦曲线不光滑，那么这个特征值是虚的。在程 序中通过设置最大迭代次数来确定迭代是否收敛，当超过或者出现奇 异情况时，则该值为虚值。非线性算法只能求矩阵的实特征值。 该算法很容易用m a 廿a b 语言写出，源程序见附录。其中n o n l i n g - 谢n 1 m 利用拟n e 、v 幻n 迭代法求特征向量和迭代次数的函数，函数 g 蛐s s m 用全主元消去法解线性方程组，函数n e 廿用于计算 氟产l ，2 ， ) 的值。 中南大学硬士毕业论文：求解矩阵特征值i 司韪的一种新算法一非线性算法 第三章稳定性与收敛性分析 前面一章已经从它的得出到实现详细地介绍了非线性算法，不难 看出，非线性算法必须利用n c 、v t o n 迭代法解非线性方程组。我们知 道，当选取合适的初值，n e 咖n 迭代至少二次收敛。 3 1 收敛定理 考虑形如 i = 妒l ( ，x 2 ，“) ( 3 1 ) 【矗= ( x ，屯，) 的非线性方程组。 引进向量函数p ：孵c 斗，它是由向量 识( 五，) p 降p 扎矗 死( ， ) 工1 x 2 ： 定义的，其中分量矿工x ) ( 卢1 ，2 刀) 为给定区域咒上的实值函数。此时 方程组( 3 1 ) 可简单表示为 x = 矿( x )( 3 2 ) 称形如 轴l 一矿( 硝( j ，l ) ( 3 _ 3 ) 的这种逐次逼近序列为方程组( 3 2 ) 的简单迭代法。 引理3 1设p ：孵亡r n r n 在闭区域 吼上满足条件 中南大学硬士毕业论文：求解矩阵特征值问题的一种新算法一非线性蔓垫 怕( x ) - 妒( ”忙刮k 刊l ，对任意墨y 吼o ， ( 3 4 ) o f l ，且妒( 巩o ) c 飘o ，则对任意琊吼o ，( 3 3 ) 产生的迭代序列 砖j c 蛳 收敛于方程组( 3 2 ) 的唯一解x 皱。，且 i 陬0 忙士i 陆x h l l i 1 ) ( 3 5 ) j + 口 证明已知任意和矿( 巩o ) c 孵o ，故由( 3 _ 3 ) 产生的迭代序列 ) c 孵o 。 l i ) 4 h - 刈f i f 9 ( ) 连) - 矿( ) 醵1 ) i | 蔓刮b 硌- 球1 | 于是有 | | m 剖i 蔓壹i 陬。h 矿1 + + 印+ 1 ) j 陬。删1 南l 医嘞。 因o g l ，故当| 斗o 。时，序列 站为c 卸c h y 序列。又由巩。为闭区 域，故存在x 孵。， l i m = x + 。 对黼1 = 妒( x ) 两端取极限，即得 f = 尹( x + ) ， 故f 是( 3 2 ) 的解。 若p 也是( 3 。2 ) 的解，即，= p ( ) 。由于 i l 妒( 卢) _ p ( x + ) l | = 卢由【f i q 0 卢- ) ( 幸i l o 庐1 ，所以声= ) ( + 。 因为 l l x 啊划l ( 矿1 + + 矿1 ) l i 黼l 剖l 中南大学硬士毕业论文：求解矩阵特征值饲题的一种新算 一非线性算法 南i i 瓣- i l 在上列不等式中，固定j ，让p 斗m ，即得估计式( 3 5 ) 。 定理3 1设吼o - 劁| f x 蜀i | 础亡孵c r ，伊：吼 r n _ r 在闭区域 上满足 怕( 玲矿( y ) 忙g l 陋酬，对任意墨y ， 0 g o c k ， 对一切工k o ，向量函数妒：k o c k c r 丑r 丑 尹( 牺口( x ) 】欤x ) 适定，且妒在x 处可微，导数为 d 尹( x 产i 口( x ) 】d 扳f ) 其中i 为单位矩阵。 定理3 2 设正吼仁r n 斗r n 在孵上可微， i l 啉c 狄y ) 忙叩i i x 剖| ，0 【e 皈x 粥。1 忙声，对任意墨y r n 卢、，7 满足砰声，7 1 ，若选择初值】【0 吼，使 k 0 2 蚓陋询忙j ，占户扳两) j 1 叼 c 孵， 则由迭代过程( 3 7 ) 产生的迭代序列 毪 收敛且具有平方敛速。 证明由已知条件可知，函数 p ( x 产x - 】聊r x ) 】- x ) ( 3 8 ) 对一切x k o 是适定的，且对一切x ，y k o 有 怕( x ) - 矿( y ) i i = i f x y - 瞰x ) 】1 ( ，( ) 【) 孤y ) ) + 瞰x ) 】。1 ( 颐y h x ) ) 【e 吠y ) 】欤y ) 州 赋x ) 】4 删嫩坷) _ c 扳x x x - 洲j + 颐y ) - 颐酬矿( y 蚓1 ) 卢，7 ( i b 吲卜l | 9 ( y ) - y 1 1 )( 3 9 ) 在( 3 8 ) 中，由( 3 7 ) 有x l = 妒( 洳) ，即 中南大学硕士毕业论文： 求解矩阵特征值闩题的一种薪算法非线性算法 x 1 - x 。= 【e 哌) 【o ) 】次硒) 所以 i 医1 x 洲0 颐x o ) 】4 f i 攻】【o ) 0 ( 1 g ) 占 j 即x l k o 。假设两，x l ，琏k o ， i b 聃1 刊i _ i i 尹( 玲妒( ) 辕1 ) l i 声町( 1 1 ) i p 距1 8 + 0 缈( ) 瑶1 ) _ 锥l i ) 。1 2 声珂i b 妒距l i 户d b 醑强1 0 于是有 1 1 ，抖i - 渤忙i ) 聃l - 列h i 两稚l 忖+ i | x l - ) 【0 0 ( 冉矿1 + + 矿1 ) 卢忧】【o ) 卢l i ，【x o ) l i 1 - g j 于是鞯1 k o 。利用定理3 1 中同样的方法，易证 取 为一c a u c h y 序 列，故必存在f k 。，使 l i m 辆+ f 蛔 又因为 i i 矿( x ) - 妒( f 列户 b ( - x + 一田腰x ) 】次x ) i i = | 卜田吸x ) 】。1 状) 【) 呋，【h 城) 【x x - x 川 | | 颐x ) 1 0 惯x 厕) 颐x x x - x ) 0 由于| i 呱玲【吠y ) 忙圳) 【y j j ，对任意k y ，所以贝x ) 有二阶导数且有 界。于是上面不等式卢刁j 心n 把x 换成琢，恼( 蚺尹( x ) 忙卢玎i b 时x n 即 l f 球l o 忙卢，7 l 晦- x 忾 所以迭代序列具有二阶敛速。证毕 中南大学硬士毕业论文： 求解矩阵特征值闩是的一种新算法一非线性算法 在式( 3 7 ) 中，取口( x ) 】1 为删矩阵，显然在方程的解蕊+ 处，j a c o b i 矩阵存在号等于零。根据引理3 2 及定理3 2 可知，只要初值充分接 近# ，则迭代( 3 7 ) 收敛于f ，如果j a c o b i 矩阵非奇异，迭代具有二 阶敛速。 3 2 非线性算法的稳定性分析 设4 = ( 口0 c 一，研究特征值问题的稳定性，就是研究特征值五及 其相应的特征向量是否连续地依赖于4 的元素呀。要指出的是，矩 阵的特征向量不一定是稳定的，但矩阵的特征值是稳定的，这一点见 下面的定理。 引理3 _ 3 ( o s 仃( w s l 【i 定理) 设彳气口f ) ，口气卢力c ，五口产 五0 ， a 徊) = p ， 。令 聊岱2 玎1 a x ( 1 岱fl ，i 卢f1 ) ， 护漓岛鸣l 和 - 一三三 占= ( 挖+ 2 ) 埘。”0 曰一4 i f ： 则对任一p 五) ，必有五 p ) 五0 ) ，使得 l 五正) _ p i j 对于各a f = l ，2 川) ，迭代初值为叮o ，则一。由下面定理给出。 中南大学硬士毕业论文：求解矩阵特征值闩焉的一种新算法一非线性算法 定理3 3y 瑚y 如- 1 ) y 聊( 娩2 ) 证明( 数学归纳法) 当，f _ 2 时，结论显然成立。 假设当2 t 和气“1 结论成立，则由算法 y = 3 y ( 娜- 3 y ( + y ( 咖 = 3 【( 舡1 1 k 地) p 【( 娩) y _ ( 柏) y 卿】+ ( 硒) y - ( 柚) y 蚋 = 胛m - ( 肛1 ) y 棚 由引理3 3 ，可以得到： 定理3 4 设五( 厄户 丑) ，五( a 2 产 肛 ，m 。= m a x 口。+ 锄i ，对任 z p “a z ) ，必有 ( ) 五( 4 - ) ，使 i ( 声) - p i o 和在h 岛上的解析函数 ( 占) 和向量函数硝) ，f 2 l ，2 ，以 使得 中南大学硬士毕业论文：求俐巨阵特征值问题的一种新算法一非线性算法 并满足 口- + 占喇占) 2 五( e ) k i ( 占) ( 3 1 0 ) 五( o ) = 丑，琦( 0 ) = x ， 其中工，是对应于丑的特征向量。可以证明， 黑+ 叫：) ， 一l s ( 五) l 、 假定琦( 占) 的泰勒展开式为 x | ( 占) = x ，占z ，0 ( s 2 ) 由于x l ，强构成e 的一组基，故有 茚口g 弓，c ， 把( 3 1 2 ) 代入( 3 1 1 ) 得 5 产( 1 + 跚。) x ，占杰吩矿o ( 2 ) ，( 3 1 3 ) 设占) 已选好使得吼= o ，因为五。( 占产工。+ 五。( 占卜o ( 占2 ) ，( 3 1 4 ) ( 3 1 3 ) 、( 3 2 4 ) 代入( 3 1 0 ) ，得 盘f 魄一 ) 驴( ( o ) i 诹， ( 3 1 5 ) j f 在( 3 1 5 ) 两边左乘秽，注意到铲酽o ，i 颤有 鸭一 ) 疗毕一疗瓯 f 不妨设s ( t 产j 幽i = 幽，于是 爵( 占) = 对占( 删( 丑一乃) s ( ) ) 矿o ( 占2 ) 产j 中南大学硬士毕业论文：求解矩阵特征值闩题的一种新算法一非线性算法 第四章并行性分析 n c 啪法虽然有收敛快和自校正等优点，但应用到实际计算中仍 有不少的问题。上一章说明，非线性算法的收敛性是可以保证的，但 是每步要计算j a c o b i n 矩阵j ( x ) 及解线性方程组，工作量相当大， 因此它在单机上运行的效率并不好。然而非线性算法具有并行运算的 特点，因此在计算机技术高度发展的今天，它的实现不糠是可行的， 而且是高效的。 4 1 基本概念 并行计算( p 眦l l e lc o m p u 血g ) ，简单地讲，就是在并行计算机或分 布式计算机等高性能计算机系统上所作的超级计算，其物质基础是高 性能并行计算机( 包括分布式网络计算机) 。 定义4 1 同步算法( s y n c h r o n 硎g o 舶m ) 是指算法的诸进程的 执行必须相互等待的一类并行算法。 定义4 2 异步算法( 舡”c h m n i z e d g o r i t h m ) 是指算法的诸进程 不必相互等待的一类并行算法。 定义4 3 分布算法( d i s t f i b 砷耐础g o 柚m ) 是指由通信链路连接的 多个场点( s h ) 或节点，协同完成问题求解的一类并行算法。 在分析并行算法时，通常要分析如下几个指标： 运行时间h n ) ：运行时间就是算法运行在给定理模型上求解问 中南大学硕士毕业论文：求解矩阵特征值问置的一种新算法一非线性算法 题所需的时间( 它主要是输入规模的函数) ，通常包括计算时间和通信 时间。 处理器数p ( n ) ：它是求解给定问题所用的处理器数目，通常取 p ( n 产n “，o 占 酱。 4 l = d 斗t 。p ，其中t ，= 2 ，n 矗2 。 3 、解非线性方程组： x = x ( h + j ( x h ) 一1f ( x 忙_ 1 1 ) ， 迭代初值为：y ( o ) 。 f 卦卦 得到y 。 4 、求y 佣：y 传l - j y _ ( 缸1 ) y ( o ) ，七2 。 5 、对于& ，解非线性方程组求特征向量与特征值： 其中 x = ) 【+ j ( x ) 一1 f ( x ) t h 纶 翟芝茳： 迭代初值为y 佣。 二、设计分析 划分算法中s 的计算可分给p 个处理器运行，而依照算法，特 征向量的求解是并行运行的，故可以将矩阵4 按行带状划分，每个处 理器以p 行。把单位矩阵e 丑4 按列带状划分，送给每个处理器，作 为4 i 第( 1 _ 1 ) ”矿1 到l 胆p 个特征向量的初值。 通信求s 时，每处理器之间必须进行多到多播送( 通信) 以求 中南大学硬士毕业论文：求解矩阵特征值i 题的一种新算法一非线性算法 得，2 m a x i 吩i ，萨m i n | 口厂限最后求矩阵a 的特征向量、 譬掣9 特征值时，为了把计算结果存储在p 。上，只须进行单点收集就行了。 设计的第三阶段，即组合( a 鹳l o 删湘舶n ) 阶段，目的是重新考虑 问题的粒度，以图得到一个在并行机上能有效执行的算法。考虑到每 个处理器运行的是同一程序，因此能保证很好的负载平衡，同时为了 减少软件工程的代价，故利用拟牛顿法求解非线性方程组不再划分。 从中可以看出，非线性算法的粒度是确定的，所以，在设计分析时不 再考虑“组合”。 三，算法描述 假定4 按行分成p 块，l f ，爿1 按列分成p 块l f ，l f p 。 b s p 上非线性并行算法 输入：a