6.5_交替方向法与HSS迭代法

6.5 交替方向法与HSS迭代法

6.5.1 多步迭代法

设 A=M1−N1=M2−N2A = M_{1} - N_{1} = M_{2} - N_{2} 是 AA 的两个矩阵分裂, 则可以构造迭代格式

{M1x(k+12)=N1x(k)+b,M2x(k+1)=N2x(k+12)+b,k=0,1,2,… .(6.30)\left\{ \begin{array}{l} M _ {1} x ^ {\left(k + \frac {1}{2}\right)} = N _ {1} x ^ {(k)} + b, \\ M _ {2} x ^ {(k + 1)} = N _ {2} x ^ {\left(k + \frac {1}{2}\right)} + b, \end{array} \quad k = 0, 1, 2, \dots . \right. \tag {6.30}

这就是两步迭代法, 对应的分裂称为二重分裂. 易知, 两步迭代格式 (6.23) 的迭代矩阵为

G=M2−1N2M1−1N1.G = M _ {2} ^ {- 1} N _ {2} M _ {1} ^ {- 1} N _ {1}.

因此, 其收敛的充要条件是 ρ(M2−1N2M1−1N1)<1\rho (M_2^{-1}N_2M_1^{-1}N_1) < 1 .

类似地, 我们可以推广到多步迭代法. 设 ll 是一个正整数, 则 AA 的 ll 重分裂为

A=M1−N1=M2−N2=⋯=Ml−Nl,A = M _ {1} - N _ {1} = M _ {2} - N _ {2} = \dots = M _ {l} - N _ {l},

相应的多步迭代法为

{M1x(k+1l)=N1x(k)+b,M2x(k+2l)=N2x(k+1l)+b,…Mlx(k+1)=Nlx(k+l−1l)+b,k=0,1,2,….\left\{ \begin{array}{l} M _ {1} x ^ {(k + \frac {1}{l})} = N _ {1} x ^ {(k)} + b, \\ M _ {2} x ^ {(k + \frac {2}{l})} = N _ {2} x ^ {(k + \frac {1}{l})} + b, \\ \dots \\ M _ {l} x ^ {(k + 1)} = N _ {l} x ^ {(k + \frac {l - 1}{l})} + b, \end{array} \right. \qquad k = 0, 1, 2, \ldots .

6.5.2 交替方向法

交替方向法 (Alternating Direction Implicit, ADI) 是由 Peaceman 和 Rachford [103] 于 1955 年提出, 用于计算偏微分方程的数值解, 因此也称为 PR 方法. 其本质上也可以看成是一个两步迭代法.

设 A=A1+A2A = A_{1} + A_{2} ，则ADI迭代格式为

{(αI+A1)x(k+12)=(αI−A2)x(k)+b,(αI+A2)x(k+1)=(αI−A1)x(k+12)+b,k=0,1,2,…,(6.31)\left\{ \begin{array}{l} \left(\alpha I + A _ {1}\right) x ^ {\left(k + \frac {1}{2}\right)} = \left(\alpha I - A _ {2}\right) x ^ {(k)} + b, \\ \left(\alpha I + A _ {2}\right) x ^ {(k + 1)} = \left(\alpha I - A _ {1}\right) x ^ {\left(k + \frac {1}{2}\right)} + b, \end{array} \quad k = 0, 1, 2, \dots , \right. \tag {6.31}

其中 α∈R\alpha \in \mathbb{R} 是迭代参数. 易知 ADI 方法的迭代矩阵为

GADI=(αI+A2)−1(αI−A1)(αI+A1)−1(αI−A2).G _ {\mathrm {A D I}} = (\alpha I + A _ {2}) ^ {- 1} (\alpha I - A _ {1}) (\alpha I + A _ {1}) ^ {- 1} (\alpha I - A _ {2}).

它相似于

G~≜(αI−A1)(αI+A1)−1(αI−A2)(αI+A2)−1.\tilde {G} \triangleq (\alpha I - A _ {1}) (\alpha I + A _ {1}) ^ {- 1} (\alpha I - A _ {2}) (\alpha I + A _ {2}) ^ {- 1}.

所以 ADI 迭代 (6.24) 收敛的充要条件是

ρ(G~)<1.\rho (\tilde {G}) < 1.

若 AA 对称正定, 且 A1A_{1} 和 A2A_{2} 中有一个是对称正定, 另一个是对称半正定, 则有下面的收敛定理.

定理6.34 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 对称正定, A=A1+A2A = A_{1} + A_{2} , 其中 A1A_{1} 和 A2A_{2} 中有一个是对称正定, 另一个是对称半正定, 则对任意正数 α>0\alpha > 0 , 有 ρ(G~)<1\rho(\tilde{G}) < 1 , 即 ADI 迭代法 (6.24) 收敛. (板书)

证明. 不妨假设 A1A_{1} 对称正定, A2A_{2} 对称半正定, 则 (αI−A1)(αI+A1)−1(\alpha I - A_{1})(\alpha I + A_{1})^{-1} 和 (αI−A2)(αI+A2)−1(\alpha I - A_{2})(\alpha I + A_{2})^{-1} 都对称, 故

∥(αI−A1)(αI+A1)−1∥2=max⁡λ∈σ(A1)∣α−λα+λ∣<1,\| (\alpha I - A _ {1}) (\alpha I + A _ {1}) ^ {- 1} \| _ {2} = \max _ {\lambda \in \sigma (A _ {1})} \left| \frac {\alpha - \lambda}{\alpha + \lambda} \right| < 1,
∥(αI−A2)(αI+A2)−1∥2=max⁡λ∈σ(A2)∣α−λα+λ∣≤1.\| (\alpha I - A _ {2}) (\alpha I + A _ {2}) ^ {- 1} \| _ {2} = \max _ {\lambda \in \sigma (A _ {2})} \left| \frac {\alpha - \lambda}{\alpha + \lambda} \right| \leq 1.

所以,

ρ(G~)≤∥G~∥2≤∥(αI−A1)(αI+A1)−1∥2⋅∥(αI−A2)(αI+A2)−1∥2<1.\rho (\tilde {G}) \leq \| \tilde {G} \| _ {2} \leq \| (\alpha I - A _ {1}) (\alpha I + A _ {1}) ^ {- 1} \| _ {2} \cdot \| (\alpha I - A _ {2}) (\alpha I + A _ {2}) ^ {- 1} \| _ {2} < 1.

6.5.3 HSS方法

HSS 方法全称为 Hermitian and Skew-Hermitian Splitting method, 是由 Bai, Golub 和 Ng\mathrm{Ng} [8] 于 2003 年提出.

设 A=H+SA = H + S ，其中 HH 和 SS 分别是 AA 的对称与反对称(斜对称，Skew-Hermite)部分，即

H=A+AT2,S=A−AT2.H = \frac {A + A ^ {\mathsf {T}}}{2}, \quad S = \frac {A - A ^ {\mathsf {T}}}{2}.

该分裂就称为HS分裂，即HSS

4 任何一个矩阵都具有HS分裂.如果 A∈Cn×nA\in \mathbb{C}^{n\times n} ，则取共轭转置

类似于ADI方法，我们可得下面的HSS方法

{(αI+H)x(k+12)=(αI−S)x(k)+b,(αI+S)x(k+1)=(αI−H)x(k+12)+b,k=0,1,2,… .(6.32)\left\{ \begin{array}{l} (\alpha I + H) x ^ {(k + \frac {1}{2})} = (\alpha I - S) x ^ {(k)} + b, \\ (\alpha I + S) x ^ {(k + 1)} = (\alpha I - H) x ^ {(k + \frac {1}{2})} + b, \end{array} \right. \quad k = 0, 1, 2, \dots . \tag {6.32}

易知，HSS方法的迭代矩阵为

GHSS=(αI+S)−1(αI−H)(αI+H)−1(αI−S).G _ {\mathrm {H S S}} = (\alpha I + S) ^ {- 1} (\alpha I - H) (\alpha I + H) ^ {- 1} (\alpha I - S).

同样, 它相似于

G~≜(αI−H)(αI+H)−1(αI−S)(αI+S)−1.\tilde {G} \triangleq (\alpha I - H) (\alpha I + H) ^ {- 1} (\alpha I - S) (\alpha I + S) ^ {- 1}.

我们首先考察矩阵 (αI−S)(αI+S)−1(\alpha I - S)(\alpha I + S)^{-1} . 事实上, 它是一个酉矩阵 (见习题 (5.6)). 因此

∥(αI−S)(αI+S)−1∥2=1.\left\| \left(\alpha I - S\right) \left(\alpha I + S\right) ^ {- 1} \right\| _ {2} = 1.

由于 HH 是对称矩阵，因此

∥(αI−H)(αI+H)−1∥2=max⁡λ∈σ(H)∣α−λα+λ∣.\| (\alpha I - H) (\alpha I + H) ^ {- 1} \| _ {2} = \max _ {\lambda \in \sigma (H)} \left| \frac {\alpha - \lambda}{\alpha + \lambda} \right|.

定理6.35 设 A∈Rn×nA \in \mathbb{R}^{n \times n} 正定, 则对任意正数 α>0\alpha > 0 , 有 ρ(G~)<1\rho(\tilde{G}) < 1 , 即HSS迭代法(6.25)收敛.

(板书)

证明. 由于 AA 正定, 即 HH 对称正定, 故

∥(αI−H)(αI+H)−1∥2=max⁡λ∈σ(H)∣α−λα+λ∣<1.\| (\alpha I - H) (\alpha I + H) ^ {- 1} \| _ {2} = \max _ {\lambda \in \sigma (H)} \left| \frac {\alpha - \lambda}{\alpha + \lambda} \right| < 1.

所以, 结论成立.

参数 α\alpha 的选取

为了达到最快收敛效果, 我们希望迭代矩阵的谱半径越小越好. 但是在一般情况下, 谱半径很难计算或估计. 因此要极小化谱半径是非常困难的, 或者说是不可能的. 此时, 我们能做的往往是极小化它的一个上界.

由前面的分析可知

ρ(GHSS)=ρ(G~)≤max⁡λ∈σ(H)∣α−λα+λ∣≜σ(α).\rho \left(G _ {\mathrm {H S S}}\right) = \rho (\tilde {G}) \leq \max _ {\lambda \in \sigma (H)} \left| \frac {\alpha - \lambda}{\alpha + \lambda} \right| \triangleq \sigma (\alpha).

下面考虑 σ(α)\sigma (\alpha) 的极小值点.设 HH 的最大和最小特征值分别为 λmax(H)\lambda_{\mathrm{max}}(H) 和 λmin(H)\lambda_{\mathrm{min}}(H) ，则我们有下面的结论.

定理6.36 [8]设 A∈Rn×nA\in \mathbb{R}^{n\times n} 正定，则极小极大问题

min⁡α>0max⁡λmin⁡(H)≤λ≤λmax⁡(H)∣α−λα+λ∣\min_{\alpha >0}\max_{\lambda_{\min}(H)\leq \lambda \leq \lambda_{\max}(H)}\left|\frac{\alpha - \lambda}{\alpha + \lambda}\right|

的解为

α∗=λmax⁡(H)λmin⁡(H).\alpha_ {*} = \sqrt {\lambda_ {\max} (H) \lambda_ {\min} (H)}.

此时

σ(α∗)=λmax⁡(H)−λmin⁡(H)λmax⁡(H)+λmin⁡(H)=κ(H)−1κ(H)+1.\sigma \left(\alpha_ {*}\right) = \frac {\sqrt {\lambda_ {\operatorname* {m a x}} (H)} - \sqrt {\lambda} _ {\operatorname* {m i n}} (H)}{\sqrt {\lambda_ {\operatorname* {m a x}} (H)} + \sqrt {\lambda} _ {\operatorname* {m i n}} (H)} = \frac {\sqrt {\kappa (H)} - 1}{\sqrt {\kappa (H)} + 1}.

HSS 自从被提出来以后, 很多学者将其进行了推广, 如 PSS, NSS, AHSS 等, 感兴趣的读者可以参考相关文献.

Previous6.4_加速方法
Next6.6_课后习题