Krylov子空间方法解线性方程组

题目描述：
给定一个大型稀疏线性方程组 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 是 \(n \times n\) 的矩阵，\(\mathbf{b}\) 是已知向量。由于矩阵规模较大，直接法（如LU分解）计算成本高。Krylov子空间方法通过迭代在子空间内寻找近似解。本题以典型的共轭梯度法（CG）为例，要求解对称正定矩阵的线性方程组。

解题过程：

1. 问题分析：

   • 目标：求解 \(A\mathbf{x} = \mathbf{b}\)，其中 \(A\) 对称正定（即 \(A = A^T\)，且所有特征值大于零）。
   • 难点：当 \(n\) 很大时，直接法效率低。Krylov方法通过迭代逼近解，仅需矩阵-向量乘法，避免显式存储 \(A\)。

2. Krylov子空间构建：

   • 定义初始残差 \(\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0\)（\(\mathbf{x}_0\) 为初始猜测，常取零向量）。
   • 第 \(k\) 步的Krylov子空间为：

\[ \mathcal{K}_k(A, \mathbf{r}_0) = \text{span} \{ \mathbf{r}_0, A\mathbf{r}_0, A^2\mathbf{r}_0, \dots, A^{k-1}\mathbf{r}_0 \}. \]

• 此空间由初始残差和矩阵幂的乘积张成，迭代解 \(\mathbf{x}_k\) 在此子空间中寻找。

3. 共轭梯度法原理：

   • 目标：在子空间 \(\mathcal{K}_k\) 中寻找解，使残差 \(\mathbf{r}_k = \mathbf{b} - A\mathbf{x}_k\) 与子空间正交（即 Ritz-Galerkin 条件）。
   • 关键思想：通过构造一组 \(A\)-共轭向量（即搜索方向 \(\mathbf{p}_k\) 满足 \(\mathbf{p}_i^T A \mathbf{p}_j = 0\) 对 \(i \neq j\)），确保每步更新沿最优方向。

4. 迭代步骤：

   • 步骤1：初始化。
     设 \(\mathbf{x}_0 = \mathbf{0}\)，计算 \(\mathbf{r}_0 = \mathbf{b} - A\mathbf{x}_0 = \mathbf{b}\)，令 \(\mathbf{p}_0 = \mathbf{r}_0\)。
   • 步骤2：对 \(k = 0, 1, 2, \dots\) 迭代直至收敛：
     1. 计算步长 \(\alpha_k\)：

\[ \alpha_k = \frac{\mathbf{r}_k^T \mathbf{r}_k}{\mathbf{p}_k^T A \mathbf{p}_k}. \]

    （此步长使残差在搜索方向上最小化。）  
 2. 更新解：  

\[ \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k. \]

 3. 更新残差：  

\[ \mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k A \mathbf{p}_k. \]

 4. 计算系数 $ \beta_k $：  

\[ \beta_k = \frac{\mathbf{r}_{k+1}^T \mathbf{r}_{k+1}}{\mathbf{r}_k^T \mathbf{r}_k}. \]

    （$ \beta_k $ 确保新搜索方向与之前方向 $ A $-共轭。）  
 5. 更新搜索方向：  

\[ \mathbf{p}_{k+1} = \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k. \]

• 步骤3：终止条件。
  当残差 \(\|\mathbf{r}_k\|\) 小于预设容差时，输出 \(\mathbf{x}_k\) 作为近似解。

5. 算法特性：
   • 有限步收敛：理论上，最多 \(n\) 步得到精确解（忽略舍入误差）。
   • 高效性：每步仅需一次矩阵-向量乘法和内积运算，适合稀疏矩阵。
   • 适用性：仅限对称正定矩阵。非对称矩阵需使用GMRES等变体。

总结：
Krylov子空间方法通过迭代在低维子空间逼近解，共轭梯度法是其典型代表，结合了最速下降法和共轭方向法的优点，能高效求解大规模稀疏线性方程组。