第八章线性与非线性方程组的迭代解法.ppt

!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 can’t 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. iteration methods for the solution of nonlinear systems Nonlinear system: f1, f2,…, fn--nonlinear functions Basic idea of iteration for the solution of 1-dim nonlinear function f(x)=0: Condition for convergence: Real root Initial point * 第八章 线性与非线性方程组的迭代解法 /* iteration methods for the solution of linear or nonlinear 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, limx(k)=x* 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. x(0) How to design the iteration formula? L U D B is not unique, so the iteration formula is not unique! Jacobi iteration Ax=b x=Bx+f x(k+1)=B x(k) +f Equavalent reformation Iteration matrix Jacobi iteration Matrix form Component form Convenient in programming Gauss-Seidel iteration Component form Convenient in programming Matrix form comparison 计算xi(k+1)时只需要x(k)的i+1~n个分量，因此x(k+1)的前i个分量可存贮在x(k)的前i个分量所占的存储单元，无需开两组存储单元 计算x(k+1)时需要x(k)的所有分量，因此需开两