２０１０年９月 四川师范大学学报（自然科学版） ＪｏｕｍＭ ｏｆ Ｓｉｃｈｕａｎ Ｎｏｒｍ￣Ｕｍｖｅｍｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） Ｓｅｐｔ．，２０１０ Ｖｏｌ｜３３．Ｎｏ．５ 第３３卷第５期 线性互补问题异步并行多ＧＡＯＲ方法的收敛分析 戴平凡 ， 李耀堂 （１．三明学院数学与计算机科学系，福建三明３６５００４； ２．云南大学数学与统计学院，云南昆明６５００９１） 摘要：结合矩阵的多技术，把解线性互补问题的广义加速超松弛（ＧＡＯＲ）方法并行化，建立了解线 性互补问题的异步并行多广义加速超松弛方法（ＰＭＡＧＡＯＲ），证明了当系统矩阵为 ～矩阵时，方法 的全局收敛性；当系统矩阵为Ｅ一矩阵时，方法的单调收敛性．该方法是文献（Ｂａｉ Ｚ Ｚ，Ｅｖａｎｓ Ｄ Ｊ．Ｊ Ｃｏｍｐｕｔ Ａｐｐｌ Ｍａｔｈ，１９９８，９６：１２７—１３８．）中方法（ＰＭＣＡＯＲ）的推广，算法执行时有更多松弛参数的选择． 关键词：线性互补问题；ＰＭＡＧＡＯＲ方法；收敛 中图分类号：０２４１．６ 文献标识码：Ａ 文章编号：１００１—８３９５（２０１０）０５—０６３０—０５ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—８３９５．２０１０．０５．０１４ 解大规模线性方程组的并行多迭代法是 广，算法执行时有更多松弛参数的选择． Ｄ．Ｐ．０’Ｌｅａｒｙ和Ｒ．Ｅ．Ｗｈｉｔｅ¨ 首先提出的，后来 我们将用以下记号．设Ｃ＝（Ｃ ）∈Ｒ “． 许多的文献进一步发展了这一方法 ．并行多分 ｄｉａｇ（Ｃ）指用Ｃ的对角元素构成的对角矩阵，Ｉ Ｃｌ＝ 裂迭代法采用两种基本形式：一种是同步方法，另 （Ｉｃ Ｉ）指矩阵Ｃ的绝对值．（ｃ）＝（（ｃ薪））指Ｃ的比 一种是异步方法．同步方法是指在所有并行处理器 较矩阵，即当ｋ＝ 时，（ｃ村）＝Ｉｃ村ｌ；当ｋ＃ｊ时，（ｃ坷）＝ 上，当前迭代的结果更新以后才能进行下一步并行 一ｌｃ Ｉ，ｋ√＝１，２，…，ｎ．Ｐ（Ｃ）指Ｃ的谱半径． 迭代，异步方法是指各处理器在用其它处理器的可 定义１＿】 设Ａ∈Ｒ ： 能延迟的迭代结果来计算下一步迭代时，各个处理 （１）如果０ ＞０（ｋ＝ ）且口＊≤０（ ≠ｊ．）， ， ＝ 器彼此或多或少是的．考虑到能够节省潜在的 １，２，…，ｎ，那么Ａ是 一矩阵； 时问，自从Ｄ．Ｃｈａｚａｎ和Ｗ．Ｍｉｒａｎｋｅｒｌ】 以点迭代 （２）如果Ａ是非奇异的 一矩阵且Ａ～＞１０，那 格式介绍异步迭代方法以来，该方法（也常叫混沌 么Ａ是 一矩阵； 方法）吸引了许多学者的关注． （３）如果（Ａ）是一个 一矩阵，那么Ａ是Ⅳ一 最近，通过把线性系统的多技术应用到线 矩阵． 性互补问题，ｚ．Ｚ．Ｂａｉ等 ’ 提出了一类在多处 定义２对于 ∈Ｒ ，定义向量Ｘ＋，满足（ ＋）， 理器系统解线性互补问题的并行多方法．特别 ＝１Ｔｌａｘ｛０， ｝√：１，２，…，ｎ，那么，对任何 ，Ｙ∈Ｒ ， 地，在文献［１２］中介绍了解线性互补问题的异步并 以下结果成立： 行多加速超松弛方法（ＰＭＣＡＯＲ方法）。而在 （１）（ ＋Ｊ，）＋≤ ＋＋ ＋； 文献［１３］中，作者提出了解线性互补问题的广义加 （２） ＋－ｙ＋≤（ －ｙ）＋； 速超松弛方法（ＧＡＯＲ方法）．受文献［１２］的启发， （３）Ｉ ｌ： ＋＋（一 ）＋； 在本文中，结合矩阵的多技术，把解线性互补 （４） ≤ ，贝０ ＋≤．），＋． 问题的ＧＡＯＲ方法并行化，得到解线性互补问题的 考虑线性互补问题：对任意给定的Ｍ∈Ｒ 和 异步并行多广义加速超松弛方法（ＰＭＡ－ ｑ∈Ｒ ，找到ｚ∈Ｒ 使得ｚｔ＞０，Ｍｚ＋ｑ＞１０，及ｚ （Ｍｚ ＧＡＯＲ），证明了当系统矩阵为日一矩阵时，方法的 ＋ｑ）：０．由定义２，则线性互补问题等价于如下的 全局收敛性；当系统矩阵为 一矩阵时，方法的单调 不动点问题 收敛性．该方法是文献［１２］中ＰＭＣＡＯＲ方法的推 ｚ＝（ｚ—Ｄ （Ｍｚ＋ｑ））＋， （１） 收稿日期：２００９—０３—１７ 基金项目：福建省教育厅基金（ＪＢ０９２２８）资助项目 作者简介：戴平凡（１９７５一），男，讲师，主要从事数值代数的研究 第５期 戴平凡等：线性互补问题异步并行多ＧＡＯＲ方法的收敛分析 ６３１ 这里Ｄ＝ｄｉａｇ（Ｍ）是非奇异的 引．因此，由（１）式出 现了多种迭代方法，如ＧＡＯＲ方法¨ ： ｚ ＝（ｚ ——Ｄ一 ［ｅｄ￣Ｌｚ ＋ （ —ｏＬｇＪＬ）ｚ ＋伪］）＋． 其中，Ｍ＝Ｄ＋Ｌ＋ ，Ｄ＝ｄｉａｇ（Ｍ），Ｌ和Ｕ分别是 严格下三角矩阵和严格上三角矩阵， ＝ｄｉａｇ（ ， ，…， ），其中 ∈Ｒ＋（ｉ＝１，２，…，ｎ）且 是实 数．对于ＧＡＯＲ方法的基本性质和收敛理论，见文 献［１３］．此外，（１）式也直接导致了下列引理． 引理１［１３，１５］ 设 是对角元素为正的 一矩 阵，则线性互补问题ＬＣＰ（Ｍ，ｑ）有唯一解ｚ ∈Ｒ ． １解线性互补问题的ＰＭＡＧＡＯＲ方法 设Ｍ∈Ｒ 是非奇异矩阵，Ｚ≤ｎ是一个正整数， Ｄ＝ｄｉａｇ（Ｍ），Ｍ＝Ｄ＋Ｌ＋Ｕ（ ＝１，２，…，Ｚ）．假定 和 分别是严格下三角矩阵和严格上三角矩 阵，Ｅ ∈Ｒ 是非负对角矩阵，使得ｄｅｔ（Ｄ）≠０且 （１）Ｍ＝Ｄ＋Ｌ ＋Ｕｋ， ｌ （２）∑Ｅ ＝ｊ（ｎ×凡单位矩阵）， ￣ＪＪ（Ｄ＋ ， ， ）（后＝１，２，…， ）叫做矩阵Ｍ∈ Ｒ 的一个多．定义ｆ个算子 ： 一Ｒ ， ＝ １，２，…，ｆ，使得 （ｚ）＝ ，ｊ｝＝１，２，…，ｆ， （２） 这里 是如下系统的不动点 ＝（ｚ—Ｄ （０ ＋ （ Ｍ一 ）ｚ＋ ））＋． （３） 事实上，对任何ｚ∈Ｒ“，（３）式在Ｒ 中有唯一 解．那么ＰＭＧＡＯＲ方法等价于以下格式 ｆ ＝∑ （ ），Ｐ：０，１，２，…， 同文献［１５］中模型４的并行多异步方法， 考虑下列多处理器上解线性互补问题的并行多分 裂异步广义加速超松弛方法ＰＭＡＧＡＯＲ方法． ＰＭＡＧＡＯＲ方法给一个初始向量ｚ。∈Ｒ ． 对于Ｐ＝０，１，２，…，计算 ， ＝∑ 』 似 （、 ）， ｋ＝１ Ｐ＝０，１，２，…， ＝１，２，…，ｆ， 其中， （ ，Ｐ）是复合数且满足 （ ）一 。 。…。 ， （ｋ，ｐ）≥１， 【Ｊ， （后，Ｐ）＜１． 上述方法中，异步参数ＯＺ（ ，Ｐ）是指第七个处理 器在第Ｐ步更新向量．此外 （ ：１，２，…，ｆ）是指第 个算子，它是第 个处理器所要计算的任务．另一 方面，适当选择算子 （ｊ｝＝１，２，…，ｚ）的异步参数，不 仅大大改进该方法的收敛性质，而且也会得到一系 列矩阵意义上的并行异步松弛方法． ２ Ｈ一矩阵的收敛分析 下面重点讨论当系统矩阵Ｍ∈Ｒ 为Ｈ一矩阵 时，ＰＭＡＧＡＯＲ方法的收敛性．为此，我们分析定义在 （２）、（３）式中算子 ：Ｒ 一Ｒ ， ＝１，２，…，２的性质． 定理１设 ：Ｒ 一Ｒ ， ＝１，２，…，ｆ，是定义在 （２）、（３）式中的算子，并且记 Ｇ ＝Ｉ一 Ｉ ｆ， Ｆ ＝Ｉ Ｊ—Ｄ （ｇ／Ｍ一 ）Ｉ， 后＝１，２，…，ｆ， （４） 那么对任何Ｙ，ｚ∈Ｒ 有 Ｊ （ｚ）一 （Ｙ）ｌ≤Ｇ；－ Ｆ Ｉ ｚ—Ｙ ｌ， ＝１，２，…，ｆ． （５） 证明设叼 ＝ （ ），那么 ＝（Ｙ—ＤＩ１［Ｑ ２Ｌ 叩 ＋（ 一ｄ ２Ｌ ）．），＋ ］）＋， ＝１，２，…，Ｚ． （６） 于是，从（３）式减去（６）式得 一，７ ＝（ｚ—Ｄ （０ ＋（［２Ｍ一０ ）ｚ＋ ））＋一（Ｙ—Ｄ一 ［ 』２Ｌ ＋（ 一ｄ ）Ｙ＋ ］）＋≤（（ｚ—Ｙ）一Ｄ ［ａ ２Ｌ （ 一叼 ）＋ （ 一ａ僦 ）（ｚ一 ）］）＋． 因此 （ 一 ）＋≤（一 ＊１Ｌ （ 一叩 ））＋＋ （［Ｉ—Ｄ一 （／／Ｍ一０ ２Ｌ ）］（ｚ—Ｙ））＋． （７） 类似地，得到 （叼 一 ）＋≤（一 一Ｌ （叼 一 ））＋＋ （［，一Ｄ （ —ａ ）］（Ｙ—ｚ））＋．（８） 从（７）和（８）式，我们能够获得下列估计 Ｉ 一 ｌ＝（ 一 ）＋＋（呀 一 ）＋≤ （一ａ ～Ｌ （ 一ｒ／））＋＋（一ｄ ～Ｌ （叼 一 ））＋＋ （［ ～Ｄ一 （ ～ａ ２Ｌ ）］（ｚ—Ｙ））＋＋ （［Ｊ—Ｄ （／／Ｍ— ２Ｌ ）］（Ｙ—ｚ））＋＝ Ｉ ａ 。。Ｌ （ 一叼 ）ｌ＋ｌ［Ｊ—Ｄ一 （／／Ｍ一 ２Ｌ ）］（ｚ—Ｙ）ｌ≤０１ Ｉ Ｌ Ｉ ｌ 一叩 Ｉ＋ ｌ Ｊ—Ｄ （ 一 ２Ｌ ）｝ｌ ｚ—Ｙ １． ６３２ 四川师范大学学报（自然科学版） 故 Ｉ 一 Ｉ≤Ｇｉ Ｆ ｌ ｚ—Ｙ Ｉ，ｋ＝１，２，…，ｆ． 定理得证． 定理２设定理ｌ的条件满足，则对任意Ｙ，Ｚ ＥＲ 和任何非负整数 ，有 Ｉ （ｚ）一 （Ｙ）Ｉ≤（Ｇｉ Ｆ ） ｌ ｚ—Ｙ Ｉ， ＝１，２，…，ｆ． 证明基于定理１，这个结论显然可直接由 递推得到． 有了上面的准备，现在能够建立ＰＭＡＧＡＯＲ方 法的收敛性． 定理３设Ｍ＝（ｍ ）∈Ｒ 是一个有正对角 元素的日一矩阵．设（Ｄ＋Ｌ ， ， ）（ ＝１，２，…，ｆ） 是它的多且满足 （Ｍ）＝Ｄ—Ｉ Ｉ—ｌ ｌ；Ｄ—ｌ Ｉ， ｋ＝１，２，…，Ｚ． 对任意初始向量ｚ。∈Ｒ ，如果异步参数０ｔ（．ｉ｝，Ｐ）使 得０ｇ（ｋ，Ｐ）≥１（ｋ＝１，２，…，Ｚ；ｐ＝０，１，２，…，）且松弛 参数 及 满足 ，） ０＜０９ｉ＜ Ｔ ， ０≤ ≤１， ｉ＝１，２，…，／／，， 则由ＰＭＡＧＡＯＲ方法迭代产生的序列｛ｚＰ｝收敛于 ＬＣＰ（Ｍ，ｑ）的唯一解ｚ ． 证明从引理１，ＬＣＰ（Ｍ，ｑ）有唯一解ｚ Ｅ Ｒ ．也就是说，ｚ ＝ （ｚ ）（ｋ＝１，２，…，２），因此 Ｚ ｚ ＝∑Ｅ （ｚ ）， Ｐ＝０，１，２，…，ｋ：１，２，…，ｆ． 按照ＰＭＡＧＡＯＲ方法的定义，得到 Ｚ ｌ一ｚ Ｉ＝∑Ｅ １ ‘ ’（ｚ ）一 似 （ｚ ）ｌ， Ｐ＝０，１，２，…， 由定理１和２能进一步获得 Ｚ Ｉ ｚ川一ｚ Ｉ≤∑Ｅ （Ｇ Ｆ ） ’ Ｉ Ｚ 一Ｚ Ｉ＝ Ｉ Ｚｐ—ｚ Ｉ≤Ｈ 一Ｈｏ Ｉ Ｚ。一ｚ’Ｉ， Ｐ＝０，１，２，…， 这里 ？ ＝∑Ｅ （Ｇ Ｆ ） ，Ｐ＝０，１，２，…。 因此，如果 ｌｉｍ Ｉ －［Ｈ￣ ０，迭代序列｛ｚＰ｝收敛于 ｚ ．需要证明对某个正的向量Ｕ∈Ｒ 和某个非负常 数０∈［０，１），Ｉｔｖｕ≤Ｏｕ（Ｐ＝０，１，２，…）成立．事实 上，从文献［３］知道在给定的条件下存在一个正的 向量Ｕ∈Ｒ 和一个常数０∈［０，１）满足Ｇ Ｆ Ｕ≤ “（ｋ＝ｌ，２，…，ｚ）．因此，记 （ｋ，Ｐ）≥１（（ｋ＝１，２， …，２；ｐ＝０，１，２，…），显然有 ｌ ， Ｈｐｕ＝∑Ｅ （Ｇｉ Ｆ＾） ≤∑Ｅ 似 ｌｆ≤Ｏｕ， ＝１ ＝ｌ Ｐ＝０，１，２，…． 定理证毕． ３单调收敛分析 下面主要讨论当系统矩阵Ｍ∈Ｒ 是一个￡ 一矩阵时，ＰＭＡＧＡＯＲ方法的单调收敛性质．我们 将证明，对于某个初始向量，ＰＭＡＧＡＯＲ方法产生 的迭代序列收敛于ＬＣＰ（Ｍ，ｇ）的解．为此，我们假 定线性互补问题的解的集合 ＝｛ｚ∈Ｒ”Ｉ ｚ≥０，Ｍｚ＋鼋≥０｝ 是非空的． 首先，研究下列算子的单调性质： ：Ｒ“一Ｒ ，ｋ ＝１，２，…，ｆ， （ｚ）＝ ， ＝（ｚ—ＤＩ１［ ＋ （．ＯＭ一 Ｌ ）ｚ＋ ］）＋． （９） 定理４ 设算子 ：Ｒ 一Ｒ“，ｋ＝１，２，…，２如 （９）式所定义．假定Ｍ∈Ｒ 是一个 一矩阵，且 （Ｄ＋ ， ，Ｅ ）（ ＝ｌ，２，…，２）是它的一个多分 裂，其中Ｌ ≤０，Ｕ ≤０，ｋ＝１，２，…，ｆ．还假定０＜ ≤１（ｉ＝１，２，…，ｎ），０≤ＯＬ≤１．那么对任何ｚ∈ ，有 （１） （ｚ）≤ｚ； ＝１，２，…，Ｚ； （２）Ｙ≤ｚ （Ｊ，）≤ （Ｚ）；后＝１，２，…，ｆ； （３） ＝∑ （ｚ）∈ｑ，－． 证明类似于文献［１３］中的定理４的证明． 基于定理４，能得到ＰＭＡＧＡＯＲ方法的单调收 敛性． 定理５假定Ｍ∈Ｒ 一个￡一矩阵．还假定０ ＜ ≤１，０≤ ≤１．那么对任何初始向量ｚ。Ｅ ，由 ＰＭＡＧＡＯＲ方法产生的迭代序列｛ｚＰ｝，Ｐ＝０，１，２， …，有下列性质： （１）０≤ “≤ｚ ≤ｚ。，Ｐ＝０，１，２，…； 第５期 戴平凡等：线性互补问题异步并行多ＧＡＯＲ方法的收敛分析 ６３３ （２）ｌｉｍｚ ＝Ｚ 是ＬＣＰ（Ｍ，ｑ）的解； （１）Ｌ ≤ ，ｋ＝１，２，…，ｆ； （２）０≤ ≤ｏＬ≤ｌ； （３）ＬＣＰ的任意解ｚ一若满足０≤ｚ一≤ｚ。则 Ｚ一＜－ｚ ． （３）０≤ ≤ ≤１，ｉ：１，２，…，ｒｔ； （４） （ｋ，ｐ）≤ （ｋ，Ｐ），ｋ＝１，２，…，ｌ；ｐ＝０，１， ２，…． 证明 因为ｚ。∈ ，由定理４的（１），有ｚ ≤ｚ。 及ｚ ∈ 然后再反复用定理４得（１）．从（１）知道 序列｛ｚ ｝单调有界，因此它收敛于某个向量Ｚ ，且 满足 则有 ≤乏 ，Ｐ＝０，１，２，…． （１ｏ） ｚ ＝（ｚ 一Ｄ ［ａＯＬ Ｚ ＋ （１２Ｍ—ｃｒ￣Ｏ，Ｌ ）ｚ ＋Ｏｑ］）＋， 即 证明由定理５知道序列｛ ｝及｛ ｝收敛．下 面证明（１Ｏ）式．类似于证明定理４的过程，假定对 于ｐ＝Ｏ，１，２，…，有 ， ∈ 定义算子 ：Ｒ 一Ｒ ， ｋ＝１，２，…，ｚ，满足 （ｚ）＝ （ｋ＝１，２，…，ｚ），这里 ｚ ＝（ｚ 一Ｄ ［．ＯＭｚ ＋伪］）＋． 故Ｚ 是线性互补问题ＬＣＰ（ ，口）的解．考虑（３）． 因为ｚ一是ＬＣＰ（Ｍ，ｇ）的解，则Ｚ～ｆ 是下列方程的不动点 ＝ 芋 ＝（ｚ—Ｄ ［ （ 一 芋 ＋ ）ｚ＋ ］）＋， ∑Ｅ ：１ （ｚ一），ｐ＝ｏ，１，２，…，成立．反复应用 其中， ＝ｄｉａｇ（ ， ，…，历 ）．那么，有 “＝定理４，得ｚ一≤Ｚｐ，Ｐ＝０，１，２，…，然后，不等式两边 取极限得Ｚ一≤ｚ ． ∑Ｅ 似 ’（ ）， ＝Ｉ 下列定理描述了参数∞ ， 和系统矩阵Ｍ∈Ｒ 的多（Ｄ＋ ， ，Ｅ ）（ｋ＝１，２，…，Ｚ）对ＰＭＡ— Ｐ＝０，１，２，…， ＝１，２，…，ｆ． 此外，只有（１）～（４）中有一个成立，对ｚ∈ ，能够 ＧＡＯＲ方法单调收敛率的影响． 定理６设Ｍ∈Ｒ 是一个￡一矩阵．设（Ｄ＋ 工 ， ， ）（ｋ＝１，２，…，Ｚ）和（Ｄ＋ ， ，Ｅ ）（ ＝ １，２，…，ｆ）是系统矩阵Ｍ∈Ｒ 的两个多，且 满足Ｌ ≤Ｏ， ≤０， ≤０和Ｕｋ≤０，ｋ＝１，２，…，ｚ． 由归纳法得 （ｚ）≤五（ｚ），ｋ＝１，２，…，２．因为ｚ∈ 则Ｖｋ Ｅ｛ｋ＝１，２，…，ｆ｝， （ｚ）， （ｚ）∈ ，所要 ，证的结论能由归纳法得到．事实上，当ｐ＝０，（１０） 式显然成立．假定（１Ｏ）式对某个正整数ｐ成立．那 么由（４）及反复用定理４易得 ‘ （ ）≤ ‘ （乏Ｐ）， ｐ＝０，１，２，…，ｋ＝１，２，…，Ｚ， 那么，对任何初始向量ｚ。＝ ∈缈，分别对应于参数 （ ，ｏＬ）、（历 ， ）及多（Ｄ＋ ， ，Ｅ ）（ｋ＝１， ２，一。，Ｚ）、（Ｄ＋ ， ， ）（ｋ＝１，２，…，Ｚ），由ＰＭＣ－ 因此，ｚｐ“≤之Ｐ“，Ｐ＝０，１，２，…．证毕． 致谢 感谢三明学院科研基金项目（Ｂ０８２６／ Ｑ）的资助． ＧＡＯＲ方法产生的两个迭代序列｛ｚＰ｝和｛ ｝收敛于 线性互补问题ＬＣＰ（Ｍ，ｑ）的解ｚ ∈Ｒ ．此外，如果 下列条件中至少有一个成立： 参考文献 ［１］ｏ’Ｌｅａｆｙ Ｄ Ｐ，Ｗｈｉｔｅ Ｒ Ｅ．Ｍｕｈｉｓｐｌｉｔｔｉｎｇｓ ｏｆ ｍａｔｉｒｃｅｓ ａｎｄ ｐａｒａｌｌｅｌ ｓｏｌｕｔｉｏｎ ｏｆ ｌｉｎｅａｒ ｓｙｓｔｅｍｓ［Ｊ］．ＳＩＡＭ Ｊ Ａｌｇｅ Ｄｉｓｃ Ｍｅｔｈ，１９８５， ６：６３０—６４０． ［２］Ｂａｉ Ｚ Ｚ．Ｏｎ ｔｈｅ ｍｏｎｏｔｏｎｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｍａｔｉｒｘ ｍｕｈｉｓｐｌｉｔｔｉｎｇ ｒｅｌａｘａｔｉｏｎ ｍｅｔｈｏｄｓ ｆｏｒ ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍ［Ｊ］． ＩＭＡ Ｊ Ｎｕｍｅｒ Ａｎａｌ，１９９８，１８：５０９—５１８． ［３］Ｂａｉ Ｚ Ｚ，Ｅｖａｎｓ Ｄ Ｊ．Ｍａｔｒｉｘ ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ ｒｅｌａｘａｔｉｏｎ ｍｅｔｈｏｄｓ ｏｒｆ ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｉｎｔ Ｊ Ｃｏｍｐｕｔ Ｍａｔｈ，１９９７， ６３：３０９—３２６． ［４］Ｆｒｏｍｍｅｒ Ａ，Ｍａｙｅｒ Ｇ．Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｐａｒａｌｌｅｌ ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ ｍｅｔｈｏｄｓ［Ｊ］．Ｌｉｎｅａｒ Ａｌｇｅ Ａｐｐｌ。１９８９，１ １９：１４１—１５２． ［５］Ｙｕａｎ Ｄ Ｊ．Ｏｎ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｐａｒａｌｌｅｌ ｍｕｈｉｓｐｌｉｔｔｉｎｇ ａｓｙｎｃｈｒｏｎｏｕｓ ＧＡＯＲ ｍｅｔｈｏｄ ｆｏｒ Ｈ—ｍａｔｉｒｘ［Ｊ］．Ａｐｐｌ Ｍａｔｈ Ｃｏｍｐｕｔ， ２００５，１６０：４７７—４８５． ［６］Ｓｏｎｇ Ｙ Ｚ，Ｙｕａｎ Ｄ Ｊ．Ｏｎ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｒｅｌｘｅｄ ｐａａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄｓ ｆｏｒ 一ｍａｔｉｒｘ［Ｊ］．Ｉｎｔ Ｊ Ｃｏｍｐｕｔ Ｍａｔｈ， ６３４ １９９４，５２：１９５—２０９． 四川师范大学学报（自然科学版） ３３卷 ［７］Ｎｅｕｍａｍｍ Ｍ，Ｐｌｅｍｍｏｎｓ Ｒ Ｊ．Ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｐａｒａｌｌｅｌ ｍｕｈｉｓｐｌｉｔｔｉｎｇ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄｓ ｆｏｒ肘一ｍａｔｒｉｃｅｓ［Ｊ］．Ｌｉｎｅａｒ Ａｌｇｅ Ａｐｐｌ， １９８７，８８／８９：５５９—５７３． ［８］Ｌｉ Ｗ，Ｓｕｎ Ｗ Ｗ．Ｃｏｍｐａｒｉｓｏｎ ｒｅｓｕｌｔｓ ｏｆｒ ｐａｒａｌｌｅｌ ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ ｍｅｔｈｏｄｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ ＡＯＲ ｍｅｔｈｏｄｓ［Ｊ］．Ｌｉｎｅａｒ Ａｌｇｅ Ａｐｐｌ， ２００１，３３１：１３１—１４４． ［９］ “ｗ，Ｓｕｎ Ｗ ｗ，Ｌｉｕ Ｋ．ＰａｒＭｌｅｌ ｍｕｈｉｓｐｌｉｔｔｉｎｇ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄｓ ｏｒｆ ｓｉｎｇｕｌａｒＭ—ｍａｔｒｉｃｅｓ［Ｊ］．Ｎｕｍｅｒ Ｌｉｎｅａｒ Ａｌｇｅ Ａｐｐｌ，２００１ ８：１８ｌ一１９０． Ｏ １ ２ Ｂａｉ Ｚ Ｚ．Ｏｎ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｏｆ ｐａｒａｌｌｅｌ ｎｏｎｓｔａｔｉｏｎａｒｙ ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄｓ［Ｊ］．Ｊ Ｃｏｍｐｕｔ Ａｐｐｌ Ｍａｔｈ，２００３，１５９：ｌ一１ １ Ｃｈａｚａｎｋ Ｄ，Ｍｉｒａｎｋｅｒ Ｗ．Ｃｈａｏｔｉｃ ｒｅｌａｘａｔｉｏｎ［Ｊ］．Ｌｉｎｅａｒ Ａｌｇｅ Ａｐｐｌ，１９６９，２：１９９—２２２． Ｂａｉ ｚ ｚ，Ｅｖａｎｓ Ｄ Ｊ．Ｃｈａｏｔｉｃ ｉｔｅｒａｔｉｖｅ ｍｅｔｈｏｄｓ ｆｏｒ ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍｓ［Ｊ］．Ｊ Ｃｏｍｐｕｔ Ａｐｐｌ Ｍａｔｈ，１９９８，９６：１２７—１３８ Ｌｉ Ｙ，Ｄａｉ Ｐ．Ｇｅｎｅｒａｌｉｚｅｄ ＡＯＲ ｍｅｔｈｏｄｓ ｏｒｆ ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍ［Ｊ］．Ａｐｐｌ Ｍａｔｈ Ｃｏｍｐｕｔ，２００７，１１８：７—１８． Ｙｏｕｎｇ Ｄ Ｍ．Ｉｔｅｒａｔｉｖｅ Ｓｏｌｕｔｉｏｎ ｏｆ Ｌａｒｇｅ Ｌｉｎｅａｒ Ｓｙｓｔｅｍｓ［Ｍ］．Ｎｅｗ Ｙｏｒｋ：Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，１９７１。 Ｂｒｕ Ｒ，Ｅｉｓｎｅｒ Ｌ，Ｎｅｕｍａｎｎ Ｍ．Ｍｏｄｅｌｓ ｏｆ ｐａｒａｌｌｅｌ ｃｈａｏｔｉｃ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄｓ［Ｊ］．Ｌｉｎｅａｒ ＡＪｇｅ Ａｐｐｌ，１９８８，１０３：１７５—１９２． ３ ４ ５ Ｃｏｎｖｅｒｇｅｎｃｅ Ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ Ｐａｒａｌｌｅｌ Ｍｕｈｉｓｐｌｉｔｔｉｎｇ Ｃｈａｏｔｉｃ ＧＡＯＲ Ｍｅｔｈｏｄ ｆｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ Ｐｒｏｂｌｅｍ ＤＡＩ Ｐｉｎｇ—ｆａｎ ，ＬＩ Ｙａｏ—ｔａｎｇ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆＭａｔｈｅｍａｔｉｃｓ ａｎｄ Ｃｏｍｐｕ￣ｒ，Ｓａｎｍｉｎｇ Ｃｏｌｌｅｇｅ，Ｓａｎｍｉｎｇ ３６５００４，Ｆｕｊ￣ｎ； ２．Ｄｅｐａａｒｔｍｅｎｔ ｏｆＭａｔｈｅｍａｔｉｃｓ，Ｙｕｎｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｋｕｎｍｉｎｇ ６５００９１，Ｙｕｎｎａｎ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ＡＯＲ ｍｅｔｈｏｄ ｆｏｒ ｔｈｅ ｓｏｌｕｔｉｏｎ ｏｆ ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍ ｉｓ ｐａｒａｌｌｅｌｅｄ ｂｙ ｃｏｍｂｉｎｉｎｇ ｔｈｅ ｍａ— ｔｒｉｘ ｍｕｌｔｉｓｐｈｔｔｉｎｇ ｔｅｃｈｎｉｑｕｅ ａｎｄ ｔｈｅ ａｓｙｎｃｈｒｏｎｏｕｓ ｐａｒａｌｌｅｌ ｍｕｈｉｓｐｌｉｔｔｉｎｇ ａｓｙｎｃｈｒｏｎｏｕｓ ｇｅｎｅｒａｌｉｚｅｄ ＡＯＲ（ＰＭＡＧＡＯＲ）ｍｅｔｈｏｄ ｉｓ ｅｓｔａｂ— ｌｉｓｈｅｄ．Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ，ｔｈｅ ｇｌｏｂａｌ ｃｏｎｖｅｒｇｅｎｃｅ ｉｓ ｐｒｏｖｅｄ ｆｏｒ ｔｈｅ Ｈ－ｍａｔｒｉｘ，ａｎｄ ｔｈｅ ｍｏｎｏｔｏｎｅ ｃｏｎｖｅｒｇｅｎｃｅ ｆｏｒ ｔｈｅ Ｌ—ｍａｔｒｉｘ．Ｍｏｒｅｏ— ｖｅｒ，ｔｈｅ ｎｅｗ ｍｅｔｈｏｄ，ｗｈｉｃｈ ｈａｓ ｍｏｒｅ ｒｅｌａｘｅｄ ｐａｒａｍｅｔｅｒｓ ｔｏ ｓｅｌｅｃｔ ｉｎ ｔｈｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ，ｉｓ ａ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ｏｆ ｔｈｅ Ｏ— ｉｒｇｉｎａｌ（ＰＭＣＡＯＲ）ｉｎ（Ｂａｉ Ｚ Ｚ，Ｅｖａｎｓ Ｄ Ｊ．Ｉｎｔ Ｊ Ｃｏｍｐｕｔ Ｍａｔｈ，１９９７，６３：３０９—３２６．）． Ｋｅｙ ｗｏｒｄｓ：ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍ；ＰＭＡＧＡＯＲ ｍｅｔｈｏｄ；ｃｏｎｖｅｒｇｅｎｃｅ ２０００ ＭＳＣ：６５Ｆ０２ （编辑周俊）
