计算方法 解线性方程组的迭代法ppt课件.ppt

第9次解线性方程组的迭代法 NumericalAnalysis 主要内容 迭代法的基本思想雅可比 Jacobi 迭代法雅可比迭代法的矩阵表示高斯 塞德尔 Gauss Seidel 迭代法Gauss Seidel迭代法的矩阵表示Jacobi迭代与Gauss Seidel迭代算法实现 迭代法的基本思想 迭代法是求解线性方程组 尤其是具有大型稀疏矩阵的线性方程组的重要方法之一 凡是迭代法都有一个收敛问题 有时某种方法对一类方程组迭代收敛 而对另一类方程组进行迭代时却会发散 一个收敛的迭代法不仅具有程序设计简单 适于自动计算 而且较直接法更少的计算量就可获得满意的解 第六章解线性方程组的迭代法 6 1迭代法的基本思想 将线性方程组转化为便于迭代的等价方程组 若非奇异 则线性方程组 有唯一解 步骤1 经过某变换构造出方程组 1 的一个等价同解方程组 迭代法的基本步骤 任务 设非奇异 求解方程组 1 步骤2 建立迭代公式 收敛定义 如果 当k 时 存在极限 则称迭代法是收敛的 否则就是发散的 迭代法是收敛的意味着 注1 可以构造各种不同的迭代公式 收敛时 在迭代公式 中令 则 注2 并非所有的迭代公式都收敛 例1用迭代法求解线性方程组 解 构造方程组的等价方程组 建立迭代公式 迭代不收敛的例子 取 迭代解离精确解 进行迭代计算得 越来越远 迭代不收敛 原因是迭代公式不正确 Home 雅可比 Jacobi 迭代法 6 2雅可比 Jacobi 迭代法 例2 利用迭代法求解方程组 已知精确解 x 3 2 1 T 6 2 1雅可比迭代法算法构造 解 以下列独特的方式分离出 右端不含x1 右端不含x2 右端不含x3 由此 建立迭代公式 取初始向量 进行迭代 可以逐步得出一个近似解的序列 同学们 迭代两次 当迭代到第10次有 结果表明 此迭代过程收敛于方程组的精确解 x 3 2 1 T 当近似解能达到预先要求的精度 迭代终止 以最后得到的近似解作为线性方程组的解 考察一般的方程组 将n元线性方程组 由此 得到如下的被称为解方程组的Jacobi迭代公式 实际计算中 要用雅可比迭代法公式的分量形式 k 0 1 2 例3试用雅可比迭代法解线性方程组 解 先构造雅可比迭代公式 精确解 问题 对于一个有解的线性方程组 其雅可比迭代是否一定收敛呢 回答 Sorry 我现在也不知道 Home 雅可比迭代法的矩阵表示 6 2 2雅可比迭代法的矩阵表示 记作 设方程组的系数矩阵A非奇异 且主对角元素 则可将A分裂成 D L A D L U 则等价于 即 显然D可逆 于是有 这样便得到一个迭代公式 令 则有 k 0 1 2 称为雅可比迭代公式 B称为雅可比迭代矩阵 由矩阵表达的雅可比迭代公式如下 例4 写出如下方程组的雅可比迭代公式的矩阵形式 解 先将方程组表达为矩阵形式 Home 高斯 塞德尔 Gauss Seidel 迭代法 6 3高斯 塞德尔 Gauss Seidel 迭代法 6 3 1高斯 塞德尔迭代法的基本思想 在Jacobi迭代法中 每次迭代只用到前一次的迭代值 现在修改Jacobi迭代法 使得若每次迭代充分利用当前最新的迭代值 在求时 使用用新分量 代替旧分量 就得到高斯 赛德尔迭代法 已经计算出的分量 马上就使用 i 1 2 nk 0 1 2 高斯 塞德尔迭代法格式为 旧分量 新分量 高斯 塞德尔迭代法分量形式格式为 例5 使用高斯 塞德尔迭代法解方程组 解 确定迭代公式 同学们 计算 k 0 k 1 k 2取初值 0 0 0 当k 0 代入初值 计算 得 当k 1 代入 计算 得 当k 2 代入 计算 得 初步结论 由Gauss Seidel和Jacobi迭代法解方程组 1 2 均收敛 Gauss sadel方法收敛较快针对有唯一解的线性方程组的Gauss Seidel或Jacobi迭代法是否一定收敛 例6试用Gauss Seidel迭代法解线性方程组 评论 该方程组的雅克比迭代方法收敛 同学们按照Gauss Seidel迭代法构造迭代公式 看看是否收敛 精确解 Home Gauss Seidel迭代法的矩阵表示 设方程组的系数矩阵A非奇异 且主对角元素 则可将A分裂成 A D L U 则Ax b等价于 6 3 2Gauss Seidel迭代法的矩阵表示 于是 则高斯 塞德尔迭代公式可以表达为 D L U x b 则高斯 塞德尔迭代形式为 记 在等式两端乘以D L的逆矩阵 得 Home Jacobi迭代与Gauss Seidel迭代算法实现 6 2 1雅可比迭代法的算法实现 6 3 3高斯 塞德尔迭代算法实现 高斯 塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同 只是一旦求出变元的某个新值后 就改用新值替代老值来进行这一步剩下的计算 Home 例6试用Gauss Seidel迭代法解线性方程组 精确解 将方程组改写为 x1 k 1 2x2 k 2x3 k 1x2 k 1 x1 k 1 x3 k 1x3 k 1 2x1 k 1 2x2 k 1 1 x1 k 1 2x2 k 2x3 k 1x2 k 1 x1 k 1 x3 k 1x3 k 1 2x1 k 1 2x2 k 1 1 x1 0 0 x2 0 0 x3 0 0 x1 1 1x2 1 0 x3 1 1 x1 2 1x2 2 3x3 2 3 x1 3 11x2 3 15x3 3 7 第一种解法 取初值 看来迭代公式不收敛 x1 k 1 2x2 k 2x3 k 1x2 k 1 x1 k 1 x3 k 1x3 k 1 2x1 k 1 2x2 k 1 1 x1 0 3x2 0 3x3 0 1 x1