（计算数学专业论文）loewner型矩阵类相关问题快速算法的研究.pdf

暇北t 业k 牛，峨 1 学位论文 l o e w n e r 型矩阵类相关问题快速算法的研究 摘要 随着计算机科学的迅速发展，国防科技和国民经济建设的许多领域不断提出 许多大型和超大型的计算问题对于此类问题，其相应的矩阵往往具有一些特殊的 结构，因此，利用这些矩阵的特殊结构进行技巧性的处理，使矩阵的计算量降低一 个数量级，这一问题的研究具有重要的理论意义和现实意义 在工程计算问题中，有类重要的问题就是线性方程组的求解问题，但有些线 性方程组是不相容的本文研究以l o e w n e r 型矩阵和对称l o e w n e r 型矩阵为系数 矩阵的不相容线性方程组的极小范数最小二乘解的快速算法对于m n 阶矩阵 a ，求以a 为系数阵的线性方程组a x = b 的最小二乘解的一般方法是构造法方 程组a 7 a x = a 1 b ，进而求解法方程组来实现的特别地，当a 的秩为n 时，a x = b 的惟一极小范数最小二乘解为= a ) - a b 但利用通常的方法求 法方程组时，所需的运算量为o ( m n 2 ) + o ( 月3 ) ，且若矩阵a 本身病态时，构造法方 程组后会更加病态求方程组a x = b 的最, b - - 乘解也常采用正交化法，这一方法 虽然避免了构造法方程组，但所需的运算量会更大些本文对于秩为”的m 门阶 l o e w n e r 型或对称l o e w n e r 型矩阵上，通过构造特殊分块矩阵并研究其逆的三角 分解或自身三角分解，进而得到了线性方程组l x = b 的极小范数最小二乘解快速 算法，计算复杂度为o ( m n ) + o ( n 2 ) ，而一般方法的计算复杂度为o ( m n2 ) + 0 03 ) 在工程计算问题中，由于矩阵的广义逆理论与计算在最优化理论、控制理论、 计算数学、数理统计等领域中有着广泛的应用，也使得对于矩阵广义逆问题的研 究显得尤为必要本文对于秩为咒的mx 心阶l o e w n e r 型矩阵或对称l o e w n e r 型矩 阵，通过构造特殊分块矩阵并研究其逆矩阵，进而得到它们的m o o r e p e n r o s e 逆及 其快速算法，所需运算量为o b 月) + d g 2 ) ，而利用常规方法上= 陋l ) - 1 r 求解时 所需的运算量为o ( m n2 ) + d k 3 ) 本文的结构安排如下： 第一章主要以引言的形式概括了两类方程组和广义逆的历史及研究现状： 西北工业人学硕t _ - 学位论文 第二章给出了所有算法的理论基础： 第三章给出了l o e w n e r 型矩阵为系数矩阵的线性方程组的极小范数最小二 乘解的三种快速算法及数值算例； 第四章给出了对称l o e w n e r 型矩阵为系数矩阵的线性方程组的极小范数最 小二乘解的三种快速算法及数值算例： 第五章给出了l o e w n e r 型矩阵的m o o r e p e n r o s e 逆的快速算法及数值算例； 第六章给出了对称l o e w n e r 型矩阵的m o o r e - p e n r o s e 逆的快速算法及数值算 例： 第七章分别给出了l o e w n e r 型矩阵和对称l o e w n e r 型矩阵的单边求逆公式 关键词l o e w n e r 型矩阵，对称l o e w n e r 型矩阵，极小范数最d , - 乘解，三 角分解，m o o r e p e n r o s e 逆，快速算法 中国图书资料分类号：0 2 4 1 6 a m s ( 2 0 0 0 ) c l a s s i f i c a t i o n ：1 5 a i i “ 北工业大学颐卜学位论文 r e s e a r c h i n go ff a s ta l g o r i t h m so ft h ep r o b l e m c o n n e c t e dw i t ht h ek i n do fio e w n e r - t y p em a t r i x a b s t r a c t w i t ht h es p e e d y d e v e l o p m e n to fc o m p u t e rs c i e n c e ，m a n yl a r g eo rs u b l a r g e c o m p u t a t i o np r o b l e m sa r eb r o u g h tf o r w a r di nf i e l d sa sn a t i o n a ld e f e n c ea n ds c i e n c e a n dt e c h n o l o g ya n dn a t i o n a le c o n o m yd e v e l o p m e n t f o rt h e s ep r o b l e m s ，t h er e l e v a n t m a t r i c e so f t e nh a v es o n l es p e c i a ls t r u c t u r e 。t h e r e f o r e ，w em a yg e to nw i t ht h e s e m a t r i c e st e c h n i q u eb yu s i n gt h e i rs p e c i a ls t r u c t u r e ，a n dt h e nr e d u c eaq u a n t i t a t i v e l e v e lo f t h em u l t i p l i c a t i o n s ，a n dt h er e s e a r c hh a v ed e f i n i t er e a lm e a n i n g t h e r ei sak i n do fi m p o r t a n tp r o b l e mt h a ti ss o l v i n gl i n e a r s y s t e m si nt h e c o m p u t i n gp r o b l e m so fe n g i n e e r i n g ，b u ts o m e t i m e st h e ya r eu n s o l v a b l e i nt h i sp a p e r , f a s ta l g o r i t h m sa r ep r e s e n t e dw h i c hc o m p u t et h em i n i m a ln o r ml e a s ts q u a r es o l u t i o n s f o rl i n e a rs y s t e m ss u c ha st h ec o e f f i c i e n t si s l o e w n e r - t y p em a t r i xo rs y m m e t r i c l o e w n e r - t y p em a t r i x f o rm nm a t r i xa ，t h en o r m a lm e t h o di st h a tf o r ma n o r m a ls y s t e ma a x = a 7 6w h e nw es o l u t et h es y s t e ma x = b a n dt h e ns o l u t ei t s p e c i a l l y , t h em i n i m a ln o r ml e a s ts q u a r es o l u t i o ni s 工。= 1 a ) - 1a 7 bf o ra x = b w h e nt h e1 8 n ki sno fa b u t w h e nw es o l v et h en o r m a ls y s t e mw i t ht h ec o m m o n m e t h o d ，t h em u l t i p l i c a f i o ni so ( m n 2 ) + o g3 ) ，a n di f m a t r i x 爿i sm o r b i di t s e l f , i ti s m o r em o r b i dt h a nb e f o r ea f t e r f o r m i n g n o r m a ls y s t e m w eo f t e nu s et h e o r t h o g o n a l i z a t i o nm e t h o dt o s o l v et h es y s t e ma x = b ，a l t h o u g hw ed o n tn e e d f o r m i n gt h en o r m a ls y s t e m ，t h em u l t i p l i c a t i o ni sm o r et h a no t h e r so fi t i nt h i sp a p e r , f i rm n l o e w n e r - t y p em a t r i xo rs y m m e t r i cl o e w n e r t y p em a t r i xw i t hf u l lc o l u m n r a n k ，w ef o r ms p e c i a lb l o c km a t r i xf i r s t l ya n dr e s e a r c ht h e i rt r i a n g u l a rf a c t o r i z a t i o no r o fi t si n v e r s e a n dt h e ng e tt h ef a s ta l g o r i t h mo ft h em i n i m a ln o r ml e a s ts q u a r e s o l u t i o n i t sc o m p u t a t i o nc o m p l e x i t yi s o ( r n n ) + o ( n 2 ) ，b u tt h a to fu s u a la l g o r i t h m s o ( m n 2 ) + d 03 ) i l i 两托t 业犬学砸l j 学位论文 t h er e s e a r c hf o rt h ep r o b l e mo fg e n e r a l i z e di n v e r s eo fm a t r i xi sv e r yi m p o r t a n t d u et ot h eb r o a da p p l i c a t i o no ft h et h e o r ya n dc o m p u t a t i o no fm a t r i xi nm a n yf i e l d s s u c ha so p t i m i z et h e o r y ，c o n t r o lt h e o r y , c o m p u t a t i o n a lm a t h e m a t i c s ，m a t h e m a t i c a l s t a t i s t i c s ，e t c i nc o m p u t i n gp r o b l e m so fe n g i n e e r i n g i nt h i sp a p e r , f o rm n l o e w n e r - t y p em a t r i xo rs y m m e t r i cl o e w n e r - t y p em a t r i xw i t hf u l lc o l u m nr a n k ，w e f o r ms p e c i a lb l o c km a t r i xf i r s t l ya n dr e s e a r c ht h e i ri n v e r s e ，a n dt h e ng e tt h ef a s t a l g o r i t h m o ft h em o o r e p e n r o s ei n v e r s e i t s c o m p u t a t i o nc o m p l e x i t y i s o ( m n ) + o ( n 2 ) ，b u t t h a t o f u s i n gr = ) - ti so ( m n 2 ) + d 如3 ) + t h ep a p e ri sb u i l ta sf o l l o w s i nc h a p t e r1 ，s t u d y i n gh i s t o r ya n da c t u a l i t yo ft h et w ok i n d sl i n e a rs y s t e ma r e g i v e ni ni n t r o d u c t i o n ， i nc h a p t e r2 ，t h eb a s i ct h e o r yo f t h ea l g o r i t h mi sp r e s e n t e d i nc h a p t e r3 ，t h r e ef a s t a l g o r i t h m so fm i n i m a ln o r ml e a s ts q u a r es o l u t i o nf o r s y s t e mw h o s ec o e f f i c i e n ti sl o e w n e r t y p em a t r i xa n dt h e i rn u m e r i c a le x a m p l e sa r e g i v e n i nc h a p t e r4 ，t h r e ef a s ta l g o r i t h m so fm i n i m a ln o r ml e a s ts q u a r es o l u t i o nf o r s y s t e mw h o s ec o e f f i c i e n ti ss y m m e t r i cl o e w n e r - t y p em a t r i xa n dt h e i rn u m e r i c a l e x a m p l e sa r eg i v e n i nc h a p t e r5 ，f a s ta l g o r i t h mo fm o o r e p e r t r o s ei n v e r s ef o rl o e w n e r t y p em a t r i x a n di t sn u m e r i c a le x a m p l e sa r eg i v e n ， i n c h a p t e r6 ，f a s ta l g o r i t h m o fm o o r e p e n r o s ei n v e r s ef o r s y m m e t r i c l o e w n e r - t y p em a t r i xa n di t sn u m e r i c a le x a m p l e sa r eg i v e n i nc h a p t e r7 ，au n i l a t e r a li n v e r s ef o r m u l ao fl o e w n e r - t y p em a t r i xa n ds y m m e t r i c l o e w n e r t y p em a t r i xa r eg i v e n k e yw o r d s ：l o e w n e r - t y p em a t r i x ，s y m m e t r i cl o e w n e r - t y p em a t r i x ，m i n i m a l n o r ml e a s ts q u a r es o l u t i o n ，t r i a n g u l a rf a c t o r i z a t i o n ，m o o r e p e r t r o s ei n v e r s e ，f a s t a l g o r i t h m 两j t - 1 2 业大学坝l 学位论文 第一章引言 1 1 研究特殊矩阵计算的意义 计算机科学的迅速发展，使得科学计算作为科学研究的有效手段，上升为与 科学理论和科学实验相并重的三大科学方法之一近几十年来，科学技术突飞 猛进的发展，国防科技和国民经济建设的许多领域不断提出许多大型和超大型 的计算问题这些问题要求计算机系统有更高的速度和更大的信息存储量，从 而促使计算机体系结构向巨型化和并行化方向发展然而巨型机和并行机的发 展受限于一个国家的综合国力，作为一个发展中的国家，我国的计算机发展水 平与先进国家比较还有相当的差距，我们不能依赖于别人的技术因此，如何利 用现有的计算机处理尽可能大型的问题是一个严峻而又实际的课题由于科学 技术和工程应用中要遇到大量的矩阵计算问题，而相应的矩阵往往具有一些特 殊的结构，因此利用这些矩阵的特殊结构和技巧性处理，使矩阵的计算量降低 一个数量级，这一阀题的研究具有重要的理论意义和现实意义 对于特殊矩阵的研究，一直是国内外所关注的热点在国际著名的杂志， 如美国的 l i n e a ra l g e b r aa n di t sa p p l i c a t i o n s 、s i a mm a t r i xa n a l y s i sa n di t s a p p l i c a t i o n s ) ) 、 m a t h e m a t i c c o m p u t a t i o n ) ) 和德国的 n u m e r , m a t h 等；国内 的计算数学、数值计算与计算机应用、高等学校计算数学学报等期刊上， 有关的研究论文大量出现特别是t o e p l i t z 矩阵、v a n d e r m o n d e 矩阵、l o e w n e r 矩阵、h a n k e l 矩阵、非负矩阵、对角占优矩阵、正定矩阵以及正稳定矩阵等等， 更是近年来研究的热点这些特殊矩阵在数值分析、优化理论、自动控制、数字 信号处理、系统辨识、工程计算等领域中有重要的应用为了提高矩阵计算的效 率，研究如何利用矩阵本身的结构特征，得出计算特殊矩阵的快速算法，具有 重要意义 在工程计算问题中，有一类重要的问题就是线性方程组的求解问题，但有些 方程组是不相容的本文研究以l o e w n e r 型矩阵和对称l o e w n e r 型矩阵为系数矩 阵的不相容线性方程组的极小范数最小二乘解的快速算法对于m 盯阶矩阵爿， 求解以一为系数阵的线性方程组a x = 6 的最小二乘解的一般方法是构造法方程 组a 7 a x = a 7 6 ，进而求解法方程组来实现的特别地，当4 的秩为h 时，a x = 6 的 两北t 业大学倾卜学位论文 惟一极小范数最小二乘解为= ( 4 爿) _ 1 a 7 b 但利用通常的方法求法方程组| j ， 所需的运算量为d ( 聊n 2 ) + d 3 ) ，且若矩阵a 本身病态时，构造法方程组后会更加 病态求方程组a x = 6 的最小二乘解也常采用正交化法，这一方法虽然避免了构 造法方程组，但所需的运算量会更大些本文对于秩为n 的m 竹阶l o e w n e r 型或 对称l o e w n c r 型矩阵工。通过构造特殊分块矩阵并研究其逆的三角分解或自身三 角分解，进而得到了线性方程组l x = 6 的极小范数最小二乘解快速算法，计算复 杂度为d 如珂) + o ( 胛2 ) ，而一般方法的计算复杂度为d b ”2 ) + 0 03 ) 在工程计算问题中，由于矩阵的广义逆理论与计算在最优化理沧、控制理论、 计算数学、数理统计等领域中有着广泛的应用，也使得对于矩阵广义逆的问题研 究显得尤为必要本文对于秩为n 的m n 阶l o e w n e r 型矩阵或对称l o e w n e r 型矩 阵，通过构造特殊分块矩阵并研究其逆矩阵，进而德到它们的m o o r e p e r t r o s e 逆及 其快速算法，所需运算量为。如n ) + 0 0 2 ) ，而利用常规方法r = 上，1 r 求解时 所需的运算量为o ( m n 2 ) + o k 3 ) 1 2 有关两类矩阵线性方程组和广义逆的历史及研究现状 l o e w n e r 矩阵是由k l o e w n e r 于1 9 3 4 年首先研究的，他通过单调矩阵函数 的特征及有理插值问题研究了各种l o e w n e r 矩阵之间的关系这些问题后来又被 b e l e v i t c h ，d o n o g h u e ，f i e d l e r “。1 ”等做过更深的研究。其中f i e d l e r 给出了h a n k e l 矩 阵和l o e w n e r 矩阵之间的紧密联系从这些可以看到l o e w n e r 矩阵的各种性质及 其在有理插值中的应用 1 9 8 4 年，z v a v r in “1 给出了l o e w n e r 矩阵求逆的快速算法，由此可得解 l o e w n e r 方程组的快速算法 1 9 9 5 1 9 9 6 年，k r o s t 和z v a v r i n “7 3 给出了求l o e w n e r v a n d e r m o n d e 矩阵为 系数阵的方程组的快速算法。 2 0 0 4 年安晓虹”1 在她的硕士论文中研究了l o e w n e r 矩阵为系数矩阵的线性 方程组的极小范数最小二乘解的一种快速算法； 但未见求以m 慰阶l o e w n e r 型矩阵为系数阵的线性方程组极小范数最小二 乘解快速算法的研究结果。 关于对称l o e w n e r 型矩阵的研究结果较少2 0 0 3 年陆全”给出了对称 l o e w n e r 型矩阵三角分解的快速算法同年，徐猛等人“给出了对称l o e w n e r 型矩 阵的逆矩阵的快速三角分解算法 关于对称l o e w n e r 型及对称l o e w n e r 型矩阵为系数矩阵的线性方程组极小范 数最小二乘解快速算法的研究结果未见 早在1 9 2 0 年e h m o o r e 就通过两个算子方程的解给出了广义逆矩阵的概念 但在其后的3 0 年中，他的理论几乎未被注意直到1 9 5 5 年r ，p e n r o s e 以更明确的形 式给出了m o o r e 的广义逆定义之后，广义逆矩阵的研究才进入了一个新的时期由 于广义逆矩阵在数理统计、系统理论、优化计算和控制论等诸多领域中的重要应 用逐渐为人们所认识，因而大大推动了广义逆矩阵的理论与应用的研究，使得这一 学科得到了迅速的发展，已成为矩阵论的一个重要的分支 但关于l o e w n e r 型矩阵及对称l o e w n e r 型矩阵的m o o r e p e n r o s e 逆的快速算 法的研究结果末见 1 3 本文的研究内容及安排 综上可见，对于求解以特殊矩阵为系数矩阵的线性方程组的快速算法的研究 目前主要是针对方阵进行的，面对应用广泛的拢刀阶长方矩阵线性方程组的求 解的研究结果很少甚至没有 对于两类矩阵的广义逆的快速算法的研究结果未觅 本文通过构造特殊分块矩阵研究以m n 阶l o e w n e r 型矩阵和对称l o e w n e r 型矩阵为系数矩阵的线性方程组的极小范数最小二乘解的几种快速算法及两类 矩阵的m o o r e p e n r o s e 逆的快速算法 本文在第一章概括了两类方程组的研究历史及现状；第二章给出了一些预备 知识及所有算法的理论基础：第三章给出了l o e w n e r 型矩阵为系数矩阵的线性方 程组的极小范数最小二乘解的三种快速算法及数值算例；第四章给出了对称 l o e w n e r 型矩阵为系数矩阵的线性方程组的极小范数最小二乘解的三种快速算 法及数值算例；第五章给出了l o e w n e r 型矩阵的m o o r e p e n r o s e 逆的快速算法及 数值算例；第六章给出了对称l o e w n e r 型矩阵的m o o r e p e n r o s e 逆的快速算法及 西北1 。业人学硕。1 j 学位论文 数值算例：第七章分别给出了l o e w n e r 型矩阵和对称l o e w n e r 型矩阵的单边求逆 公式 西北工业夫学硕 ：学位论文 第二章预备知识及基本结论 2 1 预备知识 给定胛阶方阵4 = k ) ：。，记 4 = k z 。( 七= 1 j 2 ，聍) 为爿的忌阶顺序主子阵 记p j 是第f 个分量为1 ，其余分量为0 的 维单位列向量 设非齐次线性方程组 血= ，i ( 2 1 ) 其中a c ，f c “给定，x c ”为待求向量如果存在向量x 使得方程组( 2 1 ) 成 立，则称方程组( 2 1 ) 相容，否则称为不相容或矛盾方程组 关于线性方程组的求解问题，常见的有以下几种情形： ( 1 ) 方程组( 2 1 ) 相容的条件是什么? 相容时求出其通解( 若解不惟一的话) ( 2 ) 当相容方程组( 2 1 ) 有无穷多个解时，求出具有极小范数的解： 。m 。i ，l x l l ， ( 2 2 ) 其中州是欧氏范数可以证明，满足该条件的解是惟一的，称之为极小范数解 ( 3 ) 如果方程组( 2 1 ) 不相容，则不存在通常意义下的解但在许多实际问题中 需要求出极值 孵1 | 血一f l l ( 2 3 ) 称为最小二乘解 ( 4 ) 一般来说，矛盾方程组的最小二乘解是不惟一的，但在最小二乘解的集合 中，具有极小范数的解 叫m i n ，。i i x 0 ( 2 4 ) 是惟一的，称之为极小范数最小二乘解 设4 是m , 的矩阵，若, x m 的矩阵x 满足条件： ( 1 ) a x a ：a ： 西北工业人学颂j 学位论文 ( 2 ) x a x = x ； ( 3 ) ( 从) h = a x ； ( 4 ) f x 4 ) “= 别 则称x 为爿的m o o r e p e n r o s e 逆，电为a + a 的m o o r e p e r t r o s e 逆4 + 惟一 设矩阵a c “，若存在矩阵x 乍c “满足a x = i 。，则称x 为爿的右逆，记 做一r 因为矩阵爿r 满足矩阵m o o r e - p e n r o s e 逆定义的前三个方程，因此又称爿r 为 矩阵爿的n ，2 ，3 卜逆若存在矩阵x c ”满足x a = l ，则称x 为a 的左逆，记 做4 l 因为矩阵4 l 满足矩阵m o o r e p e n r o s e 逆定义的第一，二，四个方程，因此又 称a 。为矩阵爿的f 1 ，2 ，4 一逆 2 2 基本结论 引理1 若月的各阶顺序主子阵4o = 1 ，n ) 均可逆，则 = f 0 t 1 匀+ ( 一1 c “卜 丁t ) g 乩2 ，也 c ：司 其中q 一。= 0 。，吼 。) t ，正，= h “吼川) ，钆= 一c 。爿矗。吼一 以下给出本文所要引用到的基本结论 引理2 给定线性方程组 a x = f ， 其中，= “， ) t ，设 = ( z ， ) 7 ， 又设 以= b 。，) t ，= 0 ，) t 分别是线性方程组 6 西北工业大学硕i 学位论义 a 札= ，4 = p p 的解向量 若a 的各阶顺序主子阵a 。瞎= l ，n ) 均可逆，则 铲心 + o k u k 其中吼：( - 。，1 k ：五一。吒一： 一艺。， ( 2 6 ) 引理3 设即阶对称矩阵一= k l 。的顺序主子阵4 忙= 1 2 一，h ) 均可逆，又设 a k u k = p 的解向量为= 0 。 ，“：一，“。) t ，则 其中 ：一1 u k k 小f 答10 + 心槭 ( 2 8 ) 引理4 设聆阶对称矩阵a 的顺序主子阵4 g = 1 ，2 ，行) 均可逆弓 k n 阶方阵 爿( 0 ) = 凰= 月，4 f ) = ( 吕昙 ( f = t ，z ，n ) ( 2 ， 其中置是n i 阶方阵又记 若取 则有 q = ( 0 ，o ，q ，- 一，“。，) 1 ( j = 1 , 2 ，n ) 一：爿( 一) p j “，吐：l ( f ：1 ，2 ，以) 甜“ a ( “= u f l , u 7 + a o ( f = l 川2 ，珂) 且矩阵a 的一种三角分解为 4 = ( ，2 ，i o ) d i a g ( d 。，d ：，d n 。，) t 7 ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 两北下业大学硕士掌位论鱼 引理5 条件同引理4 又设 a a ( ) = u a ( “一4 ( 0 y 其中u 是下三角矩阵，v 是上三角矩阵贝0 矩阵置( f = 0 , 1 ，珂一1 ) 非奇异，且 r a n k ) r a l l k ) ( f = 1 加，n ) 8 西北工业大学硕士学位论史 第三章l o e w n e r 型方程组的极小范数最, b - - 乘解 定义1 给定四组数口，岛，专，仉( f = 1 “2 一，j = l ，2 ，胛) ，且设q 只 ( f = l “2 ，m ? = 1 | 2 ， ) ，称矩阵 为小盯的l o e w n e r 矩阵 满足关系式 喊l _ ( 鬻l ， 说一l d = p ( 。k 7 f - 1 的矩阵工称为m h 的l o e w n e r 型矩阵，其中 西= d i a g ( a ，) ，d = d i a g ( f l l ，屈，属) p ( 虬扫p ) ，p ”，p 绀，q ( g l = ，q ”一，g ，) t ( 3 1 ) l o e w n e r 矩阵厶是特殊的l o e w n e r 型矩阵，即取z = 2 ，p ( 1 ) = 心，岛，幺) t ，p ( 2 ) = o , 1 ，1 ) t ，口( 1 ) = ( 1 1 一，1 z ，q 2 = 一0 。露：，仉) 坨满足关系式 忱一厶d ；瓴，岛，鼠) 7 ( 1 川1 一，1 ) 。一( 1 ，l ，1 ，。t 0 。，r h ，r ) 3 1 本章基本思想 本章对于秩为珂的m x 珂的l o e w n e r 型矩阵工，通过构造特殊分块矩阵，而后 研究该分块矩阵的逆矩阵的三角分解或其自身的三角分解，进而间接的得到了线 性方程组厶= b 的极小范数最小二乘解及其快速算法，所需运算量为 。妇h ) + 0 0 2 ) 或o b 拧) + o 白2 ) ，而裂用构造法方程组的方法求极小范数最小二 乘解时所需的运算量为o ( m n 2 ) + 0 0 3 ) ，用正交化法虽然避免了构造法方程组，但 所需的运算量更大些在本章最后一节用f o r t r a n 语言在计算机( e r a 8 0 0 m ，内存 1 2 8 m b ) 上编程计算了一些算例，验证了文中算法的有效性 西北工业大学硕上学位论文 3 2l o e w n e r 型方程组极小范数最小二乘解 的快速算法1 设m n 的l o e w n e r 型矩阵工的秩为n 构造m + h 阶矩阵 膨= ( j 甜 z ， 扩1 = 上( f f l ) - il ，t r _ l 饼1 s ， 如果可以求得式( 3 2 ) 的矩阵m 的逆矩阵m 。的三角分解 - ( 古斯l 。胎品 ， 。， 其中u ：为上三角矩阵，d 为对角矩阵，则由( 3 3 ) 和( 3 4 ) 式得 p 三) _ 1 r = u 2 d u i r ， 从而l o e w n e r 型方程组及= 6 的极小范数最小二乘解为 x o = 妒上) _ 三t 6 = u 2 d u i r b ( 3 5 ) 由( 3 1 ) 式知，( 3 2 ) 式的分块矩阵m 满足 ( 西。m 一材( 西。 = 妻 ( ) ( 0 t 。g u 丌) 一( ，) 。“汀。：) c ，s ， 设矩阵m 的顺序主子阵m ( f = 1 , 2 ，聊+ n ) 均可逆则当i m 时，由( 3 6 ) 式 知 ( 西。，。 m 一肘( 西。，。 司i - m f p o ) 、! o r 辨( 巍) 。) ， 1 0 弭北1 = 业大学硕士学位论文 设线性方程组 删= ，删= ( 惫) ，一川”， 的解向量分别为 g ：，) = ) ，g 掣，g ? ) t ， j ，) = ) ，咄， ) t 由m m = 一。，知占2 = 一，( ) ，砖1 = 0 。 又由引理2 ，得 掌p = + 一力一， = l f h i ( j 刁+ r p m ， e ：s ， 其中一”= - 羔i k 卜。g 地，r f 7 1 = 日臻一屯， 地，而= 0 。“：f ) - ，。) 。为 m = p 5 ) 的解向量 ( 3 7 ) 式两端分别左乘和右乘m i l ，得 - f 1 ( 西。 一( 西。，一。 - f l = 嘉( 掌p ，厅p 汀一 p 1 9 p p ) 上式右乘毋，并注意到 西。 母】= 届一。毋) ，得 f l , - m u i - ( 西一口 ：圭) g ”一g p ) p ) 将( 3 8 ) 式代入上式，并注意到g p l = 盯；一) h 。础) = f _ ! 。“。，得 从而 j s i - m l i - - 西 “h = 4 一。 。= “，。骞 f - ! 。 嗜。 一仃p ， 苍3 4 一。j = “”否卜。! 。1 j 一仃p l 1 j j 圭g 地一盯f ，艇靠) 产l p 。一ak 似g 耽一一蚴) 8 。一8 。 = l ，2 ，槐) ， 伍= 脚+ l ，m + 2 ，i 一1 l ( 3 9 ) 西北t 业大学硕上学位论文 尚需计算“， 9 2 m ，l f ，= p 的第i 个分量，即 将( 3 9 ) 式代入上式解得 甜=f 3 1 0 ) 由式( 3 8 ) ( 3 1 0 ) 即得求解l o e w n e r 型方程组厶= b 的极小范数最小二乘解 的如下快速算法 算法1 ( 求l o e w n e r 型方程组缸= 矗的极小范数最小二乘解的快速算法) 第一步( 求陋l ) - 上t = u z d 。，j 的元素) g g ) = 一口( ”，厅0 ) = 0 。o = l ，2 ，一，1 ) 对于i = m + 1 ，m + 2 ，m + n 盯；= 一。g 地 “1 。 ( ，= 1 州2 ，) r p = g 丝一k 。蛾 k ：杰( f 组。一。 ，班? ，。) ：1 ，2 ，i 一1 ) j = l = 妻k = l 捂* 5 丽u i i “ 似= 1 2 一，m ) “5 j i ：百u u r * 2 ，”+ l ，m + 2 ，f 1 ) 1 2 = ， 。h ，一 l l “ 两北工业大学硕1 二学位论文 g p ) = h ，0 ) ： 民= u 2 d l 阱6 ， 以2 “_ “：二 ，4 = _ + l 。九+ 。 ，盯j = f ：三一：“m , m + 1 1 该算法共需( 6 5 ) r a n + ( 2 7 + 1 5 如2 + 0 0 ) 次乘除运算，( 6 l + 3 k n + ( 2 t + o 5 如2 + d o ) 次加减运算，其计算复杂度为。如n ) + d 0 2 ) ，而用通常方法求解的 计算复杂度为d 白”2 ) + o g 3 ) 3 3l o e w n e r 型方程组极小范数最, j 、- - 乘解 的快速算法2 如果可以求得( 3 2 ) 中矩阵肘的三角分解 m = ( 一u l i u 。2 ( 一l 马 ( 一o l 葛) ， c ， l八d j 儿町j 7 其中巩为下三角阵，d j 为对角阵，则由式( 3 2 ) 和( 3 1 1 ) 得 l = u ：，l = u l d i u j ， 这是矩阵r 的一种三角分解从而l o e w n e r 型方程组上占= b 的极小范数最小二 乘解可通过求解方程组 u 2 d t 晖x = l r b f 3 1 2 ) 得到 n ( 3 1 ) 式知，式( 3 2 ) 的分块矩阵m 满足关系式 协 肼 州。 出， + 、lll、lll 门，j 北。咄o 两北工业火学硕士学位论文 ( 西 k m f 西 d jid = 龇静川加) 一 沙t 如同引理4 ，引入矩阵肘，且记 又记 。叫 ( 3 1 3 ) 吩= 凹( h ) p j ”训，d ；：，( f ：1 ，2 ，脚+ 竹) ( 3 1 4 ) “ 刚“k ( 西。m l 6 。) ( f = ，2 ，) ( 3 ，s ， 由( 3 1 3 ) 式知，r a l l l 【( m 御) s 2 ，所以由引理5 有 r a i l k 0 村卜1 ) 2 z ( = 1 ，2 ，抛+ n ) 又因为m ( “) 是对称的，从而m 0 1 ) 是反对称的，所以存在m + 门维列向量 使得 砖。) = ( 0 ，0 , x p ，x 。1 + 刀) ) t ， 谚。) = ( o ，o ，y 妒 ，y p + 力) ) t ， a m ( “) ：杰0 7 一，m “】t 一西叫对叫t ) 产l ( 3 1 6 ) 由( 3 2 ) 式及( 3 11 ) 式可知 q = ( - e ，汀，f f 2 ，o ) t ，吐：一1 ，o ：1 ，2 ，m )( 3 ，1 7 ) ( 3 。1 6 ) 式表乘e ，”( f 搬) 可得 n - p , _ j h 由上式即可求得 = 圭0 7 一一( j ) 一谚山砖棚( f ) ) ，( f 坍) ( 31 8 ) s = l 4 塑：些三些叁兰墅! 兰堡垒苎 砉g ”o ) 一y l 。忙埘 忙= i + i ，一，聊+ 疗；f m )( 3 1 9 ) 比较工t = u ：d 。町两边对角线上的元素，可得 由式( 3 1 0 ，( 3 1 5 ) ，( 3 1 6 ) ，( 3 1 8 ) 得 从而有 一攻2 ，( f 册) 圭埘1 一n 一谚x y ”) ：埘。) = ( 白。m 似叫西。 州“l ( 西小讲州。一( 白。 ( 3 2 0 ) = 窆g p 西1 ) 一砖霹。) 1 ) 一l tg 。- ( f ) 一y ? 。1 ) x p ) ( f ) ) k 酊 - i l j - - ij r d ： 。圭，：( x o - t ) r j y j 0 1 “1 ( f ) _ 硝一l y r x ? 一l ( z ) ) ，l j =j m = x 一一x 0 k ， 1j ，y = j ，? ”一d 。y y 一- o ) “一 ( 3 2 1 ) 由式( 3 1 4 ) ，( 3 1 7 ) ( 3 2 1 ) 口- 6 t 得求解l o e w n e r 型方程组极小范数最小二乘解的 快速算法 算法2 ( 求解l o e w n e r 型方程组极小范数最小二乘解的快速算法) 第一步( 求三的三角分解三= u ：d i 町) j 夕= ( ，。吣= ( ， ，( ，= t ，z ，- ， 对于i = 1 , 2 ，m + 打 当i = 1 , 2 ，m 时 1 5 瓦矗 m一 2 k ， ，h l i “ 两北t 业大学坝 学位论文 “。= 一1 = 0o = i + 1 ，m ) “= l ， 一， = ，竹+ 1 ，一，聊+ 行) 正= 一1 当i = m + 1 ，m + 2 ，一，m + n 时 2 矗黔叫 ( f ) 一y m 圳( f ) ) = i + 1 ，- m + 挖) = 乳。一d 。2 ；it - m + l d ：上 徽引激戳k “，扣墟，) y ) = y 0 ) 一d ，_ y ( o u 。”“。“v 递推求解线性方程组u 2 d i 町x = r 西求得