线性方程组直接法.ppt

2 Gauss消元法 一 高斯消去法的求解过程 可大致分为两个阶段 首先 把原方程组化为上三角形方程组 称之为 消去 过程 然后 用逆次序逐一求出三角方程组 原方程组的等价方程组 的解 并称之为 回代 过程 下面分别写出 消去 和 回代 两个过程的计算步骤 消去过程 第一步 设a11 0 取做 消去第i个方程组的x1 mi1 第一个方程 第i个方程i 2 3 n则第i个方程变为 可得第一步消元后的方程组为 i j 2 3 n i j 2 3 n 第二步 设 取做 消去第i个方程组的x2 i 3 4 n mi2 第二个方程 第i个方程i 3 4 n类似可得第二步消元后的方程组为 第k步 设 取做 消去第i个方程组的xk i k 1 k 2 n mik 第k个方程 第i个方程i k 1 k 2 n类似可得第k步消元后的方程组为 继续下去到第n 1步消元 可将线性方程组化为如下上三角方程组 高斯消元法 GaussianElimination 1GaussianElimination TheMethod 消元 记 其中 Stepk 设 计算因子且计算 共进行 步 n 1 回代 Nouniquesolutionexists Whatifwecan tfindsuchk Nouniquesolutionexists 定理 若A的所有顺序主子式 determinantofleadingprincipalsubmatrices 均不为0 则高斯消元无需换行即可进行到底 得到唯一解 注 事实上 只要A非奇异 即A 1存在 则可通过逐次消元及行交换 将方程组化为三角形方程组 求出唯一解 1GaussianElimination TheMethod 3 高斯选主元素消去法 例1 考虑如下线性方程组的Gauss消元法求解性 2x2 12x1 3x2 2解 因为a11 0 故此题不能用Gauss消元法求解 但交换方程组的顺序后 就可用Gauss消元法求解了 选主元素的必要性 例2 单精度解方程组 用GaussianElimination计算 8个 小主元 Smallpivotelement 可能导致计算失败 1GaussianElimination PivotingStrategies 例题3 讨论下面方程组的解法 0 0001x1 x2 1x1 x2 2 假设求解是在四位浮点十进制数的计算机上进行 0 1000 10 3x1 0 1000 101x2 0 1000 1010 1000 101x1 0 1000 101x2 0 2000 101 解 本题的计算机机内形式为 因为a11 0 0001 0 故可用Gauss消元法求解 进行第一次消元时有a22 1 0 1000 101 104 0 1000 101 m21 a21 a11 1 0 0001 104 0 00001 105 0 1000 105 对阶计算 0 0000 0 1000 105 0 1000 105 得三角方程组0 1000 10 3x1 0 1000 101x2 0 1000 101 0 1000 105x2 0 1000 105 回代解得x2 1 x1 0严重失真 因为本题的准确解为x1 10000 9999 x2 9998 9999 例4用高斯消去法解方程组 要求用具有舍入的10位浮点数进行计算 精确到10位真解 解法1 高斯消去法 消元 舍去或着说被 吃 舍去或着说被 吃 计算解 显然 计算解与真解相差太大 作除数 使得舍入误差太大 从而计算结果不可靠 解法2用行变换的高斯消去法 消元 计算解 该结果较好 例子说明 在采用高斯消去法解方程组时 应 对一般系数矩阵 最好保持乘数 因此在高斯消去法中引进选主元素技巧 完全主元素消去法 一选主元消元法 为非奇异矩阵 第一步 3 消元计算 在A中选取绝对值最大的元素作为主元素 即确定 第k步 重复进行 设已完成第1步 第k 1的选主元 使 A 增广阵 A 约化为 第k步的步骤 3 消元计算 二回代求解 工作量大 经过上述过程 方程组约化为 缺点 优点 改进方法 列主元消去法 设已完成第1步 第k 1步计算 得到与原方程组等价的方程组 方框内为第k步选主元素区域 列主元素消去法 以下步骤类似完全选主元素消去法 例 注 列主元法没有全主元法稳定 例 标度化列主元消去法 ScaledPartialPivoting 对每一行计算 为省时间 si只在初始时计算一次 以后每一步考虑子列中最大的aik为主元 注 稳定性介于列主元法和全主元法之间 1GaussianElimination PivotingStrategies 列主元基本思想用高斯消去法求解线性方程组时 应避免小的主元 在实际计算中 进行第k步消去前 应该在第k列元素aik i k n 中找出绝大值最大者 例如 a max a 再把第p个方程与第k个方程组进行交换 使apk k 1 成为主元 我们称这个过程为选主元 由于只在第k列元素中选主元 通常也称为按列选主元 或称部分选主元 如果在第k步消去前 在第k个方程到第n个方程所有的xk到xn的系数a i k n j k n 中 找出绝对值最大者 例如 a max a 再交换第k p两个方程和第k q两个未知量的次序 使a成为主元 称这个过程为完全选主元 不论是哪种方式选出主元 而后再按上面介绍的计算步骤进行消去的计算 一般都称为选主元的高斯消去法 在实际计算中 常用按列选主元的高斯消去法 k 1 k 1 pk k 1 ik k i n k 1 pq k 1 ij k i j n k 1 ij k 1 pq 例4 2 5 4 2 6 P78 例1用列主元消去法解方程组 解第一次消元对 因列主元素为a31 1 故先作行变换r2 r3 然后进行消元计算可得 第二次消元对 A 2 b 2 因列主元素为a32 2 故先作行变换r2 r3 然后进行消元计算可得 由此回代 得x 1 9272 0 69841 0 90038 T与精确解x 1 9273 0 69850 0 90042 T相比较是比较准确的 例1用列主元素消去法解方程组 分析 由精确解看出有两位有效数字 因此 用4位浮点数进 解 消元 行计算 回代计算解 高斯选主元消去法的步骤 注 该解若取两位有效数字 则与真解完全相同 优点 数值稳定 修正方法 消元 回代 列主元高斯 约当 Gauss Jordam 消去法 缺点 既消元 又回代 列主元高斯 约当 Gauss Jordan 消去法 假设G J消去法已完成第1步 第k 1步 得到与原方程组等价 第k步计算步骤 的方程组 其中 1 按列选主元 2 换行 消元 3 消元计算 3 消元计算 4 计算主行 主元素所在行 计算解 1 按列选主元 2 换行 消元 说明 因此 可以用来求逆矩阵 如果用列主元G J消去法将 A I 不用回代 将A化为单位矩阵 则解为常数项列 定理9 列主元高斯 约当法求逆矩阵 化为 I T 优点 缺点 因为计算量太大 但是在解多个方程组而它们的系数矩阵相同时 该方法与高等代数中求逆矩阵方法的不同之处是有选主 注 元 实际上选主元就是交换两行的位置 仍是初等变换 在一般的 求逆矩阵方法中也有交换两行元素 例4 2 8 4 2 9 P81 例6用列主元G J消去法求 解 理解完全主元素消去法 本课重点 会用列主元素消去法解方程组 列主元素消去法 列主元高斯 约当 Gauss Jordan 消去法 会用列主元高斯 约当 Gauss Jordan 消去法求矩阵的逆矩阵 高斯消去法的计算量分析高斯消去法的乘除总运算 由于计算机作乘除运算所需时间远大于作加减运算所需时间 故我们只讨论乘除运算量 分析为消元次数k消元乘法次数消元除法次数回代乘除法总次数1n n 1 n 12 n 1 n 2 n 2 k n k 1 n k n k n 12 11n n 1 2故高斯消去法的计算量为N n n2 1 3 n n 1 2 n n 1 2 n3 3 n2 n 3当N充分大时为n3 3 运算量 AmountofComputation 1GaussianElimination AmountofComputation 由于计算机中乘除 multiplications divisions 运算的时间远远超过加减 additions subtractions 运算的时间 故估计某种算法的运算量时 往往只估计乘除的次数 而且通常以乘除次数的最高次幂为运算量的数量级 GaussianElimination n k 次 n k 2次 n k 次 消元乘除次数 1次 n i 1 次 回代乘除次数 GaussianElimination的总乘除次数为 运算量为级 1GaussianElimination AmountofComputation CompletePivoting 比GaussianElimination多出比较 保证稳定 但费时 PartialPivoting 比GaussianElimination只多出比较 略省时 但不保证稳定 ScaledPartialPivoting 比GaussianElimination多出除法和比较 比列主元法稳定 但若逐次计算si k 则比全主元法还慢 Gauss JordanMethod 运算量约为 故通常只用于求逆矩阵 而不用于解方程组 求逆矩阵即 方法的特点由具体计算结果可知 全主元素法的精度优于主元素法 这是由于全主元素是在全体系数中选主元 故它对控制舍入误差十分有效 但全主元素法在计算过程中 需同时作行与列的互换 因而程序比较复杂 计算时间较长 列主元素法的精度虽稍低于全主元素法 但其计算简单工作量大为减少 且计算经验与理论分析均表明 它与全主元素法同样具有良好的数值稳定性 列主元素法是求解中小型稠密性方程组的最好方法之一 选主元消去法 包括解线性方程组的所有直接的方法 比较适用于中小型方程组 对高阶方程组 即使奇数矩阵是稀疏的 但在计算中很难保持稀疏性 因而有存储量大 程序复杂等不足 所幸的是这一缺点可用迭代法解决 另外 高斯选主元消去法还可技巧性的解决一些特殊线性方程组由于误差的影响 计算过程中可能出现一些坏现象 要尽可能防止 表现在求解线性方程组的消元法比较上 则应该注意要简化运算 减小运算次数 提高效率 提高数值稳定性等 LU分解法的与特殊方程组的解法 假定我们能把矩阵A写成下列两个矩阵相乘的形式 A LU其中L为下三角矩阵 U为上三角矩阵 这样我们可以把线性方程组Ax b写成Ax LU x L Ux bLy b令Ux y 则原线性方程组Ax bUx y于是可首先求解向量y使Ly b然后求解Ux y 从而求解线性方程组Ax b的目的 LU分解法的基本思想 内容 LU分解 关键词 LU分解 将系数矩阵A转变成等价两个矩阵L和U的乘积 其中L和U分别是下三角和上三角矩阵 而且要求L的对角元素都是1 紧凑格式 由于可以把L和U两个矩阵压缩到一个数组中 而且还可以存储在原来的系数矩阵A的数组中 这种LU分解表示常被称为紧凑格式 定义1 叫 的三角 因子 分解 其中是 是上三角 下三角 为单位下三角阵 对角元全为1 为上三角阵 则称 为Doolittle分解 若是下三角 是单位上三角 则称 定理1n阶阵 有唯一Doolittle分解 Crout 的前n 1个顺序主子式不为0 证略 三角分解不唯一 为此引入 定义2若 为Crout分解 为什么要讨论三角分解 若在消元法进行前能实现三角分解 则 容易回代求解 回代求解很容易 如 由LU A及对L和U的要求可以得到分解的计算公式 根据下式 Doolittle分解 1l211l31l321 ln1ln2 lnn 11 u11u12u13 u1nu22u23 u2n un 1nu n 1 nunn a ann LU 第j个分量 第i个分量 根据矩阵乘法及相等的定义 有 得公式u1j a1jj 1 2 nli1 ai1 u11i 2 3 n 在计算机程序中常常用这种方法解线性代数方程组 它的优点是存储量很省 L和U中的三角零元素都不必存储 就是U的对角元素也因为都是1没有必要再记录在程序中 这样只用一个n阶方阵就可以把L和U贮存起来 即 下三角 不包括对角元 存储L各元素而上三角存储U的元素 再考察公式S会发现A中任一元素aij只在计算lij ji 中用到一次以后就不再出现了 因而完全可以利用原始数组A的单元 一个个逐次贮存L或U中的相应元素 即 a11a12a13 a1nu11u12u13 u1na21a22a23 a2nl21u22u23 u2na31a32a33 a3nl31l32u33 u3nan1an2an3 annln1ln2ln3 unn 1 3 5 2n 1 2 4 6 2n 采用LU分解有如下特点 1 LU分解与右端向量无关 先分解 后回代 一般说来 分解的运算次数正比于n回代求解正比与n 求遇到多次回代时 分解的工作不必重新做 这样节省计算时间 2 分解按步进行 前边分解得到的信息为后边所用 3 A 阵的存储空间可利用 节省存储 3 2 例1 选主元的三角分解法 略 特殊方程组的解法 1 追赶法2 LDL 转置 分解法3 平方根法 1 追赶法 追赶法与稀疏线性方程组追赶法仍然保持LU分解特性 它是一种特殊的LU分解 充分利用了系数矩阵的特点 而且使之分解更简单 得到对三对角线性方程组的快速解法 因三对角矩阵的非零元素呈 带状 我们也因此将它叫做带状矩阵 三对角线性方程组 设有方程组Ax d 其中A为三对角矩阵 假设系数矩阵A满足条件 对A作Crout分解形式为 第i个分量 第j个分量 追赶法计算公式 定理如果上带宽为q 下带宽为p的n阶带状矩阵A有Doolittle分解 A LU 则L是下带宽为p的单位下三角矩阵 U是上带宽为q的上三角矩阵 下面举实例用追赶法来解三对角方程组 实际问题中 当求解方程组的系数矩阵是对称矩阵时 则用下面介绍的LDL转置分解法可以简化程序设计并减少计算量 从定理可知 当矩阵A的各阶顺序主子式不为零时 A有唯一的Doolittle分解A LU 此时 当然有 所以矩阵U的对角线元素uii 0 i 1 2 n 将矩阵U的每行依此提出uii 2 LDL 转置 分解法 由A AT 得由分解的唯一性有 即 于是可得下面的结论 定理3 若对称矩阵A各阶顺序主子式不为零时 则A可以唯一分解为A LDLT 这里 LT为L的转置矩阵 当A有LDLT分解时 利