线性方程组的直接解法.ppt

上传人：j*** IP属地：四川上传时间：2019-06-21 格式：PPT 页数：44 大小：1012.32KB 积分：15 举报 版权申诉

已阅读5页，还剩39页未读，继续免费阅读

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1,第五章线性方程组的直接解法 /* Direct Methord for Solving Linear Systems */,上一页下一页返回,第一节 Gauss消去法,第二节直接三角分解方法,第三节方程组的性态与误差估计,2,求解,上一页下一页返回,3,1 Gauss消去法,一、高斯顺序消去法,是一种古老的求解线性方程组的方法, 按自然顺序进行消元的方法.,上一页下一页返回,4,例1 解方程组,解：step1 消元,上一页下一页返回,5,Step2 对上三角形方程进行回代求解, 得,下面我们来一般性地讨论求解n阶线性方程组的高斯顺序消去法.,上一页下一页返回,6,消元,上一页下一页返回,7,Step 2：一般第 k 次消元 (1k n-1),上一页下一页返回,8,上一页下一页返回,9,Step 3：继续上述过程, 且设 aii（i-1）0(i=1,2,n-1),直到完成第 n-1 次消元, 最后得到与 A(0)x=b(0) 等价的三角形方程组 A(n-1)x=b(n-1).,将(1)式化为(2)式的过程称为消元过程.,上一页下一页返回,10,回代,定理,若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。,注：事实上，只要 A 非奇异，即 A1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。,上一页下一页返回,11,高斯顺序消去法流程图,上一页下一页返回,12,顺序消去法的缺点为当主元akk(k -1)=0时, 消元过程不能继续进行. 或者当akk (k -1) 0时, 虽然消元过程可以进行, 但若akk (k -1) 0时, 时, 会出现很小的数作除数的现象,使舍入误差增大,导致解的严重失真.,上一页下一页返回,13,例：解方程组,/* 精确解为 */,用Gauss消去法计算：,二、主元素消去法,上一页下一页返回,14,由上例可以看出,为提高算法的数值稳定性, 应选取绝对值尽可能大的元素作主元.,上一页下一页返回,按列部分选主元的消去法也称列主元消去法。,15,解：,上一页下一页返回,16,一些特殊情况, 主元就在对角线上,不需选主元.,元素满足如下条件的矩阵,即对角线上每一元素的绝对值均大于同行其他各元素绝对值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角占优矩阵.,例：,性质：严格对角占优矩阵必定非奇异.,上一页下一页返回,17,三、高斯-约当消去法（求矩阵逆）,与 Gauss消去法的主要区别：, 每一步不计算 lik ，而是先将当前主元 akk(k-1) 变为 1;, 把 akk(k-1) 所在列的上、下元素全消为0;,这种方法是不是比Gauss消去法更好?,Gauss消去法过程中，消去对角线下方和上方的元素，称这种方法为高斯-约当消去法.,上一页下一页返回,这种方法不用回代过程了，看上去是要好些？,18, 运算量 /* Amount of Computation */,由于计算机中乘除 /* multiplications / divisions */ 运算的时间远远超过加减 /* additions / subtractions */ 运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。, Gauss消去法:,(n k) 次,(n k)2 次,(n k) 次,消元时乘除次数：,1 次,(n i +1) 次,回代时乘除次数：,Gauss消去法的总乘除次数为，运算量为级。,上一页下一页返回,19, Gauss-Jordan 消去法:,运算量约为。故通常只用于求逆矩阵，而不用于解方程组。求逆矩阵即。,上一页下一页返回,20,2 直接三角分解法,一、 LU分解法 /* LU Factorization. */,就 n=3的情况分析顺序消去法的消元过程.,上一页下一页返回,21,可见, 消元过程相当于下述矩阵乘法运算：,由分块乘法可得：,直接计算可得,由(*)式可得,上一页下一页返回,22,Step 1:,以上分析推广到n阶线性方程组可得,上一页下一页返回,23,单位下三角阵 /* unitary lower-triangular matrix */,A 的 LU 分解 /* LU factorization */ 也称 A 的Doolittle分解,上一页下一页返回,24, 道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form */,根据矩阵乘法法则,先比较等式两边第1行和第1列元素有：,上一页下一页返回,25,设已定出U 的第1行到第k-1行的元素,L 的第1列到第k-1列的元素,上一页下一页返回,26,(1),(2)两式就是 LU分解的一般计算公式, 其结果与高斯消去法所得结果完全一样. 避免了中间过程的计算,故称为A的直接分解公式.,上一页下一页返回,27,按上图逐框求出矩阵A的LU分解,这种计算方法称为紧凑格式法。,上一页下一页返回,28,上一页下一页返回,29,例：利用系数矩阵的LU分解, 求解方程组,解：LU分解的紧凑格式为,上一页下一页返回,30,则求解原方程组等价于求解下面两个方程组Ly=b及Ux=y,上一页下一页返回,31,二、三对角方程组追赶法,若A满足Gauss消去法可行的条件，则可用LU分解法求解,其中：,上一页下一页返回,32,解方程组Ax=d分为两步，即求解Ly=d和Ux=y，计算公式如下：,上述方法为求解三对角方程组的追赶法，也称Thomas算法.,上一页下一页返回,追赶法公式简单，计算量和存储量都小，整个求解过程只需要5n-4次乘除运算。,33,上一页下一页返回,三、平方根法对称正定矩阵的分解法,将对称正定阵 A 做 LU 分解,34,称为矩阵A 的乔累斯基分解,上一页下一页返回,称为对称正定矩阵A 的乔累斯基分解,利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法,35,3 方程组的性态与误差估计,上一页下一页返回,一、矩阵的条件数,例，考查以下三个方程组及其准确解,其准确解,其准确解,其准确解,可以看到，后两个方程组与第一个方程组相比，系数矩阵或右端向量仅有0.0005以下的误差，但准确解却相差很大。对这样的方程组，无论用多么稳定的算法求解，一旦计算中产生误差就使解面目全非，所以该方程组的性态很差。,36,上一页下一页返回,定义：若方程组Ax=b的系数矩阵A与右端向量b的微小变化（小扰动）,将引起解向量x产生巨大变化，则称此方程组为病态方程组，其系数矩阵A称为病态矩阵，否则称Ax=b为良态方程组，称A为良态矩阵 .,方程组的病态程度与Ax=b对A和b的扰动的敏感程度有关。,37,求解时，A 和的误差对解有何影响？, 设 A 精确，有误差，得到的解为，即,绝对误差放大因子,又,相对误差放大因子,上一页下一页返回,38, 设精确，A有误差，得到的解为，即,(只要 A充分小，使得,大,上一页下一页返回,39, cond (A) 取决于A，与解题方法无关。,常用条件数有：,cond 1(A),cond (A),cond2 (A),特别地，若 A 对称，则,条件数的性质： A可逆，则 cond p (A) 1； A可逆， R 则 cond ( A) = cond (A) ； A正交，则 cond 2 (A) =1； A可逆，R正交，则 cond 2 (RA) = cond 2 (AR) = cond2 (A) 。,上一页下一页返回,40,精确解为,A1 =,解：考察 A 的特征根,39206 1, 测试病态程度：,此时精确解为,2.0102 200%,上一页下一页返回,41,cond (H2) =,27,cond (H3) ,748,cond (H6) =,2.9 106,cond (Hn) as n ,注：一般判断矩阵是否病态，并不计算A1，而由经验得出。行列式的值很大或很小（如某些行、列近似相关）；元素间的数量级相差大，且无规则；主元消去过程中出现小主元；特征值相差大数量级。,上一页下一页返回,42,二、方程组解的误差估计,定理,上一页下一页返回,43,上一页下一页返回,解

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

线性方程组的直接解法.ppt

文档简介

温馨提示

最新文档

评论

线性方程组的直接解法.ppt

文档简介

温馨提示

最新文档

评论

相关文档