数值分析解线性方程组的迭代法省公共课一等奖全国赛课获奖课件.pptx

第三章第三章 解线性方程组迭代法解线性方程组迭代法 Jacobi迭代法迭代法 Gauss-Seidel迭代法迭代法 迭代法收敛条件迭代法收敛条件(充要条件充要条件,充分条件充分条件)求求 迭代法概述迭代法概述1第1页 迭代法概述迭代法概述等价线性方程组等价线性方程组取初始向量取初始向量 x(0)Rn,结构以下结构以下单步定常线性单步定常线性迭代迭代公式公式以此来产生近似向量序列以此来产生近似向量序列 x(1),x(2),.当当k充分大时，充分大时，基本思想基本思想等价变形等价变形怎样做怎样做收敛性条件收敛性条件M:迭代矩阵迭代矩阵2第2页定义定义 对于对于Rn中向量序列中向量序列 x(k),假如假如则称则称向量序列向量序列x(k)收敛于收敛于 Rn中向量中向量 x.定义定义对于对于n阶方阵序列阶方阵序列 A(k),假如假如则称则称方阵序列方阵序列A(k)收敛于收敛于n阶方阵阶方阵A.上面两式通常表示成上面两式通常表示成 向量序列与矩阵序列收敛概念向量序列与矩阵序列收敛概念3第3页定理定理 Rn中向量序列中向量序列x(k)收敛于收敛于Rn中向量中向量x充充分必要条件是分必要条件是其中其中xj(k)和和 xj分别表示分别表示 x(k)和和 x中第中第 j个分量个分量.定理定理 n阶方阵序列阶方阵序列A(k)收敛于收敛于n阶方阵阶方阵A充充分必要条件是分必要条件是 向量序列与矩阵序列收敛充分必要条件向量序列与矩阵序列收敛充分必要条件 向量序列和矩阵序列收敛可归结为对应分量向量序列和矩阵序列收敛可归结为对应分量或对应元素序列收敛性或对应元素序列收敛性.4第4页 若由迭代公式若由迭代公式产生向量序列产生向量序列 x(k)收敛于向量收敛于向量 x，则则即向量即向量 x 是是 方程方程 Ax=b 解解.单步定常线性迭代法产生向量序列若收敛则必单步定常线性迭代法产生向量序列若收敛则必收敛到原线性方程组解收敛到原线性方程组解.5第5页 n=4Jacobi迭代法迭代法把方程组改写成以下等价形式把方程组改写成以下等价形式6第6页 n=4Jacobi迭代法计算公式迭代法计算公式已知已知 用上述迭代公式可算得用上述迭代公式可算得 7第7页 n=4Jacobi迭代法矩阵表示迭代法矩阵表示8第8页 Jacobi迭代法迭代法(k)(k)(k)(k)(k+1)9第9页 设设D为由为由A对角线元素组成对角矩阵对角线元素组成对角矩阵Jacobi迭代公式迭代公式 Jacobi迭代法矩阵表示迭代法矩阵表示 迭代矩阵迭代矩阵10第10页例例 用用Jacobi迭代法求解线性方程组迭代法求解线性方程组解解 将方程组改写成以下等价形式将方程组改写成以下等价形式11第11页Jacobi迭代法计算公式为迭代法计算公式为假设初始向量取假设初始向量取 x(0)=(0,0,0)T.第一次迭代第一次迭代第二次迭代第二次迭代12第12页 实际计算时，迭代法中止条件实际计算时，迭代法中止条件其中其中 为给定要求精度为给定要求精度.13第13页 n=4Gauss-Seidel迭代法迭代法把方程组改写成以下等价形式把方程组改写成以下等价形式14第14页 n=4Gauss-Seidel迭代法迭代法15第15页 Gauss-Seidel迭代法迭代法(k)(k)(k+1)(k+1)(k+1)16第16页在迭代每一步设定计算次序在迭代每一步设定计算次序而且，在计算迭代值而且，在计算迭代值 充分利用它前面新信息充分利用它前面新信息这么设计出来迭代公式这么设计出来迭代公式称为称为高斯高斯塞德尔迭代公式塞德尔迭代公式.Gauss-Seidel迭代法迭代法17第17页 Gauss-Seidel迭代法矩阵表示迭代法矩阵表示 设将系数矩阵设将系数矩阵A 分裂为分裂为其中其中D为对角阵为对角阵,L 和和U分别为严格下三角和严格上三分别为严格下三角和严格上三角阵角阵.迭代矩阵迭代矩阵GaussSeidel迭代公式迭代公式18第18页例例 用用Gauss-Seidel迭代法求解线性方程组迭代法求解线性方程组解解 将方程组改写成以下等价形式将方程组改写成以下等价形式19第19页Gauss-Seidel迭代法计算公式为迭代法计算公式为假设初始向量取假设初始向量取 x(0)=(0,0,0)T.第一次迭代第一次迭代20第20页第二次迭代第二次迭代Gauss-Seidel迭代法计算公式为迭代法计算公式为假设初始向量取假设初始向量取 x(0)=(0,0,0)T.21第21页 Jacobi迭代法：迭代法：x(k+1)分量计算能够分量计算能够同时同时进行，无先后次序进行，无先后次序 Gauss-Seidel迭代法：迭代法：x(k+1)分量计算有分量计算有先后次序先后次序，必须先计算，必须先计算x(k+1)前面前面分量然后再计算下一分量分量然后再计算下一分量.22第22页 Jacobi迭代法与迭代法与Gauss-Seidel迭代法计算效果哪迭代法计算效果哪一个更加好？一个更加好？前例计算结果表明前例计算结果表明,用用Gauss-Seidel迭代法比用迭代法比用Jacobi迭代法效果好迭代法效果好.但对普通情形但对普通情形,有些问题有些问题Gauss-Seidel迭代法确迭代法确实比实比Jacobi迭代法收敛得快迭代法收敛得快,但也有但也有Gauss-Seidel迭代法比迭代法比Jacobi迭代法收敛得慢迭代法收敛得慢,甚至还有甚至还有Jacobi迭代法收敛迭代法收敛,但但Gauss-Seidel迭代法发散情形迭代法发散情形.23第23页 迭代法收敛条件迭代法收敛条件定义定义(谱半径谱半径)设设n阶方阵阶方阵A特征值为特征值为 i(i=1,2,n)，则称，则称为矩阵为矩阵A谱半径谱半径.Ak 特征值为特征值为故故24第24页 矩阵范数和谱半径有以下关系矩阵范数和谱半径有以下关系设设A任一特征值为任一特征值为 i,对应特征向量为对应特征向量为ui,则则由由 任意性可知结论成立任意性可知结论成立.矩阵矩阵A谱半径不超出它任何一个由向量范数诱导谱半径不超出它任何一个由向量范数诱导出范数，即出范数，即|A|是是A特征值上界特征值上界.证证故故从而从而25第25页 设设A为为n阶方阵阶方阵，则，则 因为因为2-范数含有上面关系式，所以称范数含有上面关系式，所以称|A|2 为为谱谱范数范数.26第26页定理定理 设设A是任意是任意n阶方阵，由阶方阵，由A各次幂所组成矩阵各次幂所组成矩阵序列序列收敛于零矩阵，即收敛于零矩阵，即充分必要条件是充分必要条件是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页证实证实 必要性必要性.设序列设序列x(k)收敛于收敛于 x*，则有，则有 迭代法收敛充分必要条件迭代法收敛充分必要条件任意任意收敛收敛故故因为因为x(0)为任意为任意n维向量维向量,即即29第29页 迭代法收敛充分必要条件迭代法收敛充分必要条件任意任意收敛收敛充分性充分性.若若(M)1,则则 =1不是不是M特征值特征值,故故方程方程(IM)x=g有唯一解有唯一解,记为记为x*,即即又又且且故对任意初始向量故对任意初始向量x(0),都有都有证实证实30第30页推论推论1 若迭代矩阵若迭代矩阵M满足满足|M|1,则以下迭代公则以下迭代公式对任意初始向量式对任意初始向量x(0)收敛收敛 31第31页例例 解方程组解方程组讨论讨论Jacobi迭代法与迭代法与Gauss-Seidel迭代法收敛性迭代法收敛性.解解迭代法是否收敛等价于迭代矩阵谱半径是否小于迭代法是否收敛等价于迭代矩阵谱半径是否小于1，故先求迭代矩阵，故先求迭代矩阵32第32页 Jacobi迭代法迭代矩阵为迭代法迭代矩阵为其特征方程为其特征方程为特征值特征值谱半径谱半径故故Jacobi迭代法迭代法收敛收敛.33第33页 Gauss-Seidel迭代法迭代矩阵为迭代法迭代矩阵为34第34页其特征方程为其特征方程为特征值特征值谱半径谱半径故故Gauss-Seidel迭代法迭代法发散发散.35第35页 普通来说普通来说,计算矩阵谱半径比较困难计算矩阵谱半径比较困难,故用迭故用迭代法收敛充分必要条件来判断迭代法是否收敛往往代法收敛充分必要条件来判断迭代法是否收敛往往不太轻易不太轻易,以下介绍用其它方法判别迭代法收敛以下介绍用其它方法判别迭代法收敛充充分条件分条件.36第36页定义定义(严格对角占优阵严格对角占优阵)称称n 阶方阵阶方阵 是是严格对角占优严格对角占优，假如其主对角线元素绝对值大于同，假如其主对角线元素绝对值大于同行其它元素绝对值之和：行其它元素绝对值之和：若线性方程组系数矩阵为严格对角占优阵，则称这若线性方程组系数矩阵为严格对角占优阵，则称这个线性方程组为个线性方程组为严格对角占优方程组严格对角占优方程组.37第37页 迭代法收敛充分条件迭代法收敛充分条件定理定理 若若A为为严格对角占优阵严格对角占优阵,则求解则求解Ax=b Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.定理定理 若若A为为对称正定阵对称正定阵,则则求解求解Ax=bGauss-Seidel迭代法收敛迭代法收敛.38第38页例例 方程组方程组Ax=b系数矩阵为系数矩阵为严格对角占优阵严格对角占优阵.故故Jacobi迭代法与迭代法与Gauss-Sidel迭代法均收敛迭代法均收敛.39第39页例例 方程组方程组Ax=b系数矩阵为系数矩阵为非对角占优阵非对角占优阵交换交换两个方程次序，得原方程组同解方程组两个方程次序，得原方程组同解方程组 它是一个严格对角占优方程组，对此方程组它是一个严格对角占优方程组，对此方程组Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.当所给方程组不满足迭代法收敛条件时当所给方程组不满足迭代法收敛条件时,适当调适当调整方程组中方程次序整方程组中方程次序,有时可得到满足迭代法收敛有时可得到满足迭代法收敛条件同解方程组条件同解方程组.40第40页例例 方程组方程组Ax=b系数矩阵为系数矩阵为但但A为对称正定矩阵，为对称正定矩阵，Gauss-Seidel迭代迭代法收敛法收敛.非严格对角占优非严格对角占优41第41页例例 设有方程组设有方程组Ax=b,其中其中讨论用两种迭代法求解收敛性讨论用两种迭代法求解收敛性.解解 A是对称正定阵是对称正定阵故故Gauss-Seidel迭代法收敛迭代法收敛.A不是严格对角占优阵不是严格对角占优阵42第42页Jacobi迭代法迭代矩阵为迭代法迭代矩阵为其特征方程为其特征方程为特征值为特征值为故迭代矩阵谱半径为故迭代矩阵谱半径为 由迭代法收敛充分必要条件知由迭代法收敛充分必要条件知Jacobi迭代法发散迭代法发散.43第43页 误差预计误差预计定理定理 设由迭代格式设由迭代格式 x(k+1)=M x(k)+g,若若|M|1,则则 x(k)收敛于收敛于 x*,且有误差预计式且有误差预计式 44第44页证实证实由以上两式得由以上两式得故故45第45页证实证实46第46页由此可知，为使由此可知，为使 只要只要实际计算时，当实际计算时，当|M|不太靠近不太靠近1时，可用时，可用作为停机准则作为停机准则,x(k)即为满足精度要求之近似解即为满足精度要求之近似解.停机准则停机准则47第47页 依据事先给定精度依据事先给定精度，能够估算出迭代次数，能够估算出迭代次数k48第48页上机作业上机作业第第89页第页第1题题(1)(2).49第49页