CS205A Lecture 13 Conjugate gradients II; Formulation; preconditioning; and variants

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第十三讲,这一讲完整介绍了共轭梯度法。

首先回顾梯度下降的残差:

下面讨论$\vec r_{k+1}$和$\vec r_k$的关系。我们知道更新公式为

其中

那么$\vec r_{k+1}$计算方式如下:

特别的,在梯度下降法中,我们取

那么

递推上式得到如下命题:

命题10.3

其中

注意上述命题不能保证如下事实成立:

因为第$k$步的更新结果能会破坏前$k-1$次的结果。但是,如果找到$A$共轭向量组$\{\vec v_1,\ldots ,\vec v_n\}$,那么结合之前的讨论不难得到如下命题:

命题10.4

所以接下来只要讨论如何找到$A$共轭向量组即可。

生成$A$共轭方向

利用Gram-Schmidt的思路,不难得到最原始的做法:

不难看出该算法有如下性质:

这个算法有如下两个问题:

  1. 当迭代多次以后,$A^{k-1}\vec r_0​$趋近于$A​$最大特征值对应的特征向量,这使得投影的效果越来越差。
  2. 为了计算$\vec v_k$,我们需要存储$\vec v_1,\ldots ,\vec v_{k-1}$;因此每一轮比上一轮都需要更多的内存。

上述算法的第一步是将$A^{k-1}\vec r_0 $减去其在$\operatorname{span}\left\{\vec{v}_{1}, \ldots, \vec{v}_{k-1}\right\}$上的投影,结合(1),不难发现我们只要找到$\vec w$,使其满足如下条件即可

因为

所以结合(1),我们有

所以可以选择$\vec r_k$进行如上操作,于是得到第二个算法:

该算法解决了问题1,即不用计算$A^{k-1}\vec r_0$,但是内存问题似乎还没解决。事实上,该算法已经解决内存的问题,因为我们有如下命题:

命题10.5

证明:利用数学归纳法证明。

当$k=1$时,无需证明。

当$k>1$时,假设结论对$k’<k$成立,那么因为

所以我们有

如果$\ell <k-1$,那么由归纳假设,第一项为$0$。注意由(1)可得

由$\vec v_k$的构造($A$共轭),我们可得第二项为$0​$。

如果$\ell =k-1$,直接计算可得

由残差公式可得

和$\vec r_k​$做内积得到

由(1)可得

因为

结合命题10.4可得我们必然有

因为如果上式不成立,那么子空间存在一个方向可以减少$f ​$,因此

有了上述命题,我们可以对第二个算法的第一步进行化简:

将上述内容总结即可得到最终算法:

最后补充一个命题:

命题10.6

证明:由之前讨论可得

所以结论得证。

共轭梯度法分析

现在对上述算法稍作分析,由命题10.6可得

因此由$\vec v_k$的定义,可得

化简$\beta_k$可得

所以

最后补充证明

原因如下

将上述内容总结成如下算法:

收敛性

假设$\vec x’$为极值点,关于收敛性有如下结论:

其中

Preconditioning

我们知道,对于线性系统

如果$P$可逆,那么如下线性系统等价于原始线性系统

如果

那么新的系统比原始系统更好求解,这种条件下,称$P$为preconditioner。Preconditioner的想法很有吸引力,但是有如下两个问题:

  1. 如果$A$正定,但$PA$不一定正定。
  2. 我们需要$P$比$A^{-1}$更好计算。

CG with Preconditioning

假设Preconditioner $P$为正定对称矩阵,那么使用Cholesky分解,我们有

在这个假设下,我们有如下命题:

命题10.7

证明:首先考虑$E^{-1}AE^{-{\top} }$的奇异值,因为$E^{-1}AE^{-{\top} }$对称,所以奇异值等于特征值,所以讨论特征值即可。假设

注意

所以对(2)左乘$E^{-{\top} }​$得到

定义

那么有

所以$PA$特征值和$E^{-1}AE^{-{\top} }$的特征值相同,假设最大最小特征值为$\lambda_1,\lambda_2$,对应的特征向量为$\vec x _1,\vec x_2 $,那么

因此

最后一个等号是因为奇异值和条件数的关系。

上述事实告诉我们,如果我们求解

在条件数方面等价于求解

结合上述讨论,我们可以用如下方式近似求解$A\vec x=\vec b​$:

  1. 求解$E^{-1}AE^{-{\top} } \vec y =E^{-1}\vec b​$
  2. 求解$\vec x = E^{-\top} \vec y$

将这个步骤和CG结合得到如下算法,将$A$用$E^{-1}AE^{-{\top} } $替换:

如果定义

结合

我们可以将上述算法改写为:

常见的Preconditioners

比较常见Preconditioner为选择对角元或者用系数矩阵近似逆矩阵,具体的见讲义。

本文标题:CS205A Lecture 13 Conjugate gradients II; Formulation; preconditioning; and variants

文章作者:Doraemonzzz

发布时间:2019年04月30日 - 19:31:00

最后更新:2019年05月10日 - 15:52:06

原始链接:http://doraemonzzz.com/2019/04/30/CS205A Lecture 13 Conjugate gradients II; Formulation, preconditioning, and variants/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。