《数值分析第7章线性代数方程组的迭代法》由会员分享，可在线阅读，更多相关《数值分析第7章线性代数方程组的迭代法（35页珍藏版）》请在金锄头文库上搜索。
1、第七章,线性方程组 的迭代解法,问题驱动：绗架设计,给出。固定支点,同时受到水平方向的力,和垂直方向的力,的作用，但移动支点,只受到垂直方向的力,的作用。,图7.1.1 绗架的受力分析图,如果整个绗架处以平衡状态，每个支点的合力应为零向量， 因此每个支点上力的水平分量和垂直分量之和都应该为零。由 此可得到一个如表 7.1.1所示的线性方程组，该方程组中的系数 矩阵中含有46个零元素，而仅有18个非零元素，通常把含有大 量零元素的矩阵称为稀疏矩阵，由于使用直接法求解这类方程 组，会破坏系数矩阵的稀疏性，这种情况下一般采用迭代法求 解方程组。,表7.1.1, 问 题 在实际应用中遇到的系数矩阵多为
2、大型稀疏矩阵，如用求解线性方程组的直接法求解，在计算机上会耗费大量的时间和存储单元。在许多应用问题中使用迭代法。,思路,将 改写为 等价形式 ，建立迭代 。从初值 出发，得到序列 。, 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？,一般迭代法,迭代格式的构造,把矩阵A分裂为,则,将上式写为迭代过程 这种迭代过程称为逐次逼近法，B 称为迭代矩阵。,收敛性定义：若 称逐次逼近法收敛， 否则，称逐次逼近法不收敛或发散。,给定初值 就得到向量序列,问题：,定理1 任意给定初始向量x0，如果由逐次 逼近法产生的向量序列收敛于向量x*，那么， x*是方程组x=Bx+g的解。,证明：,是
3、否为方程组Ax=b的解？,迭代法的收敛条件,定理2 设线性方程组x=Bx+g有惟一解，那么逐次逼近法对任意初始向量X收敛的充分必要条件是迭代矩阵B的谱半径 (B ) 1。,证明：,因此，,注：要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断收敛性。,定理3 若逐次逼近法的迭代矩阵满 足B1， 那么逐次逼近法收敛。,Remark:因为矩阵范数 都可以 直接用矩阵的元素计算，因此,用定理3，很 容易判别逐次逼近法的收敛性。,证明：,迭代法的误差估计,误差表达式及收敛速度。,停机准则。,（4.1）,1雅克比（Jacobi）迭代法,设有n阶方程组,几种常用的迭代格式,若系数矩阵非奇异，
4、且 (i = 1, 2, n)，将方程组,（4.1）改写成,然后写成迭代格式,（4.2）,（4.2）式也可以简单地写为,（4.3）,写成矩阵形式：,L,U,D,Jacobi 迭代阵,Algorithm: Jacobi Iterative Method Solve .Given an initial approximation . Input: the number of equations and unknowns n; the matrix entries a ; the entries b ; the initial approximation X0 ; tolerance TOL; ma
5、ximum number of iterations Mmax. Output: approximate solution X or a message of failure. Step 1 Set k = 1; Step 2 While ( k Mmax) do steps 3-6 Step 3 For i = 1, , n Set ; /* compute xk */ Step 4 If then Output (X ); STOP; /* successful */ Step 5 For i = 1, , n Set X 0 = X ; /* update X0 */ Step 6 Se
6、t k +; Step 7 Output (Maximum number of iterations exceeded); STOP. /* unsuccessful */,What if aii = 0?,迭代过程中，A 的元素 不改变，故可以事先调整好 A 使得 aii 0，否则 A不可逆。,必须等X(k)完全计算 好了才能计算X(k+1)，因此 需要两组向量存储。,A bit wasteful, isnt it?, ,只存一组向量即可。,写成矩阵形式：,Gauss-Seidel 迭代阵,2高斯赛得尔(Gauss-Seidel)迭代法,(4.5),(4.6),Gauss-Seidel 迭代
7、阵,其迭代格式的矩阵形式为,事实上，这相当于对系数矩阵A作的另一个分裂：,定理5 n阶矩阵A是按行严格对角占优矩阵的充分必要条件是Jacobi迭代法的迭代矩阵满足 BJ1.,定理6 n阶矩阵A是按列严格对角占优矩阵的 充分必要条件是Jacobi迭代法的迭代矩阵 满足 BJ11.,相关性质,Jacobi迭代法和Gauss-Seidel迭代法的收敛性,定理 7 如果A是按行(列)严格对角占优的矩阵，那么Jacobi和GS迭代法都收敛.,定理 8 设A是不可约对角占优矩阵， 那么Jacobi迭代法与GS迭代法都收敛.,定理 9 若A是n阶正定矩阵，那么，G-S迭代法收敛.,定理 10 设A是有正对角
8、元的n阶对称矩阵， 那么Jacobi迭代法收敛的充分必要条件是A和 2D-A同为正定矩阵.,注意的问题,（2）Jacobi迭代法和Gauss-Seidel迭代法的收敛 性没有必然的联系：,即当Gauss-Seidel法收敛时，Jacobi法可能不收敛； 而Jacobi法收敛时， Gauss-Seidel法也可能不收敛。,（1）Jacobi迭代法和Gauss-Seidel迭代法的迭代 矩阵不同：,BJ =D-1(L+U), B G-S = (D-L)-1U,（3）Jacobi迭代和Gauss-Seidel迭代的特征方程：,Jacobi迭代,Gauss-Seidel迭代,举例,用Jacobi迭代法
9、求解不收敛，但用 Gauss-Seidel法收敛。,用Jacobi迭代法求解收敛， 但用 Gauss-Seidel法不收敛。,BJ的特征值为0，0，0， 而BGS的特征值为 0，2，2,系数矩阵A是正定矩阵，因此用 Gauss-Seidel法收敛.,是正定矩阵，因此用 Jacobi迭代法收敛.,利用定理7,A是有正对角元 的n阶对称矩阵,线性方程组的系数矩阵为,是严格对角占优的，所以Jacobi和Gauss-Seidel迭代格式 均收敛。,3超松驰法（Sequential Over-Relaxation),（1）迭代,（2）加速,（4.7）,矩阵形式：,即,超松弛法的收敛性,定理11 SOR方法收敛的必要条件是松驰因子,定理12 给定线性方程组Ax=b,如果A是对称正定 阵，且w （0，2），则SOR方法收敛。,注： 时，SOR迭代即为Gauss-Seidel迭代。,SOR迭代收敛的充要条件为,，其中，,桥梁绗架问题的求解,可用一个,的矩阵描述该方程组，其状态方程组可表示成,由Gauss-Seidel迭代法可得,由此可建立迭代格式,取初始向量,，用Matlab求解经,次迭代可得,
