Chapter2_2_线性方程组的迭代法.ppt

2 2解线性方程组的迭代法 IterativeMethodsforSolvingLinearSystems 思路 将改写为等价形式 建立迭代 从初值出发 得到序列 如何建立迭代格式 收敛速度 向量序列的收敛条件 误差估计 2 2 1逐次逼近法 迭代格式的构造 把矩阵A分裂为则 将上式写为迭代过程这种迭代过程称为逐次逼近法 B称为迭代矩阵 收敛性定义 若称逐次逼近法收敛 否则 称逐次逼近法不收敛或发散 给定初值就得到向量序列 问题 是否是方程组Ax b的解 定理2 2 1任意给定初始向量x0 如果由逐次逼近法产生的向量序列收敛于向量x 那么 x 是方程组x Bx g的解 证明 逐次逼近法收敛的条件 定理2 2 2设线性方程组x Bx g有惟一解 那么逐次逼近法对任意初始向量X 收敛的充分必要条件是迭代矩阵B的谱半径 B 1 证明 因此 要检验一个矩阵的谱半径小于1比较困难 所以我们希望用别的办法判断收敛性 定理2 2 3若逐次逼近法的迭代矩阵满足 B 1 那么逐次逼近法收敛 Remark 因为矩阵范数都可以直接用矩阵的元素计算 因此 用定理2 2 3 容易判别逐次逼近法的收敛性 证明 问题 如何判断可以终止迭代 误差估计 误差表达式及收敛速度 停机准则 写成矩阵形式 L U D Jacobi迭代阵 2 2 2Jacobi法 JacobiIterativeMethods Jacobi迭代的分量形式 Algorithm JacobiIterativeMethodSolvegivenaninitialapproximation Input thenumberofequationsandunknownsn thematrixentriesa theentriesb theinitialapproximationX0 toleranceTOL maximumnumberofiterationsMmax Output approximatesolutionX oramessageoffailure Step1Setk 1 Step2While k Mmax dosteps3 6Step3Fori 1 nSet computexk Step4IfthenOutput X STOP successful Step5Fori 1 nSetX0 X updateX0 Step6Setk Step7Output Maximumnumberofiterationsexceeded STOP unsuccessful Whatifaii 0 迭代过程中 A的元素不改变 故可以事先调整好A使得aii 0 否则A不可逆 必须等X k 完全计算好了才能计算X k 1 因此需要两组向量存储 Abitwasteful isn tit Gauss Seidel迭代阵 作A的另一个分裂 其迭代格式的矩阵形式为 2 2 3Gauss Seidel迭代法 下面从另一个角度来说明 写成分量形式 只存一组向量即可 注 这二种方法都存在收敛性问题 在讨论收敛性之前我们先来讲一些预备知识和有关的定理 2 2 4有关基本概念 一 严格对角占优矩阵与对角占优矩阵 定义1设A是n阶矩阵 若满足不等式 且至少有一个i 使严格不等号成立 则称A为对角占优矩阵 若对所有的i 1 2 n 都有严格不等号成立 称A为严格对角占优矩阵 二 可约矩阵与不可约矩阵 定义2 设A是n阶矩阵 如果存在排列阵P 使 其中A11和A22分别是k阶和n k阶方阵 n 2 k n 那么 称A是可约矩阵 如果不存在这样的排列阵P 使上式成立 称A是不可约矩阵 定理2 2 5设A是n阶矩阵 A是不可约的充分必要条件是对有限整数集W 1 2 n 中任意两个非空子集R S W R S W R S 存在i R j S 使aij 0 三 有关性质 定理2 2 6设A是n阶 按行 严格对角占优矩阵 那么A是非奇异的 定理2 2 7设A是严格对角占优矩阵 那么 其各阶主子阵也是严格对角占优矩阵 定理2 2 8设A是严格对角占优矩阵 记经过一步Gauss消去后的矩阵为 那么 A 2 n 1仍是严格对角占优的 定理2 2 9设A是不可约对角占优矩阵 那么A是非奇异矩阵 定理2 2 10n阶矩阵A是按行严格对角占优矩阵的充分必要条件是Jacobi迭代法的迭代矩阵满足 BJ 1 定理2 2 10 2n阶矩阵A是按列严格对角占优矩阵的充分必要条件是Jacobi迭代法的迭代矩阵满足 BJ 1 1 2 2 5Jacobi迭代法和Gauss Seidel迭代法的收敛性 定理2 2 2设线性方程组x Bx g有惟一解 那么逐次逼近法对任意初始向量X 收敛的充分必要条件是迭代矩阵B的谱半径 B 1 定理2 2 11设A是有正对角元的n阶对称矩阵 那么Jacobi迭代法收敛的充分必要条件是A和2D A同为正定矩阵 证明 如果A是有正对角元的对称矩阵 aii 0记D diag a11 a22 ann 对于BJ I D 1A 有 1 若Jacobi迭代法收敛 则 BJ 1 即 即D 1 2AD 1 2是正定矩阵 从而A也是正定矩阵 现考虑矩阵2D A 即2D A与 的特征值的符号相同 的特征值为2 i 因此2D A的特征值为正 从而2D A为正定矩阵 充分性 A为正定矩阵 I D 1A的特征值全小于1 2D A为正定矩阵 I D 1A的特征值全大于 1 I D 1A 1 BJ 1 定理 2 2 12 2 2 13 2 2 14 如果A是按行 列 严格对角占优的矩阵 那么Jacobi和G S迭代法都收敛 定理2 2 15设A是不可约对角占优矩阵 那么Jacobi迭代法与G S迭代法都收敛 定理2 2 16设A是n阶正定矩阵 那么 G S迭代法收敛 定理2 2 13A按行严格对角占优 则Gauss Seidel迭代收敛 证设是任一特征值 x是相应特征向量 设若则 注意的问题 2 Jacobi迭代法和Gauss Seidel迭代法的收敛性没有必然的联系 即当Gauss Seidel法收敛时 Jacobi法可能不收敛 而Jacobi法收敛时 Gauss Seidel法也可能不收敛 1 Jacobi迭代法和Gauss Seidel迭代法的迭代矩阵不同 BJ D 1 L U BG S D L 1U 举例 用Jacobi迭代法求解不收敛 但用Gauss Seidel法收敛 用J