迭代法的收敛定理教程.ppt

第六章 线性方程组迭代解法 §6.3 迭代法的收敛性 基本数学问题描述 一、基本收敛定理 收敛充分条件及其证明 二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件 基本数学问题描述 迭代法的收敛性，是指方程组 从任意初始向量X(0)出发，由迭代算法 算出向量序列 随着k的增加而趋向于解向量X *。 记各次误差向量 显然，迭代法的收敛性与误差向量序列 随着k的增加而趋向于零向量是等价的。 由于精确解X *自然满足 因此有 或 再递推出 所以，迭代法收敛性与迭代矩阵的幂B k，随着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) (1) 进一步，我们可以推知： 式(1)说明，当||B||1 且不接近1并且相邻两次迭代向量X(k+1) 与 X (k)很接近时，则X(k)与精确解X *很接近。因此，在实际计算中，用|| X (k+1) - X (k) ||≤ε作为迭代终止条件是合理的。 反复利用 || X (k+1) - X*||=||BX (k)- BX*||=||B(X (k)- X*)|| ≤‖B‖.‖X (k)- X*‖, 可以得到 ||X (k)- X*||≤‖B‖k ·‖X(0)- X*‖， 可见X (0)越接近X*，序列{ X (k)}收敛越快，收敛速度 与初值X (0)的选取有关。 另一方面，‖B‖越小，序列{ X (k)}收敛越快。 更精确的说法是：ρ(B) 越小，序列{ X (k) }收敛越快。 收敛速度的概念 下面我们给出收敛速度的概念： 定义6.1 R(B)= -lnρ(B)，称为迭代法的渐进收敛速度。 定理6.2的证明 证明: 显然 根据范数性质(3)(三角不等式) 可知 成立，也即 因此 -------（2） 显然 根据范数性质(4)(乘积不等式) 可知 也即 再将上两式联立，可以得出以下结果 再将此不等式两端同时减去 可得 由第（2）式可知 证明完毕。 将定理6.1和6.2用于Jacobi迭代法及Seidel迭代法，则有 在一般情况下，计算矩阵的范数比计算谱半径省事，所以通常是先利用定理6.2进行判断。 但定理6.2只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用定理6.1判断。 设有线性方程组 X=BX+f，其中 考察迭代法 X (k+1)=B X(k)+f 的收敛性。 例如 解： 由于 均大于1，故定理6.2在此无法判断； 但因为 λ1 =0.9, λ2=0.8,即ρ(B) =0.91,由定理6.1知本题迭代法收敛。 返回节 二、Jacobi 迭代法和Gauss-Seidel迭代法的收敛条件 引子 对角占优矩阵 实例 相关定理 定理6.3的证明 返回节 引子 虽然利用定理6.1和定理6.2可以判定Jacobi 迭代法和G-S迭代法的收敛性，但其中只有定理6.2对Jacobi 迭代法使用比较方便，此外，对于大型方程组，要求出G-S迭代矩阵BG和ρ(BG)以及Jacobi 迭代矩阵BJ和ρ(BJ)都不是容易的事。 这里介绍一些判定收敛的充分条件，它们是利用原方程组系数矩阵A和迭代矩阵B的特殊性质建立的，很实用，用起来也很方便。这些判定定理的建立也都是以定理6.1和定理6.2为理论基础的。 对角占优矩阵 如果线性方程组AX=b的系数矩阵A具有某种特殊性质（如对称正定、对角占优等），则可从A本身直接得出某些迭代法收敛性结论。 定义6.2 如果矩阵A满足条件 则称