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

* 第3章 解线性方程组的迭代法 迭代法的基本思想是，把n元线性方程组 （3.1） 或 Ax=b 改写成等价的方程组 ，或x=Mx+g 迭代法是从某一取定的初始向量x(0)出发,按照一个适当的迭代公式 ,逐次计算出向量x(1), x(2),…,使得向量序列{x(k)}收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现. 由此建立方程组的迭代公式 x(k+1)=Mx(k)+g , k=0,1,2,… (3.2) 其中M称为迭代矩阵。 对任意取定的初始向量x(0),由(3.2)式可逐次算出迭代向量x(k),k=1,2,…, 如果向量序列{x(k)} 收敛于x*,由(3.2)式可得 x*=Mx*+g 从而x*是方程组x=Mx+g的解,也就是方程组Ax=b的解. 这种求解线性方程组的方法称为迭代法 ,若迭代序列{x(k)}收敛,则称迭代法收敛,否则称迭代法发散. §1 Jacobi迭代法和Gauss-Seidel迭代法 Jacobi方法是由方程组(3.1)中第k个方程解出x(k),得到等价方程组: 从而得迭代公式 式(3.3)称为Jacobi迭代法,简称为J迭代法. ,则J迭代法可写成 x(k+1)=Bx(k)+g k=0,1,2,… 可见 ,J迭代法的迭代矩阵为 若记 J法也记为 G-S迭代法也可记为 式(3.4)称为Gauss-Seidel迭代法,简称为G-S迭代法. 若在J迭代法中,充分利用新值, 则可以得到如下的迭代公式 方程组的精确解为x*=(1,1,1)T. 解 J迭代法计算公式为 例1 用J法和G-S法求解线性方程组 取初始向量x(0)=(0,0,0)T,迭代可得 计算结果列表如下: 可见,迭代序列逐次收敛于方程组的解, 而且迭代6次得到精确到小数点后两位的近似解. 1 0.5000 0.2000 0.0710 0.0355 0.0116 0.0058 0 1.4000 1.1100 0.9290 0.9906 1.0116 1.0003 0 0.5000 1.2000 1.0550 0.9645 0.9953 1.0058 0 1.4000 1.1100 0.9290 0.9906 1.0116 1.0003 0 1 2 3 4 5 6 ‖x(k)-x*‖? x3(k) x2(k) x1(k) k G-S迭代法的计算公式为: 同样取初始向量x(0)=(0,0,0)T, 计算结果为 可见G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代4次,而J迭代法需要迭代6次. 1 0.4000 0.0634 0.0049 0.0012 0 1.0260 0.9875 1.0019 0.9996 0 0.7800 1.0205 0.9953 1.0008 0 1.4000 1.0634 0.9951 1.0012 0 1 2 3 4 ‖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