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

1、迭代法研究的主要问题,1）迭代格式的构造； 2）迭代的收敛性分析； 3）收敛速度分析； 4）复杂性分析；（计算工作量） 5）初始值选择。,3.5 大型方程组的迭代方法,定义:设xk是Rn上的向量序列，,又设x*（x1*，x 2*,，x n*)是Rn上的向量.,则称向量x*是向量序列x k的极限 ，,若一个向量序列有极限,称这个向量序列是收敛的.,向量序列的极限,如果,矩阵序列的极限,证：,一、简单迭代思想,设矩阵A可逆，把矩阵A分裂为 则,迭代过程 B称为迭代矩阵。,给定初值 就得到向量序列,定义：若 称简单迭代法收敛，否则，称逐次逼近法不收敛或发散。,问题： 是否是方程组 x = B x +

2、 f 的解？,结论1：任意给定初始向量 ，若由迭代公式(1)产生的迭代序列收敛到 ，则 是方程组 x = B x + f 的解。,证：,又如何判定所给迭代格式(1)是否收敛哪？,迭代法收敛的条件,定理1：对任意初始向量 ，由（1）得到的迭代序列收敛的充要条件是迭代矩阵的谱半径 证： 因此,结论2：设矩阵 ，则,注：要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断迭代格式是否收敛。,定理2：若迭代法的迭代矩阵满足 （矩阵的某一种算子范数），则迭代格式 产生的序列 收敛于x = B x + f 的精确解x*，且有误差估计式：,证：由定理1、结论1和 知迭代格式产生的序列收敛于 x

3、= B x + f 的精确解 x* 。且,整理即得估计式。,Remark: 因为矩阵范数 ， 都可以直接用矩阵的元素计算，因此，用定理2，容易判别迭代法的收敛性。定理2的条件只是充分的，而不是必要的，也就是说：如果 ，则迭代法收敛；但若 ，我们并不能断定迭代法就一定发散，此时需要用定理1来判定迭代法的敛散性。,迭代格式的收敛速度与初始值 x (0) 有关，同时也与|B| 和 (B) 有关，一般来说， |B| 和 (B) 越小，收敛速度越快。 Def ： 称为迭代法的渐近收敛速度。,二、Jacobi迭代法,例1：用迭代法解方程组,解: 将方程组化为等价形式:,构造迭代格式:,取初始值 代入计算，

4、得,注：如何判断迭代过程终止？ 利用定理2的误差估计式可以判断迭代过程是否可以终止，但这种方法比较麻烦，通常采用的方法是通过前后两次迭代近似值的差来判断，即利用：,终止迭代过程。 上述这种求解方程组的方法称为Jacobi迭代法。,Jacobi迭代法的步骤：,3、判断迭代格式的收敛性。取初值 x(0) 带入计算。,1、写出等价方程组即将第 i 个方程的 xi 解出。 2、写出相应的迭代格式 分量式：,Jacobi 迭代矩阵形式,记 则有迭代格式：,上式称为Jacobi迭代格式，其中BJ 称为Jacobi迭代矩阵。,注：Jacobi 迭代矩阵BJ ： 其中的元素恰为原方程组系数矩阵A中的主对角 线

5、元素换为0，而其余元素即为除以该行主对角元素 后的相反数。,Jacobi迭代法在计算xi(k+1)时所用分量仍为上一次近似 值的各个分量，但此时，我们已经求出了新近似值的 分量 x1(k+1), x2(k+1), xi-1(k+1)，计算 xi(k+1)时，用新分量 x1(k+1), x2(k+1), xi-1(k+1) 代替原来相应的分量，则得到 一种新的迭代格式，即Gauss-Seidel迭代格式。,三、Gauss-Seidel 迭代法,假设,Jacobi迭代,矩阵表示： 记 上式整理可得： 这是一种简单迭代格式，其中的BG-S称为GS迭代 矩阵。,例2：用G-S迭代法解方程组：,解：原方

6、程可化为等价形式：,建立迭代格式：,取初始向量 x(0) = (0,0,0)T 代入迭代格式，得：,两种迭代法收敛性判定：,希望直接对系数矩阵 A 研究这俩种迭代收敛条件。,定理4：若 A 为(行或列)严格对角占优矩阵，则相应的G-S迭代格式收敛。,定理3: A 按行(列)严格对角占优，则Jacobi迭代收敛。,证：(仅证按行占优，反证) 设 是 任一特征值，x 是相应特征向量。设,若,则,定理5： 设A是有正对角元的n阶对称矩阵，则Jacobi迭代收敛 A和2D-A同为正定矩阵。,证：记,则,由A 的对称性， 也对称，因而特征值全为实数，记为 则 的任一特征值为 。,定理6：若A为对称正定矩

7、阵，则相应的G-S迭代格式收敛。,正定。,又,，故 正定。,A 正定 正定， 特征值小于1. 若 正定, 特征值小于1, 所以 特征值大于1。,所以,所以, 迭代矩阵BG-S的谱半径(BG-S) 1,从而当方程组 Ax=b的系数矩阵A 是实对称正定矩阵时,G-S 迭代法收敛,Remark: G-S迭代法的计算过程比Jacobi迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。 G-S迭代不一定比Jacobi迭代收敛快。 Jacobi迭代和G-S迭代的收敛范围并不一致，即Jacobi迭代收敛，G-S迭代不一定收敛，反之亦然。 前面的定理1、定理2对于Jacobi迭代和G-S迭代都适用。,(

8、i=1,2, n; k = 1,2,3, ),四 超松驰(SOR)迭代法,G-S迭代格式,定理7. 若A 是对称正定矩阵,则当02时SOR迭代法解方程组 A x = b 是收敛的,定理8. 若A 是严格对角占优矩阵,则当01时SOR迭代法解方程组 A x = b 是收敛的.,迭代矩阵：,例3：用松弛迭代法解方程组：,解：松弛法迭代格式为：,五 最速下降法,证明: (1) u 是方程组 Ax = b 的解 Au b=0.,任意 xR n, 令y = x u (Ay, y) 0,(2) 设 u 使 f (x) 取极小值. 任取非零 xR n, 任意 tR,令g(t) = f ( u + t x),

9、 当t=0时, g(0)= f (u)达到极小值, 所以 , 即,所以, u 是方程组 Ax = b 的解.,最速下降法基本思想：从初值点x (0) 出发,以负梯度方向 r 为搜索方向，选择步长t1, 得 x (1) = x (0) + t1r, 求函数 f (x) 极小值,在 x 处，梯度方向是 f (x) 增长最快方向； 负梯度方向是 f (x) 下降最快方向。,梯度:,由f (x)的表达式，易知对于任意x (0) Rn, f (x)在 x (0)处的负梯度方向为,记 r (0) = b- Ax (0)，即r (0)的方向就是负梯度的方向，也是 Ax = b 的对应于x (0)的残向量。若

10、r (0) =0，则x (0)即为Ax = b的解，若r (0) 0 ，则从x (0)出发，沿r (0)方向的x为：,其中为参数，这里x 表明在 r(0)方向上以 为步长，对x(0) 做了一次修正，为确定 ，使函数,取最小值。,令,解得：,又,所以，= 0 时f (x)取最小值，令x (1) =x (0) +0 r (0)，从x (1)出发沿f (x)在x (1)处的负梯度方向r (1) = b-Ax (1)上求使 f (x)的值最小的点，记为x (2)，则,x (1) = x (0) +0 r (0),继续下去则得迭代格式：,结论1：第m+1次和第m 次负梯度方向是正交的，即 (r (m+1

11、) , r (m) ) = 0,结论2：最速下降法有误差估计式,这里1 和n 为A 的最大和最小特征值，|A 定义为,注：由结论2可以看出，当1 和n 相差较大时，最速下降法收敛缓慢。,六 共轭梯度法,A是n阶对称正定矩阵,非零向量 p1, p2Rn,共轭梯度法基本思想：由最速下降法中的下降向量r (k) 构造出关于A共轭向量组 p (k) ，并以 p (k)作为下降方向来构造迭代算法。,定理10. A是n阶对称正定矩阵, p(1), p(2) , p(n) 是关于A共轭的向量组, 任取 x (0)R n , 计算,tk = ( b Ax (k -1) , p(k) / (A p(k) , p

12、(k) ) x (k) = x (k 1) + tk p(k) ( k = 1,2, n ),则有 Ax(n) = b。即最多迭代 n 次就可得到方程组的精确解。,第一步: 取初值 x (0)Rn , 0, 计算 r ( k -1) = b Ax (0) , 若| r0| 结束; 否则 p ( 1 ) r ( k -1) , k 1, 转第二步;,共轭梯度算法：,第二步: 计算 tk = ( p (k) ,r ( k-1) ) / ( A p( k ) , p ( k ) ) x (k) = x (k -1) + tk p( k ) ;,第三步: 如果 k = n, 则结束; 否则, 计算 r ( k -1) = b