求解复对称线性方程组的两参数修正HSS方法

罗娅娟,马昌凤

(福建师范大学 数学与统计学院,福建 福州 350007)

0 引言

考虑如下复对称线性方程组的迭代解:

Ax=b,A∈Cn×n,x,b∈Cn.

(1)

其中A∈Cn×n是以下形式的复对称矩阵

A=W+iT.

(2)

复对称矩阵A∈Cn×n的Hermitian和反Hermitian的部分有

(3)

因此,当W是对称正定矩阵时,A是一个非Hermitian的复矩阵,并且是正定矩阵.这里的A*表示矩阵A的共轭转置.基于Hermitian和反Hermitian 分裂(HSS)

A=H+S.

(4)

在复矩阵A中,可以直接用Bai等[5]603-629引入的HSS迭代方法来计算复对称线性方程组(1)和(2)的近似解.通过利用系数矩阵A∈Cn×n的特殊结构,Bai等在文献[2]95-99中提出了一种修正的HSS(MHSS)迭代方法,该方法求解复对称线性方程组(1)和(2)比HSS迭代方法有效得多.

算法1 (MHSS迭代法)[2]98

步骤1 选取初始向量x(0)∈Cn.

(5)

式中α表示给定的正常数,I表示单位矩阵.

由于W∈Rn×n是对称正定矩阵,T∈Rn×n是对称半正定矩阵,α∈R是正数,矩阵αI+W和αI+T都是对称正定矩阵,因此,MHSS迭代法的每个步骤所涉及的两个线性子方程组都可以用多种实数计算的方法去有效地求解,比如精确的Cholesky 分解和非精确的 CG 方法或者多重网格方法.这与HSS迭代方法不同,在HSS迭代方法中,每个迭代步骤都需要求解系数矩阵αI+iT的移位反Hermitian线性子方程组,见文献[5]603-612,[6]413-440.如果使用稀疏的三角分解来求解每一步所涉及的线性子方程组,MHSS迭代方法需要的储存空间可能比HSS迭代方法少得多,因为只需要计算和储存2个三角因子,而不是3个.有关更多信息,请参阅文献[2]93-111,[5]603-619,[6]423-429.文献[2]93-111表明,对于任何初始猜测点,MHSS迭代方法收敛到复对称线性方程组(1)(2)的唯一解,其渐进收敛率

(6)

(7)

这里的κ2(·)用于表示相应矩阵的谱条件数.

然而,使用上述迭代方法直接求解线性方程组(1),涉及了复杂的计算,并增加了计算量.为了更好地提高数值性能,线性方程组(1)可以重新表达.设x=y+iz,b=p+iq,其中向量y,z,p,q∈RN.然后,复线性方程组(1)可以等价地表达为以下二乘二块结构:

(8)

线性方程组(8)也可以表达为广义鞍点问题的特定情况.目前,已经有许多迭代方法用于处理块二乘二块线性方程组[7],该方法包括类SOR 的迭代方法[8-10]、类HSS方法[11-13]、 预处理的Krylov子空间方法[14-15]、C 到R 迭代方法[16-17]等.有关更多的迭代方法详情,请参阅文献[18].

1 TMHSS迭代方法

在本节中,将建立MHSS实值迭代方法的新版本.通过在MHSS上应用双参数加速技术,推导一种新的迭代方法.新方法被定义为双参数MHSS(TMHSS) 实值迭代方法,或缩写为TMHSS迭代方法.设α,β>0,线性方程组(8)可以作为两个等式方程组呈现:

(9)

和

(10)

显然,如果选择α=β,TMHSS迭代方法会简化成MHSS迭代方法.此外,可以选择适当的参数α和β,以实现比MHSS迭代方法更高的计算效率,两个数值实验也验证了新方法的性能.通过上述拆分方程组,可以推导出TMHSS迭代方法来解决线性方程组(8) .接下来,将介绍TMHSS实值迭代方法:

算法2(TMHSS实值迭代方法)

步骤1 选择初始向量{y(0)T,z(0)T}T∈RN.

设α和β是两个给定的正常数,

(11)

通过简单的推导,迭代方法可以等价于以下形式:

(12)

x(k+1)=M(α,β)x(k)+N(α,β)g,

(13)

下面给出TMHSS迭代法的收敛性分析. 以下定理是TMHSS方法收敛的充分条件.

定理1 给定正参数α,β>0,且μj为T的特征值,λj为W的特征值,如果0<α≤β,β2-α2≤2αλmin,则迭代矩阵的谱半径ρ(M(α,β))≤σ2(α,β),λmin是W的最小特征值.

(14)

则TMHSS迭代法收敛.

证明由式(13)可知,TMHSS迭代方法的迭代矩阵为

(15)

其中G=(βI+T)-1,H=(αI+W)-1.易知迭代矩阵的谱半径

其中

(16)

下面再给出一个定理去证明TMHSS的收敛性.

定理2 给定正参数α,β>0,且μj为T的特征值,λj为W的特征值,如果0<β≤α,α2-β2≤2βμmin,则迭代矩阵的谱半径ρ(M(α,β))≤σ1(α,β),μmin是T的最小特征值.

(17)

则TMHSS 迭代方法收敛.

正如TMHSS迭代方法依赖于两个参数α,β,因此,确定参数α和β是有意义的,下面推导了最优参数α、β的表达式.

定理3 假设定理1、2是有效的,那么,将谱半径ρ(M(α,β))的上界σ(α)σ(β)最小化的准参数α*和β*是

(18)

其中λmin≤λj≤λmax是W的特征值,μmin≤μj≤μmax是T的特征值.

由定理1的证明,

(19)

(20)

所以σ的Hessian阵

(21)

2 数值实验

2.1 例子1[2]107

将线性方程组(2)写成以下形式:

[(-w2M+K)+i(wCV+CH)]x=b.

表1中,α,β值均是在定理3的基础上实验迭代取得的最优参数.此表说明了m=16,m=32,m=64,m=128 时,TMHSS实值迭代方法相对于α,β的收敛行为.显然,从图1中看出,TMHSS实值法的迭代次数总是低于MHSS方法,这证实了TMHSS方法具有更快的收敛速度.

表1 例子1 MHSS和TMHSS的nIT,tCPU

图1表示了当m=16时,MHSS和TMHSS实值迭代法相对于参数α的收敛行为.把参数β选择为实验的最优参数βexp,从图中可以看出,TMHSS实值迭代法总是比MHSS迭代法收敛得快.

图1 例子1中MHSS,TMHSS当m=16时的迭代次数

图2表示当m=16时,MHSS和TMHSS实值迭代法相对于参数β的收敛行为.把参数α选择为实验的最优参数βexp,从图中可以看出,TMHSS实值迭代法总是比MHSS迭代法收敛得快.

图2 例子1中TMHSS当m=16时的迭代次数

图3中,针对例子描述了TMHSS实值迭代法当m=16时的nIT相对于α,β的三维关系图,可以看出α在2.5～3,β在6～8变化较大,α,β趋于1时迭代次数较少.实验表明,TMHSS在选择适当参数时是优于MHSS迭代法的.

图3 例子1中TMHSS当m=16时的迭代次数

2.2 例子2[2]109

表2中α,β值均为在定理3的基础上实验迭代取得的最优参数.此表说明了m=16,m=32,m=64,m=128 时,TMHSS实值迭代方法相对于α,β的收敛行为.显然,从图4中看出,TMHSS实值法的迭代次数总是低于MHSS方法,这证实了TMHSS方法具有更快的收敛速度.

图4 MHSS,TMHSS当m=16时的迭代次数

表2 例子2 MHSS和TMHSS的nIT,tCPU

图4表示当m=16 时,MHSS和TMHSS实值迭代法相对于参数α的收敛行为.把参数β选择为实验的最优参数βexp,从图中可以看出,TMHSS实值迭代法总是比MHSS迭代法收敛得快.

图5中,针对例子描述了TMHSS实值迭代法当m=16时的nIT相对于α,β的三维关系图,可以看出α在1～1.2,β在8～9迭代次数较少.实验表明,TMHSS 在选择适当参数时是优于MHSS迭代法的.

图5 TMHSS当m=16时的迭代次数

3 结论

提出了大型稀疏复对称线性方程组(W+iT)x=b的双参数MHSS实值迭代方法,其中W和T是实对称正定矩阵.研究了它们的收敛性质及最优的参数选择,通过2个数值实验将TMHSS实值迭代方法与MHSS 迭代法比较,证明在收敛性和稳定性上都优于MHSS实值迭代方法.