第三章 线性方程组的迭代解法

第三章线性方程组的迭代解法第一页，共二十三页，编辑于2023年，星期四任取一个向量x(0)作为x的近似解，用迭代公式则有x*=Bx*+f，即x*是(3.2)的解，当然x*也就是Ax=b的解.1如何构造迭代公式x(k+1)=Bx(k)+f.这样的构造形式不止一种，它们各对应一种迭代法.2迭代法产生的向量序列{x(k)}的收敛条件是什么，收敛速度如何.结束

2从以上的讨论中，可以看出，迭代法的关键有：x(k+1)=Bx(k)+f,(k=0,1,2,)(3.3)产生一个向量序列{x(k)}，若第二页，共二十三页，编辑于2023年，星期四先看一个算例：按下式进行迭代

(k=0,1,2,)结束

33.2几种常用的迭代法公式例13.2.1Jacobi迭代法从以上三个方程中分别解出x1,x2,x3第三页，共二十三页，编辑于2023年，星期四任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列{x(k)}(k=0,1,2,)，列表如下表3-1。容易验证，原方程组的精确解为x=(1,2,3)T，从上面的计算可看出，{x(k)}收敛于精确解.一般说来，对方程组：设aii≠0(i=1,2,,n)，从第i个方程解出xi，得等价的方程组：k012345678x100.30000.80000.91800.97160.98040.99620.99850.9998x201.50001.76001.92601.97001.98971.99611.99861.9998x302.00002.66002.95402.95402.98232.99382.99772.9997结束

4第四页，共二十三页，编辑于2023年，星期四迭代公式为：

i=1,2,,n(3.5)(3.6)这种迭代形式称为Jacobi迭代法(雅可比迭代法)，也称简单迭代法.Jacobi迭代法的矩阵迭代形式:(推导)结束

5其中第五页，共二十三页，编辑于2023年，星期四3.2.2Gauss-Seidel迭代法在Jacobi迭代法的迭代形式(3.6)中，可以看出，在计算时，要使用.但此时已计算出来.看来此时可提前使用代替，一般地，计算(n≥i≥2)时，使用代替(i>p≥1)，这样可能收敛会快一些，这就形成一种新的迭代法，称为Gauss-Seidel迭代法。例2用Gauss-Seidel迭代法计算例1并作比较.(k=0,1,2,)结束

6解迭代公式为：第六页，共二十三页，编辑于2023年，星期四用它计算得到的序列{x(k)}列表如表3-2：可见它对这一方程组比Jacobi迭代法收敛快一些。Gauss-Seidel迭代法的公式如下：(3.9)Gauss-Seidel迭代法的矩阵迭代形式：（推导）k0123456x100.30000.88040.98430.99780.99971.0000x201.50001.94481.99221.99891.99982.0000x302.68402.95392.99382.99912.99993.0000结束

7其中第七页，共二十三页，编辑于2023年，星期四SOR迭代法也称为逐次超松弛法，它可看成Gauss-Seidel迭代法的加速，Gauss-Seidel迭代法是SOR迭代法的特例.改写为结束

83.2.3SOR迭代法将Gauss-Seidel迭代法的(3.9)式记则第八页，共二十三页，编辑于2023年，星期四为加快收敛，在增量前加一个因子,得称此公式为SOR法(逐次超松弛法).从(3.13)式不难推出SOR法的矩阵迭代形式：今后可以看到，必须取0<ω<2，当ω=1时,就是Gauss-Seidel迭代法.当ω取得适当时，对Gauss-Seidel迭代法有加速效果.结束

9其中改写为第九页，共二十三页，编辑于2023年，星期四例3用Gauss-Seidel迭代法和取ω=1.45的SOR法计算下列方程组的解，当时退出迭代，初值取x(0)=(1,1,1)T。由表３-３和表３-４可见，达到同样的精度Gauss-Seidel迭代法要72步，而取ω=1.45的SOR法只要25步，可见当松弛因子选择适当时，SOR法有明显加速收敛作用，它常用于求解大型线性方程组。结束

10第十页，共二十三页，编辑于2023年，星期四3.3迭代法的一般形式的收敛条件定理3.1

对任意初始向量x(0)和f,由上式产生的迭代序列x(k)收敛的充要条件是ρ(B)<1.3.3.1一般迭代过程的收敛条件.结束

11证:1)必要性：x(k)收敛于x*,有x*=Bx*+f成立,记k=x(k)-

x*有k+1=x(k+1)-

x*

=Bx(k)+f-Bx*-f=B(x(k)

-x*)=Bk有k+1=Bk=B2k-1=…=Bk+10,这里0=x(0)-

x*,对任意的x(0)

,0=x(0)-

x*

也是任意的,因此要有Bk+100(k),必须有Bk0(k)由上章定理2.8,必有(B)<1.第十一页，共二十三页，编辑于2023年，星期四2)充分性：定理3.1是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况.但由于ρ(B)的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义.结束

12从上面的定理可以看到,迭代法的收敛与否与B的性态有关，而与初始向量x(0)和右端向量f无关.由于ρ(B)难于计算，而由定理2.7有ρ(B)≤||B||，||B||<1时,必有ρ(B)<1，于是得到：设(B)<1,则1不是B的特征值,有|I-B|0,于是(I-B)x=f有唯一解

,

记为x*,即有x*=Bx*+f成立,则k+1=B(x(k)

-x*)=Bk

仍成立,k+1=Bk+10仍成立,因此k+1

0(k)成立,也即是x(k)

x*(k)由上章定理2.8,由(B)<1,可得Bk+10(k)成立,第十二页，共二十三页，编辑于2023年，星期四定理3.2

若||B||=q<1，则由迭代格式x(k+1)=Bx(k)+f和任意初始向量x(0)产生的迭代序列x(k)收敛于准确解x*.本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当||B||≥1时,不能断定迭代不收敛.但由于||B||,特别是||B||1和||B||∞的计算比较容易，也不失为一种判别收敛的方法。利用此定理可以在只计算出x(1)时，就估计迭代次数k，但估计偏保守，次数偏大.称为事前误差估计.定理3.3若||B||=q<1，则迭代格式x(k+1)=Bx(k)+f产生的向量序列{x(k)}中结束

13同时当||B||<1时可以用来估计迭代的次数，或用来设置退出计算的条件.这时有定理3.3和定理3.4第十三页，共二十三页，编辑于2023年，星期四例4就例1中的系数阵A1和例3中的系数阵A2讨论Jacobi迭代法和Gauss-Seidel迭代法的收敛性.因为||BJ||∞=0.6<1，由定理3.2知Jacobi迭代法收敛。解：1）就A1讨论结束

14定理3.4若||B||=q<1，则x(k)的第k次近似值的近似程度有如下估计式：本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代向量对精确解的误差也足够小.称为事后误差估计.第十四页，共二十三页，编辑于2023年，星期四用定理3.2无法判断Jacobi迭代法收敛性，现计算ρ(BJ)。2）就A2讨论解之有三实根：λ1=0.9207,λ2=-0.2846,λ3=-0.6361.所以ρ(BJ)=0.9207<1，故Jacobi迭代法收敛.结束

15因为||BS||∞=0.3<1，由定理3.2知Gauss-Seidel迭代法收敛。第十五页，共二十三页，编辑于2023年，星期四||BS||∞=0.875，故Gauss-Seidel迭代法收敛.3.3.2从矩阵A判断收敛的条件下面讨论直接由矩阵A的性态,判定Ax=b使用迭代法是否收敛.讨论前必须先介绍几个概念：1对角优势若A=(aij)n×n满足且至少有一个I值，使成立,称A具有对角优势；结束

16第十六页，共二十三页，编辑于2023年，星期四若称A具有严格对角优势.定理3.5若A具有严格对角优势，则A非奇异。定理3.6

A不可约，且具有对角优势，则A非奇异.结束

172不可约如果矩阵A能通过行对换和相应的列对换，变成：矩阵

A是否可约是不易判别的，但以下两条准则比较常用:A没有零元素或零元素太少(少于n-1)时不可约;三对角阵如果三条对角线上的元素都不为零时不可约.的形式,其中A11和A22为方阵,则称A可约,反之称A不可约.第十七页，共二十三页，编辑于2023年，星期四例5用定理3.7检验例1中方程组的矩阵A，判断该方程组用迭代法时是否收敛？解因为10│-2│+│-1│，10│-2│+│-1│，5│-1│+│-2│，结束

18定理3.7

A具有严格对角优势或A不可约且具有对角优势，则Jacobi迭代法和Gauss-Seidel迭代法都收敛.证明所以A具有严格对角优势，该方程组用Jacobi迭代法和Gauss-Seidel迭代法时收敛.第十八页，共二十三页，编辑于2023年，星期四定理3.8逐次超松弛法收敛的必要条件是0<ω<2.

定理3.9如果A实对称正定，且0<ω<2，则SOR法收敛.推论:当A实对称正定时，Ax=b使用Gauss-Seidel迭代法收敛.

注意A实对称正定时,Jacobi法并不一定收敛，这时有结论:

定理3.10如果A实对称,且对角元全为正,且A和2D-A均正定，则Jacobi迭代法收敛.第十九页，共二十三页，编辑于2023年，星期四可见即使有估计公式，计算ρ(