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 corresponding columns, col i and j . 3. A reducible?there exists a none