线性代数方程组的直接法.ppt

2020 2 20 1 王淑栋办公室 J13 409电话 88032786 H 15269283087E mail wangshd2008 数值分析 NumericalAnalysis 2020 2 20 2 第七章解线性方程组的直接方法 数值分析 NumericalAnalysis AX b 很多实际问题都可归结为求解线性方程组 2020 2 20 3 写成矩阵形式 线性方程组数值解法的分类 直接法 经过有限步算术运算即可求得方程组精确解的方法 适用于中等规模的n阶线性方程组 Gauss消去法及其变形 矩阵的三角分解法 迭代法 用某种极限过程去逐步逼近线性方程组精确解的方法 适用于高阶线性方程组 Jacobi迭代法 Gauss Seidel迭代法 逐次超松弛法 2020 2 20 4 2020 2 20 5 1Gauss消去法 或AX b 消元手续 2020 2 20 6 举例说明消去法的基本思想 基本思想 用逐次消去未知数的方法把原来方程组AX b化为与其等价的三角方程组 然后再用回代法写出方程组的解 事实上 将方程组化为与其等价的三角方程组的过程就是用行的初等变换将原来方程组的系数矩阵化为简单形式 然后再求解 1 消元 基本思想 通过消元手续将上述方程组化为三角形方程组进行求解 2020 2 20 7 Guass消去法 消元公式 2020 2 20 8 2 回代 2020 2 20 9 回代公式 2020 2 20 10 Gauss消去法可执行的前提 定理1 按顺序Gauss消去法所形成的各主元素的充要条件是矩阵的顺序主子式 即 2020 2 20 11 推论 如果的顺序主子式 2020 2 20 12 定理2 如果的所有顺序主子式都不为零 即则可通过Gauss消去法将前面的方程组约化为三角方程组 2020 2 20 13 作业 P1971 2 7 不进行交换两行的初等变换 2020 2 20 14 矩阵的三角分解 借助矩阵理论分析消去法 建立Gauss消去法和矩阵理论间的关系 对于 或AX b 在Gauss消元法中 每一步消去过程相当于左乘初等变换矩阵Lk 2020 2 20 15 2020 2 20 16 A的LU分解 其中单位下三角形 2020 2 20 17 定理3 矩阵的LU分解 设A为n n矩阵 如果解AX b用高斯消去法 限制不进行行的交换 即 能够完成 则矩阵A可分解为单位下三角矩阵L与上三角矩阵U的乘积 即A LU且这种分解是唯一的 2020 2 20 18 注 1 L为单位下三角阵而U为一般上三角阵的分解称为Doolittle分解 2 L为一般下三角阵而U为单位上三角阵的分解称为Crout分解 2020 2 20 19 2020 2 20 20 系数矩阵的三角分解 21 计算量 1 消元过程的计算量 第1步计算乘数mi1 i 1 2 n 需要n 1次除法运算 计算需要次乘法和次加 减法 22 2 计算b n 计算量 进行次乘法和加 减法 3 回代过程的计算量 总计算量 次乘除法和次加减法 较大时 乘除法次数 较大时 加减法次数 2Gauss主元素消去法 例4 用Gauss消去法解方程组 选主元素的必要性 要求用具有舍入的10位浮点数进行计算 精确到10位的精确解为 解法1 高斯消去法 消元 舍去或者说被 吃 舍去或者说被 吃 计算解 2020 2 20 23 显然 计算解与精确解解相差太大 原因是用很小的数 作除数 使得舍入误差太大 从而计算结果不可靠 解法2 用行变换的高斯消去法 消元 计算解 该结果较好 该例子说明 在采用高斯消去法解方程组时 应避免采用绝对值很小主元素 对一般系数矩阵 最好保持乘数 因此在高斯消去法中引进选主元素技巧 24 1 完全主元素消去法 选主元素消元法 为非奇异矩阵 第一步 1 选主元素 在A中选取绝对值最大的元素作为主元素 即确定使 2 交换行列 交换中第1行和i1行元素 第1列和第j1列元素 注意调换两未知量 并做记录 交换后的元素仍记为 3 第1次消元计算 重复进行上述过程 设已完成第1步至第k 1步的选主元素 交换行列和消元计算 使 为增广矩阵 25 第k步 1 选主元素 选取使 2 交换行列 交换中第k行和ik行元素 第k列和第jk列元素 3 消元计算 2020 2 20 26 回代求解 工作量大 经过上述过程 方程组约化为 缺点 优点 数值稳定 改进方法 列主元消去法 且此时 其中是未知数调换后的顺序 则 完全主元素消去法优缺点 完全主元素消去法步骤见P172 27 列主元素法考虑依次按列选主元素 然后换行 再进行消元计算 设已完成第1步 第k 1步计算 得到与原方程组等价的方程组其中 方框内为第k步选主元素区域 2 列主元素消去法 28 输入矩阵阶数n 增广矩阵A n n 1 对于 1 按列选主元 选取l 使 2 如果 交换A n n 1 的第k行与第l行元素 3 消元计算 回代计算 2020 2 20 29 列主元素消去法步骤见P173 矩阵运算描述列主元素消去法 30 先换行再消元 定理4 列主元素的三角分解 如果 为非奇异矩阵 则存在排列矩阵P 使得PA LU 其中L是单位下三角阵 U是上三角阵 例5 用列主元素消去法解方程组 我们用4位浮点数进行计算 解 消元 已知精确解 2020 2 20 回代计算解 高斯选主元消去法的步骤 注 该解若取两位有效数字 则与精确解完全相同 优点 数值稳定 修正方法 消元 回代 高斯 约当 Gauss Jordam 消去法 缺点 既消元 又回代 2020 2 20 32 3 高斯 约当 Gauss Jordan 消去法 高斯消去法始终是消去对角线下方的元素 Gauss Jordan消去法要消去对角线下方和上方的元素 假设G J消去法已完成第1步 第k 1步 得到与原方程组等价的方程组 其中 第k步计算 1 按列选主元 即确定ik 使 2 换行 交换的第k行和第ik行元素 3 消元计算 33 4 计算主行 主元素所在行 计算解 上述过程结束后 有 2020 2 20 34 说明 在解方程组 一般不用高斯 约当消去法 因为计算量太大 但是在解多个方程组而它们的系数矩阵相同时 用此方法 即求系数矩阵的逆矩阵A 1时 比较合适 设为非奇异矩阵 如果用列主元G J消去法将 A I 化为 I T 则 不用回代 将A化为单位矩阵 则解为常数项列 定理5 高斯 约当法求逆矩阵 优点 缺点 计算量较大 大约是次乘除法 注 该方法与高等代数中求逆矩阵方法的不同之处是有选主元 实际上选主元就是交换两行的位置 仍是初等变换 在一般的 求逆矩阵方法中也有交换两行元素 2020 2 20 35 例6 用列主元素G J消去法求的逆矩阵A 1 解 2020 2 20 36 所以 G J列主元求逆算法见P176算法3 2020 2 20 37 2020 2 20 38 作业 P19912 2020 2 20 39 3Gauss消去法的变形 直接三角分解法 直接从矩阵A的元素得到计算 U元素的递推公式 而不需要任何中间步骤 称之为直接三角分解法 这样 AX b L UX b LY b UX Y 不选主元的三角分解 Doolittle分解法 40 通过n步可以直接计算定出L U的元素 其中第r步确定U的第r行和L的第r列元素 第1步 设第r 1步已确定U的第r 1行和L的第r 1列元素 41 第r步 故 故 LU分解求解线性方程组 2020 2 20 42 直接三角分解法解AX b的计算公式 对于r 2 3 n 2 计算U的第r行元素 3 计算L的第r列元素 r n 1 2020 2 20 43 4 5 2020 2 20 44 例7 用直接三角分解法解 解 用分解计算公式得 求解 2020 2 20 45 2020 2 20 46 选主元的三角分解 选主元素三角分解算法见P179 2 平方根法 对称正定矩阵而言 矩阵的LDR分解 定理6 若n阶矩阵A的所有顺序主子式均不等于零 则矩阵A存在唯一的分解式A LDR 其中L和R分别是n阶单位下三角阵和单位上三角阵 D是n阶对角元素不为零的对角阵 上述分解也称为A的LDR分解 2020 2 20 47 平方根法 如果A为对称矩阵 且A的所有顺序主子式均不等于零 则A可唯一分解为A LDLT 其中L是n阶单位下三角阵和D是对角阵 定理7 对称矩阵的三角分解定理 2020 2 20 48 设A是对称正定矩阵 做LU分解 A对称 即 则仍是下三角阵 且有 2020 2 20 49 定理5 对称正定矩阵的三角分解或Cholesky分解 2020 2 20 50 如果A为对称正定矩阵 则存在一个实的非奇异下三角矩阵 使A LLT 且当限定的对角元素为正时 这种分解是唯一的 如何确定L呢 下面用直接法确定L中元素 2020 2 20 51 其中 注意到所以 因此 用平方根法解线性代数方程组的算法 1 对矩阵A进行Cholesky分解 即A LLT 由矩阵乘法 对于i 1 2 n计算 2020 2 20 52 2 求解下三角形方程组 3 求解LTX y 2020 2 20 53 改进平方根法 其中 2020 2 20 54 改进平方根法解对称正定方程组的算法 2020 2 20 55 令LTX y 先解下三角形方程组LDY b得 解上三角形方程组LTX Y得 2020 2 20 56 3 追赶法 2020 2 20 57 2020 2 20 58 4向量和矩阵的范数 1 向量范数 定义 设X Rn X 表示定义在Rn上的一个实值函数 称之为X的范数 它具有下列性质 3 三角不等式 即对任意两个向量X Y Rn 恒有 1 非负性 即对一切X Rn X 0 X 0 2 齐次性 即对任何实数a R X Rn 2020 2 20 59 由上可得 设X x1 x2 xn T 则有 1 2 3 三个常用的向量范数 范数等价 设 s和 t是Rn上任意两种范数 若存在常数c1 c2 0使得 则称 s和 t等价 2020 2 20 60 定理5 N x 的连续性 定义在Rn上的向量范数是X分量的连续函数 推论 Rn上定义的任何两个范数都是等价的 2020 2 20 61 对常用范数 容易验证下列不等式 2020 2 20 62 定义2 设为Rn中一向量序列 即 其中 若对任何i i 1 2 n 都有 则向量 称为向量序列的极限 或者说向量序列依坐标收敛于向量 记为 2020 2 20 63 定理7 13 向量序列依坐标收敛于X 的充要条件是 向量序列依范数收敛与依坐标收敛是等价的 定义3 设A为n阶方阵 Rn中已定义了向量范数 则称为矩阵A的范数或模 记为 即 2020 2 20 64 1 当A 0时 0 当A 0时 0 2 对任意实数k和任意A 有 3 对任意两个n阶矩阵A B有 4 对任意两个n阶矩阵A B 有 2020 2 20 65 2 矩阵的范数 定义3 矩阵范数 如果矩阵的某个非负的实值函数满足条件 则称是上的一个矩阵范数 模 2020 2 20 66 矩阵和向量相容的范数 其中 满足矩阵范数的定义 称为A的Frobenius范数 例5 设A aij M 定义 证明 这样定义的非负实数不是相容的矩阵范数 证明 设 从而 2020 2 20 67 定理8 设n阶方阵A aij n n 则 与相容的矩阵范数是 与相容的矩阵范数是 其中 1为矩阵ATA的最大特征值 与相容的矩阵范数是 上述三种范数分别称为矩阵的1 范数 2 范数和 范数 2020 2 20 68 可以证明 对方阵和 有 2020 2 20 69 3 矩阵范数与特征值之间的关系 定理9 矩阵A的任一特征值的绝对值不超过A的范数 即 定义4 矩阵A的诸特征值的最大绝对值称为A的谱半径 记为 并且如果A为对称矩阵 则 2020 2 20 70 注 Rn n中的任意两个矩阵范数也是等价的 定义5 设 为Rn n上的矩阵范数 A B Rn n 称 A B 为A与B之间的距离 定义6 设给定Rn n中的矩阵序列 若 则称矩阵序列收敛于矩阵A 记为 2020 2 20 71 定理10 设B Rn n 则由B的各幂次得到的矩阵序列Bk k 0 1 2 收敛于零矩阵的充要条件为 2020 2 20 72 求解时 A和的误差对解有何影响 设A精确 有误差 得到的解为 即 绝对误差放大因子 又 相对误差放大因子 5误差分析 2020 2 20 73 设精确 A有误差 得到的解为 即 Waitaminute Whosaidthat I A 1 A isinvertible 只要 A充分小 使得 大 2020 2 20 74 定义7 设A为n阶非奇异矩阵 称数为矩阵A的条件数 条件数的性质 cond A 1 cond kA cond A k为非零常数 若 则 2020 2 20 75 常用条件数有 cond A 2 特别地 若A对称 则 2020 2 20 76 例 Hilbert阵 cond H2 27 cond H3 748 cond H6 2 9 106 cond Hn 当n 注 现在用Matlab数学软件可以很方便求矩阵的状态数 定义2 设线性方程组的系数矩阵是非奇异的 如果cond A 越大 就称这个方程组越病态 反之 cond A 越小 就称这个方程组越良态 2020 2 20 77 一般判断矩阵是否病态 并不计算A 1 而由经验得出 行列式很大或很小 如某些行 列近似相关 元素间相差大数量级 且无规则 主元消去过程中出现小主元 特征值相差大数量级 2020 2 20 78 近似解的误差估计及改善 设的近似解为 则一般有 cond A 改善方法 1 Step1 近似解 Step2 Step3 Step4 若可被精确解出 则有就是精确解了 经验表明 若A不是非常病态 例如 则如此迭代可达到机器精度 但若A病态 则此算法也不能改进 2020 2 20 79 改善方法 2 对方程组进行预处理 即适当选择非奇异对角阵D C 使求解Ax b的问题转化为求解等价方程组DAC C 1x Db 且使DAC的条件数得到改善 P88 例3 10 用双精度进行计算 以便改善和减轻病态矩阵的影响 2020 2 20 80