数值方法 第三章_第四节_共轭梯度法.doc_第1页
数值方法 第三章_第四节_共轭梯度法.doc_第2页
数值方法 第三章_第四节_共轭梯度法.doc_第3页
数值方法 第三章_第四节_共轭梯度法.doc_第4页
数值方法 第三章_第四节_共轭梯度法.doc_第5页
已阅读5页,还剩9页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论