计算方法 线性方程组的迭代解法精选PPT.ppt

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

1、计算方法 线性方程组的迭代解法第1页，此课件共50页哦三、小结三、小结 二、线性方程组的解法二、线性方程组的解法一、线性方程组有解的判定条件一、线性方程组有解的判定条件回顾回顾线性代数线性代数中线性方程组的解法中线性方程组的解法第2页，此课件共50页哦一、线性方程组有解的判定条件一、线性方程组有解的判定条件一、线性方程组有解的判定条件定理定理4 n 元线性方程组元线性方程组Ax=b(i)无解的充分必要条件是无解的充分必要条件是R(A)R(A,b);(ii)有唯一解的充分必要条件是有唯一解的充分必要条件是R(A)=R(A,b)=n;(iii)有无限多解的充分必要条件是有无限多解的充分必要条件是R

2、(A)=R(A,b)n.当R(A)=R(B)=rn时，n元线性方程组可由含有n-r个参数的解来表示，这是线性方程组的通解。第3页，此课件共50页哦定理定理定理5 线性方程组线性方程组Ax=b有解的充分必要条件是有解的充分必要条件是R(A)=R(A,b).定理定理6 n元齐次线性方程组元齐次线性方程组Ax=0有非零解的充分必要条件是有非零解的充分必要条件是R(A)n.定理定理7 矩阵方程矩阵方程AX=B有解的充分必要条件是有解的充分必要条件是R(A)=R(A,B).定理定理8 设设AB=C，则，则R(C)minR(A),R(B).定理定理9 矩阵方程矩阵方程AX=0只有零解的充分必要条件是只有零

3、解的充分必要条件是R(A)=n第4页，此课件共50页哦小结小结有唯一解有唯一解bAx=()()nBRAR=()()nBRAR=有无穷多解有无穷多解.bAx=齐次线性方程组：系数矩阵化成行最简形矩阵，便可写出齐次线性方程组：系数矩阵化成行最简形矩阵，便可写出其通解；其通解；非齐次线性方程组：增广矩阵化成行阶梯形矩阵，便可判断其非齐次线性方程组：增广矩阵化成行阶梯形矩阵，便可判断其是否有解若有解，化成行最简形矩阵，便可写出其通解；是否有解若有解，化成行最简形矩阵，便可写出其通解；当当R(A)=R(B)=rn时，由于含有时，由于含有n-r个参数的解可表示线性方个参数的解可表示线性方程组的任一解，因此

4、称为线性方程组的程组的任一解，因此称为线性方程组的通解通解。第5页，此课件共50页哦二、线性方程组的解法例例1 1 求解齐次线性方程组求解齐次线性方程组解解二、线性方程组的解法二、线性方程组的解法第6页，此课件共50页哦即得与原方程组同解的方程组即得与原方程组同解的方程组第7页，此课件共50页哦由此即得由此即得方程组的通解是：第8页，此课件共50页哦例例 求解非齐次线性方程组求解非齐次线性方程组解解对增广矩阵对增广矩阵B进行初等变换，进行初等变换，,3)(,2)(=BRAR由于，由于，故方程组无解故方程组无解第9页，此课件共50页哦例例 求解非齐次方程组的通解求解非齐次方程组的通解解解 对增广

5、矩阵对增广矩阵B进行初等变换进行初等变换第10页，此课件共50页哦故方程组有解，且有故方程组有解，且有第11页，此课件共50页哦所以方程组的通解为所以方程组的通解为k1k2第12页，此课件共50页哦例例 解证解证对增广矩阵对增广矩阵B进行初等变换，进行初等变换，方程组的增广矩阵为方程组的增广矩阵为第13页，此课件共50页哦第14页，此课件共50页哦由于原方程组等价于方程组由于原方程组等价于方程组由此得通解：由此得通解：第15页，此课件共50页哦例例 设有线性方程组设有线性方程组解解第16页，此课件共50页哦第17页，此课件共50页哦其通解为其通解为第18页，此课件共50页哦这时又分两种情形：这

6、时又分两种情形：第19页，此课件共50页哦第20页，此课件共50页哦此题也可以先求系数行列式。此题也可以先求系数行列式。第21页，此课件共50页哦三、小结()()nBRAR=()()nBRAR|aij|i=1,2,n,j=1,ji 则称方阵则称方阵A是严格是严格(行行)对角占优的对角占优的.a11 a12 a13 a1n a21 a22 a23 a2n A=L+D+U an1 an3 an4 ann -4 2 1例 矩阵 A=1 -9 7 2 -6 10ULD第31页，此课件共50页哦Jacobi 迭代一：设有方程组 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn

7、=b2 .an1x1+an2x2+annxn=bn用矩阵表示：Ax=b （A 为系数矩阵，非奇异；b为右端，x为解向量）第32页，此课件共50页哦假设 aii0 令 cij=-aij/aii (ij)gi=bi/aij,i=1,2,3,n 则 x1(k+1)=c12x2(k)+c13x3(k)+c1nxn(k)+g1 x2(k+1)=c21x1(k)+c23x3(k)+c2nxn(k)+g2 。xn(k+1)=cn1x1(k)+cn2x2(k)+cn(n-1)xn-1(k)+gn Jacobi迭代格式迭代格式 若令若令 0 c12 c13 c1n x1 c21 0 c23 c2n x2BJ=x

8、=.cn1 cn3 cn4 0 xn a11 g1 a22 g=g2 易看出：BJ=D-1(L+U)P148,D=.ann gn 把方程组写成容易迭代的形式：第33页，此课件共50页哦Jacobi迭代公式迭代公式第34页，此课件共50页哦Gauss-Seidel迭代法迭代法 为了加快收敛速度，同时为了节省计算机的内存，我们作如下的改进：每算出一个分量的近似值，立即用到下一个分量的计算中去，即用迭代格式：这样所得的迭代法就称为Gauss-Seidel迭代法，也称为“异步迭代法”，简称为GS迭代法利用Ax=b 及A=L+D+U,其中D为对角矩阵,L,U分别为严格下，上三角矩阵则有，GS迭代法的矩阵

9、形式为:第35页，此课件共50页哦Seidel迭代法的具体形式迭代法的具体形式Seidel迭代格式迭代格式 x1(k+1)=c12x2(k)+c13x3(k)+c1nxn(k)+g1 x2(k+1)=c21x1(k+1)+c23x3(k)+c2nxn(k)+g2 。xn(k+1)=cn1x1(k+1)+cn2x2(k+1)+cn(n-1)xn-1(k+1)+gn 假设 aii0 令 cij=-aij/aii (ij)gi=bi/aij,i=1,2,3,n 第36页，此课件共50页哦收敛性及误差估计Jacobi迭代和GS迭代格式可表述为统一形式:对于其收敛性，我们有如下定理：定理：对任意初始向量

10、x(0)及任意右段向量 g，由此产生的迭代向量序列x(k)收敛的充要条件是证明：必要性：设x(k)收敛，其极限为 x*，则第37页，此课件共50页哦因上式对任意均成立，故Bk 0 (k ),(B)1 充分性：设(B)1,则IB为非奇异阵,且 =0,所以 有唯一解,记为 则 定理：若|B|1,则迭代法收敛.推论若 满足下列条件之一：（）第38页，此课件共50页哦推论2：如果A为严格对角占优阵，则其 Jacobi迭代和Seidel迭代对任何初始向量x(0)都收敛。推论3：如果A为对称正定阵，则其 Seidel迭代对任何初始向量x(0)都收敛。第39页，此课件共50页哦三例题及求解三例题及求解例：用

11、迭代法解方程组AX=b,其中已知该方程的解为 解：本题分别用简单迭代法（Jacobi迭代法）和GS迭代法来解(1)简单迭代法第40页，此课件共50页哦第41页，此课件共50页哦表第42页，此课件共50页哦第43页，此课件共50页哦表2第44页，此课件共50页哦四.相关程序设计原始数据（A,b)可用一个二维数组存储，也可将A用一个二维数组，b用一个一维数组分别存储，存储需要一个一维数组程序中应方便地对迭代方法和终止条件的选择以及对初始向量和值的设置在迭代过程中，为反映迭代情况，可设置一些中间数据的输出，如迭带次数，迭代向量，迭代残向量等当然不需要每迭代一次都作输出这可作为收敛情况或不收敛情况的分

12、析作为不收敛的判定，可设置一个大的整数，当迭带次数超过该数时作为不收敛处理GS 迭代法的计算公式为：第45页，此课件共50页哦开始TFTFT第46页，此课件共50页哦SOR法介绍法介绍利用利用Seidel Seidel 迭代法迭代法 ，考虑如下，考虑如下SOR SOR 迭代格式迭代格式一步一步SeidelSeidel迭代迭代松弛因子松弛因子SORSOR迭代格式也是线性迭代形式迭代格式也是线性迭代形式第47页，此课件共50页哦第48页，此课件共50页哦Seidel迭代格式为 从式中解出 得 故可得Seidel迭代矩阵为第49页，此课件共50页哦迭代法的特点优点：方法简单，每次迭代都是简单的重复运算，易于编制程序；与求解线性方程的精确法相比，简单迭代法对于字长位数较少的计算机更为适用，它可以用增加迭代次数来弥补字长位数少的不足.初值可以任取，因而中间结果偶然错误不影响最后结果的获得。缺点：迭代速度较慢。用计算机计算时，。就其收敛性而言，某些用Seidel迭代法不能收敛而无法得出结果的线性代数方程组，用Jacoai迭代法却能进行收敛计算,反之亦然.第50页，此课件共50页哦