求解绝对值方程的SOR-Like-PSS迭代法

SOR-Like-PSS Iteration Method for Solving Absolute Value Equations

摘要: 本文结合预条件移位分裂迭代法，提出了一种求解绝对值方程的SOR-like-PSS迭代法，证明了该方法的收敛性。数值实验表明，SOR-like-PSS迭代法收敛到精确解的迭代步数以及耗时都比SOR-like法更优。

Abstract: This paper develops a SOR-like-PSS iteration method through the incorporation of preconditioned shift-splitting (PSS) for solving absolute value equations, with rigorous convergence analysis. Numerical experiments demonstrate that the proposed SOR-like-PSS method requires fewer iterations and less computational time than conventional SOR-like approaches to achieve machine-precision solutions.

1. 引言

本文研究绝对值方程(Absolute Value Equation, AVE)的求解问题，其基本形式为：

$Ax-\left|x\right|=b$ (1)

其中$A=\left(a_{ij}\right)\in {ℝ}^{n\times n}$ 为n阶实系数矩阵，$b\in {ℝ}^n$ 为实常数向量，$\left|x\right|$ 表示由向量$x$ 的分量的绝对值组成的向量。

绝对值方程AVE (1)在科学与工程计算中具有广泛应用。例如，线性规划、二次规划及双矩阵博弈等问题均可转化为线性互补问题(LCP) [1] [2]。基于模方法，LCP可重新表述为形如(1)的绝对值方程组[3]。特别地，文献[4]-[9]提出了一系列基于模的矩阵分裂迭代方法来求解LCP的解。

近年来，许多学者对AVE (1)的唯一可解性进行了研究，如Wu和Li在[10]中给出了AVE (1)唯一可解的两个充要条件和一些充分条件。AV (1)的更多可解性条件可以在[11]等参考文献中找到。为了逼近其数值解，一些学者已经提出了大量的方法来求解AVE (1)，包括修正或广义牛顿法[1] [12]，矩阵分裂迭代法[13]，Picard型方法[14]，神经网络模型方法[15] [16]等。

文献[17]通过将绝对值方程(1)转化为一个等价的块结构非线性方程组，提出了一类基于块系数矩阵分裂的SOR-like迭代法。受这一方法的启发，后续研究进一步发展了多种基于等效2 × 2块形式的迭代方法，用于求解绝对值方程。这些方法主要包括：不动点迭代方法[18]，修正不动点(MFPI)迭代方法[19]、移位分裂不动点迭代方法[20]、预条件移位分裂不动点迭代方法[21]。这些方法的核心思想是利用矩阵分裂技术或等效变换，将原始问题转化为更适合迭代求解的形式，并结合预条件、松弛因子等策略来加速收敛。

本文在此基础上，结合预条件移位分裂迭代法[22]，提出了一种SOR-like-PSS迭代法。我们严格证明了在参数选取适当时，该方法的迭代序列收敛于AVE (1)的解。进一步的数值实验表明，SOR-like-PSS迭代法在计算效率与求解精度上均表现出显著优势，验证了其可行性与有效性。

本文的组织结构如下。在第1节中，我们给出了一些将在整篇论文中使用的符号和预备工作。在第2节中，我们提出了一种求解AVE (1)的SOR-like-PSS迭代法，并证明了所提出的迭代方法的收敛性。实验结果和参数选择分别在第3和4节中给出，第5节为结论。

2. 预备知识

在下文中，我们给出论文所用到的一些数学符号和基本定义。

设${ℝ}^{n\times n}$ 表示所有实$n\times n$ 矩阵的集合，且${ℝ}^n={ℝ}^{n\times 1}$ 。向量$x\in {ℝ}^n$ 的第$i$ 个分量记为$x_i\left(i=1,\dots ,n\right)$ 。对于$x\in {ℝ}^n$ ，$\text{sign}\left(x\right)$ 表示一个向量，其分量根据$x$ 对应分量的正负或零分别取1、−1或0。$\left|x\right|$ 表示一个向量，其第$i$ 个分量为$\left|x_i\right|$ 。

符号$I$ 表示$n\times n$ 单位矩阵。若$x=\left(x_1,x_2,\dots ,x_n\right)\in {ℝ}^n$ ，则$\text{diag}\left(x\right)$ 表示一个$n\times n$ 的对角矩阵，其$\left(i,i\right)$ 位置元素为$x_i$ 。设$A=\left(a_{ij}\right),B=\left(b_{ij}\right)\in {ℝ}^{n\times n}$ ，如果对所有的$i,j$ 都有$a_{ij}\ge b_{ij}\left(a_{ij}>b_{ij}\right)$ ，则记为$A\ge B\left(A>B\right)$ 。若矩阵$A\in R^{n\times n}$ 的所有元素满足$a_{ij}\ge 0\left(a_{ij}>0\right)$ ，则称其为非负(正)矩阵。对于矩阵$A\in {ℝ}^{n\times n}$ ，${\Vert A\Vert }_2$ 表示其谱范数，定义${\Vert A\Vert }_2:=\max \left\{{\Vert Ax\Vert }_2:x\in {ℝ}^n,{\Vert x\Vert }_2=1\right\}$ ，其中${\Vert x\Vert }_2$ 为2-范数。${\Vert \cdot \Vert }_P$ 表示向量或矩阵的$p$ -范数。${\Vert \cdot \Vert }_{\infty }$ 表示向量或矩阵的$\infty$ 范数。

以下命题已在文献[10]的命题4中得证。

命题1 [3] 设$A\in {ℝ}^{n\times n}$ 非奇异。若${\Vert A^{-1}\Vert }_2<1$ ，则对于任意$b\in {ℝ}^n$ ，绝对值方程(1)存在唯一解。

为后文分析求解绝对值方程(AVE)的SOR-like-PSS法的收敛性，我们给出以下引理。

引理1 [23]-[25]对于任意向量$x,y\in {ℝ}^n$ ，有以下结论：

(1) ${\Vert \left|x\right|-\left|y\right|\Vert }_2\le {\Vert x-y\Vert }_2$ ；

(2) 若$0\le x\le y$ ，则${\Vert x\Vert }_P\le {\Vert y\Vert }_P$ ；

(3) 若$x\le y$ 且$P$ 是非负矩阵，则$Px\le Py$ 。

引理2 [23] [24]对于任意矩阵$A,B\in {ℝ}^{n\times n}$ ，若$0\le A\le B$ ，则${\Vert A\Vert }_P\le {\Vert B\Vert }_P$ 。

引理3 [23] [26]实二次方程$x^2-ax+b=0$ 的两个根的模均小于1的充要条件是$\left|b\right|<1$ 且$\left|a\right|<1+b$ 。

3. 预条件移位分裂SOR-Like迭代法(SOR-Like-PSS)

设$y=\left|x\right|$ ，则AVE(1)等价于

$\{\begin{array}{l}Ax-y=b,\\ -\left|x\right|+y=0.\end{array}$ (2)

其可以被重新表述为下面的2 × 2块非线性方程

$\mathcal{A}z:=\left(\begin{array}{cc}A& -I\\ -D\left(x\right)& I\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}b\\ 0\end{array}\right):=b$ 。 (3)

其中$D\left(x\right)=\text{diag}\left(\text{sign}\left(x\right)\right)$ ，$x\in {ℝ}^n$ 。

注意，(3)式也是非线性的，因为矩阵$D\left(x\right)$ 依赖于变量$x$ 。在实际计算中，求解(3)式也是相当复杂的。

设

$\mathcal{A}=\mathcal{D}-ℒ-\mathcal{U}$ ，

其中

$\mathcal{D}=\left(\begin{array}{cc}A& 0\\ 0& I\end{array}\right)$ ，$ℒ=\left(\begin{array}{cc}0& 0\\ D\left(x\right)& 0\end{array}\right)$ ，$\mathcal{U}=\left(\begin{array}{cc}0& I\\ 0& 0\end{array}\right)$ ，

那么我们可以得到下面的不动点方程

$\left(\mathcal{D}-\omega ℒ\right)z=\left[\left(1-\omega \right)\mathcal{D}+\omega \mathcal{U}\right]z+\omega b$ ，

其中参数$\omega >0$ 。即

$\left(\begin{array}{cc}A& 0\\ -\omega D\left(x\right)& I\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{cc}\left(1-\omega \right)A& \omega I\\ 0& \left(1-\omega \right)I\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)+\left(\begin{array}{c}\omega b\\ 0\end{array}\right)$ 。 (4)

基于不动点方程(4)，我们可以建立如下的矩阵分裂迭代法来求解AVE (1)，称为SOR-like迭代法。

算法1 (用于求解绝对值方程组的SOR-like迭代法[17])

设$A\in {ℝ}^{n\times n}$ 是一个非奇异矩阵，且$b\in {ℝ}^n$ 。给定初始向量$x^{\left(0\right)}\in R^n$ 和$y^{\left(0\right)}\in {ℝ}^n$ ，对于$k=0,1,2,\cdots$ 直

到序列${\left\{x^{\left(k\right)},y^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 收敛，计算：

$\{\begin{array}{l}{x}^{(k+1)}=\left(1-\omega \right)x^{(k)}+\omega A^{-1}\left(y^{(k)}+b\right),\\ y^{(k+1)}=\left(1-\omega \right)y^{(k)}+\omega \left|x^{(k+1)}\right|.\end{array}$ (5)

通过使用矩阵A的以下预条件移位分裂(the preconditioned shift-splitting，简称PSS) [22]

$A=\frac{1}{2}\left(\alpha P+A\right)-\frac{1}{2}\left(\alpha P-A\right)$ ，

其中参数$\alpha$ 是一个正的常数，$P$ 是对称正定矩阵，矩阵$\alpha P+A\in {ℝ}^{n\times n}$ 是非奇异的，从而得到以下方程：

$\{\begin{array}{l}x*=\left(1-\omega \right)x*+\omega {\left(\alpha P+A\right)}^{-1}\left[\left(\alpha P-A\right)x*+2\left(y*+b\right)\right]\\ y*=\left(1-\omega \right)y*+\omega \left|x*\right|\end{array}$ 。 (6)

这就得到了下面的用于AVE(1)的SOR-like-PSS方法，其中$\left(x*,y*\right)$ 是(6)式的解对。

算法2 (用于求解绝对值方程组的SOR-like-PSS迭代法)

设$A\in {ℝ}^{n\times n}$ ，$b\in {ℝ}^n$ 。设$\alpha$ 是一个正的常数，使得$\alpha P+A\in {ℝ}^{n\times n}$ 是非奇异的。 给定初始向量$x^{\left(0\right)}\in {ℝ}^n$ 和$y^{\left(0\right)}\in {ℝ}^n$ ，使用以下迭代方法计算$\left(x^{\left(k+1\right)},y^{\left(k+1\right)}\right)$ ，其中$k=0,1,2,\cdots$ ，直到${\left\{x^{\left(k\right)},y^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 满足停机准则：

$\{\begin{array}{l}{x}^{\left(k+1\right)}=\left(1-\omega \right)x^{\left(k\right)}+\omega {\left(\alpha P+A\right)}^{-1}\left[\left(\alpha P-A\right)x^{\left(k\right)}+2\left(y^{\left(k\right)}+b\right)\right]\\ y^{\left(k+1\right)}=\left(1-\omega \right)y^{\left(k\right)}+\omega \left|x^{(k+1)}\right|\end{array}$ 。 (7)

其中$\omega$ ，$\alpha$ 是正的常数，$P$ 是对称正定矩阵。

注1 若矩阵$A$ 是半正定的，则矩阵$\alpha P+A$ 非奇异的条件自然成立。即使矩阵$A$ 是奇异的，我们也总能找到一些足够大的参数来保证矩阵$\alpha P+A$ 是非奇异的。因此，SOR-like-PSS方法比SOR-like方法具有更广泛的应用范围。

在本节剩余部分，假设AVE(1)存在唯一解。$\left(x*,y*\right)$ 是(6)的解对，而$\left(x^{\left(k+1\right)},y^{\left(k+1\right)}\right)$ 是由SOR-like-PSS迭代(7)生成的序列。迭代误差定义为：

$e_k^x=x*-x^{\left(k\right)}$ ，$e_k^y=y*-y^{\left(k\right)}$ 。

通过估计上述两个迭代误差，可以得到相应的收敛定理。

定理1 设$\alpha$ 是一个正的常数，使得$\alpha P+A\in {ℝ}^{n\times n}$ 是非奇异的。记

$a=\left|1-\omega \right|$ ，$c=\omega {\Vert {\left(\alpha P+A\right)}^{-1}\left(\alpha P-A\right)\Vert }_2$ ，$d=2\omega {\Vert {\left(\alpha P+A\right)}^{-1}\Vert }_2$ ，

以及

$E^{\left(k\right)}=\left(\begin{array}{l}{e}_k^x\\ e_k^y\end{array}\right)$ 。

则我们有

${\Vert E^{\left(k+1\right)}\Vert }_{\infty }\le {\Vert T\left(\alpha ,\omega \right)\Vert }_{\infty }\cdot {\Vert E^{\left(k\right)}\Vert }_{\infty }$ 。 (8)

其中，

$T\left(\alpha ,\omega \right):=\left(\begin{array}{cc}a+c& d\\ \omega \left(a+c\right)& \omega d+a\end{array}\right)$ 。

此外，当参数$\alpha$ 和$\omega$ 满足

$a+c+d<1$ ，$0<\omega <\frac{2}{1+a+c+d}$ ， (9)

则对于任何初始向量，由SOR-like-PSS迭代生成的迭代序列${\left\{x^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 收敛于AVE(1)的唯一解$x*$ 。

证明：由(6)、(7)式，得

$e_{k+1}^x=\left(1-\omega \right)e_k^x+\omega {\left(\alpha P+A\right)}^{-1}\left[\left(\alpha P-A\right)e_k^x+2e_k^y\right]$ ， (10)

$e_{k+1}^y=\left(1-\omega \right)e_k^y+\omega \left(\left|x*\right|-\left|x^{(k+1)}\right|\right)$ ， (11)

由(10)式，我们能够得到

${\Vert e_{k+1}^x\Vert }_2\le \left(a+c\right){\Vert e_k^x\Vert }_2+d{\Vert e_k^y\Vert }_2$ 。 (12)

由(11)式和引理1，有

$\begin{array}{cc}{\Vert e_{k+1}^y\Vert }_2& \le \left|1-\omega \right|{\Vert e_k^y\Vert }_2+\omega {\Vert \left|x*\right|-\left|x^{(k+1)}\right|\Vert }_2\\ & \le \left|1-\omega \right|{\Vert e_k^y\Vert }_2+\omega {\Vert x*-x^{(k+1)}\Vert }_2\\ & =a{\Vert e_k^y\Vert }_{{}_2}+\omega {\Vert e_{k+1}^x\Vert }_2\end{array}$ ， (13)

重新排列(12)式和(13)式，有

$\left(\begin{array}{cc}1& 0\\ -\omega & 1\end{array}\right)\left(\begin{array}{c}{\Vert e_{k+1}^x\Vert }_2\\ {\Vert e_{k+1}^y\Vert }_2\end{array}\right)\le \left(\begin{array}{cc}a+c& d\\ 0& a\end{array}\right)\left(\begin{array}{c}{\Vert e_k^x\Vert }_2\\ {\Vert e_k^y\Vert }_2\end{array}\right)$ 。 (14)

设

$G=\left(\begin{array}{cc}1& 0\\ \omega & 1\end{array}\right)\ge 0$ 。

(14)式左乘非负矩阵$G$ ，根据引理1，我们有

$\left(\begin{array}{c}{\Vert e_{k+1}^x\Vert }_2\\ {\Vert e_{k+1}^y\Vert }_2\end{array}\right)\le \left(\begin{array}{cc}a+c& d\\ \omega \left(a+c\right)& \omega d+a\end{array}\right)\left(\begin{array}{c}{\Vert e_k^x\Vert }_2\\ {\Vert e_k^y\Vert }_2\end{array}\right)$ ， (15)

它可以被重写为

$E^{\left(k+1\right)}\le T\left(\alpha ,\omega \right)\cdot E^{\left(k\right)}$ 。 (16)

取不等式(16)两边的$\infty$ -范数并根据引理1的(2)，则(8)式得证。

由于

${\Vert T\left(\alpha ,\omega \right)\Vert }_{\infty }=\max \left\{a+c+d,\omega \left(a+c+d\right)+a\right\}$ ，

我们有

$\begin{array}{l}\begin{array}{cc}{\Vert T\left(\alpha ,\omega \right)\Vert }_{\infty }<1\iff \{\begin{array}{l}a+c+d<1\\ \omega \left(a+c+d\right)+a<1\end{array}& \iff \{\begin{array}{l}a+c+d<1\\ \left|1-\omega \right|<1-\omega \left(a+c+d\right)\end{array}\end{array}\\ \begin{array}{cc}\iff \{\begin{array}{l}a+c+d<1\\ 1-\omega \left(a+c+d\right)>0\\ \omega \left(a+c+d\right)-1<1-\omega <1-\omega \left(a+c+d\right)\end{array}& \iff \{\begin{array}{l}a+c+d<1\\ \omega <\frac{1}{a+c+d}\\ 0<\omega <\frac{2}{1+a+c+d}\end{array}\end{array}\end{array}$

$\begin{array}{cc}\iff \{\begin{array}{l}a+c+d<1\\ 0<\omega <\frac{2}{1+a+c+d}\end{array}& \end{array}$ 。

由(16)式，我们推断

$0\le {\Vert E^{\left(k\right)}\Vert }_{\infty }\le {\Vert T\left(\alpha ,\omega \right)\Vert }_{\infty }\cdot {\Vert E^{\left(k-1\right)}\Vert }_{\infty }\le \cdots \le {\Vert T\left(\alpha ,\omega \right)\Vert }_{\infty }^k\cdot {\Vert E^{\left(0\right)}\Vert }_{\infty }$ 。

因此，如果满足条件(9)，则我们有$\underset{k\to \infty }{\lim }{\Vert E^{\left(k\right)}\Vert }_{\infty }=0$ 。

由于

${\Vert E^{\left(k\right)}\Vert }_{\infty }=\max \left\{{\Vert e_k^x\Vert }_{\infty },{\Vert e_k^y\Vert }_{\infty }\right\}$ ，

它遵循

$\underset{k\to \infty }{\lim }{\Vert e_k^x\Vert }_{\infty }=0$ ，$\underset{k\to \infty }{\lim }{\Vert e_k^y\Vert }_{\infty }=0$ ，

这意味着迭代序列${\left\{x^{\left(k\right)},y^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 在条件(9)下收敛于$\left(x*,y*\right)$ 。这就证明了定理。

通过一个新的加权范数，使用不同的误差估计，我们可以得到另一个收敛定理如下。

定理2 假设定理1的条件满足，$a,c,d$ 的定义同定理1一致，记

${\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }:=\sqrt{{\Vert e_k^x\Vert }_2^2+{\omega }^{-2}{\Vert e_k^y\Vert }_2^2}.$

则有下面不等式成立：

${\Vert \left|\left(e_{k+1}^x,e_{k+1}^y\right)\right|\Vert }_{\omega }\le {\Vert M\left(\alpha ,\omega \right)\Vert }_2\cdot {\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }.$ (17)

其中，

$M\left(\alpha ,\omega \right):=\left(\begin{array}{cc}a+c& \omega d\\ a+c& \omega d+a\end{array}\right)$ 。

此外，${\Vert M\left(\alpha ,\omega \right)\Vert }_2<1$ 当且仅当参数$\alpha$ 和$\omega$ 满足

$a\left(a+c\right)<1$ ，$2{\left(a+c\right)}^2+{\omega }^2{d}^2+{\left(\omega d+a\right)}^2-a^2{\left(a+c\right)}^2-1<0$ ， (18)

也就是说，如果条件(18)成立，则对于任何初始向量，由SOR-like-PSS迭代生成的迭代序列${\left\{x^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 收敛于AVE(1)的唯一解$x*$ 。

证明：设

$Q=\left(\begin{array}{cc}1& 0\\ 0& {\omega }^{-1}\end{array}\right)$ ，

易知$Q\ge 0$ 。

(15)式左乘非负矩阵$Q$ ，根据引理1，我们有

$\left(\begin{array}{c}{\Vert e_{k+1}^x\Vert }_2\\ {\omega }^{-1}{\Vert e_{k+1}^y\Vert }_2\end{array}\right)\le \left(\begin{array}{cc}a+c& \omega d\\ a+c& \omega d+a\end{array}\right)\left(\begin{array}{c}{\Vert e_k^x\Vert }_2\\ {\omega }^{-1}{\Vert e_k^y\Vert }_2\end{array}\right)$ ， (19)

取不等式(19)两边的2范数并根据引理1的(2)，得到

${\Vert \left|\left(e_{k+1}^x,e_{k+1}^y\right)\right|\Vert }_{\omega }\le {\Vert M\left(\alpha ,\omega \right)\Vert }_2\cdot {\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }$ 。

下证${\Vert M\left(\alpha ,\omega \right)\Vert }_2<1$ 。

设$\lambda$ 是$H\left(\alpha ,\omega \right):=M{\left(\alpha ,\omega \right)}^{{\rm T}}M\left(\alpha ,\omega \right)$ 的特征值，由于

$H\left(\alpha ,\omega \right)=\left(\begin{array}{cc}2{\left(a+c\right)}^2& \left(a+c\right)\left(a+2\omega d\right)\\ \left(a+c\right)\left(a+2\omega d\right)& {\omega }^2{d}^2+{\left(\omega d+a\right)}^2\end{array}\right)$ ，

我们有

$\text{tr}\left(H\left(\alpha ,\omega \right)\right)=2{\left(a+c\right)}^2+{\omega }^2{d}^2+{\left(\omega d+a\right)}^2$ ，

$\det \left(H\left(\alpha ,\omega \right)\right)=a^2{\left(a+c\right)}^2$ 。

因此，$\lambda$ 是以下实二次方程的根

${\lambda }^2-\left(2{\left(a+c\right)}^2+{\omega }^2{d}^2+{\left(\omega d+a\right)}^2\right)\lambda +a^2{\left(a+c\right)}^2=0$ 。

根据引理3可以得出，${\Vert M\left(\alpha ,\omega \right)\Vert }_2<1$ 当且仅当

$a\left(a+c\right)<1$ ，$2{\left(a+c\right)}^2+{\omega }^2{d}^2+{\left(\omega d+a\right)}^2-a^2{\left(a+c\right)}^2-1<0$ 。

由(17)式，我们得到

$0\le {\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }\le {\Vert M\left(\alpha ,\omega \right)\Vert }_2\cdot {\Vert \left|\left(e_{k-1}^x,e_{k-1}^y\right)\right|\Vert }_{\omega }\le \cdots \le {\Vert M\left(\alpha ,\omega \right)\Vert }_{\infty }^k\cdot {\Vert \left|\left(e_0^x,e_0^y\right)\right|\Vert }_{\omega }$

因此，当满足条件(18)时，我们有$\underset{k\to \infty }{\lim }{\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }=0$ 。

根据定义

${\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }:=\sqrt{{\Vert e_k^x\Vert }_2^2+{\omega }^{-2}{\Vert e_k^y\Vert }_2^2}$ ，

我们有

$\underset{k\to \infty }{\lim }{\Vert e_k^x\Vert }_2=0$ ，$\underset{k\to \infty }{\lim }{\Vert e_k^y\Vert }_2=0$ ，

这意味着迭代序列${\left\{x^{\left(k\right)},y^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 在条件(18)下收敛于$\left(x*,y*\right)$ 。这就证明了定理。

定理2表明，为了获得SOR-like-PSS方法的收敛性，我们需要找到其中${\Vert M\left(\alpha ,\omega \right)\Vert }_2<1$ 成立的条件。这里，我们给出了比定理2中更简单的收敛条件。

推论1 设定理1的条件满足，$a,c,d$ 的定义同定理1，$M\left(\alpha ,\omega \right)$ 和${\Vert \left|\left(e_k^x,e_k^y\right)\right|\Vert }_{\omega }$ 如定理2所定义。若

$c<\frac{\sqrt{17}-3}{4}$ ，$d<\frac{\sqrt{17}-1}{8}$ ， (20)

$\frac{7-\sqrt{17}}{4}<\omega <\min \left\{\frac{\sqrt{17}-3}{4d},\frac{\sqrt{17}+1}{4}\right\}$ ， (21)

则${\Vert M\left(\alpha ,\omega \right)\Vert }_2<1$ ，即也就是说，当条件(20)~(21)成立时，SOR-like-PSS方法是收敛的。

证明：设$\eta =\max \left\{a,c,\omega d\right\}$ ，我们有

$0\le M\left(\alpha ,\omega \right)=\left(\begin{array}{cc}a+c& \omega d\\ a+c& \omega d+a\end{array}\right)\le \left(\begin{array}{cc}2\eta & \eta \\ 2\eta & 2\eta \end{array}\right)=\eta \left(\begin{array}{cc}2& 1\\ 2& 2\end{array}\right):=\eta K$ ，

其中

$K=\left(\begin{array}{cc}2& 1\\ 2& 2\end{array}\right)$ 。

根据引理2，可以得到

${\Vert M\left(\alpha ,\omega \right)\Vert }_2\le {\Vert \eta K\Vert }_2=\eta {\Vert K\Vert }_2=\eta \cdot \frac{3+\sqrt{17}}{2}$ 。

设$\theta =\frac{\sqrt{17}-3}{4}$ 。因此，如果$\eta <\theta$ ，则我们有${\Vert M\left(\alpha ,\omega \right)\Vert }_2<1$ 。然后，

$\begin{array}{ccc}\eta <\theta & \iff \{\begin{array}{l}a=\left|1-\omega \right|<\theta \\ c<\theta \\ \omega d<\theta \end{array}& \iff \{\begin{array}{l}1-\theta <\omega <1+\theta \\ c<\theta \\ \omega <\frac{\theta }{d}\end{array}\\ & \iff \{\begin{array}{l}c<\theta \\ 1-\theta <\omega <\min \left\{\frac{\theta }{d},1+\theta \right\}\\ 1-\theta <\frac{\theta }{d}\end{array}& \\ & \iff \{\begin{array}{l}c<\frac{\sqrt{17}-3}{4}\\ \frac{7-\sqrt{17}}{4}<\omega <\min \left\{\frac{\sqrt{17}-3}{4d},\frac{\sqrt{17}+1}{4}\right\}\\ d<\frac{\theta }{1-\theta }=\frac{\sqrt{17}-1}{8}\end{array}& \end{array}$ 。

因此，如果满足条件(20)~(21)，则迭代序列${\left\{x^{\left(k\right)},y^{\left(k\right)}\right\}}_{k=0}^{+\infty }$ 收敛于$\left(x*,y*\right)$ 。

4. 数值实验

本节通过两个算例验证SOR-like-PSS法的有效性和可行性。我们将SOR-like-PSS法与SOR-like法[17]以及FPI-SS法[20]从迭代步数(表示为“IT”)、以秒为单位的CPU耗时(表示为“CPU”)和绝对残差(表示为“RES”)等方面进行比较，绝对残差定义为

$\text{RES}\left(x^{\left(k\right)}\right):={\Vert A{x}^{\left(k\right)}-\left|x\right|-b\Vert }_2$ 。

在下面所有实验中，我们选择$P=I+H$ ，其中$H=\frac{A+A^{{\rm T}}}{2}$ ，所有初始向量$x^{\left(0\right)}$ 和$y^{\left(0\right)}$ 都选择为零向量，当$\text{RES}\le {\text{10}}^{-6}$ 或最大迭代步数$k_{\max }$ 超过500时，所有的迭代都将终止。所有计算均在一台配备3.60 GHz中央处理(Intel(R) Core(TM) i7-7700 CPU @ 3.6 0GHz)和8GB内存的个人计算机上使用MATLABR2017 a上实现。

算例1 [5] 设绝对值方程(1)的系数矩阵$A\in {ℝ}^{n\times n}$ ，定义$A=\widehat{A}+\mu I\in {ℝ}^{n\times n}$ ，其中

$\widehat{A}=\text{Tridiag}\left(-I,S,-I\right)=\left[\begin{array}{cccccc}S& -I& 0& \cdots & 0& 0\\ -I& S& -I& \cdots & 0& 0\\ 0& -I& S& \cdots & 0& 0\\ ⋮& ⋮& & \ddots & ⋮& ⋮\\ 0& 0& \cdots & \cdots & S& -I\\ 0& 0& \cdots & \cdots & -I& S\end{array}\right]\in {ℝ}^{n\times n}$

是一个块三角矩阵，

$S=\text{tridiag}\left(-1,4,-1\right)=\left[\begin{array}{cccccc}4& -1& 0& \cdots & 0& 0\\ -1& 4& -1& \cdots & 0& 0\\ 0& -1& 4& \cdots & 0& 0\\ ⋮& ⋮& & \ddots & ⋮& ⋮\\ 0& 0& \cdots & \cdots & 4& -1\\ 0& 0& \cdots & \cdots & -1& 4\end{array}\right]\in {ℝ}^{m\times m}$

是一个三角矩阵，$n=m^2$ 。设$x\ast ={\left(-0.5,-1,-0.5,-1,\cdots ,-0.5,-1\right)}^{{\rm T}}\in {ℝ}^n$ 是绝对值方程(1)的精确解。

算例1在$\mu =1$ ，$\mu =4$ 时的最优实验参数、IT、CPU和RES列于表1，表2。

Table 1. Numerical results of Example 1 with $\mu =1$

表1. 算例1在$\mu =1$ 时的数值结果

Method	n	50^2	100^2	150^2	200^2
SOR-like	${\omega }_{opt}$	0.82	0.82	0.82	0.82
	IT	11	12	12	12
	CPU	0.0211	0.2080	0.6257	1.1916
	RES	9.0602e-07	3.6667e-07	4.7014e-07	5.6475e-07
FPI-SS	${\omega }_{opt}$	0.90	0.90	0.90	0.90
	${\alpha }_{opt}$	5.51	5.51	5.51	5.51
	IT	14	14	14	14
	CPU	0.0326	0.1982	0.5184	0.9921
	RES	4.8485e-07	6.8766e-07	8.4315e-07	9.7425e-07
SOR-like-PSS迭代法	${\omega }_{opt}$	0.99	0.99	0.99	0.99
	${\alpha }_{opt}$	1.29	1.29	1.29	1.29
	IT	7	7	7	7
	CPU	0.0217	0.1961	0.3962	0.7304
	RES	2.8643e-07	4.5397e-07	6.0753e-07	7.5567e-07

Table 2. Numerical results of Example 1 with $\mu =4$

表2. 算例1在$\mu =4$ 时的数值结果

Method	n	50^2	100^2	150^2	200^2
SOR-like	${\omega }_{opt}$	0.92	0.92	0.92	0.92
	IT	8	9	9	9
	CPU	0.0164	0.1883	0.7615	1.0446
	RES	5.5132e-07	7.3638e-08	1.1178e-07	1.4993e-07
FPI-SS	${\omega }_{opt}$	0.94	0.94	0.92	0.94
	${\alpha }_{opt}$	8.88	8.84	8.78	8.80
	IT	10	10	11	11
	CPU	0.0185	0.1244	0.3368	0.6825
	RES	7.7974e-07	9.8700e-07	9.5461e-07	6.7937e-07
SOR-like-PSS迭代法	${\omega }_{opt}$	0.99	0.99	0.99	0.99
	${\alpha }_{opt}$	1.07	1.07	1.07	1.07
	IT	6	6	6	6
	CPU	0.0246	0.1528	0.3511	0.7446
	RES	2.1027e-07	3.4315e-07	4.7011e-07	5.9496e-07

算例2 [5] 设绝对值方程(1)的系数矩阵$A\in {ℝ}^{n\times n}$ ，定义$A=\widehat{A}+\mu I\in {ℝ}^{n\times n}$ ，其中

$\widehat{A}=\text{Tridiag}\left(-1.5I,S,-0.5I\right)=\left[\begin{array}{cccccc}S& -0.5I& 0& \cdots & 0& 0\\ -1.5I& S& -0.5I& \cdots & 0& 0\\ 0& -1.5I& S& \cdots & 0& 0\\ ⋮& ⋮& & \ddots & ⋮& ⋮\\ 0& 0& \cdots & \cdots & S& -0.5I\\ 0& 0& \cdots & \cdots & -1.5I& S\end{array}\right]\in {ℝ}^{n\times n}$

是一个块三角矩阵，

$S=\text{tridiag}\left(-1.5,4,-0.5\right)=\left[\begin{array}{cccccc}4& -0.5& 0& \cdots & 0& 0\\ -1.5& 4& -0.5& \cdots & 0& 0\\ 0& -1.5& 4& \cdots & 0& 0\\ ⋮& ⋮& & \ddots & ⋮& ⋮\\ 0& 0& \cdots & \cdots & 4& -0.5\\ 0& 0& \cdots & \cdots & -1.5& 4\end{array}\right]\in {ℝ}^{m\times m}$

是一个三角矩阵，$n=m^2$ 。设$x\ast ={\left(-0.5,-1,-0.5,-1,\dots ,-0.5,-1\right)}^{{\rm T}}\in {ℝ}^n$ 是绝对值方程(1)的精确解。

算例2在$\mu =1,\mu =4$ 时的最优实验参数、IT、CPU和RES列于表3，表4。

Table 3. Numerical results of Example 2 with $\mu =1$

表3. 算例2在$\mu =1$ 时的数值结果

Method	n	50^2	100^2	150^2	200^2
SOR-like	${\omega }_{opt}$	0.79	0.79	0.79	0.79
	IT	15	15	15	15
	CPU	0.3892	1.5757	3.1612	6.7889
	RES	4.2355e-07	5.7706e-07	6.9771e-07	8.0051e-07
FPI-SS	${\omega }_{opt}$	0.90	0.91	0.91	0.88
	${\alpha }_{opt}$	5.34	5.40	5.38	5.26
	IT	15	15	15	16
	CPU	0.1524	0.5283	1.6408	3.0823
	RES	5.8616e-07	8.3084e-07	9.9359e-07	9.2265e-07
SOR-like-PSS迭代法	${\omega }_{opt}$	0.99	0.99	0.99	0.99
	${\alpha }_{opt}$	1.29	1.29	1.29	1.29
	IT	7	7	7	7
	CPU	0.0296	0.3821	0.8144	1.2769
	RES	2.8643e-07	4.5397e-07	6.0753e-07	7.5567e-07

Table 4. Numerical results of Example 2 with $\mu =4$

表4. 算例2在$\mu =4$ 时的数值结果

Method	n	50^2	100^2	150^2	200^2
SOR-like	${\omega }_{opt}$	0.93	0.93	0.93	0.93
	IT	8	8	8	8
	CPU	0.1478	1.1199	1.7352	3.1458
	RES	2.3886e-07	4.5917e-07	6.7920e-07	8.9916e-07
FPI-SS	${\omega }_{opt}$	0.95	0.95	0.93	0.94
	${\alpha }_{opt}$	8.62	8.67	8.50	8.09
	IT	11	11	11	12
	CPU	0.0922	0.7353	2.9834	2.1956
	RES	4.6536e-07	6.8277e-07	9.0588e-07	9.7296e-07
SOR-like-PSS迭代法	${\omega }_{opt}$	0.99	0.99	0.99	0.99
	${\alpha }_{opt}$	1.06	1.06	1.06	1.06
	IT	7	8	8	8
	CPU	0.0619	0.4147	0.9071	1.4777
	RES	9.3860e-07	1.1337e-07	1.3198e-07	1.4828e-07

我们发现，SOR-like-PSS迭代法收敛到精确解的迭代步数以及耗时都比SOR-like法以及FPI-SS法更优。

5. 参数选择

本文提出的SOR-like-PSS方法包含两个关键参数：松弛参数$\omega \in \left(0,2\right)$ 和正则化参数$\alpha >0$ 。这两个参数对算法的收敛速度有显著影响。然而，目前尚无有效的理论准则用于确定其最优值。因此我们通过数值实验的方式，在不同问题规模和矩阵类型下测试了参数组合(α, ω)对迭代次数的影响。实验结果表明，在多数测试问题中，当$\omega \in \left[0.8,1.2\right]$ 且$\alpha \in \left[1,2\right]$ 时，算法收敛最快且稳定性良好。

下面，我们以算例1中$\mu =1$ 的情形为例，进行参数敏感性分析。如图1所示，在固定参数$\alpha =1.3$ 的情况下，SOR-like-PSS方法的迭代次数对参数$\omega$ 表现出显著的敏感性。当$\omega$ 从0增加到约0.8时，迭代步数迅速下降，表明算法收敛速度加快；而在区间$\left[0.8,1.2\right]$ 内，迭代步数达到最低点并保持稳定，说明此时算法具有最优的收敛性能和较高的计算效率。当$\omega >1.2$ 时，迭代步数急剧上升并趋于最大值500次，显示算法在此区间内收敛性能显著下降甚至不收敛。因此，区间$\left[0.8,1.2\right]$ 是选择$\omega$ 的理想范围。

图2展示了固定参数$\omega =0.99$ 时，SOR-like-PSS方法在不同问题规模(n = 2500, 10000, 22500, 40000)下的迭代次数随参数$\alpha$ 变化的整体趋势。当$\alpha <0.5$ 时，所有曲线均维持在最大迭代步数500次(即未收敛)，表明算法在此区间内无法有效收敛；随着$\alpha$ 增大，迭代次数显著下降，并在区间$\left[1,2\right]$ 内趋于稳定，显示出良好的收敛性能和鲁棒性；当$\alpha >2$ 时，迭代步数有所上升，但仍保持在相对较低的水平，未出现急剧增长，这说明算法在该区域仍具备一定的稳定性，但性能不如$\alpha \in \left[1,2\right]$ 时理想。结合图3的精细扫描结果可知，当$\alpha \in \left[1.2,1.4\right]$ 时，迭代步数达到最小，因此该区间为$\alpha$ 的最优选择范围。

Figure 1. IT vs. relaxation parameter $\omega$ for different problem sizes with fixed $\alpha =1.3$

图1. $\alpha =1.3$ ，不同问题规模下迭代步数随松弛参数$\omega$ 的变化

Figure 2. IT vs. regularization parameter $\alpha$ for different problem sizes with fixed $\omega =0.99$

图2. $\omega =0.99$ ，不同问题规模下迭代步数随正则参数$\alpha$ 的变化

Figure 3. Local changes in IT vs. $\alpha$ for different problem sizes with fixed $\omega =0.99$

图3. $\omega =0.99$ ，不同问题规模下迭代步数随正则参数$\alpha$ 的局部变化

6. 结论

本文将系数矩阵的预条件移位分裂与SOR-like迭代法相结合，提出了求解绝对值方程(AVE)的SOR-like-PSS迭代法，并且给出了SOR-like-PSS迭代法的收敛条件。此外，通过两个线性互补问题的数值算例，我们证明了SOR-like-PSS迭代法在迭代步数和计算时间方面均优于SOR-like迭代法。但是，在理论上如何选择最佳的SOR-like-PSS迭代法中所涉及的参数需要进一步的研究。