第六章 解线性方程组的迭代法考试必备.ppt

* 第5章 解线性方程组的迭代法 迭代法的基本思想是，把n元线性方程组 （1） 或 Ax b 改写成等价的方程组 ，或x Mx+g 迭代法是从某一取定的初始向量x 0 出发,按照一个适当的迭代公式 ,逐次计算出向量x 1 , x 2 ,…,使得向量序列 x k 收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现. 由此建立方程组的迭代公式 x k+1 Mx k +g , k 0,1,2,… 2 其中M称为迭代矩阵。 对任意取定的初始向量x 0 ,由 2 式可逐次算出迭代向量x k ,k 1,2,…, 如果向量序列 x k 收敛于x*,由 2 式可得 x* Mx*+g 从而x*是方程组x Mx+g的解,也就是方程组Ax b的解. 这种求解线性方程组的方法称为迭代法 ,若迭代序列 x k 收敛,则称迭代法收敛,否则称迭代法发散. §1 Jacobi迭代法和Gauss-Seidel迭代法 Jacobi方法是由方程组 1 中第k个方程解出x k ,得到等价方程组: 从而得迭代公式 式 3 称为Jacobi迭代法,简称为J迭代法. ,则J迭代法可写成 x k+1 Bx k +g k 0,1,2,… 可见 ,J迭代法的迭代矩阵为 若记 J法也记为 G-S迭代法也可记为 式 4 称为Gauss-Seidel迭代法,简称为G-S迭代法. 若在J迭代法中,充分利用新值, 则可以得到如下的迭代公式 方程组的精确解为x* 1,1,1 T. 解 J迭代法计算公式为 例1 用J法和G-S法求解线性方程组 取初始向量x 0 0,0,0 T,迭代可得 计算结果列表如下: 可见,迭代序列逐次收敛于方程组的解, 而且迭代7次得到精确到小数点后两位的近似解. 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 G-S迭代法的计算公式为: 同样取初始向量x 0 0,0,0 T, 计算结果为 由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次. 1 0.4 0.0634 0.0048956 0 1.026 0.987516 10 0.78 1.02048 00 1.4 1.0634 0.9951044 0 1 2 3 ‖x k -x*‖? x3 k x2 k x1 k k 为了进一步研究,从矩阵角度来讨论上述迭代法. 对线性方程组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 由此建立J迭代法迭代公式 x k+1 D-1 L+U x k +D-1b k 0,1,2,… 或写成 x k+1 Bx k +g k 0,1,2,… 其中 G-S迭代法迭代公式可写成 x k+1 D-1Lx k+1 +D-1Ux k +D-1b 讨论迭代法 x k+1 Mx k +g k 0,1,2,… Dx k+1 Lx k+1 +Ux k +b D-L x k+1 Ux k +b x k+1 D-L -1Ux k + D-L -1b