第四章线性方程组的迭代法.doc

个人收集整理 勿做商业用途
第四章 线性方程组的迭代法
第一节 迭代法及其收敛性

一、迭代法的一般格式
在前面我们已经介绍了解线性方程组
(1）
的一些直接方法，下面我们将简略介绍一下解方程组(1)的另一类方法——迭代法,所谓迭代法是这样一种方法，对任意给定初始近似，按某种规则逐次生成序列

使极限
(2)
为方程组（1）的解,即

设把矩阵A分解成矩阵N和P之差

其中N为非奇异矩阵,于是,方程组(1）便可以表示成

即
（3）
其中，据此,我们便可以建立迭代公式
（4）
我们称迭代公式（4）中的矩阵B为迭代矩阵.
若序列收敛

显然有

即，极限便是所求方程组的解。
定义1（1)对给定的方程组(3），用公式(4）逐步代入求近似解 的方法称为迭代法.
（2） 如果存在 （记为），则称迭代法收敛，此时就是方程组的解，否则称此迭代法发散。
为了讨论迭代公式（4）的收敛性,我们引进误差向量.
(5)
由(3）和（4）便得到误差向量所满足的方程
（6）
递推下去，最后便得到
（7）

二、迭代法的收敛性
若欲由（4)所确定的迭代法对任意给定的初始向量都收敛，则由(7)确定的误差向量应对任何初始误差都收敛于0.
定义2若
(8)
则称矩阵序列依范数‖·‖收敛于。
由范数的等价性可以推出，在某种范数意义下矩阵序列收敛，则在任何一种范数意义下该矩阵序列都收敛.因此，对矩阵序列收敛到矩阵，记为
（9）
而不强调是在那种范数意义下收敛。
从定义及矩阵的行（列)范数可以直接推出下面定理.
定理1 设矩阵序列及矩阵，则收敛于的充分必要条件为
,
因此,矩阵序列的收 敛可归结为元素序列的收敛.此外，还可以推出下面定理。
定理2 迭代法(4）对任何都收敛的充分必要条件为
(10）
定理3 矩阵序列收敛于0的充分必要条件为
（11）
证明：如果,则在任一范数‖·‖意义下有

而由第六节定理4有

所以必有

反之，若则存在足够小的正数，使,则第六节定理5可知，存在范数使,.于是

因为

所以
即
定理 4：迭代法(4）对任意都收敛的充分必要条件为 
三、迭代法的收敛速度
考察误差向量

设B有n个线性无关的特征向量,相应的特征值为,由

得

可以看出，当愈小时，愈快,即愈快，故可用量来刻划迭代法的收敛快慢.
现在来确定迭代次数k,使
（12）
取对数得

定义3 称
（13）
为迭代法(4）的收敛速度.
由此看出，愈小，速度R（B)就愈大，（12）式成立所需的迭代次数也就愈少.
由于谱半径的计算比较困难，因此,可用范数‖B‖来作为的一种估计.
定理5 如果迭代矩阵的某一种范数，则对任意初始向量,迭代公式(4)收敛，且有误差估计式
（14）
或
（15)
证明 利用定理4和不等式,可以立即证得收敛的充分条件,下面推导误差估计式.
因为方程组的精确解，则

又，则由第六节定理7可知，I-B可逆，且

由于

两边取范数即得

又由于

所以,即

有了定理5的误差估计式，在实际计算时，对于预先给定的精度，若有

则就认为是方程组满足精度的近似解。此外，还可以用第二个估计式(15）来事先确定需要迭代的次数以保证
第二节 雅可比迭代法与高斯—塞德尔迭代法

一、雅可比迭代法
设线性方程组
(1）
的系数矩阵A可逆且主对角元素均不为零，令

并将A分解成
(2）
从而(1)可写成

令

其中. (3)
以为迭代矩阵的迭代法(公式）
（4）
称为雅可比(Jacobi)迭代法(公式)，用向量的分量来表示，(4)为
(5）
其中为初始向量。
由此看出,雅可比迭代法公式简单，每迭代一次只需计算一次矩阵和向量的乘法.在电算时需要两组存储单元,以存放及。
例1 用雅可比迭代法求解下列方程组

解：将方程组按雅可比方法写成

取初始值按迭代公式

进行迭代,其计算结果如表1所示
表1

0
1
2
3
4
5
6
7

0
0.72
0。971
1.057
1.0853
1.0951
1.0983
…

0
0。83
1。070
1。1571
1。1853
1。1951
1。1983
…

0
0。84
1.150
1.2482
1。2828
1.2941
1.2980
…

二、高斯-塞德尔迭代法
由雅可比迭代公式可知，在迭代的每一步计算过程中是用的全部分量来计算的所有分量，显然在计算第i个分量时,已经计算出的最新分量没有被利用,从直观上看，最新计算出的分量可能比旧的分量要好些。因此，对这些最新计算出来的第次近似的分量加以利用，就得到所谓解方程组的高斯—塞德（Gauss-Seidel）迭代法.
把矩阵A分解成
(6) 其中,分别为的主对角元除外的下三角和上三角部分，于是，方程组(1）便可以写成

即

其中
(7)
以为迭代矩阵构成的迭代法（公式）
(8）
称为高斯—塞德尔迭代法(公式)，用 量表示的形式为
(9）
由此看出,高斯-塞德尔迭代法的一个明显的优点是，在电算时，只需一组存储单元（计算出后不再使用，所以用冲掉，以便存放近似解。
例2 用高斯——塞德尔迭代法求解例1.
解：取初始值，按迭代公式

进行迭代,其计算结果如下表2
表2

0
1
2
3
4
5
6
7

0
0。72
1。04308
1。09313
1。09913
1。09989
1。09999
1。1

0
0.902
1。16719
1.19572
1.19947
1。19993
1.19999
1。2

0
1。1644
1。28205
1。29777
1。29972
1。29996
1。3
1.3

从此例看出，高斯—塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需迭代次数少）,但这个结论，在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛,而高斯-塞德尔迭代法却是发散的.
三、迭代收敛的充分条件
定理1 在下列任一条件下，雅可比迭代法(5）收敛.
① ;
② ；
③
定理2 设分别为雅可比迭代矩阵与高斯—塞德尔迭代矩阵，则
(10）
从而，当

时，高斯—塞德尔迭代法(8）收敛。
证明：由的定义,它们可表示成

用表示维向量,则有不等式

这里,记号|·｜表示其中矩阵的元素都取绝对值,而不等式是对相应元素来考虑的,于是

容易验证

所以,及可逆，且

从而有

因此必有

因为已知所以。即高斯—塞德尔迭代法收敛。
若矩阵为对称，我们有
定理3 若矩阵正定，则高斯-塞德尔迭代法收敛.
证明：把实正定对称矩阵A分解为

，则为正定的,迭代矩阵

设是的任一特征值，为相应的特征向量,则

以左乘上式两端,并由有

用向量的共轭转置左乘上式两端,得
(11)
求上式左右两端的共轭转置，得

以和分别乘以上二式然后相加,得

由，得

即
(12)
因为A和D都是正定的,且x不是零向量,所以由(11）式得,而由（12)式得， 即，从而，因而高斯-塞德尔迭代法收敛。
定义1 设为n阶矩阵。
① ①如果
(13）
即A的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵。
② ②如果

且至少有一个不等式严格成立,则称A为弱对角优势矩阵。
例如是严格对角优势矩阵,是弱对角优势矩阵.
定义2 设是n阶矩阵,如果经过行的互换及相应列的互换可化为， 即存在n阶排列矩阵P,使

其中为方阵，则称A是可约的，否则称A为不可约的。
是可约矩阵,意味着可经过若干次行列重排，化为两个低阶方程组，事实上， 可化为 ，记

于是，求解化为求解

可以证明,如果A为严格对角优势矩阵或为不可约弱对角优势矩阵，则A是非奇异的.
定理4 如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则对任意，雅可比迭代法（4)与高斯-塞德尔迭代法（8）均为收敛的.
证明：下面我们以A为不可约弱对角优势矩阵为例,证明雅可比迭代法收敛，其他证明留给读者。
要证明雅可比迭代法收敛，只要证,是迭代矩阵.
用反证法，设矩阵有某个特征值,使得，则，由于A不可约,且具有弱对角优势，所以存在,且

从而

另一方面，矩阵与矩阵A的非零元素的位置是完全相同的，所以也是不可约的,又由于，且A弱对角优势，所以

并且至少有一个i使不等号严格成立。因此,矩阵弱对角优势，故为不可约弱对角优势矩阵.从而

矛盾，故的特征值不能大于等于1,定理得证。
第三节 超松驰迭代法
逐次超松驰迭代法（Successive Over Relaxation Me thod,简称SOR方法）是高斯—塞德尔方法的一种加速方法,是解大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要较好的加速因子(即最佳松驰因子）。下面我们首先说说松驰一词的含意，再利用它来解释雅可比迭代法与高斯—塞德尔迭代法,最后给出逐次超松驰迭代法的推算公式和收敛性条件.
设线性方程组
(1)
其中可逆 ，且对角元素均不为0，如果 是（1)的近似解,一般说来
（2）
不是0，这可理解为“不合格",把不合格的更换为新的近似解X,希望新的残向量r’“变小”，想实现这一点的简单方法是每一次只把在(2)中的一个式(例如第i个)中的一个分量进行更换，使新的残向量的第i个分量变成0.这样,我们就说第i个方程被松弛了.一般都把第i个式中第i个元换掉,这相当于求使
（3)
因此，雅可比迭代法将代换为的过程，实际上是对1≤i≤n把
(4)
变为
(5)
的过程(松驰的过程).
由代换为还可看作是
(6）
而修正量与修正公式可写成为
(7）
倘若在修正量之前乘以一个因子，即以第i个分量
（8）
为向量作新的近似向量（第k+1次迭代向量)代替原来的就得到所谓带松驰因子的迭代法。注意到，用(8）中的代替（4）中的，一般并不能使
（9）
为0，而为
（10)
在（8)中取, 就是（7）中的,恰好使新的残量为0，这就使第i个方程松驰了；如，则用代换第i个方程中的将使残量由变成与有不同符号的新残量,于是我们就说第i个方程被松驰过头了（超松驰)，或说被修改过分了（超过了使残量正好为0的程度);如,则用代换第i个方程中的时，新残量与同号，并且当时，它的绝对值小于之绝对值，于是我们不妨认为第i个方程还松驰得不够（低松驰）或称被修改得不够，不管是超松驰还是低松驰(或)，我们一概都称为超松驰,即时,我们称
(11）
为带松驰因子的同时迭代法（公式)。
带松驰因子的同时迭代法用处并不大,讲它的目的只是为了解释迭代，修改和松驰的含意,使我们能容易懂得什么是逐次超松驰法.下面介绍什么是逐次超松驰法。
类似于高斯—塞德尔迭代法，在（11)式中用新的代替旧的 可得
(12）
称为带松驰因子的逐个法或逐个超松驰迭代法（公式)。显然，(12）式可改写成
(13)
其中

为高斯—塞德尔迭代所得,所以逐个超松驰迭代法是高斯-塞德尔迭代法的一种加速方法。
由（12)式

用分解式，则上式为

即
(14）
其中

(15）
(14)为超松驰迭法（公式）的矩阵形式称为其迭代矩陈
例：用逐次超松驰迭代法求解方程组

解：取，迭代公式

取计算结果为表3

表3

0
1
2
3
4
5
…

0
0。7596
1。08202
1.10088
1。09998
1.1
…

0
0。955788
1.20059
1。9989
1。20005
1.2
…

0
1.24815
1。29918
1.30021
1。3
1.3
…

对取其他值，计算结果满足误差

的迭代次数如下:
表4

0。1
0。2
0。3
0。4
0.5
0.6
0.7
0.8
0.9
1
1.1
1.2
1.3
1。4
1。5
1。6
1。7
1.8
1。9
k
163
77
49
34
26
20
15
12
9
6
6
8
10
13
17
22
31
51
105

从此例看到，松驰因子选择得好,会使超松驰迭代法的收敛大大加速。使收敛最快的松驰因子称为最佳松驰因子。本例的最佳松驰因子为,一般地，最佳松驰因子应满足

最佳松驰因子理论是由Young（1950年）针对一类椭圆型微分方程数值解得到的代数方程组（具有所谓性质A和相容次序）所建立的理论，他给出了最佳松驰因子公式

其中是雅可比迭代矩阵.
定理1 设,且超松驰迭代法(12)收敛，则松驰因子
（16)
证明：设SOR方法收敛，根据迭代法收敛的充要条件可知，.
设的特征值为，则

即

而

所以

该定理说明对于解一般线性方程组（1），超松弛迭代法只有取松弛因子在范围内才能收敛。反过来，对是正定矩阵有下面结果.
定理2 设是对称正定矩阵，且，则超松弛迭代法(12）收敛.
证明：设是的任一特征值，在上述假定下,若能证明，那么定理得证。
事实上,设为对应特征向量，即

亦即

考虑数量积

则

显然

记

由于,所以

所以

从而

当时

即。

19