解线性方程组的迭代法公开课一等奖优质课大赛微课获奖课件.pptx

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