北航数值分析B第二章课ch2.8北航数值分析B第二章课件ch2.8.ppt

§3 迭代法的收敛性 3.1 一阶定常迭代法的基本定理 设有Ax=b，其中 为非奇异阵，记 为精确解， 且设有 迭代矩阵B满足什么条件时，有 1、误差向量： 于是由（3.2）减去（3.1）式得到误差向量的递推公式 则有 于是得一阶定常迭代法 研究问题: 称为k步迭代的误差向量。 为初始向量 的误差， 2、矩阵序列的极限 定义2 设有矩阵序列 个数列极限存在，且有 收敛于A，记 例4 设 且有矩阵序列 显然，当 时，则 3、矩阵序列收敛的充要条件 定理1 证明： 由范数的等价性，只证 定理2 对任意向量 证明： 是显然的。 现证“ ”，由设对任意的 都有 ，则有 或对 都有 定理3 B所有特征值满足 或B谱半径 数列收敛 证明： 若B为一般矩阵， 即存在非奇异阵P使 为B特征值。 B为可对角化矩阵， 对任意n阶矩阵B都可化为Jordan标准型， 即存在非奇异矩阵p，使 其中J为Jordan标准型， 4、一阶定常迭代法的基本定理 （1）设有方程组 （2）有迭代法 对任意选取初始向量 ，迭代法（*）收敛的充要条件是 B的所有特征值 满 足 证明 充分性 则 有唯一解 于是，近似解 误差向量有公式 再由定理3，得 由定理2，对任意取 ，有 必要性 由设对任意取 ，都有 且 （3.3） ,由（*）及(3.3)式得到 又由题设对任意 都有 由定理2，则有 定理4 又由定理3，得到 说明：迭代法的基本定理在理论上是重要的，它是迭代法收敛 大时是有困难的 ， 如果有B某种范数 ，则 （1）迭代法收敛，即 （2） （3）误差估计 证明 ，由P281定理25，知 给出利用B范数判别迭代法收敛的充分条件。 及一阶定常迭代法 定理5 设有方程组 性的基本准则，但在实际计算中要验证 是否成立，当n较 （1）因为 再由定理4(迭代法基本定理)得 例5 考察用Jacobi迭代法，G-S迭代法解例2中的方程组 的收敛性。 解 首先将A写为： 解 Jacobi迭代法迭代矩阵为 所以用Jacobi方法解例2方程组收敛。 的G-S迭代法的迭代矩阵为 所以用G-S迭代法解例2方程组收敛。 (1)由定理5可知当 愈小,迭代法收敛愈快。 （3）可利用误差估计式（3）事先确定迭代次数，以保证误差 说明： 则G-S迭代法收敛较快。 (2)当 时，迭代法收敛将是缓慢的 。 事实上，欲使 迭代次数应取 成立的最小正整数。 3.2 关于解特殊线性方程组迭代法的收敛性 主要讨论： 不可约阵，A为对称正定矩阵等时的解法的收敛性。 定义3 （1）如果A的元素满足 则称A为严格 的系数矩阵A为对角占优阵，A为 方程组 1、对角占优阵 对角占优阵（或强占优阵）。 且上式至少 （2）如果A的元素满足 有一个不等式是严格成立，则称A为弱对角占优阵。 2、可约与不可约阵 定义4 如果存在n阶置换矩阵 P，使 （3.4） 阶方阵 ，则称A为可约矩阵， 阶方阵， A22为n-r 其中 为 否则，如果不存在这样的 置换阵p使（3.4）式成立，则称A为不可约矩阵。 矩阵A为可约阵，即对A施行若干次行列重排（即对 A在交换两行的同时，交换A相应的两列元素，称为对A施行一次行 列重排）能化为（3.4）式。 求解。 说明：1、 例7 设 则 为可约阵。 解： 所以A为可约阵。 说明：2、 若A可约，求解 可化为两个独立的低阶方程组 事实上，求解 （3.4） 或求解 由上式第2个方程组求y2 ，再代入第1个方程组求y1 。 如果A所有元素都非零，则A为不可约阵。 例6 设 注： A为强对角占优阵，但A为不可 约阵。 事实上，求解 定理6 （对角占优定理）设A为n阶严格对角占优阵，或为弱对 3、Jacobi迭代法G-S迭代法的收敛条件 角占优矩阵且为不可约阵，则A为非奇异矩阵。 定理7 其中 G-S迭代法均收敛。 （1）如果A为严格对角占优阵，则解Ax=b的Jacobi迭代法、 Jacobi迭代法、G-S迭代法均收敛。 （2）如果A为弱对角占优矩阵且为不可约阵，则解Ax=b的 证明： 先证（1）的Jacobi迭代法收敛。 只要证Jacobi迭代 法迭代阵的特征 值绝对值小于1。 解Ax=b的Jacobi迭代法的迭代阵为 因为A为严格对角占优阵， 由定理5知Jacobi迭代法收敛。 证明： 解Ax=b的G-S迭代法的迭代阵为 G的特征方程的根满足： 由设 ，则G的特征值满足： 以下证明，当 用反证法。 且至少有一个不等式严格成立。 再证（2）的G-S迭代法的收敛，其他可作习题。 矩阵C为弱对角占优阵且