解线性方程组的迭代方法精选课件.ppt

《解线性方程组的迭代方法精选课件.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代方法精选课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于解线性方程组的迭代方法第一页，本课件共有40页 定义定义:设设xk是是Rn上的向量序列，上的向量序列，又设又设x*（x1 1*，x 2*,，x n*)是是Rn上的向量上的向量.则称向量则称向量x*是向量序列是向量序列x k的极限的极限 ，若一个向量序列有极限若一个向量序列有极限,称这个向量序列是称这个向量序列是收敛的收敛的.向量序列的极限向量序列的极限如果如果向量序列向量序列x k收敛于向量收敛于向量x x*的充分必要的充分必要（i=1,2,=1,2,n）条件是条件是第二页，本课件共有40页矩阵序列的极限矩阵序列的极限定义定义:设设Ak是是 上的矩阵序列上的矩阵序列.若存在矩阵若存在矩阵

2、则称矩阵则称矩阵A 是矩阵序列是矩阵序列A k的极限，记为的极限，记为若一个矩阵序列有极限若一个矩阵序列有极限,称这个矩阵序列是称这个矩阵序列是收敛的收敛的.使得使得矩阵序列矩阵序列A k收敛于矩阵收敛于矩阵A 的充分必要的充分必要（i,j=1,2,=1,2,n）条件是条件是这里这里第三页，本课件共有40页证：证：依次取依次取 x 为为 ，其中，其中则则所以所以的充要条件是对任何的充要条件是对任何xRn，有，有设矩阵设矩阵，则，则 的的充要条件是充要条件是(A)0,记记 xTLTx=a,则有则有xTLTx=xT(D L)xxTAx=xT(D L LT)x=p a a=p 2a 0所以所以第二十

3、六页，本课件共有40页所以所以,迭代矩阵迭代矩阵BG-S的谱半径的谱半径(BG-S)1,从而当方程组从而当方程组 Ax=b的系数矩阵的系数矩阵A 是实对称正定矩阵时是实对称正定矩阵时,G-S 迭代法收敛迭代法收敛Remark:1)G-S迭代法的计算过程比迭代法的计算过程比Jacobi迭代法更简单。计算迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。过程中只需用一个一维数组存放迭代向量。2)G-S迭代不一定比迭代不一定比Jacobi迭代收敛快。迭代收敛快。3)Jacobi迭代和迭代和G-S迭代的收敛范围并不一致，即迭代的收敛范围并不一致，即Jacobi迭代收敛，迭代收敛，G-S迭代不一定

4、收敛，反之亦然。迭代不一定收敛，反之亦然。4)前面的定理前面的定理1、定理、定理2对于对于Jacobi迭代和迭代和G-S迭代都适迭代都适用。用。第二十七页，本课件共有40页(i=1,2,n;k=1,2,3,)四四 超松驰超松驰(SOR)(SOR)迭代法迭代法G-S迭代格式迭代格式第二十八页，本课件共有40页定理定理7.若若A 是对称正定矩阵是对称正定矩阵,则当则当02时时SOR迭代法解迭代法解方程组方程组 A x=b 是收敛的是收敛的定理定理8.若若A 是严格对角占优矩阵是严格对角占优矩阵,则当则当01时时SOR迭代迭代法解方程组法解方程组 A x=b 是收敛的是收敛的.迭代矩阵迭代矩阵：第二

5、十九页，本课件共有40页例例3 3：用松弛迭代法解方程组：用松弛迭代法解方程组：解解：松弛法迭代格式为：松弛法迭代格式为：第三十页，本课件共有40页 设设x,yR n,记记 (x,y)=xT y (x,y)=(y,x);(t x,y)=t(x,y);(x+y,z)=(x,z)+(y,z);(x,x)0,且且(x,x)=0 x=0;I 方程组问题方程组问题:Ax=bII II 极值问题极值问题:设设 A 是是n 阶对称阵阶对称阵 (Ax,y)=(x,Ay);(Ax，x)0,且且(Ax,x)=0 x=0 五五 最速下降法最速下降法第三十一页，本课件共有40页定理定理9.设设A=(aij)nn为为实

6、对称正定矩阵实对称正定矩阵,b,xR n,则则 x 使二次函数使二次函数 取极小值取极小值 x 是线性方程组是线性方程组 Ax=b的解。的解。证明证明:(1)u 是方程组是方程组 Ax=b 的解的解 Au b=0.任意任意 xR n,令令y=x u (Ay,y)0(2)设设 u 使使 f(x)取极小值取极小值.任取非零任取非零 xR n,任意任意 tR 第三十二页，本课件共有40页令令g(t)=f(u+t x),当当t=0时时,g(0)=f(u)达到极小值达到极小值,所所以以 ,即即(Au b,x)=0 Au b=0所以所以,u 是方程组是方程组 Ax=b 的解的解.最速下降法基本思想：最速下

7、降法基本思想：从初值点从初值点x(0)出发出发,以负梯度方向以负梯度方向 r 为搜索方向，选择步长为搜索方向，选择步长t1,得得 x(1)=x(0)+t1r,求函数求函数 f(x)极小值极小值在在 x 处，梯度方向是处，梯度方向是 f(x)增长最快方向；增长最快方向；负梯度方向是负梯度方向是 f(x)下降最快方向。下降最快方向。第三十三页，本课件共有40页梯度梯度:由由f(x)的表达式，易知对于任意的表达式，易知对于任意x(0)Rn,f(x)在在 x(0)处的负梯度方向为处的负梯度方向为记记 r(0)=b-Ax(0)，即，即r(0)的方向就是负梯度的方向，也的方向就是负梯度的方向，也是是 Ax

8、=b 的对应于的对应于x(0)的残向量。若的残向量。若r(0)=0，则，则x(0)即即为为Ax=b的解，若的解，若r(0)0，则从，则从x(0)出发，沿出发，沿r(0)方向方向的的x为：为：其中其中为参数，这里为参数，这里x 表明在表明在 r(0)方向上以方向上以 为步长，对为步长，对x(0)做了一次修正，为确定做了一次修正，为确定，使函数，使函数第三十四页，本课件共有40页取最小值。取最小值。令令解得：解得：又又所以，所以，=0 时时f(x)取最小值，令取最小值，令x(1)=x(0)+0 r(0)，从，从x(1)出发沿出发沿f(x)在在x(1)处的负梯度方向处的负梯度方向r(1)=b-Ax(

9、1)上求使上求使 f(x)的值最小的点，记为的值最小的点，记为x(2)，则，则第三十五页，本课件共有40页x(1)=x(0)+0 r(0)继续下去则得迭代格式：继续下去则得迭代格式：第三十六页，本课件共有40页结论结论1：第：第m+1次和第次和第m 次负梯度方向是正交的，即次负梯度方向是正交的，即 (r(m+1),r(m)=0 结论结论2：最速下降法有误差估计式：最速下降法有误差估计式 这里这里1 和和n 为为A 的最大和最小特征值，的最大和最小特征值，|A 定义为定义为注：注：由结论由结论2可以看出，当可以看出，当1 和和n 相差较大时，最速下相差较大时，最速下降法收敛缓慢。降法收敛缓慢。第

10、三十七页，本课件共有40页六六 共轭梯度法共轭梯度法A是是n阶对称正定矩阵阶对称正定矩阵,非零向量非零向量 p1,p2Rn n个向量个向量 p1,p2,pm 共轭概念共轭概念:(Api,pj)=0(ij;i,j=1,2,m)非零向量非零向量 p1,p2,pm Rn p1,p2,pm 关于关于A共轭共轭 p1,p2,pm 线性无关线性无关(Ap1,p2)=0 两个向量两个向量 p1,p2 共轭共轭:第三十八页，本课件共有40页共轭梯度法基本思想：共轭梯度法基本思想：由最速下降法中的下降向量由最速下降法中的下降向量r(k)构造出关于构造出关于A共轭向量组共轭向量组 p(k)，并以，并以 p(k)作为下作为下降方向来构造迭代算法。降方向来构造迭代算法。定理定理10.A是是n阶对称正定矩阵阶对称正定矩阵,p(1),p(2),p(n)是关于是关于A共轭的向量组共轭的向量组,任取任取 x(0)R n,计算计算tk=(b Ax(k-1),p(k)/(A p(k),p(k)x(k)=x(k 1)+tk p(k)(k=1,2,n)则有则有 Ax(n)=b。即最多迭代。即最多迭代 n 次次就可得到方程组的精就可得到方程组的精确解。确解。第三十九页，本课件共有40页感感谢谢大大家家观观看看第四十页，本课件共有40页