（运筹学与控制论专业论文）一类大型稀疏无约束优化的算法.pdf

摘要 本文研究一类求解大型稀疏无约束优化的几种方法，取得如下的主要结果： 1 第4 章建立求解大型稀疏无约束优化问题的对称三角分划割线算法。此算法是基于 稀疏h e s s e 阵的下三角部分的列的相容分划的基础上建立起来的，把割线法和有限 差分法有机的结合在了一起，在每次迭代中，把由p o w e l l 和t o i n t 的算法( 间接下三 角替换法) 所需要的梯度赋值次数减少了一。此算法的哥超线性收敛性和r 一敛速估 计表明了它有一个好的局部收敛性质，而且，我们对b r o y d e n 算法和s c h u b e r t 算法 更精确了误差估计，改进了k a n t o r o v i c h 一型分析。 2 第5 章基于稀疏h e r e 阵的列的相容分划，并在其c h o l e s k y 分解的基础上建立了 求解大型稀疏无约束优化问题的直接校正c h o l e s k y 因子算法。此算法利用近似稀疏 h e s s e 阵初始c h o l e s k y 分解和分划的列，然后在每步直接逐次地修正其对角因子和 下三角因子中与原h e s s e 阵的分划列相应的部分，其迭代来源于修正因子的前代和 回代。此算法的自修正性、g 超线性收敛性和卜敛速估计表明了它有一个好的局部 收敛性质。 3 第6 章对第4 章和第5 章给出的算法进行数值试验，数值试验结果表明t 面对求解 某些大型稀疏无约束优化问题，这两种算法在某些方面都明显的比其它所比较的算 法更有效。 关键词；算法；超线性收敛；数值例子；无约束优化；稀疏；有限差分；替换；割线 h e s s e 阵；c h o l e s k y ；修正；分划；自修正性 ac l a s so fa l g o r i t h m sf o rl a r g es c a l es p a r s eu n c o n s t r a i n e do p t i m i z a t i o n a b s t r a c t t h i sd i s s e r t a t i o ns t u d i e sac l a s so fs e v e r a la l g o r i t h m sf o rs o l v i n gl a r g es c a l es p a r s e u n c o n s t r a i n e do p t i m i z a t i o n i t sm a i nr e s u l t sm a yb es u m m a r i z e da sf o l l o w s ； li nc h a p t e r 4 ，as y m m e t r i ct r i a n g u l a rp a r t i t i o n e d s e c a n tm e t h o df o rs o l v i n gl a r g es c a l e s p a r s eu n c o n s t r a i n e do p t i m i z a t i o np r o b l e m si sc o n s t r u c t e d ，w h i c hi sa c o m b i n a t i o n o fas e c a n tm e t h o da n daf i n i t ed i f f e r e n c em e t h o d ，a n dd e p e n d so nac o n s i s t e n tp a r t i t i o no ft h ec o l u m n so ft h el o w e rt r i a n g u l a rp a r to ft h eh e s s i a nm a t r i x ；i tr e d u c e s t h en u m b e ro fg r a d i e n te v a l u a t i o n sr e q u i r e db yp o w e l ta n dt o i n t sa l g o r i t h m ( t h e i n d i r e c tl o w e rt r i a n g u l a rs u b s t i t u t i o na l g o r i t h m ) b yo n ea te v e r yi t e r a t i v es t e pa q - s u p e r l i n e a rc o n v e r g e n c er e s u l ta n da nr - c o n v e r g e n c er a t ee s t i m a t es h o wt h a tt h i s m e t h o dh a sg o o dl o c a lc o n v e r g e n c ep r o p e r t i e s ，a n dw es h a r p e ne r r o re s t i m a t e sa n d i m p r o v ek a n t o r o v i c h - t y p ea n a l y s e sf o rb r o y d e n sa l g o r i t h ma n ds c h u b e r t sa l g o - r i t h m 2i nc h a p t e r 5 ，an e w m e t h o dw i t hd i r e c tp a r t i t i o n e dc o l u m nu p d a t e s o fc h o l e s k yf a c t o r i z a t i o nf o rs o l v i n gl a r g es c a l es p a r s eu n c o n s t r a i n e do p t i m i z a t i o np r o b l e m si sp r o p o s e d ， w h i 出d e p e n d s o nac o n s i s t e n tp a r t i t i o no ft h ec o l u m n sa n dc h o l e s k yf a c t o r i z a t i o no f t h eh e s s i a nm a t r i x ，t h i sm e t h o de m p l o y sa ni n i t i a lc h o l e s k yf a c t o r i z a t i o na n dp a r t i t i o n e dc o l u m n so ft h ea p p r o x i m a t i o nh e s s i a na n dt h e nc o r r e c t st h ec o r r e s p o n d i n g c o l u m n so ft h ed i a g o n a lf a c t o ra n dl o w e rt r i a n g u l a rf a c t o rd i r e c t l ya n ds u c c e s s i v e l ya t e a c hs t e p i t e r a t i o n sa r eg e n e r a t e du s i n gf o r w a r da n db a c k w a r ds u b s t i t u t i o ne m p l o y - i n gt h eu p d a t e f a c t o r i z a t i o n s ，as e l f - c o r r e c t i n gp r o p e r t y , aq - s u p e r l i n e a rc o n v e r g e n c e r e s u l ta n da nr c o n v e r g e n e er a t ee s t i m a t es h o wt h a tt h i sm e t h o dh a sg o o dl o c a lc o n v e r g e n c ep r o p e r t i e s 3 ，c h a p t e r6p r o v i d e sn u m e r i c a le x p e r i m e n t sg i v e nb yt h ea l g o r i t h m si nc h a p t e r4a n d c h a p t e r5 t h en u m e r i c a lr e s u l t ss h o wt h a t ，f o rs o l v i n gs o m el a r g es c a l es p a r s eu n - c o n s t r a i n e do p t i m i z a t i o np r o b l e m s ，t h et w oa l g o r i t h m sa r eo b v i o u s l ym o r ee f f e c t i v e t h a na n yo t h e ra l g o r i t h m sc o m p a r e dw i t hi ns o m ea s p e c t s 。 k e yw o r d s ：a l g o r i t h m ；s u p e r l i n e a rc o n v e r g e n c e ；n u m e r i c a le x a m p l e ；u n c o n s t r a i n e do p t i m i z a t i o n ；s p a r s i t y ；f i n i t ed i f f e r e n c e ；s u b s t i t u t i o n ；s e c a n t ；h e s s i a n ；c h o l e s k y ；u p d a t e ； p a r t i t i o n e d ；s e l f - c o r r e c t i n gp r o p e r t y u 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名；查! 茎聋一日期；丝堕! ：! 乡 1 绪论 本章对求解大型稀疏无约束优化的几种方法进行扼要的综述，并介绍选题的背景及 主要结果。 1 1 大型稀疏无约束优化 首先，我们应该知道求解稀疏无约束优化问题就是求解导数为零的稀疏非线性方 程( 组) 的问题。因此，对本问题的研究可以先从研究稀疏非线性方程( 组) 的问题入 手。早在十九世纪七十年代，s c h u b e r t 1 9 7 0 “】就给出了割线法去解稀疏非线性方程 组的问题，这种方法实际上是b r o y d e n 1 9 6 5 一方法的稀疏修正，故称之为稀疏b r o y - d e n 算法。b r o y d e n 1 9 7 1 6 1 也单独给出了这种算法稀疏b r o y d e n 算法的最吸引人的 地方就是每一次迭代中它仅使用一个函数值，而且还保持着局部口一超线性收敛性( 见 m a z 。w i j f l 9 7 9 p 】) 近来，基于矩阵占的三角因子和稀疏修正上三角矩阵u ，b a i 和 w a n g 1 9 9 3 ，1 9 9 6 f 蝇4 q 提出了一类因子修正算法，其好处是，在没有引进m 步再因子 化，就能保持局部q 超线性收敛性，从而减少了运算量这比d e n n i s 和m a r w i l 1 9 8 2 2 6 】 提出的似步再因子化算法有了较大的改进 c u r t i s ，p o w e l l 和r e i d 1 9 7 4 一也提出了一种针对稀疏问题的方法，被称为c p r 算 法，它实际上是有限差分算法，但它利用了j a c o b i 矩阵的稀疏性使得其函数估计值数比 般的有限差分算法小此后l i 1 9 8 8 1 2 0 又给出了割线有限差分( s f d ) 法 c p r 和s f d 算法都是基于j a c o b i 矩阵的列分划。 对大型优化问题，人们关心的一个问题就是怎么有效地去计算或近似这些h e s s e 矩 阵和j a c o b i 矩阵的问题由此，人们提出了许多方法，其中包括自动微分法( a u t o m a t i c d i f f e r e n t i a t i o n ) ( 如；g r i e w a n k 和c o r l i s s 1 9 9 1 1 1 j ) 、按组部分可分离性法( g r o u pp a r t i a l s e p a r a b i l i t y ) ( 见c o n n ，g o u l d 和t o i n t 1 9 9 0 1 2 1 ) 、稀疏h e s s e 阵的拟n e w t o n 修正的扩 展( 见t o i n t 1 9 7 7 1 3 4 1 和f l e t c h e r 1 9 9 5 3 7 】) 、列修正拟n e w t o n 算法( 见f e n g 1 9 s g l t l 3 】 或f e n g 和l i 1 9 8 3 a 1 1 4 】) 以及使用插值多项式和信赖域方法的无导数算法( d e r i v a t i v e 。f r e e a l g o i i t h m ) ( 见c o l s o n 和t o i n t 2 0 0 2 4 1 ) 等。 对于更有效地求解稀疏无约束优化问题，p o w e l l 和t o i n t 1 9 7 9 1 3 2 1 把c p r 算法的 一类大型稀疏无约束优化的算法 思想引入对称的情况，提出了两种实际有效的算法( 直接法和间接下三角形替换法) 以获 得h e s s e 阵的一个好的廉价近似，这使得不得不计算的一阶导向量的估计次数变小了， 直接法是基于h e s s e 阵的对称相容分划z h a n g 和l i 1 9 9 3 2 1 】给出了带有直接法的割线 有限差分法；间接下三角形替换法是基于h e s s e 阵的下三角部分的列的相容分划本作 者在张宏伟导师和于波教授的指导下给出了带有替换法的割线有限差分法( 对称三角 分划割线算法) ；并证明了此算法的q 一超线性收敛性，给出了算法的k a n t o r o v i c h 型定 理，而且得到了算法的r 一敛速估计；通过数值试验，与三角替换法等多种算法相比较， 从而从实例中表明了算法所具有的优越性，具体情况见第四章、第六章 另外，我们还应看到，尽管割线法在方程式情形优于n e w t o n 法，但在方程组情形， 虽然它仍具有超线性收敛性，然而，每步计算量却基本与n e w t o n 法相同，因此，其效 能并不较n e w t o n 法更优。拟n e w t o n 法是割线法的推广，它保持了割线法的超线性收 敛性，而每步计算量又明显地少于n e w t o n 法，因此，它成为解非线性方程组及优化问 题的最重要方法类。b r o y d e n 1 9 6 5 5 】提出的算法是拟n e w t o n 法的代表，进一步的研究 工作发现，d a v i d o n 1 9 5 9 1 【4 q 与f l e t c h e r 及p o w e l l 1 9 6 3 s s 所提出的变尺度法也属于拟 n e w t o n 法类。 近二十年来拟n e w t o n 法的研究十分活跃，现已提出了一些有效的算法，并且形成 了系统的理论和研究方法，d e 缸l i 8 与m o r a l 1 9 7 7 1 2 4 】对这些问题做了较系统的总结。近 年来，在拟n e w t o n 法的研究中的主要课题是，这类方法对大规模问题( 即多变量问题) 的适用性，以及方法的大范围收敛性。 解决第一个问题的关键是寻找保持稀疏性的算法因为稀疏性的传递性是拟n e w t o n 法是否适用于多变量问题的关键。t o i n t 1 9 7 8 3 5 】及s h a n n o 1 9 8 0 7 试图将s c h u b e r t 的 结论推广到对称情形，但在他们所提出的方法中为保持稀疏性，每步需要解一个具有同 样多未知数的线性方程组，即每步需要s c h u b e r t 方法两倍的计算量，因此保持稀疏性的 问题实际并未解决。冯果忱、李光烨、王德人等在这方面做了大量的工作，找到了保持 稀疏性和对称性的拟n e w t o n 法类，同时还证明了这类方法具有大范围收敛性，而且有 较高的收敛阶，这就是列修正拟n e w t o n 法类及行列修正拟n e w t o n 法类( 见冯果忱、李 光烨 1 9 8 3 a “】及f 1 9 8 3 b t 1 5 】) 列修正拟n e w t o n 法类曾由王德人【1 9 8 0 一按弦法思想导 出，他称之为佗点弦法( 参考王德人 1 9 7 9 p j ) 冯果忱等人推广了这类算法，提出了换 元修正n e w t o n 型方法，并且证明了所提出的方法保持着拟n e w t o n 法的优点，而且具有 大范围收敛性，其中若干算法同时保持稀疏性和对称性( 见冯果忱、亢正刚 1 9 8 3 】【1 q ) 在原h e s s e 阵正定性的条件下，王宇和冯果忱f 1 9 9 4 4 1 】又提出了直接逐次列修正 c h o l e s k y 因子的n e w t o n 型方法。并证明了其铲超线性收敛性且进行了r 一敛速估计， 同时还做了效能分析。本人结合上面他们所做的工作，在保持原h e s s e 阵稀疏性、对称 性和正定性的条件下，提出了直接逐次分划列校正c h o l e s k y 因子的算法，同样证明了其 2 大连理工大学硕士学位论文 g - 超线性收敛性且进行了r 一敛速估计，并通过数值试验比较，表明了算法所具有的有效 性，具体情况见第五章、第六章。 1 2 研究专题及主要成果 第四章首先考虑一类大型稀疏无约束优化问题的h e s s e 阵稀疏情况，给出对称三角 分划割线算法及其特性，再对给出的算法进行k a n t o r v i c h - 型分析，从而得出比b r o y d e n 算法和s c h u b e r t 算法的误差估计精确得多的结论，故改进了k a n t o r o v i c h 型分析。进一 步，我们又证明了算法的q 一超线性收敛性并进行了算法的r 一敛速估计。 第五章针对稀疏h e s s e 阵正定的情况，提出直接逐次分划列校正c h o l e s k y 因子算 法。然后证明算法具有的一个重要性质：自修正性。在此基础上得到了q 一超线性收敛性， 并给出了其算法的r 一敛速估计。 第六章通过数值试验比较，显示第四章、第五章算法具有的某些优越性。 2 引言 这篇论文关系到求解无约束优化问题 础r a i n 。他) 其中：f ：dcr ”一兄为舻上的二次连续可微函数。 求褓这类问题的最流行的方法是n e w t o n 法，即可以通过如下迭代 ( 2 0 1 ) 。川= 扩一( h ( x 。) ) 一1 v f ( x ) ，k = 0 ，1 ，( 2 0 2 ) 其中：h ( 扩) 是，( z ) 在扩处的h e s s e 阵，v f ( x ) 是f ( x ) 在舻处的梯度向量。 本文未经特殊声明，我们常用9 ( $ ) 表示y ( x ) 在。处的梯度向量v y ( x ) ，用日( z ) 表示f ( x ) 在z 处的h e s s e 阵。 对许多问题，h e s s e 阵稀疏例如，由非线性微分方程组离散化产生的大多数问题 有一个稀疏h e s s e 阵在这篇论文中，我们着重强调稀疏问题。 n e w t o n 法有一个好的局部收敛性质然而，在每次迭代步中，我们不得不计算其 h e s s e 阵，这在大多数情况是很耗费时间的因此，我们感兴趣的是，在不很耗费时间的 情况下找到一个n x n 矩阵b 2 而胪是和h e s s e 阵日( 扩) 的一个好的近似对于h e s s e 阵的一个近似，我们可以通过如下迭代： z + 1 = 。一( b 。) 一1 v ，( z ) ，南= 0 ，l ，- ，( 2 0 3 ) 对于稀疏问题，这里的b 是和h e s s e 阵h ( z ) 具有相同稀疏性的近似。由于h e s s e 阵 对称，我们假定b 对称。为了具体说明给定矩阵b 的稀疏性，我们使用m 来定义指 标对( i ，) 的集合，其中是b 的一个非零元素，即 m = “t ，j ) ：b q o ) ， 出于8 对称，如果( t ，j ) m ，那么( j ，i ) m 为方便起见，我们再写( 2 0 3 ) 如下 z = o b 一1 9 ( z )( 204 ) 大连理工大学硬士学位论文 其中z 是当前步，虿是下一步，而且b “h ( x ) 获得h e s s e 阵日( 孑) 的一个好的廉价近似b 是许多近期文章的一个重要主题，它也 是写这篇论文的目的之一。 当前，有几种得到百的方法在此，我们将提及其中三种典型方法。 ( 1 ) 有限差分法。通常此法有一个好的局部收敛性质。这是由于b 通过适当的选择 步长能得到对h e s s e 阵h ( 面) 的一个好的近似然而，当计算g ( x ) 的值很耗费时间时， 有限差分法仍是很耗费时间的对于稀疏阃题，如果我们能单个计算函数梯度值，那么， 有限差分法能够利用稀疏性去减少函数梯度估计值数。然而，在实际上，单个计算函数 梯度值通常很耗费时间。比方说，要是g ( z ) 的分量备个都有一个很耗费时间的普通子表 达式，就会出现这种情况基于以上考虑，我们在这篇论文中假定能够作为一个整体去 估计函数梯度值，而不是逐个估计它。在这种情况下，为了减少梯度估计值数，c u r t i s ， p o w e l 和r e i d 1 9 7 4 一提出了一种差分法( c p r , 算法) ，此法是基于j a c o b i a n 矩阵列分 划。 ( 2 ) 割线( 或拟n e w t o n ) 法。这种类型的算法首先是由d a v i d o n 1 9 5 9 ( 4 2 1 用来求 解无约束优化问题时引入的，然后，由b r o y d e n 1 9 6 5 5 】用来求解方程组。b r o y d e n 算法 最吸引人的地方就是在每一个迭代步仅露要一个函数值。但是，b r o y d e n 算法不能利用 j a c o b i 矩阵的稀疏性于是，s c h u b e r t 1 9 7 0 3 1 j 提出了b r o y d e n 算法的稀疏修正 ( 3 ) 逐次置换算法。p o l a k 1 9 7 3 1 1 q 提出一种逐次置换算法求解无约束优化问题。 f e n g 和l i 1 9 8 3 a l “j 发展了这种算法用来求解非线性方程组，并把这种算法称为列修正 拟n e w t o n 算法。使用这种算法，近似j a c o b i 矩阵的列通过逐次地、周期性的置换出来 尽管在每一个迭代步需要两个函数值，且只置换了一列，但是，它较其他拟n e w t o n 算法 优越的地方是，它能保持算法的自修正性。从而恢复了n e w t o n 法的某些优点后来， l i 【1 9 8 9 1 1 9 j 又结合c o l e m a n 和m o 砖【1 9 8 3 p q 的算法和列修正拟n e w t o n 算法提出一种 称为c m 逐次列修正算法用来求解稀疏非线性方程组。 在第三章，我们将详细讨论前面所提到的各种算法。在第四章，我们将提出求解大 型稀疏无约束优化的对称三角分划割线算法，这种算法利用了特殊的分划技巧，是有限 差分法和割线法的结合，它在每次迭代中比p o w e l l 和t o i n t 1 9 7 9 i ”】的三角替换法少需 要一个函数估计值数。在第五章，我们将提出另一种算法t 大型稀疏无约束最优化的直 接列分划校正c h o l e s k y 因子算法。此算法以稀疏h e s s e 阵的列的相容分划为基础，并对 其c h o l e s k y 因子相应列进行直接修正。它将王字和冯果忱f 1 9 9 4 1 4 1 】的算法引入蒴疏领 域。 在这篇论文中，舻定义为实数e u c l i d 空间。在该空间下，通常定义内积 = x t y ，且l ( r ”) 定义为所有的实数d x n 矩阵的线性空间我们使用删定义z 2 向量范数 忙| = 。或者和f 2 向量范数相容的任何矩阵范数。在这种意义下，对每一个 5 一类大烈稀疏无约束优化的算法 z 形和a l ( r “) ，有i a x lj i i a f lj i x l f 特别地，我们使用f 定义为p r o u b e n i u s 范数，它也和1 2 向量范数相容。它能通过下式计算： a 幅= j i a - 。旷= t r ( a t a ) = 1 其中， u h 。，) 是在舻上的任意标准正交集而且，我们使用n ( y ，) 定义集 。 毋：忙一y l i o ，s 1 i h ( x ) 一h ( x + ) i is7 i l 。一。+ 忆v x d ( 3 1 2 ) 有时，我们假定日满足较强的l i p s c h i t z 条件； j p 0 ，s t 1 1 h ( 嚣) 一h ( y ) i l 卢| | z 一i | ，v x ，d ( 3 1 ，3 ) 对某些算法，我们假定日满足下列l i p s c h i t z 条件： j 。 0 ，i = 1 ，2 ，一，礼，s t i i ( h ( x ) 一日扫) ) e t | l o i i o g 儿比，y d ( 3 1 4 ) 令。= = ( ：。i ) ，则上式表明： i i h ( x ) 一h ( y ) l l f oj | 。一| | ，v x ，y d ( 3 1 5 ) 7 一类大型稀疏无约束优化的算法 下列引理对考察一个算法的收敛性很有用： 目l 理3 1 1 令z ，。十p d 贝0 如+ p ) 刊。) = z 1 趴。+ 咖出 ( 3 1 6 ) 引理3 1 1 的证明见d e n n i s 和s c h n a b e l 1 9 9 6 ，p7 5 1 嘲 引理3 1 2 令z ，虿d 给定 0 ，存在d 0 ，使得如果归一z | i 0 如果 胪) 是一个实数序列且0 1 时，百不是唯一的由割线方程 确定。这是由于我们有舻个未知量，但只有礼个方程记住目前我们所有的信息是： z ，面，9 ( z ) ，g ( 苗) 和b 我们总想尽可能多得使用这些信息。因此，百不该远离b 令 q 。= 蜃l ( 舻) ：百s = ， 则，我们将取百为b 在q 。上的投影。换句话说，百是下式的唯一解 一r a i n l i b b i f 。 d q _ 8 此问题的解可从下列引理中得到t 引理3 5 1 令b l ( 形) ，8 ，y 舻，s 0 则( 3 5 8 ) 的解是 百：b + ( y - b s ) s t 这个引理的证明可参考d e r m i sa n dm o i _ d 1 9 7 7 1 4 ( 3 5 7 ) ( 3 5 8 ) ( 3 5 9 ) 大连理工大学硕士学位论文 修正( 3 5 9 ) 由b r o y d e n 1 9 6 5 5 ) 给出因为( 3 5 8 ) 的原因，我们说b r o y d e n 修正是 最小变化割线修正。现在我们叙述具有全局策略的b r o y d e n 算法如下： 算法3 5 2 给定。o 郧和非奇异矩阵b o ，在每一步20 ( 1 ) 解b 8 矿= 一夕( 扩) ( 2 ) 令 。b l = 。 = + j 其中驴= 扩或者矿是按全局策略所选的下降方向。 ( 3 ) 检查收敛性。 ( 4 ) 令 y = g ( x + 1 ) 一q ( x 。) ( 5 ) 令 b k + 1 = b k + 垒生群 ( 3 5 l o ) - b r o y d e n 算法有以下优点： ( 1 ) 在每次迭代中函数值估计数只有一个 ( 2 ) 它g 一超线性收敛 b r o y d e n 算法的缺点就是它不具有自修正性，也就是说，伊不仅依赖b b l 而且 它还依赖所有的b ，i = 0 ，1 ，k 1 所以，来自初始步的坏信息可能一直保留到当前 步。这可以从下面的定理中解释t 定理3 5 3 令9 满足假设( 3 1 1 ) ，h ( x ) 满足假设( 3 1 3 ) ，再令g ，8 是由 b r o y d e n 算法产生的。如果 趣) 寄 d ，则 k 1 1b 一h ( z 蹦) 1 1 0 ( 1 ) 如果f r 且整数对噼( g ) ，( r ) 和整数对陋( i ) ，k ( j ) 】相同。其中，数对中 的顺序无关；且( i ) 表示包含v 2 f ( z o ) 的下三角部分的第i 列的组数( 1 k ( i ) p ) 。 推论3 8 3 如果在b 的对角线上没有非零元素，那么在定义b 的对角线上的元 素的方程组中没有替换。 推论3 8 4 在下三角替换算法中，b 的普通非零矩阵元索b l j ，( i j ) 至多依赖 于( 礼一i ) 个其它的矩阵元素。 3 9 稀疏因子分解修