考虑如下绝对值方程 (AVE) 的求解问题^[1,2]

其中 $A \in \mathbb{R}^{n\times n}, b \in \mathbb{R}^{n}$, $|x|=(|x_1|,|x_2|,\cdots,|x_n|)^{\rm T}$. AVE 问题 (1.1) 是如下广义绝对值方程 (GAVE) 的特殊情形^[3,4]

其中 $B \in \mathbb{R}^{n\times n}$. GAVE 问题 (1.2) 在各种科学与工程计算领域都有着重要的应用, 如线性规划问题、凸二次规划问题、线性互补问题等,见文献[5,6]及其参考文献.

受文献[7]的启发, 利用牛顿型单步迭代法作为预测步, 提出了一种两步迭代法, 即积分-牛顿型迭代法. 同时, 充分利用更新规则, 提出了改进的积分-牛顿迭代法.

我们先引述下面两个引理.

引理1.1^[8] 对角矩阵的奇异值等于对角线元素的绝对值.

引理1.2^[8] 当且仅当矩阵 $A^TA$ 的最小特征值超过 $B^TB$ 的最大特征值时, 矩阵 $A\in\mathbb{R}^{n \times n}$ 的所有奇异值都超过 $B\in\mathbb{R}^{n \times n}$ 的最大奇异值.

首先, 将 GAVE (1.2) 转化为非线性函数

函数 $g(x)$ 的广义 Jacobi 矩阵是

其中 $D(x)={\rm diag(sign}(x))$ 是一个满足为 $D(x)x=|x|$ 的对角矩阵. 假设 $\xi$ 是 (1.2) 式的精确解. 利用牛顿-莱布尼兹积分公式, 可以得到

在数值分析中, 著名的 Gauss-Legendre 积分 (GL) 和 Newton-Cotes 积分 (NC) 方法被用于计算各种积分, 具体如下所示

其中 $\rho(t)$ 是 Legendre 函数且 $A_k$ 是正交系数.

其中 $s_k=a+kh,h=\xi-\eta$,

(2.2) 和 (2.3) 式的右侧统一定义为 $(\xi-\eta)F(\eta,\xi)$, 则有$(\xi-\eta)F(\eta,\xi)=-g(\eta),$可得$\xi=\eta-[F(\eta,\xi)]^{-1}g(\eta).$由此可以得到迭代法$\xi^{k+1}=\eta-[F(\eta,\xi^{k})]^{-1}g(\eta).$

为了使 $\xi^k$ 收敛到 GAVE (1.2) 的解, $\eta$ 应该也收敛到 GAVE (1.2) 的解. $\eta$ 由求解 GAVE (1.2) 的单步迭代法更新.

下面研究 $\eta$ 的更新法则.令 $A=M-N$ 是矩阵 $A$ 的一个分裂, 其中 $M$ 可逆, 则 GAVE (1.2) 可以被重写为$Mx-Nx-B|x|-b=0.$进一步得到广义的单步迭代法

将上述公式的更新规则应用于变量 $\eta$, 并结合 $\xi$ 的更新法则,我们提出积分-牛顿型迭代法如下

算法 2.1 (积分-牛顿型迭代法)

步骤1 取初始点 $\xi^0,\eta^0\in\mathbb{R}^n$, 最大迭代次数 $N$ 和精度要求 $\epsilon$. 置 $k:=0,1,2,\cdots$.

步骤2 计算

步骤3 若 $| \xi^{k+1} - \xi^k|<\epsilon$, 则停算.

步骤4 若 $k=N$, 则停算; 否则, 置 $\xi^{k+1}:=\xi^{k}, k:= k+1 $, 转步骤 2.

又因为 $\xi$ 和 $\eta$ 都收敛到 GAVE (1.2) 的解, 所以充分利用更新后 $\xi$ 的值, 可以得到改进的积分-牛顿型迭代法.

算法 2.2 (改进的积分-牛顿型迭代法)

步骤1 取初始点 $\xi^0\in\mathbb{R}^n$, 最大迭代次数 $N$ 和精度要求 $\epsilon$. 置 $k:=0,1,2,\cdots$.

步骤2 计算

步骤3 若 $| \xi^{k+1} - \xi^k|<\epsilon$, 则停算.

步骤4 若 $k=N$, 则停算; 否则, 置 $\xi^{k+1}:=\xi^{k}, k:= k+1 $, 转步骤 2.

接下来对算法 2.1 和算法 2.2 作一些说明和分析. Wang 在文献[9]给出了基于牛顿法的矩阵分裂迭代法的一般形式如下

其中 $M+\Omega$ 是可逆的, 并且 $\Omega$ 是一个给定的矩阵. 如果 $\Omega = 0$, 上面的分裂形式与 (2.4) 式的广义单步迭代法相同. 基于公式 (2.4) 的迭代法包括了 Picard 法、修正牛顿法等. 那么, 适当选取分裂矩阵 $M$ 和 $N$, 可得到下列各种情形的迭代法公式.

(a)当 $M=A, N=0$, 单步迭代法 (2.4) 退化为 Picard 法^[10]

(b)当 $M=A+\Omega, N=\Omega$, 单步迭代法 (2.4) 退化为改进的牛顿法^[9]

(c) 当 $M=\dfrac{1}{\omega}A, N=\dfrac{1-\omega}{\omega}A$, 单步迭代法 (2.4) 退化为松弛 Picard 法

(d) 当 $M=D+\Omega, N=\Omega+L+U$, 单步迭代法 (2.4) 退化为基于牛顿的 Jacobi 法^[11]

(e) 当 $M=D+\Omega-L, N=\Omega+U$, 单步迭代法 (2.4) 退化为基于牛顿的 Gauss-Seidel 法^[11]

(f) 当 $M=\dfrac{1}{\alpha}(D+\alpha\Omega-\alpha L), N=\dfrac{1}{\alpha}(\alpha D+(1-\alpha)D+\alpha U)$, 单步迭代法 (2.4) 退化为基于牛顿的 SOR 法^[9]

(g) 当 $M=\frac{1}{\alpha}(D+\alpha\Omega-\beta L), N=\frac{1}{\alpha}(\alpha D+(1-\alpha)D+(\alpha-\beta)L +\alpha U)$, 单步迭代法 (2.4) 退化为基于牛顿的 AOR 法^[9]

(h) 当 $M=H, N=-S$, 单步迭代法 (2.4) 退化为 HSS 法^[11]

(i) 当 $M=H+\Omega, N=\Omega-S$, 单步迭代法 (2.4) 退化为 NHSS 法^[9]

注2.1 对于不同的积分方法, $F(\eta,\xi)$ 的具体形式是不同的. 这里对函数 $F(\eta,\xi)$ 的一个简单说明.关于 Gauss-Legendre 积分, 有

关于 Newton-Cotes 积分, 有

为了保证算法 2.1 和算法 2.2 的可行性, 需要讨论 $[F(\eta,\xi)]^{-1}$ 的存在性. 这里以 Newton-Cotes 积分 ($n=1$) 为例进行分析. 由于其他情况相似, 故此省略.

定理2.1 当 $A\in\mathbb{R}^{n\times n}$ 的奇异值 $\sigma(A)>1$, 则 $[g'(\xi)+g'(\eta)]^{-1}$ 存在, 其中 $D(x)={\rm diag}({\rm sign}(x))$.

证 根据 (2.1) 式, 有

假设 $g'(\xi)+g'(\eta)$ 是奇异的, 则 $(g'(\xi)+g'(\eta))u=0$ 对于某个向量 $u\neq0$. 记 $\dfrac{1}{2}(D(\xi)+D(\eta))=\widetilde{D}$. 根据引理 1.1, $\sigma(\widetilde{D})$ 不超过 1. 因为 $\sigma(A)>1$ 和引理 1.2 ($\lambda_{\min}(A^TA)>\lambda_{\max}$$(D^TB^TBD)$), 通过简单计算可以得到

这是矛盾的, 因此 $g'(\xi)+g'(\eta)$ 是非奇异的.

本节讨论算法 2.1 和算法 2.2 的收敛性. 考虑 GAVE 问题 (1.2) 和分裂式 $A=M-N$, 记 $\mu:=\|F(\eta^{k+1},\xi^k)^{-1}\|$.

定理3.1 如果 $\|M^{-1}\|(\|N\|+\|B\|)<1$ 且

则算法 2.1 是收敛的.

证 令 $x^*$ 是 GAVE (1.2) 的解, 则 $x^*=M^{-1}(Nx^*+B|x^*|+b)$. 根据 (2.5) 式的第一个公式, 有

对上式两边同时取范数, 结合范数性质, 可以得到

根据 (2.5) 式的第二个公式, 有

结合范数性质和简单计算, 相似地, 可以得到

因此, 定理的已知条件及 (3.2) 式立知算法 2.1 是收敛的.

定理3.2 如果$\mu(\|F(\eta^{k+1},\xi^k)-A\|+\|B\|)\|M^{-1}\|(\|N\|+\|B\|)<1$,则算法 $2.2$ 是收敛的.

证 令 $x^*$ 是 GAVE (1.2) 的解, 则 $x^*=M^{-1}(Nx^*+B|x^*|+b)$. 根据 (2.6) 式的第一个公式, 有

结合 (3.2) 式, 有

易见, 若 $\mu(\|F(\eta^{k+1},\xi^k)-A\|+\|B\|)\|M^{-1}\|(\|N\|+\|B\|)<1$,则算法 $2.2$ 是收敛的.

下面以 NC $(n=1)$ 为例, 详细讨论定理 3.1 和定理 3.2. 由于其他积分情形的讨论相似, 故此省略

其中 $\dfrac{1}{2}(D(\xi)+D(\eta))=\widetilde{D}$. 对上式两边同时取范数, 得

最后一个不等号成立是因为 $\|\widetilde{D}\|\le1$. 于是, 我们有下面的推论.

推论3.1 如果 $\|M^{-1}\|\le\dfrac{1-\|A^{-1}\|\|B\|}{2\|A^{-1}\|\|B\|(\|N\|+\|B\|)}$, 则算法 $2.1$ 和算法 $2.2$ 是收敛的.

证 首先, 讨论 $\|F(\eta^{k+1},\xi^k)-A\|+\|B\|$ 的情况.

将 (3.5) 式结合 (3.6) 式, 有

为了算法 $2.1$ 和算法 $2.2$ 收敛, 需要保证上述不等式的右端小于 1. 通过简单计算, 可得

故定理的结论成立.

在本节, 通过两个数值实验的迭代步数、CPU 时间和残差 RES 来说明算法 $2.1$ 和算法 $2.2$ 的可行性和有效性. 在实验中, 所有的初始向量 $\eta^{(0)}$ 和 $\xi^{(0)}$ 均取为零向量.

例 4.1 考虑 GAVE (1.2), 其中 $b=Ax^*-B|x^*|$ 且

$x^*=(-1,1,-1,1,\cdots,-1,1)^T\in \mathbb{R}^n$ 是 GAVE (1.2) 的解.

在实验中, MN 法、RP 法、NJ 法、NGS 法和 NHSS 法的参数 $\omega$ 分别为 $0.8$, NSOR 法的参数分别为 $\omega=0.9$ 和 $\alpha=0.9$, NAOR 法的系数分别为 $\omega=0.9, \alpha= 0.9$ 和 $\beta=0.6$. 数值结果如表1.

从表1 可以看出, 在单步迭代法中 Picard 法和 HSS 法的迭代步数最少, 但在这些单步迭代法结合了积分牛顿型方法后, 所有方法的迭代步数都有大幅度减少且同一种积分型结合不同的单步迭代法后的结果是差异较小的. 说明这个数值实验表现出积分牛顿型迭代法对于积分方法的灵敏度不是很高, 不同的积分方法得到的结果是一致的.

下面将用另一个数值实验来证明积分牛顿型迭代法的不同性质.

例 4.2^[12] 考虑线性互补问题 LCP, 对于给定的矩阵 $M\in \mathbb{R}^{n\times n}$ 和向量 $q\in \mathbb{R}^n$, 求得满足下面条件的向量 $z,w\in\mathbb{R}^n$,

LCP (4.1) 等价于下述形式的 GAVE

令 $A=M+I, B=M-I, M=\hat{M}+\mu I\in\mathbb{R}^{n\times n}, q=-Mz^*\in \mathbb{R}^n$, 其中

则有 $n=m^2$ 且 $z^*=(1.2,1.2,1.2,\cdots,1.2)^T\in\mathbb{R}^n$ 是 LCP (4.1) 问题的唯一解, 则 GAVE (4.2) 的精确解为 $x^*=(-0.6,-0.6,-0.6,\cdots,-0.6)^T\in\mathbb{R}^n$.

在例4.2 中, 分别取 $\mu=4, \Omega=\hat{M}$ 和 $\mu=4, \Omega=1.5\times\hat{M}$ 两种情况, 将具体数值实验结果分别表示在表2 和表3 中. 从表格2 中可以看出, RP 法在 $\Omega=\hat{M}$ 的情况下是不收敛的, 因此对应的积分牛顿型迭代方法也是无法去求解的. 在单步迭代法中, NJ 法、NGS 法、NSOR 法和 NAOR 法的迭代步数相较于其他方法具有明显的优势. 积分牛顿型迭代法在结合了单步迭代法后有显著的改进, 且其中 NGS 法、NSOR 法和 NAOR 法在结合 Newton-Cotes 积分 $(n=2, n=3)$ 时的迭代步数少于其他单步迭代法的结合结果, 这个实验数值说明了该方法针对结合不同单步迭代法可以得到不同的实验结果且显著优于单步迭代法.

从表3 中可以看出与表2 中实验结果一致, 单步迭代法中, NJ 法、NGS 法、NSOR 法和 NAOR 法优于其他单步迭代法, 结合积分牛顿型迭代法后的结果也大致一样, 但区别于表2, 在表3 中取 $\Omega=1.5\times\hat{M}$, 在该情况下, 可以看到在 NGS 法区别于其他方法, 其在结合 Newton-Cotes 积分 ($n=2, n=3$) 方法时, 迭代步数是不一样的, 说明积分牛顿型迭代法在选取不同的积分方法时, 不同的 $n$ 结合不同的单步迭代法会有不同的情况, $n$ 取值越大, 迭代步数不一定会更多, 从而说明积分方法中 $n$ 的选取与迭代步数不是线性关系.

本文将 Gauss-Legendre 和 Newton-Cotes 积分方法结合现有的单步迭代法提出了积分-牛顿型迭代法求解 GAVE (1.2), 对于不同的积分方法和不同的单步迭代法, 得到了相对应的两步迭代方法, 证明了所提方法的收敛性条件, 并通过数值实验去证明了所提方法的优势, 分析了不同积分的选择对迭代情况的影响.