一个新版本的加速超松弛迭代法

文摘

Hadjidimos(1978)提出了一个经典的加速超松弛迭代法(AOR)解决线性方程组,并讨论了它的收敛性条件下的系数矩阵是不可约对角优势,l矩阵,矩阵和持续订单。在这篇文章中,一个新版本的优势提出了方法。一些收敛结果推导当系数矩阵是不可约对角优势,H矩阵、对称正定矩阵l矩阵。新优势关系图法和原始的AOR法。最后,给出了一个算例来说明该方法的效率。

1。介绍

考虑下面的线性系统: 在哪里,给出了,是未知的。系统的形式(1)出现在许多应用,如线性弹性流体动力学和约束二次规划1- - - - - -4]。当系数矩阵的线性系统(1)是大而稀疏,迭代方法对直接推荐方法。为了解决(1)更有效地利用迭代方法,通常,高效的系数矩阵分裂是必需的。例如,经典的雅可比和高斯-赛德尔迭代分割得到的矩阵为其对角线和非对角的部分。

的数值解(1),加速超松弛(AOR)方法引入Hadjidimos (5),是一个泛化的逐次超松弛(SOR)方法。在某些情况下,调整优势比雅可比方法具有更好的收敛速度,乔、高斯-赛德尔,或者SOR方法(5,6]。充分条件收敛的AOR方法已经被许多作者认为包括(6- - - - - -14]。提高收敛速度的优势方法,预先处理的优势(PAOR)方法已经被许多作者认为包括(15- - - - - -21]。尽管维子空间方法(4,22)是一种重要的和有效的迭代技术求解大型稀疏线性系统,因为这些方法是廉价的实现和能够充分利用系数矩阵的稀疏,维子空间方法非常慢甚至无法收敛的系数矩阵(1)通常是极其坏心肠的和高度不确定的。

本文的目的是提出一个新版本的加速超松弛(AOR)方法为线性系统(1),这被称为准加速超松弛(QAOR)方法。我们讨论一些充分条件的收敛QAOR方法当系数矩阵不可约对角优势,矩阵、对称正定矩阵矩阵。

本文的其余部分组织如下。节2QAOR方法推导。节3,一些收敛结果QAOR方法当系数矩阵不可约对角优势,矩阵、对称正定矩阵矩阵。QAOR关系图和优势提出了部分4。最后,在节5给出了一个算例来说明该方法的效率。

2。QAOR方法

介绍QAOR方法,首先,简要回顾经典的AOR方法是必需的。

对于任何分裂,与,基本迭代法求解(1)是 让 在哪里是一个对角矩阵非奇异的判定和和分别是严格上下三角矩阵。那么经典的AOR方法(5定义: 在哪里是一种加速度参数和是一个超松弛参数。它的迭代矩阵是 在哪里和。显然,雅可比迭代矩阵的方法高斯-赛德尔迭代矩阵的方法,逐次超松弛迭代矩阵的(SOR)方法。

事实上,如果我们引入矩阵 然后 因此,我们就能很容易地验证AOR方法可以诱导矩阵分裂。

建立QAOR方法,我们考虑下面的矩阵分解的系数矩阵;也就是说, 然后 基于上述矩阵分解(8),QAOR方法定义如下: 和它的迭代矩阵

QAOR法的AOR法相比,很容易看出QAOR迭代矩阵的方法是类似于AOR方法。基于这一事实,QAOR方法可以保存所有的优点优势的方法。如果,QAOR减少QSOR方法。QSOR方法也被称为KSOR法(23,24]。

接下来,我们将讨论一些充分条件的收敛QAOR方法当系数矩阵不可约对角优势,矩阵、对称正定矩阵矩阵。

3所示。主要结果

当是一个不可约矩阵对角优势较弱,显然,这两个系数矩阵和相应的对角矩阵非奇异的。基于这种情况,我们有如下定理QAOR方法。

定理1。如果是一个不可约矩阵对角优势较弱,那么QAOR方法收敛吗和。

证明。我们假设的特征值的我们有。下面这个特征值的关系是适用的: 通过执行一系列简单的转换,我们有 在哪里 的系数和在(14)在模量小于1。为了证明这是充分必要的证明 如果在哪里和是真实的,,然后第一个不平等(15)等价于 这适用于(在这种情况下,显然,)。自,(16适用于所有真实的当且仅当它适用于。因此,(16)等价于 这是真实的。第二个不平等(15)等价于 出于同样的原因,必须满足。因此,我们有 这也是真实的。也就是说,和,是与非奇异的。因此,。

当是一个矩阵,它遵循与

定理2。如果是一个矩阵和,然后QAOR方法是收敛的。

证明。让。然后 让。然后 显然,我们有 这意味着 当且仅当 是一个单调矩阵。自是一个矩阵,然后是一个单调矩阵。因此,就完成了。

让 当是对称的正定,显然,是满秩。很容易看到 在这种情况下,QAOR方法是收敛的是正定2]。通过简单的计算,我们有 也就是说,QAOR方法是收敛的 是正定的。让的特征值。左边(29日)是正定当且仅当 自和是相似的,那么两个都有相同的特征值。让。如果下面的不平等是满意 然后QAOR方法是收敛的。因此,我们有以下定理。

定理3。假设是对称的正定。让的特征值,,。如果 然后QAOR方法是收敛的。

当是一个矩阵,下面的定理。

定理4。如果是一个矩阵和,那么QAOR方法是收敛的。

证明。假设。根据我们的假设,我们很容易得到 因此,对于迭代矩阵我们有 也就是说,是一个非负矩阵。如果对应的特征向量,我们有什么 相当于 从(37),我们有 很明显,。因此, 结合(38)和(39),我们有 通过简单的操作,我们有 如果,然后 这意味着所以,如果然后QAOR方法也是如此。

进一步,我们有下面的定理。

定理5。让是一个L-matrix和。如果,然后

证明。基于定理4很明显,这是需要证明 让。存在一个非零向量这样 相当于 让 很明显,。自,我们有 这意味着。因此,我们有 也就是说, 这是完成。

一些评价(43)给出如下。(我)很明显,。如果,然后。(2)如果,然后。事实上,我们有 (3) 当且仅当。在这种情况下,(43)我们有 (iv) 当且仅当。

4所示。一个关系图QAOR和优势

基于以上讨论,我们有 让和。因此,我们有 也就是说,当和QAOR方法减少AOR方法。基于这种情况,图1描述之间的关系QAOR方法和优势的方法。

5。数值例子

现在让我们考虑下面的例子来评估QAOR迭代方法的可行性和有效性。假设和系数矩阵(1)是由

所有测试的初始猜测是零。在MATLAB 7.0中执行的测试。在表中1和2,我们谱半径的值列表迭代矩阵的迭代数量(IT),和CPU时间(CPU)的不同的值和当QAOR (QSOR)迭代用于解决线性系统(1)。

从表1和2,迭代数据和CPU时间的QSOR比QAOR较低。也就是说,QAOR迭代并不比QSOR迭代在特定条件下。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项研究是由国家自然科学基金委(不支持。11301009),由河南省科技发展计划(没有。122300410316),河南省自然科学基础部分(没有。13 a110022)。

引用

1. r·s·巴尔加,矩阵迭代分析施普林格,柏林,德国,2000年。
2. d . m .年轻的时候,迭代解大型线性系统、学术出版社,纽约,纽约,美国,1971年。视图:MathSciNet
3. a·伯曼和r . j . Plemons非负矩阵在数学科学、暹罗、费城,宾夕法尼亚州,美国,1994年。
4. y萨阿德,稀疏线性系统的迭代方法PWS发布、波士顿、质量,美国,1996年。
5. a . Hadjidimos“加速超松弛法”,数学的计算,32卷,不。141年,第157 - 149页,1978年。视图:谷歌学术搜索|Zentralblatt数学|MathSciNet
6. g . Avdelas和a . Hadjidimos”中的有关理论和计算结果加速超松弛(AOR)方法,”为了分析Numerique et de L 'approximation理论,9卷,不。1,5 - 10,1980页。视图:谷歌学术搜索|MathSciNet
7. A . k . Yeyios”加速超松弛的收敛的必要条件(AOR)方法,”计算和应用数学杂志》上,26卷,不。3、371 - 373年,1989页。视图:出版商的网站|谷歌学术搜索|MathSciNet
8. z呗,”并行非线性单调收敛速度的优势方法,”计算机和数学与应用程序没有,卷。31日。7日,1 - 8,1996页。视图:出版商的网站|谷歌学术搜索|MathSciNet
9. Z.-Z。巴姨,“并行非线性AOR方法及其收敛性,”计算机和数学与应用程序没有,卷。31日。2,21-31,1996页。视图:出版商的网站|谷歌学术搜索|MathSciNet
10. z呗,”异步multisplitting AOR一类弱非线性方程组的方法,”应用数学和计算,卷98,不。1,49-59,1999页。视图:出版商的网站|谷歌学术搜索|MathSciNet
11. l . Cvetković诉Kostić,“注意收敛的AOR方法,”应用数学和计算,卷194,不。2、394 - 399年,2007页。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. 高z . x和t . z黄”,AOR方法收敛”,应用数学和计算,卷176,不。1,第140 - 134页,2006。视图:出版商的网站|谷歌学术搜索|MathSciNet
13. J.-Y。元,X.-Q。金,“广义AOR方法的收敛性。”应用数学和计算,卷99,不。1,35-46,1999页。视图:出版商的网站|谷歌学术搜索|MathSciNet
14. w·李和裴伟伟。太阳,“比较结果平行multisplitting方法应用AOR方法,”线性代数及其应用,卷331,不。1 - 3、131 - 144年,2001页。视图:出版商的网站|谷歌学术搜索|MathSciNet
15. j . h . Yun”预处理AOR方法的比较结果$l$矩阵”,应用数学和计算,卷218,不。7,3399 - 3413年,2011页。视图:出版商的网站|谷歌学术搜索|MathSciNet
16. 周宏儒。小王和Y.-T。李”,一个新的预处理AOR迭代法l矩阵”,计算和应用数学杂志》上,卷229,不。1,47-53,2009页。视图:出版商的网站|谷歌学术搜索|MathSciNet
17. 吴和t .黄”,修改AOR-type迭代L-matrix线性系统的方法,”ANZIAM日报卷,49号2、281 - 292年,2007页。视图:出版商的网站|谷歌学术搜索|MathSciNet
18. Y.-T。李,C.-X。李,S.-L。吴”的预先处理这些AOR迭代法的改进l矩阵”,计算和应用数学杂志》上,卷206,不。2、656 - 665年,2007页。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. Y.-T。李,C.-X。李,S.-L。吴”,改善AOR一致的线性系统的方法,”应用数学和计算,卷186,不。1,第388 - 379页,2007。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
20. l . Wang和Y.-Z。歌曲“预处理AOR迭代方法$米$矩阵”,计算和应用数学杂志》上,卷226,不。1,第124 - 114页,2009。视图:出版商的网站|谷歌学术搜索|MathSciNet
21. l . m . Wu王,y的歌,“线性系统预处理AOR迭代法”,应用数值数学卷,57号5 - 7,672 - 685年,2007页。视图:出版商的网站|谷歌学术搜索|MathSciNet
22. z呗,”夏普误差范围non-Hermitian线性系统的一些维子空间方法,”应用数学和计算,卷109,不。2 - 3、273 - 285年,2000页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
23. k·优素福,“逐次超松弛法,”数学和统计学杂志》上,8卷,不。2、176 - 184年,2012页。视图:出版商的网站|谷歌学术搜索
24. k·约瑟夫和a . a . Taha,“修改逐次超松弛法,”应用数学和计算,卷219,不。9日,第4613 - 4601页,2013年。视图:出版商的网站|谷歌学术搜索|MathSciNet

版权

版权©2014 Shi-Liang吴和于军刘。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。