（应用数学专业论文）非齐次对称特征值问题的同伦算法.pdf

华北电力大学硕士学位论文摘要 摘要 非齐次特征值问题在数学和其他领域里有很多应用。如线性微分方程组稳定性 和渐进估计的研究，球面上二次函数的稳定点求解及约束特征值问题等。同伦算法 是求解非线性问题的一种有效的方法。它克服了传统迭代法局部收敛的弱点，对初 值的选取没有严格限制，能够全局收敛，容易实施并行计算。 本文的主要工作：第一，讨论了非齐次项对非齐次对称特征值解的存在性的影 响，得到解对非齐次项的敏感性定理，并通过实验进行验证。第二，给出了求解非 齐次对称特征值问题全部解的同伦算法。根据不可约三对角矩阵特征值的性质，利 用正交相似变换将对称矩阵转换为一些低阶的不可约三对角矩阵，对每个矩阵用同 伦算法求出其非齐次特征值，进而得到全部的解。 关键词：同伦算法，非齐次特征值，对称矩阵 a b s t r a c t t h ei n h o m o g e n e o u se i g e n v a l u ep r o b l e mh a sm a n ya p p l i c a t i o n si nm a t h e m a t i c sa n d o t h e ra r e a s ，s u c ha st h es t u d yo ft h es t a b i l i t yo fl i n e a rd i f f e r e n t i a le q u a t i o n sa n da s y m p t o t i c e s t i m a t i o n ，t h es o l u t i o no ft h es t a b l ep o m o fq u a d r a t i cf u n c t i o no nas p h e r e ，t h ep r o b l e mo f c o n s t r a i n e de i g e n v a l u ea n ds oo n h o m o t o p ym e t h o di sa l le f f e c t i v em e t h o dt os o l v e n o n l i n e a rp r o b l e m ，w h i c ho v e r c o m e st h ed i s a d v a n t a g eo ft h el o c a lc o n v e r g e n c eo ft r a d i t i o n a l i t e r a t i v em e t h o d , a n dh a sn os t r i c tl i m i t a t i o no fi n i t i a lv a l u es e l e c t i o n w h a t sm o r e ，i tc a n m a k eg l o b a lc o n v e r g e n c ep o s s i b l e ，a n di m p l e m e n tp a r a l l e lc o m p u t i n ge a s i l y f o l l o w i n g r e s u l t sw e r e o b t a i n e d ：f i r s t l y , w ea n a l y z e d t h ei n f l u e n c eo ft h e i n h o m o g e n c o u st e r mo nt h ee x i s t e n c eo ft h ei n h o m o g e n e o u ss y m m e t r i ce i g e n v a l u e ，a n d o b t a i n e dt h es e n s i t i v i t yt h e o r e mo ft h es o l u t i o nt ot h ei n h o m o g e n e o u st e r ma n dv a l i d a t e di t w i t hs o m ee x a m p l e s s e c o n d l y , w ep r o p o s e dt h eh o m o t o p ym e t h o dt os o l v ea l ls o l u t i o n so f t h ei n h o m o g e n e o u ss y m m e t r i ce i g e n v a l u e a c c o r d i n gt ot h ep r o p e r t i e so ft h ee i g e n v a l u eo f i r r e d u c i b l e t r i d i a g o n a lm a t r i x ，w eu s e do r t h o g o n a ls i m i l a r i t yt r a n s f o r m a t i o n t ot u r n s y m m e t r i cm a t r i xi n t os o m el o wo r d e ri r r e d u c i b l et r i d i a g o n a lm a t r i c e s ，a n ds o l v e dt h e i n h o m o g e n e o u se i g e n v a l u eo fe a c hm a t r i xw i t hh o m o t o p ym e t h o d ，b yw h i c ha l lt h es o l u t i o n s c a nb eg o t k e yw o r d s ：h o m o t o p ym e t h o d ，i n h o m o g e n e o u se i g e n v a l u e ，s y m m e t r i cm a t r i x w a n gl i j u a n ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f g ug e n d a i 华北电力大学硕士学位论文摘要 摘要 非齐次特征值问题在数学和其他领域里有很多应用。如线性微分方程组稳定性 和渐进估计的研究，球面上二次函数的稳定点求解及约束特征值问题等。同伦算法 是求解非线性问题的一种有效的方法。它克服了传统迭代法局部收敛的弱点，对初 值的选取没有严格限制，能够全局收敛，容易实施并行计算。 本文的主要工作：第一，讨论了非齐次项对非齐次对称特征值解的存在性的影 响，得到解对非齐次项的敏感性定理，并通过实验进行验证。第二，给出了求解非 齐次对称特征值问题全部解的同伦算法。根据不可约三对角矩阵特征值的性质，利 用正交相似变换将对称矩阵转换为一些低阶的不可约三对角矩阵，对每个矩阵用同 伦算法求出其非齐次特征值，进而得到全部的解。 关键词：同伦算法，非齐次特征值，对称矩阵 a b s t r a c t t h ei n h o m o g e n e o u se i g e n v a l u ep r o b l e mh a sm a n ya p p l i c a t i o n si nm a t h e m a t i c sa n d o t h e ra r e a s ，s u c ha st h es t u d yo ft h es t a b i l i t yo fl i n e a rd i f f e r e n t i a le q u a t i o n sa n da s y m p t o t i c e s t i m a t i o n ，t h es o l u t i o no ft h es t a b l ep o 缸o fq u a d r a t i cf u n c t i o no nas p h e r e ，t h ep r o b l e mo f c o n s t r a i n e de i g e n v a h ea n ds oo n h o m o t o p ym e t h o di sa l le f f e c t i v em e t h o dt os o l v e n o n l i n e a rp r o b l e m ，w h i c ho v e r c o m e st h ed i s a d v a n t a g eo ft h el o c a lc o n v e r g e n c eo ft r a d i t i o n a l i t e r a t i v em e t h o d , a n dh a sn os t r i c tl i m i t a t i o no fi n i t i a lv a l u es e l e c t i o n w h a t sm o r e ，i tc a n m a k eg l o b a lc o n v e r g e n c ep o s s i b l e ，a n di m p l e m e n tp a r a l l e lc o m p u t i n ge a s i l y f o l l o w i n g r e s u l t sw e r e o b t a i n e d ：f i r s t l y , w ea n a l y z e d t h ei n f l u e n c eo ft h e i n h o m o g e n e o u st e r mo nt h ee x i s t e n c eo ft h ei n h o m o g e n e o u ss y m m e t r i ce i g e n v a l u e ，a n d o b t a i n e dt h es e n s i t i v i t yt h e o r e mo ft h es o l u t i o nt ot h ei n h o m o g e n e o u st e r ma n dv a l i d a t e di t w i t hs o m ee x a m p l e s s e c o n d l y , w ep r o p o s e dt h eh o m o t o p ym e t h o dt os o l v ea l ls o l u t i o n so f t h ei n h o m o g e n e o u ss y m m e t r i ce i g e n v a l u e a c c o r d i n gt ot h ep r o p e r t i e so ft h ee i g e n v a l u eo f i r r e d u c i b l e t r i d i a g o n a lm a t r i x ，w eu s e do r t h o g o n a ls i m i l a r i t yt r a n s f o r m a t i o n t ot u r n s y m m e t r i cm a t r i xi n t os o m el o wo r d e ri r r e d u c i b l et r i d i a g o n a lm a t r i c e s ，a n ds o l v e dt h e i n h o m o g e n e o u se i g e n v a l u eo fe a c hm a t r i xw i t hh o m o t o p ym e t h o d ，b yw h i c ha l lt h es o l u t i o n s c a nb eg o t k e yw o r d s ：h o m o t o p y m e t h o d ，i n h o m o g e n e o u se i g e n v a l u e ，s y m m e t r i cm a t r i x w a n gl i j u a n ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f g ug e n d a i 声 衄n = j尸 本人郑重声明：此处所提交的硕士学位论文非齐次对称特征值问题的同伦算法， 是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得的研究 成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 学位论文作者签名： 盈盔 日期： 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：兰盈缉 日 g e l ：让途! 羽 导师签名： 华北电力大学硕+ 学位论文 1 1 课题背景 第一章引言 给定矩阵彳尺删 和向量be r “，求实数a 和向量x 尺”使得 一袭：6 1 ， 若b = 0 ，则问题( 卜1 ) 就是通常的矩阵特征值问题：若b 0 ，则问题( 卜1 ) 称为非 齐次特征值问题，使其成立的数a 和向量x 分别称为非齐次特征值和对应的非齐次 特征向量。 非齐次特征值问题在数学和其他领域里有很多应用。如线性微分方程组稳定性 和渐进估计 1 1 的研究，求解具有二次约束x r x ；1 的线性最4 - 乘问题【2 ，3 1 ，球面上 二次函数的稳定点求解及约束特征值问题，以及工程结构计算、投入产出模型等。 在实际问题当中，对于非齐次特征值问题的实数解的研究更有意义，因此更常 见于在实数域上对这一问题的讨论。目前，对于非齐次特征值问题解的存在性研究、 解的个数以及求解非齐次特征值的算法已经有了一些结论。但相对于齐次特征值的 研究，非齐次特征值问题仍有很大的研究空间。 同伦算法是求解非线性问题的一种非常有效的方法，它于7 0 年代才开始发展 起来，其基本思想是：借助同伦h ( 借助同伦日的零点集日q ( o ) ) ，从辅助映射的 零点集出发，跟踪同伦日俾，f ) 一0 的解曲线，走到目标映射的零点集。它克服了传 统迭代法局部收敛的弱点，对初值的选取没有严格限制，能够全局收敛，容易实施 并行计算，因而被誉为2 0 世纪数学研究中一项带有突破性的新成果【4 j 。几十年来， 人们从非线性方程组、不动点问题、平衡问题、非线性规划、多目标规划、变分不 等式、互补问题等多种数学问题的角度对同伦算法进行了广泛深入的研究，并成功 地把它们应用于经济学、电子线路设计、自动控制、计算机辅助设计和制造等许多 领域中，成为引人注目的算法。 同伦算法用于代数特征值问题的研究始于八十年代中期，且取得了显著成果。 而对非齐次特征值问题的同伦算法，研究工作尚未完全展开。因此，研究非齐次对 称特征值问题的同伦算法有非常重要的意义。 1 2 非齐次特征值问题的国内外研究现状 非齐次特征值问题的求解，对线性微分方程组解的稳定性研究、球面上二次函 数稳定点的确定以及约束特征值问题等，已有重要的意义。 华北电力大学硕士学位论文 m a t t h e i j 指出线性微分系统的动态特征值是实的，因此，目前对非齐次特征值 问题的研究多见于对其实解的研究。近些年来，关于非齐次特征值问题的研究还在 继续进行。下面我们分别对非齐次特征值问题解的存在性、解的个数，解的扰动性 以及数值方法分别进行总结。 1 2 1 解的存在性及解的个数 研究线性微分方程组解的稳定性和渐进估计以及求解具有二次约束x r x 一1 的 线性最小二乘问题都可导出非齐次对称特征值问题。当矩阵是实对称矩阵时， g o l u b p l 已经对其进行了讨论。1 9 8 7 年m a t t h e i j 和s 6 d e r l i n d 【6 】讨论了非齐次特征值 问题解的存在性，给出了一个很重要的定理。 定理1 1 ： ( i ) 若问题( 卜1 ) 存在唯一解似，z ) 的充分必要条件是a xi 触只有零解，即a 不是a 的特征值。 ( i i ) 若彳至少有一个实特征值，且b 不正交于彳对应于该特征值的左特征向量，则 问题( 1 - 1 ) 至少有两个实解。 ( i i i ) 设4 为，l 阶非对称实矩阵，如果非齐次特征值问题( 1 - 1 ) 有k 个( 包含重数) 特 征值，则 ( 1 ) k 为偶数； ( 2 ) 0sks2 n ； ( 3 ) 如果彳的特征值均为实数，同时k 一2 n ，则最小的非齐次特征值小于a 的最 小特征值，最大的非齐次特征值大于彳的最大特征值； ( 4 ) 如果彳的特征值全为虚数，则k 可能为o 。 任力伟 7 1 在1 9 9 1 年对非齐次特征值问题解的存在性进行了研究，给出了在实 数域内问题( 1 - 1 ) 至少有两解的充分条件。类似于特征值问题的g e r s c h g o r i n 圆盘定 理，任力伟在文 e l 中给出了对于非齐次特征值问题的一个圆盘定理，即非齐次特征 值a 存在于以下区域：i a - a 盥i 墨k l + 打l b , i ，f - l ，万，并且给出了问题( 1 - 1 ) 按 范数确定a 范围的一个充要条件： 对于一般矩阵，卢旭光 9 1 在1 9 9 4 年应用拓扑和分析的方法在复数域内对非齐 次特征值问题进行了较为全面深入的研究，得到了非齐次复特征值的集合性质。其 中包括当参数t 变动时，相应的非齐次特征值集合的演变行为，并给出问题( 1 - 1 ) 存 在实解的一些充分条件以及当i 2 l 阻一心8 ：时，计算问题( 卜1 ) 所有的复解n ，x ) ， 这里r 是一个适当的常数，可以取成r t r a c e ( a ) n 等。 文献b o l 利用矩阵的谱分解给出了对称矩阵非齐次特征值问题解的存在性定理， 得到了较深入的结果。1 9 9 7 年，李志敏等人在文献 h i 中分析了非齐次对称特征值 问题解的存在性，得到了a 的最小的非齐次特征值小于a 的最小特征值丽大于 2 华北电力大学硕士学位论文 圳：一l 阻0 ：，最大的非齐次特征值大于4 的最大特征值而小于肛8 ：+ 1 1 4 ：。 1 9 9 8 年，文 1 2 , 1 3 1 通过对问题( 1 - 1 ) 的一种等价转化，将问题等价为方程，q ) = 0 的求根，讨论了非齐次代数特征值解的存在性定理，给出了两个半无限区间内解存 在的充要条件。即令b = 似+ 彳r ) 2 ，d 。与d ：分别为对称矩阵b 的最大和最小特征 值，若m i 笋f ( x ) 0 ( + ) ，则在( 一，d 。) 内有唯一解，否则无解；若m ，i n ，q ) 0 ( + o o ) ， 7 a i 一“2 则在似，+ ) 内有唯一解，否则无解。 黄贤通在文献1 1 4 1 中讨论了对称三对角矩阵基于极值约束下的非齐次特征值问 题，分析了解的存在性、解的存在区间及解的个数。他在文1 1 5 1 中又讨论了基于等式 约束的对称三对角矩阵的非齐次特征值问题。 一些工程问题，例如：工程结构计算、投入产出模型等，常常遇到对角阵非齐 次特征值的问题。2 0 0 3 年，李昆在文献 1 6 1 中，给出了不同条件下，对角阵非齐次 问题的特征值及特征向量的存在性定理。 文献 1 7 1 对非对称矩阵的非齐次特征值问题进行了研究，提出并讨论了两类特殊 的非对称矩阵( 不可约非对称三对角阵和终阶k 一循环t o e p l i t z 矩阵) 的非齐次特征 值问题，分析了解的存在性及解的个数。 近年来，出现了利用盖尔圆盘的放大缩小方法p s l ，在一定程度上给出了非齐次 特征值更小的估值范围。2 0 0 7 年，文献 1 9 1 得到了一个非齐次特征值分布的k 一型包 含域及若干估计，并给出了一个非齐次特征值的边界定理，改进了前人的一些结论。 之后文献 2 0 i 利用矩阵分析的方法，研究了矩阵的非齐次特征值的估计问题，给出了 一个新的矩阵非齐次特征值的包含域和边界定理，为线性微分动力系统的稳定性分 析提供了新的方法，改进了已有的相应结果。 综上，可以看出，对于非齐次对称特征值问题解的存在性和解的个数的研究已 经有了很充分的理论基础，但是对于非对称矩阵非齐次特征值解的存在性问题还有 待更进一步研究。 1 2 2 解的扰动性分析 1 9 9 3 年任力伟在文献p 1 中对非齐次特征值解的扰动作了一些分析，给出了一个 解扰动的估计不等式，对大矧和小两种情形作了专门讨论。 ( 1 ) 小情形 r m m m a t t h e i j 等人考虑了当剐很小的情形，他们讨论如下问题： a x 一缸+ e b ( 足够小) x r r ；1 3 华北电力大学硕士学位论文 得到，其敏感性依赖于a 的特征值问题的敏感性，若后者敏感，前者也敏感；后者 良态，前者亦良态。 ( 2 ) 一般情形 考虑 0 的情形，有 酬s 唑苦蛤掣 若a 的各个实对称值与a 不十分接近，且6 与向量似r 一盯) 。1 口一) 。2 b 之间夹 。角不太小，则问题良态，否则有可能病态，这得视具体问题而定。 ( 3 ) 大的情形 e h 一伽| | ，f 一似l ，有 l 飙ls ( 1 + 7 1 ) ( 1 一f 刈l 酗8 + 0 面8 ) 【2 ( 1 一f ) 3 1 】 得到，当庇足够小时，问题良态。事实上，当j l s _ 7 i n ，问题就是良态晶。 ( 4 ) a 对称的情形 悱i 哗嚣等铲 m 2 ， 记i ；a b 一6 ，e ) r 。设九为a 的最接近于a 的特征值，b 与九的特征向量夹角远 大于0 ，即 i x - & i 0 。 此时( 1 2 ) 的分子为西 笔f 恻蚓酗l i + o 曲分母为1 矿e 2 l ，其值主 要由西 毛f 决定，因此式( 1 - 2 ) 右边近似于 卜九嘤删制 从而问题良态。其它情况，问题可能病态，这由( i - 2 ) 的分母决定。 关于非齐次特征值的扰动性问题，研究工作还需深入进行。本文的第二章将详 细介绍对称矩阵非齐次项对非齐次特征值与特征向量的影响。 1 2 3 数值方法 1 9 7 3 年，g o l u b t 2 i 已经指出求解非齐次特征值问题可以转化为二次特征值问题， 4 华北电力大学硕士学位论文 然后再转化为求2 ，l 阶非对称矩阵的特征值问题，但是这样做的计算量和存储量都比 较大。 1 9 8 7 年，m a t t h e i j 和s 6 d e r l i n d1 6 1 研究了非齐次非对称特征值问题的乘幂法和逆 迭代法，利用了真解( a ，x ) 的某些已知信息和假定，并要求初始向量x 。充分靠近真 值z ，其收敛是一阶的。这两种方法可以方便地求出非齐次特征值及相应的非齐次 特征向量，但是依赖于初始值的选取，并且仅具有局部线性收敛性。 1 9 9 4 年，李志敏在文1 2 1 1 中，给出了对称矩阵非齐次特征值求解的数值方法， 该算法的优点是可以计算非齐次对称特征值问题的全部或最大或最小或任一给定 区间的实非齐次特征值及相应的非齐次特征向量。还给出了求解非对称矩阵非齐次 特征值问题的n e w t o n 法，该算法是二阶收敛的。李志敏给出的这两种算法比幂法 和逆迭代法的收敛速度快。 2 0 0 0 年，黄贤通在文献1 1 7 1 中给出了两类非对称矩阵非齐次特征值的求解方法。 其优点在于可以计算不可约非对称三对角矩阵的全部或指定区间的实非齐次特征 值及相应的非齐次特征向量。2 0 0 1 年，他在文献( 1 4 j 中给出了对称三对角矩阵基于 极值约束下的非齐次特征值问题的数值算法。并于2 0 0 4 年在文0 5 1 中给出了基于等 式约束的对称三对角矩阵的非齐次特征值问题的求解方法。 2 0 0 5 年，李海宁、李志敏等人【2 2 1 在总结了已有的几种迭代算法的基础上，给 出了求解非齐次特征值问题转化为方程求根的迭代法，并且进行了实验验证。该算 法在计算机中很容易实现，且收敛速度是二阶的。 综上，非齐次特征值问题的数值算法有很多，且日趋完善。但是利用同伦算法 求解该问题目前为止研究工作尚不多，本文在第三章中将着重介绍利用同伦算法求 解对称矩阵非齐次特征值问题的全部解的方法。 1 3 本文主要研究内容 鉴于上述分析，可知非齐次对称特征值问题还有很多方面值得深入的研究和继 续完善。 本文主要研究以下两个内容： 第一，关于非齐次对称特征值问题解的存在性以及解的个数的研究，目前已经 有了很多结论。但是，关于非齐次项对解的敏感性问题的研究尚未完全展开。本文 分析了非齐次项对其解的存在性的影响，得到了解对非齐次项的敏感性定理，并用 算例进行了验证。 第二，对称矩阵非齐次特征值问题的数值方法有很多，但是目前为止用同伦算 法求解该问题的研究还没有完全展开。在本文中，给出了求解对称矩阵非齐次特征 值问题的全部解的同伦算法。其基本思路是：根据不可约对称三对角矩阵特征值的 5 华北电力大学硕士学位论文 性质，将对称矩阵通过正交相似变换转换为一些低阶的不可约三对角矩阵。对每个 不可约三对角矩阵，利用同伦算法求出其对应的非齐次特征值，进而得到非齐次特 征值问题的全部解。 6 华北电力大学硕士学位论文 第二章对称矩阵非齐次特征值的敏感性分析 问题( i - i ) 中，若a 是，l ，l 阶对称矩阵，则称为非齐次对称特征值问题。为方 便起见，在接下来的讨论中我们称该问题为i s e p 。 在本章中，我们将分析非齐次项b 对非齐次对称特征值问题的敏感性，得到一 个敏感性定理，并通过实验进行验证。 2 1 解的存在性 i 司题i s e p 等价为 厂( a ) 一x 1x - 1 0 ( 2 1 ) 其中， 似一甜) z ) 一b 。 a 是对称矩阵，则存在咒阶正交矩阵p 和r l 阶实对角矩 阵d ，使得d = p r a p 。其中，d d i a g ( d 1 l 。，d 。，) ，d l 0 ，则在该区间无根；若m i n 厂q ) = 0 ，在该区间有 4 j a j 14 f d j ， 二个重根；若婴i 9 厂( a ) 0 ，则在该区间内有两个不同的根。 2 2 解对非齐次项的敏感性 在区间( 一0 0 ，d ，) 和似，+ ) 上，不论非齐次项如何变化，厂q ) 在区间_ o o ，d 。) 和 ，+ ) 上总是各有一个根，不需要再讨论。我们主要研究在有限区间 。，d m ) 上， 非齐次特征值随着c 的变化情况。由定理2 1 可知，只要观察对每一个i ，m i nf ( z ) 口i 口f 1 如何变化即可。 定理2 2 ： 对于c 的某一个分量c ，j 一1 ，力，随着l c ，i 的增加，每一个区间 似；，d ；+ 1 ) ，f 一0 一，s 一1 上的。r a ，i n ，厂q ) 都增加。 d f 0 时， 当c o ， 0 c j o m i n f ( a ) 0 ， a c j ，c 。 0 1 0 2 0 3 即m i n f ( z ) 是c j 的增函数； 即m i n f ( a ) 是c 的减函数。 解： 图2 - 1 分别给出了考虑c 1 的变化，取c 为( o 1 o 2 ，0 3 ) 、( 0 2 ，- 0 2 ，0 3 ) 、 ( o 3 ，- 0 2 ，0 3 ) 和( o 4 ，一0 2 ，0 3 ) 时的函数f l 、f 2 、f 3 和f 4 的图像；考虑c 2 的变化，取 c 为( 0 1 ，一0 2 ，0 3 ) 、( 0 1 ，一0 3 , 0 3 ) 、( 0 1 ，一0 4 ，0 3 ) f 和( 0 1 , - o 5 ，0 3 ) 时的函数f l 、f 5 、f 6 和f 7 的图像；考虑c 3 的变化，i rc 为( 0 1 ，一0 2 , 0 3 ) 、( o 1 , - o 2 ，0 4 ) 、( 0 l - 0 2 ，0 5 ) f 和 ( 0 1 一0 2 ，0 6 ) 时的函数f l 、f 8 、f 9 和f 1 0 的图像。 可以看出，当ic 。l ，lc ：l 和i c ，1 分别增加时，恶曼f ( z ) 和，m ，i n ，f ( z ) 也增加。 i z上 j 9 华北电力大学硕士学位论文 c 1 变化时c 2 变化时 c 3 变化时 例2 ：d 一 图2 - 1c l 、c 2 和c 3 分别变化时的函数图像 1o 0 o 0 o 2 0 o 0 0o3o 0 0 o 040 0 o o 05 ，c5 0 1 0 2 0 3 0 1 0 2 懈： 图2 - 2 给出了考虑c 分别取( - 0 1 , o 2 - 0 3 0 1 ，_ 0 2 ) r 、( 一0 2 ，0 3 ，- 0 4 ，0 2 ，加3 ) r 、 ( - o 3 ，0 4 ，- 0 5 ，0 3 ，- 0 4 ) r 和( _ o 4 ，0 5 ，一o 6 ，o 4 ，- o 5 ) f 时的函数f 1 、f 2 、f 3 和f 4 的图像。 可以看出，当i c ji ，j 一1 ，5 都增加时，跳厂q ) 、：m 。丑i 。n ，f ( a ) 、跳f ( a ) y f f i 卿n 。厂 ) 也增加。 耳 ) 1 0 华北电力大学硕士学位论文 r = = 1 _ l 1 2i l 三型 图2 - 2c 1 、c 2 、c 3 、c 4 和c 5 同时变化时的函数图像 1 1 华北电力大学硕士学位论文 第三章对称矩阵非齐次特征值的同伦算法 对称矩阵的特征值会有重根的现象，给我们的研究带来了不便。在本章中，我 们将对称矩阵通过正交相似变换转换为三对角对称矩阵，如果次对角线上元素为 零，则可将矩阵表示为适当的分块对角阵，使得每一块的次对角元素均不为零。已 知不可约三对角矩阵的特征值互不相同，因此我们先在第三节中讨论不可约对称三 对角矩阵非齐次特征值的同伦算法，进而在第四节中研究对称矩阵的非齐次特征值 问题的同伦算法。 、 3 1 同伦算法的概述 同伦本身是拓扑学中的一个概念，同伦算法是一种大范围求解非线性方程组的 整体算法。自从1 9 7 6 年，k e l l o g g 和y o r k e 、l i 利用微分拓扑工具解决了同伦算法 的全局收敛性问题，并用之给出了b r o u w e r 不动点定理的构造性证明，于是引起了 人们对同伦方法的重新研究。接着s m a l e 发表了全局n e w t o n 法的文章，c h o w 、 m a l l e t p a r e t 和y o r k e 利用他们构造的同伦给出了一系列重要的构造性证明，同时给 出了可用的算法，此后同伦算法的研究蓬勃发展。同伦算法经过三十多年来的研究， 现在已经发展成为一种十分重要的计算方法，得到了广泛的应用，出现了不少行之 有效的算法。 多项式方程组的同伦算法一直是一个十分活跃的研究领域。并且随着计算机技 术的飞速发展，同伦算法在并行计算方面的优势日趋明显。在同伦算法中，方程组 的每一个孤立解都可以独立地进行计算，从而使得数值求出大规模代数方程组的全 部孤立解看到了希望。 本文讨论的同伦方法是指同伦连续方法，或称为同伦延拓法。它的主要思想是 先选择一个简单的方程组q ( x ) 一0 ( 称之为初始方程组或初始系统) ，它的解已知 或者容易求解，然后构造同伦方程，即从q ( x ) ；0 到p ( x ) 一0 的形变 h ( x ，f ) 一( 1 - t ) q ( x ) + 炉( x ) ，t 【o ，1 1 ( 3 一1 ) 从t 一0 的各个已知解开始，跟踪同伦方程( 3 - 1 ) 的解曲线( 称为同伦路径或解曲 线) 至t 一1 处，就得到目标方程组p 伍) 一0 的解。这种方法就叫做同伦方法。 一个好的同伦h ( x ，f ) ，应该具有下列三条性质： ( 1 ) ( 平凡性)q o ) t0 的解是已知的； ( 2 ) ( 光滑性)当0st 1 时，h ( x ，f ) 一0 的解由有限条以t 为参数的光滑曲线 组成： 华北电力大学硕士学位论文 ( 3 ) ( 可达性) h ( x 山tp ( x ) = 0 的每一个孤立解都可由至少一条从t = 0 出发 的曲线跟踪得到，这些曲线的起点是日( x ，0 ) = q c x ) = 0 的解。 当同伦具有上述性质时，e ( x ) 一0 的全部孤立解可以通过数值跟踪从q ( x ) ；0 的解出发的光滑路径来得到。 同伦算法是一种全局收敛方法，它是目前求解多项式方程组全部孤立解的有效 的数值方法，代数几何中有著名的b 6 z o u t 定理。 定理3 1 ( b 6 z o u t 定理) 一个多项式组全部孤立解的个数不超过b 6 z o u t 数，即 h d ，其中d ，是方程组的第j 个方程的次数。 跟踪解曲线的标准数值方法和相关理论可以参考文献1 2 3 - 2 6 1 。其基本的思路是使 同伦恒等式 月o o ) ，f ) 墨0 ，v t 【0 ，1 】 ( 3 - 2 ) 成立，由已知的x ( 0 ) 出发连续变化t 直至求得x 0 ) 。式( 3 - 2 ) 两端关于t 求导得 日， p ) ，t ) x 7 ( f ) + 皿 o ) ，f ) 一0 ，v t 【o ，1 】 如果日， 0 ) ，f ) 对任意的t ( 0 ，1 ) 都是可逆的，则z o ) 的定解问题可写成 j x ) = - 【h 工 o ? ，：) 】。1 日r o ，f ) , te ( o ，1 ) ( 3 - 3 ) lz ( o ) = x o 这样，问题转化为常微分方程的初值问题。因此我们就可以采用e u l e r 折线法或牛 顿预估一校正法求得所需计算的零点，具体算法可参见 z 7 1 。 从上面的讨论可知，同伦算法的基本框架已经十分清楚。然而，具体应用时仍 有一定的困难。关键是如何选取合适的初始方程组q ( x ) ，使得既能保证其连接目 标之零点光滑道路的存在，又能使得数值跟踪这样的路径不会付出太大的代价。 我们要研究的非齐次特征值问题是多项式方程组，而且是典型的亏欠多项式方 程组。由 4 1 可知，对于亏欠多项式方程组，其b 6 z o u t 数远远大于解的个数，若采用 一般的算法就会造成很大的浪费。而采用同伦算法，根据目标方程组的结构特点构 造一种同伦，只需要跟踪有限的几条道路即可，大大的降低了计算量，减少了计算 时间。 在第三节中，对不可约对称三对角矩阵的非齐次特征值问题，我们就设法构造 这样的初始方程组，使得只需跟踪有限的几条同伦道路便可得到我们想要的结果。 3 2 不可约对称三对角矩阵特征值的性质 设，l n 不可约对称三对角矩阵 华北电力大学硕士学位论文 且屏一0 ，i 。1 2 ，j l 一1 。 称实系数多项式序列 a 一 口1p 1 卢l口2 声2 0 以一l 0 卢。- l 口。 o ) ，红o ) ，o ) 为o ) 在( 口，b ) 内的一个s t u r m 序列，如果它具有以下三个性质： ( 1 ) 最先一个多项式驴。 ) 在 ，b ) 内无公共根； ( 2 ) 序列中任意两个相邻的多项式在( 口，b ) 内无公共根； ( 3 ) 设z oe c a ，6 ) ，且妒，o o ) 一0 ，则驴卜l o o ) 与妒，+ l o o ) 反号 为了计算氕q ) = d e t 似一甜) ，引进多项式序列 q ) - d e t 芦l o f 2 一a卢2 p k 五q k d 一入t - 1 反- l口t a ，1s 七s 甩 ( 3 - 4 ) 即l ( x ) 表示a 的k 阶顺序主子式矩阵的特征多项式。规定f a x ) 一1 ，直接计算有 厂1 ( a ) 一a 。一a 厂2 q ) 一 ：- x ) l ( j t ) - a ? f o ( j t ) 一般地，用归纳法可证明 厶( 九) 一( 口。一x ) l 一。( a ) 一芦左， 一：( a ) ，k 一2 , 3 ，厅 序列 ( a ) ) 称为矩阵a 的特征多项式序列。 定理3 2 序列饥q ) 是 ( a ) 在( 一。o ，+ ) 内的s t u r m 序列。 关于对称三对角矩阵有以下的重要性质( 根的隔离定理) ，参见1 2 9 1 。 定理3 3 设a 由式( 3 4 ) 给出，屈一0 ，i = 1 2 ，j l 一1 ， 疋q ) ) 为a 的特征多 项式序列，则 ( a ) 一。有七个单根背，签，碟，并且它们与 一。( a ) 一0 的k 一1 个 1 4 华北电力人学硕十学位论文 单根硝卜n ，硝。，】似k - 以i ，有如下的隔离性质 砰 砰以 硝 a r 础 镌1 硝。 定理3 4 若a 是一个不可约三对角对称矩阵，则其特征值有如下关系 a f a j ， 1s i 一| s ，l 即任意一个不可约三对角矩阵的特征值互不相同。 3 3 不可约对称三对角矩阵非齐次特征值的同伦算法 3 3 1 同伦的构造和性质 不失一般性，在本节的讨论中，我们假定a 为珂阶不可约对称三对角矩阵，则a 的特征值互不相同。存在甩阶正交矩阵p 和甩阶实对角矩阵d ，使得dtp 丁a p 。其 中，d z d i a g ( a a ，九) ， 九。 问题i s e p 可等价为 ，( a ) ；x 1x 一1 ( 3 - 5 ) 其中，似一z o x ( z ) 一b 。 由第二章讨论可知，厂( a ) 在每个区间( ， + ，) 上都是严格凸函数，并且有唯一 的极小值r a i n 厂( a ) ，i = 1 ，以一1 。于是可知，对于不可约对称三对角矩阵a ，f ( z ) 有万一1 个最小值。 于是我们设想构造这样一种同伦道路，使得最终可以追踪到这刀一1 个最小值。 进而根据牛顿迭代法得到全部的非齐次特征值。 即考虑如下问题 r a i n 厂( a ) ax 1x 一1 s l m ( = 磁+ b 等价为 设膏。y ，则( 3 6 ) 变为 p ( x ) = ( 彳一村) x x 似一x t ) x b x x 砌卡多】 ( 3 - 6 ) ( 3 - 7 ) 华北电力人学硕十学 _ i 7 ：论文 则( 3 - 7 ) 就是我们要研究的目标函数。 关于初始方程组的构造，需要满足两个条件： 条件1 ：初始方程组是容易求解的。 条件2 ：初始方程组的每个解都互不相同。 根据它的结构特点，我们可以构造如下的初始函数 ( d x t ) y x 1 烈2 【p 嚣。6 j 。8 其中，d 为一个实对角矩阵，d = d i a g ( d l ，一，d 。) ，d 。 d 。式( 3 - 8 ) 的解 即为问题 厂( a ) = x 1x 一1 d x 一褪+ b 的n 一1 个最小值。显然，我们构造的初始方程组满足以上的两个条件。在区问 “。，d ：) ，似n - l , d 。) 内，我们可以由牛顿迭代法得到这珂- l + 最d 、值，且具有隔 离性。 于是可以构造如下的同伦方程： h q ) = ( a q ) 一) 】，一石 o ) 一z t ) x b x t y 其中a ( t ) 一( 1 - t ) d + t a ，f 【0 ，1 1 。 显然h ( a ，0 ) = q ( a ) ，h ( a ，1 ) 一p ( a ) 。 志悸甜彳童甜午m ) x ( m 1 ) 现任取( x ，y ，a ) 何q ( 0 ) ，则有a ( t ) 一m 非奇异，且 1 6 ( 3 - 9 ) 华北电力人学硕十学位论文 彳羔舡荨】一r 。苫彳c 壹盯 钗i 甜么。0 可知l 是一个非奇异矩阵，即有0 是h 的正则值。 o ( x ，y ，a ) 引理3 2 设h 由( 3 - 9 ) 所定义，则集合h 。1 ( 0 ) 是有界的。 证明：日的最高齐次多项式疗为 疗对( x ，y ，a ) 的j a c o b i 矩阵为 h = o ) 一a i ) y 似( f ) 一 x t y 南2 k o i o ( x y 一= 一i - 一，l j ，a ) i、二r f 彳 ) 一村 0 x l 0 彳( f ) 一 0 一y x o 此矩阵满秩，于是o 是疗的正则值。由文献 4 1 中的相关结论，可以得到疗只有平凡 零点，从而日一( o ) 是有界的。 引理3 3 设h 由( 3 - 9 ) 所定义，并假定 f ：( x o ) ，y g ) ，a o ) ，f o ) ) ( 3 1