数值分析第三章解线性方程组的迭代法精品文稿.ppt

《数值分析第三章解线性方程组的迭代法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数值分析第三章解线性方程组的迭代法精品文稿.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数值分析第三章解线性方程组的迭代法1第1页，本讲稿共49页 迭代法概述等价线性方程组等价线性方程组取初始向量取初始向量 x(0)Rn,构造如下构造如下单步定常线性单步定常线性迭代迭代公式公式以此来产生近似向量序列以此来产生近似向量序列 x(1),x(2),.当当k充分大时，充分大时，基本思想基本思想等价变形如何做收敛性条件M:迭代矩阵迭代矩阵2第2页，本讲稿共49页定义定义 对于对于Rn中的向量序列中的向量序列 x(k),如果如果则称则称向量序列向量序列x(k)收敛于收敛于 Rn中的向量中的向量 x.定义定义对于对于n阶方阵序列阶方阵序列 A(k),如果如果则称则称方阵序列方阵序列A(k)收敛

2、于收敛于n阶方阵阶方阵A.上面两式通常表示成上面两式通常表示成 向量序列与矩阵序列的收敛概念3第3页，本讲稿共49页定理定理 Rn中的向量序列中的向量序列x(k)收敛于收敛于Rn中的向中的向量量x的充分必要条件是的充分必要条件是其中其中xj(k)和和 xj分别表示分别表示 x(k)和和 x中的第中的第 j个分量个分量.定理定理 n阶方阵序列阶方阵序列A(k)收敛于收敛于n阶方阵阶方阵A的充的充分必要条件是分必要条件是 向量序列与矩阵序列收敛的充分必要条件 向量序列和矩阵序列的收敛可归结为对应分向量序列和矩阵序列的收敛可归结为对应分量或对应元素序列的收敛性量或对应元素序列的收敛性.4第4页，本讲

3、稿共49页 若由迭代公式产生的向量序列 x(k)收敛于向量 x，则即向量 x 是 方程 Ax=b 的解.单步定常线性迭代法产生的向量序列若收敛则单步定常线性迭代法产生的向量序列若收敛则必收敛到原线性方程组的解必收敛到原线性方程组的解.5第5页，本讲稿共49页 n=4的Jacobi迭代法把方程组改写成如下等价形式把方程组改写成如下等价形式6第6页，本讲稿共49页 n=4的Jacobi迭代法计算公式已知 用上述迭代公式可算得 7第7页，本讲稿共49页 n=4的Jacobi迭代法矩阵表示8第8页，本讲稿共49页 Jacobi迭代法(k)(k)(k)(k)(k+1)9第9页，本讲稿共49页 设设D为由

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

5、如下等价形式14第14页，本讲稿共49页 n=4的Gauss-Seidel迭代法15第15页，本讲稿共49页 Gauss-Seidel迭代法(k)(k)(k+1)(k+1)(k+1)16第16页，本讲稿共49页在迭代的每一步设定计算顺序并且，在计算迭代值 充分利用它前面的新信息这样设计出来的迭代公式称为称为高斯高斯塞德尔迭代公式塞德尔迭代公式.Gauss-Seidel迭代法17第17页，本讲稿共49页 Gauss-Seidel迭代法的矩阵表示 设将系数矩阵设将系数矩阵A 分裂为分裂为其中其中D为对角阵为对角阵,L 和和U分别为严格下三角和严格上三分别为严格下三角和严格上三角阵角阵.迭代矩阵迭代

6、矩阵GaussSeidel迭代公式迭代公式18第18页，本讲稿共49页例 用Gauss-Seidel迭代法求解线性方程组解 将方程组改写成如下等价形式19第19页，本讲稿共49页Gauss-Seidel迭代法计算公式为假设初始向量取假设初始向量取 x(0)=(0,0,0)T.第一次迭代第一次迭代20第20页，本讲稿共49页第二次迭代第二次迭代Gauss-Seidel迭代法计算公式为假设初始向量取 x(0)=(0,0,0)T.21第21页，本讲稿共49页 Jacobi迭代法：x(k+1)分量的计算可以同时进行，无先后次序 Gauss-Seidel迭代法：迭代法：x(k+1)分量的计算有分量的计算

7、有先后次序先后次序，必须先计算，必须先计算x(k+1)前前面的分量然后再计算下一分量面的分量然后再计算下一分量.22第22页，本讲稿共49页 Jacobi迭代法与Gauss-Seidel迭代法的计算效果哪一种更好？前例计算结果表明前例计算结果表明,用用Gauss-Seidel迭代法比用迭代法比用Jacobi迭代法效果好迭代法效果好.但对一般情形但对一般情形,有些问题有些问题Gauss-Seidel迭代法确迭代法确实比实比Jacobi迭代法收敛得快迭代法收敛得快,但也有但也有Gauss-Seidel迭迭代法比代法比Jacobi迭代法收敛得慢迭代法收敛得慢,甚至还有甚至还有Jacobi迭迭代法收敛

8、代法收敛,但但Gauss-Seidel迭代法发散的情形迭代法发散的情形.23第23页，本讲稿共49页 迭代法的收敛条件定义定义(谱半径谱半径)设设n阶方阵阶方阵A的特征值为的特征值为 i(i=1,2,n)，则称，则称为矩阵A的谱半径.Ak 的特征值为的特征值为故故24第24页，本讲稿共49页 矩阵范数和谱半径有如下关系设设A的任一特征值为的任一特征值为 i,对应的特征向量为对应的特征向量为ui,则则由由 的任意性可知结论成立的任意性可知结论成立.矩阵矩阵A的谱半径不超过它的任何一种由向量范数的谱半径不超过它的任何一种由向量范数诱导出的范数，即诱导出的范数，即|A|是是A的特征值的上界的特征值的

9、上界.证证故故从而从而25第25页，本讲稿共49页 设A为n阶方阵，则 由于由于2-范数具有上面的关系式，所以称范数具有上面的关系式，所以称|A|2 为为谱范数谱范数.26第26页，本讲稿共49页定理 设A是任意n阶方阵，由A的各次幂所组成的矩阵序列收敛于零矩阵，即的充分必要条件是27第27页，本讲稿共49页定理定理 对任何初始向量对任何初始向量 x(0)和右端项和右端项g，由迭代公式，由迭代公式 x(k+1)=Mx(k)+g (k=0,1,2,)产生的向量序列产生的向量序列x(k)收敛的充分必要条件是收敛的充分必要条件是(M)1其中其中(M)是迭代矩阵是迭代矩阵M的谱半径的谱半径.迭代法收敛

10、的充分必要条件 迭代法的收敛性只与迭代法的收敛性只与迭代矩阵的谱半径迭代矩阵的谱半径有关有关,而而迭代矩阵是由迭代矩阵是由A演变来的演变来的,因此迭代法是否收敛只与因此迭代法是否收敛只与系数矩阵系数矩阵A以及演变的方式有关以及演变的方式有关,与常数项和初始向与常数项和初始向量的选择无关量的选择无关.28第28页，本讲稿共49页证明证明 必要性必要性.设序列设序列x(k)收敛于收敛于 x*，则有，则有 迭代法收敛的充分必要条件任意收敛故故由于由于x(0)为任意为任意n维向量维向量,即即29第29页，本讲稿共49页 迭代法收敛的充分必要条件任意收敛充分性充分性.若若(M)1,则则 =1不是不是M的

11、特征值的特征值,故故方程方程(IM)x=g有唯一解有唯一解,记为记为x*,即即又又且且故对任意初始向量故对任意初始向量x(0),均有均有证明30第30页，本讲稿共49页推论1 若迭代矩阵M满足|M|1,则下列迭代公式对任意初始向量x(0)收敛 31第31页，本讲稿共49页例 解方程组讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性.解迭代法是否收敛等价于迭代矩阵的谱半径是否小迭代法是否收敛等价于迭代矩阵的谱半径是否小于于1，故先求迭代矩阵，故先求迭代矩阵32第32页，本讲稿共49页 Jacobi迭代法的迭代矩阵为其特征方程为其特征方程为特征值特征值谱半径谱半径故故Jacobi迭代

12、法迭代法收敛收敛.33第33页，本讲稿共49页 Gauss-Seidel迭代法的迭代矩阵为34第34页，本讲稿共49页其特征方程为特征值特征值谱半径谱半径故故Gauss-Seidel迭代法迭代法发散发散.35第35页，本讲稿共49页 一般来说,计算矩阵的谱半径比较困难,故用迭代法收敛的充分必要条件来判断迭代法是否收敛往往不太容易,以下介绍用其他方法判别迭代法收敛的充分条件.36第36页，本讲稿共49页定义(严格对角占优阵)称n 阶方阵 是严格对角占优的，如果其主对角线元素的绝对值大于同行其它元素绝对值之和：若线性方程组的系数矩阵为严格对角占优阵，则称这个线性方程组为严格对角占优方程组.37第3

13、7页，本讲稿共49页 迭代法收敛的充分条件定理定理 若若A为为严格对角占优阵严格对角占优阵,则求解则求解Ax=b 的的Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.定理定理 若若A为为对称正定阵对称正定阵,则则求解求解Ax=b的的Gauss-Seidel迭代法收敛迭代法收敛.38第38页，本讲稿共49页例 方程组Ax=b的系数矩阵为严格对角占优阵严格对角占优阵.故故Jacobi迭代法与迭代法与Gauss-Sidel迭代法均收敛迭代法均收敛.39第39页，本讲稿共49页例例 方程组方程组Ax=b的系数矩阵为的系数矩阵为非对角占优阵非对角占优阵交换交换两个方程的次序

14、，得原方程组的同解方程组两个方程的次序，得原方程组的同解方程组 它是一个严格对角占优方程组，对此方程组它是一个严格对角占优方程组，对此方程组Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.当所给的方程组不满足迭代法的收敛条件时,适当调整方程组中方程的次序,有时可得到满足迭代法收敛条件的同解方程组.40第40页，本讲稿共49页例 方程组Ax=b的系数矩阵为但但A为对称正定矩阵，为对称正定矩阵，Gauss-Seidel迭代法收敛迭代法收敛.非严格对角占优非严格对角占优41第41页，本讲稿共49页例 设有方程组Ax=b,其中讨论用两种迭代法求解的收敛性.解 A是对称正定

15、阵是对称正定阵故故Gauss-Seidel迭代法收敛迭代法收敛.A不是严格对角占优阵不是严格对角占优阵42第42页，本讲稿共49页Jacobi迭代法的迭代矩阵为其特征方程为其特征方程为特征值为特征值为故迭代矩阵的谱半径为故迭代矩阵的谱半径为 由迭代法收敛的充分必要条件知由迭代法收敛的充分必要条件知Jacobi迭代法发散迭代法发散.43第43页，本讲稿共49页 误差估计定理 设由迭代格式 x(k+1)=M x(k)+g,若|M|1,则 x(k)收敛于 x*,且有误差估计式44第44页，本讲稿共49页证明由以上两式得由以上两式得故故45第45页，本讲稿共49页证明46第46页，本讲稿共49页由此可知，为使 只要实际计算时，当实际计算时，当|M|不太接近不太接近1时，可用时，可用作为停机准则作为停机准则,x(k)即为满足精度要求之近似解即为满足精度要求之近似解.停机准则47第47页，本讲稿共49页 根据事先给定的精度，可以估算出迭代的次数k48第48页，本讲稿共49页上机作业上机作业第第89页第页第1题题(1)(2).49第49页，本讲稿共49页