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

1、第六章 线性方程组的迭代解法 /* iteration methods for the solution of linear systems */,Linear systems：,A x = b,Matrix form,Ax=b A x* =b,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 approximat

2、e solutions x(k)|kZ which approaches to the real solution x* hopefully.,How to design the iteration formula?,B is not unique, so the iteration formula is not unique!,Ax=b,x=Bx+f,Equavalent reformation,Iteration matrix,迭代法思想：第一步,第二步,B 与k无关，称为一阶定常迭代法,收敛？发散？,判断收敛的方法：,计算中判断迭代终止条件的方法：,L,U,D,6.2基本迭代法,Jaco

3、bi iteration,取M为D,Matrix form,Jacobi迭代法简单，迭代一次只需作 一次矩阵与向量的乘法即可。,Component form,Gauss-Seidel iteration 高斯塞德尔迭代法,取M为D+L,Gauss-Seidel iteration,Component form,Jacobi分量形式,comparison,迭代收敛性,定义3矩阵收敛性,Error vector of iteration,例2,How to check if a certain iteration system converges or not?,定理3迭代收敛的等价条件,Not

4、flexible to use actually,Posterior error estimated in the process of iteration,Prior errorestimated before the iteration,example,Jacobi iteration,G-S iteration,收敛速度,G-S iteration converges,example,Jacobi iteration matrix B=-D-1(L+U),G-S iteration matrix G= - (D+L)-1U,Jacobi iteration diverges,Exampl

5、e 3,G-S iteration diverges,Jacobi iteration diverges,Strictly diagonally dominantJ,G-S iteration converge,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,W1,over

6、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,!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 ha

7、s 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