数值分析 第3章 解线性方程组的迭代法

1、上页上页上页上页上页上页下页下页下页下页下页下页解线性方程组的迭代方法解线性方程组的迭代方法 1 引言引言 2 基本迭代法基本迭代法 3 迭代法的收敛性迭代法的收敛性上页上页上页上页上页上页下页下页下页下页下页下页其中其中A为非奇异矩阵为非奇异矩阵, 当当A为为低阶稠密矩阵低阶稠密矩阵时时, 用前面讨用前面讨论的选主元消去法是有效的论的选主元消去法是有效的. 但对于但对于大型稀疏矩阵方大型稀疏矩阵方程组程组(A的阶数的阶数n很大，但很大，但零元素较多零元素较多), 利用迭代法求解利用迭代法求解是合适的是合适的. 迭代法的基本思想就是用逐次逼近的方法去求线迭代法的基本思想就是用逐次逼近的方法去求

2、线性方程组的解。性方程组的解。 本章将介绍迭代法的一些基本理论及本章将介绍迭代法的一些基本理论及雅可比迭代雅可比迭代法法，高斯高斯-赛德尔迭代法赛德尔迭代法，超松弛迭代法超松弛迭代法，而超松弛迭，而超松弛迭代法应用很广泛。代法应用很广泛。 下面举简例，以便了解迭代法的思想下面举简例，以便了解迭代法的思想. 对线性方程组对线性方程组 Ax=b， (1.1) 1 引言引言上页上页上页上页上页上页下页下页下页下页下页下页 例例1 求解方程组求解方程组)2 . 1(.361236,33114,20238321321321 xxxxxxxxx记为记为Ax=b，其中，其中.363330,123611142

3、38321 bxxxxA方程组的精确解是方程组的精确解是x*=(3,2,1)T. 现将改写为现将改写为上页上页上页上页上页上页下页下页下页下页下页下页)3 . 1().3636(121),334(111),2023(81213312321 xxxxxxxxx或写为或写为x=B0 x+f，其中，其中.,0001236113382012312611111482830 fB上页上页上页上页上页上页下页下页下页下页下页下页 我们任取初始值，例如取我们任取初始值，例如取x(0)=(0, 0, 0)T. 将这些值将这些值代入代入(1.3)式右边式右边(若若(1.3)式为等式即求得方程组的解，式为等式即求得

4、方程组的解，但一般不满足但一般不满足)，得到新的值，得到新的值x(1)=(x1(1), x2(1), x3(1)T=(3.5, 3, 3)T ，再将，再将x(1)分量代入分量代入(1.3)式右边得到式右边得到 x(2)，反复利用这个计算程序，得到一向量序列和一般的计反复利用这个计算程序，得到一向量序列和一般的计算公式算公式(迭代公式迭代公式)(0)(1)( )111(0)(0)(1)(1)( )( )222(0)(1)( )333,kkkkxxxxxxxxxxxxLL上页上页上页上页上页上页下页下页下页下页下页下页)4 . 1(.12/ )3636(,11/ )334(, 8/ )2023()

5、(2)(1)1(3)(3)(1)1(2)(3)(2)1(1 kkkkkkkkkxxxxxxxxx简写为简写为 x(k+1)=B0 x(k) +f，其中其中k表示迭代次数表示迭代次数(k=0,1,2,). 迭代到第迭代到第10次有次有;)999813. 0,999838. 1,000032. 3()10(Tx ).(000187. 0)10()10()10( xx 上页上页上页上页上页上页下页下页下页下页下页下页从此例看出，由迭代法产生的向量序列从此例看出，由迭代法产生的向量序列x(k)逐步逐步逼近方程组的精确解是逼近方程组的精确解是x*=(3,2,1)T. 即有即有 对于任何一个方程组对于任何

6、一个方程组x=Bx+f(由由Ax=b变形得到的变形得到的等价方程组等价方程组)，由迭代法产生的向量序列，由迭代法产生的向量序列x(k)是否一定是否一定逐步逼近方程组的解逐步逼近方程组的解x*呢？回答呢？回答是不一定是不一定. 请同学们请同学们考虑用迭代法解下述方程组考虑用迭代法解下述方程组 . 53, 521221xxxxx(k)x* xxkk)(lim上页上页上页上页上页上页下页下页下页下页下页下页对于给定方程组对于给定方程组x=Bx+f，设有唯一解，设有唯一解x*，则，则 x*=Bx*+f .(1.5)又设又设x(0)为任取的初始向量为任取的初始向量, 按下述公式构造向量序列按下述公式构造

7、向量序列 x(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*就是方程组的解就是方程组的解, 否则称此否则称此迭代法发散迭代法发散.上页上页上页上页上页上页下页下页下页下页下页下页

8、由上述讨论，需要研究由上述讨论，需要研究x(k)的收敛性的收敛性. 引进误引进误差向量差向量,)1()1( xxkk (1.6)减去减去(1.5)式得：式得：(k+1)=B(k) (k=0,1,2, ) 递推得递推得( )(1)(0).kkkBBL 要考察要考察x(k)的收敛性，就要研究的收敛性，就要研究B在什么条件下在什么条件下有有lim(k)=0 (k)，亦即要研究，亦即要研究B满足什么条件时有满足什么条件时有Bk0 0(零向量零向量) (k) . x*=Bx*+f .(1.5) x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)上页上页上页上页上页上页下页下页下页下页下页下页

9、2 基本迭代法基本迭代法其中，其中，A=(aij)Rnn为非奇异矩阵，下面研究任何建为非奇异矩阵，下面研究任何建立立Ax=b的各种迭代法的各种迭代法. 设线性方程组设线性方程组 Ax=b， (2.1) 其中，其中，M为可选择的非奇异矩阵，且使为可选择的非奇异矩阵，且使Mx=d容易求容易求解，一般选择解，一般选择A的某种近似，称的某种近似，称M为为分裂矩阵分裂矩阵. 将将A分裂为分裂为 A=M- -N. (2.2) 上页上页上页上页上页上页下页下页下页下页下页下页 于是，求解于是，求解Ax=b转化为求解转化为求解Mx=Nx+b ，即求解，即求解.11bMNxMxbAx 求求解解可构造一阶定常迭代

10、法可构造一阶定常迭代法(0)(1)( )()(2.3)(0,1,),kkxxBxfkL初始向量 ，其中其中 B=M- -1N=M- -1(M- -A)=I- -M- -1A ， f=M- -1b. 称称 B=I- -M- -1A为迭代法的为迭代法的迭代矩阵迭代矩阵，选取，选取M矩阵，就得矩阵，就得到解到解Ax=b的各种迭代法的各种迭代法. 设设aii 0 (i=1,2,n)，并将，并将A写成三部分写成三部分上页上页上页上页上页上页下页下页下页下页下页下页1121221,11,212,1121,112,121,00000000.nnnnnnn nnnnnnnaaaAaaaaaaaaaaaaDL

11、UMMOOLLLLOMM上页上页上页上页上页上页下页下页下页下页下页下页111212122212LLMMMLnnnnnnaaaaaaAaaa 1122OnnaaDa 2112000MMLnnaLaa1212000LLOMnnaaaU即即A=D- -L- -U上页上页上页上页上页上页下页下页下页下页下页下页2.1 雅可比雅可比(Jacobi)迭代法迭代法 设设aii 0 (i=1,2,n)，选取，选取M为为A的对角元素部分的对角元素部分,即选取即选取M=D(对角阵对角阵)，A=D- -N，由，由(2.3)式得到解方式得到解方程组程组Ax=b的的雅可比雅可比(Jacobi)迭代法迭代法. 又称又称

12、简单迭代法简单迭代法.其中其中B=I- -D- -1A=D- -1(L+U)=J, f=D- -1b. 称称J为解为解Ax=b的的雅可比迭代法的迭代矩阵雅可比迭代法的迭代矩阵.(0)(1)( )()(2.5)(0,1,),L初始向量 ，kkxxBxfk上页上页上页上页上页上页下页下页下页下页下页下页于是雅可比迭代法可写为于是雅可比迭代法可写为矩阵形式矩阵形式bDxULDxkk1)(1)1()( 其其Jacobi迭代矩阵迭代矩阵为为 )(1ULDBJ1121111221222212000nnnnnnnnaaaaaaaaaaaaL LL LMMMMMML L上页上页上页上页上页上页下页下页下页下页

13、下页下页下面给出雅可比迭代法下面给出雅可比迭代法(2.5)的分量计算公式的分量计算公式, 记记( )( )( )( )1(,) ,LLkkkkTinxxxx由雅可比迭代法由雅可比迭代法(2.5)有有,)()()1(bxULDxkk 每一个分量写出来为每一个分量写出来为1(1)( )( )11(1,2, ). Linkkkiiiijjijjijjia xa xa xbin即当即当aii 0时，有时，有1(1)( )( )111() (1,2, ). Linkkkiijjijjijjiiixa xa xbina上页上页上页上页上页上页下页下页下页下页下页下页等等价价方方程程组组其中其中 aii(i

14、) 0 （i=1，2，n）11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba LLML即由方程组即由方程组Ax=b得到的得到的上页上页上页上页上页上页下页下页下页下页下页下页建立的雅可比迭代格式为建立的雅可比迭代格式为(1)( )( )( )11221331111(1)( )( )( )221 12332222(1)( )( )1 1111()1()1()LLMLkkkknnkkkknnkkknnnnnnnnxa xa xa xbaxa xa xa xbaxa xaxba上页上页上页上页上页上页下页下页下页下页下页下页于是，

15、解于是，解Ax=b的雅可比迭代法的计算公式为的雅可比迭代法的计算公式为(0)(0)(0)1(1)( )1(,) ,()/,(2.6)(1,2, ) (0,1,).LLL 表示迭代次数Tnnkkiiijjiijj ixxxxba xaink 由由(2.6)式可知，雅可比迭代法计算公式简单，式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵过程中原始矩阵A始终不变始终不变. 上页上页上页上页上页上页下页下页下页下页下页下页 从Jacobi迭代法的计算过程可知，若向量序列x(k)收敛于方程组的精确解，则显然有x(k

16、+1)比 x(k)更靠近精确解。 事实上Jacobi方法迭代过程的每一步计算是用x(k)的全部分量来计算x(k+1)的所有分量，很显然，在计算x(k+1)的第i个分量 ) 1()1(ixki时，对已计算出的最新的分量 (1)(1)(1)121,Lkkkixxx可能没有利用，而这些最新计算出来的(1)(1,2,1)Lkjxji可能比旧的分量 ( )(1,2,1)Lkjxji更接近于精确解，因此对这(1)(1,2,1)Lkjxji些新分量 加以利用是合理的。就得到了所谓求解方程组AX=b的的高斯赛德尔高斯赛德尔（Gauss-Seidel）迭代法.2.2 高斯赛德尔迭代法高斯赛德尔迭代法上页上页上页

17、上页上页上页下页下页下页下页下页下页在在 Jacobi 迭代中，计算迭代中，计算 xi(k+1)(2 i n)时时，使用使用xj(k+1)代替代替xj(k) (1 j i- -1)，即有即有(1)( )( )( )11221331111(1)(1)( )( )22112332222(1)(1)(1)11111()1()1()LLMLkkkknnkkkknnkkknnnnnnnnxa xa xa xbaxa xa xaxbaxa xaxba建建立立迭迭代代格格式式上页上页上页上页上页上页下页下页下页下页下页下页或缩写为或缩写为称为称为高斯高斯塞德尔塞德尔(Gauss Seidel)迭代法迭代法.

18、bLDxULDxkk1)(1)1()()( 其其Gauss Seidel迭代矩阵迭代矩阵为为BG = (D- -L)- -1U于是高斯于是高斯塞德尔迭代法可写为塞德尔迭代法可写为矩阵形式矩阵形式1(1)(1)( )111() (1,2, ). Linkkkiijjijjijjiiixa xa xbina上页上页上页上页上页上页下页下页下页下页下页下页 这就是说，选取分裂矩阵这就是说，选取分裂矩阵M为为A的下三角部分的下三角部分,即选取即选取M= D- -L(下三角阵下三角阵)，A=M- -N，由，由(2.3)式得到式得到解解Ax=b的的高斯高斯塞德尔塞德尔(Gauss Seidel)迭代法迭代

19、法.其中其中B=I- -(D- -L)- -1A= (D- -L)- -1U=G, f=(D- -L)- -1b. 称矩称矩阵阵G=(D- -L)- -1U为解为解Ax=b的的高斯高斯塞德尔塞德尔迭代法的迭迭代法的迭代矩阵代矩阵.)7 . 2(), 1 , 0()()()1()0( kfBxxxkk，初初始始向向量量上页上页上页上页上页上页下页下页下页下页下页下页由由高斯高斯塞德尔迭代法塞德尔迭代法(2.7)有有,)()()1(bUxxLDkk 每一个分量写出来为每一个分量写出来为1(1)(1)( )11(1,2, ). Linkkkiiiiijjijjjjia xba xa xin即当即当a

20、ii 0时，有时，有(与前面一样的式子与前面一样的式子)1(1)(1)( )111() (1,2, ). Linkkkiiijjijjjjiiixba xa xina或或,)()1()1(bUxLxDxkkk 上页上页上页上页上页上页下页下页下页下页下页下页于是，解于是，解Ax=b的的高斯高斯塞德尔塞德尔迭代法的计算公式为迭代法的计算公式为(0)(0)(0)11(1)(1)( )11(,)(),()/,(2.8)(1,2, ) (0,1,). LLL初始向量表示迭代次数Tninkkkiiijjijjiijj ixxxxba xa xaink或或(0)(0)(0)1(1)( )1(1)( )1(

21、,) ,(2.9)()/,(1,2, ) (0,1,).LLLTnkkiiiinkkiiijjijjiijj ixxxxxxxba xa xaink上页上页上页上页上页上页下页下页下页下页下页下页 雅可比迭代法雅可比迭代法不使用变量的最新信息计算不使用变量的最新信息计算xi(k+1)，而，而由由高斯高斯塞德尔迭代公式塞德尔迭代公式(2.8)可知，计算可知，计算x(k+1)的第的第 i个个分量分量xi(k+1)时，利用了已经计算出的最新分量时，利用了已经计算出的最新分量xj(k+1) (j=1,2,i- -1). 可看作可看作雅可比迭代法雅可比迭代法的一种改进的一种改进. 由由(2.8)可知，可

22、知，高斯高斯塞德尔迭代公式塞德尔迭代公式每迭代一次只需计算一次每迭代一次只需计算一次矩阵与向量的乘法矩阵与向量的乘法.Jacobi iterationGauss-Seidel iteration计算计算x(k+1)时需要时需要x(k)的所有分量，因此的所有分量，因此需开两组存储单元需开两组存储单元分别存放分别存放x(k)和和x(k+1)计算计算xi(k+1)时只需要时只需要x(k)的的i+1n个分量，因此个分量，因此x(k+1)的的前前i个分量可存贮在个分量可存贮在x(k)的的前前i个分量所占的存储单元，个分量所占的存储单元，无需开两组存储单元无需开两组存储单元上页上页上页上页上页上页下页下页

23、下页下页下页下页 例例2 用用高斯高斯塞德尔迭代法塞德尔迭代法解例解例1的方程组的方程组(1.2).(1)( )( )123(1)(1)( )213(1)(1)(1)312(2032)/8,(334)/11,(3663)/12.(0,1,2,).Lkkkkkkkkkxxxxxxxxxk 解解 用用高斯高斯塞德尔迭代公式：塞德尔迭代公式：取取x(0)=(0, 0, 0)T.迭代到第迭代到第7次有次有;)9999930. 0,9999987. 1,000002. 3()7(Tx .1002. 24)7()7( xx 上页上页上页上页上页上页下页下页下页下页下页下页 由此例可知，用由此例可知，用高斯

24、高斯塞德尔迭代法塞德尔迭代法，雅可比雅可比迭代法迭代法解线性方程组解线性方程组(1.2)(且取且取x(0)=0)均收敛，而均收敛，而高高斯斯塞德尔迭代法塞德尔迭代法比比雅可比迭代法雅可比迭代法收敛较快收敛较快(即取相即取相同的同的x(0)，达到同样精度所需迭代次数较少，达到同样精度所需迭代次数较少)，但这结，但这结论只当论只当A满足一定条件时才是对的满足一定条件时才是对的. 说明：说明：Jacobi迭代法的收敛性和迭代法的收敛性和G-S方法的收敛方法的收敛性没有必然的联系，存在前者收敛后者不收敛的方性没有必然的联系，存在前者收敛后者不收敛的方程组，也存在后者收敛二前者不收敛的方程组。程组，也存

25、在后者收敛二前者不收敛的方程组。上页上页上页上页上页上页下页下页下页下页下页下页 例例1 用雅可比迭代法解方程组用雅可比迭代法解方程组 2 . 453 . 82102 . 7210321321321xxxxxxxxx )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx.3 . 12 . 11 . 1 x解解确确精精 解：解： Jacobi 迭代格式为迭代格式为上页上页上页上页上页上页下页下页下页下页下页下页kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.

26、1511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.299997 )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx取取 x(0)=(0,0,0)T 计算计算结果结果如下：如下：上页上页上页上页上页上页下页下页下页下页下页下页 解：解：Gauss-Seidel 迭代格式为迭代格式为 )2 . 4(51)3 . 82(101)2 . 72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxx

27、xxxxxx 例例2 用用GaussSeidel 迭代法解上题迭代法解上题. 2 . 453 . 82102 . 7210321321321xxxxxxxxx上页上页上页上页上页上页下页下页下页下页下页下页取取 x(0)=(0,0,0)T 计算计算结果结果如下：如下：kx1(k) x2(k)x3(k)10.720.9021.164481.0999981.1999991.3 )2 . 4(51)3 . 82(101)2 . 72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx上页上页上页上页上页上页下页下页下页下页下页下页 定义定义2

28、 设有矩阵序列设有矩阵序列 Ak=(aij(k)Rnn 及及A=(aij)Rnn，如果，如果n2个数列极限存在且有个数列极限存在且有)., 2 , 1,(lim)(njiaaijkijk 则则Ak称收敛于称收敛于A，记为，记为lim (k).例例4 设有矩阵序列设有矩阵序列Ak, 其中其中Ak=Bk,而而,0,02,011222 kkkkkBBB 且设且设|1，考查矩阵序列极限，考查矩阵序列极限.解解 显然显然, 当当|1时时, 则有则有.0000limlim kkkkBA矩阵收敛有关结论矩阵收敛有关结论上页上页上页上页上页上页下页下页下页下页下页下页矩阵序列极限概念可以用矩阵算子范数来描述矩

29、阵序列极限概念可以用矩阵算子范数来描述. 定理定理1 其中其中|为为矩阵的任意一种算子范数矩阵的任意一种算子范数., 0limlim AAAAkkkk证明证明 显然有显然有. 0limlim AAAAkkkk再由矩阵范数的等价性再由矩阵范数的等价性, 则定理对其它算子范数亦对则定理对其它算子范数亦对.定理定理2.limlimAxxARxAAkknkk 都都有有对对证明作为练习证明作为练习.上页上页上页上页上页上页下页下页下页下页下页下页 定理定理3 设设B=(bij)Rnn，则，则limBk=0 (k)(零零矩阵矩阵)的充分必要条件是矩阵的充分必要条件是矩阵B的谱半径的谱半径 (B)1.证明证

30、明 由矩阵由矩阵B的的若当标准形若当标准形,存在非奇异矩阵存在非奇异矩阵P使使,211JJJJBPPr 其中其中若当若当(Jordan)块块,11iinniiiiJ 上页上页上页上页上页上页下页下页下页下页下页下页且，显然有且，显然有nnrii 1其中其中,11 PPJBPJPBkk.21 krkkkJJJJ)., 2 , 1( , 0lim0lim0limriJJBkikkkkk 于于是是上页上页上页上页上页上页下页下页下页下页下页下页 显然有显然有, Et,0=I, Et,k=0(当当kt)，(Et,1)k= Et,k. 由于由于Ji=I+Et,1 ，因此，因此下面考查下面考查Jik的情况

31、的情况. 引进记号引进记号).(000,ittktntRktIE 101 ,01 ,1 ,)()()(tjjtjkijkkjjtjkijkktikiECECEIJ 上页上页上页上页上页上页下页下页下页下页下页下页)., 2 , 1(11)2(211)1(12211riCCCCCCttkikiktkitkkikkitkitkkikkikki 其中其中.!)1()1()!( !jjkkkjkjkCjk 得得到到利利用用极极限限),0, 10(0lim rcckkrk. 10lim jkjkkC. 1)(), 2 , 1( 10lim BriJikik 即即所所以以上页上页上页上页上页上页下页下页下

32、页下页下页下页3 迭代法的收敛性迭代法的收敛性3.1 一阶定常迭代法的基本定理一阶定常迭代法的基本定理其中，其中，A=(aij)Rnn为非奇异矩阵，记为非奇异矩阵，记x*为为(3.1)精确精确解，且设有等价的方程组解，且设有等价的方程组 设线性方程组设线性方程组 Ax=b， (3.1) 于是于是.fBxxbAx )2 . 3(.fBxx 设有解设有解Ax=b的一阶定常迭代法的一阶定常迭代法)3 . 3(.)()1(fBxxkk 上页上页上页上页上页上页下页下页下页下页下页下页有意义的问题是：迭代矩阵有意义的问题是：迭代矩阵B满足什么条件时，满足什么条件时，由迭代法产生的向量序列由迭代法产生的向

33、量序列x(k)收敛到收敛到x*. 引进引进误差向量误差向量)., 2 , 1 , 0()()( kxxkk 由由(3.3)式减式减(3.2)得到得到误差向量的递推公式误差向量的递推公式)., 2 , 1 , 0(,)0()()()1( kBBkkkk 由由1节可知，研究迭代法节可知，研究迭代法(3.3)收敛性问题就是要研究收敛性问题就是要研究迭代矩阵迭代矩阵B满足什么条件时，有满足什么条件时，有:).)(0 kBk零零矩矩阵阵当迭代法收敛时，如何衡量收敛速度？当迭代法收敛时，如何衡量收敛速度？上页上页上页上页上页上页下页下页下页下页下页下页由定理由定理3证明中可知，如果证明中可知，如果 (B)

34、1且且 (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)，记，记.,lim)(fBxxxxkk 则则(k)=Bk(0)，故故.)0()( kkB 上页上页上页上页上页上页下页下页下页下页下页下页现设现设B为对称矩阵，则有为对称矩阵，则有.)(2)

35、0(2)0(22)( kkkBB 下面确定使初始误差缩小下面确定使初始误差缩小10-s所需的迭代次数所需的迭代次数, 即使即使.10)(skB 取对数，得到所需最少迭代次数为取对数，得到所需最少迭代次数为.)(ln10lnBsk 此式说明，满足精度此式说明，满足精度所需迭代次数与所需迭代次数与R=- -ln (B)成反成反比，当比，当 (B)1越小，越小，R=- -ln (B)越大，则满足越大，则满足所需迭所需迭代次数越少，即迭代法收敛越快代次数越少，即迭代法收敛越快. 当迭代矩阵当迭代矩阵B为一为一般矩阵时的讨论可参考相关文献。般矩阵时的讨论可参考相关文献。定义定义5 称称R(B)=- -l

36、n (B)为迭代法为迭代法 x(k+1)=Bx(k)+f (k=0,1,)的的渐近收敛速度渐近收敛速度，简称，简称迭代法收敛速度迭代法收敛速度.上页上页上页上页上页上页下页下页下页下页下页下页 定理定理4(迭代法基本定理迭代法基本定理) 设有方程组设有方程组 x=Bx+f. (3.4) 及一阶定常迭代法及一阶定常迭代法 x(k+1)=Bx(k)+f. (3.5) 对任意选择初始向量对任意选择初始向量x(0)，迭代法，迭代法(3.5)收敛的充要条收敛的充要条件是矩阵件是矩阵B的谱半径的谱半径 (B)1.证明证明 充分性充分性. 设设 (B)1，易知，易知Ax=f(其中其中A=I- -B)有唯一解

37、，记为有唯一解，记为x*，则，则 x*=Bx*+f.误差向量误差向量.,)0()0()0()()( xxBxxkkk 上页上页上页上页上页上页下页下页下页下页下页下页由设由设 (B)1，应用定理，应用定理3，有，有 . 于是对任意于是对任意x(0)有有 ，即，即 .0lim kkB0lim kk xxkk)(lim其中其中x(k+1)=Bx(k)+f . 显然，极限显然，极限x*是方程组是方程组(3.4)的解，的解，且对任意且对任意x(0)有有必要性必要性. 设对任何设对任何x(0)有有0lim kkB).(0)0()()( kBxxkkk ,lim)( xxkk由定理由定理2知知再由定理再由

38、定理3，即得，即得 (B)1.定理定理4是一阶定常迭代法的基本理论是一阶定常迭代法的基本理论.上页上页上页上页上页上页下页下页下页下页下页下页 定理定理3和定理和定理4的结论和起来即为的结论和起来即为 (1) 迭代法迭代法x(k+1)=Bx(k)+f 收敛收敛limBk=O； (2) 迭代法迭代法x(k+1)=Bx(k)+f 收敛收敛 (B)1. 推论推论 设设Ax=b，其中，其中A=D- -L- -U为非奇异矩阵且为非奇异矩阵且D非奇异矩阵，则有非奇异矩阵，则有 (1) Jacobi迭代法迭代法收敛收敛 (J)1, 其中其中J=D- -1(L+U). . (2) G- -S迭代法迭代法收敛收

39、敛 (G)1, 其中其中G=(D- -L)- -1U. . (3) SOR迭代法迭代法收敛收敛 (L)1, 其中其中L=(D- -L)- -1(1- -)D+U. . 上页上页上页上页上页上页下页下页下页下页下页下页 例例5 考察用考察用Jacobi方法解方程组方法解方程组(1.2)的收敛性的收敛性. 解解 因为方程组因为方程组(1.2)的矩阵的矩阵A及迭代矩阵及迭代矩阵J为为解得解得, 0039772727. 0034090909. 0)det(317638833 JI,3445. 01841. 0,3445. 01841. 0,3082. 0321ii . 13592. 0, 13082.

40、 0321 即即 (J)1. ,62, 1 这说明用迭代法解此方程组这说明用迭代法解此方程组不收敛不收敛. 迭代法的基本定理在理论上是重要的，根据谱迭代法的基本定理在理论上是重要的，根据谱半径的性质半径的性质 (B)|B|，下面利用矩阵，下面利用矩阵B的范数建立的范数建立判别迭代法收敛的充分条件判别迭代法收敛的充分条件.上页上页上页上页上页上页下页下页下页下页下页下页 定理定理5(迭代法收敛的充分条件迭代法收敛的充分条件) 设有方程组设有方程组 x=Bx+f， B=(bij)Rnn，及一阶定常迭代法及一阶定常迭代法 x(k+1)=Bx(k)+f. 如果有如果有B的某种算子范数的某种算子范数|B

41、|=q1 ，则，则 (1) 迭代法迭代法收敛，即对任取收敛，即对任取x(0)有有.,lim)(fBxxxxkk 且且.)2()0()(xxqxxkk .1)3()1()()( kkkxxqqxx.1)4()0()1()(xxqqxxkk 上页上页上页上页上页上页下页下页下页下页下页下页证明证明 (1)由基本定理由基本定理4结论结论(1)是显然的是显然的.(2) 显然有关系式显然有关系式x*- -x(k+1)=B(x*- -x(k) 及及x(k+1) x(k)=B(x(k) x(k- -1).于是有于是有 (a) |x(k+1) x(k)|q|x(k) x(k- -1)|; (b) |x*- -

42、x(k+1)|q|x*- -x(k)|.反复利用反复利用(b)即得即得(2)(3) 考查考查 |x(k+1) x(k)|=|x*x(k)(x*x(k+1)| |x*x(k)| x*x(k+1)| (1q)|x*x(k)|.111)1()()()1()( kkkkkxxqqxxqxx即得即得 (4) 利用利用(3)的结果反复利用的结果反复利用(a)，则得到，则得到(4). 即即 .11)0()1()1()()(xxqqxxqqxxkkkk 上页上页上页上页上页上页下页下页下页下页下页下页3.2 关于解某些特殊方程组迭代法的收敛性关于解某些特殊方程组迭代法的收敛性 在科学及工程计算中，要求解方程组

43、在科学及工程计算中，要求解方程组Ax=b，其，其矩阵矩阵A常常具有某些特性常常具有某些特性. 例如，例如，A具有对角占优性具有对角占优性质或质或A为不可约阵，或为不可约阵，或A是对称正定阵，下面讨论用是对称正定阵，下面讨论用基本迭代法解这些方程组的收敛性基本迭代法解这些方程组的收敛性.定义定义3(对角占优阵对角占优阵) 设设A=(aij)nn ,如果如果A的元素满足的元素满足 (1)., 2 , 1(1niaanijjijii称称A为为严格严格(按行按行)对角占优阵对角占优阵. (2)., 2 , 1(1niaanijjijii 且至少有一个不等号严格成立，称且至少有一个不等号严格成立，称A为

44、为弱弱(按行按行)对角占对角占优阵优阵.上页上页上页上页上页上页下页下页下页下页下页下页 定义定义4(可约与不可约矩阵可约与不可约矩阵) 设设A=(aij)nn (n2)，如果存在置换阵如果存在置换阵P使使)6 . 3(,0221211 AAAAPPT其中其中A11为为r阶方阵，阶方阵，A22为为n- -r阶方阵阶方阵(1rn)，则称，则称A为为可约矩阵可约矩阵. 否则，如果不存在这样置换阵否则，如果不存在这样置换阵P使使(3.6)式成立，则称式成立，则称A为为不可约矩阵不可约矩阵. A为可约矩阵意即为可约矩阵意即A可经过若干行列重排化为可经过若干行列重排化为(3.6)或或Ax=b可化为两个低

45、阶方程组求解可化为两个低阶方程组求解(如果如果A经过两行经过两行交换的同时进行相应两列的交换，称对交换的同时进行相应两列的交换，称对A进行一次行进行一次行列重排列重排).上页上页上页上页上页上页下页下页下页下页下页下页 事实上，由事实上，由Ax=b可化为可化为PTAP(PTx)=PTb. 于是，求解于是，求解Ax=b化为求解化为求解且记且记 ,其中其中yi, di为为r维向量维向量. 2121,ddbPdyyxPyTT .,22221212111dyAdyAyA由上式第由上式第2个方程组求出个方程组求出y2,再代入第再代入第1个方程组求出个方程组求出y1. 显然，如果显然，如果A所有元素都非零

46、，则所有元素都非零，则A为不可约阵为不可约阵.上页上页上页上页上页上页下页下页下页下页下页下页 例例7 设有矩阵设有矩阵),(.4110140110410114,11122211都都不不为为零零iiinnnnncbaBbacbacbacbA 则则A, B都是不可约矩阵都是不可约矩阵.上页上页上页上页上页上页下页下页下页下页下页下页 定理定理6(对角占优定理对角占优定理) 如果如果A=(aij)nn为为严格对角严格对角占优矩阵占优矩阵或或A为为不可约弱对角占优矩阵不可约弱对角占优矩阵，则，则A非奇异。非奇异。 证明证明 只就只就A为为严格对角占优矩阵严格对角占优矩阵证明此定理证明此定理. 采用反

47、证法，如果采用反证法，如果det(A)=0，则，则Ax=b有非零解，记有非零解，记为为x=(x1, x2,xn)T，则，则 .0max1 inxkxx 由齐次方程组第由齐次方程组第k个方程个方程, 01 njjijxa则有则有,|111 nkjjkjknkjjjkjnkjjjkjkkkaxxaxaxa即即,1 nkjjkjkkaa这与假设矛盾，故这与假设矛盾，故det(A)0.上页上页上页上页上页上页下页下页下页下页下页下页 定理定理7 设方程组设方程组Ax=b，如果，如果(1) A为为严格对角占优阵，则解严格对角占优阵，则解Ax=b的的Jacobi迭迭代法代法, Gauss- -Seidel

48、 迭代法迭代法均收敛均收敛.(2) A为弱对角为弱对角占优阵占优阵，且，且A为不可约矩阵为不可约矩阵, 则则解解Ax=b的的Jacobi迭代法迭代法, Gauss- -Seidel 迭代法迭代法均收敛均收敛. 证明证明 只证只证(1)，(2)作为练习作为练习.因为因为A是严格对角占优阵，所以是严格对角占优阵，所以aii0(i=1,n).1121111221122221200()0nnnnnnnnaaaaaaaaJDLUaaaaLLMMOML则则|J| 1，所以所以 Jacobi 迭代法迭代法收敛收敛.Jacobi迭代阵迭代阵上页上页上页上页上页上页下页下页下页下页下页下页)(det)det(1

49、ULDIGI . 0)(det)det(1 ULDLD det ()0( )DLU 下面证明下面证明GS迭代法迭代法收敛收敛.由由G=(D- -L)- -1U，得，得下面证明下面证明| |1. 若不然若不然, 即即| | 1, 则则. ), 2 , 1(|111 ijnijijijijijiiniaaaa 由于由于1det() 0DL即矩阵即矩阵 ULD)( .212222111211 nnnnnnaaaaaaaaa 是严格对角占优矩阵，故可逆，这与是严格对角占优矩阵，故可逆，这与(*) 式矛盾，所以式矛盾，所以| |1, 从而从而 (G)0.上页上页上页上页上页上页下页下页下页下页下页下页)

50、.(),(),(),(ibayLyLyyyyLT 所以所以| |1, 从而从而 (G)0为为松弛因子松弛因子，建立迭代格式如下，建立迭代格式如下1(1)(1)( )11(1)( )(1)( )(1)( )()/,(1)(),(1,2,). %Linkkkiiijjijjiijj ikkkkkkiiiiiixba xa xaxxxxxxin 即即./ )()(11)1()()1(iinijkjijijkjijikikiaxaxabxx 逐次超松弛法逐次超松弛法(SOR方法方法)或改写为或改写为, 2 , 1 , 0), 2 , 1(./ )()1 ()(11)1()()1( kniaxaxabx

51、xiinijkjijijkjijikiki 称为称为逐次超逐次超松松弛迭代法弛迭代法，简，简称称SOR方法方法. =1就是就是G-S迭代法迭代法上页上页上页上页上页上页下页下页下页下页下页下页.)()1()(1)(1)1(bLDxUDLDxkk 其其逐次超逐次超松弛迭代矩阵松弛迭代矩阵为为.)1()(1UDLDB 逐次超松弛法逐次超松弛法可写为可写为矩阵形式矩阵形式 下面用矩阵方法推导，选取分裂矩阵下面用矩阵方法推导，选取分裂矩阵M为带参为带参数的下三角矩阵数的下三角矩阵从而得到解从而得到解Ax=b的的逐次超松弛迭代法逐次超松弛迭代法 (Successive Over Relaxation M

52、ethod，简称，简称SOR方法方法).).(1LDM 其中其中 0为可选择的为可选择的松弛因子松弛因子. 于是，由于是，由(2.3)可构造一个迭代法，其迭代矩阵为可构造一个迭代法，其迭代矩阵为.)1()()(11UDLDALDIL 上页上页上页上页上页上页下页下页下页下页下页下页)10. 2(), 1 , 0()()()1()0( kfxLxxkk ，初初始始向向量量 解解Ax=b的的SOR方法方法为为.其中其中.)(,)1()(11bLDfUDLDL 下面给出解下面给出解Ax=b的的SOR方法方法的分量计算公式的分量计算公式. 记记,),()()()(1)(Tknkikkxxxx 由由(2

53、.10)式可得式可得,)1()()()1(bxUDxLDkk ).()()()1()()1(kkkkkDxUxLxbDxDx 上页上页上页上页上页上页下页下页下页下页下页下页由此，得到解由此，得到解Ax=b的的SOR方法方法的计算公式的计算公式或或)11. 2(.), 2 , 1 , 0;, 2 , 1(/ )()1 (,),()(11)1()()1()0()0(1)0( 为为松松弛弛因因子子 kniaxaxabxxxxxiinijkjijijkjijikikiTn .), 2 , 1 , 0;, 2 , 1()12. 2(/ )(,),()(11)1()()1()0()0(1)0(为为松松弛

54、弛因因子子 kniaxaxabxxxxxxxiinijkjijijkjijiiikikiTn上页上页上页上页上页上页下页下页下页下页下页下页 (1) 显然，当显然，当 =1时即为时即为GaussSeidel 迭代法迭代法. (2) SOR方法方法每迭代一次主要运算量是计算一次每迭代一次主要运算量是计算一次矩阵与向量的乘法矩阵与向量的乘法. (3) 当当 1时，称为时，称为超松弛法超松弛法；当；当 1时，称为时，称为低低松弛法松弛法. (4) 在计算机实现时可用在计算机实现时可用 )()1(11maxmaxkikiniinixxx控制迭代终止，或用控制迭代终止，或用 )()(kkAxbr控制迭代

55、终止控制迭代终止.上页上页上页上页上页上页下页下页下页下页下页下页 SOR迭代法迭代法是是GaussSeidel 迭代法迭代法的一种修正，的一种修正，可由下述思想得到可由下述思想得到. 设已知设已知x(k)及已计算及已计算x(k+1)的分量的分量xj(k+1) (j=1,2,i- -1).)14. 2().()1 ()()1()()1()()1(kikikikikikixxxxxx (1) 首先用首先用GaussSeidel 迭代法迭代法定义辅助量定义辅助量 ,)1( kix)13. 2(./ )(1)(11)1()1(iinijkjijijkjijikiaxaxabx (2) 再由再由 与与 加权平均定义加权平均定义 ，即，即)1( kix)(kix)1( kix将将(2.13)代入代入(2.14)得到解得到解Ax=b的的SOR迭代迭代(2.11)式式.例例3 用用SOR迭代法迭代法解方程组解方程组.上页上页上页上页上页上页下页下页下页下页下页下页定理定理8(SOR方法收敛的必要条件方法收敛的必要条件) 设解设解方程组方程组 Ax=b的的SOR迭代法迭代法收敛，则收敛，则0 2.