雅可比迭代法-高斯迭代法-松弛迭代法.ppt

第3章 解线性方程组的迭代法 迭代法是从某一取定的初始向量x(0)出发,按照一个适当的迭代公式 ,逐次计算出向量x(1), x(2),…,使得向量序列{x(k)}收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现. §3.1 迭代法概述 定义3.1 设向量序列 k=1, 2,…,向量 如果 则称向量序列{x(k)}收敛于向量x*, 记作 易得, 定义3.2 设序列 为n阶方阵序列，A为n阶方阵， 则称序列 收敛于向量矩阵A, 记为 如果 易得, 迭代法的基本思想是，把n元线性方程组 （3.1） 或 Ax=b 改写成等价的方程组 ，或x=Mx+g 由此建立方程组的迭代公式 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)}收敛,则称迭代法收敛,否则称迭代法发散. §3.2 几种基本的迭代法 Jacobi方法是由方程组(3.1)中第k个方程解出x(k),得到等价方程组: §3.2.1 雅可比 (Jacobi) 迭代法 从而得迭代公式 式(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迭代法中,充分利用新值, 则可以得到如下的迭代公式 §3.2.2 高斯-赛德尔 (Gauss-Seidel) 迭代法 方程组的精确解为x*=(1,1,1)T. 解 J迭代法计算公式为 例1 用J法和G-S法求解线性方程组 取初始向量x(0)=(0,0,0)T,迭代可得 计算结果列表如下: 可见,迭代序列逐次收敛于方程组的解, 而切迭代7次得到精确到小数点后两位的近似解. k x1(k) x2(k) x3(k) ‖x(k)-x*‖? 0 1 2 3 4 5 6 7 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 1 0.5 0.2 0.071 0.0355 0.01159 0.005795 0.0017636 G-S迭代法的计算公式为: 同样取初始向量x(0)=(0,0,0)T, 计算结果为 由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次. k x1(k) x2(k) x3(k) ‖x(k)-x*‖? 0 1 2 3 0 1.4 1.0634 0.9951044 0 0.78 1.02048 00 1.026 0.987516 11 0.4 0.0634 0.0048956 为了进一步研究,从矩阵角度来讨论上述迭代法. 对线性方程组Ax=b,记 D=diag(a11,a22,…,ann) 则有 A=D-L-U 于是线性方程组 Ax=b 可写成