数值分析教学课件（华南理工大学）3.3迭代法的收敛定理.ppt

第三章 线性方程组迭代解法 Iterative techniques for solving linear system §3.3 迭代法的收敛性 基本数学问题描述 The problem 一、基本收敛定理 基本数学问题描述 一、基本收敛定理 The Fundamental convergence theorem 收敛速度的概念 二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件 引子 对角占优矩阵 实例 相关定理 定理3.3的证明 引子 对角占优矩阵diagonally dominant matrix 实例(Example) 相关定理 定理3.3的证明 是严格对角占优阵，所以它是非奇异的，即 det(?(D-L)-U) ?0与特征值?满足det(?(D-L)-U) =0 矛盾。 故 | ? |1即ρ(BG) 1， G-S迭代法收敛。 定理得证。 对于对称正定矩阵A， Jacobi迭代法不一定收敛。 一般来说，可能Jacobi迭代法和Guass-Seidel迭代法都收敛，也可能都是都不收敛，或一个收敛，一个不收敛，在两者都收敛的情况下，收敛速度也不一定。 p76例3.2 迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。 但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。 只要断定系数矩阵满足收敛条件，尽管多次迭代计算工作量大一些，却能达到预定精度。 * * § 3.3 迭代法的收敛定理 The convergence theorem of iterative method The convergence theorem of iterative method The Fundamental convergence theorem 二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件 The condition for convergence of Jacobi and Guass-Seidel method 迭代法的收敛性，是指方程组 从任意初始向量X(0)出发，由迭代算法 算出向量序列 随着k的增加而趋向于解向量X *。 记各次误差向量 The error vector 显然，迭代法的收敛性与误差向量序列 随着k的增加而趋向于零向量是等价的。 由于精确解X *自然满足 因此有 或 再递推出 The convergence of {x(k) } Bk 0 (k?∞ ) 由 X(k+1)=BX(k)+f 及 X *=B X *+f 可见 X(k) ? X* ? B k? 0 (k?∞ ) εk+1 = X (k+1) - X *= B（X (k) - X *） = · · · · · · · · · · · · · = B k+1（X(0) -X *） = B k+1 ε0 可推知 ?(B) Theorem :for any initial value , the fundamental iterative method defined by x(k+1)=Bx(k)+f (k=0,1,2,…) converges to the unique solution of x=Bx+f if only if (1) Theorem 3.2: If |B|1 for any initial vector the sequence {x(k) } converges and the estimate (1) holds. Theorem 3.2 进一步，我们可以推知： 式(1)说明，当||B||1 且不接近1并且相邻两次迭代向量X(k+1) 与 X (k)很接近时，则X(k)与精确解X *很接近。因此，在实际计算中，用|| X (k+1) - X (k) ||≤ε作为迭代终止条件是合理的。 So possible stopping criteria is to iterate until | x(k+1) - x(k)| is smaller than given tolerance ε. 反复利用 || X (k+1) - X*||=||BX (k)- BX*||=||B(X (k)- X*)|| ≤‖B‖.‖X (k)-