新预条件下Gauss-Seidel迭代法及比较定理

第１０卷第３５期２０１０年１２月　科学技术与工程　Ｖ０】．１０　Ｎｏ．３５　Ｄｅｃ．２０１０　１６７１—１８１５（２０１０）３５—８６６３—０３　Ｓｃｉｅｎｃｅ　Ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　⑥２０１０　Ｓｃｉ．Ｔｅｃｈ．Ｅｎｇｎｇ．　新预条件下Ｇａｕｓｓ．Ｓｅｉｄｅｌ迭代法及比较定理　田秋菊　宋岱才　（辽宁石油化工大学基础部，抚顺１１３００１）　摘要提出了一种新预处理矩阵，研究了新预条件下Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法的收敛性，得到了比较性定理；并用数值例子验证　了定理的正确性，揭示了新预条件加快Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法的收敛速度，且优于通常的预条件（，＋　）。　关键词预条件矩阵　Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法　文献标志码比较定理　Ａ　中图法分类号０２４１．６；　求解线性方程组Ａｘ＝ｂ时，通常通过预条件的　方法加速迭代法的收敛性，即在方程组的两端同时　预条件后　Ａ　＝ＰＡ＝（，＋尺　）Ａ＝（，＋Ｒ　）（，一，Ｊ—Ｕ）＝，一，Ｊ—　＋　一　左乘一个非奇异矩阵Ｐ∈Ｒ　，使方程组变为　ＰＡｘ＝Ｐｂ。这方面的研究已有很多结论¨＿４　。对于　（　＋　）＝，一　—　＋尺　一（，　一Ｌ　）＝（，一，　）一　一Ａ　。　（　一　一　）一Ｕ＝　一，Ｊ　一　＝　系数矩阵为　一矩阵来说，它们都能加快Ｇａｕｓｓ—Ｓｅｉ—　ｄｅｌ迭代法的收敛速度。　本文提出一种新的预条件矩阵：　ｌ　其中，　＝，一，　，Ｌ　＝Ｌ一　一Ｒ　，　＝Ｕ，，　，一，Ｊ　分另０　是　（　＋　）的对角，严格下三角矩阵，Ｍ　＝，　一　，Ｊ　，　＝　：Ｕ。　０　１　０　０　０　１　…　……　０　０　０　０　０　０　则在预条件下Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法的迭代矩阵Ｇ　＝　（　—Ｌ　）‘。Ｕ　＝Ｍ２　Ｎ　。　０　０　Ｐ＝ｌ＋Ｒｄ＝　：　●　１预备知识　０　—Ｏ　一　０　・・・　…　一ｃ　１　１０　０　１　１０ｎｌ　０　ｒ上几２　—０　ｎ　１　定义１　Ｅｓ］　如果矩阵Ａ＝（。　）　满足：口　≤０　（ｉ　），Ａ是非奇异的且Ａ　Ｉ＞０，则称４为非奇异的　矩阵。　论述了在一定条件下该预条件Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭　代法为收敛的，同时数值例说明该方法要优于文献　［３］的预条件（，＋尺）。　为讨论方便，假定Ａ＝（％）　是具有单位对角　元素的非奇异Ｍ一矩阵，即Ａ＝　一，Ｊ—Ｕ＝Ｍ—Ｎ，　其中，为单位矩阵，一　，一　分别是矩阵　的严格　下三角和严格上三角矩阵，Ｍ＝，一，Ｊ，Ｎ＝Ｕ。那么　经典Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法的迭代矩阵是Ｇ＝（，一　）～Ｕ＝Ｍ　Ⅳ。　一定义２　对于／＇Ｌ×ｎ实矩阵　，　和Ⅳ，Ａ＝　≥０，Ｎ≥０，则称　＞０，ＩＭ　Ⅳ≥０，　Ⅳ是　的一个分裂，如果　Ａ：Ｍ一Ⅳ是Ａ的正规分裂，如果　则称Ａ＝Ｍ—Ｎ是　的弱正规分裂。　引理１　Ｌ６ｊ设Ａ＝（口　）　∈Ｚ　为非奇异的　一　矩阵且Ｄ∈Ｚ　满足Ｄ≥　那么有　（１）Ａ～，Ｄ　都存在，并且还有Ａ　≥Ｄ～Ｉ＞０；　２０１０年ｌ０月１３日收到　辽宁省教育厅高校科研项目　（２００９Ｔ０６２）资助　第一作者简介：田秋菊（１９７８一），女，辽宁沈阳市人，讲师，研究方　（２）Ｄ∈Ｚ　的每一个特征值都为正值；　（３）ｄｅｔ（Ｄ）≥ｄｅｔ（Ａ）＞０。　弓Ｉ理２　设Ａ＝（ａ　）　∈Ｚ　，贝４　Ａ是　一　向：数值代数。　矩阵的充要条件为　可逆且　一≥０。　８６６４　科学技术与工程　１０卷　引理３　设Ａ＝　１一Ⅳ　＝　一Ⅳ２是Ａ的两　由引理２，引理３可知　个弱正规分裂，且Ａ　≥０，若满足下列条件之一：　Ｐ（Ｅ２　Ｆ　）≤ｐ（　Ｎ）＜１，即Ｐ（Ｍ２　）≤　（１）Ⅳ１≤Ⅳ２；（２）　≥　。，Ⅳ　≥０；（３）　≥　Ｍｉ　，Ｎ　≥ｏ　则有ｐ（Ｍｌ　Ⅳ　）≤ｐ（　Ｎ２）＜１。　２主要结论　定理１设Ａ＝（ｏ　）…是非奇异的　一矩阵，且　满足１一ＯＬ１　ｌ３　ｎ３ｌ、一ＯＬ２ａ２３　０３２一…一ＯＬｎ一１　０　一１，　０　一ｌ　＞０，则有ｐ（　）≤ｐ（Ｍ　Ｎ）＜１。　证明　由Ａ　＝ＰＡ＝（，＋尺　）　，可知　Ａ＝（，＋Ｒ　）一　Ａ　＝（，＋Ｒ　）一　（Ｍ　一Ｎ　）＝（，＋　）一　一（，＋Ｒ　）一　＾　＝Ｅ　一Ｆ　。　其中Ｅ　＝（，＋Ｒ　）～Ｍ　，Ｆ　＝（，＋尺　）　。　Ｍ　＝　一　是对角元素为正的下三角矩阵，且　非对角元素小于（等于）零，所以Ｍ２　≥０，从而　Ｅ　＝［（，＋Ｒ　）　］～：Ｍ２　（，＋Ｒ　）≥０。　Ｅ：ＬＦ　＝Ｍ２１Ｎ　＝Ｍ：ＬＵ　＝Ｍ：ＩＵ≥ｏ，　所以Ａ＝Ｅ　一Ｆ　是一个弱正规分裂。　另一方面，Ａ＝Ｍ一Ⅳ，其中　～＝（，一Ｌ）～＝　（，＋，Ｊ＋　＋…）≥，≥Ｏ，Ｎ＝　≥０从而Ｍ　Ⅳ≥Ｏ，所　以Ａ＝Ｍ一Ⅳ也是Ａ的一个弱正规分裂。　下证：Ｍ　＜－Ｅ２　。　经计算可知，Ｅ　＝（，＋Ｒ　）～Ｍ＝（，一Ｒ　）×　（　一，Ｊ　），在题设条件下为ｚ一矩阵，又Ｅ　＝［（，＋　Ｒ　）　］一＝Ｍ２　（，＋Ｒ　）＞１０，所以Ｅ　＝（，＋　Ｒ　）　Ｍ为非奇异的　一矩阵。　—Ｅ　＝Ｍ一［（，＋　）一　］＝（，一￡）一（，一　Ｒ　）　＝（，一　）一（，一Ｒ　）（　—Ｌ　）＝（，一　）一　（　一　一Ｒ　，　＋Ｒ　Ｌ　’）＝（，一　）一，Ｊ＋，Ｊ　＋尺　，０一　Ｌ　＝，　一　一　＋Ｒ　—Ｒ　Ｌ　＝，　一，Ｊ　＋Ｒ　（，ｎ一　，）一Ｒ　Ｌ　＝，　一　＋Ｒ　，　一　＝，　一　一Ｒ　≥０　（其中　，　＝０）。　即　≥Ｅ　，又显然Ｍ＝，一Ｌ是Ｚ－矩阵，而Ｅ　＝　（，＋Ｒ　）～Ｍ　为非奇异的　一矩阵。所以由引理１　知Ｍ　≤Ｅ　，Ａ是非奇异的　．矩阵；Ⅳ＝　≥０，所以　Ｐ（　Ⅳ）＜１。　定理２　设Ａ＝（口　）　是非奇异的　一矩阵，　Ａ　＝（，＋尺　）Ａ＝Ｍ　一　和Ａ口＝（，＋　）Ａ＝　一　，且满足１一ＯＬｌ口１３　ｎ３１　一ＯＬ２口２３　０３２一…　一ＯＬ　ｌ　ｒ上　１，ｎｒ上ｎ．ｎ一１＞０，１一卢１ａ１３０３ｌ、一　２０２３口３２一…一　卢　一１０　一ｌ，　０　．　一ｌ＞０，０≤ＯＬ　≤卢　，ｉ＝１，２，…，ｎ一１。　则有　Ｐ（　，ｖ口）≤ｐ（　）＜１。　证明Ａ＝（，＋Ｒ　）一　Ａ　＝（，＋Ｒ　）一　Ｍ　一（，＋　Ｒ　）　Ⅳ　＝Ｅ　一Ｆ　，　其中Ｅ　＝（，＋Ｒ　）Ｉ１　，Ｆ　＝（，＋　）Ｉ１Ⅳ　。　同理　Ａ＝（，＋　）～Ａ　＝（，＋　）一　一（，＋　ＲＢ　ＮＢ＝ＥＢ—Ｆ　Ｂｏ　其中　＝（，＋Ｒ　）　，　＝（，＋　）　。　由定理１的证明可知Ａ＝Ｅ　一Ｆ　＝　一　都是Ａ　的弱正规分裂。　下证：　≤Ｆ　。　＝（，＋　）一　＝（，＋　）　＝（，一　）ｕ；　Ｆ　＝（，＋Ｒ　）一　／ｖ　＝（，＋Ｒ　）一　Ｕ　＝（，一　）Ｕ。　所以　一　＝（，一　）　一（，一　）Ｕ＝（Ｒ　一　）Ｕ＝　０　０　０　…　０　０　０　０　…　０　－　●　：　：　０　０　０　…　０　０　ｌ　２　…　１＝ｎｌ２０４１（　１一卢１），　‘ｐ１＝ｎｌ２Ⅱ４１（ＯＬ１一　１）＋ａ２３ｎ４２（　２一卢２），　ｎ—ｌ　（Ｐ一　ｎ　８　（　一卢　）。　由题设条件０≤　≤卢。，ｉ＝１，２，…，ｎ一１可知　一　Ｆ　≤０，即　≤Ｆ　。由引理３可知Ｐ（　）≤　ｐ（Ｅ２　Ｆ　）＜１即ＪＤ（　）≤ｐ（　Ⅳｄ）＜１。　３５期　田秋菊，等：新预条件下Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法及比较定理　表１预条件Ｐ＝（１＋Ｒ　）　Ｐ（Ｍｄ　（０，０）　８６６５　当（ＯＬ１，　２）＝（０，０）时为经典的Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代　法，（ＯＬ　，　）＝（１，１）时为文献［３］中预条件Ｐ＝　（，＋Ｒ）的Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法。如表１所示，得到　）　０．８２６　５　Ｏ．８ｌ６　９　０．８０６　４　０．７８０　９　０．７２５　８　０．６８９　８　０．６０９　４　０．５８５　４　（Ｏ．１．０　２）　预条件Ｐ：（，＋Ｒ　）的Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代法收敛较　快，并且该预条件要优于预条件Ｐ＝（，＋尺）。　参考文献　（０．２，０　４）　（０．４，０．８）　（１，１）　（１．２，１．２）　Ｎｉｋｉ　Ｈ，Ｈａｒａｄａ　Ｋ，Ｍｏｒｉｍｏｔｏ　Ｍ，ｅｔ　ａ１．Ｔｈｅ　ｓｕ￣ｅｙ　ｏｆ　ｐｒｅｃｏｎｄｉｔｉｏｎｅｒｓ　ｕｓｅｄ　ｆｏｒ　ａｃｃｅｌｅｒａｔｉｎｇ　ｔｈｅ　ｒａｔｅ　ｏｆ　ｃｏｎｖｅｒｇｅｎｃｅ　ｉｎ　ｔｈｅ　Ｇｒａｓｓ・－Ｓｅｉｄｅｌ　ｍｅｔｈ・・　（１．４，１．６）　（１．５，１．７）　ｏｄ．Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　ａｎｄ　Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ，２００４；１６５　（５）：５８７—　ｏｏ　２　石艳超，徐安农．预条件Ｇｒａｓｓ—Ｓｅｉｄｅｌ迭代法学报，２００８；２８（３）：２５８　２６Ｏ　桂林电子科技大学　３数值例子　设线性方程组Ａｘ＝ｂ的系数矩阵为　ｌ　１　３　１　＇　３　Ｍｏｒｌｍｏｔｏ　Ｍ，Ｋｏｔａｋｅｍｏｒｉ　Ｈ，Ｋｏｈｎｏ　Ｔ，ｅｔ　ａ１．Ｔｈｅ　Ｇｒａｓｓ—Ｓｅｉｄｅｌ　ｉｔｅｒａ—　ｔｉｏｎ　ｗｉｔｈ　ｐｒｅｃｏｎｄｉｔｉｏｎｃｒ（，＋Ｒ）．Ｉｎｄｕｓｔ　Ａｐｐｌ　Ｍａｔｈ，２００３；（１３）：　４３９—１４４５　４　１　１　ｊ　雷刚，王慧勤．一类新预条件下ＡＯＲ迭代法收敛性的讨论．安　２　徽大学大学学报，２００７；３１（３）：１－－４　１　，＇　Ａ＝　Ｖａｒｇａ　Ｒ　Ｓ．Ｍａｔｒｉｃ　ｉｔｅｒａｔｉｖｅ　ａｎａｌｙｓｉｓ．Ｂｅｒｌｉｎ：Ｐｒｅｎｔｉｃｅ　Ｈａｌｌ　Ｉｎｃ，１９６２　戴１　１　华．矩阵论．北京：科学出版社，２００１：２８３－－２８４　Ｋｏｌｏｔｉｌｉｎａ　Ｙ　Ｌ．Ｔｗｏ—ｓｉｄｅｄ　ｂｏｕｎｄｓ　ｆｏｒ　ｔｈｅ　ｉｎｖｅｒｓｅ　ｏｆ　ａｎ　Ｈ—ｍａｔｒｉｃｅ．Ｌｉｎ　Ａｌｇ　Ａｐｐｌ，１９９５；２５：１１７一ｌ２３　由定义１可知，　是非奇异的　矩阵，在满足条件　１一　１　ｒ上１３０３ｌ、～　２口２３　ｒｚ３２＞０下，得到不同参数下的预　条件Ｇａｕｓｓ—Ｓｅｉｄｅｌ迭代矩阵的谱半径Ｐ（　）。　Ｎａｂｂｅｎ　Ｒ．Ａ　ｎｏｔｅ　ｏｎ　ｃｏｍｐａｒｉｓｏｎ　ｔｈｅｏｒｅｍｓ　ｆｏｒ　ｓｐｌｉｔｔｉｎｇｓ　ａｎｄ　ｍｕｌｔｉ—　ｓｐｌｉｔｔｉｎｇｓ　ｏｆ　Ｈｅｒｍｉｔｉａｎ　ｐｏｓｉｔｉｖｅ　ｄｅｆｉｎｉｔｅ　ｍａｔｒｉｃｅｓ．Ｌｉｎｅａｒ　Ａｌｇｅｂｒａ　Ａｐ—　ｐｌ，１９９６；２３３：６７　８０　Ｐｒｅｃｏｎｄｉｔｉｏｎｅｄ　Ｇａｕｓｓ・Ｓｅｉｄｅｌ　Ｉｔｅｒａｔｉｖｅ　Ｍｅｔｈｏｄ　ａｎｄ　Ｃｏｍｐａｒｉｓｏｎ　Ｔｈｅｏｒｅｍｓ　ＴＩＡＮ　Ｑｉｕ—ｊｎ，ＳＯＮＧ　Ｄａｉ—ｃａｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｌｉａｏｎｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｐｅｔｒｏｌｅｕｍ＆Ｃｈｅｍｉｃａｌ　Ｔｅｃｈｎｏｌｏｇｙ，Ｆｕｓｈｕｎ　１　１３００１，Ｐ．Ｒ．Ｃｈｉｎａ）　［Ａｂｓｔｒａｃｔ］　Ａ　ｎｅｗ　ｐｒｅｃｏｎｄｉｔｉｏｎｅｄ　ｍａｔｒｉｘ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ｔｈｅ　ｎｅｗ　ｐｒｅｃｏｎｄｉｔｉｏｎｅｄ　Ｇａｕｓｓ—Ｓｅｉｄｅｌ　ｉｔｅｒａｔｉｖｅ　ｍｅｔｈｏｄ　ｉｓ　ｄｉｓｃｕｓｓｅｄ，ａｎｄ　ｓｏｍｅ　ｃｏｍｐａｒｉｓｏｎ　ｔｈｅｏｒｅｍｓ　ａｒｅ　ｏｂｔａｉｎｅｄ．Ｔｈｅｎ　ａ　ｎｕｍｅｒｉｃａｌ　ｅｘａｍｐｌｅ　ｉｓ　ｕｓｅｄ　ｔｏ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈｅ　ｆｅａｓｉｂｉｌｉｔｙ，ｅｘｐｌａｉｎｉｎｇ　ｐｒｅｃｏｎｄｉｔｉｏｎ　ｉｔｅｒａｔｉｖｅ　ｍｅｔｈｏｄ　ａｃｃｅｌｅｒａｔｅｓ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　Ｇａｕｓｓ—Ｓｅｉｄｅｌ　ｉｔ—　ｅｒａｔｉｖｅ　ｍｅｔｈｏｄ　ａｎｄ　ｉｓ　ｂｅｔｔｅｒ　ｔｈａｎ（Ｉ＋Ｒ）．　［Ｋｅｙ　ｗｏｒｄｓ］ｐｒｅｃｏｎｄｉｔｉｏｎｅｄ　ｍａｔｉｒｘ　Ｇａｕｓｓ—Ｓｅｉｄｅｌ　ｉｔｅｒａｔｉｖｅ　ｍｅｔｈｏｄ　ｃｏｍｐａｒｉｓｏｎ　ｔｈｅｏｒｅｍ