线性代数方程组的迭代解法.pptx

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

1、 对于大型方程组，常用迭代法求解。迭代法与直接法不同，它不能通过有限次的算术运算求得方程组的精确解，而是通过逐步迭代逼近方程组的精确解。但在使用迭代法时，必须考虑收敛性的问题。迭代法较直接法有较明显的优点：程序设计简单，存储量和计算量少等，迭代法其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。第1页/共53页3 3.2 .2 迭代法的一般迭代格式迭代法的一般迭代格式 迭代法的基本思想是将线性方程组转化迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始为便于迭代的等价方程组，对任选一组初始值值 ，按某种计算规则，不断地，按某种计算规则，不断地对所得到的值进行修正，最终获

2、得满足精度对所得到的值进行修正，最终获得满足精度要求的方程组的近似解要求的方程组的近似解。第2页/共53页设设 非奇异，非奇异，则线性方程组，则线性方程组 有惟一解有惟一解 ，经过变换构造，经过变换构造出一个等价同解方程组出一个等价同解方程组将上式改写成迭代式将上式改写成迭代式选定初始向量选定初始向量 ,反复不断反复不断地使用迭代式逐步逼近方程组的精确解地使用迭代式逐步逼近方程组的精确解,直直到满足精度要求为止。这种方法称为迭代法到满足精度要求为止。这种方法称为迭代法第3页/共53页 如果如果 存在极限存在极限则称迭代法是收敛的，否则就是发散的。则称迭代法是收敛的，否则就是发散的。收敛时，在迭

3、代公式收敛时，在迭代公式中当中当 时，时，,则则 ,故故 是方程组是方程组 的解。的解。第4页/共53页利用迭代法求解线性方程组需注意的几个问题：1、迭代格式的构造2、迭代格式的敛散性判定3、迭代格式的收敛速度第5页/共53页例例3.2.13.2.1 用迭代法求解线性方程组用迭代法求解线性方程组 解解 构造方程组的等价方程组构造方程组的等价方程组据此建立迭代公式据此建立迭代公式 取取 计算得计算得 迭代解离精确解迭代解离精确解 越来越远迭代不收敛越来越远迭代不收敛 第6页/共53页3 3.3.3 雅可比迭代法雅可比迭代法设方程组设方程组 的系数矩阵的系数矩阵A A非奇异，且主对非奇异，且主对角

4、元素角元素 ，则可将，则可将A A分裂成分裂成 记作记作 A=D-L-U 第7页/共53页则则 等价于等价于即即因为因为 ，则则这样便得到迭代公式这样便得到迭代公式令令则有则有（k=0,1,2）称为雅可比迭代公式称为雅可比迭代公式,J称为雅可比迭代矩阵称为雅可比迭代矩阵第8页/共53页雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即计算中，要用雅可比迭代法公式的分量形式。即 第9页/共53页Jacobi迭代法的算法第10页/共53页3 3.3 3 雅雅可可比比迭迭代代法法的的算算法法流流程程图图第11

5、页/共53页第12页/共53页3.4 高斯高斯-塞德尔（塞德尔（Gauss-Seidel）迭代法迭代法3.4.1 高斯高斯-塞德尔迭代法的基本思想塞德尔迭代法的基本思想 在在Jacobi迭迭代代法法中中，每每次次迭迭代代只只用用到到前前一一次次的的迭迭代代值值。若若每每次次迭迭代代充充分分利利用用当当前前最最新新的的迭迭代代值值，即在求即在求 时用新分量时用新分量代代替替旧旧分分量量 ,就就得得到到高高斯斯-赛赛德德尔尔迭迭代代法。其迭代法格式为：法。其迭代法格式为：(i=1,2,=1,2,n k=0,1,2,=0,1,2,)第13页/共53页第14页/共53页3.4.2 GaussSeide

6、l 迭代法的矩阵表示迭代法的矩阵表示将将A分裂成分裂成A=D-L-U，则则 等价于等价于 于是于是,则高斯则高斯塞德尔迭代可表示为塞德尔迭代可表示为因为因为 ,所以所以 则高斯则高斯-塞德尔迭代格式为：塞德尔迭代格式为：则有则有于是有迭代格式于是有迭代格式 令令 第15页/共53页3.4.3 高斯高斯塞德尔迭代算法实现塞德尔迭代算法实现 高高斯斯-塞塞德德尔尔迭迭代代算算法法的的计计算算步步骤骤与与流流程程图图与雅可比迭代法大致相同，只是一旦求出变元与雅可比迭代法大致相同，只是一旦求出变元的某个新值的某个新值 后后,就改用新值就改用新值 替代老值替代老值 进行这一步剩下的计算。进行这一步剩下的

7、计算。第16页/共53页Gauss-Seidel迭代法的算法第17页/共53页第18页/共53页3.5 逐次超松弛迭代法（SOR方法）使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过程的加速具有重要意义。逐次超松弛迭代（Successive-over-relaxation）法，可以看作是带参数的高斯塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。第19页/共53页3.5.1超松弛迭代法的基本思想超松弛迭代法的基本思想 超超松松弛弛迭迭代代法法目目的的是是为为了了提提高高迭迭代代法法的的收收敛敛速速度度，在在高高斯

8、斯塞塞德德尔尔迭迭代代公公式式的的基基础础上上作作一一些些修修改改。这这种种方方法法是是将将前前一一步步的的结结果果 与与高高斯斯-塞塞德德尔尔迭迭代代方方法法的的迭迭代代值值 适适当当加加权权平平均均，期期望望获获得得更更好好的的近近似似值值 。是是解解大大型型稀稀疏疏矩矩阵阵方方程程组组的的有有效效方方法之一，有着广泛的应用。法之一，有着广泛的应用。其具体计算公式如下：其具体计算公式如下：用高斯用高斯塞德尔迭代法定义辅助量。塞德尔迭代法定义辅助量。第20页/共53页把把 取为取为 与与 的加权平均，即的加权平均，即 合并表示为：合并表示为：式中系数式中系数称为称为松弛因子松弛因子，当，当=

9、1时，便为高斯时，便为高斯-塞德尔迭代法。为了保证迭代过程收敛，要求塞德尔迭代法。为了保证迭代过程收敛，要求0 2。当当0 1时，低松弛法；当时，低松弛法；当1 2时时称为超松弛法。但通常统称为超松弛法称为超松弛法。但通常统称为超松弛法(SOR)。第21页/共53页3.5.2 超松弛迭代法的矩阵表示超松弛迭代法的矩阵表示设线性方程组设线性方程组 的系数矩阵的系数矩阵A非奇异非奇异,且主对角且主对角元素元素 ,则将则将A A分裂成分裂成A=D-L-U,A=D-L-U,则超松弛迭代公式用矩阵表示为则超松弛迭代公式用矩阵表示为或或 故故 显然对任何一个显然对任何一个值值,(,(D-L)D-L)非奇异

10、非奇异,(,(因为假设因为假设 )于是超松弛迭代公式为于是超松弛迭代公式为 第22页/共53页例例4.4 用用SOR法求解线性方程组法求解线性方程组 取取=1.46，要求要求 解：解：SOR迭代公式迭代公式 k=0,1,2,，初值初值 该方程组的精确解该方程组的精确解只需迭代只需迭代20次便可达到精度要求次便可达到精度要求 如果取如果取=1(即高斯即高斯塞德尔迭代法塞德尔迭代法)和同一初和同一初值值 ,要达到同样精度要达到同样精度,需要迭代需要迭代110次次第23页/共53页3.6 迭代法的收敛性迭代法的收敛性 我们知道我们知道,对于给定的方程组可以构造成对于给定的方程组可以构造成简单迭代公式

11、、雅可比迭代公式、高斯简单迭代公式、雅可比迭代公式、高斯-塞德塞德尔迭代公式和超松弛迭代公式，但并非一定尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。收敛。现在分析它们的收敛性。对于方程组对于方程组 经过等价变换构造出的等价方程组经过等价变换构造出的等价方程组 在什么条件下迭代序列在什么条件下迭代序列 收敛？先引入如下定理收敛？先引入如下定理 第24页/共53页定理定理3.3.1 对给定方阵对给定方阵G,若若 ,则则 为非奇异为非奇异 矩阵矩阵,且且 P44 Th2.6.10P44 Th2.6.10 证证:用反证法用反证法,若若 为奇异矩阵为奇异矩阵,则存在非零向则存在非零

12、向 量量x,使使 ,即有即有 由相容性条件得由相容性条件得 由于由于 ,两端消去两端消去 ,有有 ,与已知条件与已知条件矛盾矛盾,假设不成立假设不成立,命题得证。命题得证。又由于又由于 有有 即即 将将G分别取成分别取成G和和-G，再取范数再取范数 又已知又已知 ，有有 第25页/共53页定理定理3 3.2.2 迭代公式迭代公式 收敛收敛的充分必要条件是迭代矩阵的充分必要条件是迭代矩阵G的谱半径的谱半径证证:必要性必要性 设迭代公式收敛设迭代公式收敛,当当kk时时,则在迭代公式两端同时取极限得则在迭代公式两端同时取极限得记记 ,则则 收敛于收敛于0(0(零向量零向量),),且有且有 于是于是

13、由于由于 可以是任意向量可以是任意向量,故故 收敛于收敛于0 0当且仅当且仅当当 收敛于零矩阵，即当收敛于零矩阵，即当 时时 于是于是 所以必有所以必有 第26页/共53页充分性充分性 设设 ,则必存在正数则必存在正数,使使则存在某种范数则存在某种范数 ,使使 ,P45 Th2.6.11 ,则则 ,所以所以 ,即即 。故。故 收敛于收敛于 0,收敛于收敛于 由此定理可知，不论是雅可比迭代法、高斯由此定理可知，不论是雅可比迭代法、高斯塞德尔迭代法还是超松弛迭代法，它们收敛的塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径充要条件是其迭代矩阵的谱半径 。事实上事实上,在例在例3

14、.2.1中中,迭代矩阵迭代矩阵G=，其特征多项式为其特征多项式为特征值为特征值为-2，-3，,所以迭代发散所以迭代发散 证毕证毕 第27页/共53页定理定理3 3.3(.3(迭代法收敛的充分条件迭代法收敛的充分条件)若迭代矩阵若迭代矩阵G G的一种范数的一种范数 ,则迭代公式则迭代公式收敛收敛,且有误差估计式且有误差估计式,且有误差估计式且有误差估计式 及及 证证:矩阵的谱半径不超过矩阵的任一种范数矩阵的谱半径不超过矩阵的任一种范数,已知已知 ,因此因此 ,根据定理根据定理3 3.2.2可知可知迭代公式收敛迭代公式收敛第28页/共53页又因为又因为 ,则则det(I-G)0,I-G为非奇异矩阵

15、为非奇异矩阵,故故xGxd有惟一解有惟一解 ,即即与迭代过程与迭代过程 相比较相比较,有有两边取范数两边取范数 第29页/共53页由迭代格式，有由迭代格式，有 两边取范数，代入上式，得两边取范数，代入上式，得 证毕证毕 由定理知，当由定理知，当 时，其值越小，迭代收时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代敛越快，在程序设计中通常用相邻两次迭代 （为给定的精度要求）作为为给定的精度要求）作为控制迭代结束的条件控制迭代结束的条件 第30页/共53页例例3 3.6.16.1 已知线性方程组已知线性方程组 考察用考察用JacobiJacobi迭代和迭代和G-SG-S迭代求解时的收敛性

16、迭代求解时的收敛性解解:做矩阵分解做矩阵分解第31页/共53页(1)Jacobi(1)Jacobi迭代矩阵迭代矩阵故故JacobiJacobi迭代收敛迭代收敛(2)G-S(2)G-S 迭代矩阵迭代矩阵故故G-SG-S迭代收敛迭代收敛 第32页/共53页第33页/共53页定理定理3.4 设设n阶方阵阶方阵 为对角占优阵为对角占优阵,则则 非奇非奇 P53 引理引理3.1.1证证:因因A为对角占优阵为对角占优阵,其主对角元素的绝对值大其主对角元素的绝对值大 于同行其它元素绝对值之和于同行其它元素绝对值之和,且主对角元素且主对角元素 全不为全不为0,故对角阵故对角阵 为非奇异。为非奇异。作矩阵作矩阵

17、 第34页/共53页利用对角占优知利用对角占优知 由定理由定理3 3.1知知 非奇异非奇异,从而从而A非奇异非奇异,证毕证毕 系数矩阵为对角占优阵的线性方程组称作对角系数矩阵为对角占优阵的线性方程组称作对角占优方程组占优方程组。第35页/共53页定理定理3.5 对角占优线性方程组对角占优线性方程组 的雅可比的雅可比 迭代公式和高斯迭代公式和高斯-赛德尔迭代公式均收敛。赛德尔迭代公式均收敛。证证:雅可比迭代公式的迭代矩阵为雅可比迭代公式的迭代矩阵为 由定理由定理3.4知知,这时这时 ,再由再由定理定理3.3知迭代收敛知迭代收敛 再考察高斯再考察高斯-赛德尔迭代公式的迭代矩阵赛德尔迭代公式的迭代矩

18、阵 令令 ，则有，则有 于是于是,写出分量形式有写出分量形式有 变形得变形得第36页/共53页设设 而而 由上式得由上式得 由此整理得由此整理得 利用对角占优条件知上式右端小于利用对角占优条件知上式右端小于1,(1,(如果右端大如果右端大于于1,1,则得出与对角占优条件矛盾的结果则得出与对角占优条件矛盾的结果)故有故有据定理据定理3 3.3.3知知G-SG-S收敛收敛 第37页/共53页例例3.6.23.6.2 设求解线性方程组设求解线性方程组 的雅可比迭代的雅可比迭代 求证当求证当 1 1时时,相应的高斯相应的高斯-塞德尔迭代收敛塞德尔迭代收敛 证证:由于由于B B是雅可比迭代的迭代矩阵是雅

19、可比迭代的迭代矩阵,故有故有 又又 1,1,故有故有 则则 系数矩阵系数矩阵 为对角占优阵为对角占优阵,故故G-SG-S迭代收敛迭代收敛 第38页/共53页第39页/共53页第40页/共53页例例3.6.3 3.6.3 设设 ,证明证明,求解方程组求解方程组 的的JacobiJacobi迭代与迭代与G-SG-S迭代同时收敛或发散迭代同时收敛或发散 证证:JacobiJacobi迭代矩阵迭代矩阵 其谱半径其谱半径 第41页/共53页G-SG-S迭代矩阵迭代矩阵 显然显然,和和 同时小于、等于或大于同时小于、等于或大于1,1,因而因而JacobiJacobi迭代法与迭代法与G-SG-S迭代法具有相

20、同的收敛性迭代法具有相同的收敛性 其谱半径其谱半径 第42页/共53页例例 3.6.4 考察用考察用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性，其中的收敛性，其中解：显然解：显然,该线性方程组的系数矩阵为严格对该线性方程组的系数矩阵为严格对角占优矩阵，所以角占优矩阵，所以Jacobi迭代法和迭代法和G-S迭代法迭代法均收敛。均收敛。第43页/共53页例例 3.6.5 考察用考察用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性，其中的收敛性，其中解：解：易知，该

21、线性方程组的系数矩阵为对称正定阵，易知，该线性方程组的系数矩阵为对称正定阵，故故G-S迭代法均收敛。迭代法均收敛。Jacobi迭代矩阵为迭代矩阵为 ，故，故Jacobi迭代法发散。迭代法发散。第44页/共53页 Ax=b的系数矩阵按行严格对角占优的系数矩阵按行严格对角占优,故故高斯高斯-塞德尔迭代收敛塞德尔迭代收敛例例3.6.6 设有迭代格式设有迭代格式 X(k+1)=B X(k)+g (k=0,1,2）其中其中B=I-A,如果如果A和和B的特征值全为正数，的特征值全为正数，试证：该迭代格式收敛。试证：该迭代格式收敛。分析分析:根据根据A，B和单位矩阵和单位矩阵I之间的特征值的之间的特征值的关

22、系导出关系导出()1,从而说明迭代格式收敛。从而说明迭代格式收敛。证证:因为因为B=I-A,故故(B)=(I)-(A)=1-(A)(A)+(B)=1 由于已知由于已知(A)和和 (B)全为正数，故全为正数，故 0(B)1,从而从而 (B)1 所以该迭代格式收敛。所以该迭代格式收敛。第45页/共53页例例3.6.7 讨论用讨论用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解下述线性方程组的收敛性。法解下述线性方程组的收敛性。第46页/共53页求特征值求特征值雅可比矩阵雅可比矩阵 (B)=1 用用雅可比迭代法求解时，迭代过程不收敛雅可比迭代法求解时，迭代过程不收敛 1=-1，2,

23、3=1/2第47页/共53页求特征值求特征值高斯高斯-塞德尔迭代矩阵塞德尔迭代矩阵 (G1)=0.3536 1 用用高斯高斯-塞德尔迭代塞德尔迭代法求解时，迭代过程收敛法求解时，迭代过程收敛 1=0,第48页/共53页求解求解AX=b,AX=b,当当 取何取何值时迭代收敛？值时迭代收敛？解解:所给迭代公式的迭代矩阵为所给迭代公式的迭代矩阵为 例例3.6.8 3.6.8 给定线性方程组给定线性方程组 AX=bAX=b 用迭代公式用迭代公式 X X(K+1)(K+1)=X=X(K)(K)+(b-A(b-AX X(K)(K)(k=0,1,)(k=0,1,）第49页/共53页即即 2-(2-5 )+1

24、-5 +4+4 2 2=0=0 2-(2-5 )+(1-)(1-4)=0)=0 -(1-)-(1-4)=0=0 1=1-2=1-4 (B)=max|1-|,|1-4|1取取0 1/21/2迭代收敛迭代收敛第50页/共53页本章小结 本章介绍了解线性方程组本章介绍了解线性方程组 迭代法的迭代法的一些基本理论和具体方法。迭代法是一种逐次逼一些基本理论和具体方法。迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法限为方程组的解。注意

25、到在使用迭代法解方程组时，其迭代矩阵解方程组时，其迭代矩阵B B和迭代向量和迭代向量f f在计算过在计算过程中始终不变，迭代法具有循环的计算公式，方法程中始终不变，迭代法具有循环的计算公式，方法简单，程序实现方便，它的优点是能充分利用系简单，程序实现方便，它的优点是能充分利用系数的稀疏性，适宜解大型稀疏系数矩阵的方程组。数的稀疏性，适宜解大型稀疏系数矩阵的方程组。第51页/共53页 使用迭代法解线性方程组的关键问题是其收敛使用迭代法解线性方程组的关键问题是其收敛性与收敛速度，而收敛性与迭代初值的选取无关。性与收敛速度，而收敛性与迭代初值的选取无关。在实际计算中，判断一种迭代格式收敛性较麻烦，在

26、实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于种范数都小于1 1或对角占优或对称正定性来判断收敛或对角占优或对称正定性来判断收敛性。有时也可边计算边观察其收敛性。如何加快迭性。有时也可边计算边观察其收敛性。如何加快迭代过程的收敛速度是一个很重要的问题，实用中更代过程的收敛速度是一个很重要的问题，实用中更多的采用多的采用SORSOR法，选择适当的松驰因子法，选择适当的松驰因子有赖于实际有赖于实际经验。我们应针对不同的实际问题，采用适当的数经验。我们应针对不同的实际问题，采用适当的数值算法。值算法。第52页/共53页感谢您的观看！第53页/共53页