预先处理这些Multisplitting和施瓦兹的线性互补问题的方法

文摘

提出的预调节器Hadjidimos et al .(2003)可以提高收敛速度的经典迭代方法解决线性系统。在本文中,我们扩展这个预调节器来解决其系数矩阵是线性互补问题米矩阵或H矩阵和multisplitting和施瓦兹的方法。给出了收敛性定理。数值实验表明,该方法是有效的。

1。介绍

许多科学和工程问题通常诱导线性互补问题(LCP):找到一个这样 在哪里是一个给定的矩阵和是一个向量。有必要建立一个有效的算法来解决互补问题。互补问题的数值方法两个主要类型,直接和迭代的方法。已经有大量的工作在线性互补问题的解决([1- - - - - -4)等),提出了可行的,连结控制协定的关键技术。最近一些并行multisplitting迭代方法求解大型稀疏线性互补问题提出([5- - - - - -11),等等)。这些方法都是基于系统的几个分裂矩阵和构造一个合适的解决方案的加权组合的次线性互补问题。

为大型稀疏线性互补问题,一些加速modulus-based矩阵分裂迭代方法和同步两级multisplitting modulus-based迭代方法构造(7,11]。数值结果表明,这些方法更有效。

许多研究者研究了预调节器应用于线性系统 所以相应的迭代方法,如雅可比或GS,收敛速度比经典的。Hadjidimos et al。12考虑以下预调节器: 在哪里用常量。

考虑

在(3),让;是一个预调节器由Milaszewicz [13]。它消除了第一列的元素对角线以下。文献[12]表明,新修改的原预调节器可以提高和改进经典的迭代方法的收敛率(雅可比、GS等)。

摘要multisplitting技术,我们将延长预调节器解决线性互补问题(1),提出了一种新的multisplitting和施瓦兹的方法。新方法是平行的,具有较高的计算效率。

节2,提出了一些新方法的预赛。multisplitting和施瓦兹方法部分3。给出了收敛性分析4。部分5给出了数值试验结果。

2。预赛

首先,我们简要描述符号。在和的关系表示自然组件部分排序。此外,对于,我们写如果。一个满秩矩阵称为矩阵,如果为和。或者满秩矩阵被称为矩阵,如果,,。它的比较矩阵被定义为和。据说是一个矩阵如果是一个矩阵。为了简化符号,我们可以假设。

引理1(见[2])。让是一个矩阵,让的解决方案(1)。(1)如果,然后因此。(2)如果,然后的解决方案(1)。

如果问题(1)有一个非零解,至少存在一个索引,。在本文中,我们假设。由引理1,我们有以下的结论。

引理2(见[14])。让是一个矩阵,,。如果,然后下面的线性互补问题 相当于问题(1)。

引理3(见[15])。让和为。是一个矩阵当且仅当存在一个积极的向量这样。

定义4(见[16])。(1)分裂被称为矩阵的正则分裂吗如果和。
(2)分裂称为分裂的矩阵如果是一个矩阵和。
(3)分裂称为兼容矩阵分裂如果。

引理5(见[16])。让是两个经常分裂,在那里。(1)如果,然后 (2)如果,然后
由引理5,我们有以下引理。

引理6。让是两个分裂的, 如果,然后。

引理7(见[14])。如果是一个矩阵,然后是一个矩阵和也是一个矩阵。

引理8(见[15])。 是一个非奇异的矩阵当且仅当所有的主要未成年人是积极的。

由(4),我们有

定义如下矩阵:

考虑以下剥片(12]:

定义以下与上述分裂矩阵:(我) ;(2) ;(3) ;(iv) ;(v) ;(vi) 。

定理(见[912])。根据到目前为止的符号,如果是一个矩阵,对任何,存在,,这样

3所示。同步Multisplitting和施瓦兹的方法

由定理9,。这意味着高斯-赛德尔迭代方法与新的preconditional矩阵不会比对应的吗。类似于(6),提出了一种同步multisplitting和施瓦兹算法对应。

算法10(同步multisplitting和施瓦兹的方法)。(1)给出一个初始向量。
(2)让 在哪里,是一个非负对角矩阵,是下面的连结控制协定的解决方案: 在哪里,。
(3)考虑;如果迭代解收敛,停止;别的,返回步骤(2)。

让,,。定义作为 在哪里表示和表示。

然后下面的引理显然是正确的。

引理11。对于每一个分裂,让被定义为(15)。那么子问题(14)相当于以下问题:找到,这样

4所示。收敛性分析

在本节中,我们给出算法的收敛性分析。

引理12(见[6])。让的解决方案(1),的解决方案(14);然后

定理13。让是一个矩阵;序列由算法生成10收敛的解(1)。

证明。结论容易导致引理2,引理12和定理9。

在引理7,如果,然后是一个矩阵。如果,,然后和不是一个矩阵。在续集,我们将检查是一个与积极的对角元素矩阵,满足一些条件。

引理14(见[16])。让严格对角占优或一种不能简化主导矩阵。然后是一个矩阵。

引理15。让是一个对角占优矩阵。如果和,,然后是一个用积极的对角元素矩阵。

证明。请注意,,。我们有 是定义良好的。的定义,对于,我们有,(1) ;(2) ;(3)如果,
这意味着是一个对角占优矩阵;然后它是一个矩阵与积极的对角元素的引理14。

自是一个矩阵,根据(8),我们可以解决这个问题(5)使用算法10,在那里也许是一个兼容矩阵分裂。

引理16(见[6])。让的解决方案(1),的解决方案(14);然后

类似于定理2.1的证明(8),我们有以下收敛定理。

定理17。让是一个矩阵;序列由算法生成10收敛于问题的解决方案(1)。

5。数值实验

在本节中,我们给出两个算例表明,新方法是有效的。在数值实验中,停止准则。表,MMS表示算法10预调节器,GSOR表示算法10,在这。

例1。我们考虑一个线性互补问题,其系数矩阵
结果如表所示1。

例2。让我们考虑以下问题: 在哪里,是一个单位矩阵,,。
为,让我们选择;然后是一个矩阵。在算法10 也许是一个兼容为每个分裂分裂。相应的结果如表所示2和3。
(AMAOR)加速modulus-based加速超松弛迭代法提出了郑和阴11]。在[一样11),我们选择,,。在示例2,。在表4iter表示迭代步骤,cputime表示时间(秒)。表4表明我们的预处理方法比AMAOR MMS花更少的时间。

利益冲突

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

确认

这项工作是由中国国家自然科学项目支持11161014和广西实验中心的信息科学的基础。