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

第第 4 章章线性方程组迭代解法线性方程组迭代解法基础教学部数学教研室基础教学部数学教研室 彭彭 晓晓 华华立体化教学资源系列立体化教学资源系列数值分析数值分析第第1页页线性方程组迭代解法线性方程组迭代解法4.1 引言引言当当A为低阶稠密矩阵时，选主元消去法是有效方法。为低阶稠密矩阵时，选主元消去法是有效方法。对于对于大型稀疏线性方程组迭代法是适当大型稀疏线性方程组迭代法是适当。迭代法基本步骤迭代法基本步骤（1 1）等价形式等价形式B称为迭代矩阵。称为迭代矩阵。（2 2）迭代公式迭代公式线性方程组线性方程组 A为非奇异矩阵为非奇异矩阵。基本思想基本思想:用某种极限过程逐步迫近方程组准确解用某种极限过程逐步迫近方程组准确解。（3 3）任取向量）任取向量,由上式生成向量序列由上式生成向量序列 。若若，则迭代过程，则迭代过程收敛收敛。第第2页页线性方程组迭代解法线性方程组迭代解法（3 3）计算机算法？）计算机算法？本章讨论本章讨论（2 2）迭代法收敛性与收敛速度？误差预计？）迭代法收敛性与收敛速度？误差预计？（1 1）惯用迭代方法及详细形式？惯用迭代方法及详细形式？4.2 基本迭代法基本迭代法4.2.1 雅可比迭代法雅可比迭代法一、三阶方程组雅可比（一、三阶方程组雅可比（Jacobi）迭代法）迭代法例例1 1 解方程组解方程组 第第3页页线性方程组迭代解法线性方程组迭代解法解解 1 1）等价形式）等价形式 2 2）雅可比迭代公式）雅可比迭代公式3 3）取初始向量）取初始向量 第第4页页.终止条件终止条件 线性方程组迭代解法线性方程组迭代解法显显然迭代序列然迭代序列逐步迫近准确解逐步迫近准确解迭代计算结果如表迭代计算结果如表 第第5页页二、二、n 阶方程组雅可比迭代法阶方程组雅可比迭代法线性方程组迭代解法线性方程组迭代解法第第i i个方程个方程 对于对于n阶线性方程组阶线性方程组 Ax=b,A为为非奇异矩阵，且非奇异矩阵，且 等价方程等价方程 雅可比雅可比(Jacobi)(Jacobi)迭代公式迭代公式：对于：对于 任取任取 x(0),计算得计算得第第6页页三、雅可比迭代法矩阵描述三、雅可比迭代法矩阵描述，其中，其中，线性方程组迭代解法线性方程组迭代解法终止条件终止条件为满足精度为满足精度 近似值。近似值。第第7页页，即，即 雅可比迭代公式矩雅可比迭代公式矩阵阵形式形式:线性方程组迭代解法线性方程组迭代解法其中，其中，称为称为雅可比迭代矩阵雅可比迭代矩阵，第第8页页调用函数调用函数Jacobi.mJacobi.m解例解例1.1.线性方程组迭代解法线性方程组迭代解法计算得到计算得到输入输入A=10 3 1;2-10 3;1 3 10;b=14-5 14;A=10 3 1;2-10 3;1 3 10;b=14-5 14;ep=0.005;ep=0.005;x,k,index=Jacobi(A,b,ep)x,k,index=Jacobi(A,b,ep)x=0.9982 k=7 index=1 x=0.9982 k=7 index=1 迭代成功，收敛。迭代成功，收敛。1.0001 1.0001 0.9982 0.9982第第9页页4.2.2 高斯高斯塞德尔塞德尔(G-S)迭代法迭代法线性方程组迭代解法线性方程组迭代解法例例2 2 解下面方程组（与例解下面方程组（与例1 1相同，准确解相同，准确解）解解 1 1）等价方程组等价方程组 第第10页页2 2）高斯高斯-赛德尔迭代公式赛德尔迭代公式 线性方程组迭代解法线性方程组迭代解法3 3）取初始向量取初始向量 第第11页页线性方程组迭代解法线性方程组迭代解法迭代计算，得迭代计算，得【注注】高斯高斯-赛德尔迭代法比雅可比迭代法收敛快。赛德尔迭代法比雅可比迭代法收敛快。第第12页页线性方程组迭代解法线性方程组迭代解法二、二、n阶方程组高斯阶方程组高斯塞德尔迭代法塞德尔迭代法第第i个方程个方程 等价方程组等价方程组 任取初始解向量任取初始解向量 计算得迭代序列计算得迭代序列 高斯高斯-赛德尔赛德尔(G-S)(G-S)迭代公式迭代公式对于对于 终止条件终止条件 第第13页页G-SG-S迭代矩阵形式迭代矩阵形式 线性方程组迭代解法线性方程组迭代解法【注注】（1 1）迭代法）迭代法分量形式分量形式:用于用于计计算算编编程；程；矩矩阵阵形式形式:用于研究迭代序列用于研究迭代序列是否收敛等理论分析。是否收敛等理论分析。（2 2）Jacobi适合并行适合并行计计算算.不足不足:需存放两个向量。需存放两个向量。（3 3）G-SG-S迭代法只需一个向量存放空间。迭代法只需一个向量存放空间。三、高斯三、高斯塞德尔迭代法矩阵描述塞德尔迭代法矩阵描述矩阵表示矩阵表示 第第14页页调用函数调用函数 Gauss_Seidel.m Gauss_Seidel.m 解例解例1.1.线性方程组迭代解法线性方程组迭代解法x=0.9998 k=4 index=1 x=0.9998 k=4 index=1 迭代成功，收敛。迭代成功，收敛。0.9998 0.9998 1.0001 1.0001得到得到输入输入A=10 3 1;2-10 3;1 3 10;A=10 3 1;2-10 3;1 3 10;b=14-5 14;ep=0.005;b=14-5 14;ep=0.005;x,k,index=Gauss_Seidel(A,b,ep)x,k,index=Gauss_Seidel(A,b,ep)（4 4）在一些情况下，）在一些情况下，G-SG-S迭代法加速收迭代法加速收敛敛，但它是，但它是一个一个经经典串行算法。典串行算法。第第15页页例例3 3 分分别别用雅可比和高斯用雅可比和高斯-赛赛德德尔尔迭代法解方程迭代法解方程组组，均取相同初均取相同初值值1 1）JacobiJacobi迭代迭代4 4次到达精度次到达精度G-SG-S发发散。散。线性方程组迭代解法线性方程组迭代解法2 2）JacobiJacobi发散，发散，G-SG-S发散。发散。第第16页页3 3）JacobiJacobi迭代迭代8989次到达精度次到达精度G-SG-S迭代迭代8 8次到达一次到达一样样精度。精度。线性方程组迭代解法线性方程组迭代解法4 4）JacobiJacobi发发散，散，JacobiJacobi和和G-SG-S可能同时发散；可能同时发散；【注注】也可能同时收敛，但一个快另一个慢；也可能同时收敛，但一个快另一个慢；可能一个收敛而另一个发散。可能一个收敛而另一个发散。G-SG-S迭代迭代1010次到达精度次到达精度第第17页页.线性方程组迭代解法线性方程组迭代解法4.2.3 逐次超松弛逐次超松弛(SOR)迭代法迭代法SORSOR迭代法迭代法:G-SG-S迭代法基础上迭代法基础上,用参数校正残差加速用参数校正残差加速.一、逐次超松弛迭代公式一、逐次超松弛迭代公式G-SG-S迭代公式中加、减 第第18页页线性方程组迭代解法线性方程组迭代解法第第i个方程残差个方程残差:【注注】（1 1）G-SG-S：对旧值对旧值，经残差校正而得新近，经残差校正而得新近似值，校正量大小为似值，校正量大小为（2 2）为加速收敛，将校正量乘加速因子）为加速收敛，将校正量乘加速因子 有有 为松驰因子为松驰因子.当当 时为时为低松驰因子低松驰因子；时为时为当当G-SG-S公式；公式；称为称为超松驰因子超松驰因子.第第19页页20二、逐次超松弛迭代法矩阵描述二、逐次超松弛迭代法矩阵描述其中，其中，松弛迭代矩阵松弛迭代矩阵 整理得整理得记作记作 写成矩阵形式写成矩阵形式 第第20页页线性方程组迭代解法线性方程组迭代解法例例4 4 用用SORSOR解方程组，取解方程组，取解解 方程组准确解为：方程组准确解为：取初值取初值 用用G-SG-S迭代得迭代得 第第21页页线性方程组迭代解法线性方程组迭代解法利用利用SORSOR方法方法 初值初值 迭代计算结果迭代计算结果 第第22页页线性方程组迭代解法线性方程组迭代解法【注注】SORSOR迭代迭代5 5次，与次，与G-SG-S法迭代法迭代1010次结果大致相同，次结果大致相同，SORSOR方法松驰因子起到了加速收敛主要作用方法松驰因子起到了加速收敛主要作用.第第23页页线性方程组迭代解法线性方程组迭代解法【注注】最正确松最正确松驰驰因子：使迭代收因子：使迭代收敛敛最快，最快，记记为为（）特殊情形（）特殊情形 若若A A为对称正定三对角矩阵时为对称正定三对角矩阵时 其中其中 为为JacobiJacobi迭代矩阵谱半径迭代矩阵谱半径 （）其它情形（）其它情形 采取试算方法采取试算方法 例例 方程组方程组 取取 精度精度为为:为较为较佳松弛因子佳松弛因子 显然显然第第24页页线性方程组迭代解法线性方程组迭代解法 4.3 迭代法收敛性迭代法收敛性研究：研究：（1 1）收敛性与迭代矩阵关系？）收敛性与迭代矩阵关系？（2 2）迭代公式收敛充要条件？充分条件？）迭代公式收敛充要条件？充分条件？（3 3）迭代收敛速度？）迭代收敛速度？4.3.1迭代法收敛性判别迭代法收敛性判别（迭代法收迭代法收敛敛充要充要条件）条件）n 阶线性方程组，阶线性方程组，A A 为非奇异矩阵，且为非奇异矩阵，且 等价形式等价形式为为 一、迭代矩阵一、迭代矩阵B B准确解准确解 满足满足 线性迭代公式线性迭代公式 第第25页页线性方程组迭代解法线性方程组迭代解法【定理定理1 1】设设，收敛收敛 （迭代法收迭代法收敛敛充分充分条件）条件）由由 假如假如，则则【定理定理2 2】设设，若，若，则则 收敛收敛,且且二、迭代矩阵范数二、迭代矩阵范数【注注】迭代矩阵范数小于迭代矩阵范数小于1 1是收敛充分条件是收敛充分条件.第第26页页线性方程组迭代解法线性方程组迭代解法（迭代法收敛（迭代法收敛基本定理基本定理）【定义定义1 1】方阵方阵A谱半径：谱半径：其中其中 是是An个个特征特征值值。【定理定理3 3】和和 证实证实（1）充分性：设）充分性：设因因为为 取取迭代初迭代初值值当当时时,收收敛敛（2）必要性：）必要性：若迭代法收敛，依据定理若迭代法收敛，依据定理1 1 即即 又由又由 所以所以三、迭代矩阵谱半径三、迭代矩阵谱半径（迭代法收敛基本定理）（迭代法收敛基本定理）第第27页页线性方程组迭代解法线性方程组迭代解法例例5 5证实证实:JacobiJacobi收敛，收敛，G-SG-S发散。发散。证实证实 1)1)2)2)JacobiJacobi收敛。收敛。G-SG-S发散发散【注注】|BJ|=41.利用迭代矩阵范数不能判别其收敛性。利用迭代矩阵范数不能判别其收敛性。第第28页页线性方程组迭代解法线性方程组迭代解法4.3.2 特殊方程组迭代法收敛性特殊方程组迭代法收敛性【定义【定义2 2】行占优：行占优：列占优：列占优：（对角占优矩阵）（对角占优矩阵）弱对角占优矩阵：弱对角占优矩阵：（或（或），），且最少有且最少有一个不等式是严格成立。一个不等式是严格成立。【定义【定义3 3】（可约矩阵）（可约矩阵）存在存在置置换阵换阵P P使使不存在置换阵不存在置换阵P P 使上式成立使上式成立。（不可约矩阵）（不可约矩阵）【注注】可约阵经过行列重排可约阵经过行列重排,求解求解化化为为求解求解 第第29页页线性方程组迭代解法线性方程组迭代解法【定理定理4 4】(1)(1)A为严为严格格对对角占角占优阵优阵，JacobiJacobi和和G-SG-S收敛。收敛。(2)(2)A为为弱弱对对角占角占优阵优阵,且且A不可不可约约,则则JacobiJacobi和和G-SG-S收敛。收敛。只证实只证实JacobiJacobi JacobiJacobi收敛收敛例例6 6 解解 A严格对角占优严格对角占优 JacobiJacobi和和G-SG-S收敛。收敛。【定理定理5 5】A是对称正定方阵，则解是对称正定方阵，则解 G-SG-S收敛。收敛。证实证实 第第30页页线性方程组迭代解法线性方程组迭代解法例例7 7 A对称正定，则对称正定，则G-SG-S收敛收敛.（1 1）取取（2 2）Jacobi Jacobi 发散。发散。G-S G-S 收敛。收敛。第第31页页线性方程组迭代解法线性方程组迭代解法【定理定理6 6】SORSOR收敛收敛 证实证实【定理定理7 7】A A为实对称正定矩阵为实对称正定矩阵,则则 SORSOR收敛收敛【定理定理8 8】(1)(1)A A严严格格对对角占角占优阵优阵(或或弱对角占优不可约阵弱对角占优不可约阵)则则解解Ax=bSORSOR收收敛敛。(2(2)第第32页页线性方程组迭代解法线性方程组迭代解法4.3.3 迭代法收敛速度迭代法收敛速度B B为对为对称矩称矩阵阵 确定使确定使误误差差缩缩小小迭代次数迭代次数【注注】k与与成反比成反比【定义【定义4 4】迭代法收敛速度迭代法收敛速度 第第33页页线性方程组迭代解法线性方程组迭代解法4.4 稀疏方程组及稀疏方程组及MATLABMATLAB实现实现4.4.1分块迭代法分块迭代法为大型稀疏矩阵为大型稀疏矩阵 其中其中 对对x及及b一一样样分分块块阶阶非奇异矩非奇异矩阵阵，为为 第第34页页线性方程组迭代解法线性方程组迭代解法一、块雅可比迭代法（一、块雅可比迭代法（BJBJ）其中其中【注注】块块雅可比迭代法雅可比迭代法需要求解低阶方程组需要求解低阶方程组 其中，其中，第第35页页线性方程组迭代解法线性方程组迭代解法二、块二、块SORSOR迭代法（迭代法（BSORBSOR）从从共需要解共需要解q个低个低阶阶方程方程组组【定理定理9 9】（1 1）假如）假如A为对为对称正定矩称正定矩阵阵，（2 2）则解则解Ax=bBSOR迭代收敛。迭代收敛。4.4.2 MATLAB稀疏矩阵介绍稀疏矩阵介绍例例8 8 利用利用MATLABMATLAB生成稀疏矩阵及求解，并与满阵解法作生成稀疏矩阵及求解，并与满阵解法作时间上对比：时间上对比：第第36页页线性方程组迭代解法线性方程组迭代解法n=1000;e=ones(n,1);n=1000;e=ones(n,1);A=spdiags(e 4*e e,-1:1,n,n);A=spdiags(e 4*e e,-1:1,n,n);%以对角带生成以对角带生成A A或用或用sparsesparse语句生成语句生成b=e;b=e;tic;x=Ab;elapsed_time1=toc tic;x=Ab;elapsed_time1=toc%输出解稀疏矩阵方程组所用时间输出解稀疏矩阵方程组所用时间a=full(A);a=full(A);tic;x=ab;elapsed_time2=toc tic;x=ab;elapsed_time2=toc%输出解满阵方程组所用时间（与计算机速度相关）输出解满阵方程组所用时间（与计算机速度相关）运行得到，解稀疏方程组所用时间为：运行得到，解稀疏方程组所用时间为：elapsed_time1=0.elapsed_time1=0.解满阵方程组所用时间为：解满阵方程组所用时间为：elapsed_time2=0.4380.elapsed_time2=0.4380.第第37页页线性方程组迭代解法线性方程组迭代解法例例9 9 首先编写数据文本文件首先编写数据文本文件sp.dat.sp.dat.%sp.dat%sp.dat：输入每个非零元素行数、列数及非零元素：输入每个非零元素行数、列数及非零元素5 1 105 1 103 5 203 5 204 4 304 4 305 5 405 5 40在在MATLABMATLAB命令窗口中输入指令：命令窗口中输入指令：load sp.dat load sp.dat A=spconvert(sp)A=spconvert(sp)%将数据文件将数据文件sp.datsp.dat转换为稀疏矩阵转换为稀疏矩阵A A第第38页页线性方程组迭代解法线性方程组迭代解法nn=nnz(A)%nn=nnz(A)%输出矩阵输出矩阵A A非零元素个数非零元素个数运行得到运行得到A=A=(5,1)10 (5,1)10 (4,4)30 (4,4)30 (3,5)20 (3,5)20 (5,5)40 (5,5)40 nn=4nn=4【注注】在在MATLABMATLAB中利用中利用sparsesparse建立稀疏矩阵建立稀疏矩阵.比如，比如，a=0 12 0;1 0 3;1 0 0;3 0 9;a=0 12 0;1 0 3;1 0 0;3 0 9;A=sparse(a)%A=sparse(a)%将矩阵将矩阵a a转换为稀疏矩阵形式转换为稀疏矩阵形式 第第39页页线性方程组迭代解法线性方程组迭代解法运行得到运行得到A=A=(2,1)1 (2,1)1 (3,1)1 (3,1)1 (4,1)3 (4,1)3 (1,2)12 (1,2)12 (2,3)3 (2,3)3 (4,3)9 (4,3)9第第40页页41定义定义:设设P P 是一个是一个 mn mn (0,1)(0,1)矩阵，如矩阵，如 mn mn且且 PP=EPP=E，则称，则称 P P为一个为一个 mn mn置换矩阵。其中置换矩阵。其中PP是是P P转置转置矩阵，矩阵，E E是是m m阶单位方阵。阶单位方阵。置换矩阵在置换矩阵在数学数学中中矩阵论矩阵论里，置换矩阵是一个系数只里，置换矩阵是一个系数只由由0 0和和1 1组成组成方块矩阵方块矩阵。置换矩阵每一行和每一列都恰好有。置换矩阵每一行和每一列都恰好有一个一个1 1，其余系数都是，其余系数都是0 0。在。在线性代数线性代数中，每个中，每个n n阶置换矩阵阶置换矩阵都代表了一个对都代表了一个对n n个元素（个元素（n n维空间维空间基基）置换置换。当一个矩阵。当一个矩阵乘上一个置换矩阵时，所得到是原来矩阵横行（置换矩阵乘上一个置换矩阵时，所得到是原来矩阵横行（置换矩阵在左）或纵列（置换矩阵在右）经过置换后得到矩阵。在左）或纵列（置换矩阵在右）经过置换后得到矩阵。置换矩阵也能够定义为单位矩阵一些行和列交换后得置换矩阵也能够定义为单位矩阵一些行和列交换后得到矩阵。到矩阵。返回可约阵返回可约阵第第41页页42返回谱半径返回谱半径第第42页页