线性方程组的迭代方法

第五章线性方程组迭代解法6.2基本迭代方法6.1.2Jacobi迭代法和Gauss-Seidel迭代法6.2.1迭代公式的构造第五章线性方程组迭代解法第六章线性方程组的迭代解法教学目的1.掌握Jacobi迭代法，G-S迭代法解大型线性方程组的方法及其收敛性的判别方法；2.掌握SOR迭代法及收敛的必要条件(0ω2)；3.了解三种迭代法之间的改进关系从而掌握该思想方法；4.理解迭代法基本定理。教学重点及难点重点是三种迭代法及收敛性的判别方法；难点是迭代法基本定理及三种迭代法收敛定理的证明。第五章线性方程组迭代解法迭代法是一种不断套用一个迭代公式，逐步逼近方程组的精确迭代法优点：⑴计算量小，近似解精度高。考虑问题：⑴如何构造解的有效迭代法？bAx计算量：)(3nO直接法：解低阶稠密线性方程组，解（真解）的方法。适合解大型稀疏线性方程组。•用差分法或有限元法解偏微分方程边值问题时得到的方程组。•电工学中的网络问题；大型稀疏线性方程组⑵占用内存单元较少。⑶设计程序简单（适合计算机计算）。⑵收敛性与收敛速度怎样？第6章线性方程组的迭代解法迭代法在计算机内存和运算两方面，通常都可利用A中有大量零元素的特点。第五章线性方程组迭代解法6.2.1.迭代法的基本思想),,2,1()0(nixi迭代法的基本思想是将线性方程组Ax=b(6.2.1)转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。第五章线性方程组迭代解法设非奇异，，则线性方程组有惟一解，经过变换构造出一个等价同解方程组将上式改写成单步定常迭代式nnRAnRbbAxbAx1xBxf(1)()(0,1,)kkxBxfk选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为单步定常迭代法（B,f都与k无关）.Tnxxxx)0()0(2)0(1)0(,,,第五章线性方程组迭代解法如果存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当时，,则,故是方程组的解。Tknkkkxxxx)()(2)(1)(,,,Tnxxxx**2*1*,,,k(1)()(0,1,)kkxBxfk*)(xxk**xBxf*xbAx第五章线性方程组迭代解法由前而可得：，从而递推得：为讨论收敛性，引进误差向量：.11xxkk1kkB01kkkBBkx亦即B满足什么条件使（零矩阵）。要收敛于。则须考察B在什么条件下，xkx0k0kBk第五章线性方程组迭代解法1231234123423410261125210113815xxxxxxxAxbxxxxxxx简记：例6.1Tx)1,1,2,1(*解：其精确解为：先将Ax=b转化为等价方程组12321343124423(62)/10(253)/11(112)/10(153)/8xxxxxxxxBxfxxxxxxx或第五章线性方程组迭代解法Tx)0,0,0,0()0(迭代公式：选取初始向量经10次迭代解：0002.0:)9998.0,9998.0,9998.1,0001.1()10(*)10(xxxT误差为(1)()()123(1)()()()2134(1)()()()3124(1)()()423(62)/10(253)/11(0,1,2)(112)/10(153)/8kkkkkkkkkkkkkkxxxxxxxkxxxxxxx对于给定的方程组可以构造各种迭代公式,但并非全部收敛。第五章线性方程组迭代解法例6.2用迭代法求解线性方程组352322121xxxx解构造方程组的等价方程组3423212211xxxxxx据此建立迭代公式3423)(2)(1)1(2)(2)(1)1(1kkkkkkxxxxxx0)0(2)0(1xx取计算得,3333,1515,99,33,33)5(2)5(1)4(2)4(1)3(2)3(1)2(2)2(1)1(2)1(1xxxxxxxxxx迭代解离精确解越来越远迭代不收敛1,121xx第五章线性方程组迭代解法6.1.2雅可比（Jacobi）迭代法1雅可比迭代法算法构造例6.３用雅可比迭代法求解方程组3612363311420238321321321xxxxxxxxx解：从方程组的三个方程中分离出和21,xx3x341213111114254183213312321xxxxxxxxx第五章线性方程组迭代解法建立迭代公式341213111114254183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx第五章线性方程组迭代解法取初始向量进行迭代,可以逐步得出一个近似解的序列：（k=1,2,…）直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。TTxxxx)0,0,0(),,()0(3)0(2)0(1)0(),,()(3)(2)(1kkkxxxTTxxxx)9998813.0,999838.1,000032.3(),,()10(3)10(2)10(1)10(第五章线性方程组迭代解法考察一般的方程组，将n元线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111nibxainjjij,,2,11写成若,分离出变量0iia),,2,1(niixnixabaxjnijjijiiii,,2,1)(11第五章线性方程组迭代解法据此建立迭代公式nixabaxnijjkjijiiiki,2,1)(11)()1(上式称为解方程组的Jacobi迭代公式。0iia第五章线性方程组迭代解法2雅可比迭代法的矩阵表示设方程组的系数矩阵A非奇异，且主对角元素，则可将A分裂成bAx),,2,1(0niaii121311121232223132112100000000nnnnnnnnnnaaaaaaaaAaaaaaaa记作A=-L+D-U第五章线性方程组迭代解法即()DxLUxb因为，则),,2,1(0niaii11()xDLUxDb这样便得到一个迭代公式(1)1()1()kkxDLUxDb1()1()kDDAxDbbDxADIk1)(1)(11()JJBIDAfDb令则有(1)()kkJJxBxf（k=0,1,2…）称为雅可比迭代公式,BJ称为雅可比迭代矩阵bAx则等价于()DLUxb第五章线性方程组迭代解法1121111221122221200()0nnJnnnnnnaaaaaaaaBIDAaaaa其中在例5.3中,由迭代公式写出雅可比迭代矩阵为13208841011116301212JBIDA341213111114254183)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx第五章线性方程组迭代解法雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即)(1)(1)(1)(11)(22)(11)1(2)(2)(323)(12122)1(21)(1)(313)(21211)1(1nknnnknknnnknknnkkkknnkkkbxaxaxaaxbxaxaxaaxbxaxaxaax(k=0,1,2,…)第五章线性方程组迭代解法J称为Jacobi迭代法的迭代阵Jacobi迭代法：(0)(1)()111(0,1,)()kkJJJJxxBxfkBIDADLUJfDbTknkikkxxxx),,,,()()()(1)(若记Jacobi迭代法的分量形式：，bMf11,BIMA(5.1.4)称（6.2.2）为解（6.2.1）的Jacobi迭代法，简称J法。(6.2.2)第五章线性方程组迭代解法ni,,2,1,1111)()()1(nijjkjijiijnijkjijkjijikiiixabxaxabxa当时，得到0iia由（6.2.2）有，即bxULDxkk)()1()(求解的Jacobi迭代法计算公式：bAxxabaxxxxnijjkjijiiikiTn)(1),,(1)()1()0()0(1)0(ni,,2,1(6.2.3)表示迭代次数。,,1,0k注：(1)Jacobi迭代法,每迭代一次主要是计算一次矩阵乘向量。)(kBx（2)计算过程中，原始数据A始终不变。(3)计算中需要两组工作单元用来保存及。)(),(nynx)(kx)1(kx前一例6.3即为Jacobi法求解，在此不再举例。第五章线性方程组迭代解法Algorithm:JacobiIterativeMethodSolvegivenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa[][];theentriesb[];theinitialapproximationX0[];toleranceTOL;maximumnumberofiterationsMmax.Output:approximatesolutionX[]oramessageoffailure.Step1Setk=1;Step2While(kMmax)dosteps3-6Step3Fori=1,…,nSet;/*computexk*/Step4IfthenOutput(X[]);STOP;/*successful*/Step5Fori=1,…,nSetX0[]=X[];/*updateX0*/Step6Setk++;Step7Output(Maximumnumberofiterationsexceeded);STOP./*unsuccessful*/Axb0XiinjijjijiiaXabX1)0(TOLXXXXiini|0|max||0||1Whatifaii=0?迭代过程中，A的元素不改变，故可以事先调整好A使得aii0，否则A不可逆。必须等X(k)完全计算好了才能计算X(k+1)，因此需要两组向量存储。Abitwasteful,isn’tit?第五章线性方程组迭代解法6.2.3高斯-塞德尔(Gauss-Seidel)迭代法(G-S))1(kix)1(1)1(2)1(1,,,kikkxxx)(1)(2)(1,,,kikkxxx)(1111)()1()1(