武汉大学求解方程组的迭代法公开课一等奖优质课大赛微课获奖课件.pptx

第二章 2.2 解线性方程组迭代法 数学与统计学院第1页第1页第2页第2页 解线性方程组两类办法直接法:通过有限次运算后可求得方程组准确解办法(不计舍入误差!)迭代法：从解某个近似值出发，通过结构一个无穷序列去迫近准确解办法。第3页第3页 迭代法研究主要问题1）迭代格式结构；2）迭代收敛性分析；3）收敛速度分析；4）复杂性分析；（计算工作量）5）初始值选择。第4页第4页迭代格式结构把矩阵A分裂为则 第5页第5页迭代过程B称为迭代矩阵。给定初值 就得到向量序列定义：若 称逐次迫近法收敛，不然，称逐次迫近法不收敛或发散。第6页第6页问题：是否是方程组（1）解？定理1：任意给定初始向量 ，若由迭代公式（2）产生迭代序列收敛到 ，则 是方程组（1）解。证：第7页第7页逐次迫近法收敛条件定理2：对任意初始向量 ，由（2）得到迭代序列收敛充要条件是迭代矩阵 谱半径证：因此第8页第8页要检查一个矩阵谱半径小于1比较困难，因此我们希望用别办法判断是否有定理3：若逐次迫近法迭代矩阵满足 ，则逐次迫近法收敛。Remark:由于矩阵范数 ，都能够直接用矩阵 元素计算，因此，用定理3，容易判别逐次迫近法收敛性。第9页第9页问题：如何判断能够终止迭代？定理4：若迭代矩阵 满足 则 （3）（4）Remark:1)(4)式给出了一个停止迭代判别准则。2)(3）式指出 越小收敛越快。，第10页第10页证：第11页第11页Jacobi 迭代=第12页第12页Jacobi迭代分裂第13页第13页迭代过程：若记第14页第14页算法描述1 输入2 if ,then 2.1 for 2.1.1 s=0,2.1.2 for 2.1.3 2.1.4 if then 第15页第15页 2.2 k=k+1 2.3 if then 2.3.1 2.3.2 goto 2 else 输出 结束。else 2.4 输出 迭代次数太大。3 结束 第16页第16页Gauss-Seidel迭代假设Jacobi迭代第17页第17页分裂第18页第18页算法描叙1 输入2 if ,then 2.1 for 2.1.1 s=0，2.1.2 for 2.1.3 第19页第19页 2.1.4 if then 2.2 k=k+1 2.3 if ,输出结果，结束。else 2.4 输出迭代次数太大。3 结束 第20页第20页Remark:1)Gauss-Seidel迭代法计算过程比Jacobi迭代法更简朴。计算过程中只需用一个一维数组存储迭代向量。2)Gauss-Seidel迭代不一定比Jacobi迭代收敛快。第21页第21页例第22页第22页希望直接对系数矩阵A研究这俩种迭代收敛条件。第23页第23页定理5 设A是有正对角元n阶对称矩阵，则Jacobi迭代收敛 A和2D-A同为正定矩阵。证：记则 即 ，从而有相同谱半径。第24页第24页由A对称性，也对称，因而特性值全为实数，记为则 任一特性值为 。A，正定。故 正定。第25页第25页A正定 正定，特性 值小于1。若 2D-A正定,特性值小于1,因此 特性值不小于1。第26页第26页定理6 A按行（列）严格对角占优，则Jacobi迭代收敛。引理 A按行（列）严格对角占优 （）证 （提醒）第27页第27页定理7 A按行严格对角占优，则Gauss-Seidel迭代收敛。证 设 是 任一特性值，x 是相应特性向量。设若 则第28页第28页定理8 A按列严格对角占优，则Gauss-Seidel迭代收敛。证 设 是 任一特性值，x 是相应特性向量。设第29页第29页