第五章 线性代数方程组的迭代法PPT讲稿.ppt

第五章第五章 线性代数方线性代数方程组的迭代法程组的迭代法第1页，共42页，编辑于2022年，星期三一、特殊方程组求解一、特殊方程组求解n即方程组为即方程组为 n则其解为则其解为1 引引 言言1.对角方程组对角方程组第2页，共42页，编辑于2022年，星期三2三角方程组三角方程组 当当 是三角矩阵，是三角矩阵，此时方程组为此时方程组为 如下三角矩阵如下三角矩阵思考题写出上三角方程组的求解公式 2 利用三角方程组的求解公式导出三角 矩阵求逆的计算公式第3页，共42页，编辑于2022年，星期三二、线性方程组求解的思想二、线性方程组求解的思想 通过若干变换，将一般线性方程组转化为等通过若干变换，将一般线性方程组转化为等价（即同解）的对角（系数矩阵为对角阵）价（即同解）的对角（系数矩阵为对角阵）方程组或三角（系数矩阵为三角形矩阵）方方程组或三角（系数矩阵为三角形矩阵）方程组，而后求解程组，而后求解.求方程组的迭代法，其实质是将方程组逐求方程组的迭代法，其实质是将方程组逐步对角化或三角化，即将线性方程组的求解过步对角化或三角化，即将线性方程组的求解过程表达为对角方程组或三角方程组求解过程的程表达为对角方程组或三角方程组求解过程的不断重复不断重复.第4页，共42页，编辑于2022年，星期三例例1 1 用迭代法求解线性方程组用迭代法求解线性方程组 解解 构造方程组的等价方程组构造方程组的等价方程组据此建立迭代公式据此建立迭代公式 取取 计算得计算得 迭代解离精确解迭代解离精确解 越来越远越来越远,迭代不收敛迭代不收敛.0123456001.50.61.21.20.91.080.960.961.020.9841.0081.008第5页，共42页，编辑于2022年，星期三设设 非奇异，非奇异，则线性方程组，则线性方程组 有惟一解有惟一解 .迭代矩阵求解方程组的迭代法思想求解方程组的迭代法思想 如何构造？迭代序列是否收敛？即收敛条件？误差估计及迭代的加速.第第k1次迭代次迭代第6页，共42页，编辑于2022年，星期三补充三角矩阵的知识：补充三角矩阵的知识：1 定义：定义：n上三角矩阵上三角矩阵 ；n下三角矩阵下三角矩阵 ；n单位上三角矩阵单位上三角矩阵 ；n单位下三角矩阵单位下三角矩阵 ；n严格上三角矩阵严格上三角矩阵 ；n严格下三角矩阵严格下三角矩阵 ；2 性质：性质：对角线以下为零对角线以上为零（1）同结构的三角矩阵之积，结构不变；）同结构的三角矩阵之积，结构不变；（2）三角矩阵的逆是同结构的三角矩阵）三角矩阵的逆是同结构的三角矩阵.第7页，共42页，编辑于2022年，星期三一、雅可比（一、雅可比（Jacobi）迭代法迭代法例例2 2 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 解：从方程组的三个方程中分离出解：从方程组的三个方程中分离出 和和 建立迭代公式建立迭代公式 2 迭代公式的建立迭代公式的建立第8页，共42页，编辑于2022年，星期三1.分量形式分量形式 将将n n元线性方程组元线性方程组 取取据此建立迭代公式据此建立迭代公式 上式称为解方程组的上式称为解方程组的JacobiJacobi迭代公式迭代公式（分量形式分量形式）.伪对角形方程组第9页，共42页，编辑于2022年，星期三2.矩阵形式矩阵形式 设方程组设方程组 的系数矩阵的系数矩阵A A非奇异，且主对非奇异，且主对角元素角元素 ，则可将，则可将A A分裂成分裂成 记作记作 A=L+D+U 第10页，共42页，编辑于2022年，星期三则则 等价于等价于即即因为因为 ，则则则则 得到一个迭代公式得到一个迭代公式令令则有则有（k=0,1,2）称为称为Jacobi迭代公式迭代公式,称为称为Jacobi迭代矩阵迭代矩阵Jacobi迭代的矩阵形式伪对角形方程组第11页，共42页，编辑于2022年，星期三其中其中 在例在例2 2中中,第12页，共42页，编辑于2022年，星期三 雅雅可可比比迭迭代代法法的的算算法法实实现现 第13页，共42页，编辑于2022年，星期三二、二、高斯高斯-塞德尔（塞德尔（Gauss-SeidelGauss-Seidel）迭代法迭代法第14页，共42页，编辑于2022年，星期三1.分量形式分量形式 将将n n元线性方程组元线性方程组 取取据此建立迭代公式据此建立迭代公式 上式称为解方程组的上式称为解方程组的G-SG-S迭代公式（分量形式）迭代公式（分量形式）.伪下三角形方程组 第15页，共42页，编辑于2022年，星期三例例3 用用GaussSeidel 迭代格式解方程组迭代格式解方程组 精确要求为精确要求为=0.005=0.005 解解 GaussGaussSeidel Seidel 迭代格式为迭代格式为取初始迭代向量取初始迭代向量 ,迭代结果为：迭代结果为：x*012340000.12500.3750-0.50000.23440.3031-0.49250.22450.3059-0.49390.22500.3056-0.4936第16页，共42页，编辑于2022年，星期三2 GaussSeidel 迭代法的矩阵表示迭代法的矩阵表示 将将A分裂成分裂成A=L+D+U，则则 等价于等价于 (L+D+U)L+D+U)x=b=b 则高斯则高斯塞德尔迭代过程塞德尔迭代过程 因为因为 ,所以所以 则则故故 令令 第17页，共42页，编辑于2022年，星期三如书中的例如书中的例1、例、例2：则：则：第18页，共42页，编辑于2022年，星期三3 3 迭代法的设计技术迭代法的设计技术 设有设有预报值预报值 ，寻求，寻求校正值校正值 ，使之能具有更好的精度，即能较为准确地成使之能具有更好的精度，即能较为准确地成立立 或或为此考察如下形式的为此考察如下形式的校正方程组校正方程组 （1）与与 相近似相近似,以保证迭代过程收敛；以保证迭代过程收敛；（2）的求逆较简便，以保证迭代公式形式的求逆较简便，以保证迭代公式形式 简单，而更易求解简单，而更易求解.其中称其中称 为校正矩阵，自然要求：为校正矩阵，自然要求：第19页，共42页，编辑于2022年，星期三一一、对角占优阵的概念、对角占优阵的概念1 1对角占优阵对角占优阵定义定义1 1 称方阵称方阵 是对角占优阵，如果其对角是对角占优阵，如果其对角元的绝对值大于同行（或同列）非对角元绝对值之和，元的绝对值大于同行（或同列）非对角元绝对值之和，即即 （或（或 ），），注意，有的教材中称为严格对角占优阵，而对角占优阵注意，有的教材中称为严格对角占优阵，而对角占优阵的定义如下的定义如下 （或（或 ），），其中至少成立一个严格的不等式其中至少成立一个严格的不等式.4 4 迭代法的收敛性迭代法的收敛性 定理 若 按行（或按列）是对角占优阵，则它是非奇异的.第20页，共42页，编辑于2022年，星期三证明证明 反证反证.若若 奇异，则存在奇异，则存在 ，即，即 ，由由 ，不妨设，不妨设 ，则考察第，则考察第 个方程个方程 与已知条件与已知条件矛盾，则矛盾，则 非奇异非奇异.系数矩阵为对角占优阵的线性方程组称作系数矩阵为对角占优阵的线性方程组称作对角占优的方程组对角占优的方程组第21页，共42页，编辑于2022年，星期三2迭代序列的收敛性迭代序列的收敛性定义定义2 称向量序列称向量序列 收敛于收敛于 ,若若 成立成立记作记作若记若记 ，则，则若若 按行是对角占优阵，则按行是对角占优阵，则第22页，共42页，编辑于2022年，星期三二、迭代收敛的充分条件二、迭代收敛的充分条件 定理定理1 若方程组若方程组 为对角占优方程组，则：为对角占优方程组，则：相应的相应的 迭代收敛于方程组的解迭代收敛于方程组的解.证明证明 方程组方程组 为对角占优方程组，则存在唯一为对角占优方程组，则存在唯一 解解 ，设，设 ，则，则 由由 得得 迭代的分量形式迭代的分量形式 则则第23页，共42页，编辑于2022年，星期三从而迭代误差从而迭代误差 有估计式有估计式而而 ，故有，故有所以对于任给的初值，所以对于任给的初值，迭代收敛于方程组迭代收敛于方程组 的解的解 .定理定理2 若方程组若方程组 为对角占优方程组，则：相为对角占优方程组，则：相 应应 迭代收敛于方程组的解迭代收敛于方程组的解.证明证明 迭代迭代 的分量形式的分量形式 第24页，共42页，编辑于2022年，星期三则则设迭代误差设迭代误差 ，则则 其中其中第25页，共42页，编辑于2022年，星期三则则设迭代误差设迭代误差 ，则考察第，则考察第 个方个方程程则则 其中其中 而而第26页，共42页，编辑于2022年，星期三故故 ，则，则所以对于任给的初值，所以对于任给的初值，迭代收敛于方程组迭代收敛于方程组 的解的解 ，且收敛速度快于，且收敛速度快于 迭代迭代.收敛的快慢取决于 的大小推论推论 若方程组若方程组 的系数矩阵的系数矩阵 按行按行(或按列或按列)对对角占优，则其角占优，则其 迭代的收敛速度快于其迭代的收敛速度快于其 迭代的收敛速度迭代的收敛速度.第27页，共42页，编辑于2022年，星期三例例4 用用 迭代、迭代、迭代法求解迭代法求解解：解：为严格对角占优矩阵，所以相应的为严格对角占优矩阵，所以相应的 迭代、迭代、迭代均收敛于方程组的解迭代均收敛于方程组的解 .迭代公式为：迭代公式为：取取 迭代如下：迭代如下：0123450000.77780.87500.88890.97380.97220.97530.99420.99670.99710.99930.99930.99930.99980.99990.9999第28页，共42页，编辑于2022年，星期三 迭代公式为：迭代公式为：取初始值为零，计算结果如下：取初始值为零，计算结果如下：012340000.77780.97220.97530.99420.99930.99930.99981.00001.00001.00001.00001.0000第29页，共42页，编辑于2022年，星期三例例5 证明用证明用证明用证明用 、迭代法求解方程组迭代法求解方程组迭代法求解方程组迭代法求解方程组 时不收敛，试建立收敛的迭代格式时不收敛，试建立收敛的迭代格式时不收敛，试建立收敛的迭代格式时不收敛，试建立收敛的迭代格式.证明：证明：此方程组对应的此方程组对应的 迭代为：迭代为：而此方程组的解也可以写成而此方程组的解也可以写成则则所以所以即此迭代发散即此迭代发散.将此方程组转变为等价的方程组：将此方程组转变为等价的方程组：而此时方程组的系数矩阵是严格对角占优的，则：而此时方程组的系数矩阵是严格对角占优的，则：对该方程组用对该方程组用 迭代是收敛的迭代是收敛的.迭代格式如下：迭代 所以迭代不收敛.第30页，共42页，编辑于2022年，星期三 此方程组对应的此方程组对应的 迭代为：迭代为：而此方程组的解也可以写成而此方程组的解也可以写成则则所以所以即此迭代发散即此迭代发散.将此方程组转变为等价的方程组：将此方程组转变为等价的方程组：而此时方程组的系数矩阵是严格对角占优的，则：而此时方程组的系数矩阵是严格对角占优的，则：对该方程组用对该方程组用 迭代是收敛的迭代是收敛的.迭代格式如下：迭代,所以迭代不收敛.第31页，共42页，编辑于2022年，星期三三、迭代结束的条件三、迭代结束的条件即则-迭代结束的条件迭代结束的条件 第32页，共42页，编辑于2022年，星期三四、小结：迭代法及其收敛条件（参看其它教材）四、小结：迭代法及其收敛条件（参看其它教材）方法一般迭代 迭代 迭代迭代公式充要条件充分条件 存在某种矩阵范数，使得 按行（或按列）对角占优 按行（或按列）对角占优；矩阵 对称正定第33页，共42页，编辑于2022年，星期三用高斯用高斯塞德尔迭代法定义辅助量塞德尔迭代法定义辅助量 1.超松弛迭代法的分量形式超松弛迭代法的分量形式5 超松弛迭代法（超松弛迭代法（SOR方法）方法）Successive Over-Relaxation Method简称简称SOR方法方法第34页，共42页，编辑于2022年，星期三把把 取为取为 与与 的加权平均，即的加权平均，即 代入：代入：式中系数式中系数称为称为松弛因子松弛因子，当，当=1时，便为高斯时，便为高斯-塞德尔迭代法塞德尔迭代法.当当0 1时，低松弛法；当时，低松弛法；当1 2时称为超松弛法时称为超松弛法.但通常统称为超松弛法但通常统称为超松弛法(SOR).SOR迭代公式的分量形式第35页，共42页，编辑于2022年，星期三2.超松弛迭代法的矩阵表示超松弛迭代法的矩阵表示设线性方程组设线性方程组 AxAxb b 的系数矩阵的系数矩阵A非奇异非奇异,且主对角元且主对角元素素 ,将将A A分裂成分裂成A=L+D+U,A=L+D+U,则超松弛则超松弛迭代公式用矩阵表示为迭代公式用矩阵表示为或或 故故 显然对任何一个显然对任何一个值值,(,(D+L)D+L)非奇异非奇异,(,(因为假设因为假设 )于是超松弛迭代公式为于是超松弛迭代公式为 令令则超松弛迭代则超松弛迭代公式可写成公式可写成 收敛的必要条件：第36页，共42页，编辑于2022年，星期三作业作业2、4(2)、5 第37页，共42页，编辑于2022年，星期三课堂练习课堂练习 6、8、11第38页，共42页，编辑于2022年，星期三 Ax=b的系数矩阵按行严格对角占优的系数矩阵按行严格对角占优,故故高斯高斯-塞德尔迭代收敛塞德尔迭代收敛例例 6 设有迭代格式设有迭代格式 X(k+1)=B X(k)+g (k=0,1,2）其中其中B=I-A,如果如果A和和B的特征值全为正数，的特征值全为正数，试证：该迭代格式收敛试证：该迭代格式收敛.证证:因为因为B=I-A,故故(B)=(I)-(A)=1-(A)即即 (A)+(B)=1 由于已知由于已知(A)和和 (B)全为正数，故全为正数，故 0(B)1,从而从而 (B)1 所以该迭代格式收敛所以该迭代格式收敛.第39页，共42页，编辑于2022年，星期三例例7 用用SOR法求解线性方程组法求解线性方程组 取取=1.46，要求要求 解：解：SOR迭代公式迭代公式 k=0,1,2,，初值初值 该方程组的精确解该方程组的精确解只需迭代只需迭代20次便可达到精度要求次便可达到精度要求 如果取如果取=1(即高斯即高斯塞德尔迭代法塞德尔迭代法)和同一初和同一初值值 ,要达到同样精度要达到同样精度,需要迭代需要迭代110次次第40页，共42页，编辑于2022年，星期三例例 8 设设 ,证明证明,求解方程组求解方程组 的的JacobiJacobi迭代与迭代与G-SG-S迭代同时收敛或发散迭代同时收敛或发散 证证:雅可比迭代矩阵雅可比迭代矩阵 其谱半径其谱半径 第41页，共42页，编辑于2022年，星期三例例 8 设设 ,证明证明,求解方程组求解方程组 的的JacobiJacobi迭代与迭代与G-SG-S迭代同时收敛或发散迭代同时收敛或发散 证证:G-SG-S迭代矩阵迭代矩阵 其谱半径其谱半径 显然显然,和和 同时小于、等于或大于同时小于、等于或大于1,1,因而因而JacobiJacobi迭代法与迭代法与G-SG-S迭代法具有相同的收敛性迭代法具有相同的收敛性 第42页，共42页，编辑于2022年，星期三