线性方程组的迭代法幻灯片.ppt

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

1、线性方程组的迭代法2023/4/141第1页，共87页，编辑于2022年，星期一其中其中A为非奇异矩阵为非奇异矩阵.其解法大致分为其解法大致分为直接法直接法(第六章第六章)和和迭代法迭代法(第五章第五章)两大类两大类.对线性方程组对线性方程组 Ax=b，(1.1)5.1 5.1 迭代公式的建立迭代公式的建立在用直接法解线性方程组时要对系数矩阵不断在用直接法解线性方程组时要对系数矩阵不断变变换换.如果方程组的阶数很高如果方程组的阶数很高,则运算量将会很大则运算量将会很大并且大并且大量占用计算机资源，量占用计算机资源，因此对线性方程组因此对线性方程组要求找寻更经济、要求找寻更经济、适用的数值解法适

2、用的数值解法.2023/4/142第2页，共87页，编辑于2022年，星期一当当A为为大型稀疏矩阵方程组大型稀疏矩阵方程组(A的阶数的阶数n很大，但很大，但零元零元素较多素较多),利用迭代法求解是合适的利用迭代法求解是合适的.本节将介绍迭代法的一些基本理论及本节将介绍迭代法的一些基本理论及雅可比迭雅可比迭代法代法，高斯高斯-赛德尔迭代法赛德尔迭代法，超松弛迭代法超松弛迭代法，而超松弛，而超松弛迭代法应用很广泛。迭代法应用很广泛。2023/4/143第3页，共87页，编辑于2022年，星期一q 迭代法：迭代法：从一个初始向量出发，按照一定的从一个初始向量出发，按照一定的迭代格式迭代格式，构造出，

3、构造出一个趋向于真解的无穷序列一个趋向于真解的无穷序列迭代解法是目前求解大规模线性方程组的主要方法.只需存储系数矩阵中的非零元素只需存储系数矩阵中的非零元素运算量不超过运算量不超过O(kn2),其中其中 k 为迭代步数为迭代步数(1)迭代格式的建立迭代格式的建立(3)误差估计和收敛速度误差估计和收敛速度研究研究 内容：内容：(2)收敛性判断收敛性判断 下面举一简例，以便了解迭代法的思想下面举一简例，以便了解迭代法的思想.2023/4/144第4页，共87页，编辑于2022年，星期一 例例1 求解方程组求解方程组记为记为Ax=b，其中，其中此方程组的精确解是此方程组的精确解是x*=(3,2,1)

4、T.现将改写为现将改写为2023/4/145第5页，共87页，编辑于2022年，星期一或写为或写为x=B0 x+f，其中，其中2023/4/146第6页，共87页，编辑于2022年，星期一 任取初始值，例如取任取初始值，例如取x(0)=(0,0,0)T.将这些值代入将这些值代入(1.3)式右边式右边(若若(1.3)式为等式即求得方程组的解，但一式为等式即求得方程组的解，但一般不满足般不满足)，得到新的值，得到新的值x(1)=(x1(1),x2(1),x3(1)T=(3.5,3,3)T，再将，再将x(1)分量代入分量代入(1.3)式右边得到式右边得到 x(2)，反复利用，反复利用这个计算程序，得

5、到一向量序列和一般的计算公式这个计算程序，得到一向量序列和一般的计算公式(迭代公迭代公式式)2023/4/147第7页，共87页，编辑于2022年，星期一简写为简写为 x(k+1)=B0 x(k)+f，其中其中k表示迭代次数表示迭代次数(k=0,1,2,).迭代到第迭代到第10次有次有2023/4/148第8页，共87页，编辑于2022年，星期一 迭代法的一个突出优点就是迭代法的一个突出优点就是算法简单算法简单，因而编制程序比，因而编制程序比较容易。但是迭代法也有缺点较容易。但是迭代法也有缺点,它要求方程组的系数矩阵它要求方程组的系数矩阵具有某种特殊性质，以保证迭代过程的收敛性具有某种特殊性质

6、，以保证迭代过程的收敛性.发散的迭发散的迭代过程是没有实用价值的代过程是没有实用价值的.这种方式就称为迭代法这种方式就称为迭代法.以上过程称为迭代过程以上过程称为迭代过程.迭代迭代法产生一个序列法产生一个序列如果其极限存在如果其极限存在,即即则称迭代法收敛则称迭代法收敛,否则称为发散否则称为发散.从此例看出，由迭代法产生的向量序列从此例看出，由迭代法产生的向量序列x(k)逐步逼近方逐步逼近方程组的精确解程组的精确解x*=(3,2,1)T.即有即有 2023/4/149第9页，共87页，编辑于2022年，星期一对于任何一个方程组对于任何一个方程组x=Bx+f(由由Ax=b变形得到的等价变形得到的

7、等价方程组方程组)，由迭代法产生的向量序列，由迭代法产生的向量序列x(k)是否一定逐步逼近是否一定逐步逼近方程组的解方程组的解x*呢？回答呢？回答是不一定是不一定.例如：考虑用迭代法解例如：考虑用迭代法解下述方程组下述方程组 x(k)并不是所有的都收敛并不是所有的都收敛并不是所有的都收敛并不是所有的都收敛到解到解到解到解x*！2023/4/1410第10页，共87页，编辑于2022年，星期一对于给定方程组对于给定方程组x=Bx+f，设有唯一解，设有唯一解x*，则，则 x*=Bx*+f.(1.5)又设又设x(0)为任取的初始向量为任取的初始向量,按下述公式构造向量序列按下述公式构造向量序列 x(

8、k+1)=Bx(k)+f,k=0,1,2,.(1.6)其中其中k表示迭代次数表示迭代次数.定义定义1 (1)对于给定的方程组对于给定的方程组x=Bx+f,用公式用公式(1.6)逐逐步代入求近似解的方法称为步代入求近似解的方法称为迭代法迭代法(或称为或称为一阶定常迭代一阶定常迭代法法，这里，这里B与与k无关无关).B称为称为迭代矩阵迭代矩阵.(2)如果如果limx(k)(k)存在存在(记为记为x*),称此称此迭代法收敛迭代法收敛,显然显然x*就是方程组的解就是方程组的解,否则称此否则称此迭代法发散迭代法发散.2023/4/1411第11页，共87页，编辑于2022年，星期一 由上述讨论，需要研究

9、由上述讨论，需要研究x(k)的收敛性的收敛性.引进误差向引进误差向量量 由由(1.6)减去减去(1.5)式，得式，得(k+1)=B(k)(k=0,1,2,)，递推得递推得 要考察要考察x(k)的收敛性，就要研究的收敛性，就要研究B在什么条件下有在什么条件下有lim(k)=0(k)，亦即要研究，亦即要研究B满足什么条件时有满足什么条件时有Bk00(零向量零向量)(k).2023/4/1412第12页，共87页，编辑于2022年，星期一其中，其中，A=(aij)Rnn为非奇异矩阵，下面研究任何建立为非奇异矩阵，下面研究任何建立Ax=b的各种迭代法的各种迭代法.设线性方程组设线性方程组 Ax=b，(

10、1.7)其中，其中，M为可选择的非奇异矩阵，且使为可选择的非奇异矩阵，且使Mx=d容易求解，容易求解，一般选择一般选择A的某种近似，称的某种近似，称M为为分裂矩阵分裂矩阵.将将A分裂为分裂为 A=M-N.(1.8)1 迭代公式的矩阵表示迭代公式的矩阵表示2023/4/1413第13页，共87页，编辑于2022年，星期一 于是，求解于是，求解Ax=b转化为求解转化为求解Mx=Nx+b，即求解，即求解可构造一阶定常迭代法可构造一阶定常迭代法其中其中 B=M-1N=M-1(M-A)=I-M-1A，f=M-1b.称称 B=I-M-1A为迭代法的为迭代法的迭代矩阵迭代矩阵，选取，选取M矩阵，就得到解矩阵

11、，就得到解Ax=b的的各种迭代法各种迭代法.设设aii 0(i=1,2,n)，并将，并将A写成三部分写成三部分2023/4/1414第14页，共87页，编辑于2022年，星期一2023/4/1415第15页，共87页，编辑于2022年，星期一即即A=D-L-U2023/4/1416第16页，共87页，编辑于2022年，星期一2 雅可比雅可比(Jacobi)迭代公式迭代公式 设设aii 0(i=1,2,n)，选取，选取M为为A的对角元素部分的对角元素部分,即即选取选取M=D(对角阵对角阵)，A=D-N，由，由(1.9)式得到解方程组式得到解方程组Ax=b的的雅可比雅可比(Jacobi)迭代法迭代

12、法.又称又称简单迭代法简单迭代法.其中其中B=I-D-1A=D-1(L+U)=J,f=D-1b.称称J为解为解Ax=b的的雅可雅可比迭代法的迭代矩阵比迭代法的迭代矩阵.2023/4/1417第17页，共87页，编辑于2022年，星期一于是雅可比迭代法可写为于是雅可比迭代法可写为矩阵形式矩阵形式其其Jacobi迭代矩阵迭代矩阵为为2023/4/1418第18页，共87页，编辑于2022年，星期一下面给出雅可比迭代法下面给出雅可比迭代法(1.10)的分量计算公式的分量计算公式,记记由雅可比迭代法由雅可比迭代法(1.10)有有每一个分量写出来为每一个分量写出来为即当即当aii 0时，有时，有2023

13、/4/1419第19页，共87页，编辑于2022年，星期一等等价价方方程程组组其中其中 aii(i)0(i=1,2,n)即由方程组即由方程组Ax=b得到的得到的2023/4/1420第20页，共87页，编辑于2022年，星期一建立的雅可比迭代格式为建立的雅可比迭代格式为2023/4/1421第21页，共87页，编辑于2022年，星期一于是，解于是，解Ax=b的雅可比迭代法的计算公式为的雅可比迭代法的计算公式为 由由(1.11)式可知，雅可比迭代法计算公式简单，每迭代式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵一次只需计算一次矩阵和向量的乘法且计算

14、过程中原始矩阵A始终不变始终不变.2023/4/1422第22页，共87页，编辑于2022年，星期一3 高斯赛德尔迭代法高斯赛德尔迭代法在在 Jacobi迭代中，计算迭代中，计算 xi(k+1)(2 i n)时时，使用使用xj(k+1)代替代替xj(k)(1 j i-1)，即有即有建建立立迭迭代代格格式式2023/4/1423第23页，共87页，编辑于2022年，星期一或缩写为或缩写为称为称为高斯高斯塞德尔塞德尔(Gauss Seidel)迭代法迭代法.其其Gauss Seidel迭代矩阵迭代矩阵为为BG=(D-L)-1U于是高斯于是高斯塞德尔迭代法可写为塞德尔迭代法可写为矩阵形式矩阵形式20

15、23/4/1424第24页，共87页，编辑于2022年，星期一 这就是说，选取分裂矩阵这就是说，选取分裂矩阵M为为A的下三角部分的下三角部分,即选即选取取M=D-L(下三角阵下三角阵)，A=M-N，由，由(1.9)式得到解式得到解Ax=b的的高斯高斯塞德尔塞德尔(Gauss Seidel)迭代法迭代法.其中其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.称矩阵称矩阵G=(D-L)-1U为解为解Ax=b的的高斯高斯塞德尔塞德尔迭代法的迭代矩阵迭代法的迭代矩阵.2023/4/1425第25页，共87页，编辑于2022年，星期一由由高斯高斯塞德尔迭代法塞德尔迭代法(1.12

16、)有有每一个分量写出来为每一个分量写出来为即当即当aii 0时，有时，有(与前面一样的式子与前面一样的式子)或或2023/4/1426第26页，共87页，编辑于2022年，星期一于是，解于是，解Ax=b的的高斯高斯塞德尔塞德尔迭代法的计算公式为迭代法的计算公式为或或2023/4/1427第27页，共87页，编辑于2022年，星期一 雅可比迭代法雅可比迭代法不使用变量的最新信息计算不使用变量的最新信息计算xi(k+1)，而，而由由高斯高斯塞德尔迭代公式塞德尔迭代公式(1.13)可知，计算可知，计算x(k+1)的第的第 i个分量个分量xi(k+1)时，利用了已经计算出的最新分量时，利用了已经计算出

17、的最新分量xj(k+1)(j=1,2,i-1).可看作可看作雅可比迭代法雅可比迭代法的一种改进的一种改进.由由(1.13)可知，可知，高斯高斯塞德尔迭代公式塞德尔迭代公式每迭代一次只需计算每迭代一次只需计算一次矩阵与向量的乘法一次矩阵与向量的乘法.算法算法(高斯高斯塞德尔迭代法塞德尔迭代法)见书见书p160.2023/4/1428第28页，共87页，编辑于2022年，星期一 例例2 用用高斯高斯塞德尔迭代法塞德尔迭代法解例解例1的方程组的方程组(1.2).解解 用用高斯高斯塞德尔迭代公式：塞德尔迭代公式：取取x(0)=(0,0,0)T.迭代到第迭代到第7次有次有2023/4/1429第29页，

18、共87页，编辑于2022年，星期一 由此例可知，用由此例可知，用高斯高斯塞德尔迭代法塞德尔迭代法，雅可比迭雅可比迭代法代法解线性方程组解线性方程组(1.2)(且取且取x(0)=0)均收敛，而均收敛，而高斯高斯塞德塞德尔迭代法尔迭代法比比雅可比迭代法雅可比迭代法收敛较快收敛较快(即取相同的即取相同的x(0)，达，达到同样精度所需迭代次数较少到同样精度所需迭代次数较少)，但这结论只当，但这结论只当A满足一定满足一定条件时才是对的条件时才是对的.2023/4/1430第30页，共87页，编辑于2022年，星期一 例例3 用雅可比迭代法解方程组用雅可比迭代法解方程组 解：解：Jacobi迭代格式为迭代

19、格式为2023/4/1431第31页，共87页，编辑于2022年，星期一kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15111.099993 1.199993 1.29999112 1.099998 1.199998 1.299997取取 x(0)=(0,0,0)T 计算结果如下：计算结果如下：2023/4/1432第32页，共87页，编辑于2022年，星期一 解：解：Gauss-Seidel迭代格式为迭代格式为 例例4 用用GaussSeidel 迭代法解上题迭代法解上题.2023/4/1433第33页，共87页，编辑于2022年，星期一取取 x(0)=

20、(0,0,0)T 计算结果如下：计算结果如下：kx1(k)x2(k)x3(k)10.720.9021.164481.0999981.1999991.32023/4/1434第34页，共87页，编辑于2022年，星期一4 解大型稀疏线性方程组的逐次超松弛法解大型稀疏线性方程组的逐次超松弛法(SOR方法方法)我们取我们取 0为为松弛因子松弛因子，建立迭代格式如下，建立迭代格式如下即即2023/4/1435第35页，共87页，编辑于2022年，星期一或改写为或改写为称为称为逐次超逐次超松弛迭代法松弛迭代法(Successive Over Relaxation Method),，简称，简称SOR方法方

21、法.(1.14)2023/4/1436第36页，共87页，编辑于2022年，星期一 (1)显然，当显然，当=1时即为时即为GaussSeidel 迭代法迭代法.(2)SOR方法方法每迭代一次主要运算量是计算一次矩阵每迭代一次主要运算量是计算一次矩阵与向量的乘法与向量的乘法.(3)当当 1时，称为时，称为超松弛法超松弛法；当；当 0,使得对任意使得对任意 恒有恒有（证（证:略）略）2023/4/1448第48页，共87页，编辑于2022年，星期一定理定理3 其中其中 为向量中的任一种范数为向量中的任一种范数.2023/4/1449第49页，共87页，编辑于2022年，星期一例例 3 求下列向量的

22、各种常用范数求下列向量的各种常用范数解解解解:1*499/4*4=91*499/4*4=92023/4/1450第50页，共87页，编辑于2022年，星期一定义定义3（矩阵的范数）如果矩阵（矩阵的范数）如果矩阵 的某个的某个非负的实值函数非负的实值函数 ，满足，满足则称则称 是是 上的一个上的一个矩阵范数矩阵范数(或模或模).).2023/4/1451第51页，共87页，编辑于2022年，星期一定义定义4 4（矩阵的算子范数）（矩阵的算子范数）设n 维向量X 和 n 阶方阵A，当给定一种向量范数|X|时，则定义 为矩阵的范数，并称为矩阵的算子范数。矩阵范数定义的另一种方法矩阵范数定义的另一种方

23、法:从定义可以看出，矩阵范数和向量范数密切相关。从定义可以看出，矩阵范数和向量范数密切相关。2023/4/1452第52页，共87页，编辑于2022年，星期一常用的矩阵范数常用的矩阵范数-(5)-(6)-(7)q矩阵矩阵算子算子范数：（范数：（诱导诱导范数）范数）由向量范数由向量范数|p 导出关于矩阵导出关于矩阵 A Rn n 的的 p 范数范数:2023/4/1453第53页，共87页，编辑于2022年，星期一矩阵范数的性质可由向量范数定义直接验证矩阵范数的性质可由向量范数定义直接验证.(1)设设A0,x0,使使Ax0,根据向量范数的性根据向量范数的性 质质 Ax 0,所以所以0 x0,使使

24、 Ax =0,则则=0当当A=0时时,2023/4/1454第54页，共87页，编辑于2022年，星期一(2)根据向量范数的性质根据向量范数的性质2023/4/1455第55页，共87页，编辑于2022年，星期一(3)2023/4/1456第56页，共87页，编辑于2022年，星期一例例4 4 计算方阵计算方阵 的三种范数的三种范数 解解 先计算先计算 所以所以 ,从而从而 2023/4/1457第57页，共87页，编辑于2022年，星期一例例例例5 5 5 5求矩阵求矩阵A A的各种常用范数的各种常用范数解解解解:由于由于2023/4/1458第58页，共87页，编辑于2022年，星期一特征

25、方程为特征方程为2023/4/1459第59页，共87页，编辑于2022年，星期一容易计算容易计算容易计算容易计算计算较复杂计算较复杂计算较复杂计算较复杂对矩阵元素的对矩阵元素的对矩阵元素的对矩阵元素的变化比较敏感变化比较敏感变化比较敏感变化比较敏感使用最广泛使用最广泛使用最广泛使用最广泛性质较好性质较好性质较好性质较好使用最广泛使用最广泛使用最广泛使用最广泛2023/4/1460第60页，共87页，编辑于2022年，星期一5.3 5.3 迭代过程的收敛性迭代过程的收敛性1 迭代收敛的充分条件迭代收敛的充分条件其中，其中，A=(aij)Rnn为非奇异矩阵，记为非奇异矩阵，记x*为为(3.1)精

26、确解，精确解，且设有等价的方程组且设有等价的方程组 设线性方程组设线性方程组 Ax=b，(3.1)于是于是设有解设有解Ax=b的一阶定常迭代法的一阶定常迭代法2023/4/1461第61页，共87页，编辑于2022年，星期一有意义的问题是：迭代矩阵有意义的问题是：迭代矩阵B满足什么条件时，由迭代满足什么条件时，由迭代法产生的向量序列法产生的向量序列x(k)收敛到收敛到x*.引进引进误差向量误差向量由由(3.3)式减式减(3.2)得到得到误差向量的递推公式误差向量的递推公式由由5.1节可知，研究迭代法节可知，研究迭代法(3.3)收敛性问题就是要研究迭代矩收敛性问题就是要研究迭代矩阵阵B满足什么条

27、件时，有满足什么条件时，有.2023/4/1462第62页，共87页，编辑于2022年，星期一 定义定义1 设有矩阵序列设有矩阵序列 Ak=(aij(k)Rnn 及及A=(aij)Rnn，如果，如果n2个数列极限存在且有个数列极限存在且有则则Ak称收敛于称收敛于A，记为，记为lim Ak=A(k).例例1 设有矩阵序列设有矩阵序列Ak,其中其中Ak=Bk,而而且设且设|1，考查矩阵序列极限，考查矩阵序列极限.解解 显然显然,当当|1时时,则有则有2023/4/1463第63页，共87页，编辑于2022年，星期一矩阵序列极限概念可以用矩阵算子范数来描述矩阵序列极限概念可以用矩阵算子范数来描述.定

28、理定理1 其中其中|为为矩阵的任意一种算子范数矩阵的任意一种算子范数.证明证明 显然有显然有再由矩阵范数的等价性再由矩阵范数的等价性,则定理对其它算子范数亦对则定理对其它算子范数亦对.定理定理2证明作为练习证明作为练习.2023/4/1464第64页，共87页，编辑于2022年，星期一 定理定理3(迭代法收敛的充分条件迭代法收敛的充分条件)设有方程组设有方程组 x=Bx+f，B=(bij)Rnn，及一阶定常迭代法及一阶定常迭代法 x(k+1)=Bx(k)+f.如果有如果有B的某种算子范数的某种算子范数|B|=q1，则，则 (1)迭代法迭代法收敛，即对任取收敛，即对任取x(0)有有2023/4/

29、1465第65页，共87页，编辑于2022年，星期一2 对角占优方程组对角占优方程组 在科学及工程计算中，要求解方程组在科学及工程计算中，要求解方程组Ax=b，其矩阵，其矩阵A常常具有某些特性常常具有某些特性.例如，例如，A具有对角占优性质或具有对角占优性质或A为不为不可约阵，或可约阵，或A是对称正定阵，下面讨论用基本迭代法解这些是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性方程组的收敛性.2023/4/1466第66页，共87页，编辑于2022年，星期一 定义定义2(对角占优阵对角占优阵)设设A=(aij)nn.(1)如果如果A的元素满足的元素满足称称A为为严格严格(按行按行)对角占

30、优阵对角占优阵.(2)如果如果A的元素满足的元素满足且上式至少有一个不等式成立，称且上式至少有一个不等式成立，称A为为弱弱(按行按行)对角占对角占优阵优阵.2023/4/1467第67页，共87页，编辑于2022年，星期一 定义定义3(可约与不可约矩阵可约与不可约矩阵)设设A=(aij)nn(n2)，如，如果存在置换阵果存在置换阵P使使其中其中A11为为r阶方阵，阶方阵，A22为为n-r阶方阵阶方阵(1rn)，则称，则称A为为可约矩阵可约矩阵.否则，如果不存在这样置换阵否则，如果不存在这样置换阵P使使(3.6)式成立，式成立，则称则称A为为不可约矩阵不可约矩阵.A为可约矩阵意即为可约矩阵意即A

31、可经过若干行列重排化为可经过若干行列重排化为(3.6)或或Ax=b可化为两个低阶方程组求解可化为两个低阶方程组求解(如果如果A经过两行交换的经过两行交换的同时进行相应两列的交换，称对同时进行相应两列的交换，称对A进行一次行列重排进行一次行列重排).2023/4/1468第68页，共87页，编辑于2022年，星期一 事实上，由事实上，由Ax=b可化为可化为PTAP(PTx)=PTb.于是，求解于是，求解Ax=b化为求解化为求解且记且记 ,其中其中yi,di为为r维向量维向量.由上式第由上式第2个方程组求出个方程组求出y2,再代入第再代入第1个方程组求出个方程组求出y1.显然，如果显然，如果A所有

32、元素都非零，则所有元素都非零，则A为不可约阵为不可约阵.2023/4/1469第69页，共87页，编辑于2022年，星期一 例例7 设有矩阵设有矩阵则则A,B都是不可约矩阵都是不可约矩阵.2023/4/1470第70页，共87页，编辑于2022年，星期一 定理定理4(对角占优定理对角占优定理)如果如果A=(aij)nn为为严格对角占优严格对角占优矩阵矩阵或或A为为不可约弱对角占优矩阵不可约弱对角占优矩阵，则，则A为非奇异矩阵为非奇异矩阵.证明证明 只就只就A为为严格对角占优矩阵严格对角占优矩阵证明此定理证明此定理.采用反证法，如果采用反证法，如果det(A)=0，则，则Ax=b有非零解，记有非

33、零解，记为为x=(x1,x2,xn)T，则，则 .由齐次方程组第由齐次方程组第k个方程个方程则有则有即即这与假设矛盾，故这与假设矛盾，故det(A)0.2023/4/1471第71页，共87页，编辑于2022年，星期一 定理定理5 设方程组设方程组Ax=b，如果，如果(1)A为为严格对角占优阵，则解严格对角占优阵，则解Ax=b的的Jacobi迭代迭代法法,Gauss-Seidel迭代法迭代法均收敛均收敛.(2)A为弱对角为弱对角占优阵，且占优阵，且A为不可约矩阵为不可约矩阵,则解则解Ax=b的的Jacobi迭代法迭代法,Gauss-Seidel迭代法迭代法均收敛均收敛.证明证明 只证只证(1)

34、，(2)作为练习作为练习.因为因为A是严格对角占优阵，所以是严格对角占优阵，所以aii0(i=1,n).则则|J|1，所以，所以 Jacobi 迭代法迭代法收敛收敛.Jacobi迭代阵迭代阵2023/4/1472第72页，共87页，编辑于2022年，星期一 下面证明下面证明GaussSeidel 迭代法迭代法收敛收敛.由由G=(D-L)-1U，得，得下面证明下面证明|1.若不然若不然,即即|1,则则由于由于所以所以2023/4/1473第73页，共87页，编辑于2022年，星期一即矩阵即矩阵是严格对角占优矩阵，故可逆，这与是严格对角占优矩阵，故可逆，这与(*)式矛盾，所以式矛盾，所以|1,从而

35、从而 (G)0.2023/4/1475第75页，共87页，编辑于2022年，星期一所以所以|1,从而从而(G)1,故故Gauss-Seidel迭代法迭代法收敛收敛.令令-(Ly,y)=a+ib，则由复向量内积的性质有，则由复向量内积的性质有下面研究对于解方程组下面研究对于解方程组Ax=b的的SOR方法方法中松弛因子中松弛因子在在什么范围内取值，什么范围内取值，SOR方法方法才可能收敛才可能收敛.2023/4/1476第76页，共87页，编辑于2022年，星期一定理定理7(SOR方法收敛的必要条件方法收敛的必要条件)设解设解方程组方程组 Ax=b的的SOR迭代法迭代法收敛，则收敛，则0 2.证证

36、 A=D-L-U，L=(D-L)-1(1-)D+U,由于由于SOR迭代法迭代法收敛，则收敛，则(L)1.设迭代矩阵设迭代矩阵L 的特征值为的特征值为 i(i=1,n)，则有，则有det(L)|1 2 n|(B )n1.于是于是所以所以|1-|1 1，即，即 0 2.2023/4/1477第77页，共87页，编辑于2022年，星期一定理定理7说明解说明解Ax=b的的SOR迭代法迭代法，只有在，只有在(0,2)范围范围内取松弛因子内取松弛因子，才可能收敛，才可能收敛.定理定理8(SOR方法收敛的充分条件方法收敛的充分条件)设有设有方程组方程组 Ax=b，如果：，如果：(1)A为对称为对称正定矩阵正

37、定矩阵，A=D-L-LT;(2)0 2.则解则解方程组方程组 Ax=b的的SOR迭代法迭代法收敛收敛.证证 在上述假定下，设迭代矩阵在上述假定下，设迭代矩阵L 的任一特征值为的任一特征值为，只要证明只要证明|0.令令-(Ly,y)=a+ib，则由复向量内积的性质有，则由复向量内积的性质有2023/4/1479第79页，共87页，编辑于2022年，星期一当当0 2时，有时，有(分子减分母分子减分母)即即L 的任一特征值满足的任一特征值满足|1,故故SOR迭代法迭代法收敛收敛.2023/4/1480第80页，共87页，编辑于2022年，星期一由定理由定理3证明中可知，如果证明中可知，如果(B)1且

38、且(B)越小时，越小时，迭代法收敛越快迭代法收敛越快.现设有方程组现设有方程组下面讨论迭代法的收敛速度下面讨论迭代法的收敛速度.x=Bx+f，B=(bij)Rnn，及一阶定常迭代法及一阶定常迭代法 x(k+1)=Bx(k)+f (k=0,1,)，由基本定理有由基本定理有0(B)1，且误差向量，且误差向量(k)=x(k)-x*满足满足且设且设迭代法迭代法收敛，即对任取收敛，即对任取x(0)，记，记(k)=Bk(0)，2023/4/1481第81页，共87页，编辑于2022年，星期一故故现设现设B为对称矩阵，则有为对称矩阵，则有下面确定使初始误差缩小下面确定使初始误差缩小10-s所需的迭代次数所需

39、的迭代次数,即使即使取对数，得到所需最少迭代次数为取对数，得到所需最少迭代次数为此式说明，满足精度此式说明，满足精度所需迭代次数与所需迭代次数与R=-ln(B)成反比，成反比，当当(B)1越小，越小，R=-ln(B)越大，则满足越大，则满足所需迭代次数越所需迭代次数越少，即迭代法收敛越快少，即迭代法收敛越快.2023/4/1482第82页，共87页，编辑于2022年，星期一定义定义5 称称R(B)=-ln(B)为迭代法为迭代法 x(k+1)=Bx(k)+f (k=0,1,)的的渐近收敛速度渐近收敛速度，简称，简称迭代法收敛速度迭代法收敛速度.对于对于SOR迭代法迭代法希望选择希望选择松弛因子松

40、弛因子 使迭代过程收敛使迭代过程收敛较快，在理论上即确定较快，在理论上即确定最佳因子最佳因子 opt使使对某些特殊类型的矩阵，建立了对某些特殊类型的矩阵，建立了SOR方法方法最佳因子理最佳因子理论论.例如，对所谓具有例如，对所谓具有“性质性质A”等条件的线性方程组建立等条件的线性方程组建立了最佳松弛因子公式了最佳松弛因子公式其中其中(J)为解为解Ax=b的的jacobi迭代法迭代法的迭代矩阵的的迭代矩阵的谱半径谱半径.2023/4/1483第83页，共87页，编辑于2022年，星期一在实际应用中，对于某些椭圆型微分方程在实际应用中，对于某些椭圆型微分方程(模型问题模型问题)可可以给出以给出 o

41、pt的计算方法，但一般说来，计算的计算方法，但一般说来，计算 opt是有困难的，是有困难的，可用试算的办法来确定一个适当的可用试算的办法来确定一个适当的.算法算法(SOR迭代法迭代法).2023/4/1484第84页，共87页，编辑于2022年，星期一定理定理 若若Jacobi 迭代矩阵迭代矩阵J 为非负矩阵，则下列关系为非负矩阵，则下列关系有一个且仅有一个成立：有一个且仅有一个成立：(1)(J)=(G)=0；(2)0(G)(J)1；(3)(J)=(G)=1；(4)1(J)(G).说明：说明：当当Jacobi 迭代矩阵迭代矩阵J为非负矩阵时为非负矩阵时,Jacobi方法和方法和 GaussSe

42、idel 方法方法同时收敛同时收敛或或同时发散同时发散,若为同时收敛若为同时收敛,则后者比前者收敛快则后者比前者收敛快.2023/4/1485第85页，共87页，编辑于2022年，星期一例如例如 已知方程组已知方程组判断判断雅可比迭代法雅可比迭代法和和高斯高斯塞德尔法塞德尔法的敛散性？的敛散性？解解 因为因为雅可比迭代矩阵雅可比迭代矩阵2023/4/1486第86页，共87页，编辑于2022年，星期一故故Jacobi 迭代法迭代法收敛收敛.再由定理的再由定理的(2)或由或由 A 对称正定知对称正定知 GaussSeidel迭代迭代法法也收敛，且比也收敛，且比 Jacobi 迭代法迭代法收敛得快收敛得快.2023/4/1487第87页，共87页，编辑于2022年，星期一