计算方法B.裴玉茹.06.线性方程组(3)

• PPT（线性方程组）

线性方程组

5. 共轭梯度方法

• 共轭梯度方法
  • 求解 $n\times n$ 正定线性方程组迭代方法
  • $n$ 步求解线性方程组（直接方法）
  • $x=x+tv$
    • 共轭梯度方向
  • 对矩阵进行预处理，只需大约 $n$ 步收敛
• 示意图
  • 绿色：梯度下降
  • 红色：共轭梯度下降

img

(1) 预备知识

定理 1

• 向量 $x^{\ast }$ 是正定线性方程组 $Ax=b$ 的解当且仅当 $x^{\ast }$ 最小化函数 $g(x)=x,Ax,-2x,b$
• 证明思路：$g(x+tv)$ ，偏导为 0 时的 $x$ 条件

算法

• 迭代算法如下
• 找到某个方向 $v^{(k)}$ ，然后最小化这个函数（求出 $t_k$ ）

• 如何确定 $v^{(k)}$

(2) 最速下降

• 每次的方向规定为负梯度方向
  • 最速下降方法对非线性方程组和优化问题有很好的应用
  • 但由于收敛速度慢，不适用于线性方程组
• 算法步骤

(3) 共轭梯度下降

• note
• 正定矩阵 $A$
  • $A-$正交条件

$$⟨v^{(i)},A{v}^{(j)}⟩=0,i\ne j$$

定理 1

• 共轭梯度方法定理

证明

• 直接展开证明即可

• 第 3 行到第 4 行：代入第 2 行的结果，利用 $A-$正交性
• 第 12 行：紫色部分全为 0

定理 2

• 共轭方向法的剩余向量 $r^{(k)}$ 满足 $⟨r^{(k)},v^{(j)}⟩=0$，$j=1,\cdots ,k$

$$\begin{array}{c}{r}^{(k)}=b-A{x}^{(k)}\\ r^{(k+1)}=r^{(k)}-t_{k+1}A{v}^{(k+1)}\end{array}$$

证明

• 初始方向是余项方向：$v^{(1)}=r^{(0)}$

定理 3

• 共轭方法中的余项 $r^{(k)}$ 满足 $⟨r^{(k)},r^{(j)}⟩=0$，$j=1,\cdots ,k-1$

证明

• 如何确定搜索方向 $v^{(k)}$，由如下式子决定（$s_{k-1}$ 用于调整至 $A-$正交条件）

$$v^{(k)}=r^{(k-1)}+s_{k-1}{v}^{(k-1)}$$

• 证明

共轭梯度算法如下

正交集证明

• 为什么 $v^{(k)}$ 和 $v^{(k-1)}$ 正交就可以推导得到正交集
• $j<k-1$

$$\begin{array}{rl}⟨A{v}^{(k)},v^{(j)}⟩& =⟨A{r}^{(k-1)},v^{(j)}⟩+s_{k-1}⟨A{v}^{(k-1)},v^{(j)}⟩\\ & =⟨A{r}^{(k-1)},v^{(j)}⟩\end{array}$$

• 而根据如下式子，根据 $A$ 正定，证毕

$$⟨r^{(k-1)},A{v}^{(j)}⟩=⟨r^{(k-1)},{\displaystyle \frac{r^{(j-1)}-r^{(j)}}{t^{(j)}}}⟩=0$$

• $r^{(k-1)}$ 和 $r^{(j-1)},r^{(j)}$ 正交，用到归纳 $\{v^{(1)},\cdots ,v^{(k-1)}\}$ 为正交集

(4) 预条件共轭梯度法

• note
• 降低 $A$ 条件数
• 选择一个非奇异条件矩阵 $C$，使 $\tilde{A}=C^{-1}A(C^{-1}{)}^T$ 条件更好

$$\begin{array}{c}\tilde{A}=C^{-1}A(C^{-1}{)}^T\\ \tilde{A}\tilde{x}=\tilde{b}\\ \mathrm{记}\mathrm{号}:\tilde{x}=C^{T}x,\tilde{b}=C^{-1}\tilde{b}\\ A\tilde{x}=C^{-1}Ax=C^{-1}b\end{array}$$

• $C^{-1}Ax=C^{-1}b$
• 具体算法：根据上面的算法求解 $\tilde{A}\tilde{x}=\tilde{b}$，过程中转化到解 $x$