第八章 线性代数方程组的迭代法.ppt

第八章 线性方程组 的迭代法 §1 迭代法基础 ? 问 题 ? 在实际应用中遇到的系数矩阵多为大型稀疏矩阵，如用求解线性方程组的直接法求解，在计算机上会耗费大量的时间和存储单元。在许多应用问题中使用迭代法。 思路 将 改写为 等价形式 ，建立迭代 　 ,从初值 出发，得到序列 。 研究内容： ? 如何建立迭代格式？　 ? 收敛速度？ ? 向量序列的收敛条件？ ? 误差估计？ 一般迭代法 定义1 对方程组 ，化为等价方程组 ，设 为任取的初值，将上式写为 迭代过程 这种迭代过程称为逐次逼近法，B 称为迭代矩阵。若 称逐次逼近法收敛， 否则，称逐次逼近法不收敛或发散。 问题：按上述思想迭代产生的向量序列 在什 么条件下收敛于方程组Ax=b的解？ 引进误差向量： ，其中 为方程组的解，即有 所以，要使 收敛到 ，则需研究 在什么条件下有 。 迭代法的收敛条件与误差估计 引理 当k? ?时，Bk ? 0 ? ? ( B ) 1 定理1 设有线性方程组 ，那么逐次逼近 法对任意初始向量 收敛的充分必要条件 是迭代矩阵B的谱半径 ?(B )1。 注：要检验一个矩阵的谱半径小于1比较困难， 所以我们希望用别的办法判断收敛性。 注: 1.因为矩阵范数 都可以直接用矩阵的元素 计算，因此用定理2， 很容易判别逐次逼近法的收敛性。 2.定理2是充分条件，当找不到矩阵的某一范数小于1时， 并不能判断迭代法不收敛。 ① ② 定理2 设线性方程组 有惟一解 ，若存 在一个矩阵范数使得 || B || 1, 则迭代收敛, 且有下列误差估计： （8.1） 1．雅克比（Jacobi）迭代法 设有n阶方程组 §2 几种常用的迭代法 若系数矩阵非奇异，且 (i = 1, 2,…, n)，将方程组 （8.1）改写成 然后写成迭代格式 （8.2） （8.2）式也可以简单地写为 （8.3） 记 ,其中 则雅克比迭代法的矩阵形式为： (8.4) 称 为雅克比迭代矩阵。 … … … … 写成矩阵形式： 2．高斯――赛得尔(Gauss-Seidel)迭代法 (8.5) (8.6) 其中 称为高斯―赛得尔迭代矩阵。 定理4 n阶矩阵A是严格对角占优矩阵的充分必要条件是 Jacobi迭代法的迭代矩阵满足 ‖BJ‖∞1。 3．Jacobi迭代法和Gauss-Seidel迭代法的收敛性 定理5 如果A是严格对角占优矩阵，那么Jacobi和G－S 迭代法都收敛。 定理6 若A是n阶正定矩阵，那么G-S迭代法收敛。 定理3 n阶矩阵A是严格对角占优矩阵，则A非奇异，且 所有对角元 。 注意的问题 （1）Jacobi迭代法和Gauss-Seidel迭代法的迭代矩阵不同： BJ =D-1(L+U), B G-S = (D-L)-1U （2）Jacobi迭代法和Gauss-Seidel迭代法收敛性没有必然的 联系。即当Gauss-Seidel法收敛时，Jacobi法可能不收 敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛 （3）Jacobi迭代和Gauss-Seidel迭代的特征方程： Jacobi迭代： Gauss-Seidel迭代： 用Jacobi迭代法求解收敛， 但用 Gauss-Seidel法不收敛。 （4）举例： 用Jacobi迭代法求解不收敛， 但用 Gauss-Seidel法收敛。 系数矩阵A是正定矩阵，因此用 Gauss-Seidel法收敛。 线性方程组的系数矩阵为 是严格对角占优的，所以Jacobi和Gauss-Seidel迭代格式 均收敛。 （1）迭代 （2）加速 （8.7） 即 §3 超松驰迭代法（SOR法） （Sequential Over-Relaxation) 矩阵形式： 注：1.称 为超松弛迭代矩阵