资源描述：
《数值方法 第三章_第四节_共轭梯度法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§4共轭梯度法本节介绍的共轭梯度法属变分方法的范围。我们先讨论与方程组等价的变分问题，再介绍解变分问题的方法，这要从比较直观的最速下降法开始。(I)与方程组等价的变分问题设对称正定，求解的方程组为其中.考虑二次泛函，定义为有如下的性质(1)对一切,(2)对一切,(3)设为的解，则而且对一切，有以上性质可以直接运算验证，其中用到了的对称性。35定理5.1设对称正定，则为的解的充分必要条件是满足。证明：设，由性质(3)和的正定性，.所以有。即使达到最小。反之，若有使达到最小，则。有，即因为的正定性，这只在
2、才能成立。□求，使取最小，这就是求解等价于方程组的变分问题。求解的方法一般是构造一个向量序列，使.(II)最速下降法最速下降法是求最小问题的一种简单直观的方法。它从出发寻找的极小点。从出发，先找一个是减小最快的方向，这就是负梯度方向，由性质(1)有其中是方程组对应于的剩余向量。如果，则是方程组的解。设，我们在中选择，使极小，35这称为沿方向的一维极小搜索。由性质(2)，令，解出。再由的正定性验证所以有。令，这就完成了一次迭代。其他各步类似，最速下降算法就是选取，对不难验证，相邻两次的搜索方向是正交的，
3、即定理：设为对称正定矩阵，分别为其最大，最小特征值，那么对于最速下降法有其中为的精确解，为迭代初值，。35(III)共轭梯度法从最速下降法收敛性知，当远大于时，，收敛相当慢。故在实际计算中，最速下降法不采用，但基本思想和做法非常重要！共轭梯度法就是在其基础上修改而成。最速下降法是从出发，依次沿各个方向采用一维极小搜索。共轭梯度法不再沿方向进行一维极小搜索，而且另找一组方向进行一维搜索。如果搜索方向已进行了次一维搜索，下一步要确定，再求解一维极小问题，再求解一维极小问题仿最速下降法，可令可以得到：。下一
4、个近似解,,。为讨论方便起见，令由下面来考虑取什么方向，开始取，一般时，的确定满足35（一维极小搜索）.（说明：对于，当线性无关，，此时。满足。）若，，。根据的性质有.上式中出现了“交叉项”，这样做是求的极小复杂化了。为了把极小问题分离，能分别对求极小。令即。上述对每一步都如此选择，由此引入定义。定义：设，对称正定，如果中向量组满足则称向量组为共轭的。由定义可推出，不含零向量的共轭向量是线性无关的。事实上用作内积，利用共轭有(由的正定性，)35线性无关。当时，共轭组为正交组，给出了一组线性无关的向量组
5、，可以按Gram-Schimidt正交华的方法得到对应的共轭向量组。取是共轭的，现考虑的解。设是前一步极小问题的解，即。而使，所以第一个问题，，其解为。第二个问题，。上式可化简：因为，故,。.上述过程中，取，共轭，与共轭。如果直接来确定与是共轭的，这样做法很困难，具体采用如下方法：取为的线性组合，35，利用来确定，.利用及上面推到的表达式,这样，在理论上已经给出了CG算法。任取；；对于，,(以后经常用)；；。对于具有下列性质。定理：(1)。（剩余向量构成正交组）35(1)。（为共轭向量组）。推论：用C
6、G法解n阶线性方程组（对称正定），不计舍入误差，那么最多计算n步便得方程组的精确解。CG算法任取；；对于,。；。在计算过程中，如果，则，计算停止；再如果，由于对称正定。我们已经证明，计算停止。实际计算中，由于舍入误差影响，不可能正交因此不会n步取得精确解，CG可以修改如下：任取；；35对于,如果，则输出，计算结果。否则。定理：设对称正定，其特征值，用CG方法求解k步有。对称正定，。。考虑到,令，那么有。35由此看出，当条件数大时，即方程组是病态的，共轭梯度法收敛慢。预处理共轭梯度法当 Ax=b的系数矩
7、阵Ａ的条件数cond(A)2>>1时，ＣＧ方法收敛很慢，为改进收敛速度一般采用预处理技巧。预处理首先应求一个预处理矩阵Ｍ，Ｍ应满足一些要求：1.求解Ｍｘ＝ｂ时应较为容易。其原因是在预处理的每步都要求解此方程组。2.Ｍ应在某种意义下接近于Ａ，并非奇异。3.一般称M-1Ax=b预处理方程组;Ｍ为预处理矩阵，亦称为左预处理。AM-1U=b,x≡M-1U称为右预处理。若M=MLMR，其中ML，MR为三角阵，此时预处理可以作如下处理：M-1LAM-1RU=b,x≡M-1RU35对于第三种情况特别适合于CG。A对
8、称正定，处理后希仍保持对称，正定，M=SST,S可逆Ax=bS-1AS-TU=S-1b,x=S-TU系数矩阵对称正定。令F=S-1AS-T,f=S-1bFU=f对此方程组的ＣＧ：任取U(0),令这一组公式还可以变换到原来变量令35再令PreconditionedCG任取对于k=0,1,……（解方程组）M,S选取：M对称，正定，M的cholesky分解M=LLT,可取S=L,35如果LLT≈A,那么有F=S-1AS-T≈L-1(LLT)L=I这样可以加快C
