矩阵A紧凑格式的Doolittle分解为课件.ppt

第三章线性方程组的解 1 精品课件交流 3 概述消元法三角分解法平方根法向量与范数方程组的性态与误差分析迭代法 2 3 22 2020 3 1概述 大量实际计算问题 一组线性方程组 如何求解 1 术语非齐次线性方程组 若记 则 1 1 式可表示为Am nx b 线性方程组的矩阵表示 分类 据方程的个数与未知数的个数间关系 分为 mn 即方程的个数大于未知数的个数 称为超定方程组 或矛盾方程组 它没有一般意义下的解 但可以求其广义解 m n 一般意义下的方程组 本章主要讨论的重点面临的问题 方程组Ax b有没有解 有多少解 如何求解 4 3 22 2020 2 Crammer法则求解An nx b方程组Ax b有唯一解的充要条件是 A 0 A可逆 A是非奇异矩阵Ax b在A可逆时 存在唯一解结论 Crammer法则计算量非常大 需算n 1个n阶行列式 如 n 100 1000次 秒的计算机要算10120年 3线性方程组的数值解法 直接法 思想 经有限步运算 求得精确解的方法 舍入误差 因此也是近似解 高斯消元法及其变形特点 它可靠且效率高 但它只适用于中小型方程组 迭代法 思想 构造适当的初始近似解向量x 按一定的法则 使之逐步逼近精确解 得到一个满足精度要求的近似解 即是用某种极限过程逐步逼近准确解的方法 主要方法 Jaccobi迭代法 Gauss Sidel迭代法等 6 3 22 2020 3 1 1GAUSS消元法 一 几种可以直接求解的线性方程组对角矩阵 n次除法 下三角矩阵 即 l11x1 b1l21x1 l22x2 b2l31x1 l32x2 l33x3 b3 li1x1 li2x2 liixi bi ln1x1 ln2x2 lnnxn bn 上三角矩阵 即 u11x1 u12x2 u1nxn b1u22x2 u2nxn b2 uiixi ui i 1xi 1 ui nxn biun 1 n 1xn 1 un 1 nxn bn 1un nxn bn 二 同解变换初等方阵 ri rj ri k 注对矩阵A实施初等行变换 对A左乘初等方阵初等方阵是可逆的 多个初等方阵的积仍然可逆可逆阵A经有限次初等行变换 单位矩阵 rj k ri 2 对方程组Ax b作如下的变换 解不变 交换两个方程的次序一个方程的两边同时乘以一个非0数一个方程的两边 再将之加到另一个方程将方程组Ax b对应的增广矩阵 A b 作如下变换 解不变交换矩阵的两行某行乘以一个非0数某行乘以一个非0数 加到另一行 增广矩阵第i行 第i个方程 12 3 22 2020 三 Gauss消元法 消元法基本思想 对Ax b的增广矩阵 A b 进行初等变换 变成可直接求解的三种形式之一 再求解Gauss消元法 将A化为上三角阵 回代求解 用高斯消去法解下列线性方程组原方程组对应的增广矩阵为 1 消元步骤 方程组AX b的矩阵表示为 A 1 x b 1 初始状态 第一次消元 消去对角线下第1列元素 a11 0 方法 消去对角线下第1列元素为0 即ri r1 ai1 a11 i 2 3 第二次 若a22 0 则消去对角线下第二列为0 即 ri r2 ai2 a22 i 3 4 经过k 1次消元后 增广矩阵变为 第k次消元 若akk 0 则消去对角线下第k列元素即 ri rk aik akk i k 1 k 2 2 经n次消元后得到同解方程组A n x b n 且A n 为上三角矩阵 可逐步回代求解 即 UX Y 3 算法步骤 将方程组用增广矩阵 A b aij n n 1 表示 注意c语言中数组下标从0开始 故i 0 1 n 1 j 0 1 n消元 对k 0 1 n 2 消去第k列对角线下的元素 计算li k ai k ak k第i行 第k行 li k i k 1 k 2 n 1 回代求解 xi ai n xjai j ai i i n 1 0 j i 1 i 2 n 1 21 3 22 2020 4 时间复杂度 消元过程中 第k次消元每行均需计算第k行要乘以的常数 lik aik akk 消去第i行 第k列 时 i行各列元素加上k行各列元素乘以常数lik aij aij akj lik j k k 1 n 故需做n k 1次乘法 加减法一共要做n k行综上 第k次消元 除法 n k次 乘法 n k n k 1 次 加减法 n k n k 1 次整个消元过程 除法 乘法 加减法 综上 算法时间度量为O n3 23 3 22 2020 5 Gauss顺序消元法的适用条件 GAUSS直接消元法的适用条件 akk k 0A的各阶顺序主子式均不为0时 有akk k 0 证明略 A是严格对角占优矩阵 则 akk k 0 证明略 举例说明 A的每行主对角元的绝对值 同行其余元素的绝对值之和 例2 用Gauss消元法解方程组 4位十进制机 0 0001x1 x2 1x1 x2 2因要对阶 损失有效数字 求得x1 0 x2 1显然x1 x2不是方程的解 怎么办 x1 x2 20 0001x1 x2 1解之 得到x1 1 x2 1 接近与精确解 25 3 22 2020 3 1 2列主元Gauss消元法 当采用Gauss消元法求解时 若 akk aik 会导致误差扩散第k步消元时 ri rk aik akk aij akj aik akk因为 akk aik 若rk行的误差为e ek 1 en 1 则e将被扩大 aik akk 倍 Gauss消元法在特殊情况下是不稳定的 26 3 22 2020 解决办法 选择列主元 即选出第k列对角线下绝对值最大者设 atk max aik k i nrk rt以新的akk作为主对角元进行消元故列主元消元法只是在每步消元之前选出主对角元举实例说明列主元Gauss消元法的计算过程 27 3 22 2020 列主元算法 只需在消元的第1步前增加以下几行代码i k 选择第k列的主元for j k 1 jfabs a i k i j if i k for j k j n j tmp a k j a k j a i j a i j tmp 28 3 22 2020 3 1 3Gauss Jordan消元法 算法思想 在Gauss消元的第k次消元时 只是利用akk 将第k行以下各行的第k列消元为0 最终将系数矩阵消元为s上三角阵 将上述算法改进 第k次消元时 用akk将第k列的所有元素 akk除外 均消元为0 则系数矩阵最终成为对角矩阵 或单位矩阵 29 3 22 2020 第k步消元 若akk 0 则消去除对角线外的第k列元素方法 计算 lik 即消去第k列元素 akk除外 为0 即ri rk lik 30 3 22 2020 第k 1次消元结果 第k次消元结果 31 3 22 2020 经过n次消元 原方程的增广矩阵变为 则 方程的根为 示例 Gauss Jordan消元法求解 33 3 22 2020 Gauss Jordan消元法的归一化 消元后对角线元素全为1 即单位矩阵E方法 第k次消元时 先将akk化为1 第k行除以akk 再用第k行消去各行k列的元素 34 3 22 2020 经过n 1次消元 则原方程的增广矩阵变为 则 方程的根为 35 3 22 2020 归一化Gauss Jordan消元法步骤 消元 c c 实现 对k 0 1 n 1 消去除对角线外第k列 第k行除以akk 将akk化为1第i行 第k行 aik i 0 1 n 1 且i k 增广矩阵最后一列ai n即为方程组的解 无需回代 36 3 22 2020 示例 用归一化的Gauss Jordan消元法求解 37 3 22 2020 归一化的Gauss Jordan消元法的应用可逆阵A经有限次初等行变换 单位矩阵故可利用Gauss Jordan消元法 构造矩阵 A E Gauss Jordan消元 E A 1 38 3 22 2020 示例 用Gauss Jordan消元法求矩阵的逆矩阵 39 3 22 2020 3 2矩阵的三角分解法 Gauss消元法的矩阵表示第一次消元 即 第一步消元 相当于左乘初等变换矩阵L1 相当于 L1A 1 A 2 L1b b 2 第二次消元 即 L2A 2 A 3 L2L1A 1 A 3 41 3 22 2020 经过n 1次消元后Ln 1Ln 2 L2L1A A n Ln 1Ln 2 L2L1b b n 故 A L1 1L2 1 Ln 2 1Ln 1 1A n 令L L1 1L2 1 Ln 2 1Ln 1 1 则 42 3 22 2020 故 A LA n LUGauss消元法的实质 将系数矩阵分解为两个三角矩阵的乘积将矩阵A分解成一个上三角 下三角矩阵的乘积 即 A LU 矩阵的三角分解 LU分解 43 3 22 2020 三角分解是从A的元素直接得到L U的元素 不用中间步骤 即不用消元 所以称直接三角分解 或直接分解 A的LU分解只要求L是一个下三角阵 U是一个上三角阵 当A有LU分解时 这种分解不是唯一的 当L是一个单位下三角阵或者U是一个单位上三角阵时 A的这两种LU分解是唯一的 44 3 22 2020 上述是A的两种不同的三角分解一般地 若A LU是一个三角分解 任取与A同阶的非奇异对角矩阵D 则A LD D 1U L1U1也是A的三角分解 45 3 22 2020 常用的两种分解 L为单位下三角阵而U为一般上三角阵的分解称为Doolittle分解 一般上三角 单位下三角 46 3 22 2020 L为一般下三角阵而U为单位上三角阵的分解称为Crout分解 一般下三角 单位上三角 47 3 22 2020 定理 n阶矩阵A存在唯一的杜利特尔分解 克洛特分解的充要条件是A的顺序主子矩阵Ak k 1 2 n 1 非奇异 各阶顺序主子式非0 证明略 反证法 若不唯一 则可设A L1U1 L2U2 推出 因下三角矩阵的积仍然是下三角阵 上三角矩阵的积仍然是上三角阵下三角阵 上三角阵 则两个必为单位矩阵 1 Doolittle分解 据矩阵的乘法 知 A的第一行元素 故第一列元素 故 A的第二行元素 故 第二列元素 故 A LU 一般地 50 3 22 2020 推而广之 比较A第k行 求U的第k行 比较A第k列 求L的第k列 即 53 3 22 2020 计算顺序为 为了便于记忆 将A的LU分解写成紧凑格式 1 2 3 4 5 6 对矩阵A进行Doolittle分解解 矩阵A紧凑格式的Doolittle分解为 对矩阵A进行Doolittle分解 并求 A 解 12 3 三角分解法解线性方程组 方程组Ax b 若A非奇异 且有三角分解A LU 则原方程组等价于 LUx b令 Ux y 则Ly b故可先解出y 再求x所以 等价于求U阵第k行元素ukj的公式 故可将增广矩阵 A b 同时做LU分解 则最后一列即为y 再用Ux y求解 例 用Doolittle分解法求解线性方程组 解 对增广矩阵进行Doolittle分解故 Ux y为 所以x3 1 x2 2 x1 2 2 用三角分解法求矩阵A的逆矩阵A 1 若AX E 则X A 1 2 Crout分解 类同于Doolittle分解比较两边可得 紧凑格式的Crout分解为 2 1 4 3 6 5 61 3 22 2020 原方程 AX b变为 LUX b令Ux y 则Ly b 可见yk的表达式完全类同于ukj的表达式 故可将常向量放在系数矩阵之后 对整个增广矩阵进行Crout三角分解 则UX y的解即为线性方程组的解 即 例3 11 分别用Doolittle Crout分解法求解线性方程组解一 Doolittle分解 1 2 y向量 则解Ux y可得线性方程组的解解之 得 x3 2 x2 1 x1 1 解二 Crout分解法则Ux y的解即为原方程组的解解之 得 x3 2 x2 1 x1 1 3 2 2 注意 此处与Doolittle方法的区别 3 追赶法解三对角线性方程组 概念 三对角矩阵 除主对角线 次主对角线上的元素外 其余元素均为0 对系数矩阵进行Crout分解 比较矩阵两边可得 故 A L U l1 l2 ln 定理3 6 定理 若A为对角占优的三对角阵 即 满足则方程组有唯一的LU分解证明 要证三对角方程组具有唯一的LU分解即要证 三对角方程组的各阶顺序主子式均 0也即要证 该方程组组的Crout分解中lii 0 69 3 22 2020 由于三对角矩阵的特殊性 无需用二维数组存放系数矩阵 而采用一维数组A B C D存放所有的非0元求解步骤 三角分解 A LU则方程组Ax f LUx f 令 Ux y 则Ly f故先解方程组Ly f 求出y 再解Ux y即可 70 3 22 2020 追 由Ly f 得 赶 再从Ux y 回代求解 示例 2 3 3平方根法 系数矩阵为对称正定矩阵的方程组称为对称正定方程组对称正定方程组可用高斯消去法 LU分解法求解也可导出计算量更小的平方根法利用对称正定矩阵的三角分解 Cholesky 求解对称正定方程组的方法称为平方根法对称矩阵 A AT对称正定矩阵A AT 且对任意非零向量x有 f x xTAx 0 73 3 22 2020 对称正定阵A的几个重要性质A 1亦对称正定 且aii 0A的顺序主子阵Ak亦对称正定A的特征值 i 0A的全部顺序主子式det Ak 0 74 3 22 2020 对称正定矩阵的乔累斯基分解对称正定矩阵A Rn n 存在唯一的单位下三角矩阵L和对角矩阵D 使A LDLT证明 前面已经证明了对称正定矩阵A做Doolittle分解的唯一性 设A LU 其中L为单位下三角矩阵 U为上三角矩阵 令 其中di为U阵对角线元素 故di 0则 A LD D 1U AT D 1U TDTLT D 1U TDLT 又A AT 故 LD D 1U D 1U DLT由上式知