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

数 值 分 析第第3章章 解线性方程组迭代解解线性方程组迭代解法法第1页解非线性方程：解非线性方程：f(x)=0 x=(x)令令xk+1=(xk)，若，若xk ,则则对于线性方程组对于线性方程组Ax=b.考虑等价方程组考虑等价方程组x=Bx+f,为此结构序列：为此结构序列：x(k+1)=Bx(k)+f 向量迭代公式向量迭代公式.要考虑向量列收敛性，误差，向量间距离要考虑向量列收敛性，误差，向量间距离.考虑距离考虑距离第2页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数回顾：回顾：Rn中向量范数：中向量范数：性质：性质：x:|x|0,且且|x|=0 x=0 k R,x:|kx|=|k|x|x,y:|x+y|x|+|y|第3页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数1.向量范数向量范数【定义【定义3-1】设】设V为线性空间，为线性空间，V上实值函数上实值函数N(x)=|x|满足：满足：正定性：正定性：x V:|x|0,且且|x|=0 x=0 正齐性：正齐性：k R,x V:|kx|=|k|x|三角不等式：三角不等式：x,y V:|x+y|x|+|y|则称则称N(x)=|x|为为V上向量上向量x范数范数.第4页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数性质：性质：若若x 0,|x|=|x|x|y|x y|第5页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数线性空间能够定义各种范数线性空间能够定义各种范数.其中最惯用有：其中最惯用有：x=(x1,x2,xn)Rn(Cn)欧式范数：欧式范数：又称为又称为2-范数范数 最大模范数：最大模范数：又称为又称为-范数范数 绝对值范数：绝对值范数：又称为又称为1-范数范数 p范数：范数：第6页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数注：注：能够证实上述定义均满足向量范数定义能够证实上述定义均满足向量范数定义.2-范数和范数和1-范数都是范数都是p-范数特例范数特例.-范数也是范数也是p-范数特例范数特例.(令令p，有，有|x|p|x|).第7页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数【例【例3-3】视】视m n矩阵为矩阵为m n维向量维向量,Am n:称为称为AF范数范数.第8页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵【定义【定义3-2】若】若 An n.对应一个实数对应一个实数|A|，满足：，满足：|A|0,且且|A|=0 A=0|kA|=|k|A|A+B|A|+|B|AB|A|B|则称则称|A|为方阵范数为方阵范数矩阵范数矩阵范数.比如比如 为矩阵范数为矩阵范数.第9页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵注注：矩矩阵阵理理化化及及运运算算常常要要考考虑虑矩矩阵阵与与向向量量乘乘积积，希希望望范数范数|Ax|A|x|.【定定义义3-3】设设|为为向向量量范范数数，|M为为矩矩阵阵范范数数.若若 A Rn n，x Rn|Ax|A|M|x|.则称则称|A|M为与向量范数为与向量范数|相容矩阵范数相容矩阵范数.注：注：|A|F与与|1不相容，如不相容，如第10页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵【定义【定义3-4】设】设 A Rn n，|为向量范数为向量范数.称称 为为矩矩阵阵A算算子子范范数数.(诱诱导导范范数数).注：注：能能够够证证实实算算子子范范数数满满足足矩矩阵阵范范数数4个个条条件件.故故为为矩矩阵阵范数范数.矩阵范数不一定都是算子范数，如矩阵范数不一定都是算子范数，如F-范数范数.第11页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵 算子范数与向量范数相容算子范数与向量范数相容.()第12页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵常见算子范数有：常见算子范数有：2范数范数.其中其中 max(ATA)为矩阵为矩阵ATA绝对值最大特征值绝对值最大特征值.行范数行范数(每行相加每行相加,取最大取最大)列范数列范数(每列相加每列相加,取最大取最大)第13页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数【例【例3-7】设】设则则|A|1=max2,5,2=5(列范数列范数)|A|=max3,4,2=4 3 13 2+38 25=0,第14页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数【例【例3-7】设】设则则|A|1=max2,5,2=5(列范数列范数)|A|=max3,4,2=4 1=9.1428，2=2.9211，3=0.9331.即即注：注：|A|2不易计算但有用不易计算但有用.第15页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数【定定义义3-5】设设 i(i=1,2,n)为为A Rn nn个个特特征征值值,称称 (1.2)为为A谱半径谱半径.注：注：(A)|A|p (1.3)(Ax=x(x 0),则则|x|p=|x|=|Ax|p|A|p|x|A|p (A)=max|A|p 用来预计特征值上界用来预计特征值上界).不超出任何一个矩阵算子不超出任何一个矩阵算子范数范数第16页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数【定理【定理3-1】若】若|A|1，则，则I+A可逆可逆.且且证实：证实：|A|1，(A)1 1不是不是A特征值特征值.故故I+A可逆可逆.第17页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数【定理【定理3-1】若】若|A|0 即即 第18页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍1.问题问题设有方程组设有方程组 解得解得 若有小误差若有小误差解得解得注注：初初始始数数据据A，b微微小小改改变变引引发发解解巨巨大大改改变变.病病态方程组态方程组.第19页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍2.分析分析设设Ax=b+b有解有解 则则 A(x+x)=b+b Ax+Ax=b+b Ax=b x=A-1b|x|A-1|b|其次其次:|b|=|Ax|A|x|(1.8)Ax=b第20页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍2.分析分析设设Ax=b+b有解有解 则则 (1.8)同理，若同理，若(A+A)(x+x)=b可得可得 (1.11)第21页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍2.分析分析 (1.8)(1.11)注注:解解相相对对误误差差不不超超出出初初始始数数据据相相对对误误差差|A|A1|倍倍,即即|A|A1|刻画了方程组形态刻画了方程组形态.第22页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍3.条件数条件数【定义【定义3-3】设】设A非奇异，非奇异，|为算子范数，则称为算子范数，则称 Cond(A)=|A|A1|(1.12)为矩阵为矩阵A条件数条件数.注：注：Cond(A)=|A|A1|AA1|=|I|=1 0 条件数值与范数类型相关条件数值与范数类型相关Cond(A)=|A|A1|(行模行模)第23页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍3.条件数条件数【定义【定义3-3】设】设A非奇异，非奇异，|为算子范数，则称为算子范数，则称 Cond(A)=|A|A1|(1.12)为矩阵为矩阵A条件数条件数.注：注：条件数值与范数类型相关条件数值与范数类型相关Cond(A)=|A|A1|(行模行模)(谱模谱模)其中其中 max、min分别是分别是ATA最大，最小模特征值最大，最小模特征值.第24页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍3.条件数条件数【定义【定义3-3】设】设A非奇异，非奇异，|为算子范数，则称为算子范数，则称 Cond(A)=|A|A1|(1.12)为矩阵为矩阵A条件数条件数.【定定义义3-7】设设A非非奇奇异异.若若Cond(A)1，则则称称Ax=b为病态方程组为病态方程组.若若Cond(A)相对较小，则称相对较小，则称Ax=b为良态方程组为良态方程组.第25页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍3.条件数条件数【定定义义3-7】设设A非非奇奇异异.若若Cond(A)1，则则称称Ax=b为病态方程组为病态方程组.若若Cond(A)相对较小，则称相对较小，则称Ax=b为良态方程组为良态方程组.注：本节开始时方程组中，系数矩阵注：本节开始时方程组中，系数矩阵Cond(A)=|A|A-1|=2.0001 1 40004 所以所以Ax=b为病态为病态.第26页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组病态方程组理理论论上上有有条条件件数数，但但标标准准极极难难定定，且且|A1|极极难难求求.(1)判断方法判断方法直观判断直观判断 用主元消去法求解时出现小主元；用主元消去法求解时出现小主元；一些行、列几乎线性相关一些行、列几乎线性相关 A元素间数量级很大，且无规律元素间数量级很大，且无规律若方程组出现上述情况之一，方程组有可能若方程组出现上述情况之一，方程组有可能“病态病态”。第27页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组病态方程组(2)处理办法处理办法对对于于“病病态态”方方程程组组求求解解，需需要要采采取取特特殊殊处处理理或或专专用用方法：方法：提提升升原原始始数数据据和和运运算算精精度度，如如原原始始数数据据和和运运算算采采取取双精度等。双精度等。用用适适当当方方法法改改进进原原始始模模型型性性态态，如如对对矩矩阵阵进进行行“预预处理处理”以降低其条件数。以降低其条件数。第28页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组病态方程组【例【例3-8】设线性方程组】设线性方程组试计算试计算Cond(A)，并取，并取3位有效数字求解。位有效数字求解。解：解：(1)直接计算直接计算Cond(A)，并求解。，并求解。第29页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组判断病态方程组判断【例【例3-8】设线性方程组】设线性方程组试计算试计算Cond(A)，并取，并取3位有效数字求解。位有效数字求解。解：解：(1)直接计算直接计算Cond(A)，并求解。，并求解。Cond(A)107，使用列主元素消去法求解：，使用列主元素消去法求解：回代：回代：x2=1，代入，代入x1+107x2=107，解得，解得x1=0第30页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组判断病态方程组判断【例【例3-8】设线性方程组】设线性方程组试计算试计算Cond(A)，并取，并取3位有效数字求解。位有效数字求解。解：解：(2)对对A做预处理。在方程组两边左乘矩阵做预处理。在方程组两边左乘矩阵 即即 第31页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组判断病态方程组判断【例【例3-8】设线性方程组】设线性方程组试计算试计算Cond(A)，并取，并取3位有效数字求解。位有效数字求解。解：解：(2)对对A做预处理。做预处理。设设 从而从而 第32页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组判断病态方程组判断【例【例3-8】设线性方程组】设线性方程组试计算试计算Cond(A)，并取，并取3位有效数字求解。位有效数字求解。解：解：(2)对对A做预处理。做预处理。使用列主元素消去法求解：使用列主元素消去法求解：回代：回代：x2=1，代入，代入x1+x2=2，解得，解得x1=1第33页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法 首首先先指指出出,用用近近似似解解x代代入入方方程程组组Ax=b左左端端,观观察察Ax与与b是是否否近近似似,即即用用观观察察残残差差向向量量 r=b Ax“大大小小”来判断来判断x是否能够接收方法是不可靠。是否能够接收方法是不可靠。比如用比如用x=(1,1)T 计算方程组计算方程组残差向量：残差向量：第34页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法 比如用比如用x=(1,1)T 计算方程组计算方程组残差向量：残差向量：非常非常“小小”但但x与其准确解与其准确解x=(2,0)T相差很大相差很大,显然不能接收。显然不能接收。下面介绍一个事后预计近似解相对误差方法。下面介绍一个事后预计近似解相对误差方法。第35页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法【定定理理3-2】设设|A|0且且b 0,x*和和x分分别别为为方方程程组组Ax=b准确解和近似解准确解和近似解,残差向量残差向量 r=b Ax,则有则有证证实实：因因为为x*x=A-1b A-1Ax=A-1(b Ax)=A-1r 知知|x*x|A-1|r|因为因为|b|A|x*|,且且b 0,x*0,故得故得 第36页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法【定定理理3-2】设设|A|0且且b 0,x*和和x分分别别为为方方程程组组Ax=b准确解和近似解准确解和近似解,残差向量残差向量 r=b Ax,则有则有证实：知证实：知|x*x|A-1|r|因为因为|b|A|x*|,且且b 0,x*0,故得故得 所以所以第37页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法【定定理理3-2】设设|A|0且且b 0,x*和和x分分别别为为方方程程组组Ax=b准确解和近似解准确解和近似解,残差向量残差向量 r=b Ax,则有则有定定理理3-2表表明明：近近似似解解x精精度度不不但但依依赖赖于于残残差差向向量量r,而而且还依赖于且还依赖于Cond(A).对于病态方程组对于病态方程组,即使即使r很小很小,也不能确保也不能确保x可靠性。可靠性。第38页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法采采取取高高精精度度计计算算方方法法(如如例例主主元元素素消消去去法法)与与高高精精度度算算术术运运算算(如如双双精精度度),即即使使能能够够提提升升方方程程组组近近似似解解准准确确程程度度,不不过过对对于于病病态态方方程程组组也也不不一一定定能能取取得得高高精精度度近近似解似解,而且方程组病态越严重而且方程组病态越严重,求解越困难。求解越困难。当当用用某某种种方方法法求求得得方方程程组组Ax=b(|A|0且且b0)某某个个近近似似解解x(1)后后,若若还还未未到到达达精精度度要要求求,可可采采取取下下述述改改进进迭迭代代过程取得较准确近似解过程取得较准确近似解.第39页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法 当当用用某某种种方方法法求求得得方方程程组组Ax=b(|A|0且且b0)某某个个近近似似解解x(1)后后,若若还还未未到到达达精精度度要要求求,可可采采取取下下述述改改进进迭迭代过程取得较准确近似解代过程取得较准确近似解.(1)用双精度计算残差向量用双精度计算残差向量 r(1)=b Ax(1);(2)用用列列主主元元素素消消去去法法(或或选选主主元元素素三三角角分分解解法法)解解方方程组程组Ax=r(1)得近似解得近似解d(1);(3)用用d(1)修正修正x(1)得得Ax=b新近似解新近似解x(2)=x(1)+d(1)第40页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法 (1)用双精度计算残差向量用双精度计算残差向量 r(1)=b Ax(1);(2)用用列列主主元元素素消消去去法法(或或选选主主元元素素三三角角分分解解法法)解解方方程组程组Ax=r(1)得近似解得近似解d(1);(3)用用d(1)修正修正x(1)得得Ax=b新近似解新近似解x(2)=x(1)+d(1)假如在计算假如在计算r(1)与与d(1)中没有误差中没有误差,则则 x(2)=x(1)+A-1r(1)=x(1)+A-1(b Ax(1)=A-1b=x*即即x(2)为为Ax=b准确解。准确解。但在实际计算中但在实际计算中,因为舍入误差影因为舍入误差影响响,x(2)仍为仍为Ax=b近似解。近似解。第41页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法 (1)用双精度计算残差向量用双精度计算残差向量 r(1)=b Ax(1);(2)用用列列主主元元素素消消去去法法(或或选选主主元元素素三三角角分分解解法法)解解方方程组程组Ax=r(1)得近似解得近似解d(1);(3)用用d(1)修正修正x(1)得得Ax=b新近似解新近似解x(2)=x(1)+d(1)(4)计计算算 ，若若e (精精度度常常数数),则则取取x*x(2);不不然然视视x(2)为为x(1),重重新新进进行行上上述述过过程程,直直到到满满足条件足条件e 为止。为止。第42页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法上述过程称为方程组上述过程称为方程组Ax=b近似解迭代改进。近似解迭代改进。当当方方程程组组病病态态不不十十分分严严重重时时,经经过过迭迭代代改改进进方方法法取取得得近似解序列能够很快地收敛到方程组准确解。近似解序列能够很快地收敛到方程组准确解。第43页3.3 解线性方程组迭代法解线性方程组迭代法 设线性方程组设线性方程组Ax=b (2.1)其中其中A Rn n，b，x Rn伴伴随随计计算算问问题题日日益益复复杂杂，20世世纪纪30年年代代起起，上上述述系系数数矩阵矩阵A含有两个显著特点：大型化与稀疏性。含有两个显著特点：大型化与稀疏性。大大型型化化指指其其阶阶数数可可达达上上万万阶阶，稀稀疏疏性性指指A零零元元素素占占绝绝大部分。大部分。对对这这么么A作作直直接接三三角角分分解解，稀稀疏疏性性会会受受到到破破坏坏。迭迭代代法在这么背景下得到关注和发展。法在这么背景下得到关注和发展。第44页3.3 解线性方程组迭代法解线性方程组迭代法 设设 线线 性性 方方 程程 组组 Ax=b (2.1)其其中中A Rn n，b，x Rn，将将(2.1)改改写写为为等等价价方方程程组组:x=Bx+f (2.2)取初始向量：取初始向量：令令 x(1)=Bx(0)+f，x(2)=Bx(1)+f，第45页3.3 解线性方程组迭代法解线性方程组迭代法取初始向量：取初始向量：令令 x(1)=Bx(0)+f，x(2)=Bx(1)+f，普通地令普通地令：(k=0,1,2,n).(2.3)第46页3.3 解线性方程组迭代法解线性方程组迭代法令令 (k=0,1,2,n).(2.3)称称(2.3)为为求求解解线线性性方方程程组组迭迭代代法法(迭迭代代过过程程，迭迭代代格格式式).B称称为为迭迭代代矩矩阵阵，若若当当k时时，x(k)x*，则则称称该该迭迭代代法收敛法收敛.不然称迭代法发散不然称迭代法发散.第47页3.3 解线性方程组迭代法解线性方程组迭代法令令 (k=0,1,2,n).(2.3)B称称为为迭迭代代矩矩阵阵，若若当当k时时，x(k)x*，则则称称该该迭迭代代法收敛法收敛.不然称迭代法发散不然称迭代法发散.注：注：x(k)x*，(k)，记作，记作即即|x(k)x*|0，(k)第48页3.3 解线性方程组迭代法解线性方程组迭代法令令 (k=0,1,2,n).(2.3)B称称为为迭迭代代矩矩阵阵，若若当当k时时，x(k)x*，则则称称该该迭迭代代法收敛法收敛.不然称迭代法发散不然称迭代法发散.注：注：(2.3)两端取极限得两端取极限得x*=Bx*+f，即即x*是是(2.2)解，从而是解，从而是(2.1)解解.第49页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法 记记(2.1)为为设设A=(aij)n n可逆，且可逆，且aii 0 (i=1,2,n)则有则有第50页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法写成迭代格式：写成迭代格式：(2.5)或或 (2.6)称称(2.5)或或(2.3)为分量形式雅可比迭代法为分量形式雅可比迭代法(Jacobi).第51页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法又又(*)写成矩阵形式：写成矩阵形式：Dx=Lx+Ux+b 其中其中D L U=Ax=D-1(L+U)x+D-1b令令BJ=D-1(L+U)，fJ=D-1b，则有，则有x=BJx+fJ第52页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法Dx=Lx+Ux+b 其中其中D L U=Ax=D-1(L+U)x+D-1b令令BJ=D-1(L+U)，fJ=D-1b，则有，则有x=BJx+fJ即有即有Jacobi迭代矩阵形式：迭代矩阵形式：x(k+1)=BJx(k)+fJ (2.8)第53页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法例例4 将方程组将方程组写成写成Jacobi迭代格式迭代格式(2.5)：第54页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法其矩阵形式：其矩阵形式：第55页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法其矩阵形式：其矩阵形式：取初始向量取初始向量x(0)=(0,0,0)T进行迭代进行迭代.(P224).第56页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法1.雅可比迭代法雅可比迭代法取初始向量取初始向量x(0)=(0,0,0)T进行迭代进行迭代.第57页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法2.Gauss-Seidel迭代迭代 考虑考虑Jacobi迭代分量式：迭代分量式：通常计算值通常计算值xj(k+1)比前一步计算值比前一步计算值xj(k)更准确更准确.取取 (2.9)称称(2.9)为高斯为高斯赛德尔迭代赛德尔迭代(分量式分量式).第58页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法2.Gauss-Seidel迭代迭代考虑考虑Jacobi迭代矩阵式：迭代矩阵式：x(k+1)=D-1(L+U)x(k)+D-1b Dx(k+1)=Lx(k)+Ux(k)+b取取Dx(k+1)=Lx(k+1)+Ux(k)+b(D L)x(k+1)=Ux(k)+b x(k+1)=(D L)-1Ux(k)+(D L)-1b第59页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法2.Gauss-Seidel迭代迭代取取Dx(k+1)=Lx(k+1)+Ux(k)+b(D L)x(k+1)=Ux(k)+b x(k+1)=(D L)-1Ux(k)+(D L)-1b令令BG=(D L)-1U，fG=(D L)-1Ub，则则有有x(k+1)=BGx(k)+fG (2.10)称称(2.10)为为GS迭代矩阵式迭代矩阵式.第60页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法2.Gauss-Seidel迭代迭代例例5 在例在例4中使用中使用Gauss-Seidel迭代：迭代：迭代公式：迭代公式：令令BG=(D L)-1U，fG=(D L)-1Ub，则有则有x(k+1)=BGx(k)+fG第61页3.3 解线性方程组迭代法解线性方程组迭代法3.3.1 简单迭代法简单迭代法2.Gauss-Seidel迭代迭代迭代公式：迭代公式：第62页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性 迭迭代代求求解解过过程程为为求求极极限限过过程程，这这个个极极限限过过程程收收敛敛性性就是迭代法收敛与发散问题就是迭代法收敛与发散问题.定理定理2.2 迭代法：迭代法：x(k+1)=Bx(k)+f 收敛收敛 (B)1证实证实(略略).要要检检验验一一个个矩矩阵阵谱谱半半径径小小于于1比比较较困困难难，所所以以我我们们希希望望用别方法判断收敛性用别方法判断收敛性 第63页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性定理定理2.3 若若|B|1，则，则x(k+1)=Bx(k)+f 收敛收敛.且且其中其中|B|为为B任一算子范数任一算子范数.证实：因为证实：因为(B)|B|1，所以，所以x(k+1)=Bx(k)+f 收敛收敛.又又因因为为x*x(k+1)=B(x*x(k)=B(x*x(k+1)+x(k+1)x(k)|x*x(k+1)|B|(|x*x(k+1)|+|x(k+1)x(k)|)第64页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性定理定理2.3 若若|B|1，则，则x(k+1)=Bx(k)+f 收敛收敛.且且其中其中|B|为为B任一算子范数任一算子范数.证证实实：|x*x(k+1)|B|(|x*x(k+1)|+|x(k+1)x(k)|)第65页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性定理定理2.3 若若|B|1，则，则x(k+1)=Bx(k)+f 收敛收敛.且且其中其中|B|为为B任一算子范数任一算子范数.证证实实：又又x(k+1)x(k)=B(x(k)x(k-1)=Bk(x(1)x(0)|x(k+1)x(k)|B|k|x(1)x(0)|第66页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性定理定理2.3 若若|B|1，|BJ|1=4 1第68页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例例7 设设 问使用问使用J迭代和迭代和GS迭代求解是否收敛迭代求解是否收敛.解解 考虑谱半径考虑谱半径第69页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例例7 设设 问使用问使用J迭代和迭代和GS迭代求解是否收敛迭代求解是否收敛.解解 考虑谱半径考虑谱半径 (BJ)=0 1，发散，发散.第73页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性注：两种迭代格式：注：两种迭代格式：J迭代收敛，迭代收敛，GS发散发散;T14(2)J迭代发散，迭代发散，GS收敛收敛;T14(1)第74页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例：设方程组例：设方程组Ax=b，其中，其中求求J迭代法与迭代法与GS迭代法收敛充要条件。迭代法收敛充要条件。解：雅克比迭代矩阵：解：雅克比迭代矩阵：第75页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例例：设设方方程程组组Ax=b，求求J迭迭代代法法与与GS迭迭代代法法收收敛充要条件。敛充要条件。解：雅克比迭代矩阵：解：雅克比迭代矩阵：所以，雅克比迭代收敛充要条件是所以，雅克比迭代收敛充要条件是|ab|100/3.第76页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例例：设设方方程程组组Ax=b，求求J迭迭代代法法与与GS迭迭代代法法收收敛充要条件。敛充要条件。解：高斯解：高斯赛德尔迭代矩阵：赛德尔迭代矩阵：第77页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例例：设设方方程程组组Ax=b，求求J迭迭代代法法与与GS迭迭代代法法收收敛敛充要条件。充要条件。解：高斯解：高斯赛德尔迭代矩阵：赛德尔迭代矩阵：第78页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性例例：设设方方程程组组Ax=b，求求J迭迭代代法法与与GS迭迭代代法法收收敛敛充要条件。充要条件。解：高斯解：高斯赛德尔迭代：赛德尔迭代：=0，第79页3.3 解线性方程组迭代法解线性方程组迭代法3.3.2 迭代收敛性迭代收敛性作业：作业：P235.9 P233 12，14.第80页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组定义定义2.1 设设A=(aij)n n满足：满足：(2.14)则称则称A为为(行行)对角占优阵对角占优阵.注：注：若若则称则称A为为(列列)对角占优阵对角占优阵.若若(2.14)中中严严格格不不等等式式成成立立，则则称称A为为严严格格(行行，列列)对角占优阵对角占优阵.统称为严格占优阵统称为严格占优阵.能够证实严格占优阵必可逆，即能够证实严格占优阵必可逆，即|A|0第81页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组定定理理2.4 设设Ax=b若若A为为严严格格(行行)对对角角占占优优，则则J迭代和迭代和GS迭代均收敛迭代均收敛.证实证实(1)第82页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组定定理理2.4 设设Ax=b若若A为为严严格格(行行)对对角角占占优优，则则J迭代和迭代和GS迭代均收敛迭代均收敛.证实证实(1)所以所以J-迭代收敛。迭代收敛。第83页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组定定理理2.4 设设Ax=b若若A为为严严格格(行行)对对角角占占优优，则则J迭代和迭代和GS迭代均收敛迭代均收敛.证实证实(2)BG=(D L)-1U (欲证欲证(BG)1)因为因为 I BG=I (D L)-1U =(D L)-1(D L)U0=|I BG|=|(D L)-1|(D L)U|(D L)U|=0第84页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组定定理理2.4 设设Ax=b若若A为为严严格格(行行)对对角角占占优优，则则J迭代和迭代和GS迭代均收敛迭代均收敛.证实证实(2)BG=(D L)-1U (欲证欲证(BG)1)|(D L)U|=0令令则则|G|=0.第85页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组定定理理2.4 设设Ax=b若若A为为严严格格(行行)对对角角占占优优，则则J迭代和迭代和GS迭代均收敛迭代均收敛.证实证实(2)BG=(D L)-1U (欲证欲证(BG)1)令令则则|G|=0.若若|1，则，则 G严格对角占优严格对角占优G可逆，矛盾！可逆，矛盾！第86页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组注注：(1)若若将将方方程程组组经经初初等等行行变变换换化化为为同同解解方方程程组组，其系数矩阵严格对角占优，则可使迭代法收敛。其系数矩阵严格对角占优，则可使迭代法收敛。如方程组：如方程组：此时，矩阵化为严格对角占优阵。此时，矩阵化为严格对角占优阵。第87页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 一类特殊方程组注：注：(2)若若|BJ|1，则，则GS迭代收敛迭代收敛由由|BJ|1可知可知即即A严格对角占优，严格对角占优，两种迭代都收敛两种迭代都收敛.第88页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法超超松松弛弛迭迭代代法法(Successive Over Relaxation Method)是是Gauss-seidel迭迭代代法法改改进进，是是解解大大型型稀稀疏疏矩矩阵阵线线性性方方程组有效方法。程组有效方法。第89页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法将将Gauss-seidel迭代法改写为迭代法改写为增加一个因子增加一个因子，希望以下迭代过程，希望以下迭代过程收敛更加快收敛更加快这这种种迭迭代代法法方方法法称称为为超超松松弛弛迭迭代代法法，简简称称为为SOR方方法法，其中其中 称为松弛因子。称为松弛因子。第90页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法迭代过程迭代过程称为超松弛迭代法称为超松弛迭代法,简称为简称为SOR法，法，称为松弛因子。称为松弛因子。下面我们推导下面我们推导SOR方法矩阵表示形式。由上式得方法矩阵表示形式。由上式得(i=1,2,n)，用矩阵形式表示为，用矩阵形式表示为Dx(k+1)=(1 )Dx(k)+(b+Lx(k+1)+Ux(k)第91页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法(i=1,2,n)，用矩阵形式表示为，用矩阵形式表示为Dx(k+1)=(1 )Dx(k)+(b+Lx(k+1)+Ux(k)从而有从而有(D L)x(k+1)=(1 )D+U x(k)+b即即x(k+1)=(D L)-1(1 )D+U x(k)+(D L)-1b第92页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法x(k+1)=(D L)-1(1 )D+U x(k)+(D L)-1b于是于是SOR方法矩阵表示形式为方法矩阵表示形式为x(k+1)=B x(k)+f 其其中中B =(D L)-1(1 )D+U称称为为超超松松弛弛迭迭代代矩矩阵，阵，f =(D L)-1b第93页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法例11：用：用SOR方法求下面线性方程组近似解。方法求下面线性方程组近似解。解：该该方方程程组组准准确确解解为为x*=(2,1,-1)T。若若用用SOR方方法法求求解，其迭代公式为解，其迭代公式为x(k+1)=(D L)-1(1 )D+U x(k)+(D L)-1b第94页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法解：该该方方程程组组准准确确解解为为x*=(2,1,-1)T。SOR法法迭迭代代公公式式为为取取 =1.43,x(0)=(0,0,0)T,则计算结果为则计算结果为若取若取 =1,即用即用G-S迭代法迭代法,仍取仍取x(0)=(0,0,0)T 则计算一样精度结果则计算一样精度结果,需要迭代需要迭代110次以上。次以上。第95页3.3 解线性方程组迭代法解线性方程组迭代法3.3.3 超松弛迭代法超松弛迭代法SOR方方法法也也是是一一阶阶定定常常迭迭代代法法,故故一一样样能能够够用用定定理理5-8讨论其收敛性。讨论其收敛性。但但由由上上例例引引发发我我们们注注意意是是,改改变变松松弛弛因因子子值值,不不但但影影响响迭代过程收敛速度迭代过程收敛速度,而且还会影响迭代过程收敛性。而且还会影响迭代过程收敛性。对此我们有以下定理对此我们有以下定理:定理9：若若线线性性方方程程组组Ax=b系系数数矩矩阵阵A=(aij)nn主主对对角角元元素素aii均均不不为为0，则则SOR法法迭迭代代过过程程收收敛敛必必要要条条件件是是0 2。第96页