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

1、第三章 线性方程组的迭代解法,线性方程组的直接法，用于阶数不太高的线性方程组效果较好.实际工作中有的线性方程组阶数很高，但其中的大多数系数为0，这一类的线性方程组的系数阵称为稀疏矩阵.稀疏矩阵的存贮和计算有一套技术处理，可以节约大量的存贮空间和计算工作量.用直接法计算时，因一次消元就可以使系数阵丧失其稀疏性，不能有效利用其稀疏的特点.下文介绍的迭代法就有保持系数阵稀疏的优点，此外迭代法也常用来提高已知近似解的精度.,线性方程组 Ax=b (3.1) 其中A非奇异，b0，因而它有唯一非零解.,构造与(3.1)等价的方程组 x=Bx+f (3.2) 即使得(3.2)与(3.1)同解，其中B是nn矩

2、阵，f是n维向量.,结束,1,3.1 迭代法的一般形式,任取一个向量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)，若,先看一个算例：,按下式进行迭代 (k=0,1,2, ),结束,3,3.2 几种常用的迭代法公式,例1

3、,3.2.1 Jacobi迭代法,从以上三个方程中分别解出x1, x2, x3,任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列x(k) (k=0,1,2,)，列表如下表3-1。,容易验证，原方程组的精确解为 x = (1,2,3) T，从上面的计算可看出，x(k)收敛于精确解.,一般说来，对方程组： 设aii0(i=1,2,n)，从第i个方程解出xi，得等价的方程组：,结束,4,迭代公式为：,i=1,2,n (3.5),(3.6),这种迭代形式称为Jacobi迭代法(雅可比迭代法)，也称简单迭代法.,Jacobi迭代法的矩阵迭代形式: (推导),结束,5,其中,3.2.2 Gau

4、ss-Seidel 迭代法,在Jacobi迭代法的迭代形式(3.6)中，可以看出，在计算 时，要使用 .但此时 已计算出来.看来此时可提前使 用 代替 ，一般地，计算 (ni2)时，使 用 代替 (i p1)，这样可能收敛会快一些，这就形成一种新的迭代法，称为Gauss-Seidel迭代法。,例2 用 Gauss-Seidel 迭代法计算例1并作比较.,(k=0,1,2, ),结束,6,解 迭代公式为：,用它计算得到的序列x(k)列表如表3-2：,可见它对这一方程组比Jacobi迭代法收敛快一些。,Gauss-Seidel迭代法的公式如下：,(3.9),Gauss-Seidel迭代法的矩阵迭代

5、形式： （推导）,结束,7,其中,SOR迭代法也称为逐次超松弛法，它可看成Gauss-Seidel迭代法的加速， Gauss-Seidel迭代法是SOR迭代法的特例.,改写为,结束,8,3.2.3 SOR迭代法,将Gauss-Seidel迭代法的(3.9)式,记,则,为加快收敛，在增量 前加一个因子 , 得,称此公式为SOR法 (逐次超松弛法).,从(3.13)式不难推出SOR法的矩阵迭代形式：,今后可以看到，必须取02，当=1时,就是Gauss-Seidel迭代法.当取得适当时，对Gauss-Seidel迭代法有加速效果.,结束,9,其中,改写为,例3 用Gauss-Seidel迭代法和取=

6、1.45的SOR法计算下列方程组的解，当 时退出迭代，初值取x(0)=(1,1,1)T 。,由表-和表-可见，达到同样的精度Gauss-Seidel迭代法要72步，而取=1.45的SOR法只要25步，可见当松弛因子选择适当时，SOR法有明显加速收敛作用，它常用于求解大型线性方程组。,结束,10,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=

7、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 .,2)充分性：,定理3.1是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况.但由于(B)的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义.,结束,12,从上面的定理可以看到,迭代法的收敛与否与B的性态有关，而与初始向量x

8、(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= B k+10 仍成立,因此 k+1 0 (k ) 成立, 也即是 x(k) x* (k ),由上章定理2.8, 由 (B) 1 , 可得 Bk+1 0 (k ) 成立,定理3.2 若 |B| =q1，则由迭代格式x(k+1)=Bx(k)+f 和任意

9、初始向量x(0)产生的迭代序列x(k)收敛于准确解x*.,本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当|B| 1时,不能断定迭代不收敛.但由于|B|,特别是|B| 1和|B| 的计算比较容易，也不失为一种判别收敛的方法。,利用此定理可以在只计算出x(1)时，就估计迭代次数k，但估 计偏保守，次数偏大. 称为事前误差估计.,定理3.3 若|B| =q1，则迭代格式x(k+1) =Bx(k)+f产生的向量序列 x(k)中,结束,13,同时当|B| 1时可以用来估计迭代的次数，或用来设置退出计算的条件. 这时有定理3.3和定理3.4,例4 就例1中的系数阵A1和例3中的系数阵A2讨论Jac

10、obi迭代法和Gauss-Seidel迭代法的收敛性.,因为|BJ|=0.61，由定理3.2知Jacobi迭代法收敛。,解：1）就A1讨论,结束,14,定理3.4 若|B| =q1 ，则x(k)的第k次近似值的近似程度有如下估计式：,本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代向量对精确解的误差也足够小.称为事后误差估计.,用定理3.2无法判断Jacobi迭代法收敛性，现计算(BJ)。,2）就A2讨论,解之有三实根：1=0.9207, 2 = -0.2846, 3 = -0.6361. 所以(BJ)=0.92071，故Jacobi迭代法收敛.,结束,15,因为|B

11、S|=0.31，由定理3.2知Gauss-Seidel迭代法收敛。,|BS|=0.875，故Gauss-Seidel迭代法收敛.,3.3.2 从矩阵 A 判断收敛的条件,下面讨论直接由矩阵 A 的性态,判定 Ax = b 使用迭代法是否收敛. 讨论前必须先介绍几个概念：,1对角优势 若 A=(aij)nn 满足 且至少有一个I 值，使 成立,称A具有对角优势；,结束,16,若 称A具有严格对角优势.,定理3.5 若 A 具有严格对角优势，则A非奇异。,定理3.6 A不可约，且具有对角优势，则A非奇异.,结束,17,2不可约 如果矩阵 A 能通过行对换和相应的列对换，变成：,矩阵 A是否可约是不

12、易判别的，但以下两条准则比较常用:,A没有零元素或零元素太少(少于n-1)时不可约;,三对角阵如果三条对角线上的元素都不为零时不可约.,的形式, 其中 A11 和 A22 为方阵, 则称 A可约, 反之称 A 不可约.,例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迭代法时收敛.,

13、定理3.8 逐次超松弛法收敛的必要条件是02.,定理3.9 如果A实对称正定，且02，则SOR法收敛.,推论: 当A实对称正定时，Ax=b 使用Gauss-Seidel迭代法收敛.,注意A实对称正定时, Jacobi 法并不一定收敛，这时有结论:,定理3.10 如果A实对称, 且对角元全为正, 且A 和 2D-A 均正定， 则Jacobi 迭代法收敛.,可见即使有估计公式，计算(B)也是困难的，一般采取试算方法确定.加速收敛的效果也随问题而异,对有的问题可加速好几十倍，甚至更多，对有的问题则加速不明显.,结束,20,最后提一下关于的选取，的选取影响(B) 的大小，使(B)最小的值称为最佳松弛因子，记为opt . opt的选取是一个复杂问题，尚无完善结果,只有针对一些特殊矩阵的结果，比如,定理3.11 如A对称正定，且是三对角阵，则,其中BJ 是Jacobi迭代法的迭代矩阵.,所以Ax=b对Gauss-Seidel迭代法及SOR法(0 2)都收敛