武汉大学求解方程组的迭代法.ppt

1、第二章,2.2 解线性方程组的迭代法 数学与统计学院,解线性方程组的两类方法 直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。,迭代法研究的主要问题,1）迭代格式的构造； 2）迭代的收敛性分析； 3）收敛速度分析； 4）复杂性分析；（计算工作量） 5）初始值选择。,迭代格式的构造,把矩阵A分裂为 则,迭代过程 B称为迭代矩阵。 给定初值 就得到向量序列 定义：若 称逐次逼近法收敛， 否则，称逐次逼近法不收敛或发散。,问题： 是否是方程组（1）的解？ 定理1：任意给定初始向量 ，若由迭代公式（2）产生的迭

2、代序列收敛到 ，则 是方程组（1）的解。 证：,逐次逼近法收敛的条件,定理2：对任意初始向量 ，由（2）得到的迭代序列收敛的充要条件是迭代矩阵 的谱半径 证： 因此,要检验一个矩阵的谱半径小于1比较困难，所以我们希望用别的办法判断是否有 定理3：若逐次逼近法的迭代矩阵满足 ， 则逐次逼近法收敛。 Remark:因为矩阵范数 ， ， 都可以直接用矩阵 的元素计算，因此，用定理3，容易判别逐次逼近法的收敛性。,问题：如何判断可以终止迭代？ 定理4：若迭代矩阵 满足 则 （3） （4） Remark: (4)式给出了一个停止迭代的判别准则。 (3）式指出 越小收敛越快。 ，,证：,Jacobi 迭代

3、,=,Jacobi迭代,迭代过程： 若记,算法描述,1 输入 2 if , then 2.1 for 2.1.1 s=0, 2.1.2 for 2.1.3 2.1.4 if then,2.2 k=k+1 2.3 if then 2.3.1 2.3.2 goto 2 else 输出 结束。 else 2.4 输出 迭代次数太大。 3 结束,Gauss-Seidel迭代,假设,分裂,算法描叙,1 输入 2 if , then 2.1 for 2.1.1 s=0， 2.1.2 for 2.1.3,2.1.4 if then 2.2 k=k+1 2.3 if ,输出结果，结束。 else 2.4 输出

4、迭代次数太大。 3 结束,Remark: Gauss-Seidel迭代法的计算过程比Jacobi迭代法更简单。计算过程中只需用一个一维数组存放迭代向量。 Gauss-Seidel迭代不一定比Jacobi迭代收敛快。,例,希望直接对系数矩阵A研究这俩种迭代收敛条件。,定理5 设A是有正对角元的n阶对称矩阵，则Jacobi迭代收敛 A和2D-A同为正定矩阵。 证：记 则 即 ， 从而有相同的谱半径。,由A的对称性， 也对称，因而特征值全为实数，记为 则 的任一特征值为 。 A ， 正定。 故 正定。,A正定 正定， 特征 值小于1。 若 2D-A正定, 特征值小于1, 所以 特征值大于1。,定理6 A按行（列）严格对角占优，则Jacobi迭代收敛。 引理 A按行（列）严格对角占优 （ ） 证 （提示）,定理7 A按行严格对角占优，则Gauss- Seidel迭代收敛。 证 设 是 任一特征值，x 是相应特征向