数值分析必备知识.ppt

* 第3章 解线性方程组的迭代法 迭代法的基本思想是，把n元线性方程组Ax=b改写成等价的方程组x=Mx+g,就可以建立方程组的迭代公式 x(k+1)=Mx(k)+g , k=0,1,2,… Jacobi方法是由方程组中第i个方程解出xi,得到等价方程组: 从而得迭代公式 J迭代法的迭代矩阵为： 若在J迭代法中,充分利用新值, 则可以得到Gauss-Seidel迭代法： G-S迭代法的迭代矩阵为: G=(D-L)-1U. 对任意初始向量x(0),迭代法收敛??(M)1. 定理3.1 若‖M‖1,则对任意x(0),迭代法收敛,而且 定理3.2 定理3.2只是收敛的充分条件,并不必要. 由(3.5)式可见,‖x (k) -x(k-1) ‖很小时,‖x(k) –x*‖就很小,实际上用‖x (k) -x(k-1) ‖?作为迭代终止的条件。 , 即 若使‖x(k) –x*‖? ,只需 可以事先估计达到某一精度需要迭代多少步。 例如，例1中J-法计算结果如下： 1 0.5 0.2 0.071 0.0355 0.01159 0.005795 0.0017636 0 1.4 1.11 0.929 0.9906 1.01159 1.000251 0.9982364 0 0.5 1.20 1.055 0.9645 0.9953 1.005795 1.0001255 0 1.4 1.11 0.929 0.9906 1.01159 1.000251 0.9982364 0 1 2 3 4 5 6 7 ‖x(k)-x*‖? x3(k) x2(k) x1(k) k ‖x (6) -x(5) ‖?=0.011339,‖x(7) –x(6)‖?=0.0056695 用J迭代法求例1中方程组的解,取x(0)=(0,0,0)T,若使误差??x(k)-x*???10-5,问需要迭代多少次? 解 由例1知,x(1)=(1.4,0.5,1.4)T, 于是有,??x(1)-x(0)???=1.4 ,??B???=0.5 . 例2 k应满足 故取k=19, 即需要迭代19次. §3 J迭代法和G-S迭代法的收敛性 定理3.3 J迭代法收敛??(B)1;若‖B‖1?J迭代法收敛; G-S迭代法收敛??(G)1;若‖G‖1? G-S迭代法收敛; 定义3.1 若n阶矩阵A=(aij)满足: 则称矩阵A是严格对角占优矩阵. 引理 若A是严格对角占优矩阵, 则det(A)?0. 证 A=D-L-U=D(E-D-1(L+U))=D(E-B) 因此, ?(B)?‖B‖?1,故?=1不是B的特征值,det(E-B)?0。 定理3.4 设A是严格对角占优矩阵,则解线性方程组Ax=b的J迭代法和G-S迭代法均收敛。 因为A是严格对角占优矩阵, 所以det(D)?0, 而且 所以, det(A)?0. 证 由于‖B‖?1, 所以J迭代法收敛。 设?是G的任一特征值, 则?满足特征方程 det(?E-G)= det(?E-(D-L)-1U) 所以有 det(?(D-L)-U)=0 若|?|?1, 则矩阵?(D-L)-U 是严格对角占优矩阵, 这与 det(?(D-L)-U)=0矛盾, 所以|?|1,于是?(G)1. 定理3.5 设A 是对称正定矩阵, 则解方程组Ax=b的 (1)J迭代法收敛?2D-A也正定; (2)G-S迭代法必收敛. = det((D-L)-1)(?(D-L)-U) = det((D-L)-1)det(?(D-L)-U)=0 试建立一个收敛的迭代格式,并说明收敛性. 解 按如下方法建立迭代格式 例3 已知解线性方程组 由于迭代矩阵的行范数小于1,故此迭代法收敛. 改写成 将Jacobi迭代法 §4 逐次超松弛迭代法---SOR方法 写成向量形式就是 x（k+1）=x（k）+D-1(b-Ax(k)) , k=0,1,2,… Gaus