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

《第六章 线性方程组迭代法.ppt》由会员分享，可在线阅读，更多相关《第六章 线性方程组迭代法.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、石家庄铁道学院 数理系Ch4 解线性方程组的迭代法 直接法得到的解是理论上准确的，但是我们可以看直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是得出，它们的计算量都是n3数量级，存储量为数量级，存储量为n2量级，量级，这在这在n比较小的时候还比较合适，但是对很多实际问比较小的时候还比较合适，但是对很多实际问题，往往要我们求解很大型的矩阵，而且这些矩阵含题，往往要我们求解很大型的矩阵，而且这些矩阵含有大量的有大量的0元素。对于这类矩阵，在用直接法时就会耗元素。对于这类矩阵，在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类费大量的时间和存储单元。因此我们有必要引入

2、一类新的方法：新的方法：迭代法迭代法。石家庄铁道学院 数理系对方程组做等价变换如：令，则则，我们可以构造序列若同时：所以，序列收敛与初值的选取无关石家庄铁道学院 数理系定义：（收敛矩阵）定义：（收敛矩阵）定理：定理：即：矩阵即：矩阵B为收敛矩阵当且仅当为收敛矩阵当且仅当B的谱半径的谱半径1由知，若有某种范数则迭代收敛.石家庄铁道学院 数理系1.Jacobi迭代法迭代法石家庄铁道学院 数理系格式很简单：石家庄铁道学院 数理系2.GaussSeidel迭代法迭代法在Jacobi迭代中，使用最新计算出的分量值石家庄铁道学院 数理系 迭代矩阵迭代矩阵记A=-L-UD石家庄铁道学院 数理系易知，Jaco

3、bi迭代有石家庄铁道学院 数理系 迭代矩阵迭代矩阵石家庄铁道学院 数理系Jacobi iterationGauss-Seidel iteration计算x(k+1)时需要x(k)的所有分量，因此需开两组存储单元分别存放x(k)和x(k+1)计算xi(k+1)时只需要x(k)的i+1n个分量，因此x(k+1)的前i个分量可存贮在x(k)的前i个分量所占的存储单元，无需开两组存储单元.石家庄铁道学院 数理系迭代公式:例 用Gauss-seidel 迭代法解方程组 Ax=b计算结果:石家庄铁道学院 数理系3 逐次超松弛迭代法逐次超松弛迭代法(SOR)记则可以看作在前一步上加一个修正量。若在修正量前乘

4、以一个因子，有对GaussSeidel迭代格式整理得引入松弛因子石家庄铁道学院 数理系写成分量形式，有石家庄铁道学院 数理系迭代矩阵迭代矩阵石家庄铁道学院 数理系 SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(B)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.石家庄铁道学院 数理系石家庄铁道学院 数理系石家庄铁道学院 数理系石家庄铁道学院 数理系4 4 迭代法的收敛性迭代法的收敛性定义定义 设有矩阵序列 及 ，如果 则称 收敛于 ，记为石家庄铁道学院 数理系一些关于收敛的定义及定理一些关于收敛

5、的定义及定理定理定理定理定理 设设 ，则，则 其中其中 为为 的谱半径。的谱半径。定理定理(迭代法基本定理）设有方程组迭代法基本定理）设有方程组对于任意初始向量对于任意初始向量 及任意及任意 ，解此方程组的迭，解此方程组的迭 代法代法 收敛的收敛的充要条件充要条件是是石家庄铁道学院 数理系定义定义 称 为迭代法的收敛速度.定理定理(迭代法收敛的充分条件)如果方程组的迭代公式为 ，且迭代矩阵的某一种范数 ，则 1）迭代法收敛，即对任取 ，有 2）3）实际计算中,通常利用作为控制迭代的终止条件.不过要注意,当 时,较大,尽管 已非常小,但误差向量的模 可能很大,迭代法收敛将是缓慢的.石家庄铁道学院

6、 数理系特别的特别的,Jacobi 迭代法收敛迭代法收敛G-S迭代法收敛迭代法收敛SOR迭代法收敛迭代法收敛石家庄铁道学院 数理系 定理定理 若SORSOR方法收敛,则02.证证 设SORSOR方法收敛,则(B)1,所以|det(B)|=|12 n|1而 det(B)=det(D-L)-1(1-)D+U)=det(E-D-1L)-1 det(1-)E+D-1U)=(1-)n于是|1-|1,或 02石家庄铁道学院 数理系 定理定理 设A是对称正定矩阵,02时,则解方程组 Ax=b的SORSOR方法收敛.石家庄铁道学院 数理系注意的问题（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代

7、法迭代法的收敛性没有必然的联系：的收敛性没有必然的联系：即当即当Gauss-Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时，Gauss-Seidel法也可能不收敛。法也可能不收敛。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的迭代矩阵不同：迭代矩阵不同：BJ=D-1(L+U),B G-S=(D-L)-1U石家庄铁道学院 数理系用用Jacobi迭代法求解不收敛，但用迭代法求解不收敛，但用 G-S法收敛。法收敛。用用Jacobi迭代法求解收敛，迭代法求解收敛，但用但用 G-S法不收敛。法不收敛。BJ的特征值为0

8、，0，0，而BGS的特征值为 0，2，2石家庄铁道学院 数理系系数矩阵系数矩阵A是正定矩阵，因此是正定矩阵，因此用用 Gauss-Seidel法收法收敛敛不是正定矩阵，因此用不是正定矩阵，因此用 JacobiJacobi迭代法不收敛迭代法不收敛A A是有正对角元的是有正对角元的n n阶对称矩阵阶对称矩阵石家庄铁道学院 数理系本章小结本章小结1掌握基本的迭代法掌握基本的迭代法:Jacobi迭代法迭代法,Gauss-Seidel迭代法迭代法.(分量形式分量形式,矩阵形式矩阵形式)2初识串行和并行算法初识串行和并行算法.在此基础上掌握逐次超松在此基础上掌握逐次超松弛迭代法弛迭代法.32 掌握谱半径和矩阵范数掌握谱半径和矩阵范数,知道迭代法收敛的充知道迭代法收敛的充要条件要条件,充分条件充分条件.