文章快速检索    
  同济大学学报(自然科学版)  209, Vol. 47 Issue (2): 291-297.  DOI: 10.11908/J.ISSN.0253-374x.2019.02.019
0

引用本文  

王艳, 殷俊锋, 李蕊. 松弛模系矩阵分裂迭代法求解一类非线性互补问题[J]. 同济大学学报(自然科学版), 209, 47(2): 291-297. DOI: 10.11908/J.ISSN.0253-374x.2019.02.019.
WANG Yan, YIN Junfeng, LI Rui. A Relaxation Modulus-based Matrix Splitting Iteration Method for a Class of Nonlinear Complementarity Problems[J]. Journal of Tongji University (Natural Science), 209, 47(2): 291-297. DOI: 10.11908/J.ISSN.0253-374x.2019.02.019

基金项目

中央高校基本科研业务费专项资金; 国家自然科学基金(11701221)

第一作者

王艳(1990—),女,博士生,主要研究方向为数值分析与科学计算.E-mail:7ywang@tongji.edu.cn

通信作者

殷俊锋(1979—),男,教授,博士生导师,理学博士,主要研究方向为数值分析与科学计算.E-mail:yinjf@tongji.edu.cn

文章历史

收稿日期:2018-04-07
松弛模系矩阵分裂迭代法求解一类非线性互补问题
王艳 1, 殷俊锋 1, 李蕊 1     
1. 同济大学 数学科学学院,上海 200092;
2. 嘉兴学院 数理与信息工程学院,浙江 嘉兴 314001
摘要:考虑松弛模系矩阵分裂迭代法求解一类非线性互补问题, 理论分析给出了当系数矩阵为H+-矩阵时迭代法的收敛性和松弛参数的选取方法.数值实验表明, 松弛模系矩阵分裂迭代法在迭代步数和迭代时间上均优于模系矩阵分裂迭代法.
关键词矩阵分裂    松弛模系迭代法    非线性互补问题    
A Relaxation Modulus-based Matrix Splitting Iteration Method for a Class of Nonlinear Complementarity Problems
WANG Yan 1, YIN Junfeng 1, LI Rui 1     
1. School of Mathematical Sciences, Tongji University, Shanghai 200092, China;
2. College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, China
Abstract: A relaxation modulus-based matrix splitting iteration method is proposed for solving a class of nonlinear complementarity problems. The convergence theory is established when the system matrix is H+-and the choice of relaxation parameters is given. Numerical examples show that the proposed methods are efficient and can accelerate the convergence performance of the modulus-based matrix splitting method with less iteration steps and CPU time.
Key words: matrix splitting    relaxation modulus-based iteration methods    nonlinear complementarity problems    

给定大型稀疏矩阵MRn×nn维向量qRn, 考虑如下一类非线性互补问题:求向量z, wRn满足

$ \mathit{\boldsymbol{z}} \ge 0,\;\;\;\;\mathit{\boldsymbol{w}}: = \mathit{\boldsymbol{Mz}} + \mathit{\boldsymbol{q}} + f\left( \mathit{\boldsymbol{z}} \right) \ge 0,\;\;\;\;{\mathit{\boldsymbol{z}}^T}\mathit{\boldsymbol{w}} = 0 $ (1)

这里,f:RnRn为给定的n元函数且满足对角可微[1-2],即fif的第i个分量仅仅是zi的可微函数.其中不等号是分量意义下的不等号, zT表示向量z的转置, 特别地, 当函数f为线性函数时, 问题(1)化为线性互补问题.

互补问题在科学与工程等领域有着广泛的应用[3-4], 如变分不等式、弹性接触问题、期权定价等自由边界问题均可化为互补问题.由于互补问题的重要性,引起了数学工作者的广泛关注和高度重视.近几十年来,其数值解的研究发展迅速,取得了丰硕的成果. Bai[5]提出了求解线性互补问题的模系矩阵分裂迭代法, 并且为模系矩阵分裂迭代方法提供了一个基本框架.由于其迭代格式简单,在文献[5]的基础上,模系矩阵分裂迭代法得到了进一步研究,比如,两步模系矩阵分裂迭代法[6]、加速的模系矩阵分裂迭代法[7]和松弛模系矩阵分裂迭代方法[8]等.随着高性能并行计算机系统的快速发展, Bai等[9]利用并行计算的思想, 提出了模系同步多分裂迭代法、模系同步二级多分裂迭代方法[10]和两步模系同步多分裂迭代方法[11].

针对非线性互补问题(1), 当函数f对角可微时, Xia等在文献[12]中首次将求解线性互补问题的模系矩阵分裂迭代法推广至该非线性互补问题, 构造了相应的模系矩阵分裂迭代法, 并给出了系数矩阵为正定或H+-矩阵时的收敛理论.随后, Li等[13]采用加速模系矩阵分裂迭代法对该非线性互补问题进行求解, 并且给出了矩阵MH+-矩阵时的收敛性分析.本文提出用松弛模系矩阵分裂迭代法求解该非线性互补问题, 讨论该迭代法在系数矩阵MH+-矩阵时的收敛条件,并且给出了最优参数的选取.数值实验表明, 对于大型稀疏非线性互补问题, 松弛模系矩阵分裂迭代法不仅是有效的, 而且收敛效果优于模系矩阵分裂迭代法.

1 松弛模系矩阵分裂迭代法

通过变量替换$\mathit{\boldsymbol{z = }}\frac{1}{\mathit{\gamma }}\left( {\left| \mathit{\boldsymbol{x}} \right| + \mathit{\boldsymbol{x}}} \right) $, $\mathit{\boldsymbol{w = }}\frac{1}{\mathit{\gamma }}\mathit{\boldsymbol{ \boldsymbol{\varPsi} }}\left( {\left| \mathit{\boldsymbol{x}} \right| - \mathit{\boldsymbol{x}}} \right) $,其中γ为正常数,Ψ为正对角矩阵,文献[12]给出了求解非线性互补问题的模系矩阵分裂迭代方法.

算法1[12]  令M=F-G为矩阵M的一个分裂,给定初始向量x(0)Rn, 对于k=1, 2, …, 从下列方程组中解出x(k)

$ \begin{array}{*{20}{c}} {\left( {\mathit{\boldsymbol{ \boldsymbol{\varPsi} }} + \mathit{\boldsymbol{F}}} \right){\mathit{\boldsymbol{x}}^{\left( k \right)}} = \mathit{\boldsymbol{G}}{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + \left( {\mathit{\boldsymbol{ \boldsymbol{\varPsi} }} - \mathit{\boldsymbol{M}}} \right)\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - }\\ {\gamma \left( {\mathit{\boldsymbol{q}} + f\left( {{\mathit{\boldsymbol{z}}^{\left( {k - 1} \right)}}} \right)} \right),} \end{array} $

直至{z(k)}k=1+∞收敛, 其中${\mathit{\boldsymbol{z}}^{\left( \mathit{k} \right)}} = \frac{1}{\mathit{\gamma }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( \mathit{k} \right)}}} \right| + {\mathit{\boldsymbol{x}}^{\left( \mathit{k} \right)}}} \right) $.

为了提高计算效率,下面给出松弛模系矩阵分裂迭代方法.

对于任意给定的正对角矩阵ΩΓ,令z=Ω(|x|+x), w=Γ(|x|-x),=FΩ-GΩ的一个分裂,x满足如下不动点方程

$ \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)\mathit{\boldsymbol{x}} = {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}\mathit{\boldsymbol{x}} + \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left| \mathit{\boldsymbol{x}} \right| - \left( {\mathit{\boldsymbol{q}} + f\left( \mathit{\boldsymbol{z}} \right)} \right) $ (2)

在不动点格式(2)对应的迭代格式中,考虑对原向量和更新的向量做一个加权,通过引入一个非奇异的参数矩阵PRn×n,建立如下松弛模系矩阵分裂迭代方法.

算法2  对于任意给定的正对角矩阵ΩΓ,令=FΩ-GΩ为矩阵Rn×n的一个分裂.给定初始向量x(0)Rn,对于k=1, 2, …,通过求解如下系统:

$ \left\{ \begin{array}{l} \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{ \boldsymbol{F} }}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right){\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}} = {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;q - f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| + {\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right)} \right)\\ {\mathit{\boldsymbol{x}}^{\left( k \right)}} = \left( {I - \mathit{\boldsymbol{P}}} \right){\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + \mathit{\boldsymbol{P}}{\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}} \end{array} \right. $ (3)

得到x(k),令z(k)=Ω(|x(k)|+x(k).

系统(3)等价于

$ \begin{array}{*{20}{c}} {{\mathit{\boldsymbol{x}}^{\left( k \right)}} = \left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right){\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + \mathit{\boldsymbol{P}}{{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)}^{ - 1}}\left[ {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + } \right.}\\ {\left. {\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \mathit{\boldsymbol{q}} - f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| + {\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right)} \right)} \right]} \end{array} $ (4)

算法2提供了松弛模系矩阵分裂迭代方法的一个基本框架.特别地,取

$ \left\{ \begin{array}{l} {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} = \frac{1}{\alpha }\left( {{\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} - \mathit{\boldsymbol{\beta }}{\mathit{\boldsymbol{L}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right)\\ {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} = \frac{1}{\alpha }\left( {\left( {1 - \alpha } \right){\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} + \left( {\alpha - \beta } \right){\mathit{\boldsymbol{L}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} + \alpha {\mathit{\boldsymbol{U}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right) \end{array} \right. $

α, β分别取α=β, α=β=1和α=1, β=0时,称为松弛模系逐步超松弛迭代格式(RMSOR)、松弛模系高斯赛德尔迭代格式(RMGS)和松弛模系雅克比迭代格式(RMJ).

$\mathit{\boldsymbol{ \boldsymbol{\varOmega} = }}\frac{1}{\mathit{\gamma }}\mathit{\boldsymbol{I, \boldsymbol{\varGamma} = }}\frac{1}{\mathit{\gamma }}\mathit{\boldsymbol{ \boldsymbol{\varPsi} }} $, P=I,算法2即为模系矩阵分裂迭代方法.

特别地,令P=εI, 系统(3)等价为如下形式:

$ \left\{ \begin{array}{l} \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right){\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}} = {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;q - f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| + {\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right)} \right)\\ {\mathit{\boldsymbol{x}}^{\left( k \right)}} = \left( {1 - \varepsilon } \right){\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} + \varepsilon {\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}} \end{array} \right. $ (5)

这里,εR\{0}, 并且ε随着k的变化而变化.

2 收敛性分析

H+-矩阵在数学物理问题、控制论、电力系统理论、经济数学以及弹性力学等众多领域中都有广泛应用,例如经济价值模型、反网络分析模型、经济学中的投入产出增长模型和概率统计中的Markov链等问题.

给定两个实矩阵M=(mij), N=(nij)∈Rm×n, 如果对任意的1≤im, 1≤jn都有mijnij(mij>nij), 则记MN(M>N).本文用记号|M|=(|mij|)∈Rm×n表示M的绝对值.

MRn×n为一个实n×n矩阵,它的比较矩阵〈M〉=(〈mij)定义为

$ {\left\langle m \right\rangle _{ij}} = \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} \left| {{m_{ij}}} \right|,\\ - \left| {{m_{ij}}} \right|, \end{array}&\begin{array}{l} i = j,\\ i \ne j, \end{array} \end{array}} \right.\;\;\;\;i,j = 1,2, \cdots ,n $

若对任意ij, 有mij≤0, 则称MZ-矩阵.若M为非奇异的Z-矩阵且M-1O, O为零矩阵, 则称MM-矩阵.如果〈M〉为M-矩阵, 则称MH-矩阵.对于H-矩阵M, 有M非奇异, 且|M-1|≤〈M-1.特别地, 对角元为正的H-矩阵称为H+-矩阵.

给定MRn×n, 设M=F-G, 如果F非奇异, 则称M=F-G为矩阵M的一个分裂; 如果F是非奇异的M-阵并且G≥0, 则称分裂为M-分裂;当〈F〉-|G|是一个M-矩阵,则称M=F-G是一个H-分裂;如果〈M〉=〈F〉-|G|, 则称分裂为H-相容分裂.

引理1[14]  如果矩阵MRn×n是严格对角占优的,对于任意矩阵NRn×n

$ {\left\| {{\mathit{\boldsymbol{M}}^{ - 1}}\mathit{\boldsymbol{N}}} \right\|_\infty } \le \mathop {\max }\limits_{1 \le i \le n} \frac{{{{\left( {\left| \mathit{\boldsymbol{N}} \right|\mathit{\boldsymbol{e}}} \right)}_i}}}{{{{\left( {\left\langle \mathit{\boldsymbol{M}} \right\rangle \mathit{\boldsymbol{e}}} \right)}_i}}} $

成立,这里e=(1, …, 1)TRn.

引理2[15]  矩阵M是一个对角元为正的Z-阵, M是一个M-阵当且仅当存在一个正对角矩阵D, 使得MD是对角元为正的严格对角占优矩阵.

引理3[8]  令MRn×n是一个H+-矩阵,=FΩ-GΩ为矩阵H-分裂.则存在一个正对角矩阵D使得(〈FΩ〉-|GΩ|)D和(Γ+〈FΩ〉)D是两个严格对角占优矩阵,且有

${\left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left\langle {\mathit{\boldsymbol{F \boldsymbol{\varOmega} }}} \right\rangle - \left| {\mathit{\boldsymbol{G \boldsymbol{\varOmega} }}} \right|} \right)\mathit{\boldsymbol{D}}\mathit{e}} \right]_\mathit{i}} > 0,i = 1,2, \cdots ,n $

下面, 考虑算法2的收敛性.假设对角可微函数f满足

$ 0 \le \frac{{{\rm{d}}{f_i}}}{{{\rm{d}}{z_i}}} \le {{\bar j}_i},\;\;\;i = 1,2, \cdots ,n $

这里ji, i=1, 2, …, n, 是非负常数.记:J=diag{j1, …, jn}.

令(z*, w*)为非线性互补问题(1)的解,易知${\mathit{\boldsymbol{x}}_\mathit{\boldsymbol{*}}} = \frac{1}{2}\left( {{\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{ - 1}}{\mathit{\boldsymbol{z}}_*} - {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }}^{ - 1}}{\mathit{\boldsymbol{w}}_*}} \right) $满足

$ \begin{array}{l} {\mathit{\boldsymbol{x}}_ * } = \left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right){\mathit{\boldsymbol{x}}_ * } + \mathit{\boldsymbol{P}}{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)^{ - 1}}\left[ {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}{\mathit{\boldsymbol{x}}_ * } + } \right.\\ \;\;\;\left. {\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left| {{\mathit{\boldsymbol{x}}_ * }} \right| - \mathit{\boldsymbol{q}} - f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}_ * }} \right| + {\mathit{\boldsymbol{x}}_ * }} \right)} \right)} \right] \end{array} $ (6)

由于f是对角可微的,根据均值定理,有

$ \begin{array}{l} f\left( {{\mathit{\boldsymbol{z}}^{\left( k \right)}}} \right) - f\left( {{\mathit{\boldsymbol{z}}_ * }} \right) = f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( k \right)}}} \right| + {\mathit{\boldsymbol{x}}^{\left( k \right)}}} \right)} \right) - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}_ * }} \right| + {\mathit{\boldsymbol{x}}_ * }} \right)} \right) = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\mathit{\boldsymbol{J}}^{\left( k \right)}}\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( k \right)}}} \right| - \left| {{\mathit{\boldsymbol{x}}_ * }} \right| + {\mathit{\boldsymbol{x}}^{\left( k \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) \end{array} $

这里,${\mathit{\boldsymbol{J}}^{\left( k \right)}} = {\rm{diag}}\left( {\frac{{\partial {f_1}}}{{\partial {\mathit{z}_1}}}, \cdots , \frac{{\partial {f_\mathit{n}}}}{{\partial {z_n}}}} \right) $f(z)在点ξ(k)处的雅克比矩阵,其中,ξ(k)是位于Ω(|x(k)|+x(k))和Ω(|x*|+x*)之间的向量.由假设知J(k)≥0, 用式(4)减去式(6)得

$ \begin{array}{l} {\mathit{\boldsymbol{x}}^{\left( k \right)}} - {\mathit{\boldsymbol{x}}_ * } = \left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right)\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathit{\boldsymbol{P}}{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)^{ - 1}}\left[ {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) + } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \left| {{\mathit{\boldsymbol{x}}_ * }} \right|} \right) - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| + {\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right)} \right) - } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {\left. {f\left( {\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}_ * }} \right| + {\mathit{\boldsymbol{x}}_ * }} \right)} \right)} \right)} \right] = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right)\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathit{\boldsymbol{P}}{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)^{ - 1}}\left[ {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) + } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right)\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \left| {{\mathit{\boldsymbol{x}}_ * }} \right|} \right) - \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {{\mathit{\boldsymbol{J}}^{\left( {k - 1} \right)}}\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \left| {{\mathit{\boldsymbol{x}}_ * }} \right| + {\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right)} \right] \end{array} $ (7)

矩阵M是一个H+-矩阵,=FΩ-GΩ为矩阵的一个H-分裂,下面给出算法2的收敛性分析.在式(7)两边同时加上绝对值,记JΩ(k-1):=J(k-1)Ω,由于0≤(Γ+FΩ)-1≤(Γ+〈FΩ〉)-1,有

$ \begin{array}{l} \left| {{\mathit{\boldsymbol{x}}^{\left( k \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right| = \\ \;\;\left| {\mathit{\boldsymbol{P}}{{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)}^{ - 1}}\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)\left( {{\mathit{\boldsymbol{P}}^{ - 1}} - \mathit{\boldsymbol{I}}} \right)\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) + } \right.\\ \;\;\mathit{\boldsymbol{P}}{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)^{ - 1}}\left[ {\left( {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right)\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right) + } \right.\\ \;\;\left. {\left. {\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right)\left( {\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}}} \right| - \left| {{\mathit{\boldsymbol{x}}_ * }} \right|} \right)} \right]} \right| \le \\ \;\;\mathit{\boldsymbol{P}}\left| {{{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)}^{ - 1}}} \right|\left[ {\left| {\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)\left( {{\mathit{\boldsymbol{P}}^{ - 1}} - \mathit{\boldsymbol{I}}} \right) + {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} - } \right.} \right.\\ \;\;\left. {\left. {\mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right| + \left| {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|} \right]\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right| \le \\ \;\;\mathit{\boldsymbol{P}}{\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle } \right)^{ - 1}}\left[ {\left| {\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)\left( {{\mathit{\boldsymbol{P}}^{ - 1}} - \mathit{\boldsymbol{I}}} \right) + {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}} - } \right.} \right.\\ \;\;\left. {\left. {\mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right| + \left| {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|} \right]\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right| = \\ \;\;\mathit{\boldsymbol{\hat L}}\left| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right| \end{array} $

这里,$\mathit{\boldsymbol{\hat L = P}}{\mathit{\boldsymbol{\tilde F}}^{ - 1}}\mathit{\boldsymbol{\tilde G}}{\mathit{\boldsymbol{P}}^{{\rm{ - 1}}}} $, 其中

$ \mathit{\boldsymbol{\tilde F}} = \mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle $ (8)
$ \begin{array}{l} \mathit{\boldsymbol{\tilde G}} = \left| {\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right)\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right) + {\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}\mathit{\boldsymbol{P}}} \right| + \\ \;\;\;\;\;\;\left| {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - \mathit{\boldsymbol{M \boldsymbol{\varOmega} }} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} \end{array} $ (9)

引理4  令M是一个H+-矩阵,=FΩ-GΩ的一个H-分裂,P为正对角矩阵,Γ为满足条件(Γe)i≥[(D+J)e]i的正对角矩阵,矩阵$\mathit{\boldsymbol{\tilde F}} $$\mathit{\boldsymbol{\tilde G}} $分别由公式(8)和(9)给出,如果

$ \left\{ \begin{array}{l} \left\{ {\left[ {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + 2{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}} - \left( {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| + \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - } \right.} \right.} \right.\\ \;\;\;\;\;\;\;\;\;\;{\left. {\left. {\left. {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle } \right)\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_\mathit{\boldsymbol{i}}} > 0,\\ \;\;\;\;\;\;\;\;\;\;当\;{\left( {\mathit{\boldsymbol{Pe}}} \right)_i} \ge 1\;时\\ \left\{ {\left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right|} \right)\mathit{\boldsymbol{P}} - } \right.} \right.\\ \;\;\;\;\;\;\;\;\;\;{\left. {\left. {2\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|} \right]\mathit{\boldsymbol{De}}} \right\}_\mathit{\boldsymbol{i}}} > 0,\\ \;\;\;\;\;\;\;\;\;\;当\;0 < {\left( {\mathit{\boldsymbol{Pe}}} \right)_i} < 1\;时 \end{array} \right. $ (10)

则有ρ($\mathit{\boldsymbol{\hat L}} $) < 1.其中矩阵D由引理3给出.

证明  由$\mathit{\boldsymbol{\hat L}} $的定义,有

$ \begin{array}{l} {\left\| {{\mathit{\boldsymbol{D}}^{ - 1}}{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{\hat LPD}}} \right\|_\infty } = {\left\| {{\mathit{\boldsymbol{D}}^{ - 1}}{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{P}}{{\mathit{\boldsymbol{\tilde F}}}^{ - 1}}\mathit{\boldsymbol{\tilde GG}}{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{PD}}} \right\|_\infty } = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\left\| {{\mathit{\boldsymbol{D}}^{ - 1}}{{\mathit{\boldsymbol{\tilde F}}}^{ - 1}}\mathit{\boldsymbol{\tilde GD}}} \right\|_\infty } = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\left\| {{{\left( {\mathit{\boldsymbol{\tilde FD}}} \right)}^{ - 1}}\mathit{\boldsymbol{\tilde GD}}} \right\|_\infty } \end{array} $

由于=FΩ-GΩ是一个H-分裂,由H-分裂的定义易知〈FΩ〉-|GΩ|是一个M-矩阵,此外,Γ+〈FΩ〉也是一个M-矩阵.由引理2,知道$\mathit{\boldsymbol{\tilde FD = }}\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} + }}\left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle } \right)\mathit{\boldsymbol{D}} $是严格对角占优的,利用引理1,得到

$ {\left\| {{\mathit{\boldsymbol{D}}^{ - 1}}{\mathit{\boldsymbol{P}}^{ - 1}}\mathit{\boldsymbol{LPD}}} \right\|_\infty } = {\left\| {{{\left( {\mathit{\boldsymbol{\tilde FD}}} \right)}^{ - 1}}\mathit{\boldsymbol{\tilde GD}}} \right\|_\infty } \le \mathop {\max }\limits_{1 \le i \le n} \frac{{{{\left( {\mathit{\boldsymbol{\tilde GDe}}} \right)}_i}}}{{{{\left( {\mathit{\boldsymbol{\tilde FDe}}} \right)}_i}}} $

下面,证明对于任意1≤in,都有${\left( {\mathit{\boldsymbol{\tilde FDe}}} \right)_i} > {\left( {\mathit{\boldsymbol{\tilde GDe}}} \right)_i}\ $.

根据式(9),令$\mathit{\boldsymbol{\tilde G = }}{\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{\tilde G}}}} - {\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{\tilde G}}}} $, ${\mathit{\boldsymbol{\tilde G}}} $的对角元满足

$ \begin{array}{l} {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{\tilde G}}}} \le \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\left| {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right| + \left| {{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} + \\ \;\;\;\;\;\;\;\;\left| {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} \end{array} $

${\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{\tilde G}}}} $的对角元满足

$ \begin{array}{l} {\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{\tilde G}}}} = - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right) + {\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}\mathit{\boldsymbol{P}}} \right| - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}} \ge \\ \;\;\;\;\;\;\;\; - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\left| {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right| - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}} \end{array} $

进而,有

$ \begin{array}{l} {\left( {\mathit{\boldsymbol{\tilde FDe}}} \right)_i} - {\left( {\mathit{\boldsymbol{\tilde GDe}}} \right)_i} = {\left[ {\left( {\mathit{\boldsymbol{\tilde F}} - {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{\tilde G}}}} + {\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{\tilde G}}}}} \right)\mathit{\boldsymbol{De}}} \right]_i} \ge \\ \left\{ {\left[ {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle - \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\left| {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right| - } \right.} \right.\\ \left| {{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} - \left| {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} - \\ {\left. {\left. {\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\left| {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right| - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_i}. \end{array} $ (11)

基于(Γe)i≥[(D+J)e]i的假设,从以下两个方面来讨论.

情况1:如果(Pe)i≥1,由式(11)可得到

$ \begin{array}{l} {\left( {\mathit{\boldsymbol{\tilde FDe}}} \right)_i} - {\left( {\mathit{\boldsymbol{\tilde GDe}}} \right)_i} \ge \left\{ {\left[ {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle - } \right.} \right.\\ \;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\left( {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right) - \left| {{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} - \\ \;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right)\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\left( {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right) - \\ \;\;\;\;\;\;\;{\left. {\left. {\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_i} \ge \left\{ {\left[ {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle - } \right.} \right.\\ \;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\left( {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right) - \left| {{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right)\mathit{\boldsymbol{P}} - \\ \;\;\;\;\;\;\;{\left. {\left. {\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\left( {\mathit{\boldsymbol{P}} - \mathit{\boldsymbol{I}}} \right) - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_i} = \\ \;\;\;\;\;\;\;\left\{ {\left[ {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + 2{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}} - \left( {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| + \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - } \right.} \right.} \right.\\ \;\;\;\;\;\;\;{\left. {\left. {\left. {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle } \right)\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_i} > 0 \end{array} $ (12)

情况2:如果0 < (Pe)i<1,有

$ \begin{array}{l} {\left( {\mathit{\boldsymbol{\tilde FDe}}} \right)_i} - {\left( {\mathit{\boldsymbol{\tilde GDe}}} \right)_i} \ge \left\{ {\left[ {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle - } \right.} \right.\\ \;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right) - \left| {{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right|\mathit{\boldsymbol{P}} - \\ \;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}} - \mathit{\boldsymbol{J}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}^{\left( {k - 1} \right)}} \right)\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right) - \\ \;\;\;\;\;\;\;{\left. {\left. {\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_i} \ge \left\{ {\left[ {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left\langle {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right\rangle - } \right.} \right.\\ \;\;\;\;\;\;\;\left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + {\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right) - \left| {{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left( {\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} - {\mathit{\boldsymbol{D}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right)\mathit{\boldsymbol{P}} - \\ \;\;\;\;\;\;\;{\left. {\left. {\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\left( {\mathit{\boldsymbol{I}} - \mathit{\boldsymbol{P}}} \right) - \left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{P}} - \left| {{\mathit{\boldsymbol{B}}_{\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}}}} \right|\mathit{\boldsymbol{P}}} \right]\mathit{\boldsymbol{De}}} \right\}_i} = \\ \;\;\;\;\;\;\;\left\{ {\left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right|} \right)\mathit{\boldsymbol{P}} - } \right.} \right.\\ \;\;\;\;\;\;\;{\left. {\left. {2\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|} \right]\mathit{\boldsymbol{De}}} \right\}_i} > 0. \end{array} $ (13)

结合式(12)和式(13),得到不等式(10).证毕.

基于引理4,建立如下收敛性定理.

定理1  令M是一个H+-矩阵,=FΩ-GΩ的一个H-分裂,P=εI是一个正对角矩阵,Γ是满足条件(Γe)i≥[(D+J)e]i的正对角矩阵,然后对于任意给定的初始向量x(0)Rn,如果

$ {a_i} < \varepsilon < {b_i} $

其中,D由引理3给出,则

$ \begin{array}{*{20}{c}} {{a_i} = \frac{{{{\left( {2\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{De}}} \right)}_i}}}{{{{\left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right|} \right)\mathit{\boldsymbol{De}}} \right]}_i}}}}\\ {{b_i} = \frac{{{{\left[ {\left( {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + 2{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\mathit{\boldsymbol{De}}} \right]}_i}}}{{{{\left[ {\left( {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| + \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - \left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle } \right)\mathit{\boldsymbol{De}}} \right]}_i}}}}\\ {i = 1,2, \cdots ,n} \end{array} $ (14)

由算法2生成的迭代序列收敛到非线性互补问题(1)的解x*.

证明  基于假设(Γe)i≥[(D+Je]i,结合条件(10),由引理3,得到

$ \begin{array}{l} {\left[ {\left( {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + 2{\mathit{\boldsymbol{D}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right)\mathit{\boldsymbol{De}}} \right]_i} - \left[ {\left( {2\mathit{\boldsymbol{ \boldsymbol{\varGamma} }} + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| + \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - } \right.} \right.\\ \;\;\;\;\;\;\;{\left. {\left. {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle } \right)\mathit{\boldsymbol{De}}} \right]_i} = \left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - } \right.} \right.\\ \;\;\;\;\;\;\;{\left. {\left. {\left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right|} \right)\mathit{\boldsymbol{De}}} \right]_i} > 0 \end{array} $

以及

$ \begin{array}{l} {\left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right|} \right)\mathit{\boldsymbol{De}}} \right]_i} - 2{\left( {\left| {{\mathit{\boldsymbol{B}}_{{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}}}} \right|\mathit{\boldsymbol{De}}} \right)_i} = \\ \;\;\;\;\;\;\;\;\;{\left[ {\left( {\left\langle {\mathit{\boldsymbol{M \boldsymbol{\varOmega} }}} \right\rangle + \left| {{\mathit{\boldsymbol{F}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right| - \left| {{\mathit{\boldsymbol{G}}_\mathit{\boldsymbol{ \boldsymbol{\varOmega} }}}} \right|} \right)\mathit{\boldsymbol{De}}} \right]_i} > 0 \end{array} $

然后,有0 < ai < 1 < bi.

在引理4中, 令P=εI, 如果松弛参数ε满足ai < ε < bi,有$\mathit{\rho }\left( {\mathit{\boldsymbol{\hat L}}} \right) $ < 1, 则算法2收敛到非线性互补问题的解z*Rn.证毕.

注1  定理1给出了松弛参数ε的一个区域,可以保证算法2的收敛.在文献[11]中,给出求解线性互补问题的理论最优参数,

$ \varepsilon = 1 + \frac{{{{\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}} - {\mathit{\boldsymbol{x}}_ * }} \right)}^{\rm{T}}}\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}}} \right)}}{{\left\| {{\mathit{\boldsymbol{x}}^{\left( {k - 1} \right)}} - {\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}}} \right\|_2^2}} $

由于x*未知,在具体实现时,x*x(k-1/2)代替,并且用k-1代替k.因此,松弛参数ε的一个合理的选择为

$ {\varepsilon ^{\left( k \right)}} = 1 + \frac{{{{\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 3/2} \right)}} - {\mathit{\boldsymbol{x}}^{\left( {k - 1/2} \right)}}} \right)}^{\rm{T}}}\left( {{\mathit{\boldsymbol{x}}^{\left( {k - 2} \right)}} - {\mathit{\boldsymbol{x}}^{\left( {k - 3/2} \right)}}} \right)}}{{\left\| {{\mathit{\boldsymbol{x}}^{\left( {k - 2} \right)}} - {\mathit{\boldsymbol{x}}^{\left( {k - 3/2} \right)}}} \right\|_2^2}} $ (15)

在第k步,松弛参数ε的选取方法如下:

$ \varepsilon = \left\{ \begin{array}{l} 1,\;\;\;\;\;\;\;\;当\;k = 1\;时\\ {\varepsilon ^{\left( k \right)}},\;\;\;\;\;当\;k > 1\;时\;{\varepsilon ^{\left( k \right)}} \in \left( {a,b} \right)\\ a,\;\;\;\;\;\;\;\;当\;k > 1\;时\;{\varepsilon ^{\left( k \right)}} \le a\\ b,\;\;\;\;\;\;\;\;当\;k > 1\;时\;{\varepsilon ^{\left( k \right)}} \ge b \end{array} \right. $ (16)

这里, a, b由定理1给出.

3 数值实验

本节通过数值实验验证几种松弛模系矩阵分裂迭代法求解非线性互补问题(1)的有效性.

在数值实验中, 初始向量取为x(0)=(1, 1, …, 1)TRn, Γ=2DM,对于MSOR方法和RMSOR方法,松弛参数取α=1.2,停止准则设定为

$ \mathit{\boldsymbol{E}}\left( {{\mathit{\boldsymbol{z}}^{\left( k \right)}}} \right): = \frac{{{{\left\| {\min \left( {\mathit{\boldsymbol{M}}{\mathit{\boldsymbol{z}}^{\left( k \right)}} + \mathit{\boldsymbol{q}} + \mathit{\boldsymbol{f}}\left( {{\mathit{\boldsymbol{z}}^{\left( k \right)}}} \right),{\mathit{\boldsymbol{z}}^{\left( k \right)}}} \right)} \right\|}_2}}}{{{{\left\| {\min \left( {\mathit{\boldsymbol{M}}{\mathit{\boldsymbol{z}}^{\left( 0 \right)}} + \mathit{\boldsymbol{q}} + \mathit{\boldsymbol{f}}\left( {{\mathit{\boldsymbol{z}}^{\left( 0 \right)}}} \right),{\mathit{\boldsymbol{z}}^{\left( 0 \right)}}} \right)} \right\|}_2}}} \le {10^{ - 6}} $

所有计算均在一台CPU为2.40 GHz和内存为4.00 GB的机器上运行, 编程语言为MATLAB.

例1  设m为给定的正整数, n=m2.在式(1)中取$\mathit{\boldsymbol{M}} = \mathit{\boldsymbol{\hat M + }}{\rm{4}}\mathit{\boldsymbol{I}} $, 其中

$ \mathit{\boldsymbol{\hat M}} = \left( {\begin{array}{*{20}{c}} \mathit{\boldsymbol{S}}&{ - \mathit{\boldsymbol{I}}}&0& \cdots &0\\ { - \mathit{\boldsymbol{I}}}&\mathit{\boldsymbol{S}}&{}&{}& \vdots \\ 0&{}&{}&{}&0\\ \vdots &{}&{}&S&{ - I}\\ 0& \cdots &0&{ - I}&S \end{array}} \right) \in {{\bf{R}}^{n \times n}} $

为块三对角矩阵, 其中S=tridiag(-1, 4, -1)∈Rm×m为三对角矩阵,

$ q = {\left( { - 1,1, \cdots ,{{\left( { - 1} \right)}^n}} \right)^{\rm{T}}} \in {{\bf{R}}^n}, $
$ \mathit{\boldsymbol{f}}\left( \mathit{\boldsymbol{z}} \right) = {\left( {\sqrt {\mathit{\boldsymbol{z}}_1^2 + 0.01} , \cdots ,\sqrt {\mathit{\boldsymbol{z}}_\mathit{\boldsymbol{n}}^2 + 0.01} } \right)^{\rm{T}}} \in {{\bf{R}}^n}. $

表 1给出了松弛参数ε的选取策略.对于例1,式(14)中取D=I.基于定理1,通过简单地计算,对于RMJ,RMGS,RMSOR方法, 策略2中的(a, b)为

下载CSV 表 1 3种策略描述 Tab.1 Description of three strategies
$ \begin{array}{*{20}{c}} {\left( {0,1.200\;0} \right),\left( {0.333\;3,1.200\;0} \right),}\\ {\left( {0.428\;6,1.133\;3} \right)} \end{array} $ (17)

策略3中(a, b)为

$ \left( {0,1.333\;3} \right),\left( {0,1.333\;3} \right),\left( {0,1.259\;3} \right) $ (18)

表 2分别列出当n=1 600, 松弛参数ε在0.5~1.5之间变化时几种迭代法的迭代步数(记作IT)和迭代时间(记作CPU).

下载CSV 表 2 例1的3种迭代法的迭代时间和迭代步数随参数ε的变化 Tab.2 IT and CPU for three methods with the change of ε for Example 1

表 2中可以看出,当松弛参数ε < 1时,算法2需要的迭代步数和计算时间比算法1多,当ε增大时,对于RMJ方法,迭代步数和计算时间是不断下降的,而RMGS方法和RMSOR方法的迭代步数和计算时间先减少后增大.当ε不在收敛区域时,迭代方法不收敛.

此外,ε≥1时三种方法比ε < 1时收敛得快,这表明在公式(15)中,精确解更靠近x(k-1/2).松弛参数的三种选取策略数值实验显示在表 2的最后三行.从表 2最后三行可以看出,基于三种选取策略的算法2明显优于算法1,且策略1是最优策略.

当矩阵维数不断增大时,数值实验结果显示在表 3中.从表 3中可以得出,无论是计算时间还是迭代步数,基于2种策略的算法2明显优于算法1.

下载CSV 表 3 矩阵维数变化时例1两种算法比较 Tab.3 Comparison of two algorithms with the change of n for Example 1

例2  设m为给定的正整数, n=m2.在式(1)中取

$ \mathit{\boldsymbol{M}} = \left( {\begin{array}{*{20}{c}} \mathit{\boldsymbol{S}}&{ - \mathit{\boldsymbol{I}}}&{ - \mathit{\boldsymbol{I}}}& \cdots &{}&0\\ {}&\mathit{\boldsymbol{S}}&{ - \mathit{\boldsymbol{I}}}&{ - \mathit{\boldsymbol{I}}}&{}&{}\\ \vdots &{}&{}&{}&{}& \vdots \\ {}&{}&{}&\mathit{\boldsymbol{S}}&{ - \mathit{\boldsymbol{I}}}&{ - \mathit{\boldsymbol{I}}}\\ {}&{}&{}&{}&\mathit{\boldsymbol{S}}&{ - \mathit{\boldsymbol{I}}}\\ 0&{}& \cdots &{}&{}&\mathit{\boldsymbol{S}} \end{array}} \right) \in {{\bf{R}}^{n \times n}} $

为块三对角矩阵, S=tridiag-1, 4, -1∈Rm×m为三对角矩阵,

$ \begin{array}{l} \mathit{\boldsymbol{q}} = {\left( { - 1,1, \cdots ,{{\left( { - 1} \right)}^n}} \right)^{\rm{T}}} \in {{\bf{R}}^n},f\left( \mathit{\boldsymbol{z}} \right) = \\ \;\;\;\;\;{\left( {{z_1} - \sin {z_1}, \cdots ,{z_n} - \sin {z_n}} \right)^{\rm{T}}} \in {{\bf{R}}^n}. \end{array} $

对于例2,式(14)中取D=diag[(〈FΩ〉-|GΩ|)-1e].基于定理1,通过简单的计算,对于RMJ,RMGS,RMSOR方法, 策略2的中a, b

$ \left( {0,1.333\;3} \right),\left( {0,1.333\;3} \right),\left( {0,1.259\;3} \right) $ (18)
$ \left( {0.748\;9,1.062\;5} \right) $ (19)

策略3中的(a, b)为

$ \left( {0,1.294\;8} \right),\left( {0,1.294\;8} \right),\left( {0,1.199\;1} \right) $ (20)

表 4分别列出当n=1 600, 松弛参数ε在0.5~1.5之间变化时几种迭代法的迭代步数和迭代时间.从表 4中可以看出,当松弛参数ε < 1时,算法2需要的迭代步数和计算时间比算法1多,当ε增大时,对于RMJ方法,迭代步数和计算时间是不断下降的,而RMGS方法和RMSOR方法的迭代步数和计算时间先减少后增大.算法2的实际收敛区域比式(18)、式(19)要大,因此,收敛区域还可以进行改进.

下载CSV 表 4 例2的三种迭代法的迭代时间和迭代步数随参数ε的变化 Tab.4 IT and CPU for three methods with the change of ε for Example 2

松弛参数的三种选取策略数值实验显示在表 4的最后三行.从表 4最后三行可以看出,基于三种选取策略的算法2明显优于算法1,且策略1是最优策略.

当矩阵维数不断增大时,数值实验结果显示在表 5中.从表 5可以得出,无论是计算时间还是迭代步数,基于三种策略的算法2明显优于算法1.

下载CSV 表 5 矩阵维数变化时例2两种算法比较 Tab.5 Comparison of two algorithms with the change of n for Example 2

根据实验结果,得出策略1是最优策略,在图 1图 2中,分别画出基于策略1的算法2和算法1随着迭代步数变化的残差下降曲线.从两张图中可以看出, 算法2收敛速度明显快于算法1,表明提出的新方法是有效的且明显优于模系矩阵分裂迭代方法.

图 1 例1两种算法的残差比较 Fig.1 Residual comparison of two algorithms for Example 1
图 2 例2两种算法的残差比较 Fig.2 Residual comparison of two algorithms for Example 2
4 结论

本文构造了求解一类非线性互补问题的松弛模系矩阵分裂迭代法, 理论上分析了当矩阵MH+-矩阵时的收敛性,并且给出了最优参数的选取方法.数值实验进一步验证了松弛模系矩阵分裂迭代法的有效性.数值结果表明, 松弛模系矩阵分裂迭代法无论在迭代步数还是迭代时间上均优于模系矩阵分裂迭代法.

参考文献
[1]
ORTEGA J M, RHEINBOLDT W C. Iterative solution of nonlinear equations in several variables[M]. New York: Academic Press, 1970
[2]
BAI Z Z. Parallel nonlinear AOR method and its convergence[J]. Computers and Mahtematics with Applications, 1996, 31(2): 21 DOI:10.1016/0898-1221(95)00190-5
[3]
FERRIS M C, PANG J S. Engineering and economic applications of complementarity problems[J]. SIAM Review, 1997, 39(4): 669 DOI:10.1137/S0036144595285963
[4]
COTTLE R W, PANG J S, STONE R E. The linear complementarity problem[M]. San Diego: Academic Press, 2009
[5]
BAI Z Z. Modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2010, 17(6): 917 DOI:10.1002/nla.v17.6
[6]
ZHANG L L. Two-step modulus-based matrix splitting iteration method for linear complementarity problems[J]. Numerical Algorithms, 2011, 57(1): 83 DOI:10.1007/s11075-010-9416-7
[7]
ZHENG N, YIN J F. Accelerated modulus-based matrix splitting iteration methods for linear complementarity problems[J]. Numerical Algorithms, 2013, 64(2): 245 DOI:10.1007/s11075-012-9664-9
[8]
ZHENG H, LI W, VONG S. A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems[J]. Numerical Algorithms, 2017, 74(1): 137 DOI:10.1007/s11075-016-0142-7
[9]
BAI Z Z, ZHANG L L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Numerical Linear Algebra with Applications, 2013, 20(3): 425 DOI:10.1002/nla.1835
[10]
BAI Z Z, ZHANG L L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems[J]. Numerical Algorithms, 2013, 62(1): 59 DOI:10.1007/s11075-012-9566-x
[11]
ZHANG L L. Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems[J]. Journal of Computational Mathematics, 2015, 33(1): 100 DOI:10.4208/jcm
[12]
XIA Z C, LI C L. Modulus-based matrix splitting iteration methods for a class of nonlinear complementarity problem[J]. Applied Mathematics and Computation, 2015, 271: 34 DOI:10.1016/j.amc.2015.08.108
[13]
LI R, YIN J F. Accelerated modulus-based matrix splitting iteration methods for a class of restricted nonlinear complementarity problems[J]. Numerical Algorithms, 2017, 75(2): 339 DOI:10.1007/s11075-016-0243-3
[14]
HU J G. Estimates of ‖B-1C and their applications[J]. Mathematica Numerica Sinica, 1982, 4: 272
[15]
BERMAN A, PLEMMONS R J. Nonnegative matrix in the mathematical science[M]. Philadelphia: SIAM Publisher, 1994