您好、欢迎来到现金彩票网!
当前位置:双彩网 > 线性归结 >

《计算方法》课件第二章 线性方程组直接解法ppt

发布时间:2019-06-19 20:54 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  主要内容 §2.0 概述 §2.1 消去法 一、Gauss消去法 二、Gauss列主元消去法 §2.2 直接三角分解法 一、消去法与系数矩阵的三角分解 二、Doolittle分解 习题二 答案与提示 §2.0 概述 基本数学问题描述 实际用途与特征 传统理论解法&使用价值 直接法&迭代法优缺点分析 直接法的基本思路 方法的理论依据 三角形方程组的解法* 下三角形方程组LX=b的求解过程 上三角形方程组UX=d的求解过程 计算量分析 基本数学问题描述 实际用途与特征 传统理论解法&使用价值 直接法&迭代法优缺点分析 直接法 由于存储容量限制,仅适于系数矩阵阶数不高问题 其工作量小 精确度较高 但程序复杂 迭代法 主要用于某些高阶问题(特别是椭圆型微分方程边值求解中有着广泛的应用) 一般来说,其程序比较简单,但工作量有时较大 实际计算时,应根据问题的特点和要求以及使用计算机的情况,决定方法的取舍 直接法的基本思路 方法的理论依据 三角形方程组的解法 下三角形方程组LX=b的求解过程 上三角形方程组UX=d的求解过程 计算量分析(单位:次) §2.1 消去法 一、Gauss消去法 消去法(n=4)的算法推导 Gauss消去法一般算法的推导 消去法的算法流程图 二、Gauss列主元消去法 Gauss列主元消去法计算步骤 一、Gauss消去法 消去法(n=4)的算法推导 第1次消去过程&算法归结 第2次消去过程&算法归结 第3次消去过程&算法归结 回代过程(n=4) Gauss消去法一般算法的推导 消去过程结果&算法归结 回代过程算法归结 消去法的算法流程图(p24) 二、Gauss列主元消去法 Gauss列主元消去法计算步骤: [补充例题01] §2.2 直接三角分解法 一、消去法与系数矩阵的三角分解 A矩阵的LU分解的判别定理 方法分析 二、Doolittle分解 算法构建 Doolittle分解的优点 一、消去法与系数矩阵的三角分解 A矩阵的LU分解的判别定理 方法分析 二、Doolittle分解 算法构建 Doolittle分解的优点 逆矩阵的计算方法 对角占优矩阵 Doolittle分解有许多优点: 因为计算过程中不记录中间结果,计算没有浪费,所以又称它为“紧凑消元法”。 计算量 因为进行大量形式为的内积运算,若使用“双倍位累加器”计算,并作最后一次舍入,可提高解的的精度; 节省内存,因为分解A完毕后,aij 的位置不用了,正好可以存入L、U的元素。如下图。 对于求解右端项不同的方程组,LU分解的结果可以重复使用,可以大大减少计算量。 返回节 返回章 习题二 1.利用①Gauss消去法,②Gauss列主元法解方程组 2.用Gauss列主元法求解方程组并求出系数矩阵A的行列式det(A)的值。 3.设 A=(aij),a11≠0,经过一步Gauss消去法得到 试证 (1)若A对称,则A 1对称; (2)若A严格对角占优,则A1严格对角占优。 4.设 利用第1题中消元过程求出L和U矩阵,并验证 A=LU。 5.什么时候Gauss消去法会出现数值不稳定?如何克服? 6.用Doolittle分解法再解第1题。 返回章 习题二答案与提示 1.方程组解=(2,-1,2,-1)T 2.方程组解=(1,2,3)T,det(A)=-66 ? 4. 提示: ,计算出U矩阵后,利用LU=A进行验算。 ? 5.什么时候Gauss消去法会出现数值不稳定?如何克服? 参见例2.2 返回章 [补充内容01] 方法1: 方法2: 其中: 返回引用 如果线性方程组AX=b的系数矩阵A具有某种特殊性质(如对称正定、对角占优等),则可从A本身直接得出某些迭代法收敛性结论。 定义3.1 如果矩阵A满足条件 则称A是严格对角占优阵; 如果矩阵A满足条件 且其中至少有一个不等式严格成立,则称A是弱对角占优阵。 返回引用 第k次消元---- 计算消元系数lij共(n-k)个,进行(n-k)次除法运算; 每一行计算增广矩阵中(n-k+1)个元素,每个元素需1次乘法运算; 共需(n-k)(n-k+1)次乘法运算; 而回代过程中,求 xk 需(n-k)次乘法运算,1次除法运算。 所以,以上过程所需乘(除)法运算次数为: 如果仍使用每秒完成 104 次乘法运算的计算机,求解一个30阶的线性方程组,用Gauss消去法仅需 0.9 秒左右机时。 很显然,Gauss消去法的计算效率是相当高的。 Gauss消去法中的消元过程,是在每次 的前提下进行的,这往往是得不到保证的。即使保证了每次消去时 ,但是如果它的绝对值比起同列其它元素的绝对值甚小时,计算误差就会扩大。 开始 输入 A,b,n k=1 回代 过 程 Con. xn= bn /ann i= n - 1 xi= xi /aii i=1 输出x=(x1 , x2 ,… ,xn ) 结束 xi= bi j= i + 1 xi= xi – aij xj j=n j=j+1 i = i-1 消 元 过 程 akk=0 i=k+1 i=n k=k+1 k=n ann=0 Con. lik= aik /akk bi= bi -lik bk j=k+1 aij = aij - lik akj j=n j=j+1 i=i+1 算法失败 方程无唯一解 Y Y Y Y N 返回节 返回章 Y N N N N N Y Y N Y Y 其中: a11=0,导致l21=1/0计算出现溢出,算法失败 但det (A)>0,方程组存在唯一解 解决这个问题的办法之一就是: 交换第一个方程和第二个方程,得到一个等价的方程组 其消元因子不为零,消去法就能顺利进行了 Gauss消去法中的消元过程,是在每次 的前提下进行的,这往往是得不到保证的。 例如 对方程组 另外,即使保证了每次消去时 ,但是如果它的绝对值比起同列其它元素的绝对值甚小时,计算误差就会扩大。 在具有四位标准浮点数(十进制)计算机上,用Gauss消去求解法,求解下列线性方程组 解: 回代 例2.2 (注意:教材中P21-P23排版有错误,应以课件/电子教案为准) 现在交换两个方程的位置,求解下列方程组 回代 例2.2的四位有效数字的精确解为: x1=0.8109 x2=9.998 究其原因 (误差原因分析) : 列主元:就是所消去列中绝对值最大的元素 可见 前一方法误差甚大 后一解法较好 ?后者用绝对值大的数去除较小的数,因而能缩小误差 后一种方法就是Gauss列主元消去法 ?前者在消去过程中,用绝对值小的数 去除 大的数 ,因而扩大误差 (1) 消元过程 ① 选列主元apk ,使得 akj ? apj (j=k,k+1,…,n) bk ? bp ④ 消元 对 i=k+1,…,n 1)lik = aik / akk 2)bi = bi - lik bk 3)aij = aij - lik akj ( j=k+1,…,n) 对 k=1, 2, …, n-1 ③ 若p=k ,转④,否则换行: ② 若 apk =0,则无唯一解,停止计算。 (2)回代求解 ①若ann =0 ,则无唯一解,停止计算。 ② (3) 输出 Gauss消去法的改进方法很多。 感兴趣的读者可以查阅参考书[1],[2]。 其中既简便又广为利用的方法当属列主元法。 用Gauss列主元消去法解下列方程组。(其中画方框者为列主元) [解] (2) (3) 回代, [解毕] 返回节 返回章 在上节4阶线性方程组消去过程中,第一次消去得到 这个矩阵是由增广矩阵经过行初等变换得出的。 由初等行变换性质知,这就相当于用方阵 左乘得到的,即有: 同理,第二次消元相当于用方阵 左乘 , 即: 最后,第三次消元相当于用方阵 左乘 , 即: 若记: 我们有 或 容易知道: 所以 [逆矩阵求解方法] 再记 Y=b(3) U=A(3) (2-6) 则有 由矩阵分块乘法可知 A=LU (2-7) LY =b (2-8) 式(2-7)表明,系数矩阵A 可分解为一个下三角矩阵L 与一个上三角矩阵U 的乘积。 由上述分析可以看出,式(2-7)成立的充分条件为:aii(i-1)≠0 ( i =1,2,…,n-1 ),由矩阵分块乘积,有: 返回引用 因此,Ai = Li Ui 即Ai 的顺序主子式 Di = Ai = Li ·Ui =Ui = a11(0)…ai i(i-1), 若规定D0 =1,则 aii(i-1)= Di / Di-1 ( i=1, 2 ,…, n-1 )。 这就是作矩阵LU分解。 我们将这一结论用定理来叙述: 定理2.1 (矩阵的LU分解)设A 为n 阶方阵,如果A 的顺序主子式 Di≠0 (i=1,2,…,n-1), 则A 可以分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积,且这种分解是唯一的。 由Gauss消去法即可得到定理2.1的存在性,关于唯一性的证明,应分A为非奇异(?A??0)和奇异两种情况,证明留给读者自己完成。 返回引用 以定理2.1为基础,再利用附录2.7中的知识,易证明下面两个更有实际价值的判别定理。 定理2.2 A 对称正定(A 的顺序主子式 Di0 ,i=1,2,…,n-1),则A 可作LU分解,且这种分解是唯一的。 定理2.3 A 严格对角占优,则A 可作LU分解,且这种分解是唯一的。 结论: 只要判断出矩阵A 是对称正定或严格对角占优, 则对原方程组不必任何处理, 可直接用Gauss消去法对矩阵A 作LU分解。 思路: 若判断了方阵A可做LU分解,就可按Gauss消去法。 可求出L和U矩阵解; 并将L和U矩阵的元素保留在A矩阵原来位置上。 仍以 n=4 为例。 例2.3 将下面矩阵A作LU分解 解 返回引用 最后得到 返回引用 例2.3 矩阵A作LU分解结果 由(2-2)式AX=b和 (2-7)式A=LU可以得到 AX = LUX = b 再与(2-8)式LY=b进行对比,可以得到 UX = Y 进而,我们可以得到与原方程等价的两个特殊的联立方程组: 利用(2-9)式,可以很容易地得到方程的解。 (2-9) 例2.4 利用LU分解求解矩阵方程 解: 由例2.3,我们得到了系数矩阵A的LU分解 求解 LY=b,即 得 y1=7 y2=5-2y1=5-2×7=-9 y3=33+3y1+2y2=33+3×7+2×(-9)=36 y4=-28-4y1-2y2 +y3=-28-4×7-2×(-9)+36=-2 求解 UX=Y,即 得 x4=(-2)/(-1)=2 x3=(36-6x4)/12=(36-6×2)/12=2 x2=(-9-3x3+5x4)/(-5)=-(-9-3×2+5×2)/5=1 x1=7-2x2-3x3+x4=7-2×1-3×2+2=1 即 X=(1,1,2,2)T 为方程组的解。 如果一个线性方程组可以利用Gauss消去法求解,则 存在矩阵三角分解 系数矩阵经过(n-1)次消去后,就得到矩阵U,且 A=LU 这样,我们可以轻松地得到矩阵A的行列式 det(A)=det(LU) =det(L)det(U) 应注意到,L 为单位下三角矩阵,有det(L)=1,U为上三角矩阵,所以有 这样,就可以利用Gauss消去法,求得矩阵行列式值。 虽然矩阵A 是非奇异的(即?A??0),但 以A 为系数矩阵的线性方程组,并不都存在三角分解 也就是说,Gauss 消去法可能失败 这时,我们仍可以利用Gauss 列主元消去法,求得方程组的解。 使用Gauss 列主元消去法消元过程,我们也可以得到一个上三角矩阵U, 我们用m 表示在列主元消去法消元过程中主元换行的次数,则有: det(A)=(-1)m det(U)。 请读者自行写出利用Gauss列主元消去法求矩阵行列式的算法步骤。 返回节 如果矩阵A满足定理2.1的条件[A 的顺序主子式 Di≠0 (i=1,2,…,n-1)],当然可以使用Gauss消去法得到A的LU分解。 另外, 我们可以按矩阵相等的定义和矩阵乘法规则,用待定系数法,推出直接由系数矩阵A计算L和U的算法。令: 第一步:LU分解 比较式(2-6)A=LU,即 比较式(2-10)两端第1行元素,得 u1j=a1j (j=1,2,…,n) (2-11) 再比较式(2-10)两端第1列元素,得 li1 u11 =ai1 (i=2,3,…,n) 返回引用 即 li1 = ai1/ u11 (i=2,3,…,n) 假定已完成前r –1步分解,则U的前r –1 行和L的前r – 1列元素均为已知量。 考虑第 r 步分解,先比较式(2-10)两端第 r 行元素,就会有 于是对于 r =2,3,…,n 的第 r 行元素,有 再比较式(2-10)两端第 r 列元素,有 于是对于 r =2,3,…,n-1的第 r 列元素,有 上述LU分解方法也称Doolittle分解。 第二步:求解 LY=b 第三步:求解 UX=Y * * * * 第二章 线性方程组直接解法 大连海事大学 信息科学与技术学院 宁博 《计算方法》课程讲义课件 返首页 本章要解决的数学问题是:求线性方程组 的数值解。 式(2-1)用矩阵形式可简记为 AX=b (2-2) 其中: 返回节 返回引用 线性方程组的解法有广泛的应用。 许多实际问题都归结于线性方程组的求解 在数值方法中,线性方程组的求解又是其它方法的基础,如: 样条插值 非线性方程组 用差分法解微分方程 等等。 返回节 [比如] 用每秒完成104 乘法的电子计算机 来解18阶线年! [ 结论 ] 因此,必须用数值方法来解线性方程组。 按照传统理论求解方法,当待求解方程组的系数行列式 时,在理论上可用Gramer法则求解式(2-2),可获得唯一解,其表达式为: 但因其计算量太大而失去了实际的使用价值。 其中: 第 j 列 求解AX=b的数值方法主要有: 直接法:在没有舍入误差的情况下,经过有限次的算术运算,得到 AX=b 精确解的方法。 由于计算机的字长是有限的,所以在实际计算中,舍入误差是不可避免的,因此直接法在计算机上也只能得到近似解。 迭代法:通过极限过程去逼近 AX=b 的精确解的方法。 有限步只能得到近似解。 迭代法放到第三章中介绍。 返回节 返回节 目前,在计算机上常用的直接解法,大多数是以系数矩阵的三角形化为基础的。 先对方程组进行变换,使其化为等价的(即具有相同答案的)三角形方程组 由于三角形方程组的求解非常容易,原来方程组的求解问题即告解决 本章中主要讨论这一类型的方法。 首先叙述三角形方程组的解法 然后再叙述各种将原方程组化为等价三角形方程组的方法 并比较其优劣 返回节 理论依据: 由“方程组的同解理论”可知,加减消元所得出的方程组同解(或称等价) 推理结论: 解最后的简单的方程组,也就等价于解最初的复杂的方程组 如果没有四则运算的误差,则各方法得出的解是精确的 返回节 所谓三角形方程组是指下面两种形式的方程组: 返回引用 其中L=[ lij ]为方程组(F-1)的系数所构成的下三角矩阵,其元素满足关系: lij = 0 ( ij ) U=[ uij ]为方程组(F-1)的系数所构成的上三角矩阵,其元素满足关系: uij = 0 ( ij ) 三角形方程组求解是非常简单。 其中: ?(F-1式)是下三角形方程组; ?(F-2式)是上三角形方程组。 若用矩阵符号即可分别写为:LX=b 或 UX=d 返回节 例如,对(F-1式) ,我们可以: ?先从其第(1)个方程定出 x1= b1 / l11 ?然后将其代入第(2)个方程,可得 x2= (b2 -l21x1) / l22 ?再把x1、x2代入第(3)方程,可定出 x3 ?如此,逐个方程地向前递推下去,n步后可求得全部解答 这一过程,有时也叫作----前推过程 显然,前推过程的计算公式,可以归结为: 返回节 完全类似,对(F-2式) ,我们可以: ?先从其第(n)个方程定出 xn=dn / un,n ; ?然后将其代入第(n-1)个方程,可得 xn-1 = (bn-1 –un-1,n xn) / un-1,n-1 ; ?如此逐个方程地回代下去,最终可求得全部解答。 这一计算所需要过程,通常叫做----回代过程。 显然,回代过程的计算公式,可以归结为: 返回节 n n2/2 n2/2 回代过程 n n2/2 n2/2 前推过程 除法 加减法 乘法 计算类 方法类 返回节 返回章 Gauss消去法(简称消去法) 是大多数读者早已熟悉的方法 已提出相当长的时间了,属于古老方法 实践表明 它仍是直接法中最常用方法 也是最有效的方法之一 基本思想 用逐次消去一个未知数的办法 把原来的方程组化为等价的(即同解)三角形方程组 这样,解答就很容易求得 基本作法 对方程组(2-1)进行加减消元 相当于增广矩阵[Ab]的行初等变换 例2.1 用Gauss消去法解? 为了建立一般性的算法,我们使用方程组与增广矩阵两种格式对照求解。 解: 方程组AX=b 增广矩阵[Ab] 方程编号 首先,我们来消去第(2)、(3)个方程中的未知数x1。具体操作如下: 步骤1: 步骤2: 一次消去结果 方程组AX=b 方程编号 增广矩阵[Ab] 步骤1: 二次消去结果 其次,我们来消去第(3)个方程中的未知数x2。具体操作过程如下: [ 例2.1解毕 ] 下面对一般性的算法进行推导。 为简明起见,令 n=4 则方程组的形式为: 为了建立相应的算法,我们使用增广矩阵形式进行求解。 其算法可归结为: 其算法可归结为: 其算法可归结为: 回代的一般过程如下。 算法计算量分析&误差分析

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

http://lusobeat.com/xianxingguijie/233.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有