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

第四章线性方程组迭代解法第1页，课件共75页，创作于2023年2月第四章目录§1向量序列与矩阵序列的极限§2Jacobi迭代法§3Gauss~Seidel迭代法§4松驰法§5迭代法的收敛条件及误差估计5.1矩阵的谱半径5.2迭代法的收敛条件5.3误差估计第2页，课件共75页，创作于2023年2月第四章

方程组的迭代解法概述

这一章讨论线性方程组的另一类解法——迭代法，由于

迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别

适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）

的线性方程组。解线性方程组的迭代法的基本思想与解方程的迭代法相

似，首先将方程组Ax=b化为等价方程组x=Mx+g，其中M

为n阶方阵，b=(b1,b2,…,bn)T，g

Rn，任取初始向量x(0)

Rn，

代入迭代公式：产生向量序列{x(k)}，若此序列收敛于x*，则有x*=Mx*+g，即

x*为原方程组的解。因此，可根据精度要求选择一个合适的x(k)

（k充分大时）作为近似解，这就是解线性方程组的迭代法，

上式称为迭代格式，M称为迭代矩阵，若序列{x(k)}极限存

在，称此迭代过程收敛，否则称为发散。

第3页，课件共75页，创作于2023年2月§1向量与矩阵的范数与求解方程类似，需要讨论的问题是：如何建立迭代公式，向量序列的收敛条件是什么，若向量序列{x(k)}收敛，如何进行误差估计？第4页，课件共75页，创作于2023年2月4.1向量与矩阵的范数

这三个性质刻画了向量长度的基本特征，并可以用其将平面向量长度的概念推广到一般n维向量，于是有如下定义：定义1下屏将给出范数的种类：第5页，课件共75页，创作于2023年2月常用的向量范数容易证明它们都满足上述三条性质。可以看出，2范数是平面向量长度计算公式在形式上的推广，也是线性代数中的内积定义。此处引入多种范数来刻画向量的大小，是为了在不同情况下用不同的范数研究问题。向量范数的证明：（只对第三条）对∞范数：前面2条显然，对第三条，由于对任意实数x,y，绝对值不等式：|x+y|≤|x|+|y|成立，因而有:分别称为向量x的2范数，1范数，无穷范数。第6页，课件共75页，创作于2023年2月对2范数利用实数的柯西不等式：于是，有：常用的向量范数（续）第7页，课件共75页，创作于2023年2月Rn中范数的等价性

例如可证明如下等价性：

所以，2范数与

范数是等价的。不难证明：——亦即1范数与

范数是等价的。事实上:Rn中任意两种范数都是等价的。第8页，课件共75页，创作于2023年2月矩阵范数

定义2对任意n阶方阵A=(aij)n

n，若对应一个非负实数||A||，满足：则称||A||为矩阵A的范数。与向量范数定义比较，前三条性质只是向量范数定义的推广，而第四条性质则是矩阵乘法性质的要求，它使矩阵范数在数值计算中使用更方便。第9页，课件共75页，创作于2023年2月常用的矩阵范数常用的矩阵范数有：它们分别叫做矩阵的

范数，1范数，2范数，F范数，矩阵F范数是向量2范数的推广，矩阵

范数，1范数计算容易，而矩阵2范数与ATA的特征值有关，所以又称为谱范数，它的计算较困难，但因为它有一些好的性质，所以也是常用的范数。第10页，课件共75页，创作于2023年2月常用的矩阵范数（续）可以证明，这些范数都满足定义2。以||A||

为例，前2条性质显然成立，而对：第11页，课件共75页，创作于2023年2月最大行和矩阵范数的证明第12页，课件共75页，创作于2023年2月最大行和矩阵范数的证明第13页，课件共75页，创作于2023年2月范数的相容性

在误差估计中，由于矩阵与向量会同时用到，我们总希望有上面的不等式成立，但对任意的向量范数与矩阵范数却未必如此，因而特别地把满足此不等式的范数称为相容的，可以证明，上述常用的范数是相容的，即有：在使用范数时，应选用相容的矩阵范数与向量范数。分别称为的关于P范数的绝对误差与相对误差。有了矩阵范数，就可以用它描述矩阵的误差，设是A的近似矩阵，称为的残差阵，则：第14页，课件共75页，创作于2023年2月求范数举例例10第15页，课件共75页，创作于2023年2月向量序列与矩阵序列的极限与求解方程类似，需要讨论的问题是：如何建立迭代公式，向量序列的收敛条件是什么，若向量序列{x(k)}收敛，如何进行误差估计？§1向量序列与矩阵序列的极限由于Rn中的向量可与Rn的点建立一一对应关系，因此由点列的收敛概念及向量范数的等价性，可得到向量序列的收敛概念。定义3第16页，课件共75页，创作于2023年2月向量序列与矩阵序列的极限（续）

n维点列收敛的一种等价描述是其对应坐标序列均收敛，向量序列也有类似的结论。定理1

第17页，课件共75页，创作于2023年2月矩阵序列的收敛概念及定理定义3完全类似地，可以定义矩阵序列的收敛：与向量序列类似，也有：定理2第18页，课件共75页，创作于2023年2月4.3矩阵的谱半径

迭代法的收敛性与迭代矩阵的特征值有关：设A为n阶方阵，

i(i=1,2,…，n)为A的特征值，称特征值模的最大值为矩阵A的谱半径，记为：定义5第19页，课件共75页，创作于2023年2月矩阵的谱半径（续）

矩阵的谱半径与范数之间有如下关系：设x为对应于特征值

的A的特征向量，则由：

这个不等式对A的任何范数、任意特征值都成立，因此，可得矩阵A的谱半径与A的范数之间的一个重要关系：A的谱半径不超过A的任一种范数。即：第20页，课件共75页，创作于2023年2月公式的重要性说明

它之所以重要是因为：

(A)难计算，而||A||∞、||A||1计算容易，并且对于任意正数

，存在一种矩阵范数很接近

(A)，使得成立：对任意n阶方阵A，一般不存在矩阵范数使

(A)=||A||，但若A为对称矩阵，则有：

下面的结论对建立迭代法的收敛条件十分重要：定理3第21页，课件共75页，创作于2023年2月定理3（续）证明：第22页，课件共75页，创作于2023年2月由5.1的结果，可以得到如下收敛定理：定理4对任意初始向量x(0)和右端项g，由迭代格式：证明：第23页，课件共75页，创作于2023年2月推论1第24页，课件共75页，创作于2023年2月可以看出，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有0.0005以下的误差，但准确解却相差很大。4.2方程组的误差分析数值稳定的算法是否一定能求得精度比较高的解呢？回答是不一定，解的精度还与方程组本身的性态有关，下面来考察几个例：例11第25页，课件共75页，创作于2023年2月例12若其系数，常数项改用三位有效数字的小数表示，则方程组为：第26页，课件共75页，创作于2023年2月右端项b产生0.1%的变化

引起解的变化最大变化184%。初始数据的误差（相对）<0.3%=0.003，而解的相对误差却超过50%。例13第27页，课件共75页，创作于2023年2月方程组的性态讨论

——病态、良态在许多实际问题中，线性方程组的系数矩阵和右端项的元素大多为前面计算的结果，因此上述例中的微小误差是避免不了。而对上述例中的方程组，无论用多么稳定的算法求解，计算中产生的微小误差就使解面目全非，所以这些方程组的性态是很差的。当方程组Ax=b的系数矩阵与右端向量b的微小变动（小扰动）而引起解严重失真时，称此方程组为病态方程组，其系数矩阵A称为病态矩阵，否则称为良态方程组，A称为良态矩阵，为了定量刻画方程组“病态”的程度，下面对方程组Ax=b在系数矩阵A及右端项b有扰动的几种情形进行讨论。第28页，课件共75页，创作于2023年2月此不等式表明，当右端项有扰动时，解的相对误差不超过b的相对误差的倍。首先考察右端项b的扰动对解的影响，设b有扰动

b，A为准确,记引起解x的扰动为

x,即：第29页，课件共75页，创作于2023年2月方程组的性态讨论（续2）当b为精确的而A有微小扰动

A时，在

A充分小时也同样可推得：紧接下屏讨论：第30页，课件共75页，创作于2023年2月第31页，课件共75页，创作于2023年2月方程组的性态讨论续（3）而当A,b同时有微小扰动

A，

b时，则可进一步导出更一般的误差估计式：注意到：第32页，课件共75页，创作于2023年2月在

b充分小时，此式右端实际上即为：方程组的性态讨论续（4）第33页，课件共75页，创作于2023年2月矩阵的条件数在三种情况下得到的这三个不等式反映了解的相对误差与A及b的相对误差的关系；数||A||||A-1||越小，解的相对误差也越小；反之数||A||||A-1||越大，解的相对误差也越大，实际上这个数反映了解对方程组原始数据的敏感程度，揭示了矩阵A和方程组本身的性态，称之为方程组或矩阵A的条件数，记作：cond(A)越大，A的病态程度越严重。至于cond(A)多大才算病态，这是一个相对概念，没有一个严格的数量界限。第34页，课件共75页，创作于2023年2月判断病态矩阵的几点参考求条件数要计算逆阵的范数，很不方便，如下一些现象可作为判断病态矩阵的参考。（1）在用主元消去法时消元过程出现小主元（如例12）（2）矩阵A中元素间数量级相差很大；（3）A的行列式det(A)满足（行列式值相对很大）：（4）矩阵的某些行（或列）近似相关（如例11）。第35页，课件共75页，创作于2023年2月利用条件数判断矩阵的性态举例A的条件数很大，所以方程组是病态的。的特例，它是典型的“病态”阵，n越大，“病态”越严重，如n=6时，cond(A)=29×106，对严重“病态”的方程组，即使用主元素法求解也难以保证数值稳定性。第36页，课件共75页，创作于2023年2月§3雅可比（Jacobi）迭代法设有n阶线性方程组：简记为：其系数矩阵A非奇异，不妨设aii≠0(1,2,…,n)可将上式改写为等价方程组：第37页，课件共75页，创作于2023年2月雅可比（Jacobi）迭代法（续）也可写作为：可简记为：由此可建立迭代格式：第38页，课件共75页，创作于2023年2月Jacobi迭代法定义

选取初始向量x(0)代入（4-4）右端，可得x(1)=Bx(0)+g，再将x(1)代入（3-4）右端，可得x(2)=Bx(1)+g，如此继续下去，就产生一个向量序列{x(k)}，按（3-2）或（3-3）格式迭代求解的方法称为雅可比（Jacobi）迭代法，又叫简单迭代法。迭代式（3-4）中的B称为迭代矩阵，它可直接由（3-2）或（3-3）得到，也可用系数矩阵A来表示：若将系数矩阵A分解为A=D–L–U，其中：第39页，课件共75页，创作于2023年2月Jacobi迭代法定义（续）式（3-5）为简单迭代法的矩阵形式。第40页，课件共75页，创作于2023年2月Jacobi迭代法举例用Jacobi迭代法求解线性方程组：

例1解：由第一个方程解x1，第二个方程解x2，第三个方程解x3得Joacbi迭代格式为：继续迭代下去，迭代结果见表3-1：取x(0)=(0,0,0)T代入迭代式（3-6）或（3-7）得：第41页，课件共75页，创作于2023年2月Jacobi迭代法举例00.00000.00000.000017.20008.30008.400029.710010.700011.5000310.570011.570012.4820410.853511.853412.8282510.951011.951012.9414610.983411.983412.9504710.994411.998112.9934810.998111.994112.9978910.999411.999412.9992表3-1k

x1(k)

x2(k)

x3(k)

迭代9次，得近似解x(9)=(10.9994,11.9994,12,9992)T，此方程组的准确解为x=(11,12,13)T，从表3-1可以看出，随着迭代次数的增加，迭代结果越来越接近精确解。第42页，课件共75页，创作于2023年2月收敛条件迭代格式收敛的充要条件是G的谱半径<1。对于Jacobi迭代，我们有一些保证收敛的充分条件定理：若A满足下列条件之一，则Jacobi迭代收敛。①A为行对角占优阵②A为列对角占优阵第43页，课件共75页，创作于2023年2月证明：＃证毕第44页，课件共75页，创作于2023年2月例4

讨论Jacobi迭代法的收敛性。

解：首先要求出迭代矩阵，对Jacobi迭代法：第45页，课件共75页，创作于2023年2月第46页，课件共75页，创作于2023年2月§3高斯塞德尔(Gauss-Seidel)迭代法

Jacobi迭代法的优点是公式简单，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算x(k+1)时是用x(k)的全部分量代入求x

(k+1)的全部分量。因此需同时保留两个近似解向量x(k)和x(k+1)。第47页，课件共75页，创作于2023年2月第48页，课件共75页，创作于2023年2月Gauss-Seidel迭代法求解例2用Gauss-Seidel迭代法求解例1

解：Gauss-Seidel迭代格式为：仍取x

(0)=(0,0,0)T，

计算结果见下表：

00.00000.00000.000017.20009.020011.6440210.430811.671912.8205310.931311.957212.9778410.991311.994712.9972510.998911.999312.9996610.999911.999913.0000kx1(k)x2(k)x3(k)

表3-2

显然，用Gauss-Seidel迭代法比Jacobi迭代法收敛快，这个结论在多数情况下是成立的，但也有Gauss-Seidel迭代比Jacuobi迭代收敛慢，甚至还有Jacobi迭代收敛，Gauss-Seidel迭代发散的情形。第49页，课件共75页，创作于2023年2月求例2中的Gauss-Seidel法的迭代阵M的两种方法第50页，课件共75页，创作于2023年2月求例2中的Gauss-Seidel法的迭代阵M的两种方法续1方法2：可按代入法求M，以避免计算逆矩阵，在Gauss-Seidel迭代式（3-10）中，第二个式子中的以第一个式子代替。可将第二式右端上标都化为k（可以不管常数）：第51页，课件共75页，创作于2023年2月求例2中的Gauss-Seidel法的迭代阵M的两种方法续2由于（3-10）第一式及（3-11），（3-12）的右端上标均为k，即为同时替换迭代式，类似于Jacobi迭代法可直接由它们得迭代阵为：第52页，课件共75页，创作于2023年2月收敛条件迭代格式收敛的充要条件是G的谱半径<1。我们看一些充分条件定理：若A满足下列条件之一，则Gauss-Seidel迭代收敛。①A为行或列对角占优阵②A对称正定阵第53页，课件共75页，创作于2023年2月证明：设G的特征多项式为，则为对角占优阵，则时为对角占优阵即即＃证毕注：二种方法都存在收敛性问题。有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛。第54页，课件共75页，创作于2023年2月两种迭代法举例例4

讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性。

解：首先要求出迭代矩阵，然后利用推论1（（充分条件）及定理4（充分必要条件）进行讨论。

对Jacobi迭代法：第55页，课件共75页，创作于2023年2月例4（Jacobi迭代法续）第56页，课件共75页，创作于2023年2月例4（G-S迭代法续）对G-S迭代法：

第57页，课件共75页，创作于2023年2月两种迭代法说明注1：对G-S法，为避免求逆阵可按下面两个方法：第58页，课件共75页，创作于2023年2月两种迭代法说明（续）第59页，课件共75页，创作于2023年2月§4松驰法

通过引入参数，在Gauss-Seidel法的基础上作适当修改，在不增加过多的计算量的条件下，可得到一种新的，收敛更快的迭代法。将Gauss-Seidel迭代格式（3-9）改写为：第60页，课件共75页，创作于2023年2月松驰法（续）

通过选择适当的参数

使此迭代格式收敛更快。

称为松驰因子，

<1时称为低松驰，

>1时称为超松驰法，

=1是Gauss-Seidel迭代，简称为SOR法（SuccessiveOver-Relaxation）。第61页，课件共75页，创作于2023年2月将（3-13）代入（3-14）可得：

其矩阵形式为：

所以SOR法的迭代矩阵为：第62页，课件共75页，创作于2023年2月用SOR法解线性方程组（例3）

例3

取

=1.4,x

(0)=(1,1,1)T，用SOR法解线性方程组第63页，课件共75页，创作于2023年2月例3（续1）继续下去，计算结果如下：01.00001.00001.000011.00001.00001.560021.00001.39201.618431.27441.46821.640641.21801.41361.593451.20231.39161.606861.19321.40341.600771.20511.40271.601681.19991.40001.599491.20001.39961.6001表3-3kx1(k)

x2(k)

x3(k)

第64页，课件共75页，创作于2023年2月例3（续2）所以，方程组近似解为:

松驰因子

的选取对收敛速度影响极大，如何选取

使收敛速度加快，或达到最快？这是非常重要的，但又很困难，目前尚无可供实用的计算最佳松驰因子的办法，通常的作法是采用试算法：即从同一初值出发，选不同的松驰因子进行试算，迭代相同的次数，来比较残量r

(k)=b

Ax(k)的大小，选取使r(k)最小（各分量总体相差最小）的松驰因子。这样做较简单，但比较有效。小结如下：第65页，课件共75页，创作于2023年2月迭代法的收敛条件（续2）定理4表明，迭代法收敛与否只决定于迭代矩阵

的谱半径，与初始向量及方程组的右端项无关。对同一方程组，由于不同的迭代法其迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情形。推论2第66页，课件共75页，创作于2023年2月

定理4虽然给出了判别迭代法收敛的充要条件，但实际使用时很不方便，因为求逆矩阵和特征值的难度并不亚于用直接法求解线性方程组。而推论1仅为充分条件。很多情况下如例3，由推论1无法判别收敛性。下面对一些特殊的方程组，从方程组本身出发给出几个常用的判别条件，而不必求迭代阵的特征值或范数。直接用矩阵A判定敛散性且至少有一个i值，使上式中不等号严格成立，则称A为弱对角占优阵。若对所有i，上式中不等号均严格成立，则称A为严格对角占优阵。

定义4第67页，课件共75页，创作于2023