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

数值分析 李小林重庆师范大学数学学院 NumericalAnalysis 2 第五章线性方程组的直接解法 DirectMethodforSolvingLinearSystems 求解 Cramer法则 3 Cramer法则的计算量 4 直接法 经过有限步运算后可求得方程组精确解的方法 不计舍入误差 第5章 迭代法 从解的某个近似值出发 通过构造一个无穷序列去逼近精确解的方法 第6章 分为两类 逐次逼近法 一般有限步内得不到精确解 6 1 6 3节 共轭梯度法 不考虑计算过程的舍入误差 只用有限步就收敛于方程组的精确解 6 4节 解线性方程组的两类方法 5 5 1高斯消去法 GaussianElimination 6 将增广矩阵的第i行 mi1 第1行 得到 消元过程 第一步 设 计算因子 一 顺序消去法 7 第k步 设 计算因子 将增广矩阵的第i行 mik 第k行 得到 其中 8 回代过程 共进行n 1步 得到 9 运算量 AmountofComputation 10 11 证明 归纳法证明 对k归纳 12 在归纳假设下 Gauss消去法可进行到第k 1步 因此 若矩阵的各阶顺序主子式均不为零 可以采用顺序Gauss消去法求解 13 二 选主元消去法 选主元三角分解的思想 三角分解过程中存在的问题 顺序Gauss消去法完成的条件是矩阵的各阶顺序主子式均不为零 选主元的目的就是为了完成消元且避免不稳定情况的发生 14 例 在8位制计算机上解方程组 用Gauss消去法计算 8个 小主元 Smallpivotelement 可能导致计算失败 为避免这种情况的发生 可通过交换方程的次序 选取绝对值最大的元素作主元 基于这种思想导出了 选主元消去法 15 列主元消去法 在第k步消元前 在系数矩阵第k列的对角线以下的元素中找出绝对值最大的元 列主元Gauss消去法保证了 mik 1 i k 1 k 2 n 16 全主元消去法 在第k步消去前 在系数矩阵右下角的n k 1阶主子阵中 选绝对值最大的元素作为主元素 1 Ifp kthen交换第k行与第p行 Ifq kthen交换第k列与第q列 2 消元 注 列交换改变了xi的顺序 须记录交换次序 解完后再换回来 17 三矩阵的三角分解 在顺序Gauss消去法中 每一步消去过程相当于左乘初等变换矩阵Lk 18 19 A的LU分解 LUfactorization 20 证明 只需证明唯一性 21 注 1 L为单位下三角阵而U为一般上三角阵的分解称为Doolittle分解 2 L为一般下三角阵而U为单位上三角阵的分解称为Crout分解 22 5 2矩阵三角分解法 一 直接三角分解法 Doolittle分解法 23 24 一般计算公式 25 方程组可化为两个易求解的三角方程组 26 计算x和y的工作量 加减乘除运算次数之和 均为 27 28 例1 用Doolittle算法求解方程组 解 系数矩阵 29 30 例2 用Doolittle算法求解方程组 解 系数矩阵 LU分解 31 32 平方根法 Cholesky乔列斯基分解方法 实对称正定矩阵的几个重要性质 A 1亦对称正定 且aii 0 A的顺序主子阵Ak亦对称正定 A的特征值 i 0 A的全部顺序主子式det Ak 0 充要条件 二平方根法 33 证明 设 则的所有顺序主子式为正 矩阵存在Doolittle分解 易证 其中为的主对角元素 且有 34 单位上三角阵 记 左边是单位上三角阵 右边是单位下三角阵 35 思想 Cholesky分解的计算公式 设 由对应元素相等得 36 Cholesky分解公式 37 因对称性无需存储 Step1 Step2 Step3 的计算过程 38 39 例 用Cholesky分解法求解下列方程组 解 系数矩阵为 Step1 Step2 Step3 40 求解方程组 求解方程组 41 Cholesky分解法求解方程组中需说明的几个问题 工作量 约为分解的一半 不必选主元 的正定性和算法的稳定性 稳定性 是数值稳定的 缺陷 存在开平方运算 改进方法 分解 改进的平方根法 42 改进的平方根法 ModifiedSquareRootingMethod 当时 43 Step1 Step2 Step3 时 44 例 用改进的平方根法求解下列方程组 解 系数矩阵为 Step1 Step2 Step3 45 求解方程组 求解方程组 46 在数值求解常微分方程边值问题 热传导方程和建立三次样条函数时 都需要解三对角方程组 Ax f 并且满足 条件 i 保证方程组不能降阶 条件 ii 保证三角分解可做到底 三三对角线性方程组的三对角算法 追赶法 47 下面讨论三角分解 Crout分解 比较两边得到 48 解三对角方程组的追赶法 追 的过程 赶 的过程 追赶法总计算量为5n 4次乘除法 乘除法2n 1次 乘除法2n 1次 乘除法n 2次 49 例 用追赶法求解三对角方程组 其中 解 50 51 求解方程组 求解方程组 52 5 3向量和矩阵的范数 一 向量范数 VectorNorm 正定性 齐次性 三角不等性 非负实值函数 称为赋范线性空间 可以推广到 53 常用的几种向量范数 设 1 范数 2 范数 范数 上述3种向量范数统称为p 范数 或者Holder范数 54 设 由夹逼定理 55 两个重要不等式 闵可夫斯基 Minkowski 不等式 即 p 2时 三角形两条边x和y的长度的和大于等于第三条边x y的长度 几何意义 56 柯西 施瓦茨 Cauchy Schwartz 不等式 或者 即 57 Cauchy Schwartz不等式的证明 令 58 例1 设是n阶实对称正定矩阵 则是中的一种向量范数 证明 只需验证范数的3个条件成立即可 非负性 齐次性 三角不等性 存在非奇异下三角阵 59 证明 只需验证范数的3个条件成立即可 非负性 齐次性 三角不等性 闵可夫斯基 Minkowski 不等式 60 向量范数的性质 性质1 证明 同理 61 性质2 是的n元连续函数 证明 设 其中 62 例如 设 63 性质3 向量范数的等价性具有传递性 性质4 的所有向量范数是彼此等价的 64 向量序列的极限 即向量序列的收敛定义于向量分量收敛 Def 其中 65 性质5 证明 由性质4 66 二 矩阵范数 MatrixNorm 正定性 齐次性 三角不等性 赋范线性空间 可以推广到 相容性 67 证明 只需验证范数的4个条件成立即可 记 Frobenius范数 简称F 范数 Cauchy Schwartz不等式 68 相容性 Compatibility 69 证明 设 易验证它是一种向量范数 令 70 记 由得 71 而 72 从属性 Subordination 73 证明 矩阵范数与向量范数的相容性 令 则 故 74 非负性 设 则 由 知 齐次性 三角不等性 75 相容性 算子范数的一般定义形式 76 谱半径 77 证明 列范数 记 对 78 注意到 行范数 对 79 设 令 则 80 因为是半正定的对称阵 可设其特征值为 其对应的正交规范特征向量为 则对 81 82 83 证明 取 84 证明可从矩阵的2 范数定义考虑 设 85 证明 设为的任一特征值 86 对 其中 Jordan块矩阵 对 定义 87 其中 88 可看成是维向量空间 由向量范数的性质3得 易验证 89 证明 设为的任一特征值 则有 设 则有 必要性 充分性 90 91 证明 则存在向量满足 所以矩阵有一个特征值 1 记 反证法 若不可逆 92 证明 而 故可逆 93 5 4误差分析 一 矩阵的条件数 由实际问题得到的方程组的系数矩阵或者常数向量的元素 本身会存在一定的误差 这些初始数据的误差在计算过程中就会向前传播 从而影响到方程组的解 初始数据误差和方程组的近似解的误差之间关系 例1考察方程组 精确解为 94 设方程组存在扰动 精确解为 上例说明该方程组的解对初始元素的扰动非常敏感 设方程组为 系数矩阵和常数向量的扰动分别记为 和 实际求解的方程组为 95 病态方程组对任何算法都将产生数值不稳定性 96 设为可逆阵 则称为矩阵 或者相应方程组 的条件数 若矩阵范数取2 范数 则得到谱条件数 若矩阵范数取1 范数 则得到1 条件数 若矩阵范数取 范数 则得到 条件数 97 如果是正交矩阵 则 条件数的性质 设 如果为正交矩阵 则 设和是按模最大和最小的特征值 则 98 99 证明 设 由条件 所以可逆 且 100 方程组有唯一解 101 102 推论 如果 则 如果 则 在上述定理的条件下 103 104 例如 Hilbert矩阵就是一个著名的病态矩阵 105 二 迭代改善法 常用的几种判定方程组为病态的经验方法 当相对来说很小时 或者矩阵的某些行 列 近似线性相关时 可能为