《ch9线性与非线性方程组的迭代解法》-课件设计（公开）.ppt

iteration methods for the solution of nonlinear systems Nonlinear system: Basic idea of iteration for the solution of 1-dim nonlinear function f(x)=0: Condition for convergence: f1, f2,…, fn--nonlinear functions Iteration for nonlinear system: * 第九章 线性与非线性方程组的迭代解法 /* iteration methods for the solution of linear or nonlinear systems */ Linear systems： A x = b Ax=b A x* =b x(k+1)=f(x(k)) x(k), k=0,1,2,… hopefully, limx(k)=x* x(0) How to design the iteration formula? Ax=b x=Bx+f x(k+1)=B x(k) +f L D U 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)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1) Gauss-Seidel iteration Jacobi iteration Convergence of iteration Convergence of matrix Error vector of iteration example Jacobi iteration G-S iteration How to check if a certain iteration system converges or not? Conditions of convergence Not flexible to use actually Posterior error Prior error Proof: from Jordan standard form of B, we know j+1 j+1 Proof: ? ? ? From above, we have Summary: ??B??p或?(B)越小，迭代法的收敛速度越快； 若事先给出误差精度?，由事先误差估计式可得到迭代次数的估计 实际计算中，若??B??p不太接近于1，利用事后误差估计作为控制迭代停止的条件，即当 ??x(k)-x(k-1)??p? 时，迭代终止，并取x(k)作为近似解； 迭代法是否收敛主要取决于迭代矩阵的性质，可用条件2，3判断迭代法是否收敛。 example Jacobi iteration matrix B=D-1(L+U) G-S iteration matrix G= - (D+L)-1 U Convergency for two special matrix 1.(Th4) A is symmetric and positive definite ?G-S converges. (see proof of Th7 later.) 2. (Th5) A is strictly diagonally dominant or weakly diagonally dominant and not reducible ?J and G-S both converge. order r order n-r ?A reducible, else A not reducible. Strictly diagonally dominant !note: 1. Permutation matrix 2. A reducible?Ax=b can be reduced to two linear systems of lower order by permutation(exchange two rows, e.g. row i and j as well as two correspon