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

《5第六章解线性方程组的迭代法.ppt》由会员分享，可在线阅读，更多相关《5第六章解线性方程组的迭代法.ppt（37页珍藏版）》请在三一办公上搜索。

1、考虑 Ax=b，其中detA 0。当A为低阶稠密矩阵时，上一章讨论的选主元素消去法是有效方法。但对于工程实践中的大型稀疏矩阵方程组（A的阶数n很大，但零元素较多，如：n)，则利用迭代法解此线性方程组是合适的。迭代法在计算机内存和运算两方面，通常都可利用A中有大量零元素的特点。下面先举例说明迭代法的基本思想。,第七章 解线性方程组的迭代法,1 引言,例：,先将Ax=b转化为等价方程组,迭代公式：选取初始向量,经10次迭代解：,一般地，对于线性方程组 Ax=b.转化为等价方程组 x=Bx+f,设有唯一解，则（1）又设 为任取初值向量。按下列方式产生迭代向量序列：,可见由迭代法产生的向量序列 逐次逼

2、近方程组的精确解。但是，并不是对任何一个方程组，由迭代法产生的向量序列 均收敛到精确解的。如用迭代法解下面的线性方程组：,定义1：对x=Bx+f.用（2）逐步求近似解的方法称为迭代 法（又称为一阶定常迭代法，这里B与k无关）。若 存在（记为）。称此迭代法收敛。显然 就是方程组的解。若极限不存在，则称迭代法发散。,2 Jacobi迭代法与Gauss-Seidel迭代法,一 Jacobi迭代法,特别地，若选取 M=D 则N=M-A=L+U 从而（1）化为：Dx=(L+U)x+b,Jacobi迭代公式简单，由公式（5），（6）可知，每迭代一次只需计算一次矩阵与向量乘法，计算机中只需要两组工作单元用来

3、保存 及 且可用 来控制迭代终止。由迭代计算公式可知，迭代法一个重要特征是计算过程中原来矩阵A数据始终不变。前一个例子即为Jacobi法求解，在此不再举例。,（6）,在（3）中选取M=D-L（下三角阵），则N=M-A=U。从而（1）化为等价的：（D-L）x=Ux+b(7)可得Gauss-Seidel迭代公式：,二 Gauss-Seidel迭代法,Gauss-Seidel迭代法每迭代一次只需计算一次矩阵与向量的乘法，但G-S迭代法比Jacobi迭代法有一个明显的优点，那就是计算机上仅需一组工作单元用来保存 分量（或 分量）当计算出 就冲掉旧的分量。由G-S迭代公式（9）可看出在的一步迭代中，计算

4、分量 时利用了已计算出来的新分量 因此，G-S迭代法可以看作是Jacobi迭代法的一个修正。,例：用G-S方法解下面方程组，其精确解为：,解：由（9）可得本题G-S迭代公式为：,经5次迭代得:,从此例可见，G-S迭代法比Jacobi迭代法收敛快（初始向量相同，达到同样精度，所须迭代步数较少），但这个结论对Ax=b的矩阵A满足某些条件才是对的，甚至有这样的线性方程组，用Jacobi方法是收敛的，而用G-S迭代法却是发散的。,此例用Jacobi迭代法收敛而G-S迭代法却发散。简要分析如下：（需要下一节的知识）,如线性方程组：,3 迭代法的收敛性,证明：（1）,（2）,利用此递推式即可得误差估计。,

5、例：考察用Jacobi方法求解前例1中线性方程组的收敛性.解：,但要注意 当q1时，较大，尽管|-|很小，却有可能误差向量模 很大，迭代法收敛很慢。而且此充分性条件的结果（3）可以用来事先确定需要迭代多少次才能保证,定义：（对角占优矩阵）设A=（1）若 0(i=1n)即A的每一行对角元素绝对值严格大于同行其它元素绝对值之和。则称A为严格对角占优矩阵。,定理 解方程组Ax=b的G-S迭代法收敛的充分必要条件是G为G-S迭代矩阵。,（2）若 0(i=1n)，且至少有一个不等式严格成立则称A为弱对角占优矩阵。,另外，A为可约矩阵的充要条件：存在指标集J 使,证明：1）A为严格对角占优阵，采用反证法。

6、若detA=0，则Ax=0有非零解。设为,定理（对角占优定理）若 为严格对角占优阵或为不可约弱对角占优阵，则A是非奇异阵。,（1）,于是，求解 Ax=b 化为求解：,2）A为不可约弱对角占优阵。采用反证法。,设（由弱对角占优定义）成立。再定义下标集合：,则J非空。否则J为空，有,即有：这与严格对角占优阵矛盾，故detA 0,但对任意 从而A为可约矩阵，这与A为不可约矩阵假设矛盾。,定理:若 为严格对角占优矩阵或为不可约对角占优矩 阵，则对任意的初始向量，方程组Ax=b的Jacobi迭代法和G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。证明：设A为不可约对角占优矩阵，先证明G

7、-S迭代法收敛。,由弱对角占优阵假设知 而G-S迭代矩阵为,则:,在同一条件下，对于Jacobi方法 完全类似于上可证。当A为严格对角占优阵时，证明方法完全类似。,下面来证明当 这是因为A为不可约阵，则C也不可约，由A为弱对角矩阵，可得：,且至少有一个不可约等式严格成立，这表明当 时，C为不可约弱对角占优矩阵，于是由前一个定理可知当,逐次超松弛迭代法（Successive Over Relaxation Method.简称为SOR法）是Gauss-Seidel法的一种加速方法。这是解大型矩阵方程组的有效方法之一，具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要选择好的加速因子，

8、即最佳的加速因子。,对x（）其中为非奇异矩阵，且设,分解：（）设已知第k次迭代向量，及第k次迭代向量的分量(j=1,2,i-1),现在来计算分量:,4 解线性方程组的超松弛 迭代法,先用迭代法求出辅助量（预测）,将（）代入（4）即得解x的逐次超松弛迭代公式：,再取为与的某种平均值（即加权平均）即,法中每迭代一次，主要计算量是计算一次矩阵与向量乘法。由（）可见在计算机上用法解方程组只需一组工作单元，以便存放近似解。迭代算时，,当时，称（）为低松弛法；当时，称（）为超松弛法。,可用来控制迭代终止。,解：取。则SOR迭代公式为：,对 取其它值，迭代次数如下表，由此例可见，松弛因子选择得好，会使SOR

9、迭代法的收敛大大加速。本例中，是最佳松弛因子。,松弛因子 1.0 22 1.1 17 1.2 12 1.3*11*最少迭代次数 1.4 14 1.5 17 1.6 23 1.7 33 1.8 53 1.9 109,下面考察SOR迭代公式的矩阵形式，由（5）可改写为：,称 为SOR方法的迭代矩阵，应用关于迭代法的收敛性定理于（8）可得：,定理：对Ax=b，且 则解方程组的充要条件是：（）1,引进超松弛法的想法是希望能选择松弛因子使迭代过程（5）收敛较快，也就是应选择因子 使,定理:(必要条件）对Ax=b,的SOR方法若收敛，则：0 2,因此 即：0 2,此结果表明要使SOR放收敛，松弛因子 必须在（0，2）中。那么，反过来。若选取 在（0，2）中，SOR法是否一定收敛呢？,定理（充分条件）若A为对称正定矩阵，且0 2,则解（1）的SOR法必收敛。,证明：若能证明在定理条件下，对 的任一特征值有：-1 1,则定理得证。事实上，设y为对应 的 的特征向量。即：,亦即：(1-)D+Uy=(D-L)y为找的表达式。考虑内积：,（(1-)D+Uy，y）=（(D-L)y，y），则有,而：,设 由于 则,因此：,从而：,由（9）（10）有：,