《数值分析》课件-第5章 解线性方程组的直接法.ppt

经过回代后可得 事实上,方程组的准确解为 例2所用的方法是在Gauss消去法的基础上,利用换行 避免小主元作除数,该方法称为Gauss列主元消去法 二、Gauss消元过程与系数矩阵的分解 1.Gauss消去法消元过程的矩阵描述 行变换相 当于左乘 初等矩阵 由于 令 则 显然若令 则有 因此 从而 故 即 且 顺序主元 定义1. 不带行交换的Gauss 消去法的消元过程,产生 一个单位下三角矩阵L和一个上三角矩阵U,即 该过程称之为 由上述分析不难得到 Gauss消去法 可以执行 定理1. 在定理中,可能注意到 可能存在 2.Gauss列主元消去法消元过程的矩阵描述 由于Gauss列主元消去法每一步都要选取列主元,因 此不可避免要进行行交换 即 表示不换行 初等矩阵 因此,Gauss列主元消去法的消元过程为 : 显然 上三 角阵 仍然为单位 下三角矩阵 初等矩阵的乘积,称为排列阵 则 推广到一般情形 令 仍然为单位 下三角矩阵 则 单位下三角阵与上三角阵的乘积 综合以上讨论,有 定理2. 开始 输出无解信息 消元 换行 停机 回代求解 三、Gauss列主元消去法的算法设计 (一) 流程图 (二) 自然语言 选主元 换行 消元 回代 上述过程中的储存空间需要: 注意: 储存空间需要较大 5.3 直接三角分解法 一、基本的三角分解法(Doolittle法) 上式可记为 → → 同样,由 综合以上分析,有 因此可以推导出 U的第一行 L的第一列 ------(1) ------(2) U的第r行 L的第r列 ------(3) ------(4) 称上述(1) ~ (4)式所表示的分解过程为Doolittle分解. 思考 对于线性方程组 系数矩阵非奇异,经过Doolittle分解后 线性方程组可化为下面两个三角形方程组 上述解线性方程组的方法称为 直接三角分解法的 Doolittle法( A=LU ) 例1. 用Doolittle法解方程组 解: 由Doolittle分解 Doolittle法在计算机上实现是比较容易的 但如果按上述流程运算仍需要较大的存储空间: 因此可按下列方法存储数据: 第五章 解线性方程组的直接法 成都银杏酒店管理学院《数值分析》 5.1 线性方程组与直接法 实际问题中的线性方程组分类： 按系数矩阵中 零元素的个数： 稠密线性 方程组 稀疏线性 方程组 按未知量 的个数： 高阶线性 方程组 低阶线性 方程组 (如1000) (80%) 按系数矩 阵的形状 对称正定 方程组 三角形 方程组 三对角占 优方程组 一、直接法概述 直接法是将原方程组化为一个或若干个三角形 方程组的方法，共有若干种． 对于线性方程组 其中 系数矩阵 未知量向量 常数项 ------------(1) 根据Cramer(克莱姆)法则,若 determinantal 行列式的记号 若用初等变换法求解,则对其增广矩阵作行初等变换: 经过n-1次 同解 即 以上求解线性方程组的方法称为Gauss消去法 则 都是三角 形方程组 上述方法称为直接三角形分解法 ------------(2) 不论是Gauss消去法还是直接三角形分解法, 都归结为解三角形方程组. 二、三角形线性方程组的解法 若记 下三角形线性方程组 上三角形线性方程组 即 前推方向 其解为 其解为: 回 代 方 向 K 由消元过程和回代过程构成高斯(Gauss)消去法. 基本思想 用矩阵行的初等变换将方程组系数矩阵A约化为简单的三角形矩阵,然后回代求解. 5.2 Gauss消去法 5.2 Gauss消去法 一、消元与回代计算 对线性方程组 对其增广矩阵施行行初等变换: 定义行乘数（消元因子）： 且 定义行乘数 ( n次除法 及 次乘法 ) 二、Gauss消去法的运算量 计算机作乘除运算所耗时间要远远多于加减运算 且在一个算法中，加减运算和乘除运算次数大体相当 故在衡量一个算法的运算量时只需统计乘除的运算次数 乘法次数： 除法次数： 全部回代过程需作乘除法的总次数为 于是Gauss消去法的乘除法运算总的次数为 数量级 Gauss消去法乘除法约为2700次