《解线性方程组的迭代方法课件.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代方法课件.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、解线性方程组的迭代方法第1页，此课件共37页哦 定义定义:设设xk是是Rn上的向量序列，上的向量序列，又设又设x*（x1 1*，x 2*,，x n*)是是Rn上的向量上的向量.则称向量则称向量x*是向量序列是向量序列x k的极限的极限 ，若一个向量序列有极限若一个向量序列有极限,称这个向量序列是称这个向量序列是收敛的收敛的.向量序列的极限向量序列的极限如果如果向量序列向量序列x k收敛于向量收敛于向量x x*的充分必要的充分必要（i=1,2,=1,2,n）条件是条件是第2页，此课件共37页哦矩阵序列的极限矩阵序列的极限定义定义:设设Ak是是 上的矩阵序列上的矩阵序列.若存在矩阵若存在矩阵 则称
2、矩阵则称矩阵A 是矩阵序列是矩阵序列A k的极限，记为的极限，记为若一个矩阵序列有极限若一个矩阵序列有极限,称这个矩阵序列是称这个矩阵序列是收敛的收敛的.使得使得矩阵序列矩阵序列A k收敛于矩阵收敛于矩阵A 的充分必要的充分必要（i,j=1,2,=1,2,n）条件是条件是这里这里第3页，此课件共37页哦证：证：依次取依次取 x 为为 ，其中，其中则则所以所以的充要条件是对任何的充要条件是对任何xRn，有，有设矩阵设矩阵，则，则 的的充要条件是充要条件是(A)0,记记 xTLTx=a,则有则有xTLTx=xT(D L)xxTAx=xT(D L LT)x=p a a=p 2a 0所以所以第26页，
3、此课件共37页哦所以所以,迭代矩阵迭代矩阵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迭代都适用。迭代都适用。第27页，此课件共37页哦(i=1,2,n;k=1,2,3,)四四 超松驰超松驰(SOR)(SOR)迭代法迭代法G-S迭代格式迭代格式第28页，此课件共37页哦定理定理7.若若A 是对称正定矩阵是对称正定矩阵,则当则当02时时SOR迭代法解方迭代法解方程组程组 A x=b 是收敛的是收敛的定理定理8.若若A 是严格对角占优矩阵是严格对角占优矩阵,则当则当01时时SOR迭代迭代法解方程组法解方程组 A x=b 是收敛的是收敛的.迭代矩阵迭代矩阵：第29页，此课
5、件共37页哦例例3 3：用松弛迭代法解方程组：用松弛迭代法解方程组：解解：松弛法迭代格式为：松弛法迭代格式为：第30页，此课件共37页哦 设设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 五五 最速下降法最速下降法第31页，此课件共37页哦定理定理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 第32页，此课件共37页哦令令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)下降最快方向。下降最快方向。第33页，此课件共37页哦梯度梯度:由由f(x)的表达式，易知对于任意的表达式，易知对于任意x(0)Rn,f(x)在在 x(0)处的负梯度方向为处的负梯度方向为记记 r(0)=b-Ax(0)，即，即r(0)的方向就是负梯度的方向，也的方向就是负梯度的方向，也是是 Ax=b 的对应于的对
8、应于x(0)的残向量。若的残向量。若r(0)=0，则，则x(0)即即为为Ax=b的解，若的解，若r(0)0，则从，则从x(0)出发，沿出发，沿r(0)方向方向的的x为：为：其中其中为参数，这里为参数，这里x 表明在表明在 r(0)方向上以方向上以 为步长，对为步长，对x(0)做了一次修正，为确定做了一次修正，为确定，使函数，使函数第34页，此课件共37页哦取最小值。取最小值。令令解得：解得：又又所以，所以，=0 时时f(x)取最小值，令取最小值，令x(1)=x(0)+0 r(0)，从，从x(1)出出发沿发沿f(x)在在x(1)处的负梯度方向处的负梯度方向r(1)=b-Ax(1)上求使上求使 f
9、(x)的的值最小的点，记为值最小的点，记为x(2)，则，则第35页，此课件共37页哦x(1)=x(0)+0 r(0)继续下去则得迭代格式：继续下去则得迭代格式：第36页，此课件共37页哦结论结论1：第：第m+1次和第次和第m 次负梯度方向是正交的，即次负梯度方向是正交的，即 (r(m+1),r(m)=0 结论结论2：最速下降法有误差估计式：最速下降法有误差估计式 这里这里1 和和n 为为A 的最大和最小特征值，的最大和最小特征值，|A 定义为定义为注：注：由结论由结论2可以看出，当可以看出，当1 和和n 相差较大时，最速下相差较大时，最速下降法收敛缓慢。降法收敛缓慢。第37页，此课件共37页哦