迭代法求解线性方程组.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 线性方程组的迭代解法,/*iteration methods for the solution of linear systems*/,Linear systems,：,A x,=,b,Matrix form,Ax,=,b,A x,*,=,b,x,(,k,+1),=,f,(,x,(k),),x,(,k,),k,=0,1,2,hopefully,lim,x,(,k,),=,x,*,x,(0),Iterative method:,given a linear system,Ax,=,b,design an iteration formula,x,(,k,+1),=,f,(,x,(,k,),)and choose an initial approximate solution,x,(0),.iteration results in a series approximate solutions,x,(,k,),|,k,Z,which approaches to the real solution,x,*,hopefully.,怎样设计迭代格式,?,B,并不是唯一的,因此迭代格式也不是唯一的,!,Ax,=,b,x,=,Bx,+,f,x,(,k,+1),=,B,x,(,k,),+,f,等价变换,迭代矩阵,迭代法思想：第一步,第二步,B,与,k,无关，称为一阶定常迭代法,收敛？发散？,判断收敛的方法：,计算中判断迭代终止条件的方法：,L,U,D,6.2,基本迭代法,Jacobi,iteration,取,M,为,D,Matrix form,Jacobi,迭代法简单，迭代一次只需作 一次矩阵与向量的乘法即可。,计算公式,Convenient in programming,Gauss-Seidel iteration,取,M,为,D+L,Gauss-Seidel iteration,Component form,Jacobi,分量形式,comparison,Jacobi,iteration,Gauss-Seidel iteration,计算,x,(,k,+1),时需要,x,(,k,),的所有分量，因此需开两组存储单元分别存放,x,(,k,),和,x,(,k,+1),计算,x,i,(,k,+1),时只需要,x,(,k,),的,i,+1,n,个分量，因此,x,(,k,+1),的前,i,个分量可存贮在,x,(,k,),的前,i,个分量所占的存储单元，无需开两组存储单元,Convergence of iteration,Convergence of matrix,Error vector of iteration,example,Jacobi,iteration,G-S iteration,In this example,G-S iteration converges faster than,Jacobi,iteration.Its not always true.Sometimes the later converges faster.For some linear systems,G-S converges while J diverges,and vice versa,.,How to check if a certain iteration system converges or not?,Conditions of convergence,Not flexible to use actually,Posterior error estimated in the process of iteration,Prior errorestimated before the iteration,Both error estimation can be used to control when to halt the iteration,G-S iteration diverges,example,Jacobi,iteration matrix,B,=-,D,-1,(,L,+,U,),G-S iteration matrix,G,=-(,D,+,L,),-1,U,Jacobi,iteration diverges,Convergency,for two special matrix,1.,A,is,symmetric and positive definite,G-S converges.,2.,A,is,strictly diagonally dominant,or,weakly diagonally dominant and not reducible,J and G-S both converge.,Strictly diagonally dominant,weakly diagonally dominant,order,r,order,n,-,rA,reducible,else,A,not reducible.,Example 3,G-S iteration diverges,Jacobi,iteration diverges,Strictly diagonally,dominant,J,G,-S iteration converge,Example 4,Strictly diagonally,dominant,J,G,-S iteration converge,Euavalent,reformation:,2*(1)+(2),(1)+(3),!note:if the given linear system doesnt satisfy the convergence condition,we can modify the order of the equations or do some linear combinations to get an equivalent system satisfying the convergence condition.,Jacobi,or G-S iteration can be used to solve linear systems but sometimes it converges very slowly,how to accelerate it?,SOR:successive,over relaxed methodacceleration of G-S iteration,We hope the weight averaging result to be closer to the real root,SOR,W1,over relaxed,W=1,G-S,Suppose,has been found by using G-S,now we have,to find,SORsuccessive over relaxed methodacceleration of G-S iteration,Residual of two successive iteration results,Convergency,of SOR,Conditions of convergence,:necessary condition.,In order to SOR,converge,we,must choose 0w2,else it must diverge.,Given,Ax,=,b,where,A,is symmetric and positive definite and,0,w,2,SOR converges.,This theorem includes the case,w,=1-G-S,Example 5,Solve the following linear system using J,G-,S,and,SOR(w,=1.15).Iteration halts when,Solution:take,1.Jacobi iteration,2.Gauss-Seidel iteration,3.SOR,!note:,w,chosed,well,SOR converges very fast.As for J and,G-S,the convergence speed depends on the spectral radius of the iteration matrix.,!NOTE:,The key problem in SOR is how to choose such a,w,that SOR converges fastest-the problem of how to choose the best relaxed factor,w,.Presently,the problem has been solved for a few special matrices.For the general case,successive searching method is used.At the start,choose one or more different,w,to try SOR.Then modify,w,according to the speed of convergence and successively find the best,w,.Finally fix,w,and continue iteration.,In theory,by iteration we can get approximate solution to any accuracy expected.Actually,however,due to the limit of computer word length,we cant arrive at any accuracy but the machine accuracy at most.So when we use to control iteration halting,we must be careful in choosing,in that machine accuracy or less results in dead loop.,