《解线性方程组的迭代法.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代法.ppt（79页珍藏版）》请在金锄头文库上搜索。
1、上页上页下页下页第第6章章 解线性方程组的迭代方法解线性方程组的迭代方法6.1 迭代法的基本概念迭代法的基本概念6.2 雅可比迭代法与高斯雅可比迭代法与高斯-赛德尔迭代法赛德尔迭代法6.3 超松弛迭代法超松弛迭代法6.4* 共轭迭代法共轭迭代法上页上页下页下页其中其中A为非奇异矩阵为非奇异矩阵, 当当A为为低阶稠密矩阵低阶稠密矩阵时时, 第第5章讨论的选主元消去法是有效的章讨论的选主元消去法是有效的. 但对于但对于大型稀疏大型稀疏矩阵方程组矩阵方程组(A的阶数的阶数n很大很大 104，但，但零元素较多零元素较多), 利用迭代法求解是合适的利用迭代法求解是合适的. 本章将介绍迭代法的一些基本理论
2、及本章将介绍迭代法的一些基本理论及雅可比雅可比迭代法迭代法，高斯高斯-赛德尔迭代法赛德尔迭代法，超松弛迭代法超松弛迭代法，而，而超松弛迭代法应用很广泛。超松弛迭代法应用很广泛。 下面举简例，以便了解迭代法的思想下面举简例，以便了解迭代法的思想. 对线性方程组对线性方程组 Ax=b， (1.1) 6.1 迭代法的基本概念迭代法的基本概念6.1.1 引引 言言上页上页下页下页 例例1 求解方程组求解方程组记为记为Ax=b，其中其中此方程组的精确解是此方程组的精确解是x*=(3,2,1)T. 现将现将(1.2)改写为改写为上页上页下页下页或写为或写为x=B0x+f，其中其中上页上页下页下页 我们任取
3、初始值，例如取我们任取初始值，例如取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)，反复利用这个计算程序，得到一向量反复利用这个计算程序，得到一向量序列和一般的计算公式序列和一般的计算公式(迭代公式迭代公式)上页上页下页下页简写为简写为 x(k+1)=B0x(k) +f，其中其中k表示迭代次数
4、表示迭代次数(k=0,1,2,). 迭代到第迭代到第10次有次有上页上页下页下页从此例看出，由迭代法产生的向量序列从此例看出，由迭代法产生的向量序列x(k)逐步逐步逼近方程组的精确解是逼近方程组的精确解是x*=(3,2,1)T. 即有即有 对于任何一个方程组对于任何一个方程组x=Bx+f(由由Ax=b变形得到的变形得到的等价方程组等价方程组)，由迭代法产生的向量序列由迭代法产生的向量序列x(k)是否一定是否一定逐步逼近方程组的解逐步逼近方程组的解x*呢？回答呢？回答是不一定是不一定. 请同学们请同学们考虑用迭代法解下述方程组考虑用迭代法解下述方程组但但但但 x(k)并不是并不是并不是并不是所有
5、的都收所有的都收所有的都收所有的都收敛到解敛到解敛到解敛到解x*！上页上页下页下页对于给定方程组对于给定方程组x=Bx+f，设有唯一解设有唯一解x*，则，则 x*=Bx*+f .(1.5)又设又设x(0)为任取的初始向量为任取的初始向量, 按下述公式构造向量序按下述公式构造向量序列列 x(k+1)=Bx(k)+f , k=0,1,2,.(1.6)其中其中k表示迭代次数表示迭代次数. 定义定义1 (1)对于给定的方程组对于给定的方程组x=Bx+f , 用公式用公式(1.6)逐步代入求近似解的方法称为逐步代入求近似解的方法称为迭代法迭代法(或称为或称为一阶定常迭代法一阶定常迭代法，这里，这里B与与
6、k无关无关). B称为称为迭代矩阵迭代矩阵. (2) 如果如果limx(k) (k )存在存在(记为记为x*), 称此称此迭代迭代法收敛法收敛, 显然显然x*就是方程组的解就是方程组的解, 否则称此否则称此迭代法发迭代法发散散.上页上页下页下页 由上述讨论，需要研究由上述讨论，需要研究x(k)的收敛性的收敛性. 引进误引进误差向量差向量 由由(1.6)减去减去(1.5)式，得式，得 (k+1)=B (k) (k=0,1,2,)，递推得递推得 要考察要考察x(k)的收敛性，就要研究的收敛性，就要研究B在什么条件在什么条件下有下有lim(k)=0 (k)，亦即要研究亦即要研究B满足什么条件时满足什
7、么条件时有有Bk0 0(零矩阵零矩阵) (k) . 上页上页下页下页6.1.2 向量向量序列与矩阵序列的极限序列与矩阵序列的极限 定义定义2 设向量序列设向量序列x(k) Rn, x(k)= (x1(k),xn(k)T,如果存在如果存在x= (x1, x2, , xn)T Rn，使，使则称向量序列则称向量序列x(k)收敛于收敛于x ，记作，记作显然，显然，其中其中 为任一向量范数为任一向量范数.上页上页下页下页 定义定义3 设矩阵序列设矩阵序列Ak=aij(k) Rnn及及A=aij Rnn,如果如果n2个数列极限存在，且有个数列极限存在，且有则称矩阵序列则称矩阵序列Ak收敛于收敛于A ，记作
8、，记作例例2 设有矩阵序列设有矩阵序列且设且设| |1，考察其极限，考察其极限.解解 显然，当显然，当| |(2) 用反证法，假定用反证法，假定B有一个特征值有一个特征值 ,满足满足| | 1,则存在则存在x 0,使使Bx= x,由此可得由此可得|Bkx|= | |k|x|,当当k 时时Bkx不收敛于零向量不收敛于零向量. 由定理由定理2可可知知(1)不成立，从而知不成立，从而知| |1 ，即，即(2)成立成立. (1) limBk =0; (2) (B)1; (3)至少存在一种从属至少存在一种从属的矩阵范数的矩阵范数| ，使，使|B| (3) 根据第根据第5章定理章定理18，对任意，对任意
9、0，存在，存在一种从属范数一种从属范数| ，使，使|B| (B)+ ，由，由(2)有有 (B)0，可使，可使|B| (1) 由由(3) 给出的矩阵范数给出的矩阵范数|B| N 时有时有 证明证明 由第由第5章定理章定理18，对一切，对一切k有有另一方面对任意另一方面对任意 0，记，记显然有显然有 (B )N 时，时，由由 的任意性即得定理结论的任意性即得定理结论.上页上页下页下页6.1.3 迭代法及其收敛性迭代法及其收敛性其中，其中，A=(aij)Rnn为非奇异矩阵，下面研究如何建为非奇异矩阵，下面研究如何建立解立解Ax=b的迭代法的迭代法. 设有线性方程组设有线性方程组 Ax=b，其中，其中
10、，M为可选择的非奇异矩阵，且使为可选择的非奇异矩阵，且使Mx=d容易求容易求解，一般选择解，一般选择A的某种近似，称的某种近似，称M为为分裂矩阵分裂矩阵. 将将A分裂为分裂为 A=M- -N. (1.9) 上页上页下页下页 于是，求解于是，求解Ax=b转化为求解转化为求解Mx=Nx+b ，即求解即求解从而可构造一阶定常迭代法：从而可构造一阶定常迭代法：其中其中 B=M- -1N=M- -1(M- -A)=I- -M- -1A ， f=M- -1b. 称称 B=I- -M- -1A为迭代法的为迭代法的迭代矩阵迭代矩阵，选取，选取M矩阵，就得矩阵，就得到解到解Ax=b的各种迭代法的各种迭代法. 下
11、面给出迭代法下面给出迭代法(1.11)式收敛的充分必要条件式收敛的充分必要条件.也就是求解线性方程组也就是求解线性方程组 x=Bx+ +f. (1.10) 上页上页下页下页 定理定理5(一阶定常迭代法的基本定理一阶定常迭代法的基本定理) 给定线性给定线性方程组方程组(1.10)及一阶定常迭代法及一阶定常迭代法(1.11)式，对任意式，对任意选取初始向量选取初始向量x(0)，迭代法，迭代法(1.11)式收敛的充分必要式收敛的充分必要条件是矩阵条件是矩阵B的谱半径的谱半径 (B)1.由定理由定理2知知limBk=0，再由定理，再由定理3，即得，即得 (B)1. 证明证明 (=) 设设 (B)1，易
12、知，易知Ax=f(其中其中A=I- -B)有有唯一解，记为唯一解，记为x*，则，则 x*=Bx*+ +f.误差向量误差向量 (k)=x(k)- -x*=Bk (0), (0)=x(0)- -x* .由设由设 (B) 设对任意设对任意x(0)有有limx(k)=x*, 其中其中x(k+1)=Bx(k)+ +f. 显然显然, 极限极限x*是线性方程组是线性方程组(1.10)的的解解, 且对任意且对任意x(0)有有 (k)=x(k)- -x*=Bk (0)0 (k ) .上页上页下页下页 例例3 考察线性方程组考察线性方程组(1.2)给出的迭代法给出的迭代法(1.4)式的收敛性式的收敛性. 解解 先
13、求迭代矩阵先求迭代矩阵B0的特征值的特征值. 由特征方程由特征方程可得可得解得解得即即 (B0)1，这说明用迭代法解此方程组不收敛，这说明用迭代法解此方程组不收敛.迭代法的基本定理在理论上是重要的，由于迭代法的基本定理在理论上是重要的，由于 (B) |B|，下面利用矩阵，下面利用矩阵B的范数建立判别迭代法收的范数建立判别迭代法收敛的充分条件敛的充分条件.上页上页下页下页 定理定理6(迭代法收敛的充分条件迭代法收敛的充分条件) 设有线性方程设有线性方程组组x=Bx+ +f， A=(aij)Rnn，及一阶定常迭代法及一阶定常迭代法 x(k+1)=Bx(k)+ +f.如果有如果有B的某种算子范数的某
14、种算子范数|B|=q1，则，则(1) 迭代法收敛，即对任取迭代法收敛，即对任取x(0)有有 limx(k)=x*，且，且 x*=Bx*+ +f.上页上页下页下页 证明证明 由基本定理知，结论由基本定理知，结论(1)是显然的是显然的.(2) 显然有关系式显然有关系式x*- -x(k+1)=B(x*- -x(k)及及 x(k+1)- -x(k)=B(x(k)- -x(k- -1).于是有于是有反复利用反复利用即得即得(2). (4) 反复利用反复利用，则得到，则得到(4).(3) 考察考察即有即有上页上页下页下页注意，定理注意，定理6只给出迭代法只给出迭代法(1.11)式收敛的充分式收敛的充分性，
15、即使条件性，即使条件|B|1对任何常用范数均不成立，迭代对任何常用范数均不成立，迭代序列仍可能收敛序列仍可能收敛. 例例5 迭代法迭代法x(k+1)=Bx(k)+ +f ，其中，其中显然显然|B| =1.1, |B|1=1.2, |B|2=1.043, |B|F=(1.54)1/2,但由于但由于 (B)=0.91，故由此迭代法产生的迭代序列，故由此迭代法产生的迭代序列x(k)是收敛的是收敛的.上页上页下页下页下面考察迭代法下面考察迭代法(1.11)式的收敛速度式的收敛速度. 假定迭代假定迭代法法(1.11)式是收敛的式是收敛的, 即即 (B)1, 由由 (k)=Bk (0), (0)=x(0)
16、- -x*, 得得于是于是根据矩阵从属范数定义，有根据矩阵从属范数定义，有上页上页下页下页所以所以|Bk|是迭代是迭代k次后误差向量次后误差向量 (k)的范数与初始误差的范数与初始误差向量向量 (0)的范数之比的最大值的范数之比的最大值. 这样，迭代这样，迭代k次后，平次后，平均每次迭代误差向量范数的压缩率可看成是均每次迭代误差向量范数的压缩率可看成是|Bk|1/k，若要求迭代若要求迭代k次后有次后有其中其中1，可取，可取=10- -s. 因为因为 (B)1, 故故|Bk|1/k1, 由由|Bk|1/k1/k两边取对数得两边取对数得即即它表明迭代次数它表明迭代次数k与与- -ln|Bk|1/k
17、成反比成反比.即即上页上页下页下页 定义定义4 迭代法迭代法(1.11)式的式的平均收敛速度平均收敛速度定义为定义为平均收敛速度平均收敛速度Rk(B)依赖于迭代次数及所取范数，给依赖于迭代次数及所取范数，给计算分析带来不便，由定理计算分析带来不便，由定理4可知可知lim|Bk|1/k= (B)，所以所以lim Rk(B)=- -ln (B). 定义定义5 迭代法迭代法(1.11)式的式的渐近收敛速度渐近收敛速度定义为定义为R(B)与迭代次数及矩阵与迭代次数及矩阵B取何种范数无关，它反映了取何种范数无关，它反映了迭代次数趋于无穷时迭代法的渐近性质，当迭代次数趋于无穷时迭代法的渐近性质，当 (B)
18、越越小小- -ln (B)越大，迭代法收敛越快，可用越大，迭代法收敛越快，可用作为迭代法作为迭代法(1.11)式所需的迭代次数估计式所需的迭代次数估计.上页上页下页下页例如在例例如在例1中迭代法中迭代法(1.4)式的迭代矩阵式的迭代矩阵B0的谱的谱半径半径 (B0)=0.3592. 若要求若要求则由则由(1.13)式知式知于是有于是有即取即取k=12即可达到要求即可达到要求.上页上页下页下页6.2 雅可比迭代法与高斯雅可比迭代法与高斯- -塞德尔迭代法塞德尔迭代法6.2.1 雅可比迭代法雅可比迭代法将线性方程组将线性方程组(1.1)中的系数矩阵中的系数矩阵A分成三部分分成三部分上页上页下页下页
19、即即A=D- -L- -U上页上页下页下页 设设aii 0 (i=1,2,n)，选取选取M为为A的对角元素部的对角元素部分分,即选取即选取M=D(对角阵对角阵)，A=D- -N，由，由(1.11)式得到式得到解方程组解方程组Ax=b的的雅可比雅可比(Jacobi)迭代法迭代法. 又称又称简单简单迭代法迭代法.其中其中B=I- -D- -1A=D- -1(L+U)J, f=D- -1b. 称称J为解为解Ax=b的的雅可比迭代法的迭代矩阵雅可比迭代法的迭代矩阵.上页上页下页下页于是雅可比迭代法可写为于是雅可比迭代法可写为矩阵形式矩阵形式其其Jacobi迭代矩阵迭代矩阵为为上页上页下页下页下面给出雅
20、可比迭代法下面给出雅可比迭代法(2.2)的分量计算公式的分量计算公式, 记记由雅可比迭代法由雅可比迭代法(2.2)有有每一个分量写出来为每一个分量写出来为即当即当aii 0时，有时，有上页上页下页下页等等价价方方程程组组其中其中 aii 0 (i=1,2,n)即由方程组即由方程组Ax=b得到的得到的上页上页下页下页建立的雅可比迭代格式为建立的雅可比迭代格式为上页上页下页下页于是，解于是，解Ax=b的雅可比迭代法的计算公式为的雅可比迭代法的计算公式为 由由(2.3)式可知，雅可比迭代法计算公式简单，式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算每迭代一次只需计算一
21、次矩阵和向量的乘法且计算过程中原始矩阵过程中原始矩阵A始终不变始终不变. 上页上页下页下页6.2.2 高斯高斯- -塞德尔迭代法塞德尔迭代法在在 Jacobi 迭代中，计算迭代中，计算 xi(k+1)(2 i n)时时，使使用用xj(k+1)代替代替xj(k) (1 j i- -1)，即有即有建建立立迭迭代代格格式式上页上页下页下页或缩写为或缩写为称为称为高斯高斯- -塞德尔塞德尔(Gauss- -Seidel)迭代法迭代法.其其Gauss- -Seidel迭代矩阵迭代矩阵为为G = (D- -L)- -1U于是高斯于是高斯- -塞德尔迭代法可写为塞德尔迭代法可写为矩阵形式矩阵形式上页上页下页
22、下页 这就是说，选取分裂矩阵这就是说，选取分裂矩阵M为为A的下三角部分的下三角部分,即选取即选取M= D- -L(下三角阵下三角阵)，A=M- -N，由，由(2.3)式得到式得到解解Ax=b的的高斯高斯- -塞德尔塞德尔(Gauss- -Seidel)迭代法迭代法.其中其中B=I- -(D- -L)- -1A= (D- -L)- -1UG, f=(D- -L)- -1b. 称称矩阵矩阵G=(D- -L)- -1U为解为解Ax=b的的高斯高斯- -塞德尔塞德尔迭代法的迭代矩迭代法的迭代矩阵阵.上页上页下页下页由由高斯高斯- -塞德尔迭代法塞德尔迭代法(2.4)有有每一个分量写出来为每一个分量写出
23、来为即当即当aii 0时，有时，有(与前面一样的式子与前面一样的式子)或或上页上页下页下页于是，解于是，解Ax=b的的高斯高斯- -塞德尔塞德尔迭代法的计算公式为迭代法的计算公式为或或上页上页下页下页 雅可比迭代法雅可比迭代法不使用变量的最新信息计算不使用变量的最新信息计算xi(k+1)，而由而由高斯高斯- -塞德尔迭代公式塞德尔迭代公式(2.6)可知，计算可知，计算x(k+1)的的第第 i个个分量分量xi(k+1)时，利用了已经计算出的最新分时，利用了已经计算出的最新分量量xj(k+1) (j=1,2,i- -1). 可看作可看作雅可比迭代法雅可比迭代法的一的一种改进种改进. 由由(2.6)
24、可知，可知，高斯高斯塞德尔迭代公式塞德尔迭代公式每迭每迭代一次只需计算一次矩阵与向量的乘法代一次只需计算一次矩阵与向量的乘法.上页上页下页下页算法算法(高斯高斯- -塞德尔迭代法塞德尔迭代法) 设设Ax=b, 其中其中ARnn为非奇异矩阵，且为非奇异矩阵，且aii 0(i=1,2, ,n)，本算法用，本算法用高斯高斯- -塞德尔迭代法塞德尔迭代法解解Ax=b，数组，数组x(n)开始存放开始存放x(0)，后存，后存放放x(k)，N0为最大迭代次数为最大迭代次数.迭代一次，这个算法需要运算次数至多与矩阵迭代一次，这个算法需要运算次数至多与矩阵A的非的非零元素的个数一样多零元素的个数一样多.2. 对
25、于对于k=1,2, ,N0， 对于对于i=1,2, ,n1. xi0.0 (i=1,2, ,n)上页上页下页下页 例例6 用用高斯高斯- -塞德尔迭代法塞德尔迭代法解线性方程组解线性方程组(1.2). 解解 用用高斯高斯- -塞德尔迭代公式：塞德尔迭代公式：取取x(0)=(0, 0, 0)T.迭代到第迭代到第7次有次有上页上页下页下页 由此例可知，用由此例可知，用高斯高斯- -塞德尔迭代法塞德尔迭代法，雅可比迭雅可比迭代法代法解线性方程组解线性方程组(1.2)(且取且取x(0)=0)均收敛，而均收敛，而高高斯斯- -塞德尔迭代法塞德尔迭代法比比雅可比迭代法雅可比迭代法收敛较快收敛较快(即取相即
26、取相同的同的x(0)，达到同样精度所需迭代次数较少达到同样精度所需迭代次数较少)，但这，但这结论只当结论只当A满足一定条件时才是对的满足一定条件时才是对的. 上页上页下页下页 例例1 用雅可比迭代法解方程组用雅可比迭代法解方程组 解：解： Jacobi 迭代格式为迭代格式为上页上页下页下页kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.1511 1.099993 1.199993 1.29999112 1.099998 1.199998 1.299997取取 x(0)=(0,0,0)T 计算计算结果结果如下：如下：上页上页下页下页 解：解：Gauss- -Se
27、idel 迭代格式为迭代格式为 例例2 用用Gauss- -Seidel 迭代法解上题迭代法解上题.上页上页下页下页取取 x(0)=(0,0,0)T 计算计算结果结果如下：如下：kx1(k) x2(k)x3(k)10.720.9021.164481.0999981.1999991.3上页上页下页下页6.2.3 雅可比迭代与高斯雅可比迭代与高斯- -塞德尔迭代收敛性塞德尔迭代收敛性由定理由定理5可立即得到以下结论可立即得到以下结论. 定理定理7 设设Ax=b，其中，其中A=D- -L- -U为非奇异矩阵为非奇异矩阵,且且对角矩阵对角矩阵D也奇异，则也奇异，则(1) 解线性方程组的雅可比迭代法收敛
28、的充要条解线性方程组的雅可比迭代法收敛的充要条件是件是 (J)1，其中，其中J=D- -1(L+U).(2) 解线性方程组的高斯解线性方程组的高斯- -塞德尔迭代法收敛的塞德尔迭代法收敛的充要条件是充要条件是 (G)1，其中，其中G=(D- -L)- -1U.由定理由定理6还可得到雅可比迭代法收敛的充分条件是还可得到雅可比迭代法收敛的充分条件是|J|1. 高斯高斯- -塞德尔迭代法收敛的充分条件是塞德尔迭代法收敛的充分条件是|G|1. 上页上页下页下页在科学及工程计算中，要求解线性方程组在科学及工程计算中，要求解线性方程组Ax=b,其矩阵其矩阵A常常具有某些特性常常具有某些特性. 例如，例如，
29、A具有对角占优性具有对角占优性质或质或A为不可约矩阵，或为不可约矩阵，或A是对称正定矩阵等，下面是对称正定矩阵等，下面讨论解这些方程组的收敛性讨论解这些方程组的收敛性.上页上页下页下页 定义定义6(对角占优阵对角占优阵) 设设A=(aij)nn . (1) 如果如果A的元素满足的元素满足称称A为为严格严格(按行按行)对角占优阵对角占优阵. (2) 如果如果A的元素满足的元素满足且上式至少有一个不等式成立，称且上式至少有一个不等式成立，称A为为弱弱(按行按行)对角对角占优阵占优阵.上页上页下页下页 定义定义7(可约与不可约矩阵可约与不可约矩阵) 设设A=(aij)nn (n2)，如果存在置换阵如
30、果存在置换阵P使使其中其中A11为为r阶方阵，阶方阵，A22为为n- -r阶方阵阶方阵(1rn)，则称则称A为为可约矩阵可约矩阵. 否则，如果不存在这样置换阵否则，如果不存在这样置换阵P使使(2.7)式成立，则称式成立，则称A为为不可约矩阵不可约矩阵. A为可约矩阵意即为可约矩阵意即A可经过若干行列重排化为可经过若干行列重排化为(2.7)或或Ax=b可化为两个低阶方程组求解可化为两个低阶方程组求解(如果如果A经过经过两行交换的同时进行相应两列的交换，称对两行交换的同时进行相应两列的交换，称对A进行一进行一次行列重排次行列重排).上页上页下页下页 事实上，由事实上，由Ax=b可化为可化为PTAP
31、(PTx)=PTb. 于是，求解于是，求解Ax=b化为求解化为求解且记且记 ,其中其中yi, di为为r维维向量向量.由上式第由上式第2个方程组求出个方程组求出y2,再代入第再代入第1个方程组求出个方程组求出y1. 显然，如果显然，如果A所有元素都非零，则所有元素都非零，则A为为不可约阵不可约阵.上页上页下页下页 例例7 设有矩阵设有矩阵则则A, B都是不可约矩阵都是不可约矩阵.上页上页下页下页 定理定理8(对角占优定理对角占优定理) 如果如果A=(aij)nn为为严格对严格对角占优矩阵角占优矩阵或或A为为不可约弱对角占优矩阵不可约弱对角占优矩阵，则，则A为非为非奇异矩阵奇异矩阵. 证明证明
32、只就只就A为为严格对角占优矩阵严格对角占优矩阵证明此定理证明此定理. 采用反证法，假设采用反证法，假设det(A)=0，则则Ax=0有非零解，记有非零解，记为为x=(x1, x2,xn)T，则则 . 由齐次方程组第由齐次方程组第k个方程及条件个方程及条件则有则有即即这与假设矛盾，故这与假设矛盾，故det(A)0.上页上页下页下页 定理定理9 设方程组设方程组Ax=b，如果如果(1) A为为严格对角占优阵严格对角占优阵，则解则解Ax=b的的Jacobi迭迭代法代法, Gauss- -Seidel 迭代法迭代法均收敛均收敛.(2) A为弱对角为弱对角占优阵占优阵，且，且A为不可约矩阵为不可约矩阵,
33、 则则解解Ax=b的的Jacobi迭代法迭代法, Gauss- -Seidel 迭代法迭代法均收敛均收敛. 证明证明 只证只证(1)，(2)作为练习作为练习.因为因为A是严格对角占优阵，所以是严格对角占优阵，所以aii0(i=1,n).则则|J| 1，所以所以 Jacobi 迭代法迭代法收敛收敛.Jacobi迭代阵迭代阵上页上页下页下页 下面证明下面证明GaussSeidel 迭代法迭代法收敛收敛.由由G=(D- -L)- -1U，得得下面证明下面证明| |1. 若不然若不然, 即即| | 1, 则则由于由于所以所以上页上页下页下页即矩阵即矩阵是严格对角占优矩阵，故可逆，这与是严格对角占优矩阵
34、，故可逆，这与(*) 式矛盾，所式矛盾，所以以| |1, 从而从而 (G)0, 则则(1) 解线性方程组解线性方程组Ax=b的的Jacobi迭代法迭代法收敛的收敛的充分条件是充分条件是A及及2D- -A均为正定矩阵均为正定矩阵, 其中其中D=(a11,ann).(2) 解线性方程组解线性方程组Ax=b的的Gauss- -Seidel 迭代法迭代法收敛的充分条件是收敛的充分条件是A正定正定.如果线性方程组系数矩阵如果线性方程组系数矩阵A对称正定，则有以下对称正定，则有以下的收敛定理的收敛定理.定理证明可见文献定理证明可见文献2，其中第，其中第(2)部分为下面部分为下面定理定理12的一部分的一部分
35、. 定理表明若定理表明若A对称正定，则高斯对称正定，则高斯- -塞德尔法一定收敛，但雅可比法不一定收敛塞德尔法一定收敛，但雅可比法不一定收敛.上页上页下页下页我们这里给出我们这里给出(2)的证明的证明. 证证 因为因为A对称，则对称，则A=D- -L- -LT，G=(D- -L)- -1LT，设设 为迭代矩阵为迭代矩阵G =(D- -L)- -1LT的特征值，的特征值，y为为G 的对应的对应 的的特征特征(复复)向量，即有向量，即有 (D- -L)- -1LTy= y，LTy= (D- -L)y，则内积则内积 (LTy, y)= (D- -L)y, y).从而解得从而解得 因为因为A正定，所以
36、正定，所以D也正定，故记也正定，故记(Dy, y)= 0.上页上页下页下页所以所以| |1, 从而从而 (G)1, 故故Gauss- -Seidel迭代法迭代法收敛收敛. 令令 - -(Ly, y)=a+ib，则由复向量内积的性质有则由复向量内积的性质有上页上页下页下页 例例8 在线性方程组在线性方程组Ax=b中，中，证明当证明当- -1/2a1时高斯时高斯- -塞德尔法收敛，而雅可比法塞德尔法收敛，而雅可比法只在只在- -1/2a1/2时才收敛时才收敛. 证明证明 因为当因为当- -1/2a1，雅可比不收敛，此时，雅可比不收敛，此时2D- -A不是正定的不是正定的. 对雅可比法迭代矩阵对雅可
37、比法迭代矩阵当当 (J)=|2a|1，即，即|a|0为可选择的为可选择的松弛因子松弛因子. 于是于是, 由由(1.11)可构造一个迭代法可构造一个迭代法, 其迭代矩阵其迭代矩阵为为上页上页下页下页 解解Ax=b的的SOR方法方法为为.其中其中 下面给出解下面给出解Ax=b的的SOR方法方法的分量计算公式的分量计算公式. 记记由由(3.1)式可得式可得或或上页上页下页下页由此，得到解由此，得到解Ax=b的的SOR方法方法的计算公式的计算公式或或上页上页下页下页 (1) 显然，当显然，当 =1时即为时即为GaussSeidel 迭代法迭代法. (2) SOR方法方法每迭代一次主要运算量是计算一次每
38、迭代一次主要运算量是计算一次矩阵与向量的乘法矩阵与向量的乘法. (3) 当当 1时，称为时，称为超松弛法超松弛法；当；当 1时，称为时，称为低松弛法低松弛法. (4) 在计算机实现时可用在计算机实现时可用控制迭代终止，或用控制迭代终止，或用控制迭代终止控制迭代终止.上页上页下页下页 SOR迭代法迭代法是是GaussSeidel 迭代法迭代法的一种修正的一种修正,可由下述思想得到可由下述思想得到. 设已知设已知x(k)及已计算及已计算x(k+1)的分量的分量xj(k+1) (j=1,2,i- -1). (1) 首先用首先用GaussSeidel 迭代法迭代法定义辅助量定义辅助量 , (2) 再由
39、再由 与与 加权平均定义加权平均定义 ，即，即将将(3.4)代入代入(3.5)得到解得到解Ax=b的的SOR迭代迭代(3.2)式式.上页上页下页下页 例例9 用用SOR方法解线性方程组方法解线性方程组Ax=b 解解 取初始向量取初始向量x(0)=0，迭代公式为，迭代公式为它的精确解为它的精确解为x*=(- -1, - -1, - -1, - -1 )T.上页上页下页下页取取 =1.3，第，第11次迭代结果为次迭代结果为 满足误差满足误差迭代次数迭代次数k1.01.11.21.31.41.51.61.71.81.922171211(最少迭代次数最少迭代次数)1417233353109对对 取其它
40、值，迭代次数如表取其它值，迭代次数如表. 从此例看到，松弛因子选择从此例看到，松弛因子选择得好，会使得好，会使SOR迭代法的收迭代法的收敛大大加速敛大大加速. 本例中本例中 =1.3是是最佳松弛因子最佳松弛因子.上页上页下页下页6.3.2 SOR迭代法的收敛性迭代法的收敛性根据定理根据定理5可知可知SOR迭代法收敛的充分必要条件迭代法收敛的充分必要条件是是 (L )1，而，而 (L )与松弛因子与松弛因子 有关，下面先研究有关，下面先研究 在什么范围内，在什么范围内， SOR迭代法才可能收敛迭代法才可能收敛.定理定理11(SOR方法收敛的必要条件方法收敛的必要条件) 设解设解方程组方程组 Ax
41、=b的的SOR迭代法迭代法收敛，则收敛，则0 2.证明证明 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.上页上页下页下页定理定理11说明解说明解Ax=b的的SOR迭代法迭代法，只有在，只有在(0, 2)范围内取松弛因子范围内取松弛因子 ，才可能收敛，才可能收敛.定理定理12(SOR方法收敛的充分条件方法收敛的充分条件) 设有
42、设有方程组方程组 Ax=b，如果：如果：(1) A为对称为对称正定矩阵正定矩阵，A=D- -L- -LT;(2) 0 2.则则解解方程组方程组 Ax=b的的SOR迭代法迭代法收敛收敛.证明证明 在上述假定下，设迭代矩阵在上述假定下，设迭代矩阵L 的任一特征的任一特征值为值为 ，只要证明只要证明| |0. (3.7) 令令 - -(Ly, y)=a+ib，则由复向量内积的性质有则由复向量内积的性质有上页上页下页下页当当0 2时，有时，有(分子减分母分子减分母)即即L 的任一特征值满足的任一特征值满足| |1, 故故SOR迭代法迭代法收敛收敛.上页上页下页下页定理定理13 设有设有方程组方程组 A
43、x=b，如果：如果：(1) A为为严格对角占优严格对角占优矩阵矩阵(或或A为为弱对角占优不弱对角占优不可约可约矩阵矩阵);(2) 0 1.则则解解方程组方程组 Ax=b的的SOR迭代法迭代法收敛收敛. (不证明不证明)SOR迭代法迭代法的的收敛速度与松弛因子收敛速度与松弛因子 有关，例有关，例9中中也看到不同也看到不同 的的迭代次数差别迭代次数差别.对于对于SOR迭代法迭代法希望选择希望选择松弛因子松弛因子 使迭代过程使迭代过程(3.1)式收敛较快，在理论上即确定式收敛较快，在理论上即确定 opt使使上页上页下页下页对某些特殊类型的矩阵，建立了对某些特殊类型的矩阵，建立了SOR方法最佳松方法最佳松弛因子理论弛因子理论. 例如，对所谓具有例如，对所谓具有“性质性质A”等条件的等条件的线性方程组建立了最佳松弛因子公式线性方程组建立了最佳松弛因子公式其中其中 (J) 为解为解 Ax=b 的雅可比迭代法的迭代矩阵的谱的雅可比迭代法的迭代矩阵的谱半径半径.由于由于6.3.3 块迭代法块迭代法及及6.4 共轭梯度法共轭梯度法是解线性方程组的应用，大家自学是解线性方程组的应用，大家自学.评评 注见书注见书p208页页.
