第３７卷第４期 南昌大学学报（理科版） Ｖｏ１．３７ ＮＯ．４ ２０１３年８月 Ｊｏｕｒｎａｌ ｏｆ Ｎａｎｃｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ） Ａｕｇ．２０１３ 文章编号：１００６—０４６４（２０１３）０４—０３０７—０６ 线性互补问题基于模同步块多重 分裂方法的收敛性 孙冲冲，汪 祥，李 燕 （南昌大学数学系，江西南昌 ３３００３１） 摘要：通过利用不动点迭代来研究线性互补问题，根据基模同步多重分裂迭代方法将其线性互补问题的系数矩 阵是点的形式推广到块Ｈ＋的形式，并且分析了当系数矩阵是块矩阵时线性互补问题解的收敛情况。 关键词：线性互补问题；块多重分裂；块Ｈ＋矩阵；模方法 中图分类号：Ｏ２４１．６ 文献标志码：Ａ Ｃｏｎｖｅｒｇｅｎｔ ａｎａｌｙｓｉｓ ｏｆ ｌｉｎｅａｒ ｃｏｍｐｉｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍｓ ｂａｓｅｄ ｏｎ ｓｙｎｃｈｒｏｎｏｕｓ ｂｌｏｃｋ ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄｓ ＬＩ Ｙａｎ，ＷＡＮＧ Ｘｉａｎｇ，ＳＵＮ Ｃｈｏｎｇｃｈｏｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｎａｎｃｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｃｈａｎｇ ３３００３１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｅ ｓｔｕｄｉｅｄ ｔｈｅ ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍ ｂｙ ｕｓｉｎｇ ｔｈｅ ｆｉｘｅｄ ｐｏｉｎｔ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ．Ｉｔｓ ｃｏｅｆｆｉｃｉｅｎｔ ｍａｔｒｉｘ ｗａｓ ｇｅｎｅｒａｌｉｚｅｄ ｆｒｏｍ ｐｏｉｎｔ ｆｏｒｍ ｔｏ ｂｌｏｃｋ ｆｏｒｍ，ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｍｏｄｕｌｕｓ—ｂａｓｅｄ ｓｙｎｃｈｒｏｎｏｕｓ ｍｕｌｔｉ—ｓｐｌｉｔｔｉｎｇ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄｓ．Ｗｅ ａｌｓｏ ｅｓｔａｂｌｉｓｈｅｄ ｔｈｅ ｃｏｎｖｅｒｇｅｎｃｅ ｔｈｅｏｒｙ ｏｆ ｔｈｅｓｅ ｍｏｄｕ— ｌｕｓ—－ｂａｓｅｄ ｓｙｎｃｈｒｏｎｏｕｓ ｂｌｏｃｋ ｍｕｈｉｓｐｔｉｔｔｉｎｇ ｉｔｅｒａｔｉｏｎ ｍｅｔｈｏｄｓ ｗｈｅｎ ｔｈｅ ｃｏｅｆｆｉｃｉｅｎｔ ｍａｔｒｉｘ ｗａｓ ａ ｂｌｏｃｋ ｍａ—— ｔｒｉｘ． Ｋｅｙ ｗｏｒｄｓ：ｌｉｎｅａｒ ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ ｐｒｏｂｌｅｍ；ｂｌｏｃｋ ｍａｔｒｉｘ ｍｕｌｔｉ—ｓｐｌｉｔｔｉｎｇ；ｂｌｏｃｋ Ｈ＋ｍａｔｒｉｘ；ｍｏｄｕｌｕｓ ｍｅｔｈｏｄ 线性互补问题是一类重要的优化问题，在线性 计算更高速多程序环境的要求，本文将Ｅ７］中基模 规划、凸二次问题、流体动力学的自由边界问题及网 同步多重分裂迭代法结合Ｅ６３中的块松弛迭代法来 络平衡问题等许多科学计算和工程中有着广泛的应 研究其基模同步块多重分裂迭代法的收敛情况。在 用 。 对松弛参数和块多重分裂的合理限制下，我们可以 本文考虑如下线性互补问题ＬＣＰ（ｑ，Ａ）： 得封ＭＳＢＭ的对应的块Ｊａｃｏｂｉ，块Ｇａｕｓｓ—Ｓｅｉｄｅｌ，块 ｒ：一Ａｚ＋ｇ≥０且 （Ａｚ＋ｇ）一０ （１） ＳＯＲ，块ＡｏＲ方法，其中线性互补问题的系数矩阵 其中矩阵Ａ∈Ｒ 和向量ｑ∈Ｒ”，ｒ， ∈Ｒ”为向量 Ａ为块Ｈ矩阵，且Ａ的块对角矩阵为正的。这对于 对。 研究系数矩阵是大型稀疏且呈规则块形式的线性互 为了快速而经济地解决线性互补问题ＬＣＰ（ｑ， 补问题的解的收敛情况有非常重要的意义。 Ａ），文［２］中给出了基模分裂方法，这类方法是将 ＬＣＰ（ｑ，Ａ）转换为只关于特殊向量的绝对值的不动 ｌ 预备知识 点方程系统，包括一些特殊的基模松弛方法如 为了研究线性互补问题的基模同步块多重分 Ｊａｃｏｂｉ，Ｇａｕｓｓ—Ｓｅｉｄｅｌ，ＳＯＲ和ＡＯＲ，还给出了模迭 裂迭代法的收敛情况，在此先介绍一些定义和引理。 代的一般框架形式 ，修定模迭代法［５］。为了满足 定义１［‘］ 定义集合： 收稿日期：２０１２—１０—１２。 基金项目：国家自然科学基金资助项目（１１１０１２０４），江西省青年科学家（井冈之星）项目（２０１２２ＢＣＢ２３００３），江西省自然科 学基金资助项目（２０１１４ＢＡＢ２０１００４），江西省教育厅科研项目（ＧＪＪ１２０１１），江西省研究生创新项目（ＹＣ２０１１一 Ｓ００７）。 作者简介：汪祥（１９８Ｏ一），男，博士，教授，博士生导师。Ｅ－ｍａｉｌ：ｗａｎｇｘｉａｎｇ４９＠ｎｃｕ．ｅｄｕ．ｃｎ。 南昌大学学报（理科版） Ｌ Ｊ（ １， ２，…， ）一，｛Ａ＝Ａ Ｅ Ｌ （ １，，ｚ２， （２）［ＡＢ］≤［Ａ］［Ｂ］（ＥＡｒ］≤［Ａ］［．ｚ］）； （３）［ｙＡ］≤Ｉ ｙ Ｉ［Ａ］（［弦］≤１），ｌ［ｚ］）； （４）ＪＤ（Ａ）≤ｌＤ（１ Ａ Ｉ）≤Ｐ（［Ａ］）。 弓Ｉ理２［ ］ 设Ａ∈Ｌ ，ｆ（ １， ２，…，，２ｐ），为 …， ）ｌ Ａ ∈Ｌ（Ｒ ）非奇异（ｉ一１，２，…，户）｝ Ｌ ，（ １， ２，…， ）一．｛Ａ—ｄｉａｇ（Ａ１１，Ａ２２，…， Ａ ｐ ｉ Ａ ∈Ｌ（Ｒ” ）非奇异（ 一１，２，…， ）｝ 定义２［ 对于是∈｛１，２，…，ｒ），若分块矩阵 ＾ ，Ｎ ，Ｅ＾Ｅ Ｌ （ １，”２，…， ）满足 （１）Ａ—Ｍｋ—Ｎ ，ｄｅｔ（Ｍ ）≠０，忌一１，２，…，ｒ； （２）Ｅ—ｄｉａｇ（Ｅ，ｋ１，…，Ｅ ），志一１，２，…，ｒ且 ｌ ｌＥ ｌｌ一１，ｉ一１，２，…，Ｐ。 则称三元组集（ ，Ｎ ，Ｅ ）（是一１，２，…，ｒ）为 分块矩阵Ａ的一个多分裂，这里ｌｌ・ｌｌ表示满足 ｌ ｌ一１（ ∈Ｌ（Ｒ ）为单位矩阵）的相容矩阵范 数。 定义３Ｅ 设Ａ∈Ｌ （ｎ ， ２，…， ），其（工） 型块比较矩阵（Ｍ）＝＝：（＜Ｍ） ）Ｅ Ｌ（Ｒ ）和（Ｕ）型块 比较矩阵（＜Ｍ＞）一（（（Ｍ＞） ）Ｅ Ｌ（Ｒ ）分别定义 为 一 ｌＪ ｉ，ｊ一１，２，－．－，ｐ ｆ １ ．ｉ—ｉ ‘‘Ｍ 一１一ｌｌ ｔＭ ｌｌ， ≠ ｉ，ｊ一 ’ ２，…，Ｐ 另外对于块矩阵Ａ∈Ｌ （ ， ，…， ），Ｌ Ｅ Ｌ （ １， ”，ｎ ），如果分别记Ｄ（Ｌ）一ｄｉａｇ（Ｌｌ】， Ｌ２２，…，Ｌ ），Ｂ（Ｌ） 一Ｄ（Ｌ） 一 Ｌ，Ｊ（Ａ） 一 Ｄ（Ａ）＿１Ｂ（Ａ）， （Ａ）＝ｐ（Ｊ￣ａ））， （Ａ）一』Ｄ（ （Ａ））， 则有 （ — （Ａ）＞一（（Ｊ—Ｊ（Ａ）））：＝＝（（Ａ＞＞， ２（Ａ） ≤ （Ａ） 定义４Ｅ 设Ａ∈Ｌ （ １， ２，…，ｎ ），如果存 在Ｐ，Ｑ∈Ｌ ， （，２ ， ，…，，ｚ ），使得＜ＰＡＱ）为Ｍ矩 阵，则称Ａ是关于非奇异块矩阵Ｐ，Ｑ的（Ｉ）型块Ｈ 矩阵；使得＜＜ＰＡＱ）＞为Ｍ矩阵，则称是关于非奇异 块矩阵Ｐ，Ｑ的（Ⅱ）型块Ｈ矩阵。 定义５Ｅ 设Ａ∈Ｌ （ｎ ，ｎ２，…， ），则称［Ａ］ ：＝＝（Ｉ｛Ｍｏ ｌＩ）∈Ｌ（Ｒｐ）为块矩阵Ａ的块绝对值。与 此相似，可定义块向量ｚ Ｅ Ｖ （ 。， ：，…， ）的块绝 对值［ ］Ｅ Ｒ 。 下面给出块绝对值的一些重要的性质： 引理１［ 设Ａ，Ｂ∈Ｌ （ １， ２，…， ）， ， ∈Ｖ （ １，ｎ２，…，扎 ），ｙ∈Ｒ ，贝４ （１）ｌ［Ａ］一［Ｂ］ｌ≤［Ａ＋Ｂ］≤［Ａ］＋［Ｂ］（１ ［ｚ］一［．ｙ］ｌ≤［ ＋ ］≤［ｚ］＋Ｅｙ３）； Ｈ （Ｐ，Ｑ）矩阵，则 （１）Ａ非奇异； （２）［（ＰＡＱ） ］≤＜ＰＡＱ＞～； （３） （ＰＡＱ）＜１。 弓Ｉ理３［ ］ 设Ａ∈Ｌ ，Ｊ（ ｌ， ２，…， ）为 Ｈ ”（Ｐ，Ｑ）矩阵，则 （１）Ａ非奇异； （２）Ｅ（ＰＡＱ￣ ］≤（＜ＰＡＱ）） ＥＤ（ＰＡＱ￣ ］； （３） （ＰＡＱ）＜１。 引理４Ｅ８＿’ 令Ａ∈Ｒ 是Ｈ＋矩阵，则 ＬＣＰ（ｑ，Ａ）对于任意的ｑ Ｅ Ｒ 有唯一的解。 又线性互补问题ＬＣＰ（ｑ，Ａ）可以转变为不动点 方程问题，文＿８ 中给出了如下引理。 引理５ 令Ａ—Ｍ—Ｎ为矩阵Ａ的分裂， 为正对角矩阵，并且７＞０，那么对于线性互补问题 ＬＣＰ（ｑ，Ａ）以下两种情况成立： （１）如果（ ，ｒ）是线性互补问题ＬＣＰ（ｑ，Ａ）的 １ 解，则 一去ｙ（厶 —ｎ叫ｒ）满足下面隐式不动点方程 （ｎ＋Ｍ） —Ｎｘ＋（ｎ—Ａ）ｌ ｚ Ｉ—ｙｑ。 （２）如果ｚ满足（１）中的隐式不动点方程，则 一 （１ ｚ ｌ＋ｚ）和ｒ一 ｎ（１ １一 ）。 是线性互补问题的解。 ２ 块多重分裂迭代方法 文［７］中给出了线性互补问题的基模同步多重 分裂迭代法，结合文［６］中给出的并行矩阵分裂块 松弛迭代算法，我们将其推广到块的形式，即基模同 步块多重分裂迭代法（ＭＳＢＭ）： （ＭＳＢＭ）令（ ，Ｎ ，Ｅｋ）（是一１，２，…，ｒ）是系 数矩阵Ａ∈Ｒ ”的多重分裂，任给一初始向量 ∞ ∈Ｒ”，ｍ一０，１，２，…直到迭代序列｛ ｝ 。ｃ Ｒ 收敛，ｚ‘ ”Ｅ Ｒ 和ｚ‘ ”Ｅ Ｒ阜分别是通过下列式 子计算出的 州 一土（１ ‘ ＂Ｉ＋ 卅”）和ｚ‘ ＂一 ｙ Ｅｋｘ ＾） ＝１ 其中ｚ ’是通过求解下面的线性方程得到 （ｎ＋Ｍ＾）Ｉｚ 一Ｎ ｚ ＋（ｎ—Ａ）ｌ ｚ ｌ一 第４期 汪 祥等：线性互补问题基于模同步块多重分裂方法的收敛性 ・ ３Ｏ９ ・ 对于块矩阵Ａ∈Ｒ ，其块对角矩阵为Ｄ— ｄｉａｇ（Ａ Ａ ｚ，…，Ａ ），Ｌ 为块状的严格下三角矩 阵矩阵，Ｕ＾一Ｄ—Ｌ 一Ａ，记（Ｄ—Ｌ ，Ｕ ，Ｅ ）为矩 阵Ａ∈Ｒ 的三组元多重分裂，在ＭＳＢＭ中取 Ｉ（Ｄ－ ） ，…， ＩＮｋ一上（（１一 ）Ｄ＋（ 一ｆ１）＋ Ｕ ） 可得到对应的ＭＳＢＭＡＯＲ迭代方法，其中 （ａｎ＋Ｄ一』８Ｌ ） 一Ｉ－（１一ａ）Ｄ＋（ｄ—ｆ１）Ｌ ＋ ａＵ＾］ －４－ （ —Ａ）Ｉ ｚ ’Ｉ一为］，ｋ—ｌ，２，…，ｒ 注 ＭＳＢＭＡＯＲ方法也可推广到其对称形式， 即ＭＳＢＭＳＡＯＲ方法 ｕ］。 当参数对（ａ，口）分别取（ａ，ａ），（１，１）和（１，Ｏ）， 可以得到相应的ＭＳＢＭＳＯＲ，ＭＳＢＭＧＳ和ＭＳＢＭＪ ３ 收敛性分析 在这部分将讨论ＬＣＰ（ｑ，Ａ）的系数矩阵Ａ是 块Ｈ一矩阵且其块对角矩阵为正时，ＬＣＰ（ｑ，Ａ）的 解的收敛情况。 在此，令（ ，ｒ ）是ＬＣＰ（ｑ，Ａ）的精确解，由引 理４可知 １ 一÷ｙ（ 一ｎ ｒ ） 厶 类似Ｅ７］，要证｛ ） 。的收敛性只需证｛ｚ ） 。 的收敛性。 由于Ａ∈Ｌ （ ｌ， ２，…， ），为块Ｈ （Ｐ，Ｑ） 矩阵，由前面的引理２和引理３知， （ＰＡＱ）＝＝＝ ｐ（Ｊ＜Ｈ）＜１，Ｊ 一Ｊ＜Ｈ＞＋ Ｐ ，其中Ｐ一（１，１，…，１） ∈尺 ，根据ｅ＞０是任意的，使得ｐ（Ｊ ）＜１，显然 为非负矩阵，再根据Ｐｅｒｒｏｎ－Ｆｒｏｂｅｎｉｕｓ定理＿１ 知存 在正向量 ∈Ｒ ，使得Ｊ 一ｐ￡ 。 令（ ，Ｎ ，Ｅ ）（是一１，２，…，ｒ）和（Ｄ—Ｌ ，Ｕ ， Ｅ）（ 一１，２，…，ｒ）为矩阵Ａ的块多重分裂和块三 角多重分裂，对应地可得到： 对于ＭｓＢＭ方法，下式成立 （ ＋ ）ｚ 一Ｎ ＋（ｎ—Ａ）Ｉ ｚ Ｉ一弼 （１．４） 对于ＭＳＢＭＡ０Ｒ方法，下式成立 （０Ｏ＋Ｄ一 ＾）ｚ ＝＝＝［（１一ａ）Ｄ＋ （口一ｆ１）Ｌ ＋ａＵ ］ｚ ＋ （ 一Ａ）Ｉ ｚ Ｉ一婀］ （】．５） 下面讨论ＭＳＢＭ和ＭＳＢＭＡＯＲ的收敛性 定理１ 令Ａ∈Ｌ （ １，，２２，…， ）为块 Ｈ （Ｐ，Ｑ）矩阵，Ｈ∈ （Ｂ１ （ＰＡＱ），令（Ｍ ，Ｎ ， Ｅ ）（愚一１，２，…，ｒ）和（Ｄ—Ｌ ，Ｕ ，Ｅ ）（ 一１，２， …，ｒ）为块Ｈ矩阵的块多重分裂和块三角多重分 裂，假设ｙ＞０且ｎ为正的块对角矩阵，且有ｎ≥ Ｄ（Ｈ）和ｄｉａｇ（Ｏ）一ｄｉａｇ（Ｄ（Ｈ））。 （１）如果Ｈ一 一Ｎ （愚一１，２，…，ｒ）为Ｈ一 致分裂，（Ｈ）一Ｄ 一Ｂ Ｈ ，那么按ＭＳＢＭ方法产 生迭代序列｛ｚ ｝ 。收敛到ＬＣＰ（ｑ，Ａ）关于任意 初值 ∞ ∈Ｒ 的唯一解 。 （２）如果（Ｈ＞一（ ）一［ ］一［ ］＝＝＝Ｄ 一 Ｂ＜Ｈ＞，ｋ＝：＝１，２，…，ｒ那么按ＭＳＢＭ—ＡｏＲ方法产生 的迭代系列｛２ ｝７。ｎ。收敛到ＬＣＰ（ｑ，。Ａ）关于任意 １ 初值 ∞ ∈Ｒ阜的唯一解 ，其中０＜ ≤ａ＜ 。 ｜Ｄ（Ｈ＞ 证明 （１）因Ｈ∈ （ＰＡＱ），则＜Ｈ＞：：＝ （ＰＡＱ），又Ａ∈Ｌ （ ， 。，…， ）为Ｈ ’（Ｐ，Ｑ）矩 阵，故Ｈ∈Ｌ （ １， ２，…， ）为Ｈ ’（Ｊ，Ｄ，Ｈ一 一Ｎ （ 一１，２，…，ｒ）为Ｈ一致分裂，（Ｈ＞一 Ｄ（Ｈ）一Ｂ＜Ｈ＞，则（Ｈ）≤＜Ｍ ）≤Ｄ（Ｈ），因此（ ） 为Ｍ矩阵，从而ｎ＋Ｍ ，ｋ＝＝＝１，２，…，ｒ，为块Ｈ矩 阵，且ｄｉａｇ（ｇ／）一ｄｉａｇ（Ｄ（Ｈ））。故有 ＜ ＋Ｍ ）一＜ ＞＋（ ）・Ｅｎ—Ｄ（Ｈ）］一 （ｎ＞一（Ｄ（Ｈ）＞一（力）一Ｄ＜Ｈ＞ 即 ［（ ＋Ｍ ） ］≤＜ ＋ ＞ 一（＜ｎ）＋＜Ｍ ）） 通过式（１．２）和（１．４）相减得 一ｚ 一（ｇ２＋Ｍｋ） ［Ｎ （ｚ ’一ｚ ）＋ （ —Ｈ）（Ｉ ｚ ｌ—ｌ ｚ Ｉ）］ 又∑Ｅ ＝１ 一ｚ ”，则 ｚ‘ｍ 一３２ 一∑Ｅ （ｎ＋ ）一 ［ （ｚ‘ 一ｚ ）＋ ＾一１ （ —Ｈ）（１ ’Ｉ—ｌ ｚ １）］ 从而有 ［ｚ ”一ｚ ］≤ ∑Ｅ＝１ Ｅ ］［（ｎ＋ ）～ＥＥＮ ］［（ｚ‘ 一ｚ ）］＋ ［（ —ＨＩ（Ｅｘ ］一［ｚ ］≤ ｛ＥＮ ］＋Ｅ（ｎ—Ｈ］｝［．ｚ 一 ］≤∑ＥＥ ］［（ ）＋（ ）］一 ｛［ ］＋ ＾＝１ ・３１０・ 南昌大学学报（理科版） ２０１３正 ［（ｎ—Ｈ］｝［ｚ 一３２ ］：一Ｈ ＢＭ［ｚ 一 ］ 又Ｈ—Ｍｋ—Ｎ （忌一１，２，…，ｒ）为Ｈ一致分 Ｈ Ｂ 裂，则 （Ｈ）一（ ＞一［ ］，（Ｈ＞一Ｄ＜ ）一Ｂ（Ｈ） ［Ｎ Ｉ一（Ｍ ＞一（Ｈ）一＜Ｍ ）一Ｄ＜Ｈ＞＋Ｂ＜Ｈ） 根据Ｅ 和［・］的定义知∑［ ］一Ｉ ｏ从而有 ∑［ ］（（ｎ）＋（ ））一 ｛［ ］＋ 一１ ［ —Ｈ］｝≤∑［Ｅ］（（ｎ）＋（ ）） ｛＜ ）一 ｛一１ Ｄ（ｍ＋Ｂ（Ｈ）＋＜ｎ＞一Ｄ（Ｈ）＋Ｂ《Ｈ）｝≤ ，一２∑［ ］（＜ｎ＞＋（ ））－１ Ｄ Ｈ）（Ｊ—Ｊ）≤ ＾一ｌ Ｊ一２∑［Ｅ ］（（ｎ＞＋（一 ））＿。Ｄ （ 一Ｊ ） ｋ—ｌ ［ Ｈ １Ｊ 由Ｐｅｒｒｏｎ—Ｆｒｏｂｅｎｉｚ １ｊ广●Ｌ ｕｓ定理知，存在正向量 ∈Ｒ 使得 时 ｚ ｍ 一— ｚ ｚ ］ ］ ＜Ｍ ＞）一 Ｄ（］ Ｈ、（卜一Ｊ ） 记Ｄ ＝ｄｉ≤ ａｇ（Ｍ￣），其中Ｄ 和ｎ为正的块对角 ≤ 矩阵，则有 （＜ｎ）＋＜∑一ｒＬ ∑ ｒＬ Ｅ ＞） ≥Ｅ ］Ｊ （（ｎ＞＋（Ｄ ＞） ＞０， １Ｊ ｒＬ ∑Ｅ （＜ｎ＞＋（ ＞）一１ Ｃ： ＞ｏ，志一１，２，…，ｒ 又因为 ＋ ＜１，故 ＋ Ｄ Ｈ ｕ一Ｄ ＜ 一２Ｈ （１一ＰＥ）∑［ｌ －Ｅｋ－ｌ（＜Ｏ＞＋ 一 一Ｄ ）～Ｄ（Ｈ）一 Ｈ ＢＭ ＜ 因此ｆ０（ＨＭｓＢＭ）＜１，则得到第一个结论。 下面证明（２），类似（１）的证明方法。 “ 一（ ＋ 一 ）一 ［［（１一ａ） ＋（ ）Ｌ ＋ｄ ］（ｚ ’一ｚ ）＋（ —Ｈ）（ｆ ｚ‘ ’ｌ—Ｉ ｚ １）］ Ｅ （ ＋ 一 ）一 ［［（１一 ａ） ＋（ａ— ） ＋ａ—Ｕ ］（ｚ（ 一ｚ ）＋（ｎ～Ｈ）（Ｉ 上式两边取绝对值并且放大 州 一 ］ ≤∑［＝１ Ｅ］［（ ＋Ｄ－ ）一 ］［１ ｌ—ａ ｌ［ ］＋（ａ一 ）［ ］＋口［ ］］・［（ ‘ 一ｚ ］ ＋［ —Ｈ］（［ｚ ］一［ ］） ） ］１－１－Ｉ １一ａ Ｉ［Ｍ ］＋（ａ一卢）［ ］＋ ］＋［Ｑ ≤ ］） （Ｉ １一ａ ｌ［２ 一 ］＋（ａ－ｐ）ＥＥ ］＋ ］十［ —Ｈ］）［ｚ 一－ｚ ］一Ｈ ＢＭ＾（垠（ａ， ）［ｚ 一ｚ ］ 由于 ∑ ［］ Ｂ 一［ ］＋［， ］，［ ］≥Ｄ 故有 Ｃ： Ｈ Ｍ＾０Ｒ（＋ ａ， ）一∑［Ｅ ］（ａ（ｎ＞＋ ＝１ Ｄ ｍ一 Ｌ ］） （Ｉ １一ａ Ｉ［Ｄ］＋ （ａ一 ）［Ｌ ］＋ Ｕ ］＋［ｎ—Ｈ］）一 ∑［１ Ｅ］（ａ（ｎ）＋Ｄ 一 ］）一 （Ｉ １一ａ Ｉ［ ］＋ （（ｎ）一Ｄ ）一 ］＋２０＃ ）≤Ｉ一 ∑［Ｅ ］（ａ＜ｎ＞＋Ｄ 一 Ｌ］） （（１＋ａ一 ＝ｌ １一ａ Ｉ）Ｄ（Ｈ）一２ Ｂ（Ｈ））≤ Ｊ一∑［ ］（ａ（ｎ）＋Ｄ Ｈ）一 ］）一 Ｄ｛ （（１＋ａ一 ＝１ １ １一Ｏｔ １）ｊ一２ ）≤ ∑［Ｅ ］（ａ（ｎ）＋Ｄ Ⅲ一 ］）Ｄ （（１＋ １ ａ—Ｉ ｌ—ａ Ｉ）Ｊ一２ｏｄ ） Ｈ ｅＭＡ呻（ａ， ） ≤ 一∑［ ］（ａ（ｎ）＋Ｄ Ｈ）一 ＝１ Ｌ ］）～Ｄ （（１＋ａ—ｌ １一ａ １） 一２Ｍ ） ≤ ∑［Ｅ ］（口＜ ＞＋Ｄ 一 ］）～Ｄ 其中 一１＋ａ—ｌ １一口Ｉ一２ 。 由于０＜ａ＜ ，则０：一１＋ａ～Ｊ １一ａ ｌ一２叩 ｐ（Ｈ＞ ＞０。 根据矩阵谱半径的连续性，取足够小的ｅ使得 ＞０。 ＨＭＳＢＭＡ （口，卢） ≤ 一 ∑［Ｅ ］（ａ＜ ）＋ ＝１ Ｄ（Ｈ）一 Ｌ＾］）～Ｄ（Ｈ） ＜ 因此ｌＤ（Ｈ ｅＭＡＯＲ（ ， ））＜１，即第二个结论成 立。 定理２ 令 ∈Ｌ （ ｌ， ２，…， 。）为块 Ｈ ”（Ｐ，Ｑ）矩阵，Ｈ∈ｎ ”（ＰＡＱ），令（ ，一Ｎ ， Ｅ ）（愚一１，２，…，ｒ）和（ 一 ， ，Ｅ ）（志一１，２， 第４期 汪 祥等：线性互补问题基于模同步块多重分裂方法的收敛性 ・ ３１ｌ ・ …，ｒ）为块Ｈ矩阵的多重分裂和块三角多重分裂， 假设ｙ＞０， 为正的块对角矩阵且ｎ≥Ｄ（Ｈ）， ｄｉａｇ（，ｆ２）＝ｄｉａｇ（Ｄ（Ｈ））。 ∑ＥＥ ］［（Ｄ（Ｈ）一 （ ｋ １ ＋ Ｄ（Ｈ）一 ）一 ］｛［Ｄ（Ｈ）一 ］＋［（Ｄ（Ｈ）一 ｚ 一 ｚ — ｌ≤ （１）如果Ｄ（ ）＝＝＝Ｄ（Ｈ），（＜Ｈ＞＞一＜（ ＞）一 ［Ｄ（Ｈ）一 ］一卜一Ｂ＜＜Ｈ）），（足一１，２，…，ｒ），那么按 ＭＳＢＭ方法产生迭代系列｛２ ’） 。收敛到ＬＣＰ（ｑ， Ａ）关于任意初值 ∞ ∈Ｒ罩的唯一解 。 ∑［Ｅ］［（（Ｄ（Ｈ）一 ）＞＋（（ ＞））一 ］｛［Ｎ －１＋ １ ［（Ｄ（Ｈ） 令 —Ｄ（Ｈ） Ｈ］）Ｊ ｚ‘ 一ｚ （２）如果＜（Ｈ＞＞一Ｊ一［＿＿ Ｌｋ］一［Ｄ－ Ｕｋ］一Ｉ —Ｂ．ｍ），ｋ一１，２，…，ｒ，那么ＭＳＢＭＡ０Ｒ方法产生 的迭代系列｛ｚ ｝ 。收敛到ＬＣＰ（ｑ，Ａ）关于任意 初值２∞’∈Ｒ 的唯一解 ，其中０＜ ≤ａ＜ １ ——ｏ （‘Ｈ） 证明 （１）由Ｈ∈ｎ（ＢＪ”（ＰＡＱ），＜（Ｈ）＞一 （（ ＞＞一Ｉ－Ｄ（Ｈ）＝ ］一Ｉ—Ｂ Ｈ＂，Ｄ（ ）＝＝＝ Ｄ（Ｈ），则Ｍ ∈Ｌ （７ｚ１， ２，…，ｎ ）且（＜Ｈ＞＞≤ （＜一／ＶＬ＞＞≤ ，即 为Ｈ （工，Ｄ矩阵。记 一 Ｄ（Ｈ）＿。Ｎ ，－， 一Ｄ（Ｈ） ，志＝１，２，…，ｒ由前 面的引理可得 ［＿， ］≤＜（ ＞）一 一（（ ＞）一 又 ≥Ｄ（Ｈ），ｄｉａｇ（Ｏ）＝＝＝ｄｉａｇ（Ｄ（Ｈ））。 则有 ＜ ＋ ）一（ｎ＞＋＜Ｍｋ）・［ ～Ｄ（Ｈ）］一＜Ｄ） 一（Ｄ（Ｈ）＞＝（ｎ＞一Ｄ＜Ｈ＞ ［（ｎ＋＿， ）一 ］≤（（ｎ＋－， ）＞一ｔ一（＜（ ））＋ （＜一ｌＶＬ＞＞）～ 根据（１．３）和（１．５）有 ｆ（力＋Ｍ ）ｚ ＝＝＝Ｎ ｚ ＋（ｎ—Ｈ）Ｉ ｚ Ｉ一为 【（力＋ ）ｚ 一Ｎ ＋（力一Ｈ）Ｊ Ｉ—ｙ口 上式两式相减得到 （ｎ＋ ）（ ’一ｘ ）一Ｎｋ（ｚ 一ｘ ）＋（ —Ｈ）（Ｉ ｌ—Ｉ ｘ．Ｉ） 又∑Ｅｋｘ — ‘ ”，则 １ （ｚ‘ ・ ’一ｚ ）＝＝＝ 一 Ｘ ）＋（ 一Ｈ）（１ Ｉ—Ｉ ｘ Ｉ）） 又∑［１ Ｅ］＝ ，则 一 ｔ≤塞１ｋ叫ｃ～ ｃ ＋ ））一 （Ｄ（Ｈ）一 （ ＋ 一Ｈ））］Ｉ ｘ‘ 一 １≤ Ｈ ｅＭ： 一 ∑［ ］（（（Ｄ（Ｈ）一 ）＞ ＋ （（＿， ＞＞）一 ］｛［Ｎ ］＋［（Ｄ（Ｈ）一 ｎ—Ｄ（Ｈ）一 Ｈ］） 又 ｒ Ｈ Ｍ： 一 ∑［Ｅ ］（（（Ｄ（Ｈ）一 力）＞ ＋ ＜＜ ＞））一 ］｛［Ⅳ ］＋［（Ｄ（Ｈ）一 一Ｄ（Ｈ）一 ＨＩ｝ ≤∑［Ｅ ］（＜＜Ｄ（Ｈ）一 ｎ）＞＋（（＇， ＞））－１］｛（（ ＞） 一 ＋Ｂ＜ Ｈ））＋［（Ｄ（Ｈ） ～Ｄ（Ｈ） Ｈ］｝一 ∑［最］（＜＜Ｄ（Ｈ）一 ｎ＞＞＋（＜ ＞＞）一 ］｛（（ ＞＞一Ｉ ｋ＝１ ＋Ｂ＜（Ｈ）＞＋（＜Ｄ（Ｈ） ｎ）＞一Ｊ＋Ｂ（（Ｈ）＞｝一 一 ２∑［Ｅ］（（（Ｄ（Ｈ）一 ｎ＞＞＋＜＜ ＞））＿。］｛Ｉ－－Ｂ （ ） ｋ＝ｌ —Ｉ一２∑［Ｅ ］（（（Ｄ（Ｈ）一 ｎ＞＞＋＜（ ＞＞）一 ］｛ｊ一 ＾一１ Ｊ ｃ ｃ Ｈ） ） ≤ Ｉ 一 ２∑［Ｅ ］（＜（Ｄ（Ｈ）一 ）） ＋ ＝１ ＜＜ ））） ］｛Ｊ一－，Ｅ（（Ｈ））） 其中Ｊ （＜Ｈ））一Ｊ（＜Ｈ））＋ Ｐ ，ｅ一（１，１，…，１）∈ Ｒ ，显然Ｊ Ｈ＂为非负矩阵，则存在正向量 ，使得 ．， ＜（Ｈ）＞ 一ＰＥ（（Ｈ）） ，ＰＥ（（Ｈ）） 一ｐ（Ｊ Ｈ））），因此有 Ｈ Ｍ ≤ 一２∑［Ｅ ］（＜（Ｄ（Ｈ）一 ｎ）＞＋ ＾＝１ （（Ｍ ＞＞） ］｛Ｊ一，Ｊ ＜（Ｈ）＞）＇ＵＥ＝ 一２（１一 ＰＥ Ｈ） ）∑［ ］（＜＜Ｄ（Ｈ）一 ｎ＞＞＋（（ ＞））－１ ＝１ 记Ｄ 一ｄｉａｇ（一Ｍｋ），ｋ一１，２，…，ｒ。又 和 Ｄ（Ｈ） 是正的对角矩阵，则下式成立： （（（Ｄ（Ｈ）一 ｎ）＞ ＋ （＜ ）＞）一 ≥ （＜（Ｄ（Ｈ）一 ｎ＞＞＋（（Ｄ ）＞）一 ∑（（（Ｄ（Ｈ） ＾＝１ ‘‘ ”＼ ，， 有 Ｈ Ｈ ＢＭ ≤ ２（１ ・ ３１２ ・ 南昌大学学报（理科版） ２Ｏ１３年 Ｐ￡（ ） ）∑［ｋ一１ Ｅ ］（＜（Ｄ（Ｈ）一 ｎ＞）＋（（Ｄ ）＞）一 ＜ 即』Ｄ（Ｈ ＢＭ）＜１。故按ＭＳＢＭ方法产生迭代系列 ｛ｚ ｝ 。收敛到ＬＣＰ（ｑ，Ａ）关于任意初值ｚ∞’Ｅ Ｒ 的唯一解 。 （２）由结论（１）和定理１的证明，类似可证（２）。 参考文献： ［１］ ＣＯＴＴＬＥ Ｒ Ｗ，ＰＡＮＧ Ｊ Ｓ，ＳＴＯＮＥ Ｒ Ｅ．Ｔｈｅ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ Ｐｒｏｂｌｅｍ［Ｍ］．Ｓａｎ Ｄｉｅｇｏ：Ａｃａｄｅｍｉｃ Ｐｒｅｓｓ，１９９２． ［２］ ＢＡＩ Ｚ Ｚ．Ｍｏｄｕｌｕｓ—ｂａｓｅｄ Ｍａｔｒｉｘ Ｓｐｌｉｔｔｉｎｇ Ｉｔｅｒａｔｉｏｎ Ｍｅｔｈｏｄｓ ｆｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ Ｐｒｏｂｌｅｍｓ［Ｊ］． Ｎｕｍｅｒｉｃａｌ Ｌｉｎｅａｒ Ａｌｇｅｂｒａ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０，１７： ９１７－９３３． ［３１ ＬＥＥＮＡＥＲＴＳ Ｄ Ｍ Ｗ，ｖａｎ Ｂｏｋｈｏｖｅｎ ＷＭＧ．Ｐｉｅｃｅｗｉｓｅ Ｌｉｎｅａｒ Ｍｏｄｅｌｉｎｇ ａｎｄ Ａｎａｌｙｓｉｓ［Ｍ］．Ｄｏｒｄｒｅｃｈｔ：Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ，１９９８． ［４］ ＭＵＲＴＹ Ｋ Ｇ．Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ，Ｌｉｎｅａｒ ａｎｄ Ｎｏｎｌｉｎｅａｒ Ｐｒｏｇｒａｍｍｉｎｇ［Ｍ］．Ｂｅｒｌｉｎ：Ｈｅｌｄｅｒｍａ ｎｎ－ Ｖｅｒｌａｇ，１９８８． ［５］ Ｄ０ＮＧ Ｊ Ｌ，ＪＩＡＮＧ Ｍ Ｑ．Ａ Ｍｏｄｉｆｉｅｄ Ｍｏｄｕｌｕｓ Ｍｅｔｈｏｄ ｆｏｒ Ｓｙｍｍｅｔｒｉｃ Ｐｏｓｉｔｉｖｅ－ｄｅｆｉｎｉｔｅ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉ— ｔｙ Ｐｒｏｂｌｅｍｓ［Ｊ］．Ｎｕｍｅｒｉｃａｌ Ｌｉｎｅａｒ Ａｌｇｅｂｒａ ｗｉｔｈ Ａｐｐｌｉ一 ｃａｔｉｏｎｓ，２００９，１６：１２９—１４３． ［６３ 白中治．并行矩阵多分裂块松迭代算法［Ｊ］．计算数学， １９９５，３：２３８—２５２． ［７３ ＢＡＩ Ｚ Ｚ，ＺＨＡＮＧ Ｌ Ｉ ．Ｍｏｄｕｌｕｓ～ｂａｓｅｄ Ｓｙｎｃｈｒｏｎｏｕｓ Ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ Ｉｔｅｒａｔｉｏｎ Ｍｅｔｈｏｄ ｆｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅ— ｍｅｎｔａｒｉｔｙ Ｐｒｏｂｌｅｍｓ［Ｊ］．Ｎｕｍｅｒｉｃａｌ Ｌｉｎｅａｒ Ａｌｇｅｂｒａ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１２，ＤＯＩ：１０．１００２／ｎｌａ．１８３５． Ｅ８］ ＢＡＩ Ｚ Ｚ，ＥＶＡＮＳ Ｄ Ｊ．Ｍａｔｒｉｘ Ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ Ｍｅｔｈｏｄｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ ｔｏ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔ—。ｔａｒｉｔｙ Ｐｒｏｂ—＿ ｌｅｍｓ：ｐａｒａｌｌｅｌ Ｓｙｎｃｈｒｏｎｏｕｓ ａｎｄ Ｃｈａｏｔｉｃ Ｍｅｔｈｏｄｓ［Ｊ］． Ｒ６ｓｅａｕｘ ｅｔ Ｓｙｓｔ６ｍｅｓ Ｒ６ｐａｒｔｉｓ：Ｃａｌｃｕｌａｔｅｕｒｓ Ｐａｒａｌｌｅｌ６ｓ， ２００１，１３：１２５－１５４． ［９］ ＢＡ１ Ｚ Ｚ，ＥＶＡＮＳ Ｄ Ｊ．Ｍａｔｒｉｘ Ｍｕｌｔｉｓｐｌｉｔｔｉｎｇ Ｒｅｌａｘａ— ｔｉｏｎ Ｍｅｔｈｏｄｓ ｆｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ Ｐｒｏｂｌｅｍｓ ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｍａｔｈｅｍａｔｉｃｓ， １９９７，６３：３０９－３２６． ［１０］ ＢＡＩ Ｚ Ｚ．Ｍｏｄｕｌｕｓ—ｂａｓｅｄ Ｍａｔｒｉｘ Ｓｐｌｉｔｔｉｎｇ Ｉｔｅｒａｔｉｏｎ Ｍｅｔｈｏｄｓ ｆｏｒ Ｌｉｎｅａｒ Ｃｏｍｐｌｅｍｅｎｔａｒｉｔｙ Ｐｒｏｂｌｅｍｓ［Ｊ］． Ｎｕｍｅｒｉｃａｌ Ｌｉｎｅａｒ Ａｌｇｅｂｒａ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ，２０１０，１７ ：９１７－９３３． ［１１］ 汪祥，廖旦，王瑞瑞．求解模糊线性方程组的对称加速 超松驰迭代方法，南昌大学学报：理科版，２００９，３３（２）： １Ｏ３—１Ｏ７． ［１２］ ＶＡＲＧＡ Ｒ Ｓ．Ｍａｔｒｉｘ ｈｅｒａｔｉｖｅ Ａｎａｌｙｓｉｓ［Ｍ］．Ｓｐｒｉｎｇｅｒ— Ｖｅｒｌａｇ：Ｂｅｒｌｉｎ ａｎｄ Ｈｅｉｄｅｌｂｅｒｇ，２０００．