第3章解线性方程组迭代方法

1、 迭代法研究的主要问题迭代法研究的主要问题1 1）迭代格式的构造；）迭代格式的构造；2 2）迭代的收敛性分析；）迭代的收敛性分析；3 3）收敛速度分析；）收敛速度分析；4 4）复杂性分析；（计算工作量）复杂性分析；（计算工作量）5 5）初始值选择。）初始值选择。3.5 大型方程组的迭代方法大型方程组的迭代方法 定义定义: :设设xk是是Rn上的向量序列，上的向量序列， 又设又设x*（x1 1* *，x 2* *,，x n* *) )是是Rn上的向量上的向量. . 则称向量则称向量x* *是向量序列是向量序列x k的极限的极限 ，若一个向量序列有极限若一个向量序列有极限, ,称这个向量序列是称这

2、个向量序列是收敛的收敛的. .*lim |0kkxx ( )( )( )12(,) ,1,2,kkkTknxxxxk令向量序列的极限向量序列的极限如果如果向量序列向量序列x k收敛于向量收敛于向量x x* *的充分必要的充分必要定理定理1 1（i =1,2,=1,2,n）( )*limkiikxx条件是条件是矩阵序列的极限矩阵序列的极限定义定义: : 设设Ak是是 上的矩阵序列上的矩阵序列. .若存在矩阵若存在矩阵 则称矩阵则称矩阵A 是矩阵序列是矩阵序列A k的极限，记为的极限，记为若一个矩阵序列有极限若一个矩阵序列有极限, ,称这个矩阵序列是称这个矩阵序列是收敛的收敛的. .lim |0k

3、kAA Rn nARn n使得使得limkkAA 矩阵序列矩阵序列A k收敛于矩阵收敛于矩阵A 的充分必要的充分必要定理定理2 2（i, j =1,2,=1,2,n）( )limki ji jkaa条件是条件是这里这里= ()()A创kkijnnijnna, A = a证：证：lim|lim0,0AA=危 =nkkkknkkxRA xAxxRxlim)0(1 2A=Lkiki= , ,n依次取依次取 x 为为 ，其中，其中12Ln, T(0,0,1,0,0)=LLi则则limlim0AA=kkkkI所以所以定理定理3 3limkk0A=的充要条件是对任何的充要条件是对任何xRn，有，有lim0

4、A=kkxlimkkA 0设矩阵设矩阵定理定理4 4，则，则 的的ARn n充要条件是充要条件是( A) 0, 记记 xTLTx = a , 则有则有xTLTx =xT(D L)xxTAx=xT(D L LT)x=p a a =p 2a 0apaxLDxxLxTTT )( 1)2(2222222 aappaapapa 所以所以所以所以, 迭代矩阵迭代矩阵BG-S的谱半径的谱半径(BG-S) 1,从而当方程从而当方程组组 Ax=b的系数矩阵的系数矩阵A 是实对称正定矩阵时是实对称正定矩阵时,G-S 迭代迭代法收敛法收敛Remark:G-S迭代法的计算过程比迭代法的计算过程比Jacobi迭代法更简

5、单。迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。计算过程中只需用一个一维数组存放迭代向量。G-S迭代不一定比迭代不一定比Jacobi迭代收敛快。迭代收敛快。Jacobi迭代和迭代和G-S迭代的收敛范围并不一致，即迭代的收敛范围并不一致，即Jacobi迭代收敛，迭代收敛，G-S迭代不一定收敛，反之亦迭代不一定收敛，反之亦然。然。1)前面的定理前面的定理1、定理、定理2对于对于Jacobi迭代和迭代和G-S迭代迭代都适用。都适用。)()1()1()(1)1()(bUxLxDxxkkkk )1(1)1(11)()1()( nijkjijijkjijiiikikixaxabaxx (i=1

6、,2, n; k = 1,2,3, )四四 超松驰超松驰(SOR)(SOR)迭代法迭代法G-S迭代格式迭代格式 nijkjijijkjijiiikixaxabax1)(11)1()1(1定理定理7. 若若A 是对称正定矩阵是对称正定矩阵,则当则当02时时SOR迭代迭代法解方程组法解方程组 A x = b 是收敛的是收敛的定理定理8. 若若A 是严格对角占优矩阵是严格对角占优矩阵,则当则当0dfdxArr又又所以，所以，= = 0 时时f (x)取最小值，令取最小值，令x (1) =x (0) +0 r (0)，从，从x (1)出发沿出发沿f (x)在在x (1)处的负梯度方向处的负梯度方向r

7、(1) = b-Ax (1)上求上求使使 f (x)的值最小的点，记为的值最小的点，记为x (2)，则，则x (1) = x (0) +0 r (0)(1)(1)(1)(1)1(,)(,)a=rrrAr继续下去则得迭代格式：继续下去则得迭代格式： (0)nxR(m)(m)(m)(m)(m)(m)(m+1)(m+1)(m)m+(,)0,1,2(,)=-= LmmrbAxrrrArxxr结论结论1：第：第m+1次和第次和第m 次负梯度方向是正交的，即次负梯度方向是正交的，即 (r (m+1) , r (m) ) = 0 结论结论2：最速下降法有误差估计式：最速下降法有误差估计式 1()*(0)*1

8、| +骣-桫mnmAAnxxxx这里这里1 和和n 为为A 的最大和最小特征值，的最大和最小特征值，|A 定义为定义为|()=AxAx,x注：注：由结论由结论2可以看出，当可以看出，当1 和和n 相差较大时，最速相差较大时，最速下降法收敛缓慢。下降法收敛缓慢。六六 共轭梯度法共轭梯度法A是是n阶对称正定矩阵阶对称正定矩阵,非零向量非零向量 p1, p2Rn n个向量个向量 p1, p2 , pm 共轭概念共轭概念:(Api , pj )=0(ij; i, j = 1,2,m )非零向量非零向量 p1, p2 , pm Rn p1, p2 , pm 关于关于A共轭共轭 p1, p2 , pm 线

9、性无关线性无关(Ap1, p2)=0 两个向量两个向量 p1, p2 共轭共轭:共轭梯度法基本思想：共轭梯度法基本思想：由最速下降法中的下降向量由最速下降法中的下降向量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(k) )x (k) = x (

10、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 Ax (k) ; 转第四步转第四步;第四步第四步: 如果如果 | r ( k -1) |