工科数值分析第六章wang教学课件PPT.pptx

《工科数值分析第六章wang教学课件PPT.pptx》由会员分享，可在线阅读，更多相关《工科数值分析第六章wang教学课件PPT.pptx（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第六章线性方程组的迭代法2内容提要内容提要n 单步定常迭代法单步定常迭代法n 基于矩阵分裂的迭代法基于矩阵分裂的迭代法n 特殊方程组迭代法的收敛性特殊方程组迭代法的收敛性n Matlab实践实践3单步定常迭代法单步定常迭代法l 向量序列与矩阵序列的极限向量序列与矩阵序列的极限l 迭代法的构造迭代法的构造l 迭代法的收敛性判断迭代法的收敛性判断n 迭代法的基本概念迭代法的基本概念4向量序列的极限向量序列的极限定义定义：设向量序列设向量序列 ， ，若，若存在向量存在向量 ，使得，使得 ( )0kkx ( )( )( )( )12,Tkkkknxxxx 12,Tnxxxx ( )limkiikxx

2、 i = 1, 2, , n则称向量序列则称向量序列 收敛到收敛到 x，记作，记作 ( )0kkx ( )limkkxx l 每个分量都收敛每个分量都收敛l 也称也称 x 是向量序列是向量序列 x(k) 的极限的极限5矩阵序列的极限矩阵序列的极限定义定义：设矩阵序列设矩阵序列 ，若存在矩阵，若存在矩阵 ，使得使得则称矩阵序列则称矩阵序列 Ak 收敛到收敛到 A，记作，记作( )kkijn nAa ( )limkijijkaa i, j = 1, 2, , nlimkkAA ijn nAa 例：例：设设 a 1，考察下面矩阵序列的极限，考察下面矩阵序列的极限212212,000kkkkaaaak

3、aAAAaaa 解：板书解：板书6矩阵极限判断矩阵极限判断定理定理：limkkAA lim0kkAA定理定理：lim0kkA lim0, RnkkA xx 证明：板书证明：板书(其中其中 | | 为任一算子范数为任一算子范数)证明：板书证明：板书7矩阵极限判断矩阵极限判断定理定理：lim0kkB ( )1B 定理定理：1( )limkkkBB (其中其中 | | 为任一矩阵范数为任一矩阵范数)证明：略证明：略定理定理： 存在某算子范数存在某算子范数 ，使得，使得lim0kkB 证明：略证明：略1B 证明：略证明：略8线性方程组迭代法线性方程组迭代法l 运算量大，不适合大规模的线性方程组求解运算

4、量大，不适合大规模的线性方程组求解l 无法充分利用系数矩阵的稀疏性无法充分利用系数矩阵的稀疏性l 直接法的缺点直接法的缺点 从一个初始向量出发，按照一定的迭代格式，构造出一个趋从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的向量序列。向于真解的向量序列。l 只需存储系数矩阵中的非零元素只需存储系数矩阵中的非零元素l 运算量不超过运算量不超过 O(kn2)，其中，其中 k 为迭代步数为迭代步数迭代法是目前求解大规模线性方程组的主要方法迭代法是目前求解大规模线性方程组的主要方法l 迭代法迭代法 9迭代法的构造迭代法的构造l 矩阵分裂迭代法基本思想矩阵分裂迭代法基本思想Ax = b(1

5、)( )kkxBxf k = 0, 1, 2, 给定一个初始向量给定一个初始向量 x(0)，可得，可得 迭代格式迭代格式其中其中 B = M-1N 称为称为迭代矩阵迭代矩阵 11xM NxM bA = M - NMx = Nx + bM 非奇异非奇异A 的一个的一个矩阵分裂矩阵分裂10矩阵分裂迭代法矩阵分裂迭代法k = 0, 1, 2, 定义定义：若若 存在，则称该迭代法存在，则称该迭代法收敛收敛，否则称为，否则称为发散发散(1)( )kkxBxf ( )limkkx性质性质：若若 ，则，则 x* 为原方程组为原方程组 Ax = b 的解的解( )limkkxx 11迭代法的收敛性迭代法的收敛

6、性(1)( )kkxBxf 定理定理：对任意初始向量对任意初始向量 x(0)，上述迭代格式收敛的充要条件是，上述迭代格式收敛的充要条件是( )1B 定理定理：若存在算子范数若存在算子范数 | |，使得，使得 |B| 1，对任意的初始向量，对任意的初始向量 x(0)，上述迭代格式收敛。，上述迭代格式收敛。例例：考虑迭代法考虑迭代法 x(k+1) = Bx(k) + f 的收敛性，其中的收敛性，其中0.900.30.8B 证明：板书证明：板书12迭代法的收敛性迭代法的收敛性(1)( )kkxBxf B = M-1N定理定理：若存在算子范数若存在算子范数 | |，使得，使得 |B| = q 1，则，

7、则( )(0)kkxxqxx(1) 迭代法收敛迭代法收敛(2) (3) (4) ( )( )(1)1kkkqxxxxq ( )(1)(0)1kkqxxxxq 证明：板书证明：板书13收敛速度收敛速度第第 k 步的误差：步的误差：( )( )kkxx (0)kB ( )(0)kkB 平均每次迭代后的误差压缩率约为：平均每次迭代后的误差压缩率约为：1kkBl 若要求若要求 k 步迭代后上述误差比值不超过步迭代后上述误差比值不超过 ，则，则kB 11kkkB 11lnlnkkBk 1lnlnkkkB l 迭代法的收敛速度迭代法的收敛速度14收敛速度收敛速度定义定义：迭代法迭代法 x(k+1) = B

8、x(k) + f 的平均收敛速度定义为的平均收敛速度定义为1( )lnkkkR BB 渐进收敛速度为渐进收敛速度为( )lim( )ln( )kxR BRBB l (B) 越小，迭代收敛越快越小，迭代收敛越快l 迭代法的收敛速度迭代法的收敛速度15基于矩阵分裂的迭代法基于矩阵分裂的迭代法l Jacobi 迭代法迭代法l GaussSeidel 迭代法迭代法l SOR（超松弛）迭代法（超松弛）迭代法l 迭代法收敛性分析迭代法收敛性分析n 几个基本的迭代法几个基本的迭代法16Jacobi 迭代迭代考虑线性方程组考虑线性方程组Ax = b其中其中 A=(aij)n n 非奇异，且对角线元素全不为非奇

9、异，且对角线元素全不为 0 1122diag(,)nnDaaa 211,10 0,0nn naLaa l 将将 A 分裂成分裂成 A = D - L- U， 其中其中1211,000nnnaaUa l Jacobi 迭代法迭代法17Jacobi 迭代迭代(1)1( )1()kkxDLU xD bk = 0, 1, 2, 令令 M = D，N = L + U，可得，可得 雅可比雅可比 (Jacobi) 迭代方法迭代方法l 迭代矩阵记为：迭代矩阵记为：1()JDLU l 分量形式：分量形式：1(1)11inkiiijjijjiijj ixba xa xa i = 1, 2, , n， k = 0,

10、 1, 2, Jacobi 迭代法迭代法18Gauss-Seidel 迭代迭代l 在计算在计算 时，如果用时，如果用 代替代替 ，则可能会得到更好的收敛效果。则可能会得到更好的收敛效果。(1)kix (1)(1)11,kkixx( )( )11,kkixx (1)( )( )( )11122133111(1)( )( )( )22211233222(1)( )( )( )1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa (1)( )( )( )11122133111(1)(1)( )( )22211233

11、222(1)(1)(1)(1)1122,11 kkkknnkkkknnkkkknnnnn nnnnxba xa xa xaxba xa xa xaxba xa xaxa 19Gauss-Seidel 迭代迭代 (1)1(1)( )kkkxDbLxUx写成矩阵形式写成矩阵形式:此迭代方法称为此迭代方法称为 高斯高斯-塞德尔塞德尔 (Gauss-Seidel) 迭代法迭代法k = 0, 1, 2, 11(1)( )kkxDLUxDLb 可得可得1GDLUl 迭代矩阵记为：迭代矩阵记为：20SOR 迭代迭代l 为了得到更好的收敛效果，可在修正项前乘以一个为了得到更好的收敛效果，可在修正项前乘以一个

12、松弛因子松弛因子 ，于是可得迭代格式，于是可得迭代格式 (1)(1)(1)( )( )11,11,11,kkkkkiiii iii iii nniixba xaxaxa xa1(1)( )1( )inkkiijjijjiijj ikiba xa xax (1)1(1)()1()inkkiijjijjiijkiij ikba xaaxxx G-S 迭代法的分量形式迭代法的分量形式21SOR 迭代迭代 (1)( )1(1)( )( )kkkkkxxDbLxUxDx 11(1)( )(1)kkxDLDU xDLb 写成矩阵形式写成矩阵形式:可得可得 SOR (Successive Over-Rela

13、xation) 迭代方法迭代方法 1(1)LDLDU l 迭代矩阵记为：迭代矩阵记为：l SOR 的优点的优点：通过选取合适的：通过选取合适的 ，可获得更快的收敛速度，可获得更快的收敛速度l SOR 的缺点的缺点：最优参数最优参数 的的选取比较困难选取比较困难22Jacobi、G-S、SORl Jacobi 迭代迭代(1)1( )1()kkxDLU xD b1(1)( )( )11inkkkiiijjijjiijj ixba xa xa l SOR 迭代迭代 11(1)( )(1)kkxDLDU xDLb 1(1)( )(1)( )1inkkkkiiiijjijjiijj ixxba xa x

14、a 11, (1)MDLNDUl G-S 迭代迭代 11(1)( )kkxDLUxDLb 1(1)(1)( )11inkkkiiijjijjiijj ixba xa xa , MDLNU, MDNLU23举例举例例例：分别用分别用 Jacobi、G-S、SOR 迭代解线性方程组迭代解线性方程组123210113180125xxx 取初始向量取初始向量 x(0) = ( 0, 0, 0 )，迭代过程中小数点后保留，迭代过程中小数点后保留 4 位。位。解：解：Jacobi 迭代：迭代： (1)( )12(1)( )( )213(1)( )32128352kkkkkkkxxxxxxx 迭代可得：迭代

15、可得： x(1) = ( 0.5000, 2.6667, -2.5000 )Tx(21) = ( 2.0000, 3.0000, -1.0000 )T2*31x 24举例举例G-S 迭代：迭代： (1)( )12(1)(1)( )213(1)(1)32128352kkkkkkkxxxxxxx x(1) = ( 0.5000, 2.8333, -1.0833 )Tx(9) = ( 2.0000, 3.0000, -1.0000 )T迭代可得：迭代可得： 25举例举例SOR 迭代：迭代： (1)( )( )( )1112(1)( )(1)( )( )22123(1)( )(1)( )3323122

16、833522kkkkkkkkkkkkkxxxxxxxxxxxxx 取取 = 1.1，迭代可得，迭代可得x(1) = ( 0.5500, 3.1350, -1.0257 )Tx(7) = ( 2.0000, 3.0000, -1.0000 )T如何确定如何确定 SOR 迭代中的最优松弛因子是一件迭代中的最优松弛因子是一件很困难很困难的事的事26l Jacobi 迭代收敛的迭代收敛的充要充要条件条件 (J)1l G-S 迭代收敛的迭代收敛的充要充要条件条件 (G)1l SOR 迭代收敛的迭代收敛的充要充要条件条件 (L )1收敛性收敛性l Jacobi 迭代收敛的迭代收敛的充分充分条件条件 |J|

17、 1l G-S 迭代收敛的迭代收敛的充分充分条件条件 |G| 1l SOR 迭代收敛的迭代收敛的充分充分条件条件 |L | 1收敛性分析收敛性分析27特殊方程组迭代法的收敛性特殊方程组迭代法的收敛性且且至少有一个至少有一个不等式严格成立，则称不等式严格成立，则称 A 为为 弱对角占优弱对角占优；若若所有不等式所有不等式都严格成立，则称都严格成立，则称 A 为为 严格对角占优严格对角占优。( i = 1, 2, . , n )定义定义：设设 A Rn n，若，若1, |niiijjj iaa 对角占优矩阵对角占优矩阵28可约与不可约可约与不可约定义定义：设设 A Rn n，若存在排列矩阵，若存在

18、排列矩阵 P 使得使得 则称则称 A 为为 可约矩阵可约矩阵；否则称为否则称为 不可约矩阵不可约矩阵 。111222,0TAAP APA () ()1122, 11r rn rn rARARrnl 如果如果 A 是可约矩阵，则方程组是可约矩阵，则方程组 Ax = b 等价于等价于 TTTP APP xP b 11112212222 A yA yfA yf y即可以把原方程组化成两个即可以把原方程组化成两个低阶低阶的方程组来处理。的方程组来处理。f不可约矩阵不可约矩阵29Jacobi、G-S 收敛性收敛性定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 A

19、 非奇异非奇异定理定理：若若 A 严格对角占优严格对角占优或或不可约弱对角占优不可约弱对角占优，则，则 Jacobi 迭迭代和代和 G-S 迭代均收敛迭代均收敛 定理定理：若若 A 对称，且对角线元素均大于对称，且对角线元素均大于 0，则，则(1) Jacobi 迭代收敛的充要条件是迭代收敛的充要条件是 A 与与 2D-A 均正定；均正定；(2) G-S 迭代收敛的充要条件是迭代收敛的充要条件是 A 正定。正定。l Jacobi 和和 G-S 迭代法的收敛性迭代法的收敛性证明：板书证明：板书证明：板书证明：板书证明：板书证明：板书30SOR 收敛性收敛性定理定理：若若 SOR 迭代收敛，则迭代

20、收敛，则 0 2。l SOR 收敛的必要条件收敛的必要条件定理定理：若若 A 对称正定，且对称正定，且 0 2，则则 SOR 迭代收敛。迭代收敛。l SOR 收敛的充分条件收敛的充分条件定理定理：若若 A 严格对角占优或不可约弱对角占优，且严格对角占优或不可约弱对角占优，且 0 1，则则 SOR 迭代收敛。迭代收敛。证明：板书证明：板书证明：板书证明：板书证明：略证明：略31举例举例例例：设设 ，给出，给出 Jacobi 和和 G-S 收敛的充要条件收敛的充要条件 111aaAaaaa 解：解：A 对称，且对角线元素均大于对称，且对角线元素均大于 0，故，故 (1) Jacobi 收敛的充要条

21、件是收敛的充要条件是 A 和和 2D-A 均正定均正定(2) G-S 收敛的充要条件是收敛的充要条件是 A 正定正定A 正定正定2212310,10,(1) (12 )0DDaDaa0.51a2D-A 正定正定2212310,10,(1) (12 )0DDaDaa0.50.5aJacobi 收敛的充要条件是：收敛的充要条件是：-0.5a0.5G-S 收敛的充要条件是：收敛的充要条件是：-0.5a132举例举例解法二：解法二：Jacobi 的迭代矩阵为的迭代矩阵为设设 是是 J 的特征值，则由的特征值，则由 det( I - J) = 0 可得可得111aaJaaaa ( - a)2 ( +2a) = 0Jacobi 收敛的充要条件是收敛的充要条件是 (J)1 | |1，即即 -0.5a0.5