（计算数学专业论文）关于sdd矩阵和h矩阵算法的研究.pdf

摘要 摘要 本文涉及两类重要的特殊矩阵，对称对角占优矩阵( 船i d + 矩阵) 和广义对角 占优矩阵( 日一矩阵) 由于矩阵自身具有的稀疏性等特征，在计算机中具有不同的 存储运算方式因此，应在算法上体现其差异以提高运算速度本文主要对寻找最 佳逼近s d 矩阵算法及日一矩阵快速判别算法进行改进 本文分两部分： 1 给定任意实方阵，如何计算与其最佳逼近的对角元为正的对称对角占优 矩阵在计算机图形学上具有重要的应用价值为解决该问题，近年来提出了p r i m a l 算法，p o l a r 算法及选择投影算法与p r i m a l 算法相比，选择投影算法提高了运算速 度，但对非稀疏矩阵结果误差率接近4 0 本文采用多次刷新选择集的方法对选择 投影算法进行了改进，并通过m a t l a b 编程进行了算法优劣性结果显示，改进后的 算法在保证运算速度的同时提高了运算精度 2 m a s u n o r ih a r a d a 、k o j i r o 等通过构造一个右因子正对角矩阵d ，给出了 判断严格广义对角占优矩阵的迭代算法本文对算法进行改进，并给出了奇异日一 矩阵的判别算法数值实例表明，当矩阵为稀疏矩阵时改进后的算法提高了运算速 度， 关键词：对称对角占优矩阵，选择迭代投影，( 非奇异) 日一矩阵，不可约矩阵，可约 矩阵 电子科技大学硕士学位论文 a b s t r a c t 1 1 l i sp a p e ri sc o n c e m e dw i t l lt 、v oc l a s s e so fi 芏1 1 p o r t a l l tm 衄c e s ：s y m m e t r i c d i a g o n a l l yd o m 血趾tm a 伍x ( 观) d + m a 伍x ) a n dg e n e 脚i z e dd i a g o n a l l yd o m i n a m m 删x ( 日一m 砌x ) b e c a u s eo f t l l ec h a r a c t e r so f i t s e l s u c ha ss p a r s i 饥t h em a _ c r i xw i l l b es t o r e da i l dc o m p u t c dmd i 仃e r e n tw a y s s oa l g o 枷1 1 1 1 sd e s i g n e ds h o l l l d b ed i 舵r e n t t h i sp a p e ri sd e v o t e dt oi m p r o v et h ea 1 9 0 r i 也m so ff i n d i n gt h en e a r e s ts y 删n g 砸c d i a g o n a l l yd o m i i l 趾tm 嘶x f o rag i v e nm a 位a n dj u 她i n gw h e a t l l e rag i v e i lm a t i r i xi s a i lh m 州xo r n o t t h i sp a p e rm a 抽l yi n c l u d e st w o p a r t s ： 1 m i 芏1 i m i z i n gt 1 1 ed i s t a n c ef 如mag i v e nm 删xt ot h es e to fs 脚e t r i ca n d d i a g o n a l l yd o m i a n tm a t r i c e si sv a l u e f i l l i nc o n l p u t e rg r a p h i c s ，t bs o l v et h i sp r o b l e m ， r e c e n t i yp r o p o s e di 啊m a la l g o r i t h l n ， p o l 盯 a l g o r i t l l i na n ds e l e c t i v ea l t e m a t i n g p r o j e c t i o n s c o r n p a r c d 谢t hp r i i n a la l g o d 也m ，s c l e c t i v ea l t e m a t i n gp r o j e c t i o n sp r o d u c e s as i g i n i f i c a l l tr e d u c t i o ni nc p ut i m e ，h 0 w l e 畔i s i o ni sr e d u c e d ，t o o h l “s p a p e r ，w er e m r b i s hm es e to fi n d e xt oi m p r 0 v et h ea l g o r i ，也ea d v a m a g e sa i l d d i s a d v 枷a g e so ft l l o s ea l g o r i 血m sa r ec o m p a r e dt h r o u g hm a t l a bp r o g r 锄s ，t h er e s u n 协d i c a t e s 协a t 也ei m p r o v e da l g o r i t a d v a n c e dt l l ep r e c i s i o n 2 w ee x t e n da n di m p f o v eo n ea l g o r i t h mt os 0 1 v e 也ep r o b i e mo fd e b 跚i n i n g w h e t l l e ram a t r i xi sg e n e r a l i z e dd i a g o n a l l yd o m i n a l l to rn o t a e wa l g o r i t h mi s p r o p o s e d r h i c h i ss u i t e df o rr e d u c i b l em 捌c e s ， n 啪e r i c a le v i d e n c ef o r 也c e 丘b c t i v e n e s so fm ep r o p o s e da l g 础t h mi sp r e s e n t e d ，w h i l en l em a t r i xi s s p a r e ，t h e i m p r o v e da l g r i t 8 d v 锄c e dc o m p 删0 n a lt i m e 1 ( e yw o r d s ：s y m m e t r i cd i a g o n a l l yd o i i l i n a n tm 删x ，s e l e c t i v ea l t c m a t i n gp r o j e c t i o n s ， ( n o n _ s i n g u l 神日一m a t r i x ，i n d u c i b l em a t r i x ，r e d u c i b l em a 砸x i i 电子科技大学硕士学位论文 符号说明 c m ” 阶复矩阵的全体 r n ” 以阶实矩阵的全体 譬d o 对称对角占优矩阵 s ：d d + 主对角元为正的对称对角占优矩阵 埘( 一)矩阵爿的比较矩阵 g 9 d d 广义严格对角占优矩阵 i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：筮垒盔日期：硝年。2 月：斗日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：熬立盔导师签名： 日期：础疹年，2 月2 4 日 第一章引言 1 1 研究背景 第一章引言 随着计算机的出现和发展，科学计算在各门自然科学和技术科学与工程科学 中的应用日益广泛由于矩阵具有描述问题表达简洁，实质刻画深刻等优点，是近 年来数学建模中解决实际问题常用的一种方法，引起了许多数学学者、工程技术人 员和科技人员的青睐，故科学与工程计算中出现的问题多转化为求解各种各样的 偏微分方程或方程组对于这些高阶大型方程组，由于宜接法的存储量和计算量太 大，通常采用迭代法求解，此时迭代格式的收敛性和收敛速度就是一个关键问题 对角占优矩阵、膨一矩阵、广义对角占优矩阵( 日一矩阵) 等，在矩阵理论本 身、计算数学、控制论、数量经济学、统计学等实际应用中具有重要地位，它们在 判别系统的稳定性、计算实矩阵的稳定度、判断矩阵方程的收敛性和估计特征僵 分布等众多领域中起着重要的作用如果方程组的系数矩阵是严格对角占优矩阵 或者严格广义对角占优矩阵时，g a u s s s e i d e l 迭代法、j a c o b i 迭代法、s s o r 迭代 法等都具有良好的收敛性因此，对特殊矩阵快速判别方法等进行研究具有实用价 值 1 2 犯i d + 矩阵 对任意给定矩阵，如何计算与其最佳逼近的对角元为正的对角占优矩阵 ( 龇) d + 矩阵) 是计算机图形学的一个重要课题a l l w r i g h t 等首先通过向正的半正 定锥体投影解决了该问题，但因该算法需要对矩阵特征值和特征向量进行精确估 计，致使运算量很大“。之后，g i l l 等应用改迸后的c h o l e s k y 分解算法得到了该问 题的近似解，该分解不再需要对特征值和特征向量进行估计“。，但大量的数据输入 破坏了初始矩阵的稀疏性，运算量较大，仅适用于解决中小矩阵问题；1 9 9 8 年，m a r i am e n d o z a ”。等首先将矩阵问题分解为向量问题，并应用k u h n t u c k e r 优化 条件”。判断了向量解的情况，给出了相对应的算法之后应用d y s k t r a 迭代投影算 法”将矩阵对称化，从而得到了解矩阵该算法充分利用了矩阵的稀疏性，保证了 算法的收敛性且降低了运算量，较好地解决了该问题 电子科技大学硕士学位论文 对于任葸九阶买毅方阵彳，如伺计算与其最逼近的具有正对角兀的对称对角占 优矩阵( 印o + ) 问题可以分为两步解决： 1 求解 m i n 膀一彳幢 ( 1 一l 其中z d d + 以上问题可以转化为求解，1 个互不相关的最优问题 幽舡一q 睡x 口 ( 1 - 2 ) 口= 协科：一州k f ) ，q 为矩阵一的第f 行( 卜2 ) 的行个最优问题可并行求 解，从而得到( 卜1 ) 的解矩阵的 个行向量定理1 2 1 给出了问题( 卜2 ) 解的情况 定理1 2 1 3 1 给定口皿一及行标f ，问题( 卜2 ) 的唯一解i 的特征如下： l 。若q o 且i 口1 2 川k ，则i = n 2 若q o 且i q o( 2 ) i fq 0 ，( ，f ) t h e n - = 口一孑 i f 乃 o 0 u t p u t ：d = d ( 1 ) d ( 2 ) d ”) i f4i sa n 日一m a t r i x s t e p 1 i f ( 4 ) = oo rq ，= o f o rs o m e f ， 爿i sn o ta n 日一m a t r i x ，s t o p ：o t h e 珊i s e s t e p2 s e t 爿( o ) = 4 ，d ( o ) = ，肌= 1 s t e p3 c o m p u t e 爿“= 彳卅1 d 埘- 1 = ( 秽) s t e p4 i f l ( 爿”) = ，一i sa n 日一l a t r i x ，s t o p ：o t h e r w i s e s t e p5 s e td = ( 西) ，w h e r e 吐= i ff i ( 彳”) i f f 2 ( 彳”) s t e p6 s e td ”= d i a g ( d ) ，卅= m + 1 ；g ot os t e p3 在实际应用中我们所遇到的大型矩阵多为稀疏矩阵( 矩阵中的元素大多数为 零元素) ，a h a d j i d i m o s n 8 3 首先提出了在严格广义对角占优矩阵的判别算法中，如 何对稀疏矩阵进行有效存储及运算以减少运算量，提高运算速度 1 4 本文主要工作 对于对角占优矩阵、广义对角占优矩阵的判别仍有许多工作值得去做，尤其是 数值判别方法和算法设计，仍需要进一步地研究和改进在算法设计中，应充分体 现矩阵自身所具有的性质，如稀疏性，以提高运算速度在这个思想基础上，本文进 行了算法改进以提高运算速度或准确度 紫 一l l 电子科技大学硕士学位论文 第二章首先给出了寻找最佳逼近龇) d + 矩阵的选择迭代投影算法，通过对该 算法进行分析，得出改进算法一循环选择迭代投影算法，并用m a t l a b 编程与p r i m a l 算法，选择迭代投影算法比较了算法优劣性试验表明，改进后的算法在保证运算 速度的同时提高了准确率 第三章首先给出了广义对角占优矩阵的定义及k 0 j i r o 关于严格广义对角占 优矩阵的判别算法，本文重点讨论了奇异对角占优矩阵的性质及判别算法，针对稀 疏矩阵进行了算法改进，并通过数值实例进行了算法比较结果表明，改进后的算 法有效地提高了稀疏矩阵的判别速度 6 塑三里量些墨堡翌望! 塑：丝堕簦鲨堕夔鲨 第二章寻找最佳逼近腼d + 矩阵算法的改进 2 1 选择迭代投影算法 定义2 1 1 设一= ( ) c ”，若 m ，m “e ， 则称一为对角占优矩阵矩阵；若每个不等式都是严格成立的，则称一为严格对角占 优矩阵 定义2 1 - 2 设爿一( ) c ”，若 4 u = 口 ，i ，j n 则称爿为对称矩阵 对于任意月阶实数方阵，如何计算与其最逼近的具有正对角元的对称对角 占优矩阵( 犯i d + ) 问题可以转化为以下最优化问题： 黜+ 忪一彳牡 ( z - 1 ) 对此。m e n d o z a 朝给出了投影算法，r a y d a n 在m e n d o z 8 的基础上提出了p r i m a l 算法 和p 0 1 a r 算法，在前者基础上，m o n s a l v e 在算法中加入判定因子，实现对p r i 阳l 算法和p 。i a r 算法的提速【8 记s 为对称矩阵的集合尉任意对称矩阵一 叫= s ： j l s d f = n d 噬 越 因此，问题( 2 - 1 ) 可转化为分别求解矩阵在5 d 讲上的投影，即求解： 牌膀一4 畦 ( 2 ) 记口= ( q ，吒，吒) 为矩阵一的第f 行( 列) ，x = ( 而，x 2 ，矗) 为所求矩阵的第f 行 ( 列) 在求解( 2 2 ) 时，所求矩阵z 第f 行( 列) 外的所有元素与矩阵一的对应 元素相同问题( 2 2 ) 转化为求解 元素相同问题( 2 2 ) 转化为求解 7 皇至型垫查堂堡主兰堡丝苎 r1 r n i n 恨一d l | ：= ( t 叫) 2 + 2 ( o d ：x r ” ， ( 2 3 ) l ，- j 约束条件为岛( 工) = 一一l x j l o j 纠 下面的引理给出了问题( 2 3 ) 解的情况 引理2 1 1 7 1 给出向量口r 一及f ，问题( 3 ) 的唯一解i 的求解可分为以下几 种情况： 1 ) 若q 川m ，则i = 口 2 ) 若o q j 。i 口小则五存在，i 可通过算法2 1 计算 3 ) 若q 2 | 口小则问题( 3 ) 的唯一解为i = ( o ，o ，o ) 4 ) 若q 0t h e n a 锻= n j d e l s e 口埘= 口j + d i f ( q + d 螂 o ，( j f ) t h e n = 盯一d i f 巳 p ( 曰) 时，称一为非奇异m 一阵；当s = p ( 功时， 称爿为奇异m 一阵 定义3 1 2 设一芒c ”，d = d i 删，4 = d c ，称i d 卜蚓为4 的比较矩阵，且 记为m ( 4 ) 若m ( 4 ) 为m 阵，则称4 为日一矩阵，类似地定义非奇异一矩阵和奇 异日一矩阵 定义3 1 3 设爿= ( ) c “”，若存在一个正对角矩阵d 使彳d 为对角占优矩 阵。则称爿为广义对角占优矩阵，记做4 g d d ；若存在一个正对角矩阵_ d 使爿d 为 严格对角占优矩阵，则称爿为广义严格对角占优矩阵，记做4 g d 定义3 。1 。4 彳= 魄) 仨c ”，当即2 时，若有力阶置换矩阵p 使 ：导 删，：降4 ：l l o 4 2 j 其中4 ，为r 阶子方阵，4 ：为聍一，阶子方阵，l sr 疗，则称彳为可约矩阵，若一不可 约，则称爿为不可约矩阵 定理3 1 1 n 9 1 爿为广义对角占优矩阵等价于彳为日一矩阵 近年来，很多著作中提出算法以判别一个矩阵是否为严格对角占优矩阵李磊 等1 1 6 t ”3 通过构造一个右因子正对角矩阵d ，给出了判断严格广义对角占优矩阵的 迭代算法k o j i r o n 们对算法进行了改进并证明了其收敛性，运算量由0 ( ”z ) 降为 o ( n ) 不失一般性，本文仅针对对角元素为l 的矩阵a 进行讨论 k o j i r o 针对不可约何矩阵提出了如下判剐算法， 设不可约矩阵彳= ( 嘞) c “”，记= 1 ，2 ，刀 ，q 为矩阵彳的第f 行行向量 1 ( 4 ) = 钏l ，k l ，f ，2 ( 一) = 一i = 川川他。l 1 4 第三章胃一矩阵快速判别算法的改进 若对所有f ，均有1 则一为对角占优矩阵 算法3 1 1 1 4 1 i n p u t ：爿m a t r i x 爿= ( ) c ” s t e p l ：i f j ( ) = g o rq f = of o rs o m ef ，爿i sn o ta nhm a t r i x s t o p ： o t h e r w i s e s t e p2 ：i f = of o r8 1 lf ， 4i sa nh m a t r i x ，s t o p ：o t h e 押i s e s t e p3 ：s e t = m m l ，自f o r o s t e p4 ：c o m p u t e 叫= q s t e p5 ：s e t 爿= ( q 吼q l 珥研+ l ) s t e p6 ：n o 珈a l i z e 胁r o wo f 爿b y s t e p7 ：c o m p u t e ，j s t e p8 ：i ff 1f o ra l lfa n da t1 e a s to n efi ss t r i c t ， 彳i sa n 日m a t r i x ， s t op ， i ff lf o ra 1 1f ，爿i sn o ta n h m a t r i x ， s t o p ： o t h e r w i s e s t e p9 ：s e t 彳= 4 ：g ot os t e p3 定理3 1 2 1 们爿为不可约矩阵且1 ( ) 中若一为何一矩阵，则经过有限步 运算后，算法3 1 能够得到一个对角占优矩阵 3 2 算法改进 算法3 1 1 所判定对象为不可约矩阵，本文考虑了可约矩阵对角占优( 奇异日一 矩阵) 的条件及性质，并且将算法进行扩展 注记1 在算法3 1 的输入矩阵4 为不可约矩阵，因此在s t e p3 要求t o 以保证矩阵的不可约性事实上如果存在f 使得r ，= o ，可设f ，= 占，其中占 为一个小正数在这种情况下保持了矩阵的奇异性，且对稀疏矩阵可以减少运算 量 注记2 在s t e p4 计算叫= 棚，致使巧= 1 ，破坏了z 行的对角占优性因此设 = m i n + s 引理3 2 1 。矩阵p 为任意置换阵，则4 当且仅当p 7 彳p 1 5 皇至型垫盔竺堡主堂垡笙苎一 引理3 2 2 若矩阵4 = ( ) c ”可按如下格式进行分块 肛隐射4 l e 矿印n 其中矩阵4 ：和4 ，至少有一个为零矩阵，则4 蚴当且仅当4 t 删且 如g s d d 引理3 z 3 记一= ( 嘞) c ”h = 置：乏 ，4 。c ”“( m 一) 不可约 i = 1 ，f m = 1 ，2 ，脚) ( 朋 1 ，f 一m = 小+ 1 ，刀 若存在正对角矩阵d = 旃昭 ，如，) 使得4 d 对角占优，则对所有j m ，吐均 相等，记为d 且d 1 ，可得 j i k k = k i 碡+ i j z 因此 k 。 + k 。 j i 以 由以上证明可知存在墨m 使得呔 以。 s t e p2 对，m ，若4 并非全部相等，则 d p d q ，dp s d | t j m ，i 西，d p ds s d i j n m ) 考虑矩阵b = a d 的第p 行， h i 砟2 。舌舯，k k + k 砟+ 。羔k k 。 z b k + b i + 1 k ” e m i p i g t 一m 第三章h 一矩阵快速判别算法的改进 从不等式( 2 ) 可得对任意i e m ，= 0 = o 因为矩阵4 不可约，= o ，存 在正整数七l ，如。，七r ，1 t ，屯，蔓m 使得气b ，o 由不等式( 2 ) 可知 4o ，叱= 砟分析矩阵口= 爿d 的第南。屯，i 一，行，可以得到 噍= 民，叱= 噍，矗= 矗。因此 吨；噍= = 噍= 以 分析矩阵丑= 一d 的第一行，可以得到，o ，矗= 砖因此 d p ；d q ， 这与d ， 吒矛盾因此对f m ，面均相等， d p = d q d 。 定理3 2 4 矩阵彳如引理2 所定义，则4 g d d 当且仅当4 满足以下两个 条件： 1 ) 矩阵一可进行以下分块：肚隐甜舡w m 叭 2 ) 以2 g d d p r o o f 等：若对角矩阵d 存在，从引理3 的证明知对任意i 一m 有口。= o 由于对f m ，有砖= c o 船t 趾t ，显然对f m ，e 一肘有嘞= o ，因此 4 2 = 0 4 ：g d d 可以显然得到 仁：由引理1 知显然成立 注记3 彳= ( 嘞) e c ”，若对所有f e 均有1 且存在七，= l ，则存在置 换矩阵p 使得j = 尸7 彳p 满足引理3 2 3 的定义若j 满足定理3 2 4 的两个条件， 则j 为h 一矩阵，正对角矩阵d 存在由引理3 2 1 知一亦为日矩阵，其所对应的对 角矩阵d = 尸却7 为了计算西，可设吐( f m ) = 占，则d ，( j 一m ) 可通过算法 3 2 计算得出 记m ( 彳) = f l = o ，f ， 如( 一) = 一 毛( 一) 算法3 2 ： i n p u t ：一ma _ 缸x 一= ( ) c 札” 占as m 矗hp o s i t i v en u m b e r s t e pl ：i f l ( 爿) = ao r = 0f o rs o m ef ，一i sn o ta i lh - m a 仃i x ，s t o p ： o t h e n v i s e s t e p2 ：i f 如( 一) = a ，月i s 趾h m a t r i x ，s t o p ： o t h e h v i s e ：f o rf m 似) ，s e t = 占，t h t4 = ( q 吒口一1s q 十1 一) 一 皇王型垫盔兰堡主鲎竺丝奎 _ _ _ _ _ _ w 一 s i e p 3 ：l b rf g m 名( 0 ) ，c o n l p u t e ，s e t = m l n + 占 s t e p4 ：c o m p u t e 叫= 珥 s t e p5 ：s e t4 = ( 口i 吃q i 口；口f “) 触p6 ：n o 咖l i z ef m r o w o f b y 叫， s t e p7 ：c o m p 砒c 啪f s t 印8 ：l ff ： lf o ra l lf ，彳i s n o ta i l h - m a 订i x ，s t o p ： i ff ：lf o ra l l 锄da t l e 懿t o n e i s e q l l a l ，t 咖s t e p9 o m e r i s et 唧s t e p1 0 s t e p 9 ：i fa s a t i s f i e st h ef o 彻o fm a 函xd e f i n c di nt h e o r e m1 ，s e t 爿= 如， 一= 聊，t t l ms t e p1 o t h e r w i s e ，f m d t h ep e 珊u t a d o nm 砌xqt l l a tm a k e s 爿= q 1 爿qb e 撕m a a s 乳臣互：j 玎乱互：uh 洲川一 h m 撕x ，。0 t h e 刑i s e ，彳i sn o ta nh m 砌x s t e p l o s e t4 = 一，t m _ i l t e p 3 t h e o r e m3 2 5 一为n 厅维复合矩阵且l o ) o 若为何矩阵，则算法b 经过有限步运算后，可得到相应的对角占优矩阵 p r o o f 程序运行七次后，彳和分别由一( 扣1 和代换，在s t e p7 ，。 l ，于 是有 伊= 必铲 1 8 够一 十一ii n i 矿一够“ 犯 = 第三章一矩阵快速判别算法的改进 群) = 1 ，f _ ， 对f ，随着七的增加，非对角元素减小，在s t e p6 有以下不等式成立 悱舒 伊引 多次代换后对f 2 ( 一) 有扩1 ；对f 1 ( 爿) ，有0 。1 趋近于1 因此，若彳为日矩阵，经过有限次运算后有 0 s 1 ，f 即算法终止 3 3 数值实例及算法比较 算法3 1 应用于不可约矩阵，本文所给定理在验证某些可约矩阵是否为奇异h 矩阵时具有实际应用价值。通过以下具体实例进行算法比较 实例1 ： = 1o 20 8 0 41o 6 o 5o 5 l o1l 1ol 0o o0 00 12 0 2l 由计算得出，l = r 2 = ，3 = l ，4 = 4 ，= 2 2 由于矩阵4 为可约矩阵，不能应用算法3 1 进行判断 观察知矩阵爿满足引理3 2 3 的定义，设碣= 吐= 岛= 占，通过计算知 吃= o 2 + 3 岛破= 1 ，此时l ，f ，因此4 g d d ，即爿为奇异日矩阵 实例2 ： = l20 o3 2o oo1 2 ooo o一1o ol oo o0 1o 一11 2 算法3 2 ： 第一步：由计算知，乞= f 3 = = o ，因此m ( a ) = 2 ，3 ，4 ) ，鸩( 一) = 1 ，5 故设 吨= 以= 以= s ，计算4 = 1 + 2 占，比= 4 占 1 9 电子科技大学硕士学位论文 第二步：取= r 5 = 4 占，则1 ，f | v 因此爿为何矩阵 算法3 1 ： 计算得屯= f 3 = = o ， = 3 ，毛= 4 ，由于该算法要求o ，而，岛均大于1 ，不能对 该情况进行判断 算法“应用参考文献中的算法不能得出判断结果 由以上例子可以看出，改进后的算法有效地减少了对稀疏矩阵进行判别所需 的运算量 第四章结论 第四章结论 对角占优矩阵、m 一矩阵、广义对角占优矩阵( 日一矩阵) 等，在矩阵理论本 身、计算数学、控制论、数量经济学、统计学等实际应用中具有重要地位，它们在 判别系统的稳定性、计算实矩阵的稳定度、判断矩阵方程的收敛性和估计特征值 分布等众多领域中起着重要的作用关于特殊矩阵判定和应用的理论结果日益完 善，但在如何实现快速判别的算法方向仍待优化由于矩阵自身具有的稀疏性等特 征，在计算机的存储运算中不能一概而论因此，应在算法上体现其差异以提高运 算速度本文主要对寻找最佳逼近) d + 矩阵算法及日一矩阵快速判别算法进行改 进 本文主要分两部分： 1 给定任意实方阵，如何计算与其最佳逼近的对角元为正的对称对角占优 矩阵，为解决该问题，近年来提出了p r i m a l 算法，p o l a r 算法及选择投影算法等 选择投影算法提高了运算速度，但对非稀疏矩阵，结果误差率接近4 0 本文对选 择投影算法进行了改进，并用m a t l a b 编程比较了算法优劣性 2 l a s u n o r ih a r a d a 、k o j i r o 等通过构造一个右因子正对角矩阵d ，给出了 判断严格广义对角占优矩阵的迭代算法本文对算法进行改进。并给出了奇异一 矩阵的判别算法实例表明，当矩阵为稀疏矩阵时改进后的算法提高了运算速度 鉴于对角占优矩阵、m 一矩阵、一矩阵在理论和实际应用中所具有的重要 作用，讨论它们的判定及性质有着十分重要的意义对各类特殊矩阵的判定，尤其 是数值判定方法和算法设计是矩阵计算的重要课题本文只是做了其中一部分工 作，还有许多工作值得进一步的探讨和研究 2 1 电子科技大学硕士学位论文 致谢 首先，我要衷心感谢我的导师黄廷祝教授三年来对我的辛勤培养! 他是我人生 路上的指明灯和领路人，是他带领我走进了学术研究的殿堂 本文从选题到完成都是在导师黄廷祝教授的悉心指导下进行的在学习过程 中，他给我指出了前进的方向并传授给我科学的方法黄老师还给我提供了大量的 文献资料，我撰写的每一篇论文都得到黄老师认真研读和修改我所取得的每一点 小小的成绩和进步都凝聚了他无数的心血和汗水! 他渊博的学识、开阔的视野，活 跃的思维以及严谨的治学风范都深深的感染着我，使我终生学之不尽，受益无穷! 我还要诚挚地感谢应用数学学院的许多老师热情的、无私的帮助，还有许多同 学也给了我支持、帮助和鼓舞，在此一并表示感谢! 叁耋茎墼 参考文献 1 j c a 1 l _ r i g h t p o s i t i v es e m i d e f i n i t e h u l l s8 n d1 e a s t s q u a r e ss o l u t i o no f o d t i m i z a t i o n ，1 9 8 8 ，2 6 ：5 3 7 5 5 5 m a t r i c e s ：c h a r a c t e r i z a t i o nv i a c o n i c a l am a t r i xe q u a t i o n s i a mj c o n t r 0 18 玎d 2 s h c h e n g ，n j h i g h a m am o d 订i e dc h 0 1 e s k ya 1 9 0 r i t h mb a s e do n as y m m e t r i c i n d e f i n i t ef a c t o r i z a t i o n t e c h n i c a lr e p o r tn o 2 8 9 ，m a n c h e s t e rc e n t r ef o r c o m p u t a t i o n a lm a t h 伽a t i c s ，m a n c h e s t e r ，e n 9 1 a n d ，1 9 9 6 s i a ij m a t r i x a n a l a p p l ，1 9 9 8 ，1 9 ：1 0 9 7 一l l l 0 3 m m e n d o z a ，m r a y d a n ，p t a r a z a g a c o m p u t i n gt h en e a r e s td i a g o n a l l yd o m i n 衄t m a t r i x j n u m e r l i n e a ra l g e b r aa p p l ，1 9 9 8 ，5 ：4 6 1 4 7 4 4 m a v r i e l _ n o n l i n e a rp r o g r 姗m i n g ： a n 且1 y s is a n d啊e t h o d s n e w j e r s e y ： p r e n t i c e h a l l 1 9 7 6 9 5 9 6 5 j p b o y l e ，r l d y k s t r a am e t h o df o rf i n d i n gp r o j e c t i o n so n t ot h ei n t e r s e e t i o n o fc o n v e xs e t si nh i l b e r ts p a c e s j l e c t u r en o t e si ns t a t i s t i c s ，1 9 8 6 。3 7 ：2 8 4 7 6 f d e u t s c h ， h h u n d a l t h er a t eo fc o n v e r g e n c eo fd y k s t r a sc y c l i cp r o j e c t i o n s a l g o r i t h m ：t h ep o l y h e d r a lc a s e m b e r f u n c t a n a l o p t i m i z ，1 9 9 4 ，1 5 ：5 3 7 5 6 5 7 m r a y d a n ，p t a r a z a g a p r i m a la n dp o l a ra p p r o a c hf o rc o m p u t i n gt h es y m m e t r i c d i a g o n a l l yd o m i n a n tp r o j e c t i o n j m e r l i n e a ra 1 9 e b r aa p p l ，2 0 0 2 ，9 ：3 3 3 3 4 5 8 m m o n s a l v e ，j m o r e n o ，r e s c a l 8 n t e ， e ta 1 s e l e c t i v ea l t e r n a t i n gp r o j e c t i o n st o f i n dt h en e 8 r e s t 渤+ 加a t r i x 【j a p p l i e dm a t h e m a t i c sa n dc o m p u t a t i o n ，2 0 0 3 ，1 4 5 ： 2 0 5 2 2 0 9 逢明贤矩阵谱论长春：吉林大学出版社，1 9 8 9