线性互补问题的模系矩阵分裂迭代方法外文翻译资料
2022-11-24 03:11
英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
线性互补问题的模系矩阵分裂迭代方法
白中治，张丽丽
计算数学与计算科学研究所科学与工程计算国家重点实验室，中国科学院数学与系统科学研究院，北京100190
摘要：对于线性互补问题，我们将线性互补问题变换为等价的不动点方程组，构建基于其系数矩阵的同步多分裂模系迭代方法。这些迭代方法适用于高速并行多处理机系统。包括多分裂松弛方法，如雅可比、高斯–Seidel，逐次超松弛，和该模型下的特殊情况加速松弛。当系统矩阵是一个矩阵，我们建立模的同步多分裂迭代方法和他们松弛的变体的相
收敛理论。数值结果表明，这些新的迭代方法可以实现高效并行的计算效率。
关键词：线性互补问题；模数法；矩阵多分裂；连续收敛松弛
1引言
线性互补问题是一类重要的优化问题，在线性规划、凸二次问题、流体动力学的自由边界问题及网络平衡问题等许多科学计算和工程运用中有广泛的应用。对于这类问题的所涉及的矩阵往往是大型稀疏矩阵，在系数矩阵的分裂迭代的基础上可以将线性互补问题转化为不动点迭代方程来求解。
设和是n维实向量空间和n x n 的实矩阵， 线性互补问题是求向量r，满足
这里，，表示向量z的转置矩阵。
为了快速而有效地求解线性互补问题，Bai在文中给出了基于模分裂迭代方法，包括一些特殊的基于模松弛方法如Jacobi，Gauss．Seidel，SOR和AOR方法，还给出了模迭代的一般框架形式，修正模迭代法冲及修正牛顿方法，理论分析和数值实验已经证明了用基于模松弛迭代法来研究线性互补问题要比投影松弛法和修正迭代法更加好。为了适应现代高速多程序环境的计算要求，Bai和Zhang在基于模分类迭代法和线性方程系数矩阵的多重分裂迭代法基础上进一步在文中给出了基于模并行多重分裂迭代法(MSM)，该方法比Machida和Bai的并行多重分裂迭代法计算效果更好，因为该方法在它的每一步迭代步骤中，只需要求解线性方程的子系统而不是线性互补的子问题，适当地选取系数矩阵的多重分裂，可得到一系列的MSM的松弛迭代法，如Jacobi，Gauss-Seidel，SOR和AOR等，特别地，当系数矩阵是对角项是正的H矩阵时，给出了其收敛性分析，并且数值实验表明在实际运行中MSMSOR，
MSMGS和MSMJ方法可以获得高速并行计算效率。
本文结构如下：
第二部分我们提出了一些必要的公式和有用的引理。第三部分我们建立了MSM迭代方法。第四部分证明这些收敛同步并行多分裂迭代法。第五部分给出数值结果。第六部分作出相关总结。
2公式和引理
设是1~n的正整数集，给定两个实矩阵，若()，有，，如果，那么就是非负的（正）矩阵，其中，是矩阵的绝对值。是非负矩阵，表示的转置，表示矩阵的谱半径。这些定义都分别在向量空间中。
定义
因为满足，那么，且,如果，是任意正向量，对任意的有.
因为，其比较矩阵定义为
如果它的非对角元素是非正的，则方阵称为矩阵。记。如果且则非奇异矩阵称为矩阵如果比较矩阵是一个矩阵，则称为矩阵，如果矩阵的对角项都是正的，则称之为矩阵，设是一个矩阵，是一个正对角矩阵，，若有，，有是一个矩阵。
给定一个矩阵，设是，如果是一个非奇异矩阵，则称为矩阵的一个分裂矩阵，如果,则该分裂是收敛的，如果是一个矩阵，则分裂称为分裂，如果,则分裂称为一致分裂；显然，如果是分裂，且和是矩阵，如果它是一致分裂，并且是矩阵，那么它是分裂并且是收敛的。
引理2.1
是一个矩阵，是的一个对角矩阵，，那么可以得到
（i）：是非奇异的。
（ii）：。
（iii）：是非奇异，.
如果系数矩阵是矩阵，线性互补问题有唯一解，这一定理我们将在后面进行证明，先叙述下面的定理
引理2.2
是一个矩阵，对任意的，线性互补问题有唯一解，通过利用向量的模，可以等价的转化为不动点方程的解。此结果我们将在下文精确陈述。
引理2.3
令是矩阵的分裂，为正对角矩阵并且那么对于线性互补问题对以下两种情况成立。
- 如果是线性互补问题的解；则满足下面的隐式不动点方程：
（1）
- ：如果满足（1）中的隐式不动点方程 则
是线性互补问题的解。
3多重分裂迭代法
设是一个正向量，，是系数矩阵的一个多分裂，是非负对角矩阵满足（单位矩阵），那么 三元组集就称为矩阵的一个多分裂，矩阵称为权重矩阵，给定正对角矩阵为，正常量为，由引理2.3，我们能直接得到：
如果满足隐式不动点方程
（2）
有
（3）
是线性互补问题的一个解。
通过上面的（2）和（3）对的解法，我们能推出下面的MSM迭代法。
定理3.1（线性互补问题的模系同步多分裂迭代法）
设就称为矩阵的一个多分裂，给定初始向量到迭代序列是收敛的，计算
根据
当，求解线性子系统
（4）
MSM迭代法具有很好的并行计算性质，能够在多重处理器系统上实现，由权重矩阵的零对角元素对应的分量不需要计算，所以在第次迭代中每一个处理器只需要求解一个小规模的线性子系统，然后将求解结果通过点对点通信模式传递给其他处理器，我们通过合理的选择分裂矩阵和权重矩阵使得多处理器系统中每一个处理器承载的任务都比较均衡，从而确保MSM迭代法能够达到较高的并行计算效率，显然，当时，MSM迭代法即模系矩阵分裂迭代法。
在3.1的迭代法中没个处理器都必须解决一个线性子系统，这使得MSM迭代法具体应用中不太方便下面我们将讨论几种特殊的方法，以方便实际应用中的实现。
由此，设，设是严格的下三角矩阵，是零对角矩阵，且满足是非对角矩阵且满足（单位矩阵），则称为矩阵的三角分裂，其中称为权重矩阵。
设
其中是松弛参数，则局部解可求解三角线性系统
而得到。
我们称其为模系同步多分裂快速松弛迭代法，简称为MSMAOR迭代法。
对于MSMAOR迭代法，每一个处理器在每一次迭代中治需要求解一个三角子系统，通过地推即可精确求解，在实际应用中，恰当地选取松弛系数可使得MSMAOR迭代法的收敛性大为完善。
4 收敛理论
在这一节中，我们将建立在第三节中描述的MSM迭代法的收敛理论及其轻松变体，当线性互补问题的系数矩阵是一个矩阵时的情况。
为此，假设是的一个解，由引理2.3我们得到
满足隐式定点方程（1）,对于由MSM和MSMAOR迭代法所产生的迭代序列，有当且仅当时，迭代序列收敛，这足以证明的收敛性。
因为是一个矩阵，，明显的，,此外，由引理2.1（iii），设的系数均为1的向量，是任意小的数。则有由Perron-Frobenius 定理知，存在一个正向量使得
令 ，是矩阵的一个多分裂和三角分裂，然后我们可以打出如下结论：
- 对于MSM迭代法有：
（6）
（b）对于给定的MSMAOR迭代法有：
， （7）
由此，我们证明了MSM和MSMAOR迭代法的收敛性。
定理4.1
设是矩阵，，设，是矩阵的一个多分裂和三角分裂，明显地，假设且正对角矩阵满足
（i）设是的一个相容分裂，有MSM的迭代序列对线性互补问题有唯一解，对任意的初始化向量成立。
（ii）设满足有MSMAOR的迭代序列对线性互补问题有唯一解，对任意的初始化向量成立。 关系参数满足
证明：（4）-（6）推出
得出关于MSM迭代法的误差如下
（8）
同理（5）-（7）得
（9）
显然（8）和（9）之间的误差就是MSM迭代法和MSMAOR迭代法之间的误差。
我们首先证明（1）的有效性。设是矩阵的矩阵的相容矩阵是一个正对角矩阵，，因此，是由定理2.1（ii）有
（10）
- 两边取绝对值，利用（10）估计不等式，相似地，我们可以得到
（11）
其中 （12）
又设是相容分裂也即
又有
（13）
由（12），（13）得出
=
=
= （14）
设，因为且是一个正对角矩阵，有
（15）
且 （16）
当时，（14）-（（15） （16））得
、
因此，由 （14）（12）我们能立即得到MSM迭代法得到的序列，对任意的初始向量线性互补问题有唯一解。
现在，我们证明（ii）的有效性，（9）两边取绝对值，同上。
考虑不等式类似地，有
（17）
其中
（18）
因为且
根据（18）有
=
推出
其中
因为推出
由于谱半径的连续性，我们可以取足够小的满足推出
因此， 由（17），（18）得到MSMAOR迭代法得到的序列，对任意的初始向量线性互补问题有唯一解。
在定理4.1的条件下，MSMGS和MSMJ方法是收敛的，当参数满足
此外,当时，MSMOAR的收敛域大于MSMGS和MSMJ的收敛域。
5数值结果
在本节中，我们使用了两个数值例子来检查并行计算效率。定义MSM松弛法，用和来快速的解决线性互补问题。另外，我们用表示并行计算机处理器的迭代次数。
我们在C和MPICH2写代码，在PC集群上进行实验，每个计算节点由两x5550处理器（四个处理器，每个处理器2.67 GHz）具有24 GB的内存，并采用点对点通信的方式来交换处理器消息。
在具体的实现中，我们采用权重矩阵，计算结果均匀的分布在个处理器上。为此，我们定义
，
其中的大小由矩阵给出
是两个非负整数，满足，关于系数矩阵的三角分裂，设是的严格下三角子矩阵，满足，所有迭代方法都是从初始向量最终当剩余误差满足
其中最小值是最小分量形式。另外，设，选择参数使得总迭代的数目达到最小。
例5.1
给定
，其中 n是一个正整数。是一个对角线为4，非对角线为-1的矩阵。
这里我们可以建立表格比较MSMJ,MSMGS,MSMOAR三种迭代法之间的时间消耗，并行计算的效率，通过建立表格比较我们发现当参数时，达到最优。
下面是我们关于表格数据的一些讨论：
（i）通过观察所有的，我们发现，就电脑的并行效率来说，MSMOAR迭代法是最快的而MSMGS是最慢的，MSMJ是最接近的；
（ii）取固定值，MSMJ,MSMGS,MSMOAR迭代法的计算效率减少为一半而变为原来的两倍。
（iii）MSMJ,MSMGS,MSMOAR迭代法的效率达到最高时有对应的，包括在时MSMJ达到最高例外。
（iv）几乎所有的计算效率超过0.5，其中一些甚至超过1
（v）对于每一个方法对应的每一个，并行效率并不是单调的，它往往取决于处理器的数量，这可能是由于数据大小，内存系统、通信方式和工作负载重叠与处理器型号不同。
（vi）对于每一个方法对应的每一个，MSMAOR迭代法的迭代次数的最优参数由于系统矩阵A的特殊结构导致对于不同的处理器编号保持不变。因为在每个迭代步骤中的近似相对于数值不改变。
涉及并行效率的详细分析，当，。对于每一个，MSMJ和MSMGS的效率是相等的。即图1所显示的。上面三个图分别表示了例5.1的msmj，msmgs，和msmsor迭代方法的相关数据。左：中：右。
显然，MSMAOR迭代法对应参数明显在减小，当时，MSMAOR迭代法是最接近的，而MSMJ是最有效的，当时，，MSMAOR，MSMJ都比MSMGS最有效的。当时，MSMGS是最接近的而MSMAOR是最有效的。，对每一个，MSMJ和MSMGS的效率都是相同的。两者都显著小于MSMAOR；当时，对每一个，MSMAOR是最接近的，MSMJ是最有效的；当，MSMAOR是最接近的，MSMGS是最有效的。当，对于所有的，MSMJ的效率低于MSMGS，MSMAOR仍然是三种分裂迭代法中最有效的。
另外。此外，对于，MSMJ，MSMGS和MSMSOR的并行计算效率从到以及从到之间有显着的跳跃。我们看到MSMJ和 当和的MSMGS超过1.0，当和可能是由PC集群的内存系统引起时，MSMSOR的效率大于1.0。 通过比较执行时间相对于和，进一步证实了这一观察结果。当和，对于每种方法，当问题大小变成四倍时，在计算时间内，我们看到增加约15和10倍 分别从到更大。 对于尺寸为和的问题，也会出现类似的现象。
例5.2
LCP（q，A）从九点有限差分近似得到，网格大小为的均匀网格，以下自由边界问题建模
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[26430]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
