第六章线性方程组迭代法PPT讲稿.ppt
第六章线性方程组迭代法第1页，共28页，编辑于2022年，星期三对方程组做等价变换如：令，则则，我们可以构造序列若同时：所以，序列收敛与初值的选取无关第2页，共28页，编辑于2022年，星期三定义：（收敛矩阵）定义：（收敛矩阵）定理：定理：即：矩阵即：矩阵B为收敛矩阵当且仅当为收敛矩阵当且仅当B的谱半径的谱半径1由知，若有某种范数则迭代收敛.第3页，共28页，编辑于2022年，星期三1.Jacobi迭代法迭代法第4页，共28页，编辑于2022年，星期三格式很简单：第5页，共28页，编辑于2022年，星期三2.GaussSeidel迭代法迭代法在Jacobi迭代中，使用最新计算出的分量值第6页，共28页，编辑于2022年，星期三 迭代矩阵迭代矩阵记A=-L-UD第7页，共28页，编辑于2022年，星期三易知，Jacobi迭代有第8页，共28页，编辑于2022年，星期三 迭代矩阵迭代矩阵第9页，共28页，编辑于2022年，星期三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个分量所占的存储单元，无需开两组存储单元.第10页，共28页，编辑于2022年，星期三迭代公式:例 用Gauss-seidel 迭代法解方程组 Ax=b计算结果:第11页，共28页，编辑于2022年，星期三3 逐次超松弛迭代法逐次超松弛迭代法(SOR)记则可以看作在前一步上加一个修正量。若在修正量前乘以一个因子，有对GaussSeidel迭代格式整理得引入松弛因子第12页，共28页，编辑于2022年，星期三写成分量形式，有第13页，共28页，编辑于2022年，星期三迭代矩阵迭代矩阵第14页，共28页，编辑于2022年，星期三 SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(B)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.第15页，共28页，编辑于2022年，星期三第16页，共28页，编辑于2022年，星期三第17页，共28页，编辑于2022年，星期三第18页，共28页，编辑于2022年，星期三4 4 迭代法的收敛性迭代法的收敛性定义定义 设有矩阵序列 及 ，如果 则称 收敛于 ，记为第19页，共28页，编辑于2022年，星期三一些关于收敛的定义及定理一些关于收敛的定义及定理定理定理定理定理 设设 ，则，则 其中其中 为为 的谱半径。的谱半径。定理定理(迭代法基本定理）设有方程组迭代法基本定理）设有方程组对于任意初始向量对于任意初始向量 及任意及任意 ，解此方程组的迭，解此方程组的迭 代法代法 收敛的收敛的充要条件充要条件是是第20页，共28页，编辑于2022年，星期三定义定义 称 为迭代法的收敛速度.定理定理(迭代法收敛的充分条件)如果方程组的迭代公式为 ，且迭代矩阵的某一种范数 ，则 1）迭代法收敛，即对任取 ，有 2）3）实际计算中,通常利用作为控制迭代的终止条件.不过要注意,当 时,较大,尽管 已非常小,但误差向量的模 可能很大,迭代法收敛将是缓慢的.第21页，共28页，编辑于2022年，星期三特别的特别的,Jacobi 迭代法收敛迭代法收敛G-S迭代法收敛迭代法收敛SOR迭代法收敛迭代法收敛第22页，共28页，编辑于2022年，星期三 定理定理 若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第23页，共28页，编辑于2022年，星期三 定理定理 设A是对称正定矩阵,02时,则解方程组 Ax=b的SORSOR方法收敛.第24页，共28页，编辑于2022年，星期三注意的问题（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代法迭代法的收敛性没有必然的联系：的收敛性没有必然的联系：即当即当Gauss-Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时，Gauss-Seidel法也可能不收敛。法也可能不收敛。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的迭代矩阵不同：迭代矩阵不同：BJ=D-1(L+U),B G-S=(D-L)-1U第25页，共28页，编辑于2022年，星期三用用Jacobi迭代法求解不收敛，但用迭代法求解不收敛，但用 G-S法收敛。法收敛。用用Jacobi迭代法求解收敛，迭代法求解收敛，但用但用 G-S法不收敛。法不收敛。BJ的特征值为0，0，0，而BGS的特征值为 0，2，2第26页，共28页，编辑于2022年，星期三系数矩阵系数矩阵A是正定矩阵，因此是正定矩阵，因此用用 Gauss-Seidel法收敛法收敛不是正定矩阵，因此用不是正定矩阵，因此用 Jacobi Jacobi迭代法不收敛迭代法不收敛A A是有正对角元的是有正对角元的n n阶对称矩阵阶对称矩阵第27页，共28页，编辑于2022年，星期三本章小结本章小结1掌握基本的迭代法掌握基本的迭代法:Jacobi迭代法迭代法,Gauss-Seidel迭代法迭代法.(分量形式分量形式,矩阵形式矩阵形式)2初识串行和并行算法初识串行和并行算法.在此基础上掌握逐次超松弛迭在此基础上掌握逐次超松弛迭代法代法.32 掌握谱半径和矩阵范数掌握谱半径和矩阵范数,知道迭代法收敛的充要条件知道迭代法收敛的充要条件,充分条件充分条件.第28页，共28页，编辑于2022年，星期三
