63迭代法的收敛性.ppt

一、矩阵的谱半径 第六章 解线性方程组的迭代法 §3 迭代法的收敛性 二、迭代法的收敛条件 三、举例 复习： 1、矩阵的特征值与特征向量的定义与计算； 设A为方阵，Au = λu (u ≠ 0) 即λ是方程 |λE - A| = 0的根 2、矩阵的特征值与特征向量的性质 3、Ak = AA…A的特征值是: 一、迭代法的谱半径 称迭代公式 中的矩阵 B 为迭代矩阵. 定义1： 定义2： 设A为n阶方阵，λi (i = 1,…,n)为A的特征值，称特征值模的最大值为矩阵A的谱半径，记为 称为矩阵A的谱. 性质： 若矩阵A的谱为 谱半径为 则 Ak = AA…A k个 的谱为 ( k = 1, 2, …) 谱半径为 定理：设A为任意n阶方阵，||.||为矩阵的任意诱导范数，则 证明： 对A的任一特征值λi 及相应的特征向量 ui，都有 因为ui为非零向量，即||ui||≠0，于是有 由λi 的任意性得 定理：设A为n阶方阵，则对任意正数ε，存在 一种矩阵范数||.||，使得 （证明略） 注：对n阶方阵，一般不存在矩阵范数||.||，使得 但若A为对称矩阵，则有 下面的定理对建立迭代法的收敛条件十分重要. 定理：设A为n阶方阵，则 的充要条件为 证明：(必要性)若 则 而 于是由极限存在准则，有 故 (充分性)若 取 则存在一种矩阵范数||.||，使得 而 于是 所以 再由有限维空间范数的等价性知结论真。 定理：设A为n阶方阵，则 的充要条件为 二、迭代法的收敛条件 定理：对任意初始向量 x(0)和右端项g，由迭代 格式 x(k+1) = Mx(k) + g 产生的向量序列收敛的充要条件为 证明：→ 设存在n维向量x*，使得 则 x* 满足 由迭代公式有 于是有 因为x(0)为任意向量，因此 即 ← 若 则λ=1不是M的特征值，所以 |I－Ｍ |≠0 于是对任意n维向量g，方程组(I－M)x=g有唯 一解，记为x*，即 并且 此时考虑 故对任意初始向量x(0)，都有 即由迭代公式产生的向量序列{x(k)}收敛。 推论1：若迭代矩阵满足 ||M||1，则迭代公式 产生的向量序列{x(k)}收敛。 推论2：松弛法收敛的必要条件是 0ω2 证明: 设松弛法的迭代矩阵M有特征值 因为 由定理，松弛法收敛必有 而 又 于是有 所以 注：定理表明，迭代法收敛与否只决定于迭代 矩阵的谱半径，与初始向量及方程组的右 端项无关。对同一方程组，由于不同的迭 代法迭代矩阵不同，因此可能出现有的方 法收敛，有的方法发散的情形。 举例：解方程组 讨论Jacobi法与Gauss-Seidel法的收敛性。 解：由定理，迭代法是否收敛等价于迭代矩阵的谱半径是否＜１，故应先求迭代矩阵。而 故A裂解后的各矩阵分别为 Jacobi迭代法的迭代矩阵为 其特征方程为 因此有 故Jacobi法收敛 如果用Gauss-Seidel迭代，由 可得 于是迭代矩阵为 其特征方程为 故 所以Gauss-Seidel迭代法发散。 请思考: (1)试推导Jacobi迭代法和Gauss-Seidel迭代法的迭代矩阵。 (2)试归纳判断迭代法收敛的方法。 答: (1)略 (2)先用两个推论，再用充要条件，即 ||M||1 迭代法收敛 松弛法收敛 0ω2 迭代法收敛 下面对一些特殊的系数矩阵给出几个常用的判断收敛的条件（代数判据）。 定义：若n阶方阵 A=(aij)满足 且至少有一个 i 值，使上式中不等号严格成立，则称A为弱对角占优阵。 若对所有 i，不等号均严格成立，则称A为严格对角占优阵。 例如： 矩阵 是严格对角占优 矩阵 不严格对角占优，是弱对角占优 定义： 如果矩阵A不能通过行的互换和相应列的互换成为形式 其中A11，A22为方阵，则称A为不可约. 例如：判断下列矩阵是否可约？ 矩阵 是可约的。 矩阵 是不可约的。 交换第1与3行(列) 设有线性方程组Ax=b，下列结论成立： 若A为严格对角占优阵或不可约弱对角占 优阵，则Jacobi迭代法和Gauss-Seidel迭代 法均收敛。 2.若A为严格对角占优阵，0ω≤1，则松弛法收敛。 3. 若A为对称正定阵，0ω2，则松弛法收敛. 即：若A是对称正定阵，则松弛法收敛的充要条件为0ω2。 归纳判断迭代法收敛的方法依次如下： 1. 首先根据方程组的系数矩阵A的特点判断； 2.