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

求特征值 高斯-塞德尔迭代矩阵 ? (G1) = 0.3536 1 ∴用高斯-塞德尔迭代法求解时，迭代过程收敛 ?1=0, 解:所给迭代公式的迭代矩阵为 取0 ?1/2迭代收敛 例4 用SOR法求解线性方程组 取ω=1.46，要求 解：SOR迭代公式 k = 0,1,2,…， 初值 该方程组的精确解 只需迭代20次便可达到精度要求. 如果取ω=1(即高斯—塞德尔迭代法)和同一初值, 要达到同样精度, 需要迭代110次. 我们知道, 对于给定的方程组可以构造成简单迭代、雅可比迭代、高斯-塞德尔迭代和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。 在什么条件下迭代序列 收敛？先引入 如下定理 经过等价变换构造出的等价方程组 对于方程组 得到迭代序列 § 6.5 迭代法的收敛性 定理 对给定方阵G, 若 ,则 为非奇异矩阵,且 若 为奇异矩阵,则存在非零向量x, 使 由于 ,两端消去 ,有 ,与已知条件 矛盾,假设不成立,命题得证。 证:用反证法 由相容性条件得 ,即有 定理 对给定方阵G, 若 ,则 为非奇异矩阵,且 即 将G分别取成G和-G，再取范数 又由于有 证:必要性 由于 可以是任意向量,故 收敛于0当且仅 当 收敛于零矩阵，即当 时， 基本定理5 迭代公式 收敛的充分必要条件是迭代矩阵G的谱半径 则在迭代公式两端同时取极限得 设迭代公式收敛,当k→∞时, 充分性: 设 , 则必存在正数ε, 使 则存在某种范数?? ? ??, 使 , ,则 , , 即 。故 收敛于 0, 由此定理可知，不论是雅可比迭代法、高斯—塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径 前例2 用迭代法求解线性方程组 构造的等价方程组 据此建立迭代公式 并非所有迭代公式都收敛,例如： 迭代矩阵G= ，其特征多项式为 特征值为 -2，-3， 所以迭代发散 定理6 (迭代法收敛的充分条件) 若迭代矩阵G的一种范数 ,则迭代公式 收敛,且有误差估计式 及 计算 十分麻烦，因此将定理5改为 定理6 (迭代法收敛的充分条件) ,则迭代公式 收敛,且有误差估计式 及 证: 矩阵的谱半径不超过矩阵的任一种范数,即 根据定理4.9可知迭代公式收敛。 因为 , 故 x＝Gx＋d 有惟一解 , 即 两边取范数 与迭代过程 相比较, 有: 由迭代格式，有 两边取范数，代入上式，得 证毕 由定理知，当 时迭代收敛， 值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代 （ε为给定的精度要求）作为 控制迭代结束的条件。 例5 已知线性方程组 考察用Jacobi迭代和Gauss-Seidel迭代求解时的收敛性 解: ⑴ 雅可比迭代矩阵 例5 已知线性方程组，考察Jacobi迭代的收敛性 故Jacobi迭代收敛 解: 雅可比迭代矩阵 ⑵ 高斯-塞德尔迭代，将系数矩阵分解 则高斯-塞德尔迭代矩阵 高斯-塞德尔迭代矩阵 故高斯—塞德尔迭代收敛。 定理7 设n阶方阵 为严格对角占优阵, 则 非奇异 证: 因A为对角占优阵, 其主对角元素的绝对值大 于同行其它元素绝对值之和, 且主对角元素 全不为0, 故对角阵 为非奇异。 作矩阵 利用对角占优知 由定理知 非奇异,从而A非奇异,证毕 系数矩阵为严格对角占优矩阵的线性方程组称为对角占优方程组。 结论： 严格对角占优线性方程组 的雅可比 迭代公式和高斯-赛德尔迭代公式均收敛。 例6 设 ,证明, 求解方程组 的Jacobi迭代与G-S迭代同时收敛或发散 证:雅可比迭代