第5章-线性方程组的迭代解

结束第5章线性方程组的迭代解法

线性方程组的直接法，用于阶数不太高的线性方程组效果较好.实际工作中有的线性方程组阶数很高，但其中的大多数系数为0，这一类的线性方程组的系数阵称为稀疏矩阵.稀疏矩阵的存贮和计算有一套技术处理，可以节约大量的存贮空间和计算工作量.用直接法计算时，因一次消元就可以使系数阵丧失其稀疏性，不能有效利用其稀疏的特点.下文介绍的迭代法就有保持系数阵稀疏的优点，此外迭代法也常用来提高已知近似解的精度.5.1迭代法的一般形式线性方程组Ax=b(5.1)其中A非奇异，b≠0，因而它有唯一非零解.

1构造与(5.1)等价的方程组x=Bx+f(5.2)即使得(5.2)与(5.1)同解，其中B是n×n矩阵，f是n维向量.结束任取一个向量x(0)作为x的近似解，用迭代公式

x(k+1)=Bx(k)+f,(k=0,1,2,)(5.3)产生一个向量序列{x(k)}，若则有x=Bx+f，即x是(5.2)的解，当然x也就是Ax=b的解.从以上的讨论中，可以看出，迭代法的关键有：

1如何构造迭代公式x(k+1)=Bx(k)+f

？这样的构造形式不止一种，它们各对应一种迭代法.

2迭代法产生的向量序列{x(k)}的收敛条件是什么，收敛速度如何.后面将进行讨论.5.2几种常用的迭代法公式5.2.1简单迭代法

2结束先看一个算例：例1

从以上三个方程中分别解出x1,x2,x3。按下式进行迭代

(k=0,1,2,)

3结束任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列{x(k)}(k=0,1,2,)，列表如下表5-1。容易验证，原方程组的精确解为x=(1,2,3)T，从上面的计算可看出，{x(k)}收敛于精确解.一般说来，对方程组：

i=1,2,，n(5.4)并设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迭代公式为：结束

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

5结束5.2.2塞德尔(Seidel)迭代法在简单迭代法的迭代形式(5.6)中，可以看出，在计算

时，要使用.但此时已计算出来.看来此时可提前使用代替，一般地，计算(n≥i≥2)时，使用代替(i>p≥1)，这样可能收敛会快一些，这就形成一种新的迭代法，称为塞德尔迭代法。例2

用塞德尔迭代法计算例1并作比较.解迭代公式为：(k=0,1,2,)

6结束用它计算得到的序列{x(k)}列表如表5-2：可见它对这一方程组比简单迭代法收敛快一些。塞德尔迭代法的公式如下：(5.9)

Seidel迭代法的矩阵迭代形式：（推导）

7k0123456x100.30000.88040.98430.99780.99971.0000x201.50001.94481.99221.99891.99982.0000x302.68402.95392.99382.99912.99993.0000结束5.2.3逐次超松弛法(SOR方法)逐次超松弛法可看成塞德尔迭代法的加速，塞德尔迭代法是逐次超松弛法的特例.将塞德尔迭代法的(5.9)式改写为

8结束为加快收敛，在增量

前加一个因子，得称此公式为逐次超松弛法(SOR法).从(5.13)式不难推出SOR方法的矩阵迭代形式：下面定理5.8可以看到，必须取0<ω<2，当ω=1时，就是Seidel迭代法.当ω取得适当时，对塞德尔迭代法有加速效果.

9结束例3

用塞德尔迭代法和取ω=1.45的逐次超松弛法计算下列方程组的解，当

时退出迭代，初值取x(0)=(1,1,1)T

。由表5-３和表5-４可见，达到同样的精度Seidel迭代法要72步，而取ω=1.45的逐次超松弛法只要25步，可见当松弛因子选择适当时，逐次超松弛法有明显加速收敛作用，它常用于求解大型线性方程组。

10结束5.3迭代法的一般形式的收敛条件5.3.1一般迭代过程

在什么条件下收敛.定理5.1

对任意初始向量x(0)和f,

由上式产生的迭代序列x(k)收敛的充要条件是ρ(B)<1.证:1)必要性：

11结束2)充分性：定理5.1是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况.但由于ρ(B)的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义.从上面的定理可以看到，迭代法的收敛与否与B的性态有关，与初始向量x(0)和右端向量f无关。.由于ρ(B)难于计算，而由第二章定理4有ρ(B)≤||B||，||B||<1时，必有

ρ(B)<1，于是得到：

12结束定理5.2

若||B||=q<1，则由迭代格式x(k+1)=Bx(k)+f

和任意初始向量x(0)产生的迭代序列x(k)收敛于准确解x*。本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当||B||≥1时，不能断定迭代不收敛。但由于||B||,特别是||B||1和||B||∞的计算比较容易，也不失为一种判别收敛的方法。同时当||B||<1时可以用来估计迭代的次数，或用来设置退出计算的条件。利用此定理可以在只计算出x(1)时，就估计迭代次数k，但估计偏保守，次数偏大.定理5.4

若||B||=q<1，则x(k)的第k次近似值的近似程度有如下估计式：本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代向量对精确解的误差也足够小.

13定理5.3

若||B||=q<1，则迭代格式x(k+1)=Bx(k)+f产生的向量序列

{x(k)}中结束例4

就例1中的系数阵A1和例3中的系数阵A2讨论简单迭代法和塞德尔迭代法的收敛性.因为||BJ||∞=0.6<1，由定理5.2知简单迭代法收敛。解：1）就A1讨论因为||BS||∞=0.3<1，由定理5.2知Seidel迭代法收敛。

14结束用定理5.2无法判断简单迭代法收敛性，现计算ρ(BJ)。2）就A2讨论解之有三实根：λ1=0.9207,λ2=-0.2846,λ3

=-0.6361.所以ρ(BJ)=0.9207<1，故简单迭代法收敛.

15结束||BS||∞=0.875，故塞德尔迭代法收敛.5.3.2从矩阵A判断收敛的条件能否直接由矩阵A

的性态，讨论Ax=b

使用迭代法是否收敛.讨论前必须先介绍几个概念：1.对角优势若A=(aij)n×n

满足且至少有一个i值，使成立，称A具有对角优势；

16结束若称A具有严格对角优势.定理5.5

若A

具有严格对角优势，则A非奇异。2.不可约如果矩阵A能通过行对换和相应的列对换，变成：的形式，其中A11和A22为方阵，则称A

可约，反之称A

不可约.定理5.6

A不可约，且具有对角优势，则A非奇异.以上两个定理的证明要使用较多的数学知识，本书从略.定理5.7

A

具有严格对角优势或A

不可约且具有对角优势，则简单迭代法和塞德尔迭代法都收敛.证明：

17定理5.8

逐次超松弛法收敛的必要条件是0<ω<2.例5

用定理5.5检验例1中方程组的矩阵A，判断该方程组用迭代法时是否收敛？解因为

10│-2│+│-1│，10│-2│+│-1│，

5│-1│+│-2│，所以A具有严格对角优势，该方程组用简单迭代法和塞德尔迭代法时收敛。结束

定理5.9

如果A实对称正定，且0<ω<2，则逐次超松弛法收敛.推论:当A实对称正定时，Ax=b使用塞德尔迭代法收敛.最后提一下关于ω的选取，ω的选取影响ρ(Bω)的大小，使ρ(Bω)最小的ω值称为最佳松弛因子，记为ω

opt.ω

opt的选取是一个复杂问题，尚无完善结果，只有针对一些特殊矩阵的结果，比如

18结束定理5.10

如A对称正定，且是三对角阵，则其中BJ是简单迭代法的迭代矩阵.

可见即使有估计公式，计算ρ(Bω)也是困难的，一般采取试算方法确定.加速收敛的效果也随问题而异，对有的问题，可加速好几十倍，甚至更多，对有的问题则加速不明显.

1