《线性代数方程组》PPT课件.ppt

第3章线性方程组求解的数值方法 1n阶线性代数方程组的一般形式 解线性代数方程组的数值解法有 直接法 迭代法 在没有舍入误差的情况下 经过有限次运算可以得到方程组的精确解的方法 线性代数方程组的直接解法 DirectMethodforSolvingLinearAlgebraicSystems 求解 Cramer法则 所需乘除法的运算量大约为 n 1 n n 20时 每秒1亿次运算速度的计算机要算30多万年 直接法 3 1Gauss消去与矩阵LU分解 一Gauss消去1直接法的关键思想如果方程组是 上三角方程组 或 下三角方程组 就可以很容易地求出方程组的解 因此 直接法的关键思想就是如何把一般方程组约化为上 下三角方程 属于解方程的直接法 2上三角方程组与回代过程 3下三角方程组与前推过程 4Gauss消去过程 则Gauss消去过程如下 该Gauss消去法为顺序高斯消去法 Gauss法的消元过程 回代过程 顺序高斯消去法必须保证第k步的akk 0 因为它在消去过程和回代过程中起关键作用 所以称它为主元素 例 用基本Gauss消元法求解下列方程组 解 增广矩阵 基本Gauss消元法的工作量 消元过程 回代过程 加减法的次数 乘除法的次数 基本Gauss消元法的实现条件 小主元可能导致计算失败 8个 解 主元素要作除数 其绝对值相对于被除数过小会影响到计算的精度 所以 我们可以采用 5 列主元Gauss消去法解方程组 除了 列主元消去法 还有 全主元消去法 但后者计算量过大 一般不用 思想 每次消元之前 在剩余元素中选择绝对值最大的非零元素作为主元 然后经过换行换到主元位置 列主元消去法 ColumnPivotingStrategies Stepk 第k步首先选择主元 寻求满足 然后交换矩阵的第行和行 再进行消元过程 算法 Gauss列主元消去算法求方程组Ax b的解 输入 增广矩阵An n 1 A b 输出 近似解xk ak n 1 k 1 2 n 或失败信息 消元过程fork 1 2 n 1doStep1 Step4Step1寻找行号ik 使得Step2如果 则交换第k行和ik行 否则转Step7 算法 Gauss列主元消去算法 续 Step3fori k 1 n计算Step4forj k 1 n 1计算回代过程Step5Step6fori n 1 1计算Step7Output 系数矩阵奇异 不成功 STOP 例 用Gauss列主元消去法求解下列方程组 解 首先写出增广矩阵 Step1 Step2 全主元消去法 CompletePivotingStrategies Stepk 第k步选择主元 寻求和满足 然后交换矩阵的第行和行 第列和列 二LU分解 1矩阵的三角分解对方程组Ax b的顺序Gauss消去过程的结果 就是把矩阵A分解成两个三角距阵L和U的乘积 A LU 利用这个特点可以进行线性方程组的直接三角分解法 解方程组的直接三角分解法有3种形式 1 A LU 2 A L U 3 A LDU 单位下三角阵 上三角阵 下三角阵 单位上三角阵 单位下三角阵 对角阵 单位上三角阵 A的Doolittle分解 A的Crout分解 A的LDU分解 2解方程组的直接三角分解法 Ax b LUx b Doolittle分解法 本质 它是基本Gauss消元法的一种等价变形 Gauss消元法的矩阵形式 MatrixForm 为上三角矩阵 为单位下三角 矩阵分解为单位下三角和上三角矩阵的乘积 设 矩阵分解的计算公式 根据矩阵的乘法 由对应元素相等 得到 分解计算过程 Step1 Step2 Step3 Step4 Step5 Step6 方程组求解的计算公式 先求解方程组 再求解方程组 例8 用Doolittle分解法求解下列方程组 解 系数矩阵 3 2乔列斯基 Cholesky 分解法 平方根法 实对称正定矩阵的几个重要性质 A 1亦对称正定 且aii 0 A的顺序主子阵Ak亦对称正定 A的特征值 i 0 A的全部顺序主子式det Ak 0 充要条件 证明 设 则的所有顺序主子式为正 矩阵存在Doolittle分解 易证 其中为的主对角元素 且有 单位上三角 记 由矩阵的分解的唯一性知 思想 Cholesky分解的计算公式 设 由对应元素相等得 Cholesky分解公式 因对称性无需存储 Step1 Step2 Step3 的计算过程 例10 用Cholesky分解法求解下列方程组 解 系数矩阵为 Step1 Step2 Step3 求解方程组 求解方程组 Cholesky分解法求解方程组中需说明的几个问题 工作量 约为分解的一半 不必选主元 的正定性和稳定性 稳定性 是数值稳定的 缺陷 存在开平方运算 改进方法 分解 改进的平方根法 改进的平方根法 ModifiedSquareRootingMethod 当时 Step1 Step2 Step3 时 例6 用改进的平方根法求解下列方程组 解 系数矩阵为 Step1 Step2 Step3 求解方程组 求解方程组 求解方程组 等价方程组 先求解方程组 再求解方程组 方程组求解的实际计算公式 3 3向量范数与矩阵范数 一向量范数1定义设向量x Rn 若与x对应的一个实值函数 并记为 x 满足 x 0 其中 x 0当且仅当x 0 称为正定性 kx k x k R 称为齐次性 x y x y 且x y Rn 称为三角不等式 例 设x 2 4 3 T 求 x 1 x 2和 x 称为矩阵ATA的谱半径 3 4线性代数方程组的迭代解法 IterativeMethodforSolvingLinearAlgebraicSystems 求解 迭代法 从一个初始向量出发 按照一定的递推格式 产生逼近方程组的近似解序列 迭代法是一种逐次逼近的方法 与直接法比较 具有 程序简单 存储量小的优点 特别适用于求解系数矩阵为大型稀疏矩阵 sparsematrices 的方程组 思路 二 Jacobi迭代法 2J法的迭代矩阵 B称为迭代矩阵 f称为常数项 二Gauss Seidel迭代 2 GS法迭代矩阵 一般情况下 迭代公式用来计算x的值和求迭代矩阵 迭代矩阵用来分析迭代是否收敛 J法适用于并行计算 GS法适用于串行计算 并且所需要的存储空间较小 3 5迭代法的分析 由该定理可知 只要迭代矩阵的谱半径小于1 则J法和GS法收敛 定理3 2 如果A是严格对角占优矩阵 则它一定非奇异 定理3 3 如果方程组的系数矩阵A是严格对角占优的 则对任意初始近似值 Jacobi迭代法和G S迭代法均收敛 证明 3 6超松弛 SOR 迭代法 OverrelaxationIteration 一 超松弛 SOR 迭代法 思想 类似于G S迭代法的改进方法 利用第k次迭代值和第k 1次的G S迭代值作加权平均 G S迭代法的计算公式 作加权平均 超松弛 SOR 迭代法的分量形式 其中称为松弛因子 时即为G S迭代 SOR迭代法的迭代矩阵 记 超松弛 SOR 迭代法的迭代公式 解 SOR迭代法的迭代公式 方程组的近似解 的值 求解方程组的SOR法收敛的必要条件是 二 SOR迭代法的收敛性 3 7线性方程组的条件 对方程组的右端b作一个 微小 变化 考虑系数矩阵及右端项的微小变化对方程解的影响 如果对系数矩阵作 微小 改变 如何评价方程组的 好坏 分别考虑右端项及系数矩阵变化对解的