数值方法 第三章_第四节_共轭梯度法.docVIP

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