![点击分享此内容可以赚币 分享](/master/images/share_but.png)
计算方法解线性方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx
《计算方法解线性方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《计算方法解线性方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx(96页珍藏版)》请在咨信网上搜索。
1、数 值 分 析第第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|
2、=|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、念基本概念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|)
4、.第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 向量与矩阵范数向量与矩
5、阵范数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,|为向量范数为向量范数.称称 为为矩
6、矩阵阵A算算子子范范数数.(诱诱导导范范数数).注:注:能能够够证证实实算算子子范范数数满满足足矩矩阵阵范范数数4个个条条件件.故故为为矩矩阵阵范数范数.矩阵范数不一定都是算子范数,如矩阵范数不一定都是算子范数,如F-范数范数.第11页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵 算子范数与向量范数相容算子范数与向量范数相容.()第12页3.2 基本概念基本概念3.2.1 向量与矩阵范数向量与矩阵范数2.矩阵范数矩阵范数只考虑只考虑Rn中方阵中方阵常见算子范数有:常见算子范数有:2范数范数.其中其中 max(ATA)为矩阵为矩
7、阵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不易计算但有用
8、不易计算但有用.第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不
9、是不是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
10、|=|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非奇异,非奇异,|为算子
11、范数,则称为算子范数,则称 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、mi
12、n分别是分别是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非非奇奇异异.若若C
13、ond(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)判断方法判断方法直观判断直观判断 用主元消去法求解时出现小主元;用主元消去法求解时出现小主元;一些行、列几乎线性相关一些行、列
14、几乎线性相关 A元素间数量级很大,且无规律元素间数量级很大,且无规律若方程组出现上述情况之一,方程组有可能若方程组出现上述情况之一,方程组有可能“病态病态”。第27页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍4.病态方程组病态方程组(2)处理办法处理办法对对于于“病病态态”方方程程组组求求解解,需需要要采采取取特特殊殊处处理理或或专专用用方法:方法:提提升升原原始始数数据据和和运运算算精精度度,如如原原始始数数据据和和运运算算采采取取双精度等。双精度等。用用适适当当方方法法改改进进原原始始模模型型性性态态,如如对对矩矩阵阵进进行行“预预处理处理”以降低其条件数。以降低其条件数
15、。第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,使用列主元素消去法求解:,使
16、用列主元素消去法求解:回代:回代: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位有效数字求解。位
17、有效数字求解。解:解:(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左左
18、端端,观观察察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
19、基本概念基本概念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准确解和近似解准确解和近似解,残差
20、向量残差向量 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可靠性。可靠性。第
21、38页3.2 基本概念基本概念3.2.2 误差分析介绍误差分析介绍5.迭代改进法迭代改进法采采取取高高精精度度计计算算方方法法(如如例例主主元元素素消消去去法法)与与高高精精度度算算术术运运算算(如如双双精精度度),即即使使能能够够提提升升方方程程组组近近似似解解准准确确程程度度,不不过过对对于于病病态态方方程程组组也也不不一一定定能能取取得得高高精精度度近近似解似解,而且方程组病态越严重而且方程组病态越严重,求解越困难。求解越困难。当当用用某某种种方方法法求求得得方方程程组组Ax=b(|A|0且且b0)某某个个近近似似解解x(1)后后,若若还还未未到到达达精精度度要要求求,可可采采取取下下述
22、述改改进进迭迭代代过程取得较准确近似解过程取得较准确近似解.第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
23、(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
24、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 (精精度
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算方法 线性方程组 解法 公共课 一等奖 全国 获奖 课件
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。