数值分析2-2.ppt

《数值分析2-2.ppt》由会员分享，可在线阅读，更多相关《数值分析2-2.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 线性方程组求解线性方程组求解线线性定常迭代法及其收性定常迭代法及其收敛敛性性雅克比迭代法雅克比迭代法高斯高斯-赛赛德德尔尔迭代法迭代法超松弛迭代法超松弛迭代法共共轭轭梯度法梯度法1误差分析误差分析解线性方程组的计算结果不准确的原因：解线性方程组的计算结果不准确的原因：（1）计算方法不合理；）计算方法不合理；（2）线性方程组本身存在问题。）线性方程组本身存在问题。例例2.3 线性方程组线性方程组 的解是的解是而方程组而方程组 的解的解右端项微小的误差（右端项微小的误差（0.5 10-5），解完全不同。），解完全不同。2误差分析误差分析定义定义2.4 如果矩阵或常数项的微小变化，引起

2、方程如果矩阵或常数项的微小变化，引起方程组组Ax=b 解的巨大变化，则称此方程组为解的巨大变化，则称此方程组为“病态病态”方方程组程组，系数矩阵，系数矩阵 称为称为“病态病态”矩阵，否则称方程组矩阵，否则称方程组为为“良态良态”方程组方程组，系数矩阵为系数矩阵为“良态良态”矩阵矩阵。3研究方程组的研究方程组的系数矩阵系数矩阵A 和和右端向量右端向量b 的微小误差的微小误差（扰动扰动）对解的影响。设）对解的影响。设|.|为任何一种向量范为任何一种向量范数，矩阵范数是从属范数。数，矩阵范数是从属范数。误差分析误差分析设设 A非奇异，有微小扰动非奇异，有微小扰动 A，b有微小扰动有微小扰动 b，则，

3、则Ax=b 的扰动方程为的扰动方程为为了估计为了估计 x，对上式两端取范数，则有，对上式两端取范数，则有由由Ax=b 可得：可得：由于由于A非奇异，所以存在非奇异，所以存在A-1，4误差分析误差分析5误差分析误差分析定理定理2.1：设：设A 是非奇异阵，是非奇异阵，。若系数矩。若系数矩阵阵A 及右端项及右端项 b分别有微小误差分别有微小误差 A及及b，引起解，引起解x 的误差的误差x，当，当|A-1|A|4 105 19误差分析误差分析病态方程组的求解准则：病态方程组的求解准则：1）采用高精度的算术运算（如双倍字长），以改善）采用高精度的算术运算（如双倍字长），以改善和减轻病态矩阵的影响；和减

4、轻病态矩阵的影响；2）系数矩阵元素的数量级相差悬殊时，用直接法计）系数矩阵元素的数量级相差悬殊时，用直接法计算时，即使采用主元素消去法，求解过程中有效数字算时，即使采用主元素消去法，求解过程中有效数字也会严重损失。可以对方程组的系数矩阵进行预处理也会严重损失。可以对方程组的系数矩阵进行预处理来降低条件数。来降低条件数。比如，可适当选择非奇异对角阵比如，可适当选择非奇异对角阵C,D,使求解使求解 Ax=b的的问题转化为求解等价方程组问题转化为求解等价方程组10第二章第二章 线性方程组求解线性方程组求解线线性定常迭代法及其收性定常迭代法及其收敛敛性性雅克比迭代法雅克比迭代法高斯高斯-赛赛德德尔尔迭

5、代法迭代法超松弛迭代法超松弛迭代法共共轭轭梯度法梯度法11迭代法迭代法1.特别适合求解大型矩阵的方程组特别适合求解大型矩阵的方程组2.基本思想：构造一串收敛到解的序列，即建立一基本思想：构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则种从已有近似解计算新的近似解的规则迭代法的一般格式迭代法的一般格式12称为多步迭代法称为多步迭代法称为单步迭代法。再设称为单步迭代法。再设 是线性的，即是线性的，即式中式中 ，称，称为为单单步步线线性迭代法性迭代法 迭代法迭代法称为迭代矩阵。若称为迭代矩阵。若 、fk 与与k无关，即无关，即输入：输入：x(0),B,f;输出：输出：x.x=x(0

6、);while 不满足收敛条件不满足收敛条件 x=Bx+f;end13称为称为单步线性定常迭代法单步线性定常迭代法,或或一阶线性定常迭代法一阶线性定常迭代法算算法法：一一阶阶定定常常迭迭代代法法迭代法迭代法定义定义2.6 设设x(0),x(1),x(2),是是Rn中一向量序列中一向量序列x(k)，xRn是一个常向量。如果是一个常向量。如果则称向量序列则称向量序列收敛收敛于于x，记为，记为14定理定理2.2 Rn中的向量序列中的向量序列x(k)收敛于收敛于Rn中的向量中的向量x,当且仅当当且仅当 其中其中x(k)=(x1(k),x2(k),xn(k)T，x=(x1,x2,xn)T迭代法迭代法证证

7、 由定义由定义2.6，x(k)收敛于收敛于x，即，即而对任意而对任意 ，有，有 15由极限存在准则得由极限存在准则得即即迭代法迭代法成立，其中成立，其中x*为一确定的向量，它不依赖于为一确定的向量，它不依赖于x(0)的选的选取，则称迭代法是取，则称迭代法是收敛的收敛的，否则称，否则称迭代法发散迭代法发散。1.构造迭代格式构造迭代格式3.求出迭代序列求出迭代序列迭代解法基本步骤迭代解法基本步骤:2.代入初始向量代入初始向量定义定义2.7 如果对任意的初始向量如果对任意的初始向量 x(0)及及 f，迭代法得，迭代法得到的向量序列到的向量序列x(k)都有都有16迭代法迭代法同解方程组同解方程组:x=

8、Bx+f迭代格式迭代格式:x(k+1)=B x(k)+f初始解初始解x(0)线性方程组线性方程组 Ax=b解向量序列解向量序列x(k)B 迭代矩阵迭代矩阵 x(k)迭代序列迭代序列17迭代法迭代法18迭代格式迭代格式:x(k+1)=B x(k)+f 是否收敛？是否收敛？如果收敛，其收敛速度如何？如果收敛，其收敛速度如何？设准确解为设准确解为x*，则它满足方程，则它满足方程 x*=Bx*+f近似解的误差近似解的误差e(k)为为 e(k)=x(k)-x*e(k+1)=x(k+1)-x*=Bx(k)+f-Bx*+f=Be(k),(k=0,1,)递推有递推有 e(k)=Bke(0)要保证迭代收敛，也就

9、是要求要保证迭代收敛，也就是要求通常通常 e(0)0，所以必须要求，所以必须要求迭代法迭代法的收敛性的收敛性定理定理2.3 设设BRn n，则，则 （零矩阵）的（零矩阵）的充分必要条件是矩阵充分必要条件是矩阵B的谱半径的谱半径 。（此定理的严格证明，需使用矩阵的若当标准型此定理的严格证明，需使用矩阵的若当标准型）下面仅考虑矩阵下面仅考虑矩阵B可对角化的简化情况：可对角化的简化情况：设设 B=XX-1其中其中 是是B 的特征值组成的对角阵的特征值组成的对角阵则则 B k=XkX-1的所有的所有对角元对角元小于小于119迭代法迭代法的收敛性的收敛性定理定理2.4 设设I-B为非奇异矩阵，对任意的初

10、始向量为非奇异矩阵，对任意的初始向量x(0)和右端项和右端项 f，由迭代格式，由迭代格式x(k+1)=Bx(k)+f (k=0,1,2,)产生的向量序列产生的向量序列x(k)收敛的充要条件是收敛的充要条件是 ，且序列且序列x(k)的极限的极限x*必定是方程必定是方程 x=Bx+f 的唯一解。的唯一解。（由解向量序列收敛，推导迭代矩阵谱半径小于由解向量序列收敛，推导迭代矩阵谱半径小于1)设设 ，则，则x*=B x*+f 证：（必要性）因为证：（必要性）因为 I-B 为非奇异矩阵，所以为非奇异矩阵，所以x=Bx+f 一定有唯一解存在，设为一定有唯一解存在，设为 x*。（。（用反证法，假设有两用反证

11、法，假设有两个解，推出矛盾个解，推出矛盾）20由此，有由此，有 x(k)-x*=B x(k-1)+f -(B x*+f)=Bk(x(0)-x*)迭代法迭代法的收敛性的收敛性于是于是 因为因为x(0)为任意为任意n维向量，因此上式成立必须维向量，因此上式成立必须 由定理由定理2.3，即得，即得 。21迭代法迭代法的收敛性的收敛性(充分性充分性)若若(B)1，则，则=1不是不是B的特征值，因而的特征值，因而有有|I-B|0,即即I-B非奇异。于是对任意非奇异。于是对任意n维向量维向量 f，方程组方程组(I-B)x=f 有唯一解有唯一解，记为，记为 x*，即，即x*=B x*+f 并且（由定理并且（

12、由定理2.3知，知，(B)1 时）时）又因为又因为 x(k)-x*=B x(k-1)+f -(B x*+f)=Bk(x(0)-x*)所以，对任意初始向量所以，对任意初始向量x(0)，都有，都有即由迭代公式产生的向量序列即由迭代公式产生的向量序列x(k)收敛收敛22迭代法迭代法的收敛性的收敛性对定理对定理2.4的说明：的说明：1）定理的结论是对任意初值）定理的结论是对任意初值x(0)，迭代法都收敛，迭代法都收敛，即它是一种全局收敛的概念。即它是一种全局收敛的概念。2）定理的一个前提条件是）定理的一个前提条件是:I-B 为非奇异矩阵，这为非奇异矩阵，这非常重要。它反映了迭代法是通过对方程非常重要。

13、它反映了迭代法是通过对方程Ax=b进进行等价变换得到的，而行等价变换得到的，而A是非奇异的。是非奇异的。3）定理给出了充要条件，因此可以通过迭代矩阵）定理给出了充要条件，因此可以通过迭代矩阵的特征值（谱半径）判断一阶定常迭代法的收敛的特征值（谱半径）判断一阶定常迭代法的收敛性。性。2324定理定理2.5 (充分条件充分条件)对方程组对方程组 x=Bx+f,若某种算子若某种算子范数范数|B|1,则则（2）（3）|x(k)x*|B|k|(x(0)x*)|迭代法迭代法（1）对任意初始向量）对任意初始向量x(0)Rn,此一阶定常迭代格此一阶定常迭代格式收敛于式收敛于 x*，且有，且有迭代序列收敛迭代序

14、列收敛k次迭代之后次迭代之后误差估计误差估计首次迭代之后首次迭代之后估计迭代次数估计迭代次数25迭代法迭代法|B|0.0001 er=0;k=k+1;for i=1:3 t=x(i);x(i)=0;s=A(i,:)*x;x(i)=t;y(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-y(i),er);end x=yend 1.0000 2.0000 3.0000k=11%评估最大误差评估最大误差%右端第右端第i i项不累加，先暂项不累加，先暂存在存在t t中，再将其清零中，再将其清零36 高斯赛德尔高斯赛德尔(Gauss-Seidel)迭代法迭代法雅可比迭代格式：雅可比

15、迭代格式：经典经典迭代法迭代法37经典经典迭代法迭代法高斯赛德尔高斯赛德尔迭代法迭代法J-迭代法需要迭代法需要2组单元分别存放组单元分别存放x(k)和和x(k+1)，而，而 G-S迭代法只需迭代法只需1组单元。组单元。38经典经典迭代法迭代法(D-L)x(k+1)=U x(k)+bGf其矩阵形式：其矩阵形式：x(k+1)=D-1(b+L x(k+1)+U x(k)Dx(k+1)=L x(k+1)+Ux(k)+b39经典经典迭代法迭代法例例2.6 用用G-S迭代法解方程组迭代法解方程组解解40经典经典迭代法迭代法kx1(k)x2(k)x3(k)000010.30001.56002.684020.

16、88041.94452.953930.98431.99232.993840.99781.99892.999150.99971.99992.999961.00002.00003.000071.00002.00003.000041经典经典迭代法迭代法A=10 2 1;-2 10 1;-1 2 5;b=3;15;10;x=0;0;0;er=1;k=0;while er0.0001 er=0;k=k+1;for i=1:3 t=x(i);x(i)=0;s=A(i,:)*x;x(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);end xend 1.0000 2.000

17、0 3.0000k=742经典经典迭代法迭代法超松弛超松弛(SOR)迭代法迭代法SOR(Successive Over Relaxation)迭代法是迭代法是G-S迭代法的迭代法的一种修正，其基本思想：一种修正，其基本思想：设已知设已知 x(k)及已计算的及已计算的x(k+1)的分量的分量xj(k+1)(j=1,2,i-1)(1)首先用首先用G-S迭代法定义辅助量迭代法定义辅助量(2)再由再由xi(k)与与 加权平均定义加权平均定义xi(k+1)，即，即43经典经典迭代法迭代法即即称为松弛因子，当称为松弛因子，当 1时称为超松弛法时称为超松弛法（SOR）。）。写成矩阵形式写成矩阵形式x(k+1

18、)=(1-)x(k)+D-1(b+Lx(k+1)+Ux(k)x(k+1)=(1-)I+D-1U x(k)+D-1Lx(k+1)+D-1bDx(k+1)=(1-)DI+U x(k)+Lx(k+1)+b44左乘左乘D：经典经典迭代法迭代法(D-L)x(k+1)=(1-)DI+Ux(k)+bx(k+1)=(D-L)-1(1-)DI+Ux(k)+(D-L)-1bLf例例2.7 用用SOR迭代法解方程组迭代法解方程组45移项：移项：经典经典迭代法迭代法解解 迭代公式为迭代公式为 46A=10 2 1;-2 10 1;-1 2 5;b=3;15;10;x=0;0;0;er=1;k=0;w=1.05;whi

19、le er0.0001 er=0;k=k+1;for i=1:3 t=x(i);x(i)=0;s=A(i,:)*x;x(i)=(1-w)*t+w*(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);end xend经典经典迭代法迭代法 1.0000 2.0000 3.0000k=547经典经典迭代法迭代法松弛因子对迭代收敛速度的影响松弛因子对迭代收敛速度的影响（满足（满足|x(k)-x(k-1)|0.0001）k1.0071.0551.1571.2591.35111.45141.552048迭代法迭代法的收敛性的收敛性推论推论 SOR法收敛的必要条件是法收敛的必要条件

20、是1 2。例例2.8:研究用研究用J-和和G-S迭代法解方程组迭代法解方程组 Ax=b 敛散敛散性。性。解：解：（1）J-迭代法的迭代矩阵为迭代法的迭代矩阵为J=D-1(L+U)49迭代法迭代法的收敛性的收敛性其特征方程为其特征方程为|I-D-1(L+U)|=0 或或|D-(L+U)|=0 由已知由已知|D-(L+U)|=3=0 得得1=2=3=0，故，故(J)1，因此因此G-S迭代法发散。迭代法发散。J-和和G-S迭代法的迭代法的特点：特点：(1)两种方法可能同时收敛，或同时发散，或一个两种方法可能同时收敛，或同时发散，或一个收敛，另一个发散。收敛，另一个发散。(2)二者同时收敛时，二者同时

21、收敛时，G-S迭代法收敛更快。迭代法收敛更快。51迭代法迭代法的收敛性的收敛性特殊矩阵迭代法特殊矩阵迭代法(Ax=b)的收敛性：的收敛性：(1)若若A为严格对角占优阵，则为严格对角占优阵，则J-迭代法和迭代法和G-S迭代法迭代法均收敛；均收敛；(2)若若A为严格对角占优阵，为严格对角占优阵，0 1，则，则SOR迭代法迭代法收敛；收敛；(3)若若A为对称正定阵，为对称正定阵，则则SOR迭代法收敛的充要条迭代法收敛的充要条件是件是0 2(包括了包括了G-S迭代法迭代法)。52共轭梯度法共轭梯度法经经典迭代法都是通典迭代法都是通过对过对矩矩阵阵的的简单简单分裂得到一分裂得到一阶阶定常迭代公式。定常迭

22、代公式。对对一般的矩一般的矩阵阵无法保无法保证证收收敛敛性，性，即使收即使收敛敛，其收，其收敛敛速度也可能很慢。速度也可能很慢。20世世纪纪70年代年代发发展起来的展起来的Krylov子空子空间间迭代法在迭代法在一定程度上弥一定程度上弥补补了了经经典迭代法的不足典迭代法的不足泛函泛函函数的函数（更广泛的函数）函数的函数（更广泛的函数）变分变分求解泛函极小值的问题求解泛函极小值的问题由由变变分原理分原理导导出的共出的共轭轭梯度法，是一种重要的梯度法，是一种重要的Krylov子空子空间间迭代法迭代法53共轭梯度法共轭梯度法初等初等变变分原理分原理为了问题描述方便，引入内积符号。设为了问题描述方便，

23、引入内积符号。设x和和y的内积记为的内积记为,A是是n阶对称正定矩阵，内积有一些重要性质阶对称正定矩阵，内积有一些重要性质，且，且 的充要条件是的充要条件是 x=0.定定义义2.16 设设A是是n阶对阶对称正定矩称正定矩阵阵，对对两个非零向两个非零向量量 ，若，若 ，则则称向量称向量 p1,p2关关于矩于矩阵阵A共共轭轭。易证：共轭向量线性无关易证：共轭向量线性无关5455共轭梯度法共轭梯度法共轭梯度法共轭梯度法设线设线性方程性方程组为组为 Ax=b其中其中A是是n阶实对阶实对称正定矩称正定矩阵阵。其求解可以与一个其求解可以与一个多元二次函数的极小值点相联系，多元二次函数的极小值点相联系，这就

24、是这就是简单变分原理简单变分原理。如果如果A是是对对称正定矩称正定矩阵阵，构造二次函数，构造二次函数下面的定理说明了线性方程组求解问题与二次函数下面的定理说明了线性方程组求解问题与二次函数极小值问题的等价关系，通常称为极小值问题的等价关系，通常称为初等变分原理初等变分原理。56共轭梯度法共轭梯度法定理定理2.6 ：设：设 为实对称正定矩阵，为实对称正定矩阵，,则则x使得二次函数使得二次函数取极小值的充要条件是取极小值的充要条件是 x是线性方程组是线性方程组 Ax=b 的解。的解。（具体的证明过程见讲义）（具体的证明过程见讲义）57共轭梯度法共轭梯度法最速下降法最速下降法下面讨论如何从某一给定的

25、初始近似下面讨论如何从某一给定的初始近似 x0 出发，来出发，来求求H(x)的极小值点的极小值点 x*假设沿方向向量假设沿方向向量 p0搜索下一个点搜索下一个点 x1使得使得 x1为该方向的最小值点，即为该方向的最小值点，即然后从然后从 x1出发，选定一个搜索方向出发，选定一个搜索方向 p1，搜索下一，搜索下一个最小值点个最小值点 x2，即，即58共轭梯度法共轭梯度法逐步搜索，得到一系列多维空间的点逐步搜索，得到一系列多维空间的点 x0,x1,x2,逐步逼近逐步逼近 H(x)在全空间上的最小值点在全空间上的最小值点x*，即方程，即方程组组 Ax=b 的解的解迭代计算过程迭代计算过程关键：确定关

26、键：确定搜索方向搜索方向pk和和搜索步长搜索步长k如何确定搜索步长？如何确定搜索步长？假设从假设从xk出发，已确定搜索方向为出发，已确定搜索方向为pk，令，令则搜索步长则搜索步长 k 是使上式取最小值的是使上式取最小值的 值值59共轭梯度法共轭梯度法将将代入代入有有其中其中 为方程组为方程组Ax=b 的残差向量的残差向量函数函数 f()为简单的一元二次函数，且矩阵为简单的一元二次函数，且矩阵A对称对称正定，保证了正定，保证了 60共轭梯度法共轭梯度法不同的方法采用不同的策略来确定搜索方向不同的方法采用不同的策略来确定搜索方向最速下降法的策略是：沿函数最速下降法的策略是：沿函数 H(x)的负梯度

27、方向的负梯度方向进行搜索进行搜索函数函数 H(x)的负梯度方向的负梯度方向(rk)就是等值线的法向就是等值线的法向此外，还可证明，在每步搜索的终点处，搜索方此外，还可证明，在每步搜索的终点处，搜索方向垂直于等值线的法向，即：向垂直于等值线的法向，即：61易证，易证，f()有唯一的最小值。令有唯一的最小值。令f()=0，得对应，得对应的的 值为值为由于最速下降法的搜索方向沿着当前点的等值线由于最速下降法的搜索方向沿着当前点的等值线法向，因此在搜索过程中，相邻两步的搜索方向法向，因此在搜索过程中，相邻两步的搜索方向总是相互垂直的，即总是相互垂直的，即将将 代入搜索步长公式代入搜索步长公式共轭梯度法

28、共轭梯度法可得可得最速下降法最速下降法搜索搜索步长步长的计算公式为：的计算公式为：62最速下降法最速下降法算法算法共轭梯度法共轭梯度法输入：输入：x,A,b;输出输出:x.r=b-Ax;while 不满足判停准则不满足判停准则 x=x+r r=r Ar%end 63例例2.9：根据最速下降法的算法，写出求解线性：根据最速下降法的算法，写出求解线性方程组方程组 Ax=b 的过程，其中：的过程，其中：共轭梯度法共轭梯度法64解：首先判断矩阵解：首先判断矩阵A对称正定。对称正定。假设取初始解为假设取初始解为 ，计算残差，计算残差迭代第一步，为计算迭代第一步，为计算 ，首先计算，首先计算则：则：共轭梯

29、度法共轭梯度法65因此有因此有采用相似的步骤进行后续计算，可依次得到采用相似的步骤进行后续计算，可依次得到66共轭梯度法共轭梯度法kx(1)x(2)10.08-0.613321.0044-2.000031.5221-1.654941.7522-2.000051.8811-1.914161.9383-2.000071.9704-1.978681.9847-2.000091.9926-1.9947101.9962-2.0000准确值：准确值：x=2,-2T最速下降法的特点：最速下降法的特点：u每个迭代步主要是做矩阵每个迭代步主要是做矩阵 A 和向量和向量 r 的乘法的乘法u若若A为稀疏矩阵，只需要

30、遍历矩阵非零元，并且为稀疏矩阵，只需要遍历矩阵非零元，并且算法不改变原始矩阵算法不改变原始矩阵Au迭代过程中，向量迭代过程中，向量 和和 r 不断变化，因此前后两不断变化，因此前后两个迭代解之间不满足一种固定的递推公式（个迭代解之间不满足一种固定的递推公式（与经典与经典迭代法不同迭代法不同）u由于多元二次函数由于多元二次函数 H(x)是凸函数，所以一定存在是凸函数，所以一定存在唯一的最小值点。即：当唯一的最小值点。即：当矩阵矩阵A对称正定对称正定时，最速时，最速下降法一定下降法一定收敛收敛共轭梯度法共轭梯度法67最速下降法的缺点：最速下降法的缺点：负梯度方向虽然从局部来看是最佳的搜索方向，而且

31、负梯度方向虽然从局部来看是最佳的搜索方向，而且每步都在该方向上使每步都在该方向上使 H(x)达到最小，但并没有在全达到最小，但并没有在全局上使局上使H(x)最小化。最小化。结果：收敛速度很慢结果：收敛速度很慢改进为改进为共轭梯度法共轭梯度法(-CG)共轭梯度法共轭梯度法(Conjugate Gradient)算法原理算法原理：给定初始向量：给定初始向量 x0，第一步仍选负梯度方向，第一步仍选负梯度方向为搜索方向，即为搜索方向，即 ，于是有，于是有68将该平面记为：将该平面记为：共轭梯度法共轭梯度法设设要求出要求出 的极小值，以及它对应的的极小值，以及它对应的 值值则应计算则应计算 f 的偏导数

32、，并令其为零：的偏导数，并令其为零：69对第对第k+1步步 ，搜索方向不仅仅考虑，搜索方向不仅仅考虑 rk，而是在，而是在过点过点 xk，由向量，由向量 rk和和 pk-1 所张成的平面内寻找函数所张成的平面内寻找函数 H(x)的最小值的最小值共轭梯度法共轭梯度法即即设要求的极小值点为设要求的极小值点为 ：若若 ,有有 ，可取新的搜索方向为，可取新的搜索方向为70它是在上述二维平面中的最佳搜索方向，且搜索步长它是在上述二维平面中的最佳搜索方向，且搜索步长为为 。此处不直接推导。此处不直接推导 的计算公式，而是先确定的计算公式，而是先确定搜索方向搜索方向pk.(rk系数为系数为1)令令 ，由前述

33、第二个方程，由前述第二个方程 共轭梯度法共轭梯度法可得：可得：所以最佳搜索方向为所以最佳搜索方向为且易证且易证即前后两步搜索方向是即前后两步搜索方向是 A共轭共轭（或（或A正交正交）的）的71利用前面的公式利用前面的公式 即可确定搜索步长即可确定搜索步长则下一个迭代解为则下一个迭代解为共共轭轭梯梯度度法法算算法法共轭梯度法共轭梯度法输入输入:x0,A,b;输出：输出：xk.r0=b Ax0;p0=r0;k=0;while 不满足判停准则不满足判停准则 rk+1=rk Apk;k=k+1;end72计算一次矩阵向计算一次矩阵向量乘法，三次向量乘法，三次向量乘积量乘积73共轭梯度法共轭梯度法例例2

34、.10：根据共轭梯度算法，写出求解线性方程组：根据共轭梯度算法，写出求解线性方程组Ax=b的过程，其中的过程，其中解：同样假设取初始解为解：同样假设取初始解为 ，然后计算出，然后计算出 ，算法执行过程如下表，算法执行过程如下表kApkxk+1rk+1pk+1052,72T0.17330.08,-0.6133T2.9867,-4.48T0.13944.6592,-3.365T17.2476,-10.8715T0.41212,-2T二维问题，两步计算出准确解二维问题，两步计算出准确解74共轭梯度法共轭梯度法每迭代一步，产生每迭代一步，产生3个向量个向量 xk,rk,pk，分别称为近，分别称为近似解

35、向量、残差向量和搜索方向向量似解向量、残差向量和搜索方向向量共轭梯度法有如下特点：共轭梯度法有如下特点：1），其中，其中 一般称为一般称为Krylov子空间，记为子空间，记为 (A,r0)；2）xk+1不但在向量不但在向量rk和和pk-1所张成的平面上使所张成的平面上使 H(x)最最小，而且在超平面小，而且在超平面x0+(A,r0)上使上使H(x)最小；最小；3）搜索方向向量间相互）搜索方向向量间相互 A 共轭（正交），即共轭（正交），即说明若不考虑数值说明若不考虑数值误差，经过误差，经过n次迭代次迭代后的解为准确解后的解为准确解反映了共轭梯度法反映了共轭梯度法的名称由来的名称由来75共轭梯度

36、法共轭梯度法4）残差向量相互正交，即：）残差向量相互正交，即：5）搜索方向向量与残差向量相互正交，即：）搜索方向向量与残差向量相互正交，即：6）在超平面）在超平面x0+(A,r0)上的所有点中，近似解上的所有点中，近似解xk的误差范数最小，即：的误差范数最小，即：其中其中 x*表示方程表示方程 Ax=b 的准确解，而的准确解，而|A是由矩是由矩阵阵A定义的向量范数，定义的向量范数，。76共轭梯度法共轭梯度法由上述特点，可以改由上述特点，可以改写计算写计算和和的公式，的公式，由由改写为改写为实用的共轭梯度法实用的共轭梯度法输入输入:x0,A,b;输出：输出：xk.r0=b Ax0;p0=r0;k

37、=0;while 不满足判停准则不满足判停准则 rk+1=rk Apk;k=k+1;end计算一次矩阵向量乘计算一次矩阵向量乘法，两次向量内积法，两次向量内积77共轭梯度法共轭梯度法对于对于n阶对称正定线性方程组，理论上，共轭梯度阶对称正定线性方程组，理论上，共轭梯度法经过法经过n次迭代后，必定收敛到准确解。次迭代后，必定收敛到准确解。优点：优点：克服了最速下降法和其它迭代法收敛速度可克服了最速下降法和其它迭代法收敛速度可能很慢的缺点，是一种能很慢的缺点，是一种具有迭代法形式的直接法具有迭代法形式的直接法为什么共轭梯度法经常被当作迭代方法？为什么共轭梯度法经常被当作迭代方法？每一步可以给出一个

38、近似解。且随着计算的进行，每一步可以给出一个近似解。且随着计算的进行，残差残差rk的范数在减小，的范数在减小，Axk越来越接近于越来越接近于 b通过监控残差通过监控残差rk，可以求出一个足够好的解，以避，可以求出一个足够好的解，以避免完成所有的免完成所有的n步步当当A的条件数接近于的条件数接近于1时，收敛非常迅速时，收敛非常迅速共轭梯度法共轭梯度法缺点：缺点：随着迭代步的增加，舍入误差很严重，尤其随着迭代步的增加，舍入误差很严重，尤其是当是当A是病态矩阵时。是病态矩阵时。此时，共轭梯度法比不上选主元的高斯消去法此时，共轭梯度法比不上选主元的高斯消去法解决办法：解决办法：预条件技术预条件技术(p

39、reconditioning)与共轭梯度与共轭梯度法结合法结合高斯消去法必须执行完毕才能给出准确解高斯消去法必须执行完毕才能给出准确解78其中，其中，79共轭梯度法共轭梯度法且且 Mz=y 比较容易求解比较容易求解还要保证系数矩阵对称正定还要保证系数矩阵对称正定通常要先对通常要先对 对称正定矩阵对称正定矩阵 M 做做Cholesky矩阵分解矩阵分解 M=LLT其中其中L是下三角矩阵。然后对是下三角矩阵。然后对L-1AL-T应用共轭梯度法应用共轭梯度法M-1Ax=M-1b其中矩阵其中矩阵M-1近似等于近似等于A-1，M-1A就会比较良态就会比较良态用矩阵用矩阵M-1乘以乘以A，然后求解等价方程，

40、然后求解等价方程预条件技术的一种基本做法：预条件技术的一种基本做法：预预条条件件共共轭轭梯梯度度法法算算法法共轭梯度法共轭梯度法80输入输入:x,A,b,M;输出：输出：x.r=b Ax;p=M-1r;z=p;%z=M-1rwhile 不满足判停准则不满足判停准则%搜索步长搜索步长%更新解更新解%上一个残差上一个残差结结果果 r=r Ap;%更新残差更新残差 z=M-1r;%新的搜索方向新的搜索方向end81小结小结三种经典迭代法：雅克比迭代法、高斯三种经典迭代法：雅克比迭代法、高斯-塞塞德尔迭代法、超松弛迭代法，迭代格式的特德尔迭代法、超松弛迭代法，迭代格式的特点、收敛条件点、收敛条件共轭梯度法的特点、应用范围共轭梯度法的特点、应用范围828.设矩阵设矩阵 A 为实对称正定阵，为实对称正定阵，x*为方程为方程 Ax=b 的准的准确解。试证明：确解。试证明：x*为为 的唯一最的唯一最小值点，即对小值点，即对习题习题讲义第二章习题二：讲义第二章习题二：2,4,7其中：其中：4.(2)：编程计算，给出程序和计算结果：编程计算，给出程序和计算结果