求解复对称线性系统的极小残差非平衡修正HSS迭代法

Minimum Residual Lopsided Modified HSS Iteration Method for a Class of Complex Symmetric Linear Systems

摘要: 结合非平衡MHSS (LMHSS)迭代法和极小残差策略，本文提出了极小残差LMHSS (MRLMHSS)迭代法，并推导了两个广义参数的计算公式以及分析了所提出方法的收敛性。数值实验验证了所提出方法的有效性和优越性。

Abstract: Combining the minimum residual technique and the lopsided MHSS (LMHSS) method, the minimum residual LMHSS (MRLMHSS) iteration method is established. The formulas for computing these two parameters are derived, and a detailed convergence analysis is presented. Numerical results demonstrate the effectiveness and superiority of the proposed methods.

1. 引言

考虑大型稀疏线性系统

$Ax=b,$ (1)

这里系数矩阵$A\in C^{n\times n}$ 为复对称矩阵，可以表示为如下形式：

$A=W+iT,$

其中，$i=\sqrt{-1}$ 表示虚数单位，$W\in R^{n\times n}$ 为对称正定矩阵，$T\in R^{n\times n}$ 为对称半正定矩阵。假设$T\ne 0$ ，这意味着$A$ 是非Hermitian矩阵。这类复对称线性系统[1]它常出现在科学计算和工程应用中的许多重要领域，应用背景非常广泛，如光的成像问题[2]，基于快速Fourier变换(FFT)的某些时变微分方程数值解[3]，波的传导[4]，格点量子色动力学[5]，结构动力学[6]，分子散射[7]，分子动力学和流体动力学[8]等，对这些实际问题的求解，最终都转化为对复对称线性系统(1)的求解。随着科学问题复杂性的增加，需要处理的复数域的问题也越来越多。因此，如何高效求解复对称线性系统(1)就显得尤为重要。

2003年Bai等提出了求解非Hermitian正定线性系统的Hermitian和反Hermitian分裂(HSS)迭代法[9]，2007年，Li等针对求解非Hermitian正定线性系统，提出了非平衡HSS (LHSS)迭代法[10]。通过理论分析和数值实验验证了LHSS迭代法的高效性。2010年，Bai等提出了求解复对称线性系统(1)的修正HSS (MHSS)迭代法[11]。2014年，Li等针对求解复对称线性系统(1)，提出了非平衡PMHSS (LPMHSS)迭代法[12]，将LPMHSS迭代法中的预处理矩阵特殊为单位矩阵时，就得到了求解复对称线性系统(1)的LMHSS迭代法，迭代方案如下：

算法1 (LMHSS迭代法). 对于给定的初始向量$x^{(0)}\in C^n$ ，$k=0,1,2,\cdots$ ，利用下述迭代格式计算$x^{\left(k+1\right)}$ 直到迭代序列${\left\{x^{(k)}\right\}}_{k=0}^{\infty }\in C^{n\times n}$ 满足停止准则：

$\{\begin{array}{c}W{x}^{\left(k+\frac{1}{2}\right)}=-iT{x}^{(k)}+b,\\ \left(\alpha I+T\right)x^{(k+1)}=\left(\alpha I+iW\right)x^{\left(k+\frac{1}{2}\right)}-ib,\end{array}$ (2)

其中，$\alpha$ 是一个给定的正常数，$I$ 是一个单位矩阵。

2019年，Yang等提出了极小残差HSS (MRHSS)迭代法[13]，通过理论分析和数值结果验证MRHSS的高效性。本文基于极小残差技术的思想，我们将极小残差技术应用LMHSS迭代方法中，提出了极小残差LMHSS (MRLMHSS)迭代法，并给出了该方法的收敛性分析，最后通过数值实验验证了所提出方法的可行性和高效性。在这项工作中，不同于现有MHSS变体的思想，我们将通过引入两个额外的控制参数来介绍一种非平稳的LMHSS迭代方案。由于新方案中涉及新的控制参数是通过最小化相应的残差范数确定的，我们称这种非平稳的LMHSS迭代方案为极小残差LMHSS (MRLMHSS)迭代法。这种加速的思想来源于用于求解鞍点问题的非平稳Uzawa方法[14]。其他类似且重要的加速技术，如最小残差平滑，可参考文献[15] [16]。除此之外，很多学者也提出了求解复对称线性系统的一些其他的迭代法和相应的变体[17]-[20]。

在本文中，我们用$\left(x,y\right)=y^{*}x$ 表示任何复向量的Euclidean内积，对任意向量$x\in C^n$ ，$\Vert x\Vert =\sqrt{\left(x,x\right)}$ 用来表示向量的2-范数，$\Vert X\Vert$ 表示矩阵$X\in R^{n\times n}$ 的2-范数，2-范数和Euclidean范数在数学和工程领域经常交换使用，所以在本文中2-范数也就等于Euclidean范数。${\Vert \left|x\right|\Vert }_A=\Vert Ax\Vert$ ，对任意矩阵$X\in C^{n\times n}$ ，${\Vert \left|X\right|\Vert }_A=\Vert AX{A}^{-1}\Vert$ ，$\rho \left(A\right)$ 表示矩阵$A$ 的谱半径，$\sigma \left(A\right)$ 表示矩阵$A$ 的谱集。

2. MRLMHSS迭代法的建立

为了提高LMHSS迭代法的效率，在迭代方案(2)中记$r^{(k)}=A{x}^{(k)}-b$ ，和$r^{\left(k+\frac{1}{2}\right)}=A{x}^{\left(k+\frac{1}{2}\right)}-b$ ，则可以将迭代方案(2)可以等价的重新写为

$\{\begin{array}{c}{x}^{\left(k+\frac{1}{2}\right)}=x^{(k)}+W^{-1}{r}^{(k)},\\ x^{(k+1)}=x^{\left(k+\frac{1}{2}\right)}-i{\left(\alpha I+T\right)}^{-1}{r}^{\left(k+\frac{1}{2}\right)},\end{array}$ (3)

迭代方案(3)在数值上优于(2)，具体细节参考文献[21]。然后，我们记

$d^{(k)}=W^{-1}{r}^{(k)},d^{\left(k+\frac{1}{2}\right)}={\left(\alpha I+T\right)}^{-1}{r}^{\left(k+\frac{1}{2}\right)},$

则将迭代方案(3)重新写为

$\{\begin{array}{c}{x}^{\left(k+\frac{1}{2}\right)}=x^{(k)}+d^{(k)},\\ x^{(k+1)}=x^{\left(k+\frac{1}{2}\right)}-i{d}^{\left(k+\frac{1}{2}\right)},\end{array}$

我们可以沿$d^{(k)}$ 和$d^{\left(k+\frac{1}{2}\right)}$ 更新方向乘以两个广义参数${\lambda }_k$ 和${\theta }_k$ ，期望它们能很好地提高收敛速度。然后，推导出了一种改进的迭代方案，如下

$\{\begin{array}{c}{x}^{\left(k+\frac{1}{2}\right)}=x^{(k)}+{\lambda }_k{d}^{(k)},\\ x^{(k+1)}=x^{\left(k+\frac{1}{2}\right)}-i{\theta }_k{d}^{\left(k+\frac{1}{2}\right)},\end{array}$ (4)

我们在下面的运算中定义了两种符号

$F_1:=A{W}^{-1},F_2:=A{\left(\alpha I+T\right)}^{-1},$

然后，迭代方案(4)的残差向量可以写成

$r^{(k)}=r^{(k)}-{\lambda }_k{F}_1{r}^{(k)},r^{(k+1)}=r^{\left(k+\frac{1}{2}\right)}+i{\theta }_k{F}_2{r}^{\left(k+\frac{1}{2}\right)},$

现在我们确定参数${\lambda }_k$ 和${\theta }_k$ 的值，在每个迭代步骤中分别极小化残差范数$\Vert r^{\left(k+\frac{1}{2}\right)}\Vert$ 和$\Vert r^{(k+1)}\Vert$ 的适当值。通过直接计算

$\begin{array}{l}{\Vert r^{\left(k+\frac{1}{2}\right)}\Vert }^2={\Vert r^{(k)}\Vert }^2-2\mathrm{Re}\left({\lambda }_k\right)\left(H\left(F_1\right)r^{(k)},r^{(k)}\right)-2\mathrm{Im}\left({\lambda }_k\right)\left(iS\left(F_1\right)r^{(k)},r^{(k)}\right)\\ +\left(\mathrm{Re}{\left({\lambda }_k\right)}^2+\mathrm{Im}{\left({\lambda }_k\right)}^2\right){\Vert F_1{r}^{(k)}\Vert }^2,\end{array}$ (5)

$\begin{array}{l}{\Vert r^{(k+1)}\Vert }^2={\Vert r^{\left(k+\frac{1}{2}\right)}\Vert }^2-2\mathrm{Im}\left({\theta }_k\right)\left(H\left(F_2\right)r^{\left(k+\frac{1}{2}\right)},r^{\left(k+\frac{1}{2}\right)}\right)+2\mathrm{Re}\left({\theta }_k\right)\left(iS\left(F_2\right)r^{\left(k+\frac{1}{2}\right)},r^{\left(k+\frac{1}{2}\right)}\right)\\ +\left(\mathrm{Re}{\left({\theta }_k\right)}^2+\mathrm{Im}{\left({\theta }_k\right)}^2\right){\Vert F_1{r}^{(k)}\Vert }^2,\end{array}$ (6)

其中$\mathrm{Re}(\cdot )$ 和$\mathrm{Im}(\cdot )$ 分别表示复数的实部和虚部，$H(\cdot )$ 和$S(\cdot )$ 分别表示矩阵的Hermitian反Hermitian部分，很容易观察到，这两个范数可以分别看作是两个变量$\mathrm{Re}\left({\lambda }_k\right)$ 和$\mathrm{Im}\left({\lambda }_k\right)$ ，$\mathrm{Re}\left({\theta }_k\right)$ 和$\mathrm{Im}\left({\theta }_k\right)$ 的两个实值凸函数。从而，每个函数的极小值点可以直接推导出

$\mathrm{Re}\left({\lambda }_k\right)=\frac{\left(H\left(F_1\right)r^{(k)},r^{(k)}\right)}{{\Vert F_1{r}^{(k)}\Vert }^2},\mathrm{Im}\left({\lambda }_k\right)=\frac{i\left(S\left(F_1\right)r^{(k)},r^{(k)}\right)}{{\Vert F_1{r}^{(k)}\Vert }^2},$ (7)

和

$\mathrm{Re}\left({\theta }_k\right)=-\frac{i\left(S\left(F_2\right)r^{\left(k+\frac{1}{2}\right)},r^{\left(k+\frac{1}{2}\right)}\right)}{{\Vert F_2{r}^{\left(k+\frac{1}{2}\right)}\Vert }^2},\mathrm{Im}\left({\theta }_k\right)=\frac{\left(H\left(F_2\right)r^{\left(k+\frac{1}{2}\right)},r^{\left(k+\frac{1}{2}\right)}\right)}{{\Vert F_2{r}^{\left(k+\frac{1}{2}\right)}\Vert }^2}.$ (8)

然后，我们可以得到

${\lambda }_k=\mathrm{Re}\left({\lambda }_k\right)+i\mathrm{Im}\left({\lambda }_k\right)=\frac{\left(r^{(k)},F_1{r}^{(k)}\right)}{{\Vert F_1{r}^{(k)}\Vert }^2},$ (9)

${\theta }_k=\mathrm{Re}\left({\theta }_k\right)+i\mathrm{Im}\left({\theta }_k\right)=\frac{i\left(r^{\left(k+\frac{1}{2}\right)},F_2{r}^{\left(k+\frac{1}{2}\right)}\right)}{{\Vert F_2{r}^{\left(k+\frac{1}{2}\right)}\Vert }^2},$ (10)

具体的细节计算类似于文献[22]，则它们可以重新写为

${\lambda }_k=\frac{\left(r^{(k)},A{d}^{(k)}\right)}{{\Vert A{d}^{(k)}\Vert }^2},{\theta }_k=\frac{i\left(r^{\left(k+\frac{1}{2}\right)},A{r}^{\left(k+\frac{1}{2}\right)}\right)}{{\Vert A{r}^{\left(k+\frac{1}{2}\right)}\Vert }^2},$

综上，可以得到MRLMHSS迭代法，迭代方案如下：

算法2 (MRLMHSS迭代法). 对于给定的初始向量$x^{(0)}\in C^n$ ，$k=0,1,2,\cdots$ ，利用下述迭代格式计算$x^{\left(k+1\right)}$ 直到迭代序列${\left\{x^{(k)}\right\}}_{k=0}^{\infty }\in C^{n\times n}$ 满足停止准则：

$\{\begin{array}{c}{x}^{\left(k+\frac{1}{2}\right)}=x^{(k)}+{\lambda }_k{d}^{(k)},\\ x^{(k+1)}=x^{\left(k+\frac{1}{2}\right)}-i{\theta }_k{d}^{\left(k+\frac{1}{2}\right)},\end{array}$ (11)

其中，

$d^{(k)}=W^{-1}{r}^{(k)},{\lambda }_k=\frac{\left(r^{(k)},A{d}^{(k)}\right)}{{\Vert A{d}^{(k)}\Vert }^2};$

$d^{\left(k+\frac{1}{2}\right)}={\left(\alpha I+T\right)}^{-1}{r}^{\left(k+\frac{1}{2}\right)},{\theta }_k=\frac{i\left(r^{\left(k+\frac{1}{2}\right)},A{r}^{\left(k+\frac{1}{2}\right)}\right)}{{\Vert A{r}^{\left(k+\frac{1}{2}\right)}\Vert }^2};$

$\alpha$ 是一个给定的正常数，$I$ 是一个单位矩阵。

附注1. 当我们在算法2的每一步选择${\lambda }_k={\theta }_k=1$ 时，MRLMHSS迭代法立即简化为LMHSS迭代法。

附注2. MRLMHSS迭代方法也适用于矩阵$W$ 为对称半正定的，$T$ 为对称正定的情况。更普遍地说，如果存在实数$\beta$ 和$\delta$ 使得两个矩阵$\overline{W}:=\beta W+\delta T$ 和$\overline{T}:=\delta T-\beta W$ 都是对称半正定的，其中至少有一个是正定的，我们可以首先将复对称系统(1)乘以复数$\beta -i\delta$ 得到等效系统

$\left(\overline{W}+i\overline{T}\right)x=\overline{b}$ ,

其中，$\overline{b}:=\left(\beta -i\delta \right)b$ ，然后采用MRLMHSS迭代方法近似求解上述线性系统。

3. 收敛性分析

引理1. 由(7)和(8)确定的数组$\left(\mathrm{Re}\left({\lambda }_k\right),\mathrm{Im}\left({\lambda }_k\right),\mathrm{Re}\left({\theta }_k\right),\mathrm{Im}\left({\theta }_k\right)\right)$ 是函数$\Vert r^{(k+1)}\Vert$ 的最小值点，这意味着由(9)和(10)确定的${\lambda }_k$ 和${\theta }_k$ 在复数域$C$ 中是最优的。

以上引理的证明类似于文献[22]定理1的证明。

接下来，我们研究了MRLMHSS迭代方法的收敛性，用$\Re \left(M\right)$ 表示复矩阵$M\in C^{n\times n}$ 的值集，即

$\Re \left(M\right)=\left\{\left(My,y\right)/\left(y,y\right):0\ne y\in C^n\right\},$

其中，$\left(x,y\right)$ 表示$C^n$ 中两个向量的Euclidean内积。

定理1. 当且仅当

$0\notin \Re \left(A{W}^{-1}\right)\cap \Re \left(A{\left(\alpha I+T\right)}^{-1}\right)$

成立时，残差满足

$\Vert r^{(k+1)}\Vert \le \frac{\sqrt{{\Vert A{W}^{-1}\Vert }^2-d_1{}^2}}{\Vert A{W}^{-1}\Vert }\frac{\sqrt{\Vert A{\left(\alpha I+T\right)}^{-1}\Vert -d_2^2}}{\Vert A{\left(\alpha I+T\right)}^{-1}\Vert }\Vert r^{(k)}\Vert ,$ (12)

对于任何非负整数$k,d_1$ 和$d_2$ 分别表示从原点到$\Re \left(A{W}^{-1}\right)$ 和$\Re \left(A{\left(\alpha I+T\right)}^{-1}\right)$ 的距离，则对任意的$x^{(0)}\in C^n$ ，求解复对称线性系统(1)的MRLMHSS迭代方法都收敛。

证明：用$R(\cdot )$ 表示任意给定矩阵的值空间，上标$\perp$ 表示复向量空间$C^n$ 中任意给定向量空间的正交补空间。我们可以发现在MRLMHSS方法的每一步都包含两个残差投影过程，即$\Vert r^{\left(k+\frac{1}{2}\right)}\Vert$ 和$\Vert r^{(k+1)}\Vert$ 分别是$r^{(k)}$ 和$r^{\left(k+\frac{1}{2}\right)}$ 到向量空间$R{\left(A{W}^{-1}\right)}^{\perp }$ 和$R{\left(A{\left(\alpha I+T\right)}^{-1}\right)}^{\perp }$ 投影。因此，$\Vert r^{(k+1)}\Vert \le \Vert r^{(k)}\Vert$ 当且仅当$r^{(k)}$ 与$A{W}^{-1}$ 正交时，即

$\left(r^{(k)},A{W}^{-1}{r}^{(k)}\right)=0$

时取等号。这意味着当且仅当$0\notin \Re \left(W^{-*}{A}^{*}\right)$ 时，$\Vert r^{(k+1)}\Vert <\Vert r^{(k)}\Vert$ 。因为对于任何矩阵$M\in C^{n\times n}$ ，$M^{*}$ 的值集是$M$ 值集的复共轭，所以，当且仅当$0\notin \Re \left(A{W}^{-1}\right)$ 时，

$\Vert r^{\left(k+\frac{1}{2}\right)}\Vert <\Vert r^{(k)}\Vert ,$

类似地，可以得到，当且仅当$0\notin \Re \left(A{\left(\alpha I+T\right)}^{-1}\right)$

$\Vert r^{(k+1)}\Vert <\Vert r^{\left(k+\frac{1}{2}\right)}\Vert ,$

因此，综上可以得到当且仅当$0\notin \Re \left(A{W}^{-1}\right)\cap \Re \left(A{\left(\alpha I+T\right)}^{-1}\right)$ 时，

$\Vert r^{(k+1)}\Vert <\Vert r^{(k)}\Vert ,$

因为值域是一个闭集，所以$\Re \left(A{W}^{-1}\right)$ 和$\Re \left(A{\left(\alpha I+T\right)}^{-1}\right)$ 到原点的距离可以分别表示为

$d_1=\underset{0\ne y\in C^n}{\min }\left|\frac{\left(A{W}^{-1}{r}^{(k)},r^{(k)}\right)}{\left(y,y\right)}-0\right|,$

$d_2=\underset{0\ne y\in C^n}{\min }\left|\frac{\left(A{\left(\alpha I+T\right)}^{-1}y,y\right)}{\left(y,y\right)}-0\right|,$

将(7)和(8)代入(5)和(6)得

$\begin{array}{l}{\Vert r^{\left(k+\frac{1}{2}\right)}\Vert }^2={\Vert r^{(k)}\Vert }^2-\frac{{\left|\left(A{W}^{-1}{r}^{(k)},r^{(k)}\right)\right|}^2}{{\Vert A{W}^{-1}{r}^{(k)}\Vert }^2}\\ ={\Vert r^{(k)}\Vert }^2\left(1-{\left|\frac{{\left|\left(A{W}^{-1}{r}^{(k)},r^{(k)}\right)\right|}^2}{\left(r^{(k)},r^{(k)}\right)}\right|}^2\frac{{\Vert r^{(k)}\Vert }^2}{{\Vert A{W}^{-1}{r}^{(k)}\Vert }^2}\right)\\ \le {\Vert r^{(k)}\Vert }^2\left(1-\frac{d_1^2}{{\Vert A{W}^{-1}\Vert }^2}\right)\end{array}$

和

${\Vert r^{(k+1)}\Vert }^2\le {\Vert r^{\left(k+\frac{1}{2}\right)}\Vert }^2\left(1-\frac{d_2^2}{{\Vert A{\left(\alpha I+T\right)}^{-1}\Vert }^2}\right)$

结合上述两个不等式，有

${\Vert r^{(k+1)}\Vert }^2\le {\Vert r^{(k)}\Vert }^2\left(1-\frac{d_1^2}{{\Vert A{W}^{-1}\Vert }^2}\right)\left(1-\frac{d_2^2}{{\Vert A{\left(\alpha I+T\right)}^{-1}\Vert }^2}\right)$

综上，得到了结果(12)，证明完毕。

附注3. 根据以上证明得到，当且仅当

$0\notin \Re \left(A{W}^{-1}\right)\cap \Re \left(A{\left(\alpha I+T\right)}^{-1}\right)$

时，对于任意初始猜测$x^{(0)}\in C^n$ ，MRLMHSS迭代法是收敛的。但在实际应用中，验证以上条件对给定的矩阵$A$ 和给定的正常数$\alpha$ 是否有效并不容易。基于上述定理，接下来我们给出一个更加容易判定收敛性的充分必要条件。

设$\nu >0$ 和$\nu \ge 0$ ，分别为矩阵$W$ 和$T$ 的特征值，记${\nu }_{\min }$ 和${\nu }_{\max }$ 分别为矩阵$W$ 的极小和最大特征值，${\mu }_{\min }$ 和${\mu }_{\max }$ 为矩阵$T$ 的极小和最大特征值。首先，我们引出了文献[12]中关于LMHSS迭代法的收敛结果，LMHSS迭代法的迭代矩阵为

$M\left(\alpha \right)=-i{\left(\alpha I+T\right)}^{-1}\left(\alpha I+iW\right)W^{-1}T$ .

定义：

$M_1=W$ , $N_1=-iT$ , $M_2=\left(\alpha I+T\right)$ , $N_2=\left(\alpha I+iW\right)$ .

在LMHSS迭代法中，我们通过分析迭代矩阵$M\left(\alpha \right)$ 谱半径的上界给出了LMHSS迭代法的收敛条件，即

$\begin{array}{c}\rho \left(M\left(\alpha \right)\right)=\rho \left(-i{\left(\alpha I+T\right)}^{-1}\left(\alpha I+iW\right)W^{-1}T\right)\\ =\rho \left(-i\left(\alpha I+iW\right)W^{-1}T{\left(\alpha I+T\right)}^{-1}\right)\\ \le \Vert -i\left(\alpha I+iW\right)W^{-1}T{\left(\alpha I+T\right)}^{-1}\Vert \\ \le \Vert \left(\alpha I+iW\right)W^{-1}\Vert \Vert -iT{\left(\alpha I+T\right)}^{-1}\Vert \\ =\underset{\nu \in sp(W)}{\max }\frac{\sqrt{{\alpha }^2+{\nu }^2}}{\nu }\cdot \underset{\mu \in sp(T)}{\max }\frac{\mu }{\alpha +\mu }\end{array}$

谱半径的上界与参数$\alpha$ 以及$W$ 和$T$ 的特征值有关，即收敛性条件也与它们三者有关。

引理1. [12] 设$A=W+iT\in C^{n\times n}$ 是一个复对称矩阵，$W\in R^{n\times n}$ 和$T\in R^{n\times n}$ 分别为对称正定和对称半正定矩阵，那么，LMHSS迭代矩阵的谱半径$\rho \left(M\left(\alpha \right)\right)\le \sigma \left(\alpha \right)$ ，其中

$\sigma \left(\alpha \right)=\frac{\sqrt{{\alpha }^2+{\nu }_{\min }^2}}{{\nu }_{\min }}\frac{{\mu }_{\max }}{\alpha +{\mu }_{\max }},$

• 如果${\nu }_{\min }\ge {\mu }_{\max }$ ，则对任意的$\alpha >0$ ，$\sigma \left(\alpha \right)<1$ ，即LMHSS迭代法是无条件收敛的。

• 如果${\nu }_{\min }<{\mu }_{\max }$ ，当且仅当

$\alpha <\frac{2{\mu }_{\max }{\nu }_{\min }^2}{{\mu }_{\max }^2-{\nu }_{\min }^2}$ (13)

时，$\sigma \left(\alpha \right)<1$ ，这意味着LMHSS迭代法在条件(13)下是收敛的。

接下来，我们将引入一个引理，介绍两个广义参数是函数$\Vert r^{(k+1)}\Vert$ 的极小值点。

引理2. 在(9)和(10)中定义的${\lambda }_k$ 和${\theta }_k$ 是函数$\Vert r^{(k+1)}\Vert$ 的极小值点，即

$\left({\lambda }_k,{\theta }_k\right)=\underset{(\lambda ,\theta )\in C^n}{\arg \min }\Vert \left(I+i\theta F_2\right)\left(I-\lambda F_1\right)r^{(k)}\Vert ,$

或

$\Vert r^{(k+1)}\Vert =\Vert \left(I+i{\theta }_k{F}_2\right)\left(I-{\lambda }_k{F}_1\right)r^{(k)}\Vert =\underset{(\lambda ,\theta )\in C^n}{\min }\Vert \left(I+i\theta F_2\right)\left(I-\lambda F_1\right)r^{(k)}\Vert .$

证明：具体过程类似文献[22]的定理1。

我们在证明MRLMHSS迭代法的收敛性时，用到了LMHSS迭代矩阵谱半径的上界，而最优参数${\alpha }_{opt}$ 是通过最小化迭代矩阵的谱半径得到的，即

${\alpha }_{opt}=\underset{\alpha >0}{\arg \min }\rho \left(-i{\left(\alpha I+T\right)}^{-1}\left(\alpha I+iW\right)W^{-1}T\right)$

如果要最小化迭代矩阵的谱半径就会涉及到求解矩阵$W$ 和$T$ 的特征值，在实际过程中，计算$W$ 和$T$ 的特征值比较困难，所以在LMHSS迭代法中引入两个迭代参数控制步长，这样加快了LMHSS迭代法的计算效率。即我们有如下MRLMHSS迭代法的收敛性，所以，我们也根据迭代矩阵谱半径的上界来分析MRLMHSS迭代法的收敛性。

然后，根据以上两个引理，我们得到了如下推论，当系数矩阵$A$ 正规时，用于求解复对称线性系统(1)的MRLMHSS迭代法都收敛。

推论1. 假设矩阵$A=W+iT\in C^{n\times n}$ 是正规的，且满足引理1的条件时，则对任意的初始向量$x^{(0)}\in C^n$ ，求解复对称线性系统(1)的MRLMHSS迭代方法都收敛。

证明：由引理2可知

$\Vert r^{(k+1)}\Vert =\underset{(\lambda ,\theta )\in C^2}{\min }\Vert \left(I+i\theta F_2\right)\left(I-\lambda F_1\right)r^{(k)}\Vert \le \Vert \left(I+i{F}_2\right)\left(I-F_1\right)r^{(k)}\Vert .$

根据$F_1$ 和$F_2$ 的定义，矩阵$I-F_1$ 和$I+i{F}_2$ 满足

$I-F_1=I-A{W}^{-1}=-iT{W}^{-1},$ (14)

$I+i{F}_2=I+iA{\left(\alpha I+T\right)}^{-1}=\left(\alpha I+iW\right){\left(\alpha I+T\right)}^{-1}.$ (15)

结合(14)和(15)得

$\begin{array}{c}\Vert r^{(k+1)}\Vert \le \Vert -i\left(\alpha I+iW\right){\left(\alpha I+T\right)}^{-1}T{W}^{-1}{r}^{(k)}\Vert \\ =\Vert -i\left(\alpha I+iW\right){\left(\alpha I+T\right)}^{-1}T{W}^{-1}\Vert \Vert r^{(k)}\Vert \end{array}$

由于矩阵$A$ 是正规的，即

$\begin{array}{l}\Vert r^{(k+1)}\Vert \le \Vert \left(\alpha I+iW\right)W^{-1}\Vert \Vert -iT{\left(\alpha I+T\right)}^{-1}\Vert \Vert r^{(k)}\Vert \\ =\sigma \left(\alpha \right)\Vert r^{(k)}\Vert \end{array}$

以及引理1可知，$\sigma \left(\alpha \right)<1$ ，则我们可以得到，当$k\to \infty$ 时

$\Vert r^{(k+1)}\Vert \le \sigma \left(\alpha \right)\Vert r^{(k)}\Vert \le \cdots \le {\left(\sigma \left(\alpha \right)\right)}^{(k+1)}\Vert r^{(0)}\Vert \to 0$

证明完毕。

4. 数值实验

在本节中，我们用两个不同的数值算例来说明MRLMHSS迭代方法的可行性和有效性。我们将比较MRLMHSS迭代方法，修正的Hermitian和反Hermitian分裂迭代方法(MHSS)，非平衡MHSS分裂迭代方法(LMHSS)，以及极小残差修正的Hermitian和反Hermitian分裂迭代方法(MRMHSS)的数值结果，包括迭代步数(IT)和经过的CPU时间(CPU)。在所有实验中，选择初始向量为$x^{(0)}=0$ ，当迭代次数超过2000次，或当前迭代满足

$\mathrm{Re}s:=\frac{\Vert b-A{x}^{(k)}\Vert }{\Vert b\Vert }\le {10}^{-6}$

这时，算法被终止。

数值实验实现平台：使用MATLAB (R2021b)，中央处理单元Core(TM) i5 1.60GHz CPU 和 8.0 GB RAM。在本文中我们所用的参数$\alpha$ 都是实验最优参数。

考虑以下复Helmholtz方程[3]：

$-\Delta u+{\sigma }_{1}u+i{\sigma }_{2}u=f$ ,

其中，${\sigma }_1$ 和${\sigma }_2$ 是实系数函数，$u$ 在区域$D=\left[0,1\right]\times \left[0,1\right]$ 上定义且满足Dirichlet边界条件。使用一致网格步长$h=\frac{1}{m+1}$ 的五点中心差分格式离散负拉普拉斯算子，得到的矩阵为$H$ ，将其写为张量积形式$H=I\otimes B_m+B_m\otimes I$ ，其中，$B_m=h^{-2}\cdot \text{tridiag}\left(-1,2,-1\right)\in R^{m\times m}$ 。因此，$H\in R^{n\times n}$ 是一个块三对角矩阵，其中$n=m^2$ ，由此导出复对称线性系统：

$\left[\left(H+{\sigma }_{1}I\right)+i{\sigma }_{2}I\right]x=b.$

另外，我们取右端项$b=\left(1+i\right)A1$ 其中$1$ 表示所有元素都为1的列向量。进一步，我们通过两边同乘$h^2$ 将系数矩阵和右端项规范化。

MHSS，LMHSS，MRMHSS和MRLMHSS迭代方法的实验最优参数如表1所示。表2中，我们给出了具有不同参数${\sigma }_2$ 的MHSS，LMHSS，MRMHSS和MRLMHSS 迭代方法的迭代次数(IT)和CPU时间(CPU)。从表2的结果可以看出，当系数矩阵的实部$W$ 占优时，随着${\sigma }_2$ 的变化，MRLMHSS方法在迭代次数和CPU时间上优于MRMHSS迭代方法，同时MRLMHSS迭代方法也优于表2的其他方法。

Table 1. The experimentally optimal parameters for ${\sigma }_1=100$

表1. ${\sigma }_1=100$ 时的实验最优参数

		网格
${\sigma }_2$	方法	16 × 16	32 × 32	64 × 64	128 × 128
1	MHSS $\left({\alpha }_{\exp }\right)$	1.4500	0.7500	0.4100	0.2150
	LMHSS $\left({\alpha }_{\exp }\right)$	1.0500	0.4100	1.0500	0.4100
	MRMHSS $\left({\alpha }_{\exp }\right)$	0.0500	0.0400	0.0310	0.0150
	MRLMHSS $\left({\alpha }_{\exp }\right)$	0.5500	0.5500	0.5500	0.0500
10	MHSS $\left({\alpha }_{\exp }\right)$	0.0350	0.0100	0.0021	0.0005
	LMHSS $\left({\alpha }_{\exp }\right)$	1.0500	0.5100	0.2500	0.5100
	MRMHSS $\left({\alpha }_{\exp }\right)$	0.1000	0.0500	0.0290	0.0150
	MRLMHSS $\left({\alpha }_{\exp }\right)$	0.5000	0.5500	0.2100	0.5500
100	MHSS $\left({\alpha }_{\exp }\right)$	0.5100	0.1000	0.0200	0.0050
	LMHSS $\left({\alpha }_{\exp }\right)$	0.5000	0.1500	0.0270	0.0091
	MRMHSS $\left({\alpha }_{\exp }\right)$	0.8000	0.2000	0.0200	0.0150
	MRLMHSS $\left({\alpha }_{\exp }\right)$	0.5500	0.5500	0.4500	0.0500
1000	MHSS $\left({\alpha }_{\exp }\right)$	1.5000	0.7500	0.2940	0.0750
	LMHSS $\left({\alpha }_{\exp }\right)$	0.0500	0.0130	0.0034	0.00085
	MRMHSS $\left({\alpha }_{\exp }\right)$	0.5500	1.5000	0.2500	0.0510
	MRLMHSS $\left({\alpha }_{\exp }\right)$	0.4100	0.0100	0.5400	0.0400

Table 2. Numerical results for four methods using experimentally optimal parameters for ${\sigma }_1=100$

表2. ${\sigma }_1=100$ 时，四种方法使用实验最优参数的数值结果

网格
${\sigma }_2$	方法	$m\times m$	16 × 16	32 × 32	64 × 64	128 × 128
1	MHSS	IT	64	104	180	326
		CPU	0.0070	0.0176	0.2472	3.1990
	LMHSS	IT	3	3	3	3
		CPU	0.0003	0.0006	0.0038	0.0282
	MRMHSS	IT	4	6	10	15
		CPU	0.0006	0.0019	0.0151	0.1617
	MRLMHSS	IT	3	3	3	2
		CPU	0.0004	0.0006	0.0027	0.0217
10	MHSS	IT	38	40	40	41
		CPU	0.0015	0.0076	0.0508	0.3971
	LMHSS	IT	6	5	5	5
		CPU	0.0002	0.0008	0.0062	0.0487
	MRMHSS	IT	5	7	10	15
		CPU	0.0004	0.0018	0.0162	0.1627
	MRLMHSS	IT	4	4	4	4
		CPU	0.0003	0.0011	0.0064	0.0446
100	MHSS	IT	30	36	39	40
		CPU	0.0011	0.0066	0.0501	0.3864
	LMHSS	IT	30	29	27	24
		CPU	0.0012	0.0048	0.0341	0.2287
	MRMHSS	IT	10	12	10	15
		CPU	0.0008	0.0030	0.0158	0.1642
	MRLMHSS	IT	8	10	10	10
		CPU	0.0005	0.0025	0.0150	0.1042
1000	MHSS	IT	29	29	32	37
		CPU	0.0022	0.0060	0.0409	0.3563
	LMHSS	IT	1919	1905	1859	1753
		CPU	0.0614	0.3331	2.2072	16.5894
	MRMHSS	IT	8	13	18	21
		CPU	0.0011	0.0037	0.0273	0.2300
	MRLMHSS	IT	10	23	40	53
		CPU	0.0005	0.0054	0.0601	0.5672

5. 结论

本章基于极小残差的思想，将极小残差技术应用于LMHSS迭代法中，提出了求解复对称线性系统的极小残差LMHSS (MRLMHSS)迭代法和不精确的MRLMHSS (IMRLMHSS)迭代法。虽然MRLMHSS方法比经典的LMHSS迭代方法多涉及两个迭代参数，但它们可以自动地计算。数值结果表明，当系数矩阵实部占优时，MRLMHSS迭代法是优于数值实验中其他方法的。因此，当系数矩阵实部占优时，本章提出的方法为求解复对称线性系统提供了更好的选择。