雅克比高斯赛德尔迭代法

--WORD格式--可编辑------第八节雅可比迭代法与高斯—塞德尔迭代法一雅可比迭代法设线性方程组bAx(1)的系数矩阵A可逆且主对角元素nna,...,a,a2211均不为零,令nna,...,a,adiagD2211并将A分解成DDAA(2)从而(1)可写成bxADDx令11fxBx其中bDf,ADIB1111.(3)以1B为迭代矩阵的迭代法(公式)111fxBxkk(4)称为雅可比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为,...,,k,n,...,ixabaxnijj)k(jjiiii)k(i21021111(5)其中Tnx,...x,xx002010为初始向量.由此看出,雅可比迭代法公式简单,每迭代一次只需计算一次矩阵和向量的乘法.在电算时需要两组存储单元,以存放kx及1kx.例1例1用雅可比迭代法求解下列方程组2453821027210321321321.xxx.xxx.xxx解将方程组按雅可比方法写成840202083020107202010213312321.x.x.x.x.x.x.x.x.x取初始值TT,,,x,x,xx0000302010按迭代公式--WORD格式--可编辑------840202083020107202010211331123211.x.x.x.x.x.x.x.x.xkkkkkkkkk进行迭代，其计算结果如表1所示表1k01234567kx100.720.9711.0571.08531.09511.0983…kx200.831.0701.15711.18531.19511.1983…kx300.841.1501.24821.28281.29411.2980…二高斯—塞德尔迭代法由雅可比迭代公式可知,在迭代的每一步计算过程中是用kx的全部分量来计算1kx的所有分量,显然在计算第i个分量1kix时,已经计算出的最新分量1111kikx,...,x没有被利用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第1k次近似1kx的分量1kjx加以利用,就得到所谓解方程组的高斯—塞德（Gauss-Seidel）迭代法.把矩阵A分解成ULDA(6)其中nna,...,a,adiagD2211,U,L分别为A的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成bUxxLD即22fxBx其中bLDf,ULDB1212(7)以2B为迭代矩阵构成的迭代法(公式)221fxBxkk(8)称为高斯—塞德尔迭代法(公式),用量表示的形式为,...,,k,n,,ixaxabaxijnij)k(jij)k(jijiii)k(i21021111111(9)由此看出,高斯—塞德尔迭代法的一个明显的优点是,在电算时,只需一组存储单元(计算出1kix后kix不再使用,所以用1kix冲掉kix,以便存放近似解.例2例2用高斯——塞德尔迭代法求解例1.--WORD格式--可编辑------解取初始值TT,,,x,x,xx0000302010，按迭代公式840202083020107202010121113311123211.x.x.x.x.x.x.x.x.xkkkkkkkkk进行迭代，其计算结果如下表2表2k01234567kx100.721.043081.093131.099131.099891.099991.1kx200.9021.167191.195721.199471.199931.199991.2kx301.16441.282051.297771.299721.299961.31.3从此例看出,高斯—塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需迭代次数少),但这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯—塞德尔迭代法却是发散的.三迭代收敛的充分条件定理1在下列任一条件下,雅可比迭代法(5)收敛.①111nijjiiijiaamaxB;②1111nijiiiijjaamaxB;③111njiijjijjTaamaxADI定理2设21BB,分别为雅可比迭代矩阵与高斯—塞德尔迭代矩阵,则12BB(10)从而，当111nijjiiijiaamaxB时，高斯—塞德尔迭代法(8)收敛.证明由21BB,的定义,它们可表示成ULDB11UDLDIULDB11112用e表示n维向量T,...,,e111,则有不等式eBeB11--WORD格式--可编辑------UDLDB111这里,记号｜·｜表示其中矩阵的元素都取绝对值,而不等式是对相应元素来考虑的,于是IeBLDIeLDBeUD111111容易验证011nnLDLD所以,LDI1及LDI1可逆，且1111111111LDILD...LDILD...LDILDInnILDI11从而有eIBLDILDIeUDLDIeB111111121eBeLDIIBI11111因此必有12BB因为已知11B所以12B.即高斯—塞德尔迭代法收敛.若矩阵A为对称，我们有定理3若矩阵A正定,则高斯—塞德尔迭代法收敛.证明把实正定对称矩阵A分解为TLLDATLU,则D为正定的,迭代矩阵TLLDB12设是2B的任一特征值,x为相应的特征向量,则xxLLDT1以LD左乘上式两端,并由TLLDA有AxxLT1用向量x的共轭转置左乘上式两端,得AxxxLxTTT1(11)求上式左右两端的共轭转置,得AxxxLxTT1以1和1分别乘以上二式然后相加,得--WORD格式--可编辑------AxxxLLxTTT211由TLLDA,得AxxxADxTT211即AxxxLxTT2211(12)因为A和D都是正定的,且x不是零向量,所以由(11)式得1,而由(12)式得012,即1,从而12B,因而高斯—塞德尔迭代法收敛.定义1设nnijaA为n阶矩阵.①①如果n,...,i,aanijijijii21(13)即A的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵.②②如果n,...,i,aanijijijii21且至少有一个不等式严格成立,则称A为弱对角优势矩阵.例如310131012是严格对角优势矩阵，310121011是弱对角优势矩阵.定义2设nnijaA是n阶矩阵，如果经过行的互换及相应列的互换可化为2212110AAA,即存在n阶排列矩阵P,使2212110AAAAPPT其中2211A,A为方阵，则称A是可约的,否则称A为不可约的.A是可约矩阵,意味着bAx可经过若干次行列重排,化为两个低阶方程组,事实上,bAx可化为bPxPAPPTTT,记2121dddbP,yyyxPTT于是，求解bAx化为求解22221212111dyAdyAyA可以证明,如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则A是非奇异的.--WORD格式--可编辑------定理4如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则对任意0x,雅可比迭代法(4)与高斯—塞德尔迭代法(8)均为收敛的.证明下面我们以A为不可约弱对角优势矩阵为例，证明雅可比迭代法收敛，其他证明留给读者.要证明雅可比迭代法收敛，只要证11B,1B是迭代矩阵.用反证法,设矩阵1B有某个特征值,使得1,则01BIdet,由于A不可约,且具有弱对角优势，所以1D存在，且DADDADIIBI111从而0DADdet另一方面，矩阵DAD与矩阵A的非零元素的位置是完全相同的，所以DAD也是不可约的,又由于1,且A弱对角优势，所以n,...,i,aaanijijijiiii21并且至少有一个i使不等号严格成立.因此,矩阵DAD弱对角优势，故DAD为不可约弱对角优势矩阵.从而0DADdet矛盾，故1B的特征值不能大于等于1，定理得证.