数值分析解线性方程组的迭代法市公开课获奖课件

1、第三章 解线性方程组迭代法 Jacobi迭代法 Gauss-Seidel迭代法 迭代法收敛条件(充要条件, 充足条件)求 迭代法概述1第1页第1页 迭代法概述等价线性方程组取初始向量 x(0)Rn, 结构下列单步定常线性迭代公式以此来产生近似向量序列 x(1), x(2), .当k充足大时， 基本思想等价变形如何做收敛性条件M: 迭代矩阵2第2页第2页定义 对于Rn中向量序列 x(k), 假如则称向量序列x(k)收敛于 Rn中向量 x.定义对于n阶方阵序列 A(k), 假如则称方阵序列A(k)收敛于n阶方阵A. 上面两式通常表示成 向量序列与矩阵序列收敛概念3第3页第3页定理 Rn中向量序列x

2、(k)收敛于Rn中向量x充足必要条件是其中xj(k)和 xj分别表示 x(k)和 x中第 j个分量.定理 n阶方阵序列A(k)收敛于n阶方阵A充足必要条件是 向量序列与矩阵序列收敛充足必要条件 向量序列和矩阵序列收敛可归结为相应分量或相应元素序列收敛性.4第4页第4页 若由迭代公式产生向量序列 x(k) 收敛于向量 x，则即向量 x 是 方程 Ax=b 解. 单步定常线性迭代法产生向量序列若收敛则必收敛到原线性方程组解.5第5页第5页 n=4Jacobi迭代法把方程组改写成下列等价形式6第6页第6页 n=4Jacobi迭代法计算公式已知 用上述迭代公式可算得 7第7页第7页 n=4Jacobi

3、迭代法矩阵表示8第8页第8页 Jacobi迭代法(k)(k)(k)(k)(k+1) 9第9页第9页 设D为由A对角线元素构成对角矩阵Jacobi迭代公式 Jacobi迭代法矩阵表示 迭代矩阵10第10页第10页例 用Jacobi迭代法求解线性方程组解 将方程组改写成下列等价形式11第11页第11页Jacobi迭代法计算公式为假设初始向量取 x(0)=(0, 0, 0)T.第一次迭代第二次迭代12第12页第12页 实际计算时，迭代法中断条件其中 为给定要求精度.13第13页第13页 n=4Gauss-Seidel迭代法把方程组改写成下列等价形式14第14页第14页 n=4Gauss-Seidel

4、迭代法15第15页第15页 Gauss-Seidel迭代法(k)(k)(k+1)(k+1)(k+1) 16第16页第16页在迭代每一步设定计算顺序并且，在计算迭代值 充足利用它前面新信息这样设计出来迭代公式称为高斯塞德尔迭代公式. Gauss-Seidel迭代法17第17页第17页 Gauss-Seidel迭代法矩阵表示 设将系数矩阵A 分裂为其中D为对角阵, L 和U分别为严格下三角和严格上三角阵. 迭代矩阵GaussSeidel迭代公式18第18页第18页例 用Gauss-Seidel迭代法求解线性方程组解 将方程组改写成下列等价形式19第19页第19页Gauss-Seidel迭代法计算公

5、式为假设初始向量取 x(0)=(0, 0, 0)T.第一次迭代20第20页第20页第二次迭代Gauss-Seidel迭代法计算公式为假设初始向量取 x(0)=(0, 0, 0)T.21第21页第21页 Jacobi迭代法：x(k+1)分量计算能够同时进行，无先后顺序 Gauss-Seidel迭代法：x(k+1)分量计算有先后顺序，必须先计算x(k+1)前面分量然后再计算下一分量.22第22页第22页 Jacobi迭代法与Gauss-Seidel迭代法计算效果哪一个更加好？ 前例计算结果表明, 用Gauss-Seidel迭代法比用Jacobi迭代法效果好. 但对普通情形, 有些问题Gauss-S

6、eidel迭代法确实比Jacobi迭代法收敛得快, 但也有Gauss-Seidel迭代法比Jacobi迭代法收敛得慢, 甚至尚有Jacobi迭代法收敛, 但Gauss-Seidel迭代法发散情形.23第23页第23页 迭代法收敛条件定义(谱半径) 设n阶方阵A特性值为i (i=1,2,n)，则称为矩阵A谱半径. Ak 特性值为故24第24页第24页 矩阵范数和谱半径有下列关系设A任一特性值为i , 相应特性向量为ui , 则由任意性可知结论成立. 矩阵A谱半径不超出它任何一个由向量范数诱导出范数，即|A|是A特性值上界.证故从而25第25页第25页 设A为n阶方阵，则 由于2-范数含有上面关系

7、式，因此称 |A|2 为谱范数.26第26页第26页定理 设A是任意n阶方阵，由A各次幂所构成矩阵序列收敛于零矩阵，即充足必要条件是27第27页第27页定理 对任何初始向量 x(0)和右端项g，由迭代公式 x(k+1) =Mx(k)+g (k=0, 1, 2, )产生向量序列x(k)收敛充足必要条件是(M)1其中(M)是迭代矩阵M谱半径. 迭代法收敛充足必要条件 迭代法收敛性只与迭代矩阵谱半径相关, 而迭代矩阵是由A演变来, 因此迭代法是否收敛只与系数矩阵A以及演变方式相关, 与常数项和初始向量选择无关.28第28页第28页证实 必要性. 设序列x(k)收敛于 x*，则有 迭代法收敛充足必要条

8、件任意收敛故由于x(0)为任意n维向量,即29第29页第29页 迭代法收敛充足必要条件任意收敛充足性. 若(M)1, 则 =1不是M特性值, 故方程 (IM)x=g有唯一解, 记为x*, 即又且故对任意初始向量x(0), 都有证实30第30页第30页推论1 若迭代矩阵M满足|M|1, 则下列迭代公式对任意初始向量x(0)收敛 31第31页第31页例 解方程组讨论Jacobi迭代法与Gauss-Seidel迭代法收敛性.解迭代法是否收敛等价于迭代矩阵谱半径是否小于1，故先求迭代矩阵32第32页第32页 Jacobi迭代法迭代矩阵为其特性方程为特性值谱半径故Jacobi迭代法收敛.33第33页第3

9、3页 Gauss-Seidel迭代法迭代矩阵为34第34页第34页其特性方程为特性值谱半径故Gauss-Seidel迭代法发散.35第35页第35页 普通来说, 计算矩阵谱半径比较困难, 故用迭代法收敛充足必要条件来判断迭代法是否收敛往往不太容易, 下列简介用其它办法判别迭代法收敛充足条件.36第36页第36页定义(严格对角占优阵) 称n 阶方阵 是严格对角占优，假如其主对角线元素绝对值不小于同行其它元素绝对值之和：若线性方程组系数矩阵为严格对角占优阵，则称这个线性方程组为严格对角占优方程组.37第37页第37页 迭代法收敛充足条件定理 若A为严格对角占优阵, 则求解Ax=b Jacobi迭代

10、法和Gauss-Seidel迭代法均收敛.定理 若A为对称正定阵, 则求解Ax=bGauss-Seidel迭代法收敛.38第38页第38页例 方程组Ax=b系数矩阵为严格对角占优阵.故Jacobi迭代法与Gauss-Sidel迭代法均收敛.39第39页第39页例 方程组Ax=b系数矩阵为非对角占优阵互换两个方程顺序，得原方程组同解方程组 它是一个严格对角占优方程组，对此方程组Jacobi迭代法和Gauss-Seidel迭代法均收敛. 当所给方程组不满足迭代法收敛条件时, 适当调整方程组中方程顺序, 有时可得到满足迭代法收敛条件同解方程组.40第40页第40页例 方程组Ax=b系数矩阵为但A为对称正定矩阵，Gauss-Seidel迭代法收敛.非严格对角占优41第41页第41页例 设有方程组Ax=b, 其中讨论用两种迭代法求解收敛性.解 A是对称正定阵故Gauss-Seidel迭代法收敛. A不是严格对角占优阵42第42页第42页Jacobi迭代法迭代矩阵为其特性方程为特性值为故迭代矩阵谱半径为 由迭代法收敛充足必要条件知Jacobi迭代法发散.43第43页第43页 误差预计定理 设由迭代格式 x(k+1)=M x(k)+g, 若|M|1,则 x(k)收敛于 x*, 且有误差预