解线性方程组的迭代法名师优质课赛课一等奖市公开课获奖课件

考虑Ax=b，其中detA0。当A为低阶稠密矩阵时，上一章讨论选主元素消去法是有效方法。但对于工程实践中大型稀疏矩阵方程组（A阶数n很大，但零元素较多，如：n>)，则利用迭代法解此线性方程组是适当。迭代法在计算机内存和运算两方面，通常都可利用A中有大量零元素特点。下面先举例说明迭代法基本思想。第七章解线性方程组的迭代法§1引言例：第1页

先将Ax=b转化为等价方程组迭代公式：选取初始向量第2页经10次迭代解：第3页准确解为若取则普通地，对于线性方程组Ax=b.转化为等价方程组x=Bx+f,设有唯一解，则（1）又设为任取初值向量。按以下方式产生迭代向量序列：

可见由迭代法产生向量序列逐次迫近方程组准确解。不过，并不是对任何一个方程组，由迭代法产生向量序列均收敛到准确解。如用迭代法解下面线性方程组：k为迭代次数。（2）第4页由（1），（2）得：，从而递推得：为讨论收敛性，引进误差向量：定义1：对x=Bx+f.用（2）逐步求近似解方法称为迭代法（又称为一阶定常迭代法，这里B与k无关）。若存在（记为）。称此迭代法收敛。

显然就是方程组解。若极限不存在，则称迭代法发散。亦即B满足什么条件使（零矩阵）。要收敛于。则须考查B在什么条件下，第5页§2Jacobi迭代法与Gauss-Seidel迭代法一Jacobi迭代法又将A分裂为：A=M-N。则（1）等价于Mx=Nx+b(3)其中M应选择为一个非奇异阵。并使Mz=f轻易求解。对Ax=b.设detA0.0.(i=1~n)(1)将A改写为:A=--=D-L-U(2)第6页（初始向量），其中：（5）J称为Jacobi迭代法迭代矩阵。可得:Jacobi迭代公式：尤其地，若选取M=D则N=M-A=L+U从而（1）化为：Dx=(L+U)x+b对应于（3）可结构一个迭代过程：初始向量，（4）Jacobi迭代法分量形式：引进记号：为第k次近似，由（5）有:第7页Jacobi迭代公式简单，由公式（5），（6）可知，每迭代一次只需计算一次矩阵与向量乘法，计算机中只需要两组工作单元用来保留及且可用来控制迭代终止。由迭代计算公式可知，迭代法一个主要特征是计算过程中原来矩阵A数据一直不变。前一个例子即为Jacobi法求解，在此不再举例。（6）第8页在（3）中选取M=D-L（下三角阵），则N=M-A=U。从而（1）化为等价：（D-L）x=Ux+b(7)可得Gauss-Seidel迭代公式：初始向量x(0)，，其中，（8）(9)，有迭代公式（9）G称为Gauss-Seidel迭代矩阵。G-S迭代法分量形式为：记二Gauss-Seidel迭代法第9页Gauss-Seidel迭代法每迭代一次只需计算一次矩阵与向量乘法，但G-S迭代法比Jacobi迭代法有一个显著优点，那就是计算机上仅需一组工作单元用来保留分量（或分量）当计算出就冲掉旧分量。由G-S迭代公式（9）可看出在一步迭代中，计算分量时利用了已计算出来新分量所以，G-S迭代法能够看作是Jacobi迭代法一个修正。例：用G-S方法解下面方程组，其准确解为：第10页解：由（9）可得本题G-S迭代公式为：经5次迭代得:第11页

从此例可见，G-S迭代法比Jacobi迭代法收敛快（初始向量相同，到达一样精度，所须迭代步数较少），但这个结论对Ax=b矩阵A满足一些条件才是正确，甚至有这么线性方程组，用Jacobi方法是收敛，而用G-S迭代法却是发散。此例用Jacobi迭代法收敛而G-S迭代法却发散。简明分析以下：（需要下一节知识）如线性方程组：第12页第13页§3迭代法的收敛性第14页第15页证实：（1）第16页（2）利用此递推式即可得误差预计。第17页例：考查用Jacobi方法求解前例1中线性方程组收敛性.

解：则Jacobi迭代矩阵为：故解此方程组Jacobi方法收敛。第18页第19页第20页但要注意当q≈1时，较大，尽管||-||很小，却有可能误差向量模很大，迭代法收敛很慢。而且此充分性条件结果（3）能够用来事先确定需要迭代多少次才能确保定义：（对角占优矩阵）设A=（1）若>>0(i=1∼n)即A每一行对角元素绝对值严格大于同行其它元素绝对值之和。则称A为严格对角占优矩阵。定理解方程组Ax=bG-S迭代法收敛充分必要条件是G为G-S迭代矩阵。第21页（2）若≥>0(i=1∼n)，且最少有一个不等式严格成立则称A为弱对角占优矩阵。其中为r阶子矩阵，为n-r阶子矩阵（1≤r<n),则称矩阵A为可约。若不存在排列矩阵P使上式成立，则称A为不可约矩阵。定义：（可约与不可约矩阵）设A=，当n≥2时，假如存在n阶排列矩阵P使=成立。求解。实际上，由AX=b化为：设其、为r维向量当A为可约矩阵，则AX=b可经过若干行列重排化为两个低阶方程组第22页另外，A为可约矩阵充要条件：存在指标集J使证实：1）A为严格对角占优阵，采取反证法。若detA=0，则Ax=0有非零解。设为定理（对角占优定理）若为严格对角占优阵或为不可约弱对角占优阵，则A是非奇异阵。（1）设由齐次方程中第k个方程得：得：于是，求解Ax=b化为求解：第23页2）A为不可约弱对角占优阵。采取反证法。设（由弱对角占优定义）成立。再定义下标集合：则J非空。不然J为空，有即有： 这与严格对角占优阵矛盾，故detA0由此可见，当不然，上式就与A为弱对角占优阵矛盾。对任意在（1）中取k=m。将造成与（2）矛盾。故第24页但对任意从而A为可约矩阵，这与A为不可约矩阵假设矛盾。定理:若为严格对角占优矩阵或为不可约对角占优矩阵，则对任意初始向量，方程组Ax=bJacobi迭代法和G-S迭代法均收敛。且G-S迭代法比Jacobi迭代法收敛速度快。证实：设A为不可约对角占优矩阵，先证实G-S迭代法收敛。由弱对角占优阵假设知而G-S迭代矩阵为第25页则:这一结论表明detC=0根均满足：即故G-S法收敛。在同一条件下，对于Jacobi方法完全类似于上可证。当A为严格对角占优阵时，证实方法完全类似。下面来证实当这是因为A为不可约阵，则C也不可约，由A为弱对角矩阵，可得：

且最少有一个不可约等式严格成立，这表明当时，C为不可约弱对角占优矩阵，于是由前一个定理可知当第26页逐次超松弛迭代法（SuccessiveOverRelaxationMethod.简称为SOR法）是Gauss-Seidel法一个加速方法。这是解大型矩阵方程组有效方法之一，含有计算公式简单，程序设计轻易，占用计算机内存较少等优点，但需要选择好加速因子，即最正确加速因子。对Ａx＝ｂ（１）其中为非奇异矩阵，且设,分解：Ａ＝Ｄ－Ｌ－Ｕ（２）设已知第k次迭代向量，及第k＋１次迭代向量分量(j=1,2,……i-1),现在来计算分量:§4解线性方程组的超松弛迭代法第27页先用Ｇ－Ｓ迭代法求出辅助量（预测）将（３）代入（4）即得解Ａx＝ｂ逐次超松弛迭代公式：再取为与某种平均值（即加权平均）即（5）其中称为松弛因子，或写为：第28页显然时，解（１）ＳＯＲ法即为Gauss-Seidel迭代法。ＳＯＲ法中每迭代一次，主要计算量是计算一次矩阵与向量乘法。由（５）可见在计算机上用ＳＯＲ法解方程组只需一组工作单元，方便存放近似解。迭代算时，当时，称（５）为低松弛法；当时，称（５）为超松弛法。可用来控制迭代终止。第29页第30页解：取。则SOR迭代公式为：对取其它值，迭代次数以下表，由此例可见，松弛因子选择得好，会使SOR迭代法收敛大大加速。本例中，是最正确松弛因子。第31页松弛因子

1.0221.1171.2121.3*11*最少迭代次数1.4141.5171.6231.7331.8531.9109第32页下面考查SOR迭代公式矩阵形式，由（5）可改写为：称为SOR方法迭代矩阵，应用关于迭代法收敛性定理于（8）可得：第33页定理：对Ax=b，且则解方程组充要条件是：（）<1

引进超松弛法想法是希