（应用数学专业论文）几种特殊矩阵类的数值特征、算法和预处理技术.pdf

摘要 摘要 矩阵计算和特殊矩阵分析在计算数学、数学物理、经济学、物理学，生物学等 领域都有着广泛的应用本文主要研究了几种特殊矩阵的数值特征、算法和预处理 技术，主要内容和创新点包括， 1 对非奇皿矩阵进行了进一步研究，发现了一些较好的特征，提出了一种新 的非奇皿矩阵快速判别算法其较经典的算法而言，大大减少了计算量；且具有 简单直接。易于编程实现等特点从而促进了一些新的快速算法的产生和相应理论 的发展 2 提出了一种新的p - 矩阵子类一m b 一矩阵类研究了此类矩阵的性质及其 与最近出现的其他几个相关p 一矩阵子类的关系；基于这些关系获得了一种新的不 同于非奇日- 矩阵的非奇矩阵类，并进一步获得了一些新的一般实矩阵实特征值包 含区间 3 基于一些非负矩阵理论，推广或改进了一些经典的矩阵特征值和奇异值的 包含域，给出了著名的k yf a n 定理的几种推广形式，如下列区间就包含了矩阵a 的所有奇异值( 详见定理3 3 2 和3 3 3 ) ： e b ( a ) ：= uu z 0 ：i z 一啦i | z 一吩i ( p ( b ) 一k ) ( p ( b ) 一b j j ) ， ( 1 ) i = 1 ，p ( a ) 或 口( 4 ) ：= u = 0 ：j z o js i i ( p ( b ) 一k ) ) ， ( 2 ) c ( a )1 i e 其中对任意i j 非负矩阵b = ( 峙) 舻，“满足幻m a x l 叼i ，1 i m 上述结论的个重要意义在于对个对角元为正的矩阵来说上述包含域形式可 以同时包含其所有的特征值和奇异值( 见注3 3 2 ) 另外，关于奇异值也给出了个 几乎最优的“g e r j g o r i n - t y p e ”型包含区间( 详见定理3 3 9 ) ： g ( n ) ：= 0 ，m 。，i n 。蟛r n a 鱼xm a x 去耋i 壶薹i 啄h 】， ( s ) 其包含了所有与矩阵a 等模的矩阵( 记作n ：= b = ( ) ：l 峙i = l l ，ls i ，j n ) 的所有奇异值，并且从理论上证明此区间的上界对某些矩阵来说是精确的 4 证明并改进了关于 乒矩阵a 与其逆阵h a d a m a r d 积最小特征值( q ( a0 a - 1 ) ) 下界的f i e d l e r - m a r k h a m 8 猜想； 、j 2 一n 一 n ， 一 i a0a “ 其中n 为m 一矩阵a 的阶数 5 对般迭代矩阵m 一1 的谱半径p ( m 。n ) 的估计给出一种新形式( 详见 定理4 2 2 ) ： 肚。) 浃m a x 坠学， ( 5 ) 辞巧 其中f = 阢，2 ，厶】是个满足一定线性关系的岱函数，a = i m l l r n j j i 一 ( m ) 疗( m ) ，b 7 = m l l n 晰+ 仉i ”协i + f ( m ) f j ( n ) + ( ) 办( m ) 和c = 一【i “菇i + ( ) 办( ) 】其在一些情况下优越于一些经典的结果，最后将其推广到了分块矩阵 的情形 6 对一般对角占优三对角矩阵给出了逆元素的新估计，其优于近期的一些著 名结果，并对三对角日一矩阵的逆元素的符号首次给出了一种简单计算公式( 详见 定理5 2 1 ) ： “若a = f i d i a g n i ，氏，c i ) 是三对角日一矩阵，那么a 。= ( c f j ) 存在且有 ( 1 ) s i g n ( q j ) = ( 一1 ) ( 件# ) s i g n ( b jl ia k b k ) ，i j ； ( 2 ) s i g n ( c ， ) = s i 乒m ) ，i = j ； ( 3 ) s i g n ( c i z ) = ( 一1 ) “+ j ) s i g n ( b j c k b k ) ，i 00 n ) 时，我们有 ( 4 ) s i g n ( c i d ) = ( 一1 ) o + j ) s i g n ( ) ，i j ； k = j + l ( 5 ) s i g n ( c t # ) = ( - - i ) ( + j ) s i g n ( 1 - io k ) ，i j ； ( 2 ) s i g n ( c ， ) = s i g n ( b 1 ) ，i = j ； ( 3 ) s i g n ( c f d ) = ( 一1 ) “+ j ) s i g n ( b # 兀c k b ) ，i 00 ) ，w eh a v e ( 4 ) s i g n ( 盘j ) = ( 一1 ) o + # ) s i g n ( 1 - i 口k ) ，i j ； = j + l ；一1 ( 5 ) s i g n ( c j ) = ( 一1 ) ( i + j ) s i g n ( r i q ) ，i 0 解 a + | | a i i f i i a 1 2 d e t a t r a a 口 a t ( a ) r ( a ) p ( a ) a ( a ) m ( a ) ao b 以( q 卢) d i a g ( 口1 ，靠) 主要符号表 自然数集 1 ，2 ，n ) 单位矩阵 复( 实) m 维列向量空间 m 峻( 实) 矩阵集 n 阶非奇异 厶矩阵类 a g ”，”的各元素取绝对值的矩阵 矩阵a 是非负矩阵 矩阵a 是正矩阵 a 的转置 a 的共轭转置 a 的f r o b e n i u s 矩阵范数 a 的矩阵2 一范数 a c n “的行列式 a e n “的迹 ( 通常指) 矩阵a 的特征值 ( 通常指) 矩阵a 的奇异值 矩阵a 的最大奇异值 a g ”，“的直接图或有向图 ( 通常指) 矩阵a 的谱半径，若a 为非负矩阵，即为p e r r o n 根 矩阵以g m “的谱( 所有特征值的集合) 矩阵以的比较矩阵 a ，b e t ，i ，“的h a d a m a r d 乘积 由指标集a ，绷自定的矩阵a 的子矩阵 以口l ，为对角元的对角矩阵 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：日期：五慨月乙日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定)， 虢够脚导师虢乞珈 1日期：年月 日 第一章绪论 第一章绪论 随着现代科学技术的迅猛发展和计算机的普遍运用，数学的独特魅力，在借助 于计算机这一强大的工具作用下，在解决科技生产中的重大实际问题的过程中正得 以了充分的体现 在数学中，确立矩阵概念和产生“矩阵”一词的动机是试图为研究行列式提供 适当的代数语育如今，矩阵已是数学上的个重要概念由于它描述问题表达简 洁，刻画实质深刻等优点，近几十年来已成为解决科技生产中的重大实际问题所最 常用的方法之一譬如，在概率论和经济学等学科中经常用的非负矩阵；在均衡论、 投入产出分析和增长模型的研究中产生的 厶矩阵；在控制论及神经网络大系统的 稳定性、线性时滞系统的稳定性研究中需要的日矩阵及正稳定矩阵等等由于这 些特殊矩阵应用背景的广泛性，近年来国内外对这方面的研究工作相当活跃已经 成为经济学、生物学、现代物理学等领域处理数学问题的不可缺少的强大工具，成 为。大规模科学工程计算理论”的一个重要组成部分 下面仅就本文所涉及的几个特殊矩阵类进行简要的回顾与阐述，关于其进一步 的研究，可参见文献f 1 , 2 ，3 】 ( 1 ) 非负矩阵是元素非负的实矩阵其重要理论源于1 9 0 7 年由p e r r o n 发现， 后来由f r o n e n i u s 发展的关于非负矩阵谱半径的个优美结果- - p e r r o n - p r o n e n i u s 定理： 定理1 1 1 1 1 , 2 】设b 0 ( b 0 ) 是一个n 阶不可约非负矩阵( 正矩阵) ，则矩阵 日有且仅有一个最大正特征值p ( b ) 使得b x = p ( 口) x 成立，其中p ( b ) 被称为非 负矩阵口的p e r r o n 根。正向量x 称为p e r r o n 向量 注意到b 和p ) 皆是非负的，因此一般来说， = c x ( e 0 ) 也可以被看作 p e r r o n 向量在本文中，不失一般性，我们假设每个p e r r o n 向量皆被尺度化使得 其最小分量为1 由于非负矩阵理论与数值分析、组合数学、概率论和经济数学等学科有密切联 系，近年来，发展迅速，已成为数值代数中最活跃的领域之一关于它的其他优美 结果和具体应用，可参见文献f 2 】 ( 2 ) 另外，肛矩阵类也是极其活跃的领域之一，例如，在偏微分方程中的有 限元方法、运筹学中的线性互补问题、概率统计中的马尔科夫链等问题中经常应用 m 一矩阵理论在 乒矩阵的许多可能的定义中，下面给出的定义强调了这类矩阵 与非负矩阵的重要联系z 定义1 1 1 1 1 , 2 j 实矩阵a 被称之为 扛矩阵，如果这里存在一个乱阶非负矩阵 电子科技大学博士学位论文 b 和某一实数a 使得 a = o d b ，a j 9 ( b ) ，( 1 - 1 ) 其中，是一与矩阵a 同阶的单位矩阵另外，若a = p ( b ) ，那么a 被称之为奇异 a 扛矩阵；若a p ( b ) ，那么a 被称之为非奇异m - 矩阵，记为a m 。在本文 中，若没有特别说明，主要涉及的是非奇异m 矩阵 起先， 扛矩阵是由a m o s t r o w s k i 于1 9 3 7 年引入，后来，随着对 扛矩 阵的不断研究，人们发现了m 一矩阵的个重要性质，即若实矩阵a 的主对角元全 为正值，非对角元全非正( 即a 为l 矩阵) ，则a 是a 扛矩阵当且仅当a 为拟对角 占优矩阵( 近几年来，一些学者又称它为广义对角占优矩阵【4 5 】) ，也就是说存在正 对角矩阵d ，使得a d 严格对角占优 1 1 如今，在许多数学家和经济学家的共同努 力，使得m 矩阵理论得到迅速发展并且日臻完善，其中刻划非奇异的 扛矩阵的 等价命题就有5 0 多个1 ( 3 ) h 一矩阵是a 正矩阵的个自然推广，它们之间一般通过下列关系直接建立 联系： 定义1 1 2 【2 1 个矩阵a 为卜矩阵当且仅当它的比较矩阵m ( a ) = ( m 玎) 舻一为非奇异朋二矩阵，其中 m “= i 口i ，玎= 一i 。莳l ，i ，j n ，i j 另外，在本文中经常用到的另一等价定义为： 定义1 1 3 【2 】一个矩阵a = ( a o ) g ”为肌矩阵当且仅当存在正对角矩阵 d = d i a g ( d l ，d 2 ，d | i ) ，使得a d 严格对角占优，即对任意j n ，有 i 硝蚓而 显然，皿矩阵除包含上面的m - 矩阵外，还包含控制论及电力系统中出现的对角 占优矩阵、非零元素链对角占优矩阵等等 目前，对日一矩阵的研究主要集中在两个方面，一是研究它与其他特殊矩阵类 的关系与代数性质( 见 6 ，7 ，8 】) 及其在不同学科分支中的应用一如最优化中的线性 互补问题( l c p ) ；二是研究与它有关的迭代算法的收敛性分析，如迭代矩阵的谱半 径的估计、误差传播以及算法的稳定性等等 ( 4 ) 与日一矩阵和 乒矩阵有着紧密联系的一类特殊矩阵是p 一矩阵，它是所有 主子式均大于零的实矩阵一般地，实日一矩阵是p - 矩阵当且仅当其所有对角元 均为正值p ，1 0 l 今后，为了方便，在本文中将把所有对角元均为正值的日一矩阵称 为风矩阵l g l ( 记为口 ) 关于它与其他矩阵类之间的联系，可详见文献【2 ，6 】 最后，关于主子式问题，我们给出下列著名的b a u a n t i n e - f i s h e r - f u l l e r 定理： 定理1 1 2 7 1 设a 为n 阶实的或复的矩阵，若a 的所有顺序主子式均非零，则 存在对角矩阵d ，使得a d 的所有特征值是实正数，且严格分离 2 第一章绪论 显然，上述 扛矩阵、日- 矩阵和p 一矩阵皆具有这个优美性质然而，这个定 理的逆命题是否成立1 7 至今仍未见解决 1 2 线性方程组求解的主要内容、意义及面临的挑战 众所周知，许多实际问题最后常常归结为一个或一些大型系数矩阵为特殊矩阵 的线性方程组； a z = b ，。，b r ，i( 1 - 2 ) 的求解问题 1 1 - 2 0 1 如在材料模拟与设计、电磁场计算、计算流体力学和核爆数值 模拟等领域中经常要求解微分方程，并通过有限元或有限差分与有限体积等方法进 行离散，最后转化为非线性方程组或大型甚至超大型稀疏线性方程组然而，一般 地非线性方程组的求解又通过n e w t o n 迭代或简单迭代线性化为稀疏线性方程组 如二维三温能量方程组离散求解问题； 问题描述【1 1 二维三温辐射流体力学在惯性约束聚变( i c f ) 的模拟中扮演着十 分重要的角色，其能量( 电子温度正，离子温度正和光子温度露) 方程可描述为 在一定的边值条件下，如固壁和轴对称条件；( r ) 。= 0 ，o = e ，i ，r 和自由面边界 条件t ( e k = h = 0 ，砟= 霉( z ，y ，t ) ( 此处n 表示法方向) ，采用一致的四边形 网格离散上述偏微分方程( 1 - 3 ) 后，就得到个非线性方程组当采用n e w t o n 迭 代求解，并对网格节点采用自然排序时，问题就转化为求解以如下矩阵 a = b l c 1 a 2b 2c z a m 。1 b lc m 一1 a mb 仇 ( 1 - 4 ) 作为系数的块三对角线性方程组问题，其中最为块三对角矩阵，a 和g 为对角 阵“m ) 如今，随着对计算精度要求的提高，得到的稀疏线性方程组的规模越来越大( 如 上述问题系数矩阵a 的阶数已达1 0 0 多万阶) ，稀疏线性方程组的求解在整个计算 过程中越来越成为瓶颈对此类矩阵，直接法( 如g u a s s 消元法) 存储需求和计算 1 这个问题于1 9 8 8 年在加拿大v i c t o r i a 的国际会议上由著名学者d g e x l s o n 提出川 3 藏篙暗 电子科技大学博士学位论文 量都比较大，且难以控制从而迭代法，特别是与预处理技术相结合的k r y l o v 子 空间方法正逐步受到青睐 1 l ，1 3 ，1 4 ，1 8 下面我们就几种常见的迭代法予以简单介 绍，特别是k r y l o v 子空间方法及其相应的预处理技术： ( 1 ) 经典迭代法1 3 】= 其一般可表述为 。k = 妒i ( 茹一1 ，z k 1 ) ，七= z ，z + 1 ( 1 - 5 ) 其中慨称作迭代算子， 2 3 0 ，z f - l 为迭代初值，通常称迭代法( 1 - 5 ) 为l 步迭代 法1 = 1 时，亦称为单步迭代法如果迭代算子帆与k 无关，即m 三则称 迭代法( 1 - 5 ) 为定长迭代法，否则称为不定长迭代法 对于单步定长迭代法，最常见的是所谓的分裂迭代法，令a = m n ，则 z k = m 一1 n x 一1 + m 一1 b ，= 1 ，2 ，( 1 - 6 ) 其中m _ 1 n 称为迭代矩阵，z o 称为迭代初值对m 取不同的值，就会得到不同的 迭代算法，比如j a c o b i ，g a u s s - s e i d e l ，s o r ，a o r 等方法_ 眭来说这类方法收敛的 充要条件是要求m - 1 的谱半经小于l ( 即p ( m _ 1 n ) 1 ) 尽管定常迭代法具有 数学的雅致，但有严重的缺陷：其一，其收敛速度一般受谱半经p ( m - 1 n ) 大小的制 约，如当p ( m “n ) 非常接近1 时，其收敛速度通常很慢；另外其迭代矩阵m - 1 的谱，预先很难计算，而且关于收敛参数缺乏充分的一般性为此，h a g e m a n 和 y o u n g 在1 9 8 1 年提出了自适应参数估计过程 ( 2 ) k r y l o v 子空间方法，创建于1 9 5 0 年，以著名的俄国科学家n i k o l a ik r y b v 命 名的k r y l o v 子空间方法，被认为是2 0 世纪最优秀的十大算法之一k r y l o v 子空间 方法最简单的情形是共轭梯度法它是由l a n c z 0 8 1 2 1 1 ，h e s t e n e s 和s t i e f e l l 2 2 1 分别独 立和几乎同时发现的用于求解对称正定的系数矩阵线性系统的一种方法其基于线 性方程组的变分原理，把求解线性方程组( 1 - 2 ) 等价于个多元二次函数眨函) 极 小化问题但在其后2 0 多年，人们一直认为这类方法是数值不稳定的，很少用于实 际计算直到7 0 年代初p a i g e 在其著名的博士论文矧中重新研究了l a n c e s 方法 以及8 0 年代初s a a d 【2 q 重新研究了a r n o l d i 方法，才使人们重新认识了这种方法 之后，人们又做了大量的理论分析和数值试验，充分认识到k r y l o v 子空间方法是 求解大型线性方程组和大型矩阵特征值问题的一类有效的方法如今，在c g 迭代 法的基础上又推广得到的方法有m i n r e s ，s y m m l q ，g m r e s q m r ，b p c g s t a b 等等关于k r y l o v 子空间方法的具体描述可进一步参见文献1 1 ，1 3 1 在本文中， 我们主要采用的是针对非对称线性系统的且较稳定的b i - c g s t a b 算法； b i - c g s t a ba l g o r i t h m 1 1 , p 2 1 “ f o rs o l v i n g t h e l i n e a rs y s t e m a x = b ，z ，b 舻： 1 c o m p u t er 0 ：= b a x o ；r 5a r b i t r a r y ； 2 p o = r o 3 f o rj = 0 ，1 ，2 ，u n t i lc o n v e r g e n c ed o ： 4 第一章绪论 4 哟= ( 吩，t 6 ) ( a p j ，喵) 5 3 j = r j 一a p j 6 “各= ( a a j ，) ( a 勺，a s j ) 7 ；r j + l = z i + a j p i + u j 3 i 8 r j + l = 彤一w j a s j 9 易= 簪嚣 1 0 p j 札= r j + l + 6 j b 5 一w # a p # 1 1 1 e n d d o 般来说，此类迭代法的收敛性依赖于系数矩阵的谱分布，谱分布越集中，收 敛越快( 这一般都需要事先经过预处理后才能达到，见下( 3 ) ) 然而，对于大型矩阵 来说，若直接计算其特征值是很不容易的，因此对于这样的系数矩阵的谱半径给出 尽可能精确的估计，具有重要的理论意义和实践价值 ( 3 ) 预处理( p r e c o n d i t i o n i n g ) 技术，这一概念首先由美国著名学者图灵于1 9 4 8 年提出，随后c o n c u s 、g o l u b 和o l e a f y 等著名科学家进行了深入研究并将其 应用于数值计算中，是数值计算领域的重大突破此后，该技术引起了国内外许多 学者的关注，并被大量应用于计算科学、计算物理、计算地质学、经济学、最优控 制理论和软件开发等相关领域【1 3 1 其主要目的就是试图改进系数矩阵的谱属性， 将线性方程组( 1 2 ) 转换为具有更好性质的另外一个等价的系统c l a c n y = c l b ， y = g i l z 以便于更容易求解，其中既，c k 舻一为非奇异矩阵，分别被称为左、 右预处理子在很多情况下，c l 和c k 的联合作用效果类似于单独一个左预处理 子g ，即类似于c a x = c b 可以确认，大规模线性方程组的预处理技术的研究在 科学工程计算和国防建设中有着极其重要的理论价值和极为广阔的应用前景 一般地，良好的预处理子应该满足以下要求【1 9 | ： ( a ) 预处理后系统更容易求解； ( b ) 预处理子的构造和应用代价应该较低 在实际应用中，在这两种需要之间达到一个平衡是必要的近几年，关于大型线性 方程组所采用的预处理技术主要有( 【1 9 】) ： 1 稀疏近似逆方法( s a i ) ：稀疏近似逆预处理子是一类在应用时具有天然并行 性的方法已有证据显示这类预处理子可解一些i l u 预处理子难以求解的问题其 大体分为三类1 2 5 j ： 第类是基于对近似求解来构造稀疏近似逆。般归结为求解依赖某种稀疏性 约束的f r o b e n i u s 范数极小化的最优化问题； 第二类是基于分解的s a i ，现有f s a i 、a i n v 和s a i n v 等形式，其缺点是 技术的实现依赖于个稀疏性模式，目前对一般稀疏矩阵没被很好的研究； 第三类是基于i l u 分解的s a i 2 不完全l u 分解( i l u ) ：i l u 由美国著名计算数学专家r s v a , r g a 教授于 6 0 年代首次提出，是目前最常用的预处理技术之一但i l u 分解有个主要弱点， 5 电子科技大学博士学位论文 即不易并行化为了使i l u 分解适宜于向量计算机及并行计算，有专家和学者提出 了b i l u f ”】，b i l u m 2 7 】等等，并考虑了并行两水平及多水平i l u 预处理等方法 3 多水平预处理子。这类方法基于多水平技巧( 例如多重网格) ，特别适用于规 则阿格划分下的偏微分方程离散化后的线性方程组这些方法包含一些类似不完全 分锯和稀疏近似逆预处理等方法的变种近来，z h a n gj u n l 2 目提出了结合s a i 的多 水平i l u 预处理技术，具有可控的稀疏模式和增强的并行性特点另外，研究并 行的代数多重网格( a m g ) 以及其他代数多水平方法已被认为是个难题最近， ve h e n s o n l ”j 以及a k r e c h e n 3 0 j 等人在这方面取得了进展，但还有许多工作要 做，特别是不定问题，3 d 问题和p d e s 系统 4 对角尺度化( d i a g o n ms c a l i n g ) 预处理子，对比较病态的系数矩阵的方程 组，如般二维椭圆型方程组的差分方程，其系数矩阵往往为弱对角优势为此常 采用对角尺度化预处理子来增强对角优势获得好的收敛效果1 3 l | 然而，目前预处理技术在诸多应用中还远没有达到满意的程度因此，如何充 分发挥计算机的潜在性能，研究面向具体的计算工程问题中的大型线性系统的高性 能预处理子就显得尤其重要和突出 1 3 本文的研究内容、方法与主要贡献 针对上述问题，并结合一些实际中大型线性系统的特点，本文就科学计算中大 型特殊矩阵的数值特征、算法和预处理技术进行了若干研究其内容主要涉及非奇 弘矩阵和p o 矩阵的研究、以及基于非奇准则的矩阵特征值和奇异值的包含域；迭 代矩阵m - 1 的谱半径的估计；一般三对角矩阵逆元素的快速计算和块三对角线 性系统预处理技术等等 本文所采用的研究方法包括： ( 1 ) 线性代数的基本理论；( 2 ) 非负矩阵、非奇 日- 矩阵、 扛矩阵和( 块) 三对角矩阵等特殊矩阵理论；( 3 ) 矩阵分块和s h u r 补 降阶技术；( 4 ) 矩阵的( 不完全) 分解和迭代算法；( 5 ) 线性矩阵不等式理论；( 6 ) k r y l o v 子空间方法与预处理技术；( 7 ) 二阶线性或三阶线性递推( 归) 算法等等 主要内容和刨新点包括s 1 ，对非奇孔矩阵和非奇矩阵的本质，做了进一步研究，发现了一些较好的 特征，提出了一些新的非奇何一矩阵快速判别算法其较经典的算法而言，大大减 少了计算量；另一个方面，较最新的研究成果，具有简单直接的特点，且易于编程 实现从而促进了一些新的快速算法的产生和相应理论的发展； 2 、结合非奇县矩阵和p 一矩阵的理论，提出了一种新的p _ 矩阵子类一m 口一 矩阵类研究了此类矩阵的相关性质及其与最近出现的其他几个相关子类的关系； 基于这些关系获得了一种新的不同与非奇日一矩阵的非奇矩阵类从而进步获得 了一些新的实矩阵的实特征值的包含区间； 3 、基于一些非负矩阵理论，推广或改进了一些经典的矩阵特征值和奇异值的 包含域一给出了著名的k yf a n 定理的几种推广形式，并获得了可以同时包含 6 第一章绪论 个矩阵的所有特征值和奇异值的包含域；另外，对奇异值也获得了几乎最优的 。g e r j g o r i n - t y p e ”型上界包含区间； 4 、证明并改进了关于 乒矩阵与其逆阵h a d a l a r d 积最小挣匝值下界的f i e d l e r - m a r k h a m 8 猜想； 5 、对迭代矩阵m _ 1 的谱半径p ( m - 1 n ) 的估计给出个新的形式并将其推 广到分块矩阵情形； 6 、对一般对角占优三对角矩阵给出了逆元素的估计，并对非奇三对角日一矩 阵的逆元素的符号给出了简单计算公式；特别地对一般三对角矩阵的逆给出新的表 示形式并给出了一种新型符号算法； 7 、针对上文提到的块三对角矩阵类，结合阶梯矩阵和多项式预处理的技术， 提出了一种新的可高度并行的预处理子，数值试验表明其可优越于著名的多水平不 完全l u 分解( i l u ( k ) ) 预处理子； 8 、孝1 - x 于最近一种常用的n e w t o n 型预处理方法，通过修改其迭代策略获得一 种至少三阶收敛的加速方案 1 4 本文的结构安排 本节将对本文所做工作作以简单介绍除本章对本文的研究背景、对象和研究 方法给出了概要性介绍外，下面的第二章到第七章主要总结了迄今作者本人在这一 领域所作的几点工作其主要内容已在前面作了介绍，各章的结构安排如下t 在第二章中主要研究非奇上卜矩阵和p - 矩阵类的性质，获得了一种改进的 g a u s s - s e i d e l 型非奇皿矩阵判别算法随后对p 一矩阵的几个子类进行了研究，获 得了几个新的实特征值的包含区间 在第三章中首先研究矩阵特征值和奇异值的估计与包含域，最后对 扛矩阵与 其逆阵h a d a a n a r d 积最小特征值下界的f i e d l e r - m a r k h a m b 猜想进行了深入研究获 得了满意的结果，并将其应用于行列式的估计 在第四章中研究了迭代矩阵m - 1 的谱半径估计，获得一个新的结果后，又 将其推广到分块矩阵的情形 在第五章首先对三对角矩阵逆元素的估计与符号分布进行了研究，随后将研究 方法推广到一般的三对角矩阵，获得了计算三对角矩阵逆元素的新型符号算法 在第六章首先研究了前面提到的大型稀疏块三对角矩阵( 1 4 ) 的一种具有很高 并行性的多项式预处理技术，随后对一种n e w t o n 型预处理方法进行了研究，改进 了其收敛速度 在第七章中对全文进行了总结，并提出了对今后进步工作的展望 7 电子科技大学博士学位论文 2 1 引言 第二章非奇日- 矩阵和p - 矩阵类的研究 正如上一章所述，日矩阵是一类在工程和科学计算中有着广泛应用背景的特 殊矩阵类【2 3 2 一然而，如何判断个矩降是日矩阵，却不是很简单，特别是对大 型矩阵因此，给出一些县矩阵判别算法是非常重要，在实际应用中也是必不可少 的个前提，见【5 ，3 4 ，3 6 ，3 7 最近，一种有趣的算法被k o j i r o n 提出，我们总结如 下：对给定的矩阵a = ( ) g ”，让记为矩阵a 的第 个列向量对任意。n ， 记兄= 例i i ，t l = 南和1 ( a ) = 训啦d 最，i ) ，2 ( a ) = 1 ( a ) 那么下列a l g o r i t h ma 可以判别矩阵a 是否为点卜矩阵 a l g o r i t h ma 1 4 】 i n p u t ：a m a t r i x a = ( ) g ” 1 i fn 1 ( a ) = 口o t 啦i = 0f o rs o i n ei n ，ai sn o ta nh - m a t r i x ，s t o p ： o t h e r w i s e i ft l = 0f o ra l li ，ai sa nh - m a t r i x ，s t o p ：o t h e r w i s e s e tt l = m i n l 叼，彤i p 1 ) k = lk = l 在文献【4 0 】中，把此类矩阵称为口矩阵( b ) ，并指出其实为一个p 矩阵这个性 质后来被用作定位个实矩阵的实特征值： 定理2 1 1 设a = ( 吼j ) 舻一，a 是矩阵以的- - 4 实特征值那么 9 # 【j 7 鼠， p 2 ) 其中 鲰：= 一口一。缸i t - a , t l ，一r + 。和i 叮一峨t i ， 付：= m a x o ，iv j i ) ，叮：= m i n o ，a 0lv j t 随后，文【4 1 1 介绍了p - 矩阵另个子类双b - 矩阵( d b ) ，其包含了上面的b 矩阵，即个对角元素满足下列关系的实矩阵a = ( ) ： 口k k 懂，v k 1 ，2 ，n ) 是双b - 矩阵，若对所有t j6 i i j ， ( 一寸) ( 一哆) ( 峭( 寸一) ) ( 。却( 哆一t ) ) ( 2 - 3 ) 相似于文献f 4 0 】，在文f 4 1 】中一些关于双b - 矩阵的性质也被研究，其也被用 来定位实矩阵的实特征值获得了一个类似于著名b r a u e r 定理l 删的包含区间t 定理2 1 2 设a = ( a i j ) 形- - ，对任意i 6 n ，q ：= 一寸，一叮j ，且对任 意i ，j n , i j ，定义( 不失一般性地，假设s 锄) ：= u u b 。， ( 2 4 ) 其中r ( b + ) = 判( 付一) ，见( b 一) = k 扣( 一r ) 码一伽6 ( 一c o ，) ：i o “一寸一z l l o z 一学一圳s 冠( b + ) r j ( b + ) ) ， ：= 和( ，a z ) ：1 叮一z “一时一刮s 忍( b 一) 岛( b + ) ， 9 电子科技大学博士学位论文 b 。3 ，：= z ( a j i ，o o ) ：i n “一r f z f 扣撕一r i z i r 。( b 一) r j ( b 一) ) 那么，所有矩阵a 的实特征值属于区间 尽：= ( u 兰。g ) u ( u 罐，曰o ) ( 2 - 5 ) 在本章的第二部分，我们将介绍另一p - 矩阵子集一m b 一矩阵，包含了上面 的b 一矩阵和双b 矩阵作为个数值实验的结果我们也确立了它与已知的其他 p 一矩阵子集的关系最后，一些m b 一矩阵的子集也被用来确立个实矩阵的实特 征值包含区间，其有力的改进了上面定理2 1 1 2 的结果 2 2 非奇h - 矩阵的迭代判据 首先，我们需要回想下列定义和引理让a ，卢分别是集合n 两非空子集我 们记矩阵a 的行列指标分别位于集合a ，卢的子矩阵为a ( a ，卢) ，特别地，我们把 a ( a ，a ) 简记为a ( a ) 引理2 2 1 若a = ( ) c ”是皿矩阵，那么j 口，其中，= a f a l l 例b ，i ) 引理2 2 2 【2 】若a z ”，其中z ”= a 舻一i 0 ，i j ) ，那么下列三个 条件等价： a ) 矩阵a 是 扛矩阵； b ) 矩阵a 的所有主子式皆是正的； c ) 矩阵a 的每个主子矩阵皆是m - 矩阵 引理2 2 3 矩阵a a “是日一矩阵当且仅当g a d 是皿矩阵，其中q d 是 任意正对角矩阵 另外，最近文献【5 提供了个有趣的算法，其不但能用于判别卜矩阵，而且 在某些情况下也可以用来计算个非负矩阵的谱半径t a l g o r i t h mb 【5 1 f o ra g i v e nc o m p l e x m a t r i x a = ( ) ，0 ，i ： 1 f o r i n ，c o m p u t e 厩= “i i 2 s e t 赴= 0 f o ri = 1 ，2 ，n ，i f | i 风，t h e ns e tt = t + 1 3 i ft = 0 t h e np r i n t ai sn o ta l lh m a t r i x ：s t o p 4 i ft = n t h e np r i n t ai sa l lh - m d t r i x ：s t o p 5 f o ri = 1 ，2 ，n ，c o m p u t e 口jo d = 罴，a i l = 吐，j = 1 ，2 a i i a i i， 也2 丽2 啦，2 ，n ， w h e r e 0i sap o s i t i v ep a r a m e t e r 6 g o t os t e p l 1 0 第二章非奇日一矩阵和p - 矩阵类的研究 现在我们用下列定理，来进一步解释问题2 1 ，它的证明采用了文删中引理 2 2 的技巧 定理2 2 1 如果a l g o r i t h ma 产生个无穷迭代序列( 即没有终j d ，那么矩阵 a 不是日一矩阵 证明；既然a l g o r i t h ma 产生一个无穷迭代序列，这就意味着对所有n = l ，2 ，( 这里n 是迭代麴，1 ( a ( 曲) o ，n d a ( “) ) n 和a l l 0 0 ) 情况l ：若1 ( a ) = n ，由a l g o r i t h ma 中步8 ，那么对所有 n ，如= 1 ( 否则a l g o r i t h ma 终止) ，因此，= o 这样由引理2 2 1 ，我们知道矩阵a 不是日- 矩阵证明完成 情况2 ：若1 ( a ( ”) ) n ，那么n 2 ( 由) n 由a l g o r i t h ma 中步3 ，容易推 出，对所有n = i ，2 ，白 0 且0 ：m j 0 对任意 ，j n 对a ( ，由( 2 - 1 ) ，推出对任意s ，t n ， d 譬) 是个非增有界序列这样l i i i la y 存在对所有s ，t n 即l i l na ( m ) 存 在设l i r aa ( m ) = b 然而，对任意i 2 ) ，t i 1 这样b ( n 2 ) ) 不是h - 矩 阵由定义1 1 2 和引理2 2 2c ) ，b 不是m 矩阵因此，由引理2 2 3 ，a 亦不是 皿矩阵证明完毕 口 注2 2 ，l ：根据上述结论可知，对非m 矩阵，a l g o r i t h ma 需要大量迭代的原 因是对i n 2 ( a ) ，让如= 1 太强根据文【4 ，5 ，3 4 】，我们下面介绍另一算法，其减弱 了 的值 1 1 电子科技大学博士学位论文 a l g o r i t h ma ，： f o rag i v e nc o m p l e x m a t r i x a = ( ) ，a l l 0 ，i ： 1 f o r i n ，c o m p u t e 置= 硝i la n d t = 岛 2 ，i f 屯 0i sap o s i t i v ep a r a m e t e r 6 i fk 1 哟2 t 忑萨m 厶j t ll “，# i 由引理2 2 4 ，推出结论成立 口 注2 2 3 ：显然，a ( 1 ) 仍是弱对角占优矩阵，因此我们可以继续此过程直到 l = 1 ，即 a l g o r i t h ma t ： f o ra 西v e nc o m p l e x m a t r i x a = ( 口莳) ，n 杆0 ，a n d 岛1 f o ra l l i ： 1 i f 1 = 1 ，t h e np r i n t ai smh - m a t r i x ：s t o p o t h e r w i s e 2 f o rs o m ei 1a n d j 2 ，i f 0 ，t h e n 1 3 电子科技大学博士学位论文 1 = 1 m ，n 2 = 1 ，o t h e r w i s e f o ra n yi 1a n dj n 2 ，i f = 0 ，t h e np r i n t ai sn o ta n 日一m a