第七章 线性代数方程组的迭代法精选PPT.ppt

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

1、第七章 线性代数方程组的迭代法第1页，本讲稿共21页1 1 迭代法基础迭代法基础 问问问问 题题题题 在实际应用中遇到的系数矩阵多为大型稀疏矩阵，如在实际应用中遇到的系数矩阵多为大型稀疏矩阵，如用求解线性方程组的直接法求解，在计算机上会耗费用求解线性方程组的直接法求解，在计算机上会耗费大量的时间和存储单元。在许多应用问题中使用迭代大量的时间和存储单元。在许多应用问题中使用迭代法。法。第2页，本讲稿共21页思思路路将将 改写为改写为 等价形式等价形式 ，建立迭代，建立迭代 ,从初值从初值 出发，得到序列出发，得到序列 。研究内容：研究内容：如何建立迭代格式？如何建立迭代格式？收敛速度？收敛速度？

2、向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？第3页，本讲稿共21页一般迭代法一般迭代法定义定义1 1 对方程组对方程组 ，化为等价方程，化为等价方程组组 ，设，设 为任取的初值，将上式写为为任取的初值，将上式写为迭代过程迭代过程这种迭代过程称为这种迭代过程称为逐次逼近法逐次逼近法，B B 称为称为迭代矩阵迭代矩阵。若若 称逐次逼近法称逐次逼近法收敛，收敛，否则，称否则，称逐次逼近法逐次逼近法不收敛或发散不收敛或发散。第4页，本讲稿共21页问题：问题：按上述思想迭代产生的向量序列按上述思想迭代产生的向量序列 在什在什 么条件下收敛于方程组么条件下收敛于方程组Ax=bAx=b的解？

3、的解？引进误差向量引进误差向量：，其中，其中 为方程为方程组的解，即有组的解，即有所以，要使所以，要使 收敛到收敛到 ，则需研究，则需研究 在什么条在什么条件下有件下有 。第5页，本讲稿共21页迭代法的收敛条件与误差估计迭代法的收敛条件与误差估计引理引理 当当k 时，时，Bk 0 0 (B)1)1定理定理1 1 设有线性方程组设有线性方程组 ，那么逐次逼近，那么逐次逼近 法对任意初始向量法对任意初始向量 收敛的充分必要条件收敛的充分必要条件 是迭代矩阵是迭代矩阵B B的谱半径的谱半径 (B B)11。注：注：要检验一个矩阵的谱半径小于要检验一个矩阵的谱半径小于1 1比较困难，比较困难，所以我们

4、希望用别的办法判断收敛性。所以我们希望用别的办法判断收敛性。第6页，本讲稿共21页注注:1.1.因为矩阵范数因为矩阵范数 都可以直接用矩阵的元素都可以直接用矩阵的元素 计算，因此用定理计算，因此用定理2 2，很容易判别逐次逼近法的收敛性。很容易判别逐次逼近法的收敛性。2.2.定理定理2 2是充分条件，当找不到矩阵的某一范数小于是充分条件，当找不到矩阵的某一范数小于1 1时，时，并不能判断并不能判断迭代法不收敛。迭代法不收敛。定理定理2 2 设线性方程组设线性方程组 有惟一解有惟一解 ，若存若存 在一个矩阵范数使得在一个矩阵范数使得|B|1,则则迭代收敛迭代收敛,且有下列误差估计：且有下列误差估

5、计：第7页，本讲稿共21页（7 7.1）1 1雅克比（雅克比（JacobiJacobi）迭代法）迭代法设有设有n n阶方程组阶方程组2 2 几种常用的迭代法几种常用的迭代法第8页，本讲稿共21页若系数矩阵非奇异，且若系数矩阵非奇异，且 (i=1,2,n)，将方程组将方程组（7.1）改写成改写成第9页，本讲稿共21页然后写成迭代格式然后写成迭代格式（7.2）（7.2）式也可以简单地写为式也可以简单地写为（7.3）第10页，本讲稿共21页记记 ,其中其中则雅克比迭代法的矩阵形式为：则雅克比迭代法的矩阵形式为：(7.4)称称 为雅克比迭代矩阵。为雅克比迭代矩阵。第11页，本讲稿共21页第12页，本讲

6、稿共21页 写成矩阵形式：写成矩阵形式：2 2高斯高斯赛得尔赛得尔(Gauss-Seidel)(Gauss-Seidel)迭代法迭代法(7.5)(7.6)其中其中 称为称为高斯高斯赛得尔赛得尔迭代矩阵。迭代矩阵。第13页，本讲稿共21页定理定理4 4 n n阶矩阵阶矩阵A A是严格对角占优矩阵的充分必要条件是是严格对角占优矩阵的充分必要条件是 Jacobi Jacobi迭代法的迭代矩阵满足迭代法的迭代矩阵满足 B BJ J11。3 3JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的收敛性迭代法的收敛性定理定理5 5 如果如果A A是严格对角占优矩

7、阵，那么是严格对角占优矩阵，那么JacobiJacobi和和G GS S 迭代法都收敛。迭代法都收敛。定理定理6 6 若若A A是是n n阶正定矩阵，那么阶正定矩阵，那么G-SG-S迭代法收敛。迭代法收敛。定理定理3 3 n n阶矩阵阶矩阵A A是严格对角占优矩阵，则是严格对角占优矩阵，则A A非奇异，且非奇异，且 所有对角元所有对角元 。第14页，本讲稿共21页注意的问题注意的问题（1 1）JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的迭代矩阵不同：迭代法的迭代矩阵不同：BJ=D-1(L+U),B G-S=(D-L)-1U（2 2）Jacob

8、iJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法收敛性没有必然的迭代法收敛性没有必然的 联系。即当联系。即当Gauss-SeidelGauss-Seidel法收敛时，法收敛时，JacobiJacobi法可能不收法可能不收 敛；而敛；而JacobiJacobi法收敛时，法收敛时，Gauss-SeidelGauss-Seidel法也可能不收敛法也可能不收敛（3 3）JacobiJacobi迭代和迭代和Gauss-SeidelGauss-Seidel迭代的特征方程：迭代的特征方程：第15页，本讲稿共21页JacobiJacobi迭代：迭代：Gauss-Seidel

9、Gauss-Seidel迭代：迭代：第16页，本讲稿共21页用用JacobiJacobi迭代法求解收敛，迭代法求解收敛，但用但用 Gauss-Seidel Gauss-Seidel法不收敛。法不收敛。B BJ J的特征值为的特征值为0 0，0 0，0 0，B BG GS S的特征值为的特征值为0 0，2 2，2 2（4 4）举例）举例：用用JacobiJacobi迭代法求解不收敛，迭代法求解不收敛，但用但用 Gauss-Seidel Gauss-Seidel法收敛。法收敛。第17页，本讲稿共21页系数矩阵系数矩阵A A是正定矩阵，因此用是正定矩阵，因此用 Gauss-SeidelGauss-S

10、eidel法收敛。法收敛。线性方程组的系数矩阵为线性方程组的系数矩阵为是严格对角占优的，所以是严格对角占优的，所以Jacobi和和Gauss-Seidel迭代格式迭代格式均收敛。均收敛。第18页，本讲稿共21页（1）迭代）迭代（2）加速）加速（7.7）即即3 3 3 3 超松驰超松驰迭代法（迭代法（SOR法）法）（Sequential Over-Relaxation)Sequential Over-Relaxation)矩阵形式：矩阵形式：第19页，本讲稿共21页注：注：1.1.称称 为为超松弛超松弛迭代矩阵。迭代矩阵。2.2.称称 为为松弛因子。松弛因子。3.3.当当 时，就是时，就是G-S

11、G-S迭代法；当迭代法；当 时，称为低时，称为低 松弛松弛迭代法；当迭代法；当 时，称为时，称为超松弛超松弛迭代法。迭代法。4.SOR 4.SOR法也称为法也称为G-SG-S迭代法的一种加速方法。迭代法的一种加速方法。5.5.研究研究SORSOR法就是需要找到最佳法就是需要找到最佳松弛因子，使得松弛因子，使得迭代迭代 过程的收敛速度最快，即过程的收敛速度最快，即 。6.6.在找最佳在找最佳松弛因子之前，先要解决松弛因子之前，先要解决 在什么范围内在什么范围内 取值，才能保证取值，才能保证SOR法法收敛。收敛。第20页，本讲稿共21页定理定理7 7 对对Ax=b,Ax=b,设设 ，SORSOR方方 法收敛的必要条件是法收敛的必要条件是松驰因子松驰因子 。定理定理8 8 给定线性方程组给定线性方程组Ax=b,Ax=b,如果如果A A是对称正定矩是对称正定矩 阵，且阵，且 ，则，则SORSOR方法收敛。方法收敛。第21页，本讲稿共21页