[理学]35迭代法.ppt

3.5迭代法 什么是迭代法？ 迭代法的基本思想就是把n元线性方程组 改写成等价的方程组 由此建立方程组的迭代公式： 从而 §1 Jacobi迭代法和Gauss-Seidel迭代法 Jacobi方法是由方程组(3.1.1)中第i个方程解出 ,得到等价方程组: 从而得迭代公式 式（3.3）称为Jacobi迭代法，简称J迭代法。 J法也记为： 若记 ,则J迭代法可写成 式(3.4)称为Gauss-Seidel迭代法,简称为G-S迭代法。 G-S迭代法也可记为 例1 用J法和G-S法求解线性方程组 取初始向量x(0)=(0,0,0)T,迭代可得 计算结果列表如下: 可见,迭代序列逐次收敛于方程组的解, 而切迭代7次得到精确到小数点后两位的近似解. G-S迭代法的计算公式为: 同样取初始向量x(0)=(0,0,0)T, 计算结果为 由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次. 由此建立J迭代法迭代公式 G-S迭代法迭代公式可写成 §2 迭代法的收敛性 的收敛性. 证 由于 所以 所以有 所以 设?是B的任一特征值, y是对应的特征向量, 则 SOR方法收敛??(￡?)1;若‖￡?‖1,则SOR方法收敛. 定理3.7 若SOR方法收敛, 则0?2. 定理3.6 证 设SOR方法收敛, 则?(￡?)1,所以 |det(￡?)| =|?1?2… ?n|1 而 det(￡?) =det[(D-?L)-1 ((1-?)D+?U)] =det[(E-?D-1L)-1 ]det[(1-?)E+?D-1U)] =(1-?)n 于是 |1-?|1, 或 0?2 定理3.8 设A是严格对角占优矩阵,则解方程组Ax=b的SOR方法,当0??1时收敛. 定理3.9 设A是对称正定矩阵, 则解方程组Ax=b的SOR方法,当0?2时收敛. 证 设?是￡?的任一特征值, y是对应的特征向量, 则 [(1-?)D+?U]y=? (D-?L)y 于是 (1-?)(Dy,y)+?(Uy,y)=?[(Dy,y)-?(Ly,y)] 由于A=D-L-U是对称正定的, 所以D是正定矩阵, 且L=UT. 若记(Ly,y)=?+i?, 则有 当0?2时,有 所以|?|21, 因此?(￡?)1,即S0R方法收敛. * * 迭代法是从某一给定的初始向量 出发按照一个适当的迭代公式，逐次计算向量 使得向量序列 收敛于方程组的精确解。迭代法是一类逐次近似的方法。其优点是算法简便，程序易于实现。 或 3.1.1 或 3.1.2 其中M称为迭代矩阵。对于任意初始向量 由（3.2）式可逐次算出迭代向量 如果向量序列 收敛于 ，由3.2式可得 是方程组 的解， 也是方程组 的解。 这种求解线性方程组的方法称为迭代法， 若迭代序列 收敛，则称迭代法收敛， 否则称迭代法发散 可见 ,J迭代法的迭代矩阵为 若在J迭代法中,充分利用新值, 则可以得到如下的迭代公式 方程组的精确解为x*=(1,1,1)T. 解 J迭代法计算公式为 为了进一步研究,从矩阵角度来讨论上述迭代法. 对线性方程组Ax=b,记 D=diag(a11,a22,…,ann) 则有 A=D-L-U 于是线性方程组 Ax=b 可写成 (D-L-U)x=b 等价于Dx=(L+U)x+b 或 x=D-1(L+U)x+D-1b 或写成 其中 所以G-S迭代法可以写成 其中 讨论迭代法 由于 所以 递推可得 定理3.2 于是有 ‖x(k+1) -x(k) ‖=‖(x (k+1) –x* )-(x(k) –x* )‖ ?‖x (k) –x*‖-‖x(k+1) –x*‖ ?(1-‖M‖)‖x(k) –x*‖ 所以 定理3.2只是收敛的充分条件,并不必要,如 则‖M‖1=1.2,‖M‖?=1.3,‖M‖2=1.09,‖M‖F=1.17 但?(M)=0.81,所以迭代法是收敛的. 由(3.5)式可见,‖M‖越小收敛越快,且当‖x (k) -x(k-1) ‖很小时,‖x(k) –x*‖就很小,实际上用‖x (k) -x(k-1) ‖?作为 迭代终止的条件.例如 1 0