数值分析迭代法的收敛性.ppt

现在学习的是第1页，共32页复习：复习：1、矩阵的特征值与特征向量的定义与计算；、矩阵的特征值与特征向量的定义与计算；设设A为方阵，为方阵，Au=u (u 0)即即是方程是方程|E-A|=0的根的根2、矩阵的特征值与特征向量的性质、矩阵的特征值与特征向量的性质3、Ak=AAA的特征值是的特征值是现在学习的是第2页，共32页一、迭代法的谱半径一、迭代法的谱半径称迭代公式称迭代公式中的矩阵中的矩阵 B 为为迭代矩阵迭代矩阵.定义定义1：定义定义2：设设A为为n阶阶方方阵阵，i(i=1,n)为为A的的特特征征值值，称称特特征征值值模模的的最最大大值值为为矩矩阵阵A的的谱半径，记为谱半径，记为称为矩阵称为矩阵A的谱的谱.现在学习的是第3页，共32页性质：性质：若矩阵若矩阵A的谱为的谱为 谱半径为谱半径为则则 Ak=AAAk个个的谱为的谱为(k=1,2,)谱半径为谱半径为现在学习的是第4页，共32页定理：定理：设设A为任意为任意n阶方阵，阶方阵，|.|为任意由向量为任意由向量 范数诱导出的矩阵的范数，则范数诱导出的矩阵的范数，则证明：证明：对对A的任一特征值的任一特征值i 及相应的特征向量及相应的特征向量ui，都有，都有因为因为ui为非零向量，即为非零向量，即|ui|0，于是有，于是有由由i 的任意性得的任意性得现在学习的是第5页，共32页定理：定理：设设A为为n阶方阵，则对任意正数阶方阵，则对任意正数，存在，存在 一种矩阵范数一种矩阵范数|.|，使得，使得（证明省略）（证明省略）注：注：对对n阶方阵，一般不存在矩阵范数阶方阵，一般不存在矩阵范数|.|，使得，使得但若但若A为对称矩阵，则有为对称矩阵，则有现在学习的是第6页，共32页下面的定理对建立迭代法的收敛条件十分重要下面的定理对建立迭代法的收敛条件十分重要.定理：定理：设设A为为n阶方阵，则阶方阵，则的充要条件为的充要条件为证明：证明：必要性必要性:若若则则而而于是由极限存在准则，有于是由极限存在准则，有故故现在学习的是第7页，共32页充分性充分性:若若取取则存在一种矩阵范数则存在一种矩阵范数|.|，使得，使得而而于是于是所以所以现在学习的是第8页，共32页二、迭代法的收敛条件二、迭代法的收敛条件定理：定理：对任意初始向量对任意初始向量 x(0)和右端项和右端项g，由迭代，由迭代 格式格式 x(k+1)=Mx(k)+g 产生的向量序列收敛的充要条件为产生的向量序列收敛的充要条件为 现在学习的是第9页，共32页证明：证明：必要性必要性设存在设存在n维向量维向量x*，使得，使得则则 x*满足满足由迭代公式有由迭代公式有于是有于是有因为因为x(0)为任意向量，因此上式成立必须为任意向量，因此上式成立必须即即现在学习的是第10页，共32页充分性充分性:若若 则则=1不是不是M的特征值，所以的特征值，所以|I|0于是对任意于是对任意n维向量维向量g，方程组，方程组(IM)x=g有唯有唯一解，记为一解，记为x*，即，即并且并且现在学习的是第11页，共32页又因为又因为故对任意初始向量故对任意初始向量x(0)，都有，都有即由迭代公式产生的向量序列即由迭代公式产生的向量序列x(k)收敛。收敛。推论推论1：若迭代矩阵满足若迭代矩阵满足|M|1，则迭代公式则迭代公式 产生的向量序列产生的向量序列x(k)收敛。收敛。现在学习的是第12页，共32页推论推论2：松弛法收敛的必要条件是松弛法收敛的必要条件是 02证明证明:设松弛法的迭代矩阵设松弛法的迭代矩阵M有特征值有特征值因为因为由定理，松弛法收敛必有由定理，松弛法收敛必有又因为又因为而而现在学习的是第13页，共32页于是有于是有所以所以注：注：定理表明，迭代法收敛与否只决定于迭代定理表明，迭代法收敛与否只决定于迭代 矩阵的谱半径，与初始向量及方程组的右矩阵的谱半径，与初始向量及方程组的右 端项无关。对同一方程组，由于不同的迭端项无关。对同一方程组，由于不同的迭 代法迭代矩阵不同，因此可能出现有的方代法迭代矩阵不同，因此可能出现有的方 法收敛，有的方法发散的情形。法收敛，有的方法发散的情形。现在学习的是第14页，共32页举例：解方程组举例：解方程组讨论讨论Jacobi法与法与Gauss-Seidel法的收敛性。法的收敛性。解解：由由定定理理，迭迭代代法法是是否否收收敛敛等等价价于于迭迭代代矩矩阵阵的的谱谱半半径是否，故应先求迭代矩阵。而径是否，故应先求迭代矩阵。而故故A分解后的各矩阵分别为分解后的各矩阵分别为现在学习的是第15页，共32页Jacobi迭代法的迭代矩阵为迭代法的迭代矩阵为其特征方程为其特征方程为因此有因此有故故Jacobi法收敛法收敛现在学习的是第16页，共32页如果用如果用Gauss-Seidel迭代，由迭代，由可得可得于是迭代矩阵为于是迭代矩阵为其特征方程为其特征方程为现在学习的是第17页，共32页故故所以所以Gauss-Seidel迭代法发散。迭代法发散。请思考请思考:(1)(1)若若记记不不住住JacobiJacobi迭迭代代法法和和Gauss-SeidelGauss-Seidel迭代法的矩阵表示，怎么写出迭代矩阵？迭代法的矩阵表示，怎么写出迭代矩阵？(2)(2)试归纳判断迭代法收敛的方法？试归纳判断迭代法收敛的方法？现在学习的是第18页，共32页答答:(1)从分量表示开始从分量表示开始 (2)先用两个推论，再用充要条件，即先用两个推论，再用充要条件，即|M|1迭代法收敛迭代法收敛松弛法收敛松弛法收敛02迭代法收敛迭代法收敛现在学习的是第19页，共32页现在学习的是第20页，共32页现在学习的是第21页，共32页现在学习的是第22页，共32页下面对一些特殊的系数矩阵给出几个常用的判断下面对一些特殊的系数矩阵给出几个常用的判断收敛的条件。收敛的条件。定义：定义：若若n阶方阵阶方阵 A=(aij)满足满足且至少有一个且至少有一个 i 值，使上式中不等号严值，使上式中不等号严格成立，则称格成立，则称A为为弱对角占优阵弱对角占优阵。若若对对所所有有 i，不不等等号号均均严严格格成成立立，则则称称A为为严格对角占优阵。严格对角占优阵。现在学习的是第23页，共32页例如：例如：矩阵矩阵是严格对角占优阵是严格对角占优阵矩阵矩阵不是严格对角占优阵不是严格对角占优阵现在学习的是第24页，共32页设有线性方程组设有线性方程组Ax=b，下列结论成立：，下列结论成立：1.若若A为为严严格格对对角角占占优优阵阵，则则Jacobi迭迭代代法法和和Gauss-Seidel迭代法均收敛。迭代法均收敛。2.若若A为为严严格格对对角角占占优优阵阵，01，则则松松弛弛法法收收敛。敛。3.若若A为对称正定阵，为对称正定阵，02，则松弛法收敛，则松弛法收敛.即即：若若A是是对对称称正正定定阵阵，则则松松弛弛法法收收敛敛的的充充要要条件为条件为02。现在学习的是第25页，共32页归纳判断迭代法收敛的方法如下：归纳判断迭代法收敛的方法如下：1.首先根据方程组的系数矩阵首先根据方程组的系数矩阵A的特点判断；的特点判断；2.可根据迭代矩阵的范数判断；可根据迭代矩阵的范数判断；3.只好根据迭代矩阵的谱半径判断只好根据迭代矩阵的谱半径判断.现在学习的是第26页，共32页三、举例三、举例例例1：设有方程组：设有方程组Ax=b，其中，其中讨论用三种迭代法求解的收敛性。讨论用三种迭代法求解的收敛性。现在学习的是第27页，共32页解：首先不是对角占优阵，但是对称阵，解：首先不是对角占优阵，但是对称阵，且其各阶顺序主子式均大于，故为对且其各阶顺序主子式均大于，故为对称正定阵，由判别条件可得称正定阵，由判别条件可得Gauss-Seidel法与松弛法法与松弛法(02)均收敛。均收敛。又因为又因为Jacobi迭代法的迭代矩阵为迭代法的迭代矩阵为故故|B|1=|B|=1，因因此不能用范数判断。此不能用范数判断。现在学习的是第28页，共32页下面计算迭代矩阵的谱半径。下面计算迭代矩阵的谱半径。解特征方程解特征方程可得谱半径可得谱半径故故Jacobi迭代法不收敛。迭代法不收敛。现在学习的是第29页，共32页值得注意的是：值得注意的是：改变方程组中方程的顺序，改变方程组中方程的顺序，即将系数矩阵作行交换，会改变迭代法的收即将系数矩阵作行交换，会改变迭代法的收敛性。敛性。例例2：设方程组：设方程组Ax=b的系数矩阵为的系数矩阵为则则Jacobi法法与与Gauss-Seidel法法的的迭迭代代矩矩阵阵分分别是别是其谱半径分别为其谱半径分别为现在学习的是第30页，共32页故这两种迭代法均不收敛。故这两种迭代法均不收敛。但但若若交交换换两两个个方方程程的的次次序序，得得原原方方程程组组的的同同解解方程组方程组显然显然A是严格对角占优阵，因此对方程组是严格对角占优阵，因此对方程组用用Jacobi法和法和Gauss-Seidel法均收敛。法均收敛。现在学习的是第31页，共32页例例3：设设 A=(aij)是是 二二 阶阶 方方 阵阵，且且a11a220.试试 证证 求求解解方方程程组组Ax=b的的Jacobi法法与与Gauss-Seidel法法同同时时收敛或发散。收敛或发散。证明：证明：Jacobi迭代矩阵为迭代矩阵为其谱半径为其谱半径为现在学习的是第32页，共32页