电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本
换一换
首页 金锄头文库 > 资源分类 > PPT文档下载
分享到微信 分享到微博 分享到QQ空间

现代数值分析课件第2章线性方程组的直接法

  • 资源ID:91080474       资源大小:957KB        全文页数:54页
  • 资源格式: PPT        下载积分:10金贝
快捷下载 游客一键下载
账号登录下载
微信登录下载
三方登录下载: 微信开放平台登录   支付宝登录   QQ登录  
二维码
微信扫一扫登录
下载资源需要10金贝
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

 
账号:
密码:
验证码:   换一换
  忘记密码?
    
1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
下载须知 | 常见问题汇总

现代数值分析课件第2章线性方程组的直接法

第二章 解线性方程组的直接方法,高斯(Gauss)消元法 矩阵的三角分解法 矩阵的条件数与方程组的性态,解线性方程组的两类方法: 直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!) 迭代法:从解的某个近似值出发,通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解),一、高斯消去法,§2.1 高斯消去法和选主元高斯消去法,将增广矩阵的第 i 行 + li1 第1行,得到:,消去过程:,第一步:设 ,计算因子,第k步:设 ,计算因子 且计算,共进行 n 1步,得到,定理2.1:若A的所有顺序主子式 均不为0,则高斯消去法能顺序进行消元,得到唯一解。,回代过程:,例2.1.1 高斯消元法,x1 = -13 x2 = 8 x3 = 2,二、选主元消去法,为避免这种情况的发生, 可通过交换方程的次序,选取绝对值大的元素作主元. 基于这种思想导出了主元素法,在高斯消去法消去过程中可能出现 的情况, 这时高斯消去法将无法进行;即使主元素 但很小,其作除数 ,也会导致其它元素数量级的严 重增长和舍入误差的扩散,列主元消去法,在第k步消元前,在系数矩阵第k列的对角线以下的元素中找出绝对值最大的元。,列主元Gauss消去法保证了lik1 ( i = k +1, k +2,,n ).,例2.1.2 列主元法,第一列中绝对值最大是10,取10为主元,n阶方程组第k 轮消元时,选第k 列的后( n k + 1 )个元素中绝对值最大作主元。,x3=6.2/6.2=1,x2=(2.5-5x3)/2.5= -1,x1=(7+7x2-0x3)/10=0,x1=0 x2= -1 x3=1,第二列的后两个数中选出主元 2.5,全主元消去法,在第k 步消去前, 在系数矩阵右下角的n- k+1阶主子阵中,选绝对值最大的元素作为主元素。,(1) If p k then 交换第 k 行与第p 行; If q k then 交换第 k 列与第 q 列;,(2) 消元,注:列交换改变了xi 的顺序,须记录交换次序,解完后再换回来。,例2.1.3 全主元解方程组:, 运算量 (Amount of Computation),(1)用克莱姆(Cramer)法则求解n阶线性方程组,每个行列式由n!项相加, 而每项包含了n个因子相乘,乘法运算次数为(n-1) n!次.,仅考虑乘(除)法运算, 计算解向量包括计算n+1个行列式和n次除法运算, 乘(除)法运算次数 N=(n+1)(n-1)n!+n.,(2) 高斯消去法:,在第1个消去步, 计算 li1(i=2,3,n), 有n-1次除法运算. 使aij(1)变为 aij(2) 以及使bi(1)变为bi(2)有n(n-1)次乘法运算 和 n(n-1)次加(减)法运算.,在第k个消去步, 有n-k次除法运算, (n-k+1)(n-k)次乘法运算和相同的加(减)法运算.,首先统计乘法运算总次数. 将每个消去步的乘法运算次数相加,有 n(n-1)+(n-1)(n-2)+3×2+2×1=n(n-1)(n+1)/3,加(减)法运算次数总计也为n(n-1)(n+1)/3. 除法运算总次数为n+(n-1)+1= n(n-1)/2,回代过程的计算,除法运算次数为n次. 乘法运算和加法运算的总次数 都为n+(n-1)+1= n(n-1)/2次,Gauss消去法(顺序消去法) 除法运算次数为: n(n-1)/2+n= n(n+1)/2, 乘法运算次数为: n(n-1)(n+1)/3+n(n-1)/2= n(n-1)(2n+5)/6, 加(减)法运算次数为: n(n-1)(2n+5)/6,通常也说Gauss消去法的运算次数与n3同阶,记为O(n3),全主远消去法:,比 高斯消去法多出 , 保证稳定, 但费时.,列主元消去法:,比 高斯消去法只多出 的 , 略省时.,§2.2 三角分解法, 高斯消元法的矩阵形式:L U 分解,每一步消去过程相当于左乘初等变换矩阵L1,A 的 LU 分解 ( LU factorization ),定理2.2.1: 若A的所有顺序主子式 均不为0,则 A 的 LU 分解唯一(其中 L 为单位下三角阵)。,证明:由§1中定理可知,LU 分解存在。下面证明唯一性。,若不唯一,则可设 A = L1U1 = L2U2 ,推出,上三角矩阵,对角线上为1的下三角矩阵,注: (1) L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解 (2)L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。, Doolittle分解法 :,一般计算公式,L第一行乘U 每一列: a11= u11, ···, a1n= u1n,L每一行乘U 第一列: a21 = l 21u11, ··· , an1 = ln1u11,l 21u12+ u22=a22, ··· , l21u1n+ u2n=a2n,l31u12+ l32u22=a32, ··· , ln1u12+ ln2u22=an2,L第二行乘U 每一列:,L每一行乘U 第二列:,注:该公式的特点:U 的元素按行求, L 的元素按列求; 先求 U 的第k 行, 再求 L 的第k 列, U 和 L 一行一列交叉计算. 计算量与 Gauss 消去法同.,一般地:,LU 分解求解线性方程组,例2.2.1 求矩阵的Doolittle分解, 求解正定方程组的Cholesky方法(平方根法),回顾:对称正定阵A的几个重要性质 (1)A1 亦对称正定,且 aii 0 (2)A 的顺序主子阵 Ak 亦对称正定 (3)A 的特征值 i 0 (4)A 的全部顺序主子式 det ( Ak ) 0,定理2.2.2: 设矩阵A对称正定,则存在唯一的对角元全为正的下三角阵G 使得 AGGT,计算格式为:,平方根法的优点: (1) 乘除法运算量比一般 LU分解要小得多; 不选主元的平方根法是数值稳定的。 缺点:有n 个开方运算。,为避免过多的开方运算,在更多情况下是将A分解 为:A=LDLT,其中L为下三角,D为对角阵。事实上, 由前面的讨论可知:A=LU,其中L 为单位下三角阵, U为上三角阵。记U的元素为uij,D=diag(uii),由于A 对称正定,必有uii0(i=1,2,n),所以U=DU*,其中,注:将矩阵 A 作Doolittle分解或Crout分解, 由矩阵乘 法可得 A 的 LDLT 分解。, 解三对角方程组的追赶法,定理2.2.3:若 A 为对角占优 的三对角阵,且满足 则方程组有唯一的LU分解。,第一步 : 对 A 作Doolittle 分解,追赶法公式的推导:(以四阶为例),该过程称为“追”的过程。,该过程称为“赶”的过程。,一般情形的三对角方程组计算公式:,计算次序为:,最 好 牢记,直接比较等式两边的元素,可得到计算公式:,第一步: 对 A 作Crout 分解:,注: 也可通过对 A 作Crout 分解进行求解,第二步: 追即解:,第三步: 赶即解:,§ 2.3 矩阵的条件数与方程组的性态,预备知识范数, 向量范数 ( vector norms ),对任意,定义1:Rn空间的向量范数 | · | ,对任意 满足下列条件,常用向量范数:, 向量 的Lp范数定义为:,主要性质,性质1:-x=x,性质2:x-yx-y,性质3: 向量范数x是Rn上向量x的连续函数.,范数等价:设·A 和·B是R上任意两种范数,若存在 常数 C1、C2 0 使得 ,则称 ·A 和·B 等价。,定理1,Rn 上一切范数都等价。,向量 x 的1范数 向量 x 的2范数 向量 x 的范数, 矩阵范数 ( matrix norms ),定义3:对任意 ,称| · | 为Rmn空间的矩阵范数, 指| · |满足(1)-(3):,对任意,(4) | AB | | A | · | B |,若还满足(4),称为相容的矩阵范数,相容性,(1)矩阵范数与矩阵范数的相容性: ABAB,(2)矩阵范数与向量范数相容性,常用的算子范数:,由向量范数 | · |p 导出关于矩阵 A Rnn 的p范数:,则,注: 称为A的谱半径。,证明:,由算子范数的相容性,得到,将任意一个特征根 所对应的特征向量 代入,命题,若A对称,则有:,证明:,若 是 A 的一个特征根,则2 必是 A2 的特征根。,又:对称矩阵的特征根为实数,即 2(A) 为非负实数,故得证。,对某个 A 的特征根 成立,定理3,若矩阵 A 对某个算子范数满足 |A| 1,则必有,.,可逆;,.,证明:, 若不然,则 有非零解,即存在非零向量 使得, 病态方程组线性方程组的性态(误差分析) ( Error Analysis for Linear system of Equations ),例:方程组,有精确解(1,1),对系数矩阵和右端常熟项作微小变化,则,的解为(10, -2). 扰动后方程组的解面目全非。 Def :如果方程组 Ax = b 中, 矩阵A和右端项 b 的变化|A|和 |b |微小, 引起解向量 x 的变化|x |很大, 则称A为关于解 方程组和矩阵求逆的病态矩阵, 称相应的方程组为病态方程组. 反之, 如果|A|和|b |微小, |x |也微小, 则称 A为良态矩 阵, Ax=b 为良态方程组.,思考:求解 时, A 和 的误差对解 有何影响?, 设 A 精确, 有误差 ,得到的解为 ,即,绝对误差放大因子,又,相对误差放大因子,矩阵和方程组病态程度的刻划, 设 精确,A有误差 ,得到的解为 ,即,(只要 A充分小,使得,常用条件数有:,cond 2(A),特别地,若 A 对称,则,3.4.2 矩阵的条件数,Def:设 存在,则称数 cond ( A )=| | A | 为矩阵 A 的 条件数,其中 是矩阵的算子范数。,1-条件数,-条件数,2-条件数,例:Hilbert 阵,注:现在用Matlab数学软件可以很方便求矩阵的条件数!,说明: 设线性方程组的系数矩阵是非奇异的, 如果cond(A)越大, 就称这个方程组越病态. 反之, cond(A) 越小, 就称这个方程组越良态.,若 A 对称正定,则,其中 分别为A的按模最大和最小的特征值。,例1:求矩阵 的条件数,例2: 设,求,

注意事项

本文(现代数值分析课件第2章线性方程组的直接法)为本站会员(E****)主动上传,金锄头文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读金锄头文库的“版权提示”【网址:https://www.jinchutou.com/h-59.html】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.