NC-2-3.ppt

1、1,第2章 线性方程组的解法,计算方法/数值计算,胡小兵 E-mail: 重庆大学数学与统计学院,2,主要内容,线性方程组的直接解法； 向量与矩阵的范数、条件数的概念; 线性方程组的迭代解法。,3,线性方程组的迭代解法,运算量大，不适合大规模的线性方程组求解 无法充分利用系数矩阵的稀疏性,直接法的缺点：,迭代法是目前求解大规模线性方程组的主要方法,4,线性方程组的迭代解法,构造与(2.25)等价的方程组 x = Bx + f (2.26) 使得(2.25)与(2.26)同解，其中B是nn矩阵，f是n维向量。,迭代法思路：,5,线性方程组的迭代解法,任取一个初始向量x(0)作为x的近似解，用迭代

2、公式 x(k+1)=Bx(k)+f, (k=0,1,2,.) (2.27) 产生一个向量序列x(k)。,则有 x = Bx + f，即 x 是(2.26)的解，当然 x 也就是 Ax = b 的解，称B为迭代矩阵。,若满足,6,Jacobi迭代法,例2.8 求解下面的方程组,解：将方程组化为等价的形式：,7,Jacobi迭代法,构造迭代格式：(k=0, 1 , 2, .),若取初始向量x(0)=(0, 0, 0)T，得到迭代序列x(k) (k=0,1,2,)，列表如下表2.1。,8,Jacobi迭代法,表2.1 迭代过程结果,9,Jacobi迭代法,一般说来，对方程组： i=1,2,，n (2

3、.28) 并设aii0 (i=1,2,n)，从第 i 个方程解出 xi，得等价的方程组：,i=1,2,n (2.29),10,Jacobi迭代法,构造迭代公式：,该迭代格式称为Jacobi迭代法，也称为简单迭代法。,11,Jacobi迭代法,将矩阵 A 表示成： A = L + D + U，其中：,Ax = b,Lx + Dx + Ux = b,x = -D-1Lx - D-1Ux + D-1b,12,Jacobi迭代法,则Jacobi迭代法的矩阵形式为：,记为： （2.31）,其中 （2.32）,13,Gauss-Seidel迭代法,在简单迭代法的迭代形式(2.31)中，可以看出，在计算 时

4、，要使用 。 但此时 已计算出来。看来此时可提前使用 代替 。一般地，计算 (ni2)时，使用 代替 (i p1)，这样可能收敛会快一些，这就形成一种新的迭代法，称为Gauss-Seidel迭代法。,Gauss-Seidel迭代法基于的假设：后计算出来的值比前面的值更准确！,14,Gauss-Seidel迭代法-例子,例2.9 用Gauss-Seidel迭代法计算例2.8并作比较。 解 Gauss-Seidel迭代公式为：,15,Gauss-Seidel迭代法-例子,用它计算得到序列 ，列表如下：,比 Jacobi 迭代法收敛快！,16,Gauss-Seidel迭代法矩阵公式,Gauss-Se

5、idel的公式如下：,Gauss-Seidel迭代法的矩阵迭代形式：,(2.33),17,逐次超松弛法(SOR方法),SOR方法可看成Gauss-Seidel迭代法的加速，Seidel迭代法是逐次超松弛法的特例。将Seidel迭代法的(2.33)式,改写为：,将Seidel迭代法的(2.33)式,18,逐次超松弛法(SOR方法),记,则,19,逐次超松弛法(SOR方法),为加快收敛，在增量 前加一个因子 ，得,称此公式为逐次超松弛法(SOR法)。,或改写为：,20,逐次超松弛法(SOR方法),从 (3.13) 式不难推出SOR方法的矩阵迭代形式：,条件：必须取02，当=1时，就是Seidel迭

6、代法。当取得适当时，对Seidel迭代法有加速效果。,其中,21,SOR方法-例子,例2.10 用Gauss-Seidel迭代法和取=1.45的逐次超松弛法计算下列方程组的解，当 时退出迭代，初值取x(0) = (1, 1, 1)T 。,达到同样的精度Seidel迭代法要72步，而取=1.45的逐次超松弛法只要25步，可见当松弛因子选择适当时，逐次超松弛法有明显加速收敛作用，它常用于求解大型线性方程组。,22,SOR方法-例子,表2-3 Gauss-Seidel迭代法,表 2-4 SOR法,23,迭代法的收敛条件,定理2.9 对任意初始向量 x(0) 和 f，由（2.27）式产生的迭代序列 x

7、(k) 收敛的充要条件是(B) 1。,证：1）必要性：,设 收敛于 ，有,记,有,有,24,对任意的 ， 也是任意的，,迭代法的收敛条件,要有 ，必须有：,由定理2.8有：,25,迭代法的收敛条件,2）充分性：,设 ，则 1 不是 B 的特征值。,于是 ，于是 有唯一解，记为x*。 即 成立。,由定理 2.8 有 ，所以,即,26,迭代法的收敛条件,定理2.9是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况。 由于(B)的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义。 迭代法的收敛与否与B的性态有关，与初始向量x(0)和右端向量 f 无关。,由于(B)

8、难于计算，而由定理2.7有(B) |B| ，|B|1时，必有 (B) 1，于是得到：,27,迭代法的收敛条件,定理2.10 若|B| = q 1，则由迭代格式x(k+1) = Bx(k) + f 和任意初始向量 x(0) 产生的迭代序列 x(k) 收敛于准确解x*。,本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当|B|1时，不能断定迭代不收敛。 由于|B|，特别是|B|1和 |B|的计算比较容易，也不失为一种判别收敛的方法。 同时当|B|1时可以用来估计迭代的次数，或用来设置退出计算的条件。,28,迭代法的收敛条件,定理2.11 若|B| = q 1，则迭代格式 x(k+1) = Bx

9、(k) + f 产生的向量序列 x(k)中,利用此定理可以在只计算出x(1)时，就估计迭代次数k，但估计偏保守，次数偏大。,29,定理2.12 若|B| = q 1 ，则 x(k) 的第 k 次近似值的近似程度有如下估计式：,迭代法的收敛条件,说明：本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代向量对精确解的误差也足够小。,30,迭代法的收敛条件,例2.11 就例2.9中的系数阵A1和例2.10中的系数阵A2讨论Jacobi 迭代法和 Seidel迭代法的收敛性。,解：1）就 A1 讨论,因为|BJ|1=0.9751，由定理2.10知Jacobi迭代法收敛。,31,

10、迭代法的收敛条件,因为|BS|= 0.8 1，由定理2.10知Seidel迭代法收敛。,2）就 A2 讨论,32,迭代法的收敛条件,用定理2.10无法判断简单迭代法收敛性，现计算(BJ)。,解之有三实根：1=0.9207, 2 =-0.2846, 3 =-0.6361. 所以(BJ) = 0.9207 1，故简Jacobi代法收敛。,|BS|=0.875，故Gauss-Seidel迭代法收敛。,33,定义2.8 若 A=(aij)nn 满足： 且至少有一个 i 值，使 成立， 称 A 具有对角优势。 若 称 A 具有严格对角优势。,迭代法的收敛条件,34,迭代法的收敛条件,设 的特征值为 ，则

11、,定理2.13 若 A 具有严格对角优势，则A非奇异。,定理2.14 A 具有严格对角优势或A不可约且具有对角优势，则 Jacobi 迭代法和 Seidel 迭代法都收敛。,定理2.15 逐次超松弛法收敛的必要条件是02.,证 因为SOR法收敛，所以,35,迭代法的收敛条件,所以 ，即,从而,故得,36,迭代法的收敛条件,定理2.16 如果A实对称正定，且02，则逐次超松弛法收敛。,推论: 当A实对称正定时，Ax=b使用Seidel迭代法收敛。,关于的选取，的选取影响(B) 的大小，使(B)最小的值称为最佳松弛因子，记为opt。 opt的选取是一个复杂问题，尚无完善结果，只有针对一些特殊矩阵的结果。一般采取试算方法确定。加速收敛的效果也随问题而异，对有的问题，可加速好几十倍，甚至更多，对有的