（计算数学专业论文）线性方程组迭代法的若干问题.pdf

中文摘要 线性方程组毂隶解往往在许多科学工程以及其他学科的计算问题中处于核 心地位而迭代法正是解决该类问题最常用的有效的方法 在求解线性方程组的迭代法的1 8 0 多年的发展历史过程，产生了众多不同 的迭代方法经典的迭代法，例如j a c o b i 迭代法g a u s s - s e i d e l 迭代法超松弛 ( s o r ) 迭代法，都足h a d j i d i m o s 在1 9 7 8 年所提出的加速超松弛( a o r ) 迭代法 的特例 在这篇学位论文中，我们考虑了三个与求解线性方程组相关的问题，它们分 别是t 求解亏秩最小二乘问题的块加速超松弛迭代法； 求解奇异p - 循环线性方程组的块加速超松弛迭代法； 广义的关于预处理线性方程组的支撑理论 众所周知，对于非奇异的线性方程组。即该方程组的系数矩阵a 是可逆的。 此时求解该方程组的迭代法收敛的充分必要条件是迭代矩阵的谱半径严格小于 1 然而当线性方程组奇异时，我们只能要求迭代法半收敛 首先，我们把求解线性方程组的块加速超松弛迭代法应用于求解亏秩线性方 程组的最小范数最i 、- - 乘解，其中线性方程组的系数矩阵a 是秩为k 的m n 复矩阵我们证明了a o r 和j o r ( 外推j a c o b i ) 方法半收敛的一些充分必要条 件，并且进一步讨论了由原系数矩阵a 扩充面得的新的系数矩阵的不同分裂所 导出的a o r 迭代法的半收敛性，同时给出了最优参数使得a o r 迭代法达到最 快的收敛速度 其次，我们研究了求解系数矩阵为奇异p - 循环矩阵的线性方程组的块加速 超松弛迭代法的半收敛性在讨论半收敛性之前，我们给出了块a o r 迭代矩阵 和相应的块j a c o b i 迭代矩阵的特征元素之间的一些基本性质，这些性质在我们 的半收敛性分析过程中起着十分重要的作用利用块a o r 迭代矩阵和相应的块 j a c o b i 迭代矩阵的特征值之间所存在的关系，我们证明了求解奇异p _ 循环线性 方程组的块a o r 迭代法半收敛的一些充分条件 预处理是用来加速迭代法收敛的一个重要手段值得注意的是，经典的求解 线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线 性方程组的迭代法换句话来说，原线性方程组的松弛迭代法等价于预处理之后 的方程组的定点迭代法 谱条件数足反映顶处理因子性态是否良好的个有效指标在估计特征值和 摘要 条件数的界的研究领域，虽然已经有了很多的研究成果，但是支持理论还是一个 全新的概念支撑理论是一个用于分析预处理方程组的最大( 或最小) 特征值和 条件数的代数架构，它最初产生于对称正定的线性方程组 最后，我们将适用于对称正定矩阵的支撑理论推广到一般的矩阵( 包括不定 的和非对称的矩阵) 在回顾了广义支撑数的概念以及它是如何用来估计矩阵对 ，b ) 的广义奇异值和条件数的界之后，我们证明了广义支撵数的一系列基本的 代数性质，并且给出了用于分析低秩的预处理因子以及关于s c h u r 补和k r o n e c k e r 积的一些重要的结论和技巧 关键词；奇异线性方程组；迭代法；a o r 方法；j o r 方法；亏秩最r j 、- - 乘 问题；半收敛性；最优参数；p 循环矩阵；相容次序矩阵；预处理；矩阵对； 特征界；条件数；广义奇异值；支撑数 a b s t r a c t t h es o l u t i o no fl i n e a rs y s t e m sa x = bi sa tt h eh e a r to fm a n yc o m p u t a t i o n s i ns c i e n c e , e n g i n e e r i n g ，a n do t h e rd i s c i p l i n e s i t e r a t i v em e t h o d sa r eo f t e nt h e m o s te f f i c i e n tm e a l mt os o l v es u c hs y s t e m s i t e r a t i v em e t h o d sf o rs o l v i n gl i n e a ra y s t e r a aa l em o r et h a n1 8 0y e a r so l d m a n yd i 矗e r e n ti t e r a t i r em e t h o d sh a v eb e e nd e v e l o p e d t h ec l a s s i c a li t e r a t i v e m e t h o d s ，s u c ha sj a c o b im e t h o d ，g a u s s - s e i d e lm e t h o da n ds u c c e s s i v eo v e r r e l a x - a t i o n ( s o r ) m e t h o d ，a r ea l ls p e c i a lc a s e so fa c c e l e r a t e do v e r r e x a l a t i o n ( a o r ) m e t h o dw h i c hp r o p o s o db yh a d j i d i m 0 6i n1 9 7 8 t h i st h e s i sc o n t a i n st h r e et o p i c si nt h ei t e r a t i v em e t h o df o rl i n e a rs y s t e m s t h e ya r er e s p e c t i v e l y ： b l o c ka o ri t e r a t i v em e t h o df o rr a n kd e f i c i e n tl e a s ts q u a r e sp r o b l e m s ； b l o c ka o rm e t h o df o rs i n g u l a rp - c y c l i cm a t r i c e s ； g e n e r a l i z a t i o no fs u p p o r tt h e o r yf o rp r e c o n d i t i o n i n g i t i sw e l lk n o w nt h a t ，f o rn o n s i n g u l a rs y s t e m sw h e r eaj 8i n v e r t i b l e ，t h e i t e r a t i v e m e t h o d c o n v e r g e s i f a n d o n l y i f t h es p e c t r a lr a d i u s o f t h e i t e r a t i o n m a t r i x i ss t r i c t l yl e s st h a n1 晒翻t h es y s t e m sa r es i n g u l a r o n er e q u i r e so n l yt h e s e m i e o n v e r g e n c eo ft h ei t e r a t i v em e t h o d f i r s t l y , w ea p p l yb l o c ka o rm e t h o dt ol i n dt h el e a s ts q u a r es o l u t i o no f m i n i m a ln o r n lt ot h er a n kd e f i c i e n tl i n e a rs y s t e m sw h e r eai sa c o m p l e xm nm a t r i xw j t hr a n kk w ep r o v es o m en e c 髑s a f va n d8 u 伍c i e n tc o n d i t i o n sf o r s o m i c o n v e r g e n c eo ft h ea o ra n dj o ri t e r a t i v em e t h o d s m o r e o v e r w em a k ea f u r t h e rs t u d yo ft h es e m i e o n v e r g e n c eo ft h ea o ri t e r a t l y em e t h o d si n d u c e db y s o m e 出f f e r e n ts p l i t t i n g so ft h ea u g m e n t e dc o e f f i c i e n tm a t f i xo fa t h eo p t i m u m p a r a m e t e r sa n dt h ea s s o c m t e dc o n v e r g e n c ef a c t o ra r ed e r i v e d s e c o n d l y , w ed i s c u s st h es e m i c o n v e r g e n c eo ft h eb l o c ka o rm e t h o df o rs o l v - i n gs i n g u l a rl i n e a rs y s t e m sw i t hp - c y c l i cm a t r i c e s s o m eb a s i cf a c t sa b o u tt h e e i g e n e l e m e n t sb e t w e e nt h eb l o c ka o ri t e r a t i o nm a t r i xa n da s s o c i a t e db l o c kj 扣 c o b ii t e r a t i o nm a t r i xa r eg i v e nb e f o r et h eg e n e r a lp - c y c l i cs i n g u l a rs y s t e m sa r e d i s c l m s e d t h er e l a t i o n s h i p sb e t w e e nt h ee i g e n v a l u e so fj a c o b ii t e r a t i o nm a t r i x a n dt h eb l o c ka o ri t e r a t i o nm a t r i xm a k eav e r yi m p o r t a n tr o l ei no u ra n a l y s i s t h e nw ep r o v es o m e8 u 伍c i e n tc o n d i t i o n sf o rt h es e m i c o n v e r g e n c eo ft h eb l o c k a o rm e t h o d a b s t r a c t p r e c o n d i t i o n i n gi ss tt e c h n i q u ef o ra c c e l e r a t i n gt h ec o n v e r g e n c eo fa ni t e r a t i v e m e t h o d a ni n t e r e s t i n go b s e r v a t i o ni st h a tt h ec l a s s i c a li t e r a t i v em e t h o d sc a na 1 1 b ev i e w e da si n s t a n c e so fa np r e c o n d i t i o n e ds y s t e mw i t hd i f i e r e n tp r e c o n d i t i o n e r s i no t h e rw o r d s ，ar e l a x a t i o ns c h e m ei se q u i v a l e n tt os tf i x e d - p o i n ti t e r a t i o no na p r e c o n d i t i o n e ds y s t e m t h es p e c t r a lc o n d i t i o nn u m b e ri sau s e f u li n d i c a t o ro ft h eq u a l i t yo fs tp r e - c o n d i t i o n e r m u c hw o r kh a sb e e nd o n ei nt h ef i e i do fb o u n d i n gd g e n v a l u e sa n d c o n d i t i o nn u m b e r s ，b u tt h es u p p o r tt h e o r yi san e wc o n c e p t i o n s u p p o r tt h e o r y i sam a t h e m a t i c a lf r a n l e w o r kt oa n a l y z ee x t r e m ee i g e n v a l u e sa n dc o n d i t i o nh u m - b e r so fp r e c o n d i t i o n e ds y s t e m sa n di sd e v e l o p e dw i t hs y m m e t r i cp o s i t i v ed e f i n i t e ( s p d ) s y s t e m sa tf i r s t f i n a l l y , w ee x t e n dt h es u p p o r tt h e o r yo fs y m m e t r i cp o s i t i v ed e f i n i t em a t r i c e s t og e n e r a l ( i n c l u d i n gi n d e f i n i t ea n dn o n s y m m e t r i c ) m a t r i c e s a f t e rr e v i e w i n gt h e c o n c e p to fg e n e r a l i z e ds u p p o r tn u m b e ra n dd e s c r i b i n gh o wi tc a nh eu s e dt ob o u n d t h eg e n e r a l i z e ds i n g u h rv a l u e sa n dc o n d i t i o nn u m b e rf o ram a t r i xp e n c i l ( a ，b ) ， w ep r o v i d eac o l l e c t i o no ff u n d a m e n t a la l g e b r a i cp r o p e r t i e so fg e n e r a l i z e ds u p p o r t n u m b e r s i sf o l l o w e dw i t ho n rm o s ti m p o r t a n ts e to ft o o l sa n dt e c h n i q u ef o r a n a l y z i n gl o wr a n kp r e c o n d i t i o n e r s ，s c h u rc o m p l e m e n t sa n dk r o n e c k e rp r o d u c t s k e y w o r d s ：s i n g u l a rl i n e a rs y s t e m s ；i t e r a t i v em e t h o d s ；a o rm e t h o d ；j o r m e t h o d ；r a n kd e f i c i e n tl e a s ts q u a r e sp r o b l e m s ；s e m i e o n v e r g e n c o ；0 p t i m u mp a - r a m e t e r s ；p - c y c l i cm a t r i x ；c o n s i s t e n t l yo r d e r e dm a t r i x = ；p r e c o n d i t i o n i n g ；m a t r i x p e n c i l ；e i g e n v a l u eb o u n d s ；c o n d i t i o nn u m b e r ；g e n e r 删s i n g u l a rv a l u e ；s u p - p o r tn u m b e r 学位论文独创性声明 本人郑重声明t 1 坚持以“求实，刨新”的科学精神从事研究工作 2 本论文是我个人在导师指导下进行的研究工作和取得的研究成果 3 本论文中除引文外，所有实验，数据和有关材料均是真实的 4 本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或 撰写过的研究成果 5 其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意 作者签名 日 期 学位论文使用授权声明 本人完全了解南京师范大学有关保留，使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版；有权将 学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查询；有权将 学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出 版保密的学位论文在解密后适用本规定 作者签名； 日期： a c k n o w l e d g e m e n t s f o r e m o s ta n df o r e v e r 1w o u l di i k et oc x p r 目sm ys i n c e r e s tg r a t i t u d et op t o - f e s s o ry o n g z h o n gs o n g ，m ys u p e r v i s o r ，f o rh i sg u i d a n c ea n dh e l p ，c o n s t a n te n - c o u r a g e m c n ta n ds u p p o r tt h r o u g h o u tm yg r a d u a t es t u d i e sa n dr e s e a r c h h i 8 m e t i c u l o u ss c h o l a r s h i pi nt h es c i e n t i f i cr e s e a r c hh a sa9 0 0 di n f l u e n c eo nm ea n d ih a v el e a r n tm u c hf r o mh i m h j 8i n v a l u a b l et r u s ta n ds u p p o r th a v eb e e no f u t t e r m o s ti m p o r t a n c ef o rt h ed e v e l o p m e n to ft h er e s u l t sp r e s e n t e di nt h i st h e s i s 1w o u l dl i k et ot a k et h i so p p o r t u n i t yt ot h a n kp r o f e s s o ry o n g l i nc h e nf o rh i s c f l l ea n dh e l pd u r i n gm ys t u d y i n ga tn a n j i n gn o r m a lu n i v e r s i t y h i sp r o f o u n d k n o w l e d g eo nn u m e r i c a la l g e b r aa n dp r o f i c i e n tt e c h n i q u ei m p r e s so nm ed e e p l y s p e c i mt h a n k sa r ed u et od r l iw a n g h e rb e n e f i c i a la d v i c ea n di d e a sh a v e g i v e i lm eg r e a th e l p ，e s p e c i a l l yo i lt h es e m i c o n v e r g e n c ea n a l y s i so fa o rm e t h o d f o rs i n g u l a rp - c y c l i cl i n e a rs y s t e m s m o r e o v e r ，m a n yo t h e r ss h o u l db ea l s oa p p r e c i a t e ds i n c e r e l yf o rt h e i rs e l f l e s s h e l p t h e ya r ep r o f e s s o r sj i n r uc h e n ，z h i r e ns u n ，w e n y us u n ，q 血砸d u ，m i n g - s h e n gy a n g ，d o c t o r sy u s h u nw a n g ，x i nc h c n ，q i n g h o n gl i ，h o n gl i ua n d8 0 o n f i n a l i y ia mg r a t e f u lt om yf a m i l yf o rt h e i re n d l e s sl o v e ，w h i c hh a sb e e n b o r n ei nm ym i n dd e e p l y ，a n db e s t i r sm ea ta n yt i m e y a n l ih u a n g a tn a n j i n gn o r m a lu n i v e r s i t y c h a p t e r1 i n t r o d u c t i o n n u m e r i c a ll i n e a ra l g e b r ai sa l le x c i t i n gf i e l do fr e s e a r c ha n dm u c ho ft h i s r e s e a r c hh a sb e e nt r i g g e r e db yt h ei m p o r t a n tp r o b l e mo fs o l v i n gf i n e a rs y s t e m s m a n ys c i e n t i f i ca n de n g i n e e r i n gp r o b l e m sl e a dt ot h er e q u i r e m e n tt os o l v el i n e a r s y s t e m so fe q u a t i o n sa sp a r to ft h ec o m p u t a t i o n s ， c o n s i d e rt h es o t u t i o no fl i n e a rs y s t e m so ft h ef o r m a x = b ( 1 0 1 ) w h e r e a i s a n n n m a t r i x a n d b o t h z a n dba r e n 1v e c t o r s o fs p e c i a l i n t e r e s t i st h ec a s cw h e r eai sl a r g ea n ds p a r s e s y s t e m so ft h i ss o r t8 d s ef r e q u e n t l yi n m a n ya p p l i c a t i o n ss u c ha se l e c t r i c a ln e t w o r k s d i f f n s i o na n d s t r u c t u r a lm e c h a n i c s ( a 文e l s s o n ( 1 9 9 4 ) 1 3 1 ) ， 7 1 1 1 et e r m8 p a r s ea b o v er e f e r st ot h er e l a t i v en u m b e ro fu o n - z o r e si nt h e m a t r i xa a nn nm a t r i xai sc o n s i d e r e dt ob es p a r s ei fah a so n l y0n ) n o n - z o r ee n t r i e s i nt h i sc a s e ，t h em a j o r i t yo ft h ee n t r i e si nt h em a t r i xa r ez o r e s ， w h i c hd on o th a v e t ob ee x p l i c i t l ys t o r e d a nn nd e n s em a t r i xh a sq ( 舻) n o n y _ a 撂o o n eo ft h eg o a l 8o fd e a l i n gw i t hs p a r s em a t r i c e si st om a k ee f f i c i e n t t l s oo ft h es p a r s i t yi no r d e rt om i n i m i z es t o r a g et h r o u g h o u tt h ec o m p u t a t i o n s ， a sw e l la st om i n i m i z et h er e q u i r e dn u m b e ro fo p e r a t i o n s s p a r s el i n e a rs y s t e m s a r eo f t e ns o l v e du s i n gd i f f e r e n tc o m p u t a t i o n a lt e c h n i q u e sf r o mt h o s ee m p l o y e dt o s o l v ed e n s es y s t e m s t h et e r m a r y ev a r i e sw i t hr e s p e c tt ot h ec u r r e n tg e n e r a t i o no fc o m p u t e r s ， a n dw i t ht h es p a r s i t yo ft h es y s t e m ad e n s en ns y s t e mr e q u i r e sn ( 舻) s t o r a g e v s o 国) f o ras p a r s em a t r i xo ft h e 昭m eo r d e r n o n e t h e l e s s ，s o m eg e n e r a l i z a t i o n s c a l lb ei n a d ew i t hr e s p e c tt ot h es i z eo ff e a s i b l el i n e a rs y s t e m s w h e r ea to i l e t i m ef 1 9 6 0 s ) d e n s el i n e a rs y s t e m sw i t hn 1 0 0w e r ec o n s i d e r e dl a r g 岛s u c h s y s t e m sc a nb es o l v e de a s i l yi n1 9 9 0 s a n di n1 9 9 0 s ，d e n s el i n e a rs y s t e m sw i t h 件 加，0 0 0 ，a n ds p a r s el i n e a rs y s t e m s i ，i t h ，l 1 0 0 ，0 0 0a r ec o n s i d e r e dl a r g e b ym o s tc o m p u t a t i o n a ls c i e n t i s t s a n dnc o n t i n u e st og r o w a ss y s t e m sw i t h n = 1 0 。0 0 0b e c o m et h en o r m ，t h ed e s i r ef o rm o r er e s o l u t i o na n dm o r ea c c u r a t e s i m u l a t i o n sw i l lp u s hnt ob e c o m el a r g e ra n dl a r g e r t h e r ea r et w ob r o a dc a t e g o r i e so fm e t h o d sf o rs o l v i n gl i n e a rs y s t e m s ：d i r e c t a n di r e r a t i v e 。 1 2 ad i r e c tm e t h o df o rs o l v i n gt h es y s t e mo fe q u a t i o n s ( 1 0 1 ) i sa n ym e t h o d t h a tp r o d u c e st h es o l u t i o n a f t e raf i n i t en u m b e ro fo p e r a t i o n s a ne x a m p l eo f ad i r e c tm e t h o di su s i n gg a u s s i a ne l i m i n a t i o nt of a c t o tai n t om a t r i c la n du w h e r eli sl o w e rt r i a n g u l a ra n dui su p p e rt r i a n g u l a r ，t h e ns o l v i n gt h et r i a n g u l a r s y s t e m sb yf c l r w a r da n db a c ks u b e t i t u t i o n d i r o c tm e t h o d sa r et y p i c a l l yp r e f e r r e d f o rd e n s el i n e a rs y s t e m s t h ep r o b l e mw i t hd i r e c tm e t h o d sf o r ”s y s t e m si 8 t h a tt h ea m o u n to fc o m p u t a t i o n a le f f o r ta n ds t o r a g er e q u i r e dc a nb ep r o h i b i t i v e a na l t e r n a t i v et od i r e c tm e t h o d so fs o l u t i o na x ei t e r a t i v em e t h o d s ，w h i c h i n v o l v et h ec o n s t r u c t i o no fas e q u e n c ef z ) ，o fa p p r o x i m a t i o n st ot h es o l u t i o nz ， f o rw h i c hz “) z i ne a r l i e rt i m e s i t e r a t i v em e t h o d sw e r eo f t e ns p e c i a l - p u r p o s e i nn a t u r e t h e yw e r ed e v e l o p e dw i t hc e r t a i na p p l i c a t i o n si nm i n d a n dt h e i r e f f i c i e n c yr e l i e do nm a n yp r o b l e m - d e p e n d e n tp a r a m e t e r s u n t i lr e c e n t l y , d i r e c t s o l u t i o nm e t h o d sa r es t i l lo f t e np r e f e r r e dt oi t e r a t i v em e t h o d si nr e a la p p l i c a - t i o n sb e c a u s eo ft h e i rr o b n s t n e 目a n dp r e d i c t a b l eb e h a v i o r h o w e v e r ，f o rs o l v i n g g e n e r a l ，l a r g es p a r s el i n e a r 删b e l n s ，i t e r a t i v em e t h o d sh a v eb e e ng a i n i n gp o p u - l a r i t yi nm a n ya r e a so f8 c i e n t i f i cc o m p u t i n gb e c a u s et h e ya x ee a s i e rt oi m p l e m e n t e f f i c i e n t l yo nh i g h - p e r f e r m a n c ec o m p u t e 璐t h a nd i r e c tm e t h o d s i t e r a t i v em e t h o d sf o rs o l v i n gl i n e a rs y s t e m sa r em o r et h a n1 8 0y e a r so l d m a n yd i f f e r e n ti t e r a t i v em e t h o d sh a v eb e e nd e v e l o p e d t h ef i r s ti t e r a t i v em e t h o d i sd u et oc f g a u s 8i n1 8 2 3i no n eo fh i sl e t t e r s ( h a c k b n s c h ( 1 9 9 4 ) 1 2 7 i ) h e a p p l i e di t e r a t i v em e t h o dt os o l v et h ee q u a t i o n sa r i s i n gf r o mt h el e a s ts q u a r e m e t h o d a n dp o s s i b l yt h em o s tb a s i ci t e r a t i v em e t h o di st h ej a c o b im e t h o d w h i c hp r o p o s e di n1 8 4 5 ，d e i i n e db yz ( + 1 ) = x ( o d - 1 ( a z c 0 + 6 ) ，w h c r ed i st h e m a t r i xc o n t a i n i n go n l yt h em a i nd i a g o n a lo fa i n1 8 7 4 p l s e i d e l as t u d e n to f j a c o b i u s e di t e r a t i v em e t h o d st os o l v eg e n e r a ll i n e a re q u a t i o n s a n dt h eg 口泌s s e i d e li t e r a t i v em e t h o dw a st h es t a r t i n gp o i n tf o rt h es u c c e s s i v eo v e r r e l a x a t i o n ( s o r 、m e t h o dw h i c hd o m i n a t e dm u c ho ft h el i t e r a t u r eo ni t e r a t i v em e t h o d sf o r a b i gp a r to ft h e s e c o n dh a l f o ft h e2 0c e n t u r y t h es o rm e t h o d w h i c hi n c r e a s e d t h es p e e do fc o n v e r g e n c ew i t hap a r a m e t e r ，w a sf o r m a l l ye s t a b l i s h e db yd m y o u n gi n1 9 5 0 a n di n1 9 7 8 ，a h a d j i d i m 0 6f i r s ts u g g e s t e das i m p l eb u tp o w e r f u l s c h e m ew i t ht w op a r a m e t e r su n d e rt h en a m eo ft h ea c c e l e r a t e do v e r r e l a x a t i o n ( a o r ) n ew e l lk n o w nc l a s s i c a lj a c o b im e t h o d g a t t s s - s e i d e lm e t h o da n dt h e s o rm e t h o da l lc a nb ev i e w e da st h es p e c i a tc a s e so ft h ea o rm e t h o d t h ec o n v e r g e n c ea n dt h ea p p l i c a t i o n so fi t e r a t i v em c t h o d sf o rs o l i n gt h e n o n s i g u l a rl i n e a rs y s t e m sh a v eb e e ni n v e s t i g a t e di nal a r g en u m b e ro fp a p e m a n db o o k s c u r r e n t l y , t h er e s e a r c ho nt h ei t e r a t i v em e t h o d sf o rs o l v i n gs i n g u l a r 3 l i n e a rs y s t e m sh a sg o tm o r ea t t e n t i o nb e c a u s eo ft h ep r a c t i c a la p p l i c a t i o n s t h e a o rm e t h o di n v e s t i g a t e di nc h a p t e r3o ft h i st h e s i si sa l s oa p p l i e dt os o l v er a n k d e f i c i e n tl i n e a rs y s t e m s s i l i c e1 a r g el i n e a rs y s t e m sm a r e q u i r ei n t e s i v ec o m p u t a t i o n a lr e s o l l r c c st o s o l v e ，i ti si m p o r t a n tt ot a k ea d v a n t a g eo fa n ys p e c i a li n f o r m a t i o na b o u tt h e o d e m c i e n tm a t r i c e st h a ti sa v a i l b l e ，c o n s e q u e n