（计算数学专业论文）cgs方法及其光滑化.pdf

摘要 c g s 方法是求解大型非对称线性方程组的一类重要方法，它具有计算量和 存贮量小的优点，但残量范数振荡严重。本文应用极小化光滑技术改进c g s 方 法残量范数的光滑性，提出了求解非对称线性方程组：q m r c g s 方法。 c s c g s 是在c g s 的基础上对其主元素中断问题进行适当改进而得到的一种 方法，也是求解大型非对称线性方程组的一种有效方法，但它具有与c g s 一样 残量范数收敛不规则的缺点，本文针对这一问题提出了m r s c s c g s 方法。 数值试验结果表明这两种新方法不仅改善了原方法的收敛性，而且大大减少 了计算时间。 关键词：大型非对称线性方程组，c g s 方法，c s c g s 方法，q m r 方法，m r s 方法，m r s c s c g s 方法，q m r c g s 方法 a b s t r a c t t h ec g sm e t h o di so n eo f t h ei m p o r t a n tm e t h o df o rs o l v i n gl a r g es p a r s es y s t e m s t h ea m o u n to f c o m p u t a t i o n a lw o r k a n dt h em e m o r y s p a c ea r es m a l l ，b u ti tm a y l e a dt o ar a t h e ri r r e g u l a rc o n v e r g e n c eb e h a v i o u r t h eq m r c g sm e t h o di sp r o p o s e di nt h i s p a p e l t h ec s c g sm e t h o di m p r o v e st h ep r o b l e ma b o u tp i v o tb r e a k i n gd o w no i lt h e b a s i so fc g s ，a n di ti sau s e dm e t h o df o rs o l v i n gl a r g es p a r s es y s t e m sb u ti th a st h e s a m ei r r e g u l a rc o n v e r g e n c eb e h a v i o u ra sc g s t h en e wm e t h o do fm r s c s c g si s p r o p o s e dt od e a lw i t h t h ep r o b l e ma b o v ei nt h ep a p e r n u m e r i c a le x p e r i m e n t si n d i c a t et h a tt h en e wm e t h o d si m p r o v et h ec o n v e r g e n c e p r o p e r t ya n d d i s c r e a s ec o n s i d e r a b l yc o m p u t a t i o nt i m e k e y w o r d s ：c g s m e t h o d ，c s c g sm e t h o d ，q m rm e t h o d ，m r sm e t h o d ，m r s c s c g sm e t h o d ，q m r c g sm e t h o d 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立 进行研究工作所取得的成果。尽我所知，除文中已经注明引用的内容 外，本学位论文的研究成果不包含任何他人享有著作权的内容。对本 论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明 确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其他复制手段保存论文。 作者签名：工塞选 j i 蜘 日期： 2 q q 生! 旦2 5 旦丛丝f 弓、弓p 注释表 用大写字母表示矩阵或线性算子，小写字母表示向量，小写希腊字母表示数。 r “表示碰往实向量空间，r 表示所有”m 实矩阵全体。 x 。和x 7 分别表示向量芏和矩阵的转置。 爿表示”阶实对称矩阵，丑表示爿的第f 个最大或摄小的特征值。爿的特征 对表示为( 五，x ) ，其中工为特征值，z 为相应的特征向量。 d e t ( a ) 表示矩阵a 的行列式。 任何对称矩阵的特征向量均为正交规范化特征向量，所有矩阵或向量范数均 耿为e u c l i d e a n 范数。 ，表示 阶荤侮矩阵。e ，表示f 的第眵0 。 列r f 交规范矩阵9 r 是指满足q q ：，的矩阵。 。上y 表示x 和y 正交，而x 上u r ”7 表示向量z 和u 的各列所张成的子空 吲f 交。 哎”，、”一，是m 个n 维向量，则v = q 如，】表示一个n 。删矩阵，其中 印“”，”一”n r ) 表不由 ”t ，心，v 。 张成的子空间。s p a n ( v l ，v ，) 一表示 5 p a n ( v i ，也，匕) 的正交补。 方程组爿z = b 中4 为维大型稀疏非对称正定矩阵，6 为维非零向量。 南_ 航空航尤人学硕t ：学位论文 第一章绪论 求解大型线。r l ：力私l 组问题是数值代数的个重要研究领域，别它的彻究儿 有晕要的理论意义用i 膨朋价值。计多科学和l 程问题最终1 1 | 转化为求解夫，一线 性方“程纠。 对于求解刈称i i 定的火型线性力程组，共轭梯度( c g ) 法是最有效的方浊 之+ 。c g 方法小身j l 需要j l q ：就能被精确的描述出来，但它却捌有许多好咐r l ： 质，如它具有最优俐- ( 存某+ 给定的k r y l o v 子空间内使残龄最小化) 和短递拊 的特点。 人们试巨i 将( 、g ，j 法扣到般的非对称问题。然而f a b e j 和m a n t e u f l c l1 ，_ 1 文献f 1 1 叫t 证明，1 蚴佝非划称情况r ，任何种方法不r u 能| ：j 时具有最优性_ = | | 短递推两种性质，现仃的迭代方法“般司分为两类。一类是jl 有最优性但小儿 有短递推的方法，此类方i _ _ ：中以g m r e s 2 - i 方法最具代表队。好一一类方法h n 短递推但不具有最优。这类方法如，g c g 方法13 ( 1 1 ，b c g 力法12 1 ，c g s 乃浊， b i c g s t a b 疗；：f “，q m r 方法f f q m r 方法4 “，q m r c g s l a b 乃法1 “，o r i i _ i o d i r 方法i “”等。花第+ 类方法l f lb c g 方法是c g 方法最然的推广。b c ( t 方法是在两个4 用ia 日关的k r y l o v 子空间上应用g a l e r k i n 条件而得到n 。 b c g 疗法伍解决汁彩刘题叶i 仍保持其优势，如文 6 】。 1 9 8 9 年s o l m e v e l d 赴文献【3 ，提出了c g s 方法。已经史c g s 力诎对j 求解非对称大型稀疏线性方程组足非常有效的方法。c g s 山。法足在b c g 力泄j n 勺 基础上刈其残量多项一弋进 ：i f 方丽得到的，因此它具有b c g 乃法的算法简1 1 ) 利 短递推的特点，f i 讣洲j 它义避免了b c g 方法q 、的a 。与向鞋乘积的订算i u j 题，使 得计算量jb c g ，j 洲i _ | i 比人人减少。 列rb c g ，j 。法的一| 嘣i 问题，”j 文献进i j ：了硼：究。b c ( j 乃。法韵两种l i 呐f ： 一种是由于在b ( ( ；迭代- 旷二g a l e r k i n 条件定义的残量多顾j 不存在耐j 、7 t - 中断( 通常称为17 儿豢小断) ：另种中断则是山于隐减的 , a l l c z o s 过棚，扪m 产“i 的( 通常称为l a n c z o s i i 断) 。c g s 方法是在b c g 力泄：n 0j 。础| 二搿剑n q ， 因t l i - , 在c g s 力浊俅”j b ( 1 g 疗浊优t “| ( ) 同时，也具有了b c g 乃法的缺j l ，i ，它 会j “生两 q 川目i 划卜衅决( 、g si j 叫，断问题，最近g u t k n e c h t 抛出j b i o r 瞵 的们去i ”1 ，b r e z i n s k i 刷s a d o k 提的m r z s 方法13 , 1 ，这些，j 、卜要足解决c g s c g sd 法及其光滑化 方法中的精确 , a n c z o s l 断问题，b r e z i n s k i 和r e d i v o z a g l i a i 2 1 敞 0 7 1 l _ l 刈c g s 方法中的近似- fr 惭l _ 题进f r 了词沦。 如果在不发小i o i l c z o s 中断的情况f 产生主元豢l 川析，s a a d i s l 捉；刈j l a n c z o s 过程产。0i 刈角矩阵，采用部分主元素高斯消去法i q - 避免 ：元素i i i 断、 f r e u d 和n a c h t i g a l 川捉了q m r 力 | ：，q m r 方法是通过刚拟最小化原则消、 j 乒儿素。i - 断。撤近i ? , a n k 垌ic h a r t l 挺h 了c s b c g 方法，这种一法主要越通j 跳过残繁多项) 小存f 1 - 的那步j “。卜个2 2 的复合步而得剑的。对c s b ( 1 ( j 儿 法进行平方就褂到了复合步c g s ( c s c g s ) 方法1 9 1 。 l a n c z o si i i 惭很雄解决，目前提l 1 了许多前瞻类型的方法术解决这类中断。a l i f r e u n d i “1 1 ，b r e z i n s k i b i e z i n s k i 和s a d o k i ”1 ，j o u b e r t l l “，p a r l e t t i3 1 i 等都提, q - i 了炎 似的方法。 c g s 方法除j ，l ，断m 邀外，还仃钱量范数振荡阎题，礼：迭代过程，f 现的 残量范数不规州抓荡j 能会破坏迭代过程j 2 生的解这使我们丌始研究耍i 伺 生一个收敛更光滑的b c g 类型的= j ：r 法，使其既保持c g s 力法的收敛速度，x 比c g s 疗法的，鼬i 范敬收敛光滑。1 9 9 2 呵：v a nd e rv o s t 挫了b i c g s t a bj j 法14 i ，1 9 9 6 印l ；o ik k c m a 等人提i t 了g c g s 方法i ，这些力浊1 i f | j 钏刈c g s 玎沙 的饯量范数收敛小胤i j ! | j 问题进行改进。 本文将两利一咒计_ ： 投术q m r 方法p ”i 与m r s 方法f 2 f 1 分刖腑朋j _ - c g s 方法羽i c s c g s 方法，以【致# f 这两种疗法残量范数的光滑性。本文给m 了q m r c g s 力 法干m r s c s ( 1 g s 乃浊。敬值试验表明新方法确实取得了较1 勺效果。 南京航空航天夫学硕十学位论文 2 1 b c g 方法 第二章q m r c g 8 方法 对于求解对称正定的大型线性方程组，c g 方法是最有效的方法之一，因此 人们一直试图将c g 方法推广到般的非对称问题，然而发现在般的非对称情 况下，任何一种方法都不可能同时具有c g 方法的最优性和短递推两种性质。而 在各种推广方法中b c g 方法是c g 方法的最自然的推广，至今b c g 方法在解决许 多问题中都保持其优势。下面给出b c g 算法。 2 1 1 1 3 c g 算法2 0 j 1 ) 选择仞始向量矗， 计算确；6 一a x f ) ，置p 。= r o ， 选择瓦0 ，置芦。= 焉，p l = l ， 2 ) 对于k = l ，2 ，计算 。r = i 、8k ：且 p 一 pk = r k 8k pk “， p 。= 瓦t 声t t i ， o | = 萤2 a p t ， + f2 j a a p 女 , v k + i _ = + 口 p k 。 在b c g 算法中，砭的收敛并不需要实际展示出来，但在计算成和吒时要用 到t 因此必须计算砭，使得工作量增加。另外，b c g 算法中有大量的关于爿7 虿，的 计算，这便大大增加了存贮量和计算量，针对这些问题，1 9 8 9 年s o n n e v e l d 提 出了c g s 方法”， 2 2 o g s 方法 c g s 方法的基本原理是，首先将b c g 方法转化为矩阵多项式，令算法2 1 1 中的7 j ，p ，为 o = 谚，( 一) ， p 。：妒，( 4 ) ， 4g一 墅一弘户 口 c 鱼! 塑璧墨茎垄堂些一 一一 出b c g 厅法知 p ，= 驴。( 爿) 矗+ 。v - 、( a ) r o = ”( 4 ) f ， + 】= 谚，( 爿) 一口。4 渺，( 4 ) = 痧川( 4 ) 得到 ，( f ) = 砬，( r ) + 屈，v ，i ( f ) 谚川( r ) 毒痧，( r ) 一口。r 妒。( r ) 可r r v f r 然后再将多项式平方，而得到c g s 方法t 婴令 f “= 簖( 一) 矗b h 。q 4 - r - i ( a ) r o ， 利用前面的多项式谚( r ) ，。( r ) 求出衙( r ) ，五，( r ) 就得到了c g 5 方法。 2 2 1c g s 算法i ” 1 ) 选择初始向量x 。及焉o ，景p n2 “。h ， 计算v 。= 印。，p f ) 2 矗。r 2 ) 对于k = l ，2 ，计算 仃，一，：焉7 h 一、，口。一。= 笋 吼一| 2 “t 一1 一口一i o t 一1 风= 茚。，成= 争， “ = _ + q ， p 。= h i 十芦( g 女一1 十卢女p 一i ) ， v = 4 p 厂 = 0 一l 一口t 一1 爿( “ 一i + g 1 ) x = x 一1 + a 女一1 ( “k ，1 + q k 一1 ) 。 23q 骶方法的原理 许多迭代法在求解大型线性方程组时会出现残量范数振荡严重的情形，如 c g s 方法、b c g 方法等都存在这样的阃题。针对这种问题文【2 0 】给出了残量光 批慧李，2 黑篇b 下c 面g 雾薹凳鬈氍? 雩譬筹霆黔吣。子捌 以文f 3 中给出的 方法为基础，_ t _ ，唯一l 彤础j “r y 。3 1 ”3 h ：s p a n ( r ( i ，爿r ，一，a k - i t o ) 的基。令 e = ( v 1 v 2 ，v ) ， 其中、：“7 p ，、= 忆一、| l ，, - i p 南京航空航天人学硕士学位论文 则p ；的列形成了砟( ，爿) 的基，对于任意x x 0 + 峨( r o 爿) ，则 工= x 0 十圪：， z 彤( 2 31 ) 由非对称的l a n a z o s 过程，有 爿k = k + l 。，( 2 3 2 ) 其中h 。r ”“”2 是三对角的。与( 2 4 1 ) 中x 对应的残量，为 b a x = r o 一4 圪：= 一圪+ l 爿j ： ：圪+ l ( p o e l 一日k z ) ， ( 23 - 3 ) 其中e = ( 1 o 0 o ) 7 r “。现将第k 步q m r 迭代产生的解定义为 带r = x 1 y k z k ， 其中：。满足 蜘i 一风础。；r a ：驯i np o 巳一峨批 由文 5 中知 l ”蚣丽。 ( 23 4 ) 由算法2 21 知，在迭代进行至第k 步时，p 。，p ，p 构成了h ( ，爿) 的一 组基。令 k = ( 口o p o 一，吼一，p ) ， 且 ( p o g k + l = i 1 。 i反j 假设b c g 算法能够成功地进行到第k 步，在这种情况下，口n 一，口。均不等于 零，且k 的列构成q ( ，爿) 的一组基。由b c g 算法得到 hk = 由于e 的列构成x a r o ，爿) 的基，则可以将x x 0 + x k ( r o 一) 写为 x = x o 十瓦- z 。 z 由( 2 3 5 ) 有 h a x = 一爿瓦手= 一k + j g + l 再：； ( 2 ，3 5 ) h +嚷+吒 i l ， 砭 4 中其 c g s 方法及其光滑化 = k + 瓯+ ( q 一峨：) 】 比较( 23 3 ) 和f 2 2 6 ) j _ f l 容易得到 铲磐她也巩= 卿心一峨：) 1 j ： ( 2 3 7 ) 中等式右边的最小二乘阃题很容易求解。令 = = ( 氧，f ! ，氕) 。， 则有 r ；= m i ；【p ：( 1 一g ，) 2 + p ? ( m a x 批4 ，i k , 捌 r ( 3 l4 ) 若遇到了上面的条件而我们又选择了l x l 步的话，则其残量收敛曲线上会出现一 个尖点。而如果此时选择了2 2 步，就可以跳过这个尖点使收敛曲线更光滑。 为了方便计算，我们把条件( 3 14 ) 转化为 若忆， 选l l 步 否则 若帆，h 选1 1 步 否则选2 2 步 下面给出c s c g s 算法“。 c g s 方法及其光滑化 3 3 1c s c g s 算法1 9 1 1 ) 置风= 召f t ，p ( j = “o = r o ，b o = p o = a p 计算芷= ! ， 对于n = 0 ，l 一计算 o - 广焉b q 。1 = 盯。“。一p ，b 。， c 。i = a q 。， j 肿 = 盯j p ，仃，。一p 。o 肿l ， 知= 慨扎，妒户川1 ：。 2 ) 决定选1x 1 步还是2 2 步 若善。 盯：，此时忆+ ，1 1 2 忆| l ： 则选l l 步 否则计算 臼。= 焉。，1 ，f 。l = 嘲氟l ， 6 ，= d j ，p ：一8 j 。t 西。= 拿。p ：，& 。l = p 。p ：， ，肿 = 盯。一p 。e “ i ，= j i u 一口，l c 。l 讳。= 占。f + l 一壶。c 。i 一。l 心，l i ，：= 恽地+ r 怜( 占以+ i 。) 旭“( 缸一谛洲： 若帮 t 3 ”i p 。：此时忆l l ： h ：1 1 2 t 则选l l 步 否则计算 d 。i = a s 。1 ，= 焉7 d “， 瓦= 盯。f 。p ：一鲒i ， 若艿，誓 仃。；。2 ， 则选1x l 步。 3 ) 具体计算迭代过程 如果是1 1 步，此时实际上是c g s 方法 则计算 口一= 生， 盯 j = ，j ，一盘，( p 。+ c 。l d j ， x 卅1 = x 。+ g 。( 材，+ q 叶l o - ，) ， 南京航空航大人学硕十学位论文 p 。1 = e ：r ，8 。1 = p 。1 p , ? ， “= l 4 - 屈q + 盯 e ，r + l 2 a u j t + 1 ， p 。1 = “。1 矽，( g 。1 盯，+ 屈，p ，) ， b 。l = e 。+ p ，( c c r 。+ 屈b ) t 如果是2 2 步 则计算 o 【n = 。i p j i6 。，。【j 。“= o 。“p i 6 一 v ”= 钎 一掰州b 一口f ，+ i c + 1 ， w + i = r 十1 一口”c f h l 一口m 1 d ，+ i ， ，+ 2 = ，一a a ，( “。+ v 。) + 1 2 l ( ，。1 + ) 】， 工= 工。+ 口。( 甜。+ v 。) 4 - a + i ( f 胖14 - w ) 】， p 。3 = 斥。l m ，屈，= 一，+ 2 p “肿! = l 州+ 声，( v 。+ 屈，p 。+ 屈川g + i ) + 尼川( w 川+ 屈q b ，+ 2 = a p 。+ ! 。 3 2 残量光滑技术 在第一章中简要介绍了q m r 方法，这种方法主要是针对一些迭代方法中的 残量范数振荡严重问题而提出的。它是一种能够将残量进行光滑化的方法。除 了q m r 方法外还有一种可以将残量进行光滑化的方法一m r s 方法。这种方法 是出s c h 6 n a u e r 和w e i s s ”2 4 1 提出的，z h o u 和w a l k e r l 2 5 1 及b r e z i n s k i 和r e d i v o z a g l i - a m l 都给予了进一步的推广和改善。 文 2 6 1 中给出了m r s 方法的讨论。其主要思想是设 是由一种迭代方法 得到的一列向量。用儿= ( 1 - r l , 。) m ，+ 仉矗得到一列 只， ，然后选择仇使其对任慈 的h 满足使得 l b - a ( o - r l , ，) 只。+ 研，) i i ： 最小，即 。：尘亟二! j = ! ! 怫一_ 一虻 其中s 。= 6 一a y 。 显然，对于任意的一慨0 1 恢i i ： 3 2 2m r s 算法 1 ) 令 s o = 矗y o = 2 ) 对于k = 1 ，2 执行 c g s 方法及其光滑化 计算 k 及 叩女= 一j ：一l ( 一矗 令 j 女= s 一i + r j ( r k 一一1 )y k = y k 一1 + ，7 i ( 坼一j 0 一i ) 3 3m r s c s c g s 方法 c s c g s 方法存在着与c g s 方法类似的残量范数不规则的问题，先将m r s 方法应用到c s c g s 中 对于l l 步的情况与在c g s 中应用m r s 方法相同。可令 y 。= ( 1 一r l , ) y 。t + 7 ，x 一选择刁。使得忙一如，i l ：最小。 3 3 1 m r s c s c g s 算法 1 ) 令s 。= “y o = x “0 = “= = o ， x 4 i ，t 王lt 曼2 ，t 为c s c g s 方法中的向量 ( 用1 l 步或2 2 步) 2 ) 对于h = 1 ，2 执行 p ，= i 。一量，l ， “，= “，i + a p 。， ，。h + 只。， ，7 。= “一i i g 。“：“ s ，= t h r l , ，“。，2 y ，1 一，7 。， “。+ _ ( 1 一仉，) “。， ，一( 1 一r l 。) v ， 3 4 数值试验 例3 4 1 在方程组爿x = b 中 a = 21 o2 10 21 o2 b = 选择初始向量为零。 在f 图i 是m r s c s c g s 曲线，i i 是c g s 曲线。 2 1 南京航空航天人学硕士学位论文 】0 5 j p , ij ： 图3 1 例34 1 的运行结果 数值试验表明，m r s c s c g s 方法对，收敛光滑性及收敛速度更优于c g s 等方法。 c g s 方法及其光滑化 第四章总结与展望 c g s 方法是求解大型非对称线性方程组的一类重要方法，它具有收敛速度 快，计算量和存贮量小的优点，但其残量范数振荡严重。 本文主要是对c g s 方法及其在其基础e 建立的c s c g s 方法的残量范数振荡 问题做了研究。将两种残量光滑技术q m r 方法和m r s 方法分别应用到c g s 方法 和c s c g s 方法中，提出了q m r c g s 方法和m r s c s c g s 方法。 数值结果表明，这两种新方法的残量范数的光滑性较原方法确实有所改善。 对于( 焉s 方法的研究是当前国内外的一个热点，本文所涉及的方法只不过 是冰山一角。每种方法都有其优点和不足，并没有对各种问题的“万能之法”， 只能具体问题具体分析。在该领域内，很多问题可以做进一步的研究，例如： 可以将解决c 6 s 方法的中断问题和残量光滑化问题同时结合进行等。因此，该 领域的研究的景是非常广阔的。 南京肮兰i 三航天人学硕十学位论文 参考文献 1 】f a b e rv , m a n t e u f f e l n e c e s s a r y a n ds u f f i c i e n tc o n d i t i o nf o r t h ee x i s t e n c eo f a c o n j u g a t eg r - a d i e n tm e t h o d j s i a mjn u m e ra n a l 19 8 4 2 1 ：315 - 3 3 9 【2 】l a n c z o sc s o l u t i o no f l i n e a re q u a t i o n sb ym i n i m i z e di t e r a t i o n s j jr e sn a t lb u rs t a n d ，1 9 5 2 4 9 ：3 3 5 3 【3 】s o n n e v e l dp c g s ：af a s tl a n c z o s - t y p es o l v e rf o rn o n s y m m e t r i cl i n e a rs y s t e m s j s i a mjs c i c o m p ，1 9 8 9 ，1 0 ：3 6 - 5 2 【4 】4 v a n d e rv o r s tha b i c g s t a b ：af a s ta n ds m o o t h l y c o n v e r g i n gv a r i a n to f b lc g f o rt h es o l u - t i o no f n o n s y m m e t r i c l i n e a rs y s t e m s j s i a mjs c i c o m p ，1 9 9 2 ，1 3 ：6 3 1 6 4 4 【5 】f r e u n drw , n a c h t i g a lnm q m r ：q u a s ir e s i d u a lm e t h o df o rn o n - h e r m i t i o nl i n e a rs y s t e m s j n u m e rm a t h 1 9 9 1 6 0 ：3 15 - 3 3 9 6 】t o n gc h ac o p a r a t i v es t u d yo f p r e c o n d i t i o n e dl a n c z o sm e t h o d sf o rn o n s y m m e t r i cl i n e a rs y s - t e r n s c t h er e ps a n d g l - 8 4 0 2u c 一4 0 4 s a n d i a n a t i o n a ll a b o r a t o r u s ，a l b u q e r q u e ，1 9 9 2 【7 】b a n kre ，c h a nt f ac o m p o s i t es t e pb i - c o n j u g a t eg r a d i e n ta l g o r i t h mf o rs o l v i n gn o n s y m m e t r i cl i n e a rs y s t e m s j n u m e r a l g o r i t h m s ，1 9 9 4 ，7 ：1 7 - 3 3 8 s a a dy _ t h e l a n c z o sb i o r t h o g o n a l i z a t i o na n do t h e r o b l i q u ep r o j e c t i o nm e t h o d s f o rs o l v i n gl a r - g eu n s y m m e t r i cs y s t e m s j s i a mjn u m e r a n a l 1 9 8 2 1 9 ：4 8 5 - 5 0 6 【9 】c h a nte s z e t otac o m p o s i t es t e pc o n j u g a t eg r a d i e n ts q u a r e da l g o r i t h mf o rs o l v i n gn o n s y m - m e t r i cl i n e a rs y s t e m s a l g o r i t h m j n u m e r a l g o r i t h m s ，1 9 9 4 7 ：1 7 - 3 3 【1 0 f r e u n dr w g u t k n e c h tm ha n d n a c h t i g a ln m a n i m p l e m e n t a t i o no f t h el o o k h e a dl a n c z o - sa l g o r i t h mf o rn o n - h e r r n i t i a nm a t r i c e s j ，s l a mjs c ic o m p 1 9 9 2 13 ：1 3 7 1 5 8 11 b r e z i n s k ic ，r e d i v o z a g l i am a n ds a d o khab r e a k d o w n f l e el a n c z o s t y p ea l g o r i t h mf o rs o l y i n gl i n e a rs y s t e m s j n u m e r a l g o r i t h m s ，1 9 9 2 ，6 ：2 9 - 3 8 【12 】b r e z i n s k ic r e d i v o - z a g l i am a n ds a d o k h a v o i d i n gb r e a k - d o w na n dn e a r - b r e a k d o w ni nl a n c z o st y p ea l g o r i t h m s j n u m e r a l g o r i t h m s 1 9 9 1 1 ：2 6 1 - 2 8 4 【13 】b r e z i n s k ic s a d o khl a n c z o s t y p ea l g o r i t h m sf o rs o l v i n gs y s t e m so f l i n e a re q u a t i o n s a p p ln u m e rm a t h