求解一类隐式互补问题的加速模系矩阵分裂迭代法

摘要

构造了求解一类隐式互补问题的加速模系矩阵分裂迭代法。理论分析建立了新方法在系数矩阵为H₊⁃矩阵时的收敛性质。数值实验结果表明新方法是行之有效的，并且加速模系矩阵分裂迭代法在迭代步数和时间上均优于传统的模系矩阵分裂迭代法。

关键词

矩阵分裂; 加速模系迭代法; 隐式互补问题

1 背景介绍

互补问题广泛地出现在科学和工程的许多应用中，如弹性接触、经济运输、流体动力学的边界问题、凸二次规划以及反问题等^［1］，因此受到越来越多研究者的关注和研究，并已经取得了丰硕的成果。本文考虑如下一类隐式互补问题^［2］： 求向量$\mathit{u}$和$\mathit{r}\in {\mathbf{R}}^n$满足

$$\begin{array}{l}\mathit{u}-f(\mathit{u})\ge \mathrm{0},\mathit{r}≔\mathit{M}\mathit{u}+\mathit{q}\ge \mathrm{0},\\ (\mathit{u}-f{(\mathit{u}))}^{\mathrm{T}}(\mathit{M}\mathit{u}+\mathit{q})=\mathrm{0}\end{array}$$

（1）

式中：$\mathit{M}\in {\mathbf{R}}^{n\times n}$为给定矩阵；$\mathit{q}=\left(q_{\mathrm{1}},q_{\mathrm{2}},\cdots ,q_n\right)\in {\mathbf{R}}^n$为给定实向量；$f$为${\mathbf{R}}^n$到它本身的一个映射。特别地，当函数$f=\mathrm{0}$，问题（1）化为线性互补问题^［3］。

针对线性互补问题，白中治^［4］提出了模系矩阵分裂迭代法，并对系数矩阵为正定或H₊⁃矩阵下迭代法的收敛性进行了分析。由于模系矩阵分裂迭代算法格式简单且收敛速度较快，该方法吸引了众多学者的关注并得到了进一步的研究。如两步模系矩阵分裂迭代法^［5］、广义模系矩阵分裂迭代法^［6］和松弛模系矩阵分裂迭代法^［7］等。为了更快速有效地求解大型稀疏线性互补问题，白中治等^［8］通过引进并行计算技术，构造了模系矩阵同步多分裂迭代法，并建立了此算法在系数矩阵为H₊⁃矩阵时的收敛性分析。夏泽晨等^［9］首次构造了求解非线性互补问题的模系矩阵分裂迭代法，进一步地还有两步模系矩阵分裂迭代法^［10-12］、松弛模系矩阵分裂迭代法^［13］以及加速模系矩阵分裂迭代法^［14-15］等也相继被构造。

李郴良等^［16-17］构造求解隐式互补问题（1）的模系矩阵分裂迭代法和模系矩阵同步多分裂迭代法，并建立了当系数矩阵为正定或H₊⁃矩阵时迭代法的收敛性质。曹阳等^［18］对文献［16］中的模系矩阵分裂迭代法的收敛理论给出了更加完整的证明。王艳等^［19］采用两步模系矩阵分裂迭代法对隐式互补问题（1）进行求解，并且分析了系数矩阵为H₊⁃矩阵时算法的收敛性。曹阳等^［20］同样构造了两步模系矩阵分裂迭代法求解隐式互补问题（1）并且建立了迭代法在系数矩阵为正定或H₊⁃矩阵时迭代法的收敛性质。

郑宁等^［21-22］通过对向量边计算边更替的思想，将线性互补问题转换成了新的隐式不动点方程，提出了加速模系矩阵分裂迭代法求解线性互补问题，并从理论上分析了算法在系数矩阵为正定或H₊⁃矩阵时的收敛性质。通过选择合适的系数矩阵，该方法也可以得到文献［4］中的传统模系矩阵分裂迭代法。为了进一步加快求解隐式互补问题的收敛速度，本文引入对向量边计算边更替的思想，提出了加速模系矩阵分裂迭代法。理论分析建立了新方法在系数矩阵为H₊⁃矩阵时的收敛性质。数值实验表明所提方法是有效的，并在迭代步数和时间上均优于传统的模系矩阵分裂迭代法。

2 加速模系矩阵分裂迭代法

先给出本文讨论中使用的一些记号及基本概念。

给定两个实矩阵$\mathit{M}=\left(m_{ij}\right),\mathit{N}=\left(n_{ij}\right)\in {\mathbf{R}}^{m\times n}$，如果对任意的$\mathrm{1}\le i\le m,\mathrm{1}\le j\le n$都有$m_{ij}\ge n_{ij}\left(m_{ij}>n_{ij}\right)$，则记$\mathit{M}\ge \mathit{N}\left(\mathit{M}>\mathit{N}\right)$。本文，用记号$\left|\mathit{M}\right|=\left(\left|m_{ij}\right|\right)\in {\mathbf{R}}^{m\times n}$表示$\mathit{M}$的绝对值。

令$\mathit{M}\in {\mathbf{R}}^{n\times n}$为一个实$n\times n$矩阵，它的比较矩阵定义为

若对任意$i\ne j$，有$m_{ij}\le \mathrm{0}$，则称$\mathit{M}$为$\mathit{Z}$⁃矩阵。若$\mathit{M}$为非奇异的$\mathit{Z}$⁃矩阵且${\mathit{M}}^{-\mathrm{1}}\ge \mathit{O}$，其中$\mathit{O}$为零矩阵，则称$\mathit{M}$为$\mathit{M}$⁃矩阵。如果为$\mathit{M}$⁃矩阵，则称$\mathit{M}$为$\mathit{H}$⁃矩阵。对于$\mathit{H}$⁃矩阵$\mathit{M}$，有$\mathit{M}$非奇异且。特别地，对角元为正的$\mathit{H}$⁃矩阵称为${\mathit{H}}_{+}$⁃矩阵。

给定$\mathit{M}\in {\mathbf{R}}^{n\times n}$，设$\mathit{M}=\mathit{F}-\mathit{G}$，如果$\mathit{F}$非奇异，则称$\mathit{M}=\mathit{F}-\mathit{G}$为矩阵$\mathit{M}$的一个分裂； 如果$\mathit{F}$是非奇异的$\mathit{M}$⁃矩阵并且$\mathit{G}\ge \mathrm{0}$，则称该分裂为$\mathit{M}$⁃分裂；当是一个$\mathit{M}$⁃矩阵，则称$\mathit{M}=\mathit{F}-\mathit{G}$是一个$\mathit{H}$⁃分裂；如果，则称此分裂为$\mathit{H}$⁃相容分裂。

作变量替换$\mathit{u}-f(\mathit{u})=\frac{\mathrm{1}}{\gamma }(|\mathit{x}|+\mathit{x}),\mathit{r}=\frac{\mathrm{1}}{\gamma }\mathit{\Omega }(|\mathit{x}|-\mathit{x})$和$g\left(\mathit{u}\right)=\mathit{u}-f\left(\mathit{u}\right)$，其中$\gamma$为正常数，$\mathit{\Omega }$为正对角矩阵。假设$g\left(\mathit{u}\right)$可逆，可得$\mathit{u}={\mathit{g}}^{-\mathrm{1}}\left[\frac{\mathrm{1}}{\gamma }(|\mathit{x}|+\mathit{x})\right]$。下面的定理给出了隐式互补问题的等价不动点方程，其对于建立加速模系矩阵分裂迭代算法是至关重要的。

定理  1^［16］     令$\mathit{M}=\mathit{F}-\mathit{G}$为矩阵$\mathit{M}$的一个分裂，给定初始向量${\mathit{x}}^{\left(\mathrm{0}\right)}$，对于隐式互补问题（1），下列结论成立：

1） 如果$\left(\mathit{u},\mathit{r}\right)$是问题（1）的解，则$\mathit{x}=\frac{\gamma }{\mathrm{2}}(\mathit{u}-{\mathit{\Omega }}^{-\mathrm{1}}\mathit{r}-f(\mathit{u}))$满足下列隐式不动点方程：

$$\begin{array}{l}(\mathit{\Omega }+\mathit{F})\mathit{x}=\mathit{G}\mathit{x}+(\mathit{\Omega }-\mathit{M})|\mathit{x}|-\gamma \cdot \mathit{M}\cdot \\ f\left[{\mathit{g}}^{-\mathrm{1}}\left(\frac{\mathrm{1}}{\gamma }(|\mathit{x}|+\mathit{x})\right)\right]-\gamma \mathit{q}\end{array}$$

（2）

2） 如果$\mathit{x}$满足隐式不动点方程（2），则

$$\begin{array}{l}\mathit{u}=\frac{\mathrm{1}}{\gamma }(|\mathit{x}|+\mathit{x})+f(\mathit{u})\\ \mathit{r}=\frac{\mathrm{1}}{\gamma }\mathit{\Omega }(|\mathit{x}|-\mathit{x})\end{array}$$

是隐式互补问题（1）的解。

基于隐式不动点方程（2），李郴良等^［16］构造了如下求解隐式互补问题的模系矩阵分裂迭代法。

算法1   （模系矩阵分裂迭代法）

步骤1   定义$\mathit{U}=\{\mathit{u}:\mathit{u}-f(\mathit{u})\ge \mathrm{0},\mathit{M}\mathit{u}+\mathit{q}\ge \mathrm{0}\},$令$\mathit{M}=\mathit{F}-\mathit{G}$为矩阵$\mathit{M}$的一个分裂。

步骤2   给定$\mathit{\epsilon }>\mathrm{0},{\mathit{u}}^{(\mathrm{0})}\in \mathit{U},$$k=\mathrm{0}\mathrm{。}$

步骤3   计算解：

1）计算初始向量

$${\mathit{x}}^{(\mathrm{0},k)}=\frac{\gamma }{\mathrm{2}}\left({\mathit{u}}^{(k)}-{\mathit{\Omega }}^{-\mathrm{1}}{\mathit{r}}^{(k)}-f({\mathit{u}}^{(k)})\right)$$

其中：${\mathit{r}}^{(k)}=\mathit{M}{\mathit{u}}^{\left(k\right)}+\mathit{q},$令$j≔\mathrm{0}\mathrm{。}$

2）通过下列迭代格式计算${\mathit{x}}^{(j+\mathrm{1},k)}$：

$$\begin{array}{l}(\mathit{\Omega }+\mathit{F}){\mathit{x}}^{(j+\mathrm{1},k)}=\mathit{G}{\mathit{x}}^{(j,k)}+(\mathit{\Omega }-\mathit{M})|{\mathit{x}}^{(j,k)}|-\\ \gamma \cdot \mathit{M}\cdot f({\mathit{u}}^{(k)})-\gamma \mathit{q}\end{array}$$

3）计算

$${\mathit{u}}^{(k+\mathrm{1})}=\frac{\mathrm{1}}{\gamma }\left(|{\mathit{x}}^{(j+\mathrm{1},k)}|+{\mathit{x}}^{(j+\mathrm{1},k)}\right)+f({\mathit{u}}^{(k)})$$

步骤4   如果${\mathit{u}}^{(k+\mathrm{1})}$满足停止准则，则迭代停止。否则，令$k=k+\mathrm{1}$且转向步骤2。

为了加快求解隐式互补问题的传统模系矩阵分裂迭代法的收敛速度，通过引入对向量边计算边更替的思想，可构造如下加速模系矩阵分裂迭代法。

算法2   （加速模系矩阵分裂迭代法）

步骤1   定义$\mathit{U}=\{\mathit{u}:\mathit{u}-f(\mathit{u})\ge \mathrm{0},\mathit{M}\mathit{u}+\mathit{q}\ge \mathrm{0}\},$令$\mathit{M}={\mathit{F}}_{\mathrm{1}}-{\mathit{G}}_{\mathrm{1}}={\mathit{F}}_{\mathrm{2}}-{\mathit{G}}_{\mathrm{2}}$为矩阵$\mathit{M}$的两个分裂。

步骤2   给定$\mathit{\epsilon }>\mathrm{0},{\mathit{u}}^{(\mathrm{0})}\in \mathit{U},$$k=\mathrm{0}\mathrm{。}$

步骤3   计算解${\mathit{u}}^{(k+\mathrm{1})}$：

1）计算初始向量

$${\mathit{x}}^{(\mathrm{0},k)}=\frac{\gamma }{\mathrm{2}}\left({\mathit{u}}^{(k)}-{\mathit{\Omega }}^{-\mathrm{1}}{\mathit{r}}^{(k)}-f({\mathit{u}}^{(k)})\right)$$

其中：${\mathit{r}}^{(k)}=\mathit{M}{\mathit{u}}^{\left(k\right)}+\mathit{q},$令$j≔\mathrm{0}\mathrm{。}$

2）通过下列迭代格式计算${\mathit{x}}^{(j+\mathrm{1},k)}$：

$$(\mathit{\Omega }+{\mathit{F}}_{\mathrm{1}}){\mathit{x}}^{(j+\mathrm{1},k)}={\mathit{G}}_{\mathrm{1}}{\mathit{x}}^{(j,k)}+(\mathit{\Omega }-{\mathit{F}}_{\mathrm{2}})|{\mathit{x}}^{(j,k)}|+{\mathit{G}}_{\mathrm{2}}|{\mathit{x}}^{(j+\mathrm{1},k)}|-\gamma \cdot \mathit{M}\cdot f({\mathit{u}}^{(k)})-\gamma \mathit{q}$$

（3）

3）计算

$${\mathit{u}}^{(k+\mathrm{1})}=\frac{\mathrm{1}}{\gamma }\left(|{\mathit{x}}^{(j+\mathrm{1},k)}|+{\mathit{x}}^{(j+\mathrm{1},k)})+f({\mathit{u}}^{(k)}\right)$$

（4）

步骤4   如果${\mathit{u}}^{(k+\mathrm{1})}$满足停止准则，则迭代停止；否则，令$k=k+\mathrm{1}$且转向步骤2。

特别地，如果${\mathit{F}}_{\mathrm{1}}=\frac{\mathrm{1}}{\alpha }(\mathit{D}-\beta \mathit{L}),{\mathit{G}}_{\mathrm{1}}=\frac{\mathrm{1}}{\alpha }[(\mathrm{1}-\alpha )\mathit{D}+(\alpha -\beta )\mathit{L}+\alpha \mathit{U}],{\mathit{F}}_{\mathrm{2}}=\mathit{D}-\mathit{U},{\mathit{G}}_{\mathrm{2}}=\mathit{L},\gamma =\mathrm{2}$，可得到加速的模系加速超松弛迭代法，这里$\alpha$和$\beta$是两个松弛系数，$\mathit{D}$、$-\mathit{L}$和$-\mathit{U}$分别是矩阵$\mathit{M}$的对角部分，严格下三角部分及严格上三角部分，且：①当$\alpha =\beta$时，得相应的加速模系逐步超松弛迭代法；②当$\alpha =\beta =\mathrm{1}$时，得相应的加速模系高斯⁃赛德尔迭代法；③当$\alpha =\mathrm{1}\mathrm{、}\beta =\mathrm{0}$时，得相应的加速模系雅可比迭代法。

3 收敛性分析

本节建立了系数矩阵为H₊⁃矩阵情况下加速模系矩阵分裂迭代法求解隐式互补问题（1）的收敛性分析。

引理  1^［23］     令$\mathit{M}\in {\mathbf{R}}^{n\times n}$是一个${\mathit{H}}_{+}$⁃矩阵，则$|{\mathit{M}}^{-\mathrm{1}}|$≤。

引理  2^［24］     令$\mathit{M}\in {\mathbf{R}}^{n\times n}$，则$\rho (\mathit{M})<\mathrm{1}$当且仅当$\underset{n\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}{\mathit{M}}^n=\mathrm{0}\mathrm{。}$

由定理1知，若$\left({\mathit{u}}_{\mathrm{*}},{\mathit{r}}_{\mathrm{*}}\right)$为隐式互补问题（1）的解，则

$${\mathit{u}}_{\mathrm{*}}=\frac{\mathrm{1}}{\gamma }(|{\mathit{x}}_{\mathrm{*}}|+{\mathit{x}}_{\mathrm{*}})+f({\mathit{u}}_{\mathrm{*}})$$

（5）

且${\mathit{x}}_{\mathrm{*}}=\frac{\gamma }{\mathrm{2}}\left({\mathit{u}}_{\mathrm{*}}-{\mathit{\Omega }}^{-\mathrm{1}}{\mathit{r}}_{\mathrm{*}}-f({\mathit{u}}_{\mathrm{*}})\right)$满足

$$\begin{array}{l}(\mathit{\Omega }+{\mathit{F}}_{\mathrm{1}}){\mathit{x}}_{\mathrm{*}}={\mathit{G}}_{\mathrm{1}}{\mathit{x}}_{\mathrm{*}}+(\mathit{\Omega }-{\mathit{F}}_{\mathrm{2}})|{\mathit{x}}_{\mathrm{*}}|+\\ {\mathit{G}}_{\mathrm{2}}|{\mathit{x}}_{\mathrm{*}}|-\gamma \cdot \mathit{M}\cdot f({\mathit{u}}_{\mathrm{*}})-\gamma \mathit{q}\end{array}$$

（6）

定理2   令矩阵$\mathit{M}\in {\mathbf{R}}^{n\times n}$为${\mathit{H}}_{+}$⁃矩阵，$\mathit{M}={\mathit{F}}_{\mathrm{1}}-{\mathit{G}}_{\mathrm{1}}={\mathit{F}}_{\mathrm{2}}-{\mathit{G}}_{\mathrm{2}}$为矩阵$\mathit{M}$的两个$\mathit{H}$⁃相容分裂。假设$\mathit{\Omega }\in {\mathbf{R}}^{n\times n}$为一个正对角矩阵，$\gamma$是一个正常数，且$f\left(\mathit{u}\right)$是一个李普希兹连续函数，即存在非负矩阵$\mathit{N}$满足$|f(\mathit{u})-f(\mathit{v})|\le N|\mathit{u}-\mathit{v}|,\forall \mathit{u},\mathit{v}\in {\mathbf{R}}^n$， 定义

$$\lambda =\Vert \mathit{N}\Vert$$

如果$\mathit{\Omega }\ge \mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left({\mathit{F}}_{\mathrm{2}}\right)$且是一个$\mathit{M}$⁃矩阵及

$$\left(\mathrm{1}+\frac{\mathrm{2}‖{\mathit{\varphi }}_{\mathrm{2}}‖}{\mathrm{1}-‖{\mathit{\varphi }}_{\mathrm{1}}‖}\right)$$$$\cdot \lambda <\mathrm{1}$$

则任意给定初始向量${\mathit{u}}^{\left(\mathrm{0}\right)}\in \mathit{U},$算法2生成的迭代序列$\{{\mathit{u}}^{(k)}{\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$收敛到隐式互补问题（1）的唯一解${\mathit{u}}_{\mathrm{*}}$。

证明   式（4）减去式（5），两边同时取绝对值得

$$\begin{array}{l}|{\mathit{u}}^{(k+\mathrm{1})}-{\mathit{u}}_{\mathrm{*}}|=|f({\mathit{u}}^{(k)})-f({\mathit{u}}_{\mathrm{*}})+\\ \frac{\mathrm{1}}{\gamma }\left.({\mathit{x}}^{(j+\mathrm{1},k)}|-|{\mathit{x}}_{\mathrm{*}}|+{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}})\right|\le \\ |f({\mathit{u}}^{(k)})-f({\mathit{u}}_{\mathrm{*}})|+\frac{\mathrm{1}}{\gamma }\left(|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|+\right.\\ \left.|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|\right)\le \\ \mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|+\frac{\mathrm{2}}{\gamma }|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|\end{array}$$

因为$\mathit{M}={\mathit{F}}_{\mathrm{1}}-{\mathit{G}}_{\mathrm{1}}={\mathit{F}}_{\mathrm{2}}-{\mathit{G}}_{\mathrm{2}}$是矩阵$\mathit{M}$的两个$\mathit{H}$⁃相容分裂，则

由$\mathit{M}$是${\mathit{H}}_{+}$⁃矩阵可得${\mathit{F}}_{\mathrm{1}}$为${\mathit{H}}_{+}$⁃矩阵，且由引理1知

类似地，式（3）减去式（6），且两边同时加上绝对值得

$$\begin{array}{l}\left|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}\right|\le \\ \left|{\left(\mathit{\Omega }+{\mathit{F}}_{\mathrm{1}}\right)}^{-\mathrm{1}}\right|\left(\left|{\mathit{G}}_{\mathrm{1}}\right|\left|{\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}\right|+\right.\\ \left|{\mathit{G}}_{\mathrm{2}}\right|\left||{\mathit{x}}^{(j+\mathrm{1},k)}|-|{\mathit{x}}_{\mathrm{*}}|\right|+\end{array}$$

或者等价的有

因为为$\mathit{M}$⁃矩阵，则也为$\mathit{M}$⁃矩阵。 因此是$\mathit{M}$⁃分裂，且

进一步知为$\mathit{M}$⁃矩阵，且其逆为非负矩阵，从而

类似可得$\begin{array}{l}|{\mathit{x}}^{(\mathrm{0},k)}-{\mathit{x}}_{\mathrm{*}}|=\\ \left|\frac{\gamma }{\mathrm{2}}\left({\mathit{u}}^{(k)}-{\mathit{\Omega }}^{-\mathrm{1}}{r}^{(k)}-f({\mathit{u}}^{(k)})\right)-\right.\\ \left.\frac{\gamma }{\mathrm{2}}\left({\mathit{u}}_{\mathrm{*}}-{\mathit{\Omega }}^{-\mathrm{1}}{r}_{\mathrm{*}}-f({\mathit{u}}_{\mathrm{*}})\right)\right|=\\ \frac{\gamma }{\mathrm{2}}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}+{\mathit{\Omega }}^{-\mathrm{1}}(r_{\mathrm{*}}-r^{(k)})+f({\mathit{u}}_{\mathrm{*}})-f({\mathit{u}}^{(k)})|\le \\ \frac{\gamma }{\mathrm{2}}(|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|+{\mathit{\Omega }}^{-\mathrm{1}}|r_{\mathrm{*}}-r^{(k)}|+|f({\mathit{u}}_{\mathrm{*}})-f({\mathit{u}}^{(k)})|)\le \end{array}$$\begin{array}{l}\frac{\gamma }{\mathrm{2}}(|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}||{\mathit{u}}_{\mathrm{*}}-{\mathit{u}}^{(k)}|+\mathit{N}|{\mathit{u}}_{\mathrm{*}}-{\mathit{u}}^{(k)}|)=\\ \frac{\gamma }{\mathrm{2}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\end{array}$

$$\begin{array}{l}\left|{\mathit{u}}^{(k+\mathrm{1})}-{\mathit{u}}_{\mathrm{*}}\right.|\le \\ \frac{\mathrm{2}}{\gamma }|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|+\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\le \end{array}$$

$$\frac{\mathrm{2}}{\gamma }[{\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}|{\mathit{x}}^{(\mathrm{0},k)}-{\mathit{x}}_{\mathrm{*}}|+\gamma ({\mathit{\varphi }}_{\mathrm{1}}^j{\mathit{\varphi }}_{\mathrm{2}}+{\mathit{\varphi }}_{\mathrm{1}}^{j-\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}+\cdot \cdot \cdot$$

$$\begin{array}{l}+{\mathit{\varphi }}_{\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}+{\mathit{\varphi }}_{\mathrm{2}})\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|]+\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\le \\ \frac{\mathrm{2}}{\gamma }[{\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}\frac{\gamma }{\mathrm{2}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|+\\ \gamma ({\mathit{\varphi }}_{\mathrm{1}}^j{\mathit{\varphi }}_{\mathrm{2}}+{\mathit{\varphi }}_{\mathrm{1}}^{j-\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}+\cdot \cdot \cdot +{\mathit{\varphi }}_{\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}+\\ {\mathit{\varphi }}_{\mathrm{2}})\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|]+\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|=\end{array}$$

$$\begin{array}{l}\left({\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})\right)|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|+\\ (\mathrm{2}{\mathit{\varphi }}_{\mathrm{1}}^j{\mathit{\varphi }}_{\mathrm{2}}+\mathrm{2}{\mathit{\varphi }}_{\mathrm{1}}^{j-\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}+\cdot \cdot \cdot +\mathrm{2}{\mathit{\varphi }}_{\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}+\\ \mathrm{2}{\mathit{\varphi }}_{\mathrm{2}}+\mathit{I})N|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|=\\ \left({\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})+{\mathit{\varphi }}_{\mathrm{3}}\mathit{N}\right)|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\end{array}$$

（7）

定义$\widehat{\mathit{Z}}={\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})+{\mathit{\varphi }}_{\mathrm{3}}\mathit{N}$，则式（7）可以表示为

$$|{\mathit{u}}^{(k+\mathrm{1})}-{\mathit{u}}_{\mathrm{*}}|\le \widehat{\mathit{Z}}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|$$

显然，如果$\rho (\widehat{\mathit{Z}})<\mathrm{1},$ 迭代序列$\{{\mathit{u}}^{(k)}{\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$收敛到${\mathit{u}}_{\mathrm{*}}$。事实上

$$\begin{array}{l}\rho (\widehat{\mathit{Z}})=\rho ({\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})+{\mathit{\varphi }}_{\mathrm{3}}\mathit{N})\le \\ \Vert {\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})+{\mathit{\varphi }}_{\mathrm{3}}\mathit{N}\Vert \le \\ \Vert {\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}\Vert \cdot \Vert \mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N}\Vert +‖\mathrm{2}\sum _{i=\mathrm{0}}^j{\mathit{\varphi }}_{\mathrm{1}}^i{\mathit{\varphi }}_{\mathrm{2}}+\mathit{I}‖\cdot \lambda \end{array}$$

由文献［21］可知当$\mathit{M}={\mathit{F}}_{\mathrm{1}}-{\mathit{G}}_{\mathrm{1}}={\mathit{F}}_{\mathrm{2}}-{\mathit{G}}_{\mathrm{2}}$为矩阵$\mathit{M}$的两个$\mathit{H}$⁃相容分裂，且是一个$\mathit{M}$阵时，可得$\rho ({\mathit{\varphi }}_{\mathrm{1}})<\mathrm{1}$。由引理2可得$\underset{j\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}{\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}=\mathrm{0}$。故存在一个正整数$j_{\mathrm{0}}$，当$j\ge j_{\mathrm{0}}$时有

$$\Vert {\mathit{\varphi }}_{\mathrm{1}}^{j+\mathrm{1}}\Vert \cdot \Vert \mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N}\Vert \le \mathit{\epsilon }$$

于是，对于$\forall j\ge j_{\mathrm{0}}$有

$$\begin{array}{l}\rho (\widehat{\mathit{Z}})\le \mathit{\epsilon }+‖\mathrm{2}\sum _{i=\mathrm{0}}^j{\mathit{\varphi }}_{\mathrm{1}}^i{\mathit{\varphi }}_{\mathrm{2}}+\mathit{I}‖\cdot \lambda \le \\ \mathit{\epsilon }+(\mathrm{2}‖(\mathrm{1}-{\mathit{\varphi }}_{\mathrm{1}}{)}^{-\mathrm{1}}{\mathit{\varphi }}_{\mathrm{2}}‖+\mathrm{1})\cdot \lambda \le \\ \mathit{\epsilon }+\left(\mathrm{1}+\frac{\mathrm{2}‖{\mathit{\varphi }}_{\mathrm{2}}‖}{\mathrm{1}-‖{\mathit{\varphi }}_{\mathrm{1}}‖}\right)\cdot \lambda \end{array}$$

故随着 $j\to \mathrm{\infty }$，如果$\left(\mathrm{1}+\frac{\mathrm{2}‖{\mathit{\varphi }}_{\mathrm{2}}‖}{\mathrm{1}-‖{\mathit{\varphi }}_{\mathrm{1}}‖}\right)$$\cdot \lambda <\mathrm{1},$可得$\rho (\widehat{\mathit{Z}})<\mathrm{1}$。证毕。

类似地，可以建立下列加速的模系矩阵加速超松弛迭代法的收敛理论。

推论1   设矩阵$\mathit{M}$为H₊⁃矩阵，令M=D-L-U=D-B，这里$\mathit{D}$、$-\mathit{L}$和$-\mathit{U}$分别是矩阵$\mathit{M}$的对角部分，严格下三角部分及严格上三角部分。 假设$\mathit{\Omega }$为一个正对角矩阵满足$\mathit{\Omega }\ge \mathit{D}$，$\gamma$是一个正常数，若$\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\left|\mathit{L}\right|$为$\mathit{M}$⁃矩阵，松弛系数$\alpha$和$\beta$满足下列条件：

$$\mathrm{0}\le \beta \le \alpha ,\mathrm{0}<\alpha <\frac{\mathrm{1}}{\rho }$$

（8）

这里$\rho =\rho \left({\mathit{D}}^{-\mathrm{1}}\left|\mathit{B}\right|\right)$且$\left(\mathrm{1}+\frac{\mathrm{2}‖{\mathit{\Delta }}_{\mathrm{2}}‖}{\mathrm{1}-‖{\mathit{\Delta }}_{\mathrm{1}}‖}\right)$$\cdot \lambda <\mathrm{1}$，其中$\lambda$同定理2中定义。

$$\begin{array}{l}{\mathit{\Delta }}_{\mathrm{1}}={\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-|\mathit{L}|\right)}^{-\mathrm{1}}\left(\begin{array}{c}\\ \end{array}\right.\mathit{\Omega }+\\ \left.\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\frac{\mathrm{1}+\alpha -|\mathrm{1}-\alpha |}{\alpha }\mathit{D}+|\mathit{B}|+|\mathit{U}|\right)\\ {\mathit{\Delta }}_{\mathrm{2}}={\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-|\mathit{L}|\right)}^{-\mathrm{1}}|\mathit{M}|\end{array}$$

则任意给定初始向量${\mathit{u}}^{(\mathrm{0})}\in \mathit{U}$，算法2生成的迭代序列$\{{\mathit{u}}^{(k)}{\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$收敛到隐式互补问题（1）的唯一解${\mathit{u}}_{\mathrm{*}}$。

证明   当取${\mathit{F}}_{\mathrm{1}}=\frac{\mathrm{1}}{\alpha }(\mathit{D}-\beta \mathit{L}),{\mathit{G}}_{\mathrm{1}}=\frac{\mathrm{1}}{\alpha }[(\mathrm{1}-\alpha )\mathit{D}+(\alpha -\beta )\mathit{L}+\alpha \mathit{U}],{\mathit{F}}_{\mathrm{2}}=\mathit{D}-\mathit{U},{\mathit{G}}_{\mathrm{2}}=\mathit{L}$，可得加速的模系矩阵加速超松弛迭代格式

$$\begin{array}{l}\left(\mathit{\Omega }+\frac{\mathrm{1}}{\alpha }(\mathit{D}-\beta \mathit{L})\right){\mathit{x}}^{(j+\mathrm{1},k)}=\\ \frac{\mathrm{1}}{\alpha }\left((\mathrm{1}-\alpha )\mathit{D}+(\alpha -\beta )\mathit{L}+\right.\\ \left.\alpha \mathit{U}\right){\mathit{x}}^{(j,k)}+(\mathit{\Omega }-\mathit{D}+\mathit{U})\left|{\mathit{x}}^{(j,k)}\right|+\\ \mathit{L}\left|{\mathit{x}}^{(j+\mathrm{1},k)}\right|-\gamma \mathit{q}-\gamma \mathit{M}f({\mathit{u}}^{(k)})\end{array}$$

（9）

若$\left({\mathit{u}}_{\mathrm{*}},{\mathit{r}}_{\mathrm{*}}\right)$是问题（1）的解，则${\mathit{x}}_{\mathrm{*}}=\frac{\gamma }{\mathrm{2}}({\mathit{u}}_{\mathrm{*}}-{\mathit{\Omega }}^{-\mathrm{1}}{\mathit{r}}_{\mathrm{*}}-f({\mathit{u}}_{\mathrm{*}}))$满足

$$\left(\mathit{\Omega }+\frac{\mathrm{1}}{\alpha }(\mathit{D}-\beta \mathit{L})\right)$$$${\mathit{x}}_{\mathrm{*}}=\frac{\mathrm{1}}{\alpha }((\mathrm{1}-\alpha )\mathit{D}+(\alpha -\beta )\mathit{L}+\alpha \mathit{U}){\mathit{x}}_{\mathrm{*}}+(\mathit{\Omega }-\mathit{D}+\mathit{U})\left|{\mathit{x}}_{\mathrm{*}}\right|+\mathit{L}\left|{\mathit{x}}_{\mathrm{*}}\right|-\gamma \mathit{q}-\gamma \mathit{M}f({\mathit{u}}_{\mathrm{*}})$$

（10）

用式（10）减去式（9），可得

$$\begin{array}{l}\left(\mathit{\Omega }+\frac{\mathrm{1}}{\alpha }(\mathit{D}-\beta \mathit{L})\right)\left({\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}\right)=\\ \frac{\mathrm{1}}{\alpha }\left((\mathrm{1}-\alpha )\mathit{D}+(\alpha -\beta )\mathit{L}+\alpha U\right)\left({\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}\right)+\\ (\mathit{\Omega }-\mathit{D}+U)\left(|{\mathit{x}}^{(j,k)}|-|{\mathit{x}}_{\mathrm{*}}|\right)+\\ \mathit{L}\left(|{\mathit{x}}^{(j+\mathrm{1},k)}|-|{\mathit{x}}_{\mathrm{*}}|\right)-\gamma M\left(f({\mathit{u}}^{(k)})-f({\mathit{u}}_{\mathrm{*}})\right)\end{array}$$

（11）

由定理2知，${\mathit{F}}_{\mathrm{1}}$是一个${\mathit{H}}_{+}$⁃矩阵，从而$\mathit{\Omega }+\frac{\mathrm{1}}{\alpha }\mathit{D}-\frac{\beta }{\alpha }\mathit{L}$是一个${\mathit{H}}_{+}$⁃矩阵。故由引理1可得

$${\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}$$

由条件可知$\mathit{\Omega }\ge \mathit{D}$且$\mathrm{0}\le \beta \le \alpha$，在式（11）两边同时加上绝对值可得

$$\left|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}\right|$$≤

$$\begin{array}{l}{\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\right.\\ \left.\frac{\mathit{D}}{\alpha }-\mathit{D}+\frac{|\mathrm{1}-\alpha |}{\alpha }\mathit{D}+|\mathit{B}|+|\mathit{U}|\right)|{\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}|+\\ {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{L}||{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|+\\ \gamma {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{M}|\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\end{array}$$

（12）

式（12）等价于

$$\begin{array}{l}\left(\mathit{I}-{\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{L}|\right)|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|\le \\ {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\right.\\ \left.\frac{\mathrm{1}+\alpha -|\mathrm{1}-\alpha |}{\alpha }\mathit{D}+|\mathit{B}|+|\mathit{U}|\right)|{\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}|+\\ \gamma {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{M}|\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\end{array}$$

因为$\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\left|\mathit{L}\right|$为$\mathit{M}$⁃矩阵，则$\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }$也为$\mathit{M}$⁃矩阵。故$\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\left|\mathit{L}\right|$是$\mathit{M}$⁃分裂，且

ρ$\left({\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{L}|\right)$<1

则$\mathit{I}-{\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{L}|$为$\mathit{M}$⁃矩阵。且逆为非负矩阵，从而

$$\begin{array}{l}|{\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}_{\mathrm{*}}|\le \\ {\left(\mathit{I}-{\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}\left|\mathit{L}\right|\right)}^{-\mathrm{1}}{\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}·\\ \left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\right.\left.\frac{\mathrm{1}+\alpha -|\mathrm{1}-\alpha |}{\alpha }\mathit{D}+|\mathit{B}|+|\mathit{U}|\right)·\\ |{\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}|+\gamma {\left(\mathit{I}-{\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}\left|\mathit{L}\right|\right)}^{-\mathrm{1}}·\\ {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }\right)}^{-\mathrm{1}}|\mathit{M}|\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|=\\ {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-|\mathit{L}|\right)}^{-\mathrm{1}}\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-\right.\\ \left.\frac{\mathrm{1}+\alpha -|\mathrm{1}-\alpha |}{\alpha }\mathit{D}+|\mathit{B}|+|\mathit{U}|\right)|{\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}|+\\ \gamma {\left(\mathit{\Omega }+\frac{\mathit{D}-\beta |\mathit{L}|}{\alpha }-|\mathit{L}|\right)}^{-\mathrm{1}}|\mathit{M}|\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|=\end{array}$$

$$\begin{array}{l}{\mathit{\Delta }}_{\mathrm{1}}|{\mathit{x}}^{(j,k)}-{\mathit{x}}_{\mathrm{*}}|+\gamma {\mathit{\Delta }}_{\mathrm{2}}\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|=\\ {\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}|{\mathit{x}}^{(\mathrm{0},k)}-{\mathit{x}}_{\mathrm{*}}|+\gamma \sum _{i=\mathrm{0}}^j{\mathit{\Delta }}_{\mathrm{1}}^i{\mathit{\Delta }}_{\mathrm{2}}\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\end{array}$$

与定理2类似可得

$$\begin{array}{l}|{\mathit{u}}^{(k+\mathrm{1})}-{\mathit{u}}_{\mathrm{*}}|\le \\ {\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}M|+N)|{\mathit{u}}^k-{\mathit{u}}_{\mathrm{*}}|+\\ \left(\mathrm{2}\sum _{i=\mathrm{0}}^j{\mathbf{\Delta }}_{\mathrm{1}}^i{\mathit{\Delta }}_{\mathrm{2}}+\mathit{I}\right)\mathit{N}|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|=\\ {\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N}+{\mathit{\Delta }}_{\mathrm{3}}\mathit{N})|{\mathit{u}}^{(k)}-{\mathit{u}}_{\mathrm{*}}|\end{array}$$

这里 ${\mathit{\Delta }}_{\mathrm{3}}=\mathrm{2}\sum _{i=\mathrm{0}}^j{\mathit{\Delta }}_{\mathrm{1}}^i{\mathit{\Delta }}_{\mathrm{2}}+\mathit{I}\mathrm{。}$定义$\mathit{Q}={\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})+{\mathit{\Delta }}_{\mathrm{3}}\mathit{N}$。显然，当$\rho (\mathit{Q})<\mathrm{1}$时由算法2生成的迭代序列$\{{\mathit{u}}^{(k)}{\}}_{k=\mathrm{0}}^{\mathrm{\infty }}$收敛到隐式互补问题（1）的唯一解${\mathit{u}}_{\mathrm{*}}$。下证$\rho (\mathit{Q})<\mathrm{1}$。

由$\mathit{Q}$定义可得

$$\rho (\mathit{Q})=\rho ({\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}(\mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N})+{\mathit{\Delta }}_{\mathrm{3}}\mathit{N})\le \Vert {\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}\Vert \cdot \Vert \mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N}\Vert +\Vert {\mathit{\Delta }}_{\mathrm{3}}\Vert \cdot \lambda$$

由文献［21］可知，当$\alpha \mathrm{、}\beta$满足条件（8）时，有$\rho ({\mathit{\Delta }}_{\mathrm{1}})<\mathrm{1}$。由引理2可得$\underset{j\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}{\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}=\mathrm{0}$。故存在一个正整数$j_{\mathrm{0}}$，当$j\ge j_{\mathrm{0}}$时

$$\Vert {\mathit{\Delta }}_{\mathrm{1}}^{j+\mathrm{1}}\Vert \cdot \Vert \mathit{I}+|{\mathit{\Omega }}^{-\mathrm{1}}\mathit{M}|+\mathit{N}\Vert \le \mathit{\epsilon }$$

从而对于$\forall j\ge j_{\mathrm{0}}$，有

$$\rho (\mathit{Q})\le \mathit{\epsilon }+\Vert \mathrm{2}\sum _{i=\mathrm{0}}^j{\mathit{\Delta }}_{\mathrm{1}}^i{\mathit{\Delta }}_{\mathrm{2}}+\mathit{I}\Vert \cdot \lambda \le \mathit{\epsilon }+(\mathrm{2}\Vert (\mathit{I}-{\mathit{\Delta }}_{\mathrm{1}}{)}^{-\mathrm{1}}{\mathit{\Delta }}_{\mathrm{2}}\Vert +\mathrm{1})\cdot \lambda \le \mathit{\epsilon }+\left(\mathrm{1}+\frac{\mathrm{2}‖{\mathit{\Delta }}_{\mathrm{2}}‖}{\mathrm{1}-‖{\mathit{\Delta }}_{\mathrm{1}}‖}\right)\cdot \lambda$$

故随着$j\to \mathrm{\infty }$，如果$\left(\mathrm{1}+\frac{\mathrm{2}‖{\mathit{\Delta }}_{\mathrm{2}}‖}{\mathrm{1}-‖{\mathit{\Delta }}_{\mathrm{1}}‖}\right)$$\cdot \lambda <\mathrm{1}$可得$\rho (\mathit{Q})<\mathrm{1}$。证明完成。

4 数值实验

本节将给出一些数值算例来验证加速模系矩阵分裂迭代法的有效性。数值实验将从迭代步数（IT）、所消耗时间（CPU）和残差范数（RES）3个方面来反映算法的优劣。其中残差范数定义为

$$\mathrm{R}\mathrm{E}\mathrm{S}({\mathit{u}}^{(k)})≔\Vert \mathrm{m}\mathrm{i}\mathrm{n}(\mathit{M}{\mathit{u}}^{(k)}+\mathit{q},{\mathit{u}}^{(k)}-f({\mathit{u}}^{(k)})){\Vert }_{\mathrm{2}}$$

所有计算均在一台CPU为1.8 GHz和内存为 8 GB的机器上运行，编程语言为MATLAB。在本实验中，所有的初始向量取为：${\mathit{u}}^{(\mathrm{0})}={(\mathrm{0,0},\dots ,\mathrm{0,0},\dots )}^{\mathrm{T}}\in {\mathbf{R}}^n.$并且内迭代的停止准则为$\Vert {\mathit{x}}^{(j+\mathrm{1},k)}-{\mathit{x}}^{(j,k)}\Vert \le {\mathrm{10}}^{-\mathrm{4}}$，外迭代的停止准则为$\mathrm{R}\mathrm{E}\mathrm{S}({\mathit{u}}^{(k)})\le {\mathrm{10}}^{-\mathrm{6}}\mathrm{。}$$\alpha$为加速模系矩阵逐步超松弛迭代法与模系矩阵逐步超松弛迭代法的迭代系数，最优参数为使得这两种迭代法迭代步数与时间最小的参数。

例1   设$m$为给定的正整数，$n=m^{\mathrm{2}}$。在式（1）中取$\mathit{M}=\widehat{\mathit{M}}+\mu \mathit{I},\mathit{q}=-\mathit{M}{\mathit{z}}_{\star }$，其中

$$\widehat{\mathit{M}}=\left(\begin{array}{ccccc}S& -\mathrm{0.5}I& \mathrm{0}& \cdots & \mathrm{0}\\ -\mathrm{1.5}I& S& \ddots & \ddots & ⋮\\ \mathrm{0}& \ddots & \ddots & \ddots & \mathrm{0}\\ ⋮& \ddots & \ddots & S& -\mathrm{0.5}I\\ \mathrm{0}& \cdots & \mathrm{0}& -\mathrm{1.5}I& S\end{array}\right)\in {\mathbf{R}}^{n\times n}$$

为块三对角矩阵，其中S=tridiag（-1.5，4， -0.5）$\in {\mathbf{R}}^{m\times m}$为三对角矩阵，取${\mathit{z}}_{\star }$=（1，2，1，2，…，1，2，…）^T$\in {\mathbf{R}}^n$和f（u）=（arctan（u₁），…，arctan（u_n））。

例2   设$m$为给定的正整数， $n=m^{\mathrm{2}}$。在式（1）中取$\mathit{M}=\widehat{\mathit{M}}+\mu \mathit{I},\mathit{q}=-\mathit{M}{\mathit{z}}_{\star }$其中

$$\widehat{\mathit{M}}=\left(\begin{array}{ccccc}S& -I& \mathrm{0}& \cdots & \mathrm{0}\\ -I& S& \ddots & \ddots & ⋮\\ \mathrm{0}& \ddots & \ddots & \ddots & \mathrm{0}\\ ⋮& \ddots & \ddots & S& -I\\ \mathrm{0}& \cdots & \mathrm{0}& -I& S\end{array}\right)\in {\mathbf{R}}^{n\times n}$$

为块三对角矩阵，其中S=tridiag（-1，4，-1）$\in {\mathbf{R}}^{m\times m}$为三对角矩阵， 取${\mathit{z}}_{\star }$=（1，2，1，2，…，1，2，…）^T$\in {\mathbf{R}}^n$和$f\left(\mathit{u}\right)$=$\left(\sqrt[]{u_{\mathrm{1}}},\cdots ,\sqrt[]{u_n}\right)\mathrm{。}$

表1列出了例1和例2中使用的6种测试方法及其缩写符号。表2列出了$\mu =\mathrm{2}$，$\alpha$以0.2为间隔从1.0到2.2变化以及矩阵维数增加时，MSOR及AMSOR算法迭代步数与迭代时间的数值结果。

表1 测试方法及其缩写

Tab. 1 Abbreviations of testing methods

符号	方法
MJ	模系矩阵雅可比迭代法
AMJ	加速模系矩阵雅可比迭代法
GS	模系矩阵高斯⁃赛德尔迭代法
AGS	加速模系矩阵高斯⁃赛德尔迭代法
MSOR	模系矩阵逐步超松弛迭代法
AMSOR	加速模系矩阵逐步超松弛迭代法

表2 例1中当$\mathit{\alpha }$变化时MSOR和AMSOR的迭代步数与时间（μ=$\mathrm{2}$）

Tab. 2 IT and CPU for MSOR and AMSOR with the change in α for example 1（μ=$\mathrm{2}$）

$\alpha$	$n=400$				$n=1600$				$n=3600$				$n=6400$
	MSOR		AMOSR		MSOR		AMOSR		MSOR		AMOSR		MSOR		AMOSR
	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s
1.0	7	0.06	5	0.05	8	1.15	5	0.86	8	6.14	6	4.12	8	38.84	5	28.41
1.2	7	0.06	4	0.04	7	0.97	4	0.67	7	4.96	4	3.19	7	37.56	4	21.44
1.4	6	0.05	3	0.03	7	0.89	3	0.47	7	5.72	3	2.78	7	36.50	3	15.06
1.6	6	0.05	3	0.03	6	0.79	3	0.44	6	4.78	3	2.31	6	30.64	3	17.24
1.8	5	0.04	3	0.02	5	0.71	3	0.48	6	4.77	3	2.75	5	27.29	4	20.72
2.0	4	0.03	4	0.03	4	0.64	3	0.55	5	4.04	3	2.86	5	30.30	4	23.53
2.2	5	0.04	4	0.03	5	0.78	4	0.67	5	4.64	4	3.59	5	29.15	4	27.47

从表2中可以看到当$\mu =\mathrm{2},$矩阵维数为400、 1 600、3 600和6 400时，从最小化迭代时间考虑，MSOR相对应的最优参数分别为2.0、2.0、2.0和1.8，然而AMSOR的最优参数分别为1.8、1.6、1.6和1.4。

表3和表4中列出了当$\mu$分别为2和4，矩阵维数增加时在最优参数下6种方法的迭代步数、迭代时间以及残差范数的比较结果。

表3 例1中最优参数下6种方法的数值结果（μ=$\mathrm{2}$）

Tab. 3 Numerical results for six methods with optimal parameters for example 1（μ=$\mathrm{2}$）

方法	$n=400$			$n=1600$			$n=3600$			$n=6400$
	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES
MJ	9	0.12	8.17×10-7	10	1.95	5.17×10-7	10	10.19	6.36×10-7	10	52.33	6.33×10-7
AMJ	7	0.08	8.67×10-7	8	1.80	4.40×10-7	8	8.10	4.56×10-7	8	42.52	6.50×10-7
GS	7	0.06	8.67×10-7	8	1.15	4.40×10-7	8	6.14	4.56×10-7	8	38.84	6.50×10-7
AGS	5	0.05	6.65×10-7	5	0.86	7.67×10-7	6	4.12	3.81×10-7	5	28.41	7.44×10-7
MSOR	4	0.03	9.47×10-7	4	0.64	2.39×10-7	5	4.04	2.97×10-7	5	27.79	9.91×10-7
AMSOR	3	0.02	4.15×10-7	3	0.44	1.72×10-7	3	2.31	2.78×10-7	3	15.06	3.85×10-7

表4 例1中最优参数下6种方法的数值结果（μ=$\mathrm{4}$）

Tab. 4 Numerical results for six methods with optimal parameters for example 1（μ=$\mathrm{4}$）

方法	$n=400$			$n=1600$			$n=3600$			$n=6400$
	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES
MJ	6	0.04	4.39×10-7	6	1.21	6.66×10-7	6	6.20	5.82×10-7	6	34.13	8.14×10-7
AMJ	5	0.03	3.89×10-7	5	1.07	4.41×10-7	5	5.06	7.18×10-7	5	28.24	4.25×10-7
GS	5	0.04	3.89×10-7	5	0,87	4.41×10-7	5	4.67	7.18×10-7	5	25.29	4.25×10-7
AGS	4	0.03	3.78×10-7	4	0.75	2.46×10-7	4	3.63	3.90×10-7	3	22.13	9.62×10-7
MSOR	4	0.02	1.50×10-7	4	0.50	7.35×10-7	4	3.75	9.09×10-7	5	22.77	1.51×10-7
AMSOR	2	0.01	1.58×10-7	2	0.36	8.33×10-7	3	2.11	5.33×10-8	3	14.53	6.86×10-8

从表3和图1中可以看到所有的方法都快速收敛，并且所有迭代法的迭代时间随着矩阵维数的增加而增加。测试的6种算法中AMSOR需要最少的迭代步数与时间，并且所有的加速模系矩阵分裂迭代法与相对应的模系矩阵分裂迭代法相比迭代步数与迭代时间都更少。

图1 例1两种算法的残差随迭代步数变化的比较

Fig. 1 Residual comparison of two algorithms for example 1

当$\mu =\mathrm{4}$时系数矩阵变得更加对角占优。从表4可以看出，在相同的矩阵维数下，6种方法的迭代步数与时间少于表3中的结果，并且加速模系矩阵分裂迭代法仍优于相对应的模系矩阵分裂迭代法。

表5列出了$\mu =\mathrm{2}$时，$\alpha$以0.2为间隔从1.0到2.2变化以及矩阵维数增加时，MSOR及AMSOR算法迭代步数与迭代时间的数值结果。

表5 例2中当α变化时MSOR和AMSOR的迭代步数与时间 （μ=$\mathrm{2}$）

Tab. 5 IT and CPU for MSOR and AMSOR with the change in α for example 2（μ=$\mathrm{2}$）

$\alpha$	$n=400$				$n=1600$				$n=3600$				$n=6400$
	MSOR		AMOSR		MSOR		AMOSR		MSOR		AMOSR		MSOR		AMOSR
	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s	IT/步	CPU/s
1.0	7	0.06	6	0.05	7	1.18	6	1.12	7	8.78	6	6.04	7	57.11	6	36.82
1.2	6	0.04	5	0.03	6	0.97	5	0.93	6	5.63	5	5.06	6	40.36	5	35.61
1.4	6	0.04	4	0.03	6	0.92	4	0.81	6	5.79	4	4.11	6	33.72	5	31.03
1.6	5	0.03	4	0.01	5	0.86	4	0.78	5	5.13	4	4.21	5	29.04	4	28.14
1.8	5	0.02	4	0.02	5	0.85	5	0.83	6	5.53	4	3.75	5	33.28	4	21.27
2.0	6	0.04	5	0.03	6	1.08	5	0.99	6	6.79	5	4.19	6	47.15	4	22.77
2.2	6	0.04	5	0.03	6	1.23	5	1.08	6	7.83	5	4.51	6	55.52	5	29.62

从表5中可以看到，当$\mu =\mathrm{2}$，矩阵维数为400、 1 600、3 600和6 400时，MSOR相对应的最优参数分别为1.8、1.8、1.6和1.6，而AMSOR的最优参数分别为1.6、1.6、1.8和1.8。

表6和表7中列出了当$\mu$分别为2和4，矩阵维数增大时在最优参数下6种方法的迭代步数、迭代时间以及残差范数的比较结果。

表6 例2中最优参数下6种方法的数值结果（μ=$\mathrm{2}$）

Tab. 6 Numerical results for six methods with optimal parameters for example 2（μ=$\mathrm{2}$）

方法	$n=400$			$n=1600$			$n=3600$			$n=6400$
	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES
MJ	8	0.06	5.10×10-7	8	1.73	6.69×10-7	8	9.43	7.58×10-7	8	50.99	7.29×10-7
AMJ	8	0.05	4.32×10-7	7	1.72	7.83×10-7	7	8.68	8.17×10-7	8	47.49	4.44×10-7
GS	7	0.06	5.80×10-7	7	1.18	3.99×10-7	7	8.78	4.15×10-7	7	57.11	5.78×10-7
AGS	6	0.05	6.39×10-7	6	1.12	5.43×10-7	6	6.04	4.96×10-7	6	36.82	6.92×10-7
MSOR	5	0.02	4.35×10-7	5	0.85	3.28×10-7	5	5.13	5.14×10-7	5	29.04	3.83×10-7
AMSOR	4	0.01	9.30×10-7	4	0.78	3.27×10-7	4	3.75	9.68×10-7	4	21.27	8.00×10-7

表7 例2中最优参数下6种方法的数值结果（μ=$\mathrm{4}$）

Tab. 7 Numerical results for six methods with optimal parameters for example 2（μ=$\mathrm{4}$）

方法	$n=400$			$n=1600$			$n=3600$			$n=6400$
	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES	IT/步	CPU/s	RES
MJ	6	0.04	4.05×10-7	6	1.14	5.35×10-7	6	6.30	4.53×10-7	6	32.45	6.24×10-7
AMJ	5	0.03	8.47×10-7	5	1.13	9.79×10-7	5	5.67	7.29×10-7	6	30.79	2.47×10-7
GS	5	0.04	7.54×10-7	5	0.89	8.63×10-7	5	5.22	6.42×10-7	5	26.60	8.83×10-7
AGS	5	0.03	2.77×10-7	5	0.87	2.68×10-7	4	4.88	8.36×10-7	5	24.26	2.29×10-7
MSOR	5	0.02	5.06×10-7	5	0.82	6.65×10-7	5	4.49	8.26×10-7	5	23.58	9.60×10-7
AMSOR	4	0.01	5.49×10-7	4	0.76	5.73×10-7	3	3.67	6.93×10-7	4	20.97	6.24×10-7

表6和表7中的数值结果进一步验证了从表3和表4得到的结论，并且6种方法对于对称矩阵的迭代步数与时间略多于非对称矩阵。测试的6种算法中AMSOR算法的计算效率优于其他5种方法，并且所有的加速模系矩阵分裂迭代法仍优于相对应的模系矩阵分裂迭代法。

5 结论

本文构造了求解一类隐式互补问题的加速模系矩阵分裂迭代法。理论分析建立了系数矩阵为$H_{+}$⁃矩阵时的收敛性。数值结果表明，加速模系矩阵分裂迭代法在迭代步数和迭代时间上均优于传统的模系矩阵分裂迭代法。

然而对于隐式互补问题的求解，无论是模系矩阵分裂迭代法还是加速的模系矩阵分裂迭代法，内迭代的收敛速度在整个迭代过程中都有着十分重要的影响。合适的内迭代停止准则或迭代步数可以加速求解隐式互补问题的计算效率。目前，对于内迭代最优的停止准则以及停止的迭代步数还没有很好的结论，并且内迭代与外迭代之间如何平衡也是一个十分有挑战性的课题，这需要笔者进一步的研究。