第四章迭代求解线性方程组

1、河南师大数学与信息科学学院河南师大数学与信息科学学院线性方程组迭代解法线性方程组迭代解法本章讨论解线性方程组 bAx 古典迭代解法。主要内容包括：雅可比(Jacobi)迭代法高斯-赛德尔(Gauss-Seidel)迭代法超松驰(SOR)迭代法收敛性分析.;,.,) 1 . 4(, 2 , 1,)0()1()()0(或或发发散散的的否否则则就就称称它它是是不不收收敛敛的的敛敛的的则则称称该该迭迭代代法法是是收收序序列列有有极极限限如如果果由由算算法法产产生生的的向向量量叫叫做做叫叫做做做做叫叫其其中中的的迭迭代代称称作作形形如如指指定定初初始始向向量量代代算算法法我我们们很很容容易易建建立立如如

2、下下迭迭那那么么假假若若线线性性方方程程组组初始向量常数项迭代矩阵单步线性定常迭代.nnnnkkxgMkgMxxxgxMxbAxRRR单步线性定常迭代算法单步线性定常迭代算法雅可比(Jacobi)迭代法0000,0000),(:, 122311312, 1213231212211nnnnnnnnnnaaaaaaUaaaaaaLaaadiagDULDAbAx其其中中令令考考虑虑线线性性方方程程组组.),(,11bDgULDBgBxxbAx其中其中可等价写成可等价写成那么那么。JacobiBkgBxxxxxxJacobikkTn迭迭代代矩矩阵阵称称为为其其中中给给定定迭迭代代法法我我们们得得到到从

3、从而而, 2 , 1,),(:,)1()()0()0(2)0(1)0(雅可比迭代法的分量形式nnnnnnnnnnnnnnnnnnnababababgaaaaaaaaaaaaaaaaaaaaaaaaULDBJacobi333222111,1,2,1 , 13332333122222232221111111311121,0000)(迭迭代代矩矩阵阵注注意意到到., 2 , 1., 2 , 1,1)1(,11)1(,)(kniaxaxabxJacobiiinijkjjiijkjjiiki迭迭代代法法的的分分量量形形式式为为于于是是雅可比迭代程序设计编制计算程序时,应注意以下几个问题:.,.;, 0否

4、否则则迭迭代代终终止止时时迭迭代代继继续续当当大大限限定定值值和和最最量量还还需需要要增增设设迭迭代代次次数数变变情情形形如如果果考考虑虑到到算算法法发发散散的的否否则则继继续续迭迭代代终终止止算算法法当当并并确确定定一一种种向向量量范范数数预预定定一一个个允允许许误误差差常常量量CNTcountCNTcountxy )(:,1bxULDyyxyx这这样样作作为为输输出出作作为为输输入入和和设设置置向向量量根根据据迭迭代代法法的的特特点点 算法的终止 程序设计点击对象展开程序点击对象展开程序 算法的实现高斯-赛德尔(Gauss-Seidel)迭代法0000,0000),(:, 12231131

5、2, 1213231212211nnnnnnnnnnaaaaaaUaaaaaaLaaadiagDULDAbAx其其中中令令考考虑虑线线性性方方程程组组.)(,)(,11bLDgULDGgxGxbAx其其中中可可等等价价写写成成那那么么。SeidelGaussSGGkgxGxxxxxSeidelGaussSGkkTn迭迭代代矩矩阵阵称称为为其其中中给给定定迭迭代代法法我我们们得得到到从从而而)(, 2 , 1,),(:)(,)1()()0()0(2)0(1)0(G-S迭代法的分量形式., 2 , 1., 2 , 1,)(,1)1(,11)(,)(1)1(1)(1)()1()(kniaxaxabx

6、SGbDUxDLxDxbUxxLDiinijkjjiijkjjiikikkkkk迭迭代代法法的的分分量量形形式式为为于于是是所所以以由由于于.,)3(.,)2(.,) 1 (:很很大大的的区区别别因因此此它它们们的的收收敛敛性性有有着着阵阵区区别别很很大大但但迭迭代代矩矩迭迭代代法法的的分分量量形形式式相相似似迭迭代代法法和和尽尽管管计计算算顺顺序序有有关关迭迭代代法法与与分分量量的的而而关关系系迭迭代代与与分分量量的的顺顺序序没没有有量量出出向向量量的的已已计计算算好好的的分分时时地地使使用用了了输输子子中中的的前前一一个个和和式式中中及及区区别别仅仅在在于于右右端端迭迭代代式式似似迭迭代代

7、的的分分量量形形式式非非常常相相迭迭代代法法的的分分量量形形式式与与注注意意SGJacobiSGJacobiJacobiSGG-S迭代程序设计编制计算程序时,应注意以下几个问题:.,.;, 0否否则则迭迭代代终终止止时时迭迭代代继继续续当当大大限限定定值值和和最最量量还还需需要要增增设设迭迭代代次次数数变变情情形形如如果果考考虑虑到到算算法法发发散散的的否否则则继继续续迭迭代代终终止止算算法法当当并并确确定定一一种种向向量量范范数数预预定定一一个个允允许许误误差差常常量量CNTcountCNTcountxy )( :,1bxULDxx既既作作为为输输入入又又作作为为输输出出只只需需要要设设置置

8、向向量量根根据据迭迭代代法法的的特特点点 算法的终止 程序设计点击对象展开程序点击对象展开程序 算法的实现超松驰(Successive Overrelaxation)迭代法0000,0000),(:, 122311312, 1213231212211nnnnnnnnnnaaaaaaUaaaaaaLaaadiagDULDAbAx其其中中令令考考虑虑线线性性方方程程组组.)(,)()()1 (,11bLDgULDGgxGxxbAx其其中中可可等等价价写写成成那那么么对对于于任任一一正正数数 )1()(:, 2 , 1, )()1 (,),(:)(,1)1()(1)1()()0()0(2)0(1)0

9、(UDLDLkbUxxLDxxxxxxtionOverrelaxaSuccessiveSORkkkkTn 其其迭迭代代矩矩阵阵为为给给定定迭迭代代法法我我们们得得到到从从而而SOR迭代法的分量形式., 2 , 1., 2 , 1)1 (,1)1(,11)(,)1()(kniaxaxabxxSGiinijkjjiijkjjiikiki 迭迭代代法法的的分分量量形形式式为为于于是是.,)4(.,)3(.,1)2()1 (,) 1 (:)()1()()()1(,1)1()1(,11)()(,)(应应该该存存在在最最佳佳松松驰驰因因子子程程来来说说甚甚至至对对一一特特定定的的方方导导致致不不同同的的迭

10、迭代代效效果果不不同同的的松松驰驰因因子子可可能能会会算算法法具具有有相相对对的的可可变变性性因因此此子子由由于于算算法法引引入入了了松松驰驰因因有有关关迭迭代代与与分分量量的的计计算算顺顺序序迭迭代代法法一一样样与与迭迭代代法法就就转转化化为为了了时时当当作作如如下下组组合合和和对对确确定定一一个个正正数数即即迭迭代代的的一一种种外外推推是是迭迭代代法法实实质质上上可可以以看看作作注注意意SORSORSGSGSORxxxxxaxaxabxSGSORkikikikikiiinijkjkjiijkjkjiiki G-S迭代程序设计编制计算程序时,应注意以下几个问题:.,.;, 0否否则则迭迭代代

11、终终止止时时迭迭代代继继续续当当大大限限定定值值和和最最量量还还需需要要增增设设迭迭代代次次数数变变情情形形如如果果考考虑虑到到算算法法发发散散的的否否则则继继续续迭迭代代终终止止算算法法当当并并确确定定一一种种向向量量范范数数预预定定一一个个允允许许误误差差常常量量CNTcountCNTcountxy )( :,1bxULDxx既既作作为为输输入入又又作作为为输输出出只只需需要要设设置置向向量量根根据据迭迭代代法法的的特特点点 算法的终止 程序设计点击对象展开程序点击对象展开程序 算法的实现注意注意: : 迭代阵迭代阵M不唯一不唯一, ,影响收敛性。影响收敛性。1()max |()|ii n

12、 MM (0)( )(1)( )0,1,2,;.kknnAxbxMxgxxMxgkx线性方程组单步线性定常迭代算法指定初始向量如果由收敛算法产生的向量序列有极限 则称该迭代法是的不收敛否则就称它是的发散或的单步线性定常迭代法的收敛性单步线性定常迭代法的收敛性定义定义：矩阵M的谱半径谱半径为：定义定义：如果存在矩阵G使：G(I M)=A，Gg=b.则称迭代法与方程组Ax=b是相容相容的。0 ()kk Mn nMCn nC()MM0nnC()MM引理引理1 迭代法迭代法 收敛当且仅当收敛当且仅当引理引理4.3.2 设设 ，则有，则有 1. 对对 上的任意矩阵范数上的任意矩阵范数 ，有，有2. 对任

13、给的对任给的 ,存在存在 上的算子范数上的算子范数 使得使得(1)( )kkxMxg注注: 引理的详细证明过程引理的详细证明过程,请阅读第四章请阅读第四章,第第3节节.定理定理1 1 当且仅当当且仅当 定理定理2 2 单步线性定常迭代法收敛当且仅当单步线性定常迭代法收敛当且仅当1.M（）,0()n nkkMRM1.M（）例例 1 当方程组的系数矩阵为122111221A可以验证：Jacobi迭代收敛，而Gauss-Seidel迭代不收敛。 例例 2 当方程组的系数矩阵为211111112A可以验证：Jacobi迭代不收敛，而Gauss-Seidel迭代收敛。 例例3 3 对于方程组对于方程组1

14、212321532xxxx Jacobi Jacobi迭代公式为迭代公式为，迭代矩阵为23103530, ( )10BB Gauss-Seidel Gauss-Seidel迭代公式为迭代公式为(1)()121233(1)(1)522133kkkkxxxx，迭代矩阵为231091090, ( )10GG(1)()121233(1)()522133kkkkxxxx显然，两种迭代都不收敛。显然，两种迭代都不收敛。 若将方程的顺序调整，即若将方程的顺序调整，即1212532321xxxx Jacobi Jacobi迭代公式为迭代公式为，迭代矩阵为353 1010320,( )10BB Gauss-Se

15、idel Gauss-Seidel迭代公式为迭代公式为(1)()321255(1)(1)312122kkkkxxxx，迭代矩阵为359109100, ( )10GG(1)()321255(1)()312122kkkkxxxx显然，两种迭代都收敛。显然，两种迭代都收敛。1 qM1I)(kx*x,1)0()1(*)(xxqqxxkk定理定理3 若迭代矩阵M的范数 且 ，则单步线性定常迭代的第k次迭代向量与准确解的误差有估计式 ,1)()1(*)(kkkxxqqxx1 qM1I)(kx*x定理定理4 若迭代矩阵M的范数 且 ，则单步线性定常迭代的第k次迭代向量与准确解的误差有估计式定理定理5 5 若系数矩阵A对称，对角线元素),.,2 , 1(0niaii则Jacobi迭代收敛的充分必要条件是A和2D-A都正定。定理定理6 6 若系数矩阵A正定，则G-S迭代收敛。定理定理7 7 若矩阵A是严格对角