共轭梯度法解对称正定线性方程组

字数 2662 2025-10-26 09:00:43

共轭梯度法解对称正定线性方程组

题目描述
给定一个对称正定矩阵 \(A \in \mathbb{R}^{n \times n}\) 和向量 \(b \in \mathbb{R}^n\)，求解线性方程组 \(A x = b\)。要求使用共轭梯度法（Conjugate Gradient Method），并解释其逐步迭代过程。

解题过程

1. 共轭梯度法的基本思想

共轭梯度法是一种迭代算法，用于求解对称正定（SPD）线性方程组。它的核心思想是：

在每一步迭代中，沿着一个共轭方向（A-正交方向）更新解向量 \(x\)，使得残差（误差）在每一步均减小。
共轭方向满足：\(p_i^T A p_j = 0\)（对 \(i \neq j\)），即方向向量两两关于 \(A\) 正交。

2. 算法步骤详解

设初始解向量为 \(x_0\)，初始残差 \(r_0 = b - A x_0\)，初始搜索方向 \(p_0 = r_0\)。迭代步骤如下（对 \(k = 0, 1, 2, \dots\) 直至收敛）：

步骤 1：计算步长 \(\alpha_k\)

\[\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k} \]

分子 \(r_k^T r_k\) 是当前残差的模长平方。
分母 \(p_k^T A p_k\) 是搜索方向 \(p_k\) 在 \(A\) 度量下的模长。
\(\alpha_k\) 的作用是沿 \(p_k\) 方向移动多远，使残差最小化。

步骤 2：更新解向量 \(x_{k+1}\)

\[x_{k+1} = x_k + \alpha_k p_k \]

沿搜索方向 \(p_k\) 移动步长 \(\alpha_k\)，得到新的近似解。

步骤 3：更新残差 \(r_{k+1}\)

\[r_{k+1} = r_k - \alpha_k A p_k \]

残差表示当前解与真实解的误差。由于 \(A x_{k+1} = A x_k + \alpha_k A p_k\)，代入 \(r_{k+1} = b - A x_{k+1}\) 可得上式。

步骤 4：计算方向更新系数 \(\beta_k\)

\[\beta_k = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k} \]

\(\beta_k\) 用于调整下一个搜索方向，使其与当前方向 \(p_k\) 共轭（A-正交）。

步骤 5：更新搜索方向 \(p_{k+1}\)

\[p_{k+1} = r_{k+1} + \beta_k p_k \]

新方向由当前残差和上一个方向的线性组合构成，确保 \(p_{k+1}\) 与所有之前的 \(p_i\) 共轭。

3. 终止条件

当残差 \(r_k\) 的范数小于预设阈值（如 \(\|r_k\| < 10^{-6}\)）时停止迭代。
对于 \(n\) 维问题，理论上最多 \(n\) 步即可得到精确解（忽略数值误差）。

4. 示例演示（简化计算）

考虑对称正定矩阵 \(A = \begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix}\)，\(b = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\)，初始解 \(x_0 = \begin{bmatrix} 0 \\ 0 \end{bmatrix}\)。

第 0 步：

\(r_0 = b - A x_0 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\)，\(p_0 = r_0\)。
\(\alpha_0 = \frac{r_0^T r_0}{p_0^T A p_0} = \frac{5}{p_0^T \begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix} p_0} = \frac{5}{1\cdot 4\cdot 1 + 1\cdot 1\cdot 2 + 2\cdot 1\cdot 1 + 2\cdot 3\cdot 2} = \frac{5}{25} = 0.2\)。
\(x_1 = x_0 + 0.2 p_0 = \begin{bmatrix} 0.2 \\ 0.4 \end{bmatrix}\)。
\(r_1 = r_0 - 0.2 A p_0 = \begin{bmatrix} 1 \\ 2 \end{bmatrix} - 0.2 \begin{bmatrix} 6 \\ 7 \end{bmatrix} = \begin{bmatrix} -0.2 \\ 0.6 \end{bmatrix}\)。
\(\beta_0 = \frac{r_1^T r_1}{r_0^T r_0} = \frac{0.4}{5} = 0.08\)。
\(p_1 = r_1 + 0.08 p_0 = \begin{bmatrix} -0.2 \\ 0.6 \end{bmatrix} + 0.08 \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} -0.12 \\ 0.76 \end{bmatrix}\)。

第 1 步：

重复上述过程，更新 \(x_2\)、\(r_2\)。最终在 2 步内得到精确解 \(x = \begin{bmatrix} 0.0909 \\ 0.6364 \end{bmatrix}\)。

5. 关键性质

共轭性：搜索方向 \(p_k\) 满足 \(p_i^T A p_j = 0\)（\(i \neq j\)）。
残差正交性：残差向量 \(r_k\) 两两正交（\(r_i^T r_j = 0\)）。
高效性：适用于大型稀疏矩阵，无需显式存储 \(A\)，只需计算矩阵-向量乘 \(A p_k\)。

通过以上步骤，共轭梯度法逐步逼近解，兼具理论有限步收敛性和实际数值稳定性。

共轭梯度法解对称正定线性方程组题目描述给定一个对称正定矩阵 \( A \in \mathbb{R}^{n \times n} \) 和向量 \( b \in \mathbb{R}^n \)，求解线性方程组 \( A x = b \)。要求使用共轭梯度法（Conjugate Gradient Method），并解释其逐步迭代过程。解题过程 1. 共轭梯度法的基本思想共轭梯度法是一种迭代算法，用于求解对称正定（SPD）线性方程组。它的核心思想是：在每一步迭代中，沿着一个共轭方向（A-正交方向）更新解向量 \( x \)，使得残差（误差）在每一步均减小。共轭方向满足：\( p_ i^T A p_ j = 0 \)（对 \( i \neq j \)），即方向向量两两关于 \( A \) 正交。 2. 算法步骤详解设初始解向量为 \( x_ 0 \)，初始残差 \( r_ 0 = b - A x_ 0 \)，初始搜索方向 \( p_ 0 = r_ 0 \)。迭代步骤如下（对 \( k = 0, 1, 2, \dots \) 直至收敛）：步骤 1：计算步长 \( \alpha_ k \) \[ \alpha_ k = \frac{r_ k^T r_ k}{p_ k^T A p_ k} \] 分子 \( r_ k^T r_ k \) 是当前残差的模长平方。分母 \( p_ k^T A p_ k \) 是搜索方向 \( p_ k \) 在 \( A \) 度量下的模长。 \( \alpha_ k \) 的作用是沿 \( p_ k \) 方向移动多远，使残差最小化。步骤 2：更新解向量 \( x_ {k+1} \) \[ x_ {k+1} = x_ k + \alpha_ k p_ k \] 沿搜索方向 \( p_ k \) 移动步长 \( \alpha_ k \)，得到新的近似解。步骤 3：更新残差 \( r_ {k+1} \) \[ r_ {k+1} = r_ k - \alpha_ k A p_ k \] 残差表示当前解与真实解的误差。由于 \( A x_ {k+1} = A x_ k + \alpha_ k A p_ k \)，代入 \( r_ {k+1} = b - A x_ {k+1} \) 可得上式。步骤 4：计算方向更新系数 \( \beta_ k \) \[ \beta_ k = \frac{r_ {k+1}^T r_ {k+1}}{r_ k^T r_ k} \] \( \beta_ k \) 用于调整下一个搜索方向，使其与当前方向 \( p_ k \) 共轭（A-正交）。步骤 5：更新搜索方向 \( p_ {k+1} \) \[ p_ {k+1} = r_ {k+1} + \beta_ k p_ k \] 新方向由当前残差和上一个方向的线性组合构成，确保 \( p_ {k+1} \) 与所有之前的 \( p_ i \) 共轭。 3. 终止条件当残差 \( r_ k \) 的范数小于预设阈值（如 \( \|r_ k\| < 10^{-6} \)）时停止迭代。对于 \( n \) 维问题，理论上最多 \( n \) 步即可得到精确解（忽略数值误差）。 4. 示例演示（简化计算）考虑对称正定矩阵 \( A = \begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix} \)，\( b = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \)，初始解 \( x_ 0 = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \)。第 0 步： \( r_ 0 = b - A x_ 0 = \begin{bmatrix} 1 \\ 2 \end{bmatrix} \)，\( p_ 0 = r_ 0 \)。 \( \alpha_ 0 = \frac{r_ 0^T r_ 0}{p_ 0^T A p_ 0} = \frac{5}{p_ 0^T \begin{bmatrix} 4 & 1 \\ 1 & 3 \end{bmatrix} p_ 0} = \frac{5}{1\cdot 4\cdot 1 + 1\cdot 1\cdot 2 + 2\cdot 1\cdot 1 + 2\cdot 3\cdot 2} = \frac{5}{25} = 0.2 \)。 \( x_ 1 = x_ 0 + 0.2 p_ 0 = \begin{bmatrix} 0.2 \\ 0.4 \end{bmatrix} \)。 \( r_ 1 = r_ 0 - 0.2 A p_ 0 = \begin{bmatrix} 1 \\ 2 \end{bmatrix} - 0.2 \begin{bmatrix} 6 \\ 7 \end{bmatrix} = \begin{bmatrix} -0.2 \\ 0.6 \end{bmatrix} \)。 \( \beta_ 0 = \frac{r_ 1^T r_ 1}{r_ 0^T r_ 0} = \frac{0.4}{5} = 0.08 \)。 \( p_ 1 = r_ 1 + 0.08 p_ 0 = \begin{bmatrix} -0.2 \\ 0.6 \end{bmatrix} + 0.08 \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} -0.12 \\ 0.76 \end{bmatrix} \)。第 1 步：重复上述过程，更新 \( x_ 2 \)、\( r_ 2 \)。最终在 2 步内得到精确解 \( x = \begin{bmatrix} 0.0909 \\ 0.6364 \end{bmatrix} \)。 5. 关键性质共轭性：搜索方向 \( p_ k \) 满足 \( p_ i^T A p_ j = 0 \)（\( i \neq j \)）。残差正交性：残差向量 \( r_ k \) 两两正交（\( r_ i^T r_ j = 0 \)）。高效性：适用于大型稀疏矩阵，无需显式存储 \( A \)，只需计算矩阵-向量乘 \( A p_ k \)。通过以上步骤，共轭梯度法逐步逼近解，兼具理论有限步收敛性和实际数值稳定性。