解线性方程组的迭代法(东北大学).ppt

* 第3章 解线性方程组的迭代法 建立迭代法的基本过程是：首先将线性方程组： Ax=b (3.1) 转化成等价的方程组: x=Mx+g 然后，即可建立迭代格式： x(k+1)=Mx(k)+g , k=0,1,2,…，x(0)取定， (3.2) 迭代法的基本思想是：从某一取定的初始向量x(0)出发,按照一个适当的迭代公式 ,逐次计算出向量x(1), x(2),…,使得向量序列{x(k)}收敛于方程组的精确解 x*.则对充分大的 k，可取x(k)作为x* 的近似值。迭代法是一类逐次近似的方法.其优点是,算法简便,存储量小，程序易于实现. 其中M称为迭代矩阵。对任意取定的初始向量x(0),由(3.2)式可逐次算出迭代向量x(k),k=1,2,…,如果向量序列{x(k)} 收敛于x*,对(3.2)式取极限可得 x*=Mx*+g ?Ax*=b 从而x*是方程组x=Mx+g的解,也就是方程组Ax=b的解. 这种求解线性方程组的方法称为迭代法 ,若迭代序列{x(k)}收敛,则称迭代法收敛,否则称迭代法发散. §1 Jacobi迭代法和Gauss-Seidel迭代法 Jacobi方法是由方程组(3.1)中第i个方程解出xi,得到等价方程组: (以3个未知量为例） 从而得迭代公式 式(3.3)称为Jacobi迭代法,简称为J迭代法. 对于一般的线性方程组： 其等价形式为： 则可建立它的J迭代法 在Jacobi迭代法中，是按顺序 迭代求解 的，也既在计算 时, 已经计算出， 如果能够利用必威体育精装版的计算值，则可能得到收敛更快的迭代 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,迭代可得 计算结果列表如下: 可见,迭代序列逐次收敛于方程组的解, 而且迭代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 为了便于理论研究,现在从矩阵角度来讨论上述迭代法. 对矩阵 A 进行分解,记 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,… 其中 如果将 Ax=b 或 (D-L-U)x=b 改写成 （D-L)x=Ux+b 或 x=(D-L)-1Ux+(D-L)-1b 迭代法的一般形式为( Ax=b ? x=Mx+g ) x(k+1)=Mx(k)+g， k=0