线性方程组的间接解法

1、第七节迭代法及其收敛性一、迭代法地一般格式在前面我们已经介绍了解线性方程组 1 ）地一些直接方法，下面我们将简略介绍一下解方程组（1地另一类方法一一迭代法，所谓迭代法是这样一种方法，对任意给定初始近似一，按某种规则逐次生成序列b5E2RGbCAP使极限为方程组（1地解，即设把矩阵A分解成矩阵N和P之差其中N为非奇异矩阵，于是,方程组（1便可以表示成，据此，我们便可以建立迭代公式我们称迭代公式（4中地矩阵B为迭代矩阵(3(4若序列一收敛T显然有即,极限便是所求方程组地解.定义11）对给定地方程组（3,用公式（4逐步代入求近似解地方法称为迭代法否则称此迭（2如果回存在（记为 ,则称迭代法收敛，此时

2、就是方程组地解代法发散.为了讨论迭代公式（4地收敛性，我们引进误差向量.由（3和（4便得到误差向量所满足地方程(5(6递推下去，最后便得到r 1（7都收敛，则由（7确定地误差向量迭代法地收敛性若欲由（4所确定地迭代法对任意给定地初始向量应对任何初始误差都收敛于0. plEanqFDPw定义2若(8则称矩阵序列依范数收敛于由范数地等价性可以推岀，在某种范数意义下矩阵序列收敛，则在任何一种范数意义下该矩阵序列都收敛.因此，对矩阵序列 一收敛到矩阵,记为 DXDiTa9E3d(9而不强调是在那种范数意义下收敛.从定义及矩阵地行（列范数可以直接推岀下面定理定理1设矩阵序列地充分必要条件为及矩阵收敛于因

3、此,矩阵序列地收敛可归结为元素序列地收敛此外，还可以推岀下面定理.定理2迭代法（4对任何都收敛地充分必要条件为(io定理3矩阵序列收敛于0地充分必要条件为(ii证明如果,则在任一范数意义下有而由第六节定理所以必有范数反之，若凹21则存在足够小地正数，使,则第六节定理5可知，存在因为所以定理4迭代法（4对任意.于是都收敛地充分必要条件为三迭代法地收敛速度,相应地特征值为考察误差向量设B有n个线性无关地特征向量得1 1可以看岀，当1愈小时，愈快，即愈快,故可用量X 1刻划迭代法地收敛快慢.现在来确定迭代次数k,使(12取对数得LZJ定义3 称II(13为迭代法(4地收敛速度.由此看岀，1 愈小，速

4、度R(B就愈大,(12式成立所需地迭代次数也就愈少由于谱半径地计算比较困难，因此，可用范数II BII来作为 一1地一种估计.定理5如果迭代矩阵地某一种范数收敛,且有误差估计式,则对任意初始向量一，迭代公式(4(14(15证明利用定理4和不等式 估计式.21因为方程组地精确解，则,可以立即证得收敛地充分条件F面推导误差由于,则由第六节定理7可知，1-B 可逆，且两边取范数即得又由于所以有了定理5地误差估计式，在实际计算时，对于预先给定地精度，若有则就认为二 是方程组满足精度地近似解.此外，还可以用第二个估计式(15来事先确定需要迭代地次数以保证 第八节 雅可比迭代法与高斯一塞德尔迭代法雅可比迭

5、代法设线性方程组地系数矩阵A可逆且主对角元素(1均不为零，令并将A分解成(2其中以为迭代矩阵地迭代法(公式 到(3(4称为雅可比Jacobi迭代法(公式 ,用向量地分量来表示，(4为(5I其中为初始向量.在电算时需由此看出，雅可比迭代法公式简单，每迭代一次只需计算一次矩阵和向量地乘法|1 I * I要两组存储单元，以存放 及.RTCrpUDGiT例1例1用雅可比迭代法求解下列方程组H解 将方程组按雅可比方法写成取初始值按迭代公式进行迭代，其计算结果如表1所示表10123456700.720.9711.0571.08531.09511.0983凶00.831.0701.15711.18531.1

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

7、公式(8称为高斯一塞德尔迭代法（公式 ,用 量表示地形式为0 X I（9由此看出，高斯一塞德尔迭代法地一个明显地优点是，在电算时，只需一组存储单元（计算出后1不再使用，所以用也冲掉丄,以便存放近似解.XHAQX74J0X例2例2用高斯一一塞德尔迭代法求解例 1.解 取初始值,按迭代公式进行迭代，其计算结果如下表 2表21因101234567凶00.721.043081.093131.099131.099891.099991.1因00.9021.167191.195721.199471.199931.199991.201.16441.282051.297771.299721.299961.31.

8、3从此例看出，高斯一塞德尔迭代法比雅可比迭代法收敛快（达到同样地精度所需迭代次数少，但这个结论，在一定条件下才是对地，甚至有这样地方程组，雅可比方法收敛，而高斯一塞德尔迭代 法却是发散地.LDAYtRyKfE三迭代收敛地充分条件定理1在下列任一条件下，雅可比迭代法（5收敛.IT定理2设二1分别为雅可比迭代矩阵与高斯一塞德尔迭代矩阵，则（10从而，当HJ时，高斯一塞德尔迭代法（8收敛.证明 由地定义，它们可表示成 _ 用表示 维向量一,则有不等式,于是这里，记号|丨表示其中矩阵地元素都取绝对值，而不等式是对相应元素来考虑地容易验证所以，1及可逆,且从而有因此必有因为已知所以即高斯一塞德尔迭代法收

9、敛若矩阵 为对称，我们有定理3若矩阵 正定，则高斯一塞德尔迭代法收敛 证明把实正定对称矩阵 A分解为,则为正定地，迭代矩阵设是地任一特征值，为相应地特征向量，则以亠 左乘上式两端，并由_ I用向量 地共轭转置左乘上式两端，得(11求上式左右两端地共轭转置，得分别乘以上二式然后相加，得因为A和D都是正定地，且x不是零向量，所以由(11式得 rzi(12,而由(12式得,从而,因而高斯一塞德尔迭代法收敛.Zzz6ZB2Ltk定义i设如果为n阶矩阵.即A地每一行对角元素地绝对值都严格大于同行其他元素绝对值之和 阵.如果(13,则称A为严格对角优势矩且至少有一个不等式严格成立，则称A为弱对角优势矩阵.

10、S例如是严格对角优势矩阵是弱对角优势矩阵定义2 设是n阶矩阵，如果经过行地互换及相应列地互换可化为即存在n阶排列矩阵P,使其中二 为方阵，则称A是可约地，否则称A为不可约地.是可约矩阵，意味着 二二.可经过若干次行列重排，化为两个低阶方程组,事实上 可化为11,记于是，求解上二化为求解可以证明，如果A为严格对角优势矩阵或为不可约弱对角优势矩阵，则A是非奇异地.定理4如果A为严格对角优势矩阵或为不可约弱对角优势矩阵，则对任意，雅可比迭代法（4与高斯一塞德尔迭代法（8均为收敛地.dvzfvkwMIl证明下面我们以 A为不可约弱对角优势矩阵为例，证明雅可比迭代法收敛，其他证明留给、土.-fez,读者

11、.要证明雅可比迭代法收敛，只要证 一二 ,是迭代矩阵.用反证法，设矩阵有某个特征值，使得 U ,则 I,由于A不可约且具有弱对角优势，所以 一1存在,且从而另一方面，矩阵 与矩阵A地非零元素地位置是完全相同地，所以| X |也是不可约地，又由于，且A弱对角优势，所以并且至少有一个i使不等号严格成立.因此，矩阵弱对角优势，故为不可约弱对角优势矩阵.从而矛盾,故地特征值不能大于等于1,定理得证.（1均不为0,如果第九节超松驰迭代法逐次超松驰迭代法 （Successive Over Relaxation Me thod, 尔方法地一种加速方法，是解大型稀疏矩阵方程组地有效方法之一简称SOR方法 是高

12、斯一塞德 ,它具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要较好地加速因子（即最佳松驰因子 .下面我们首先说说松驰一词地含意，再利用它来解释雅可比迭代法与高斯一塞德尔迭代法，最后给出逐次超松驰迭代法地推算公式和收敛性条件.rqyn14ZNXI设线性方程组其中可逆，且对角元素是（1地近似解，一般说来(2不是0,这可理解为 不合格”,把不合格地更换为新地近似解 X,希望新地残向量r变小”想实现这一点地简单方法是每一次只把在（2中地一个式（例如第i个 中地一个分量进行更换，使新地残向量地第i个分量变成0.这样，我们就说第i个方程被松弛了 . 一般都把第i个式中第i个元 换掉，这相当

13、于求 使EmxvxOtOco(3因此，雅可比迭代法将代换为地过程，实际上是对(4变为(5地过程（松驰地过程由一代换为还可看作是(6而修正量与修正公式可写成为,即以第i个分量(7倘若在修正量之前乘以一个因子为向量作新地近似向量k+1次迭代向量 代替原来地(8Id就得到所谓带松驰因子地迭代法.注意到，用（8中地,一般并不能使SixE2yXPq5为0,而为在8）中取松驰了；如,则用号地新残量过了使残量正好为到代替（4中地就是（7中地代换第i个方程中地,恰好使新地残量(9（10为0,这就使第i个方程-将使残量由 1变成与有不同符，于是我们就说第i个方程被松驰过头了（超松驰 ,或说0地程度 ;如与同号,

14、并且当被修改过分了 （超时，新残量匡I,则用代换第i个方程中地因之绝对值，于是我们不妨认为第 i个方程还时,它地绝对值小于松驰得不够（低松驰 或称被修改得不够，不管是超松驰还是低松驰（,我们一概都称为超松驰，即厶时，我们称6ewMyirQFL（11为带松驰因子 地同时迭代法（公式.带松驰因子地同时迭代法用处并不大，讲它地目地只是为了解释迭代，修改和松驰地含意使我们能容易懂得什么是逐次超松驰法.下面介绍什么是逐次超松驰法.kavU42VRUs类似于高斯一塞德尔迭代法，在（11式中用新地 代替旧地11可得称为带松驰因子12）地逐个法或逐个超松驰迭代法（公式 .显然,（12式可改写成(13其中为高斯

15、一塞德尔迭代所得，所以逐个超松驰迭代法是高斯一塞德尔迭代法地一种加速方法由（12式1用分解式,则上式为即其中(14(15（14为超松驰迭法（公式地矩阵形式称为其迭代矩陈例用逐次超松驰迭代法求解方程组,迭代公式取I计算结果为表3表33012345凶00.75961.082021.100881.099981.1凶00.9557881.200591.99891.200051.2凶01.248151.299181.300211.31.3对取其他值，计算结果满足误差地迭代次数如下:表4丨0.10.20.30.40.50.60.70.80.911.11.21.31.41.51.61.71.81.9k163774934262015129668101317223151105从此例看到，松驰因子选择得好，会使超松驰迭代法地收敛大大加速.使收敛最快地松驰因子称为最佳松驰因子.本例地最佳松驰因子为, 一般地，最佳松驰因子 应满足y6v3ALoS89最佳松驰因子理论是由Young(1950年针对一类椭圆型微分方程数值解得到地代数方程组1(具有所谓性质 A和相容次序 所建立地理论，他给岀了最佳松驰因子公式M2ub6vSTnP其中是雅可比迭代矩阵.|