分块矩阵的Gauss-Seidel迭代法解线性方程组
题目描述
考虑大型线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是 \(n \times n\) 可逆矩阵，\(\mathbf{x}\) 和 \(\mathbf{b}\) 是 \(n\) 维向量。当 \(A\) 是分块矩阵时（例如因问题维度高或结构特殊而需分块处理），需设计分块形式的Gauss-Seidel迭代法求解。将 \(A\) 划分为 \(p \times p\) 的分块形式：
\[A = \begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1p} \\ A_{21} & A_{22} & \cdots & A_{2p} \\ \vdots & \vdots & \ddots & \vdots \\ A_{p1} & A_{p2} & \cdots & A_{pp} \end{bmatrix}, \quad \mathbf{x} = \begin{bmatrix} \mathbf{x}_1 \\ \mathbf{x}_2 \\ \vdots \\ \mathbf{x}_p \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} \mathbf{b}_1 \\ \mathbf{b}_2 \\ \vdots \\ \mathbf{b}_p \end{bmatrix}, \]
其中每个对角块 \(A_{ii}\) 可逆。分块Gauss-Seidel法通过迭代更新每个子向量 \(\mathbf{x}_i\) 来逼近解。
解题过程
- 分块分解与迭代格式推导
将 \(A\) 写为分块下三角部分 \(L\)、分块对角部分 \(D\)、分块上三角部分 \(U\) 之和：
\[ A = L + D + U, \]
其中：
- \(L\) 为分块严格下三角矩阵（对角块为零），
- \(D = \operatorname{diag}(A_{11}, A_{22}, \dots, A_{pp})\) 为分块对角矩阵，
- \(U\) 为分块严格上三角矩阵（对角块为零）。
迭代格式基于分裂 \(A = (L + D) + U\)：
\[ (L + D)\mathbf{x}^{(k+1)} = -U\mathbf{x}^{(k)} + \mathbf{b}, \]
其中 \(\mathbf{x}^{(k)}\) 是第 \(k\) 次迭代的近似解。展开后，对每个子向量 \(\mathbf{x}_i^{(k+1)}\) 有：
\[ A_{ii}\mathbf{x}_i^{(k+1)} = \mathbf{b}_i - \sum_{j=1}^{i-1} A_{ij}\mathbf{x}_j^{(k+1)} - \sum_{j=i+1}^{p} A_{ij}\mathbf{x}_j^{(k)}, \]
即每次更新 \(\mathbf{x}_i\) 时，使用已更新的 \(\mathbf{x}_1^{(k+1)}, \dots, \mathbf{x}_{i-1}^{(k+1)}\) 和未更新的 \(\mathbf{x}_{i+1}^{(k)}, \dots, \mathbf{x}_p^{(k)}\)。
- 迭代步骤详解
- 步骤1：初始化 \(\mathbf{x}^{(0)}\)（通常设为零向量或近似解）。
- 步骤2：对于第 \(k+1\) 次迭代，按 \(i=1,2,\dots,p\) 的顺序更新子向量：
\[ \mathbf{x}_i^{(k+1)} = A_{ii}^{-1} \left( \mathbf{b}_i - \sum_{j=1}^{i-1} A_{ij}\mathbf{x}_j^{(k+1)} - \sum_{j=i+1}^{p} A_{ij}\mathbf{x}_j^{(k)} \right). \]
注意：
- 求和项 $ \sum_{j=1}^{i-1} A_{ij}\mathbf{x}_j^{(k+1)} $ 使用当前迭代中已更新的子向量，
- 求和项 $ \sum_{j=i+1}^{p} A_{ij}\mathbf{x}_j^{(k)} $ 使用前一次迭代的子向量。
- 步骤3：检查收敛条件，如相对残差 \(\|\mathbf{b} - A\mathbf{x}^{(k+1)}\| / \|\mathbf{b}\| < \epsilon\) 或迭代次数达到上限。若未满足，返回步骤2。
-
收敛性分析
若 \(A\) 按分块严格对角占优（即 \(\|A_{ii}^{-1}\| \sum_{j \neq i} \|A_{ij}\| < 1\)）或分块对称正定，则迭代收敛。收敛速度依赖于分块矩阵的谱半径 \(\rho((L+D)^{-1}U)\)。 -
示例说明
设 \(p=2\)，方程组为：
\[ \begin{cases} A_{11}\mathbf{x}_1 + A_{12}\mathbf{x}_2 = \mathbf{b}_1, \\ A_{21}\mathbf{x}_1 + A_{22}\mathbf{x}_2 = \mathbf{b}_2. \end{cases} \]
迭代格式为：
\[ \begin{aligned} \mathbf{x}_1^{(k+1)} &= A_{11}^{-1}(\mathbf{b}_1 - A_{12}\mathbf{x}_2^{(k)}), \\ \mathbf{x}_2^{(k+1)} &= A_{22}^{-1}(\mathbf{b}_2 - A_{21}\mathbf{x}_1^{(k+1)}). \end{aligned} \]
每次先更新 \(\mathbf{x}_1\)，再利用新值更新 \(\mathbf{x}_2\)。
关键点
- 分块Gauss-Seidel法通过分块求解降低计算复杂度，尤其适用于并行或分层存储系统。
- 对角块 \(A_{ii}\) 需易求逆（如小矩阵或特殊结构），否则需内层迭代。