（计算数学专业论文）特殊矩阵类及其逆矩阵的快速三角分解算法.pdf

特殊矩阵类及其逆矩阵的快速 三角分解算法 摘要 对于特殊矩阵的快速三角分解算法的研究，目前主要是对一些较简单的矩 阵进行的如对t o e p l i t z 矩阵、l o e w n e r 矩阵、v a n d e r m o n d e 矩阵、h a n k e l 矩阵 等，都得到了一些有效的三角分解算法，其计算量均为o ( n 2 ) 本文研究更广类 型的一些特殊矩阵，如t o e p l i t z 型矩阵、l o e w n e r 型矩阵、对称l o e w n e r 型矩阵 以及v a n d e r m o n d e 型矩阵等，根据这些特殊矩阵的结构特点，给出了相应的快速 三角分解算法 2 给出了本文所有算法的理论基础 在3 中，首先给出t o e p l i t z 型矩阵的定义，然后推导t o e p l i t z 型矩阵的逆矩 阵的快速三角分解算法继而推导t o e p l i t z 型矩阵的快速三角分解算法 在4 中，首先给出l o e w n e r 型矩阵的定义，然后推导l o e w n e r 型矩阵的逆 矩阵的快速三角分解算法继而推导l o e w n e r 型矩阵的快速三角分解的算法 在5 中，首先给出对称l o e w n e r 型矩阵的定义，然后推导对称l o e w n e r 型 矩阵的逆矩阵的快速三角分解算法继而推导对称l o e w n e r 型矩阵的快速三角分 解算法 在6 中，首先给出v a n d e r m o n d e 型矩阵的定义，然后推导v a n d e r m o n d e 型 矩阵的逆矩阵的快速三角分解算法 在7 中，首先给出h a n k e l 矩阵的定义，然后推导h a n k e l 矩阵的逆矩阵的快 速三角分解算法 在8 中，给出了本文算法的一些数值算例，说明了算法的有效性 关键词：t o e p l i t z 型矩阵，l o e w n e r 型矩阵，对称l 0 e w n e r 型矩阵，v a n d e m o n d e ，碑矩阵 h a n k e l 矩阵，逆矩阵，快速三角分解 中国图书资料分类号： 0 1 5 1 2 1 a m s ( 2 0 0 0 ) c l a s s i f i c a t i o n ： 15 a t h ef a s tt r i a n g u l a rf a c t o r i z a t i o na l g o r i t h m s o f s p e c i a im a t r i c e sa n dt h e i ri n v e r s i o n a b s t r a c t i ti s m a i n l y t os o m es i m p l em a t r i c e st ot h er e s e a r c ho ft h ef a s t t r i a n g u l a r f a c t o r i z a t i o na l g o r i t h m so fs p e c i a lm a t r i c e su pt on o w f o re x a m p l e ，t ot o e p l i t z m a t r i c e s 、l o e w n e rm a t r i c e s 、v a n d e r m o n d em a t r i c e s 、h a n k e lm a t r i c e s ，e t c w eh a v e g o t t e ns o m ee f f e c t i v ef a s tt r i a n g u l a rf a e t o r i z a t i o na l g o r i t h m st ot h e s em a t r i c e s t h e y a r ea l ln e e do fo ( n 2 ) o p e r a t i o n s i nt h i sp a p e r , w er e s e a r c hs o m em o r eg e n e r a ls p e c i a l m a t r i c e s ，f o re x a m p l e ，t e o p l i t zt y p em a t r i c e s 、l o e w n e rt y p em a t r i c e s 、s y m m e t r i c a l l o e w n e rm a t r i c e sa n dv a n d e r m o n d et y p em a t r i c e s ，a n ds oo n w er e s p e c t i v e l yg e t t h e i rf a s tt r i a n g u l a rf a c t o r i z a t i o na l g o r i t h m sa c c o r d i n gt ot h ec h a r a c t e ro ft h e s e s p e c i a l m a t r i c e s 。 i n 2 w eg i v et h et h e o r e t i c a lb a s eo fa l lt h ea l g o r i t h m si nt h i sp a p e r t n 3 ，w ef i r s tg i v et h ed e f i n i t i o no ft o e 窭i t zt y p em a t r i c e s ，t h e nw eg i v et h e t r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo f t h ei n v e r s i o no f t o e p l i t zt y p em a t r i c e s w eg i v e t h et r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo f t o e p l i t zt y p em a t r i c e si nt h ee n d i n 4 ，w ef i r s tg i v et h ed e f i n i t i o no fl o e w n e rt y p em a t r i c e s ，t h e nw eg i v et h e t r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo f t h ei n v e r s i o no fl o e w n e r t y p em a t r i c e s w eg i v e t h et r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo f l o e w n e r t y p e m a t r i c e si nt h ee n d ， i n 5 ，w ef i r s tg i v et h ed e f i n i t i o no fs y m m e t r i cl o e w n e rt y p em a t r i c e s ，t h e nw e g i v et h et r i a n g u l a rf a e t o r i z a t i o na l g o r i t h mo ft h ei n v e r s i o no fs y m m e t r i cl o e w n e r t y p em a t r i c e s 。w eg i v et h et r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo fs y m m e t r i cl o e w n e r t y p em a t r i c e si nt h ee n d i n 6 ，w ef i r s tg i v et h ed e f m i t i o no fv a n d e r m o n d et y p em a t r i c e s ，t h e nw e g i v e t h et r i a n g u l a rf a c t o r i z a t i o na l g o r i t h mo f t h ei n v e r s i o no f v a n d e r m o n d e t y p em a t r i c e s i n 7 ，w ef i r s tg i v et h e d e f i n i t i o bo fh a n k e lm a t r i c e s ，t h e nw eg i v et h e t r i a n g u l a rf a c t o r i z a t i o na l g o r i t h m o f t h ei n v e r s i o no f h a n k e lm a t r i c e s 。 t n 8 w eg i v es o m en u m e r i c a le x a m p l e st oc h e c kt h e v a l i d i t y o ft h e s e a l g o r i t h m s k e y w o r d s ：t o e p l i t zt y p em a t r i x ，l o e w n e rt y p em a t r i x ，s y m m e t r i cl o e w n e rt y p e m a t r i x ，v a n d e r m o n d et y p em a t r i x ，h a n k e lm a t r i x ，i n v e r t i n gm a t r i x ，f a s t t r i a n g u l a rf a c t r o i z a t i o n c l c ：0 1 5 1 2 l a m s ( 2 0 0 0 ) c l a s s i f i c a t i o n ：1 5 a 1前言 一、研究特殊矩阵计算的意义 计算机技术的迅速发展，使得科学计算作为科学研究的有效手段，上升为与 科学理论和科学实验相并重的三大科学方法之一近几十年来，科学技术突飞猛 进的发展，国防科技和国民经济建设的许多领域不断提出许多大型和超大型的 计算问题这些问题要求计算机系统有更高的速度和更大的信息存储量，从而促 使计算机体系结构向巨型化和并行化方向发展然而巨型机和并行机的发展受 限于一一个国家的综合国力，作为一个发展中的国家，我国的计算机发展水平与先 进国家比较还有相当的差距，并且不能指望人家把最先进的技术和最好的计算 机卖给我们因此，如何利用现有的计算机处理尽可能大型的问题是很实际的一 个课题由于科学技术和工程应用中要遇到大量的矩阵计算问题，而相应的矩阵 往往具有一些特殊的结构，因此利用这些矩阵的特殊结构和技巧性处理，使矩阵 的计算量降低一个数量级，即由一般的o ( n 3 ) 降低到o ( n2 ) 或更低，这一问题的 研究具有理论意义和现实意义 对于特殊矩阵的研究，一直为国际和国内所关注在国际著名的杂志，如美 国的l i n e a ra l g e b r aa n di t s a 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 cc 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 矩阵、非负矩阵、 对角占优矩阵、正定矩阵以及正稳定矩阵等等，更是近年来研究的热点这些特 殊矩阵在数值分析、优化理论、自动控制、数字信号处理、系统辨识、工程计算 等领域中有重要的应用为了提高矩阵计算的效率，研究如何利用矩阵本身的结 构特征，得出计算特殊矩阵的快速算法，具有重要意义 众所周知，对n 阶方阵进行三角分解，所需计算量为o ( n3 ) 而对一些特殊 矩阵，我们可以根据其结构特点，得出o ( n 2 ) 阶的快速三角分解算法当n 较大 时，这大大减少了运算量本文对一些特殊矩阵类的快速三角分解算法进行研 究 二、有关特殊矩阵类三角分解的研究现状 有关t o e p l i t z 矩阵的o ( n 2 ) 阶快速三角分解的研究，开始于l e v i o s i o n 在1 9 4 7 年对以t o e p l i t z 矩阵为系数的线性方程组的研究m 】 1 9 6 0 年d u r b i n ” ，1 9 6 4 年t r e n c h “】1 9 6 9 年z o h a r t ”1 等人分别把l e v i n s i o n 的 工作加以补充和推广，分别给出了有关t o e p l i t z 矩阵的逆矩阵的快速三角分解算 法 1 9 7 2 年g o h b e r g ，s e m e n a l t ”】，1 9 7 8 年k a i l a t h ，v i e r a 和m o r t _ f ”】，1 9 8 6 年b e n a r t z ia ，s h a l o m t 【2 4 】以及1 9 8 7 年k a i l a t h ”i 等表明t o e p l i t z 矩阵的逆矩阵一般不再 是t o e p l i t z 矩阵，但能表示为一些三角t o e p l i t z 矩阵的乘积之和 1 9 7 3 年a k a i k e l 2 ”，1 9 8 4 年h e i n i n g 和r o s d ”1 给出了分块t o e p l i t z 矩阵的逆矩 阵的快速三角分解算法 1 9 7 5 年b u r g 2 5 1 给出了t e o p l i t z 矩阵的逆矩阵的u d l ( 上三角、对角、下三角) 分解 19 8 7 年k a i l a t h ”i ，l 9 7 3 年r i s s a n e n t ”，19 6 9 年b a r e i s s l 2 “，19 7 0 年m o r t = 1 2 ”19 7 4 年m o r f 2 ”，1 9 7 7 年l er o u x ，g u e g u e n t 2 9 1 等给出了t o e p l i t z 矩阵本身的o ( n2 ) 阶决 速三角分解算法 对有关l o e w n e r 矩阵以及相关的矩阵的三角分解的研究，现有文献较少 1 9 9 9 年徐仲，张凯院，陆全m 1 等人给出了有关c a u c h y 型矩阵及其逆矩阵的三角分 解以及对称l o w e n e r 型矩阵的逆矩阵的o ( n 2 ) 阶快速三角分解算法 关于v a n d e r m o n d e 矩阵的三角分解的研究，从二十世纪5 0 年代末至今，一直 受到人们的重视人们把v a n d e r m o n d e 矩阵从不同角度推广，得到诸如 v a n d e r m o n d e 型矩阵，v a n d e r m o n d e 类矩阵，合流v a n d e r m o n d e 矩阵等等一系列 重要结果 1 9 9 1 年c h u n ，k a i l a t h t 3 2 1 给出了v a n d e r m o n d e 矩阵o ( n 2 ) 阶三角分解的快速算 法 1 9 9 7 年徐仲【3 5 l 给出了合流v a n d e r m o n d e 矩阵的逆矩阵的o ( n 2 ) 阶快速三角 分解算法 有关h a n k e l 矩阵o ( n 2 ) 阶快速三角分解算法的研究大致如下：1 9 6 5 年 t r e n c h 1 9 6 8 年b e r l e k a m p ，1 9 7 4 年r i s s a n e n 鸭1 9 8 3 年g r a g g 和l i n d q u i s t i ”i 1 9 8 4 年h e i n i g 和r o s t i l 9 1 分别出h a n k e l 矩阵的逆矩阵的o ( n 2 ) 阶快速三角分解算 法 1 9 7 1 年p h i l l i p s 巴1 9 7 4 年g r a g g 巴1 9 8 6 年l e v a r i 和1 k a i l a t h t “，1 9 8 9 年c h u n t “， 1 9 9 0 年l a b a h n ，c h o i ，c a b a y 呷1 ，1 9 9 4 年p a l ，k a i l a t h t “1 分别给出求h a n k e l 矩阵的 o ( n 2 ) 阶三角分解算法 1 9 7 3 年r i s s a n e n ，1 9 8 6 年c i t r o n t 9 1 分别给出h a n k e l 矩阵及其逆矩阵的 o ( n 2 ) 阶快速三角分解算法 三、本文的研究内容及安排 综上所述，对于特殊矩阵的快速三角分解算法的研究，目前主要是对一些较 简单的矩阵进行的如对t o e p l i t z 矩阵、l o e w n e r 矩阵、 v a n d e r m o n d e 矩阵、 h a n k e l 矩阵等，都得到了一些有效的三角分解算法，其计算量均为o ( n 2 ) 本文研究更广类型的一些特殊矩阵，如t o e p l i t z 型矩阵、l o e w n e r 型矩阵、 对称l o e w n e r 型矩阵以及v a n d e r m o n d e 型矩阵等，根据这些特殊矩阵的结构特点， 给出了相应的快速三角分解算法 本文在2 中，给出本文所给算法的理论基础，在3 、4 、5 ，分别给出 了t o e p l i t z 型矩阵，l o e w n e r 型矩阵，对称l o e w n e r 型矩阵以及它们的逆矩阵的快 速三角分解算法在6 、7 ，分别给出了v a n d e r m o n d e 型矩阵和h a n k e l 矩阵的 逆矩阵的快速三角分解算法在8 ，给出了一些算法的数值算例 2 主要结论 给定 阶方阵4 = ( a ，) ? ，汜爿的阶顺序主子阵和倒序主子阵分别为 f 甜“+ a t = ( a ，) ，互= lo p l 订 m l o n “吼m h l ： ：j a 。，一， a 。一i 。j 七。= 1 ，2 ，月 口 一1口n nj 又记p 是第f 个分量为1 ，其余分量为0 的 维单位列向量 引理1 若4 的各阶顺序主子阵4 ( 女：1 ，疗) 均可逆，则 禽1 = ( 筝约+ ( 一鼍m 卜矗t ) c e 吃m 。：， 其中c “2 ( q ，口“，t ) 7 ， 啦= a k l , , a k , k _ o ，吼：一吐，月矗q 。 证昵由假设知 伞引 因为 ( 一髓 由a k 可逆知饥0 ，所以 设 又设 铲滢刊挣算0 ) 2 ( 爷1 弘r ，心甜，) 证毕 副理2 给定线性方程组舭= ，4 r y 。擘，其中 ，= ( ：，z ) 7 ，g = ( 鼬一，g 。) r 2 ，无) 7 ，= ( 耵一，) t 、1， o 吼 靠矿 ， j f 、，l q 。 一 r o v o 足 _ 女椎 晚= ( 吨一，x k k ) ，y k = ( 儿，y “) 1 = ( “，l d k k ) 7 ，v k = ( v 卅，v 从) 7 分别是线性方程组 a k x k = | | 的解向量 若爿的各阶顺序主子阵a 。( k = 1 ，n ) 均可逆，则 f 一1 2 l 刊 女j ，。= j 占1 + r 。v 。 其中 吼= ( _ 啦爿矗。l 阢= 一吐，砟一，= 一芝机 靠：( _ c 己，4 矗1 k 。：既一c 己。儿一：乳一芝y 。， 证明利用引理l ，有 = 弘r 1 卜站) 上式及其转置分别右乘p r 得 由 = 4 一e = 一( 一4 亏，n ，叱= 爿，e = 彩i 1 ( 一4 荦“。 c z 2 ， 并利用( 2 2 ) 式得 = ( + ) 1 ，g 。= ( 乳+ g ) 7 铲 2 纠慨i 卜州骺卜吼 y 。= 占。2 爿絮“ + 列( 一智k 1 卜一c 工硭乳沪( 名 帆叱 引入2 n 阶方阵 证毕 m = e2 对己 ”( 蠢。恕， 其中，。t 一。，： 。：二：。一。， ，且，z 厅时，有 由( 3 1 1 ) 可得 m k zk m k z = 善( 吖p 设 o r ) + 帆= k ， j 。( 一。)1 o ( t 一。) 。【一。) j 矗”= ( 矗n ，砝) 1 ，毹= ( 叮 弦一，础，) - ，“抽) 7 ，v = ( v ，) 1 ，唧= ( ，b k k ) 7 ，q = ( c 4 ( 3 1 2 ) 0 一 ，u 、， ”呻0 r，、 + 、j 叫 t 。”卅 月 ，“ p 一 分别为线性方程组 蚶，- 蚴k m k u k = e ，m j vk = e 譬 m 。r k = 雌。锻 m 女b 女= ( 1 ，一f 1 。，一一，一r 。p ：野) m j c t = ( 1 ，一f 川，一f i ，0 1 ) m 。fo 一。，： l h 一1 妻掣佳科。川 卜， j = ll ”i 一 f - 2 然后再两边左乘m i l ，有 一f n in - f 。p 巴 “三， 一h 。= ( 善“力 ( 喜 ，j ) l , l l _ l , k _ i + “。一以 c ，z ，式两边取转置，再右o l ，三 ，有 一，。 ，。l 睫o n m j ( 。二) 一e = 善 二 ( 砉g ，j ) v k _ i , t _ i 一喜屯v 。扎，( 墨。 + v 。 然后再左乘m i l ，有 ( 3 1 3 ) 一。一 0 唯一 ” 0 h 一 ( ，三， v 。= = ( 善毹 ( 砉g ，1 ) v 。一，。一。 j r v k _ l , n c k - - ，：。，。v 。一，s 。 c ，。， 利用引理2 ，可得到如下关系式： 对于线性方程组 m k 的解，满足关系式 k 叫 其中。 门= ( - e 告 t f 2 。 ，：( ! 2 一e ：! i 帕1 p l 骘= 一矗：k 一。 珊k 毹呜螂。 其槠( k - n ) t 硝栏卜。( k - 町础叫翘卜。 g k r k = ( 。邑 有 厶“= 肘：i p 嚣”= l t l “ 当k + 1 时，由引理2 得 咋= i t ：1 + 五 其中瓦= ( - k - 。町1 孵，( 。是 = 一( k - ，町7 钆= 一训。 砧。锻 ( 3 15 ) f 3 1 6 ) ( 3 1 7 ) ( 3 1 8 ) s h 十1 2 m n - + t l f n ( n + + l ) = v 十j 当k n + 1 时，由引理2 得 铲( 5 ；1 怖。 其中瓦= ( _ e ：譬岍m = l l e ：o l = 一e 告邮一。= 一“小。 对于线性方程组 m 女b i = ( 1 ，一t l 。，f ”一lh ，t n n p k 1 - 1 n 7 ) 7 的解，由引理2 得 e 。= i ，饥= ( 1 + 子。脚c 七= z ，z 珂， 嚣中 o k 2 一靠- 1 。一，“岛j i ( 七= 2 ，- 一，n ) ( 女= n + 1 ) ( t = 胆+ 2 ，一，2 n ) ( 3 1 9 ) ( 3 2 0 ) ( 3 2 1 ) 对于线性方程组 m j 吒= ( 1 ，一t ，一t n , n - i 0 7 ) 1 的解，由引理2 得 = 素一= k - 却川咄勘， b z z ， 其中 一卜t 一缸c “。，( 七：2 ，。) ( = ”+ 1 ，- 一，2 n ) 将( 3 1 5 ) 式，( 3 1 8 ) 式，( 3 2 1 ) 式分别代入( 3 1 3 ) 式，有 饥= ( 0 。 一善( 砉矽k 廿， c ( 苍) ) + 一。雌，吨卜c ( i + 文巩， 7 )峨 + 、， k o r“ 0 i m ， + l + 芝窆 h 。仃：) + 俄一瓦( n - i 。u ，) j 嘶： l ，= i = 2 k il ( m o 。一， 一善( 砉一，7 ) “，一t 一一t ( 繁 一“。，。一，( 1 + 筹r 。，“，。一，f c ，z s ， k 2 = ( 。o 一) 艺j = l f ：1 i = 2 ：硝7 ) v t 一。，一) c ( 嘭 r 7 ) v 。，一v 。一，c ( 。占1 - t j v 。， + k ) 川嘞， 整理得 j1 + 善萋跏卜，+ t t ( n h ) k l j 。2 k ll ( 0 一薯( 砉西”v t 一“一。) 9 2 0 1 一v 。， 。k 。- 1 + ( 喜，。v 。一v ) ( 5 k 。- - c 。z 。， 综合( 3 1 5 ) ( 3 2 4 ) 得求解t o e p l i t z 型矩阵z = ( f f ) ：h 的快速三角分解算法 如下 算法3 2 前h 步同算法3 1 6 = 士 lj l l c i i 2 l 对t = 2 ，h ，计算 吼一t k 却一o6 l 卜， t = 一，r 巩= + 哓峨 哪。 对k = ”+ 1 ，胛+ 2 ，一，2 n ，计算 仃= 一p 掐。 r ：”= 一q 出。 0 k 。一一n 女一i “= 一s i 1 一n 卜f 。一b h 7 = 【一b k 一。 一i z k2 - - c k l 一月 ( ，= 1 , 2 ，m ) ( ，= 1 , 2 ，朋) 如果k = t t + 1 如果k 疗+ 1 一薯( 耖 一) 。+ 缸。( 讣泸啦，川 叱= 11 + ng j ”v 。， ”+ v 。，t 一氕( n 屯v 。，) l im1 = f = l，；l 1 2 ，= 1 i c ，三 一善( 砉g j 。) v 。一，一 ( 9 一v ；一，( 。k 。- 1 + 蕃nt 。v 。一，( 1 ，c ，= ，z ，- ， 11 一 u k kv “ = 科”1 2 ，川 矾忆m 。”墟，晰) 9 吒。1 ( - n + l1 + 瓯如果七 ”+ s 2 ( 。 + 瓦v t 如果尼 n + - 钆= 城 c 。= ( 。k 。- 1 + 幺v 。 4l o e w n e r 型矩薄及其逆矩阵的快速三角分惩 给定四组数搿，影，( j = 1 , 2 ，月) ，且设a ，只( f ，= 1 , 2 ，1 ) ，称矩阵 上。f 殳列8 i 一易l ； 为l o e w n e r 矩陈 容易验证，l o e w n e r 矩阵三满足关系式 d i a g ( a _ i ，) 三一l d i a g ( f i t ，成) = 裔，磊y 垂，1 ) 一( 1 ，1 ) t 橛，纸) 由此给出如下定义 定义2 给怒两缀数q ，g ( = l ，攒) 和行维列向薰g ”，( 歹= l ，m ) 蓑 摊玲方黪l = ( 屯圪：；瀵足 d i a g ( c t ，一，哎) 三一l d i a g ( i l l ，缓) = h 7 f 4 。1 ) 则称工为l o e w n e r 型矩阵 可见，当m 。2 ，髓g = 营l ，l 一，磊y ，h ”= g = ( 1 ，1 ) 7 ， h 栩= 一幻 一，玩罗露，五靼麓l o e w n e r 缒薄 一、l o e w n e r 型矩阵憋逆矩阵的快速兰焦分解 设王为l o e w n e r 型矩簿，叉设熬莠狯燕瑟彦麦子阵纛掺鸯辩，弱国4 。1 ) 褥 d i a g ( c l ，t 一，颤) 鑫一l , d i a g ( i l l ，反) = 羔誉矗p 7 ( 4 2 ) 箕孛痰”= ( g l ”，g ，”= ( ，磷) 7 又设 壤2 ( g i ，l g k k ) ， 烈”= ( 反努，崩) 7 ，或”= 磁一，竣1 ) 7 2 1 分别是线性方程组 厶u k = p ， 厶“= g ： e h = e e q ：= 彬 的解向量 ( 4 2 ) 式两边同时左乘及右乘1 ，再右乘p ，有 ( i k d i a g ( i l l ，鼠) ) = g ：f 一7 ( 4 2 ) 式取转置，再同时左乘及右乘丘，并右乘e ，有 m ( d i a g ( a l ，( r k ) - - 鼠l ) ) 咋= p ：毹” 由引理2 ，方程组 厶矗力= 毹”，上t 碰”= 雕” 的解向量满足 “”= 帆 k l 其中盯 = g i ”一_ p j - l 毹忆( 钟枷。 其坩= h l j ) - 蕃k - i 酬2 r 把( 4 5 ) 式代入( 4 3 ) 式，有 c i k - d i a g ( 盼，”v 寺：”饥秘，吼 把( 4 6 ) 式代k ( 4 4 ) 式，有 ( d i a 咖l i ，) 一f l k i k ) ) v k ：r a 哗1 m 。羔一吩咋 j = l”j = l ( 4 3 ) ( 4 4 ) ( 4 5 ) ( 4 6 ) ( 4 7 ) 嚣 1 i 肚 v 1 i 竹 “ 代入前面两式，并整理得 d i a g ( ( i l k 一层) ，( i l k 一反 ) ，0 ) 砘知， ( 4 8 ) j = llu d i a s ( ( 口t 一口e ) ，一，( d t t 一口e ) ，。) 叱= “u 善一” q | j ( 。，) 综合( 4 5 ) 一( 4 9 ) 得求解l o e w n e r 型矩阵上= ( ，) i ，= l 的逆矩阵的快速三角分 解算法如下 算法4 1 1 ”一丁 兄= ， 硝) = 芈 ( 川，m ) g f f k 等 泸l ，训 对k = 2 ，n 有 k - l 础k g 一k p ( ，= 1 ，朋) k - l r = 桫一屯g ( ，= 1 ，坍) 。：孚丑 ( ，：1 ，。) 仃肚 n 11 t 2 2 “船v 触 “* = 瓦v o 艺。r 踟( f _ l ，七一1 ，= 1 ，m ) 2 者静，( f ：1 ，扣小， 毹蛇帆n 秽艚卜：。 ( j = 1 ，m ) ( = l ，聊) 该算法需要2 ( m + 1 ) n 2 + o ( m n ) 次乘除运算，( 2 m + i 如2 + o ( m n ) 次加减运算 二、l o e w n e r 型矩阵的快速三角分解 设肘= ( 乏： ，又设 硝”= d i a g ( a 1 i 一，) ，叫2 l d i a g ( f l , ，成) 由( 4 1 ) 式可得 r 帮m m ( 璎