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

3. 系数矩阵A和右端项b的扰动对解的影响 定理3.10 矩阵A的条件数的定义 准确，可靠，理论上得到的解 是精确的 第四章 解线性代数方程组的直接法 背景：在自然科学和工程技术中，很多问题往往最终都归结为解线性代数方程组，例如：结构分析、网络分析、数据分析、最优化和微分方程组数值解等，常遇到线性方程组的求解问题. 记为矩阵形式： 解线性方程组的数值方法大体上可分为两类：直接法和迭代法 ① 直接法是指在没有舍入误差的情况下经过有限次运算可求得精确解； ② 迭代法是从一个初始向量出发按照一定的计算格式逐次逼近精确解. 在线性代数课程中，给出了求解线性方程组的一种直接法 --- 克莱姆（Cramer，瑞典数学家）算法.例如 一、直接法 速度快，但有误差 或者： 根据Cramer法则：当且仅当 时，有唯一解，而且解为： 如取n＝100，1033次/秒的计算机大约要算10120年.可见，该方法对高阶方程组计算量太大,不是一种实用的算法. 实用的直接法中具有代表性的算法是高斯（Gauss,德国）消去法（一般适用于低阶稠密矩阵方程组求解），其它很多算法都是它的变形和应用. 为了给出高斯消去法公式，我们回顾一些知识： 需计算n+1个行列式，而每个行列式的计算需（n-1）*n！次乘法.计算x需n次除法 ? 1. 下面三种线性方程组的解可直接求出： ① ② ③ 求解次序 第i行 第i行 0 0 对方程组，作如下的变换，解不变！ ①交换两个方程的次序. ②一个方程的两边同时乘以一个非0的数. ③一个方程的两边同时乘以一个非0数，加到另一个方程. 因此，相应地对增广矩阵(A，b)，作如下的变换，解不变！ ①交换矩阵的两行. ②某一行乘以一个非0的数. ③某一行乘以一个非0数，加到另一行. ? 2. 初等变换矩阵的性质： 的思想 使用初等行变换,将Ax=b转化为同解的上三角方程组，再回代求解 . = = Gauss消元法 0 Gauss消元法的求解过程可分为两个环节：消元过程和回代过程. 消元过程是将系数矩阵 A化为上三角矩阵的过程 回代过程是 求解上三角方程 组的过程 下面主要讨论消元过程：实质上是将方程组的增广矩阵 通过 初等行变换化成三角方程组的增广矩阵 的过程. 矩阵形式为: 第1行 称为顺序 Gauss消去法 矩阵形式： 第2行 矩阵形式 第k行 类似地进行下去，经n-1步消元后便得到 记 则上式可以写成： 或者 上三角矩阵！ 可以证明： ? 要使Gauss消去法能够进行下去，必须有约化后的主对角元素非零。 问：矩阵A在什么条件下能够保证此条件成立？ 定理 1.3 下面，我们对一些特殊的矩阵，提出一些特定的分解法 在实际计算中，用Gauss消去法解方程组，即使 不为零，但其绝对值很小，也会导致其他元素数量级的严重增长和舍入误差扩散，从而会严重地损失精度！ 不能保证计算过程是数值稳定的！ 注： 例1.1 用Gauss消去法解方程组，计算中取5位有效数字. 解： 消去是精确的！ x √ 这说明：在计算过程中若规定取5位有效数字，用消去法得到的近似解与准确解相差很大！ √ 这是因为：用0.0003做除数，也会导致其他元素数量级的严重增长和舍入误差扩散，从而会严重地损失精度！ 因此，要控制舍入误差。 控制舍入误差的增长，通常有两种途径： 1.增加参加计算的数字位数，从而使最后结果中积累起来的误差随之减小。例如： 采用双精度，但增加计算时间. 2.从上面的计算过程可知：有些运算舍入误差会扩散，但有些运算舍入误差影响 比较小。例如：在做除法运算时，分母的绝对值越小，舍入误差影响就越大！ 第k行 对于某些特殊类型的系数矩阵，可以保证“主元不会很小”，从而不需要选主元！ 主元消去法的基本思想：在做除法运算时，要选取绝对值比较大的做分母！ 定义 1.1 定理 1.1 定理 1.2 可保证：Gauss消去法能 进行下去！ 可保证：Gauss消去法不 用选主元！ 列主元消去法计算步骤： 1、输入矩阵阶数n，增广矩阵 A(n,n+1); 2、对于 (1) 按列选主元：选取 l 使 (2) 如果 ，交换A的第k行与底l 行元素 (3) 消元计算 ： 3、回代计算 初始化 消元过程 列选主元 回代过程 第2节 矩阵三角分解法 — Gauss消去法的变体 通过比较法，直接导出L和U 的计算公式. 思路 ① Doolittle分解法的计算公式： ② (1) 第k列 第k行 1 (2) 计算U的第k行和L的第k列 已知 ① Crout分解法的计算公式： ② (1) 第k列 第k行 1 (2) 计算L的第k列和U的第k行 已知 ① 第k列 第k行 (1)