《第3章 线性方程组的间接解法.doc》由会员分享，可在线阅读，更多相关《第3章 线性方程组的间接解法.doc（13页珍藏版）》请在三一文库上搜索。
1、第七节 迭代法及其收敛性一、迭代法的一般格式在前面我们已经介绍了解线性方程组 （1）的一些直接方法，下面我们将简略介绍一下解方程组(1)的另一类方法迭代法，所谓迭代法是这样一种方法，对任意给定初始近似,按某种规则逐次生成序列使极限 (2)为方程组(1)的解，即设把矩阵A分解成矩阵N和P之差其中N为非奇异矩阵,于是,方程组(1)便可以表示成即 (3)其中,据此,我们便可以建立迭代公式 (4)我们称迭代公式(4)中的矩阵B为迭代矩阵.若序列收敛显然有即，极限便是所求方程组的解.定义1（1）对给定的方程组(3)，用公式(4)逐步代入求近似解 的方法称为迭代法.(2) 如果存在 (记为)，则称迭代法收
2、敛，此时就是方程组的解,否则称此迭代法发散.为了讨论迭代公式(4)的收敛性,我们引进误差向量. (5)由(3)和(4)便得到误差向量所满足的方程 (6)递推下去,最后便得到 (7)二 迭代法的收敛性若欲由(4)所确定的迭代法对任意给定的初始向量都收敛,则由(7)确定的误差向量应对任何初始误差都收敛于0.定义2若 (8)则称矩阵序列依范数收敛于.由范数的等价性可以推出，在某种范数意义下矩阵序列收敛，则在任何一种范数意义下该矩阵序列都收敛.因此,对矩阵序列收敛到矩阵，记为 (9)而不强调是在那种范数意义下收敛.从定义及矩阵的行(列)范数可以直接推出下面定理.定理1 设矩阵序列及矩阵，则收敛于的充分
3、必要条件为, 因此，矩阵序列的收 敛可归结为元素序列的收敛.此外,还可以推出下面定理.定理2 迭代法(4)对任何都收敛的充分必要条件为 (10)定理3 矩阵序列收敛于0的充分必要条件为 (11)证明 如果,则在任一范数意义下有而由第六节定理4有所以必有 反之，若则存在足够小的正数，使,则第六节定理5可知,存在范数使，.于是因为所以即定理 4 迭代法(4)对任意都收敛的充分必要条件为三 迭代法的收敛速度考察误差向量设B有n个线性无关的特征向量,相应的特征值为,由得可以看出，当愈小时，愈快，即愈快，故可用量来刻划迭代法的收敛快慢.现在来确定迭代次数k，使 (12)取对数得定义3 称 (13)为迭代
4、法(4)的收敛速度.由此看出,愈小,速度R(B)就愈大，(12)式成立所需的迭代次数也就愈少.由于谱半径的计算比较困难,因此,可用范数B来作为的一种估计.定理5 如果迭代矩阵的某一种范数，则对任意初始向量，迭代公式(4)收敛,且有误差估计式 (14)或 (15)证明 利用定理4和不等式,可以立即证得收敛的充分条件,下面推导误差估计式.因为方程组的精确解，则又,则由第六节定理7可知,I-B可逆，且 由于 两边取范数即得又由于所以，即有了定理5的误差估计式,在实际计算时,对于预先给定的精度，若有则就认为是方程组满足精度的近似解.此外，还可以用第二个估计式(15)来事先确定需要迭代的次数以保证第八节
5、 雅可比迭代法与高斯塞德尔迭代法一 雅可比迭代法设线性方程组 (1)的系数矩阵A可逆且主对角元素均不为零,令 并将A分解成 (2)从而(1)可写成 令 其中. (3)以为迭代矩阵的迭代法(公式) (4)称为雅可比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为 (5)其中为初始向量.由此看出,雅可比迭代法公式简单,每迭代一次只需计算一次矩阵和向量的乘法.在电算时需要两组存储单元,以存放及.例1 例1 用雅可比迭代法求解下列方程组解 将方程组按雅可比方法写成取初始值按迭代公式进行迭代，其计算结果如表1所示 表1 0 1 2 3 4 5 6 700.720.9711.0571.0853
6、1.09511.0983 00.831.0701.15711.18531.19511.1983 00.841.1501.24821.28281.29411.2980 二 高斯塞德尔迭代法由雅可比迭代公式可知,在迭代的每一步计算过程中是用的全部分量来计算的所有分量,显然在计算第i个分量时,已经计算出的最新分量没有被利用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第次近似的分量加以利用,就得到所谓解方程组的高斯塞德（Gauss-Seidel）迭代法.把矩阵A分解成 (6) 其中,分别为的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成 即其中 (7)
7、以为迭代矩阵构成的迭代法(公式) (8)称为高斯塞德尔迭代法(公式),用 量表示的形式为 (9)由此看出,高斯塞德尔迭代法的一个明显的优点是,在电算时,只需一组存储单元(计算出后不再使用,所以用冲掉,以便存放近似解.例2 例2 用高斯塞德尔迭代法求解例1.解 取初始值，按迭代公式进行迭代，其计算结果如下表2 表2 0 1 2 3 4 5 6 700.721.043081.093131.099131.099891.09999 1.100.9021.167191.195721.199471.199931.19999 1.201.16441.282051.297771.299721.299961.3
8、 1.3从此例看出,高斯塞德尔迭代法比雅可比迭代法收敛快(达到同样的精度所需迭代次数少),但这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯塞德尔迭代法却是发散的.三 迭代收敛的充分条件定理1 在下列任一条件下,雅可比迭代法(5)收敛. ; ; 定理2 设分别为雅可比迭代矩阵与高斯塞德尔迭代矩阵,则 (10)从而，当时，高斯塞德尔迭代法(8)收敛.证明 由的定义,它们可表示成用表示维向量,则有不等式这里,记号表示其中矩阵的元素都取绝对值,而不等式是对相应元素来考虑的,于是容易验证所以,及可逆，且从而有因此必有因为已知所以.即高斯塞德尔迭代法收敛.若矩阵为对称，我们有定
9、理3 若矩阵正定,则高斯塞德尔迭代法收敛.证明 把实正定对称矩阵A分解为 ,则为正定的,迭代矩阵设是的任一特征值,为相应的特征向量,则以左乘上式两端,并由有用向量的共轭转置左乘上式两端,得 (11)求上式左右两端的共轭转置,得以和分别乘以上二式然后相加,得由,得即 (12)因为A和D都是正定的,且x不是零向量,所以由(11)式得,而由(12)式得, 即,从而,因而高斯塞德尔迭代法收敛.定义1 设为n阶矩阵. 如果 (13)即A的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵. 如果且至少有一个不等式严格成立,则称A为弱对角优势矩阵.例如是严格对角优势矩阵，是弱
10、对角优势矩阵.定义2 设是n阶矩阵，如果经过行的互换及相应列的互换可化为, 即存在n阶排列矩阵P,使 其中为方阵，则称A是可约的,否则称A为不可约的.是可约矩阵,意味着可经过若干次行列重排,化为两个低阶方程组,事实上, 可化为 ,记于是，求解化为求解可以证明,如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则A是非奇异的.定理4 如果A为严格对角优势矩阵或为不可约弱对角优势矩阵,则对任意,雅可比迭代法(4)与高斯塞德尔迭代法(8)均为收敛的.证明 下面我们以A为不可约弱对角优势矩阵为例，证明雅可比迭代法收敛，其他证明留给读者.要证明雅可比迭代法收敛，只要证,是迭代矩阵.用反证法,设矩阵有某个
11、特征值,使得,则,由于A不可约,且具有弱对角优势，所以存在，且从而 另一方面，矩阵与矩阵A的非零元素的位置是完全相同的，所以也是不可约的,又由于,且A弱对角优势，所以并且至少有一个i使不等号严格成立.因此,矩阵弱对角优势，故为不可约弱对角优势矩阵.从而 矛盾，故的特征值不能大于等于1，定理得证.第九节 超松驰迭代法逐次超松驰迭代法(Successive Over Relaxation Me thod,简称SOR方法)是高斯塞德尔方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易,占用计算机内存较少等优点,但需要较好的加速因子(即最佳松驰因子).下面我们首
12、先说说松驰一词的含意,再利用它来解释雅可比迭代法与高斯塞德尔迭代法,最后给出逐次超松驰迭代法的推算公式和收敛性条件.设线性方程组 (1)其中可逆 ，且对角元素均不为0，如果 是(1)的近似解，一般说来 (2)不是0，这可理解为“不合格”，把不合格的更换为新的近似解X，希望新的残向量r“变小”，想实现这一点的简单方法是每一次只把在(2)中的一个式(例如第i个)中的一个分量进行更换,使新的残向量的第i个分量变成0.这样,我们就说第i个方程被松弛了.一般都把第i个式中第i个元换掉,这相当于求使 (3)因此，雅可比迭代法将代换为的过程，实际上是对1in把 (4)变为 (5)的过程(松驰的过程).由代换
13、为还可看作是 (6)而修正量与修正公式可写成为 (7)倘若在修正量之前乘以一个因子，即以第i个分量 (8)为向量作新的近似向量(第k+1次迭代向量)代替原来的就得到所谓带松驰因子的迭代法.注意到,用(8)中的代替(4)中的,一般并不能使 (9)为0，而为 (10)在（8）中取, 就是(7)中的,恰好使新的残量为0，这就使第i个方程松驰了；如，则用代换第i个方程中的将使残量由变成与有不同符号的新残量,于是我们就说第i个方程被松驰过头了(超松驰)，或说被修改过分了(超过了使残量正好为0的程度)；如,则用代换第i个方程中的时,新残量与同号，并且当时，它的绝对值小于之绝对值，于是我们不妨认为第i个方程
14、还松驰得不够(低松驰)或称被修改得不够，不管是超松驰还是低松驰(或),我们一概都称为超松驰,即时,我们称 (11)为带松驰因子的同时迭代法(公式).带松驰因子的同时迭代法用处并不大,讲它的目的只是为了解释迭代,修改和松驰的含意,使我们能容易懂得什么是逐次超松驰法.下面介绍什么是逐次超松驰法.类似于高斯塞德尔迭代法，在(11)式中用新的代替旧的 可得 （12）称为带松驰因子的逐个法或逐个超松驰迭代法(公式).显然,(12)式可改写成 (13)其中为高斯塞德尔迭代所得，所以逐个超松驰迭代法是高斯塞德尔迭代法的一种加速方法.由(12)式用分解式,则上式为即 (14)其中 (15)(14)为超松驰迭法
15、(公式)的矩阵形式称为其迭代矩陈例 用逐次超松驰迭代法求解方程组解 取,迭代公式取计算结果为表3 表3 012345 00.75961.082021.100881.099981.100.9557881.200591.99891.200051.201.248151.299181.300211.31.3对取其他值，计算结果满足误差的迭代次数如下： 表40.10.20.30.40.50.60.70.80.911.11.21.31.41.51.61.71.81.9k163774934262015129668101317223151105从此例看到,松驰因子选择得好,会使超松驰迭代法的收敛大大加速.使收
16、敛最快的松驰因子称为最佳松驰因子.本例的最佳松驰因子为,一般地，最佳松驰因子应满足 最佳松驰因子理论是由Young(1950年)针对一类椭圆型微分方程数值解得到的代数方程组(具有所谓性质A和相容次序)所建立的理论,他给出了最佳松驰因子公式 其中是雅可比迭代矩阵.定理1 设,且超松驰迭代法(12)收敛，则松驰因子 (16)证明 由设SOR方法收敛，根据迭代法收敛的充要条件可知，.设的特征值为，则 即 而 所以 该定理说明对于解一般线性方程组(1)，超松弛迭代法只有取松弛因子在范围内才能收敛.反过来,对是正定矩阵有下面结果. 定理2 设是对称正定矩阵,且,则超松弛迭代法(12)收敛. 证明 设是的任一特征值,在上述假定下,若能证明,那么定理得证. 事实上,设为对应特征向量，即 亦即 考虑数量积 则 显然记 由于,所以 所以 从而 当时即.