三角分解解线性方程组的公式.ppt

February16 2020 yfnie 1 的求解过程为 可推导求解单位下三角形方程组的递归公式为 求解上三角形方程组的递归公式为 三角分解解线性方程组的公式 February16 2020 yfnie 2 直接三角分解法 发现计算的规律与计算的规律相同 因此计算的求方程组的过程可用三角分解的紧凑格式取代 事实上 这只要把做为A的第n 1列进行直接三角分解即可 Reamrk 上述直接三角分解法所对应的是Gauss顺序消去法 二者的乘除运算次数是相当的 实际中对阶数较高的线性方程组 应采用选主元的三角分解法求解 以保证计算结果的可靠性 续 February16 2020 yfnie 3 设对的分解已完成k 1步 即L的前k 1列 U之的前k 1行已求出 第k步计算 先选主元 再计算列 最后计算行 3 3列主元直接三角分解法 参选主元量 若 则需将第k行与第ik行完全交换 这样满足前面情形 按第一种情形实施计算 February16 2020 yfnie 5 1 正定矩阵的Cholesky分解 定义 设A为n阶对称正定矩阵 L是非奇异下三角矩阵 称为矩阵A的Cholesky分解 定理 n阶对称正定矩阵A一定存在分解 其中L为单位下三角阵 D是对角元全为正的对角阵且这种分解式唯一 其中L为下三角阵 当限定L的对角元为正时的分解式唯一 Cholesky分解 3 4平方根法 Cholesky分解 February16 2020 yfnie 6 证明 因为 平方根法 Cholesky分解 定理证明 February16 2020 yfnie 7 D可逆 平方根法 Cholesky分解 即 由Doolittle分解的唯一性 及的分解过程可知该分解式的唯一性 续1 由Doolittle分解的唯一性有 February16 2020 yfnie 8 改写 则 这时为一般的下三角矩阵 故 若的对角元全为正时 由Doolittle分解的唯一性及上述分解的推理过程 可以得到Cholesky分解的唯一性 平方根法 Cholesky分解 续2 February16 2020 yfnie 9 第一步 平方根法 Cholesky分解 分解公式 设L前k 1列元素已求出 则第k步 February16 2020 yfnie 10 平方根法 Cholesky分解 February16 2020 yfnie 11 在分解过程中有n次开方运算 故Cholesky分解法也称为平方根法 用Gauss顺序消去法求解对称正定的方程组Ax b 由 用平方根法解对称正定的方程组时 不必考虑选主元的问题 算法本身数值稳定 这表明用Gauss顺序消去法求解对称正定方程组也不用选主元 几点说明 February16 2020 yfnie 12 从运算量的角度看 平方根法是有利的 用平方根法解Ax b所需乘除法的运算次数为 令有n次开方运算 n次开方运算一般使用迭代法 所需乘除法的运算次数大约为n的常数倍 故平方根法总的乘除法运算次数大约为 为避免开方运算 也可对A做分解 续 February16 2020 yfnie 13 矩阵对角占优的概念 类似地 也可定义按列对角占优和按列严格对角占优的概念 通常的对角占优是指按行或者按列 则称矩阵A按行严格对角占优 则称矩阵A按行对角占优 3 5三对角线性方程组求解 February16 2020 yfnie 14 满足严格对角占优条件 严格对角占优的矩阵行列式不等于零 故该系数矩阵的各级顺序主子式不等于零 追赶法解三对角方程组 February16 2020 yfnie 15 若A为上述三对角阵时 则A有三角分解 追赶法解三对角方程组 分解公式 February16 2020 yfnie 16 追赶法解三对角方程组 由得 由得 方程求解公式 February16 2020 yfnie 17 追赶法解三对角方程组 Remark 只要三对角矩阵按行严格对角占优 则追赶法定能进行下去 且计算过程是稳定的 不必选主元素 其乘除法运算次数为5n 4 上述方法称为解三对角方程组的追赶法 又称为Thomas方法 说明 February16 2020 yfnie 18 其中Ai Bi Ci均为q阶矩阵 是q维向量 对于这种方程组 可以类似地建立追赶法 追赶法解块状三对角方程组 February16 2020 yfnie 19 追赶法解块状三对角方程组 其中I为q阶单位矩阵 Li和Ui是q阶矩阵 根据矩阵的分块运算 容易求得块三对角方程组的追赶法如下 续 February16 2020 yfnie 20 追赶法解块状三对角方程组 续2 February16 2020 yfnie 21 4 1向量范数 1 定义 设的某个实值函数满足 3 三角不等式 2 齐次性 c为任意实数 1 非负性 当且仅当时有 0 则称是上的一个向量范数 4矩阵的条件数和方程组的性态 February16 2020 yfnie 22 证明 故必有 命题1向量范数具有性质 4 1向量范数 连续性定理 设为上的某种范数 则为分量 的连续函数 证明 February16 2020 yfnie 23 对任意给定正数 向量范数范数连续性证明 February16 2020 yfnie 24 等价性定理 设是上的两种向量范数 则存在与无关的常数 使得 证明 当时上式显然成立 故假设 首先证明存在常数 由连续性定理结论成立 等价性定理 February16 2020 yfnie 25 向量范数的性质 联合即得 即 其中 续 February16 2020 yfnie 26 1 定义 如果矩阵A的实值函数 满足 1 正定性 当且仅当A 0 2 齐次性 c为实数 3 三角不等式其中A B 4 则称是上的一个矩阵范数 特别地 若还具备特性 5 为的某种向量范数 则方阵范数特别叫做与向量范数相容的方阵范数 4 2矩阵范数 February16 2020 yfnie 27 称为A的行范数 称为A的列范数 称为A的2一范数 其中表示的按模最大的特征值 称为A的F一范数 常用的矩阵范数 February16 2020 yfnie 28 设 A 给出一种向量范数 p 1 2或等 定义矩阵的非负函数 是上矩阵的一种范数 称为A的算子范数 也称从属范数 Remark 向量范数所导出的矩阵范数与该向量范数是相容的 矩阵的算子范数 February16 2020 yfnie 29 证明 常用向量范数与矩阵范数间的关系 February16 2020 yfnie 30 即对任何非零向量有 a 下面来说明有一向量使 设在第行达到 即 算子范数 续 证明 February16 2020 yfnie 31 且A的第个分量为 即有 b 结合 a b 得 取向量其中 j 1 2 n 2 证明与 1 类似 算子范数 续 这说明 证明 February16 2020 yfnie 32 3 因A为实矩阵 故为实对称的 并且还是非负定的 设为任一非零向量 则有 故 算子范数 续 证明 February16 2020 yfnie 33 即 从而得到 取 则 算子范数 续 证明 February16 2020 yfnie 34 背景 实际求解方程组Ax b时 A和b都可能有微小变化 如计算机计算时产生的舍入误差 采集数据误差等 此时方程组的解会如何变化 例 求解方程组 该方程组的精确解是x1 x2 1 考虑系数矩阵及右端项有微小扰动的方程组 该方程组的精确解是x1 2 x2 8 5 扰动方程组解的误差界 February16 2020 yfnie 35 从上例可看出 虽系数矩阵和右端向量变化很小 但解的误差却很大 这说明该方程组的解对系数矩阵和右端项的扰动很敏感 事实上 该方程组的系数矩阵行列式仅为 0 002 方程组的解为两条接近平行的直线的交点 因而当其中一条直线稍微变化时 新交点与原来的交点相偏离很远 方程组的这种扰动性质是由其系数矩阵的固有性质所确定的 举例分析 February16 2020 yfnie 36 定理 设有方程组Ax b 其中A非奇异 设A和b有微小扰动 A和 b 扰动后的方程组为 这里用到向量范数和矩阵范数相容 则当时 有误差估计 扰动方程组解的误差界 证明 将扰动方程组与原方程组相减 得 February16 2020 yfnie 37 扰动方程组解的误差界 续 因Ax b 故上式为 故 证明 February16 2020 yfnie 38 扰动方程组解的误差界 Remark 若方程组仅有右端扰动 b 即 A 0时 解的误差界为 若方程组仅有系数矩阵扰动 A 即 b 0时 解的误差界为 结论 解的相对误差是在扰动相对误差和的基础上通过量所刻划的 其大小反映了解的相对误差的大小 分析 February16 2020 yfnie 39 定义 设A是n阶非奇异矩阵 称为矩阵A的条件数 由此可见 当Cond A 较大时 A和b的小扰动可能引起解的较大误差 故条件数Cond A 刻划了方程组Ax b的性态 条件数 February16 2020 yfnie 40 例 n阶Hilbert矩阵 例 February16 2020 yfnie 41 Remark 对于给定的Ax b 计算涉及到矩阵求逆 按照定义 若Ax b的解x和有小扰动的方程组的解误差很大 则原方程组是病态的 但这并不是一个实用的判断方法 一种可能的情况是 若接近于零或者说A的行向量组 或列向量组 近似线性无关 则有可能方程组Ax b病态 至于是否接近于零 可在列主元消去法的进行过程中观察是否某个主元绝对值很小而进行判断 说明 February16 2020 yfnie 42 矩阵的条件数和方程组的性态 另外一种情况是 当A的元素数量级差别很大并且无一定规则时 方程组Ax b可能病态 如 相应的方程组Ax b是病态的 但对于 相应的方程组Ax b是良态的 续 February16 2020 yfnie 43 一般病态方程组的求解是比较困难的 方程组给定 其系数矩阵的条件数就随之确定 所以方程组的性态是方程组的固有性质 与求解方法无关 一般来说 在计算机上求解的方程组都是所给方程组的扰动方程 这是因为计算机存储数据的舍入误差所致 对于良态方程组 只要求解方法稳定 即可得到比较满意的计算结果 但对于病态方程组 即使用稳定性很好的算法求解也未必得到理想的结果 对于病态方程组Ax b的求解 可在计算实践中考虑下述方法的使用 关于病态方程组的求解 February16 2020 yfnie 44 关于病态方程组的求解 1 采用高精度的算术运算 如采用双精度运算 使由于舍入误差的放大损失若干有效位数之后 还能保留一些有效位数 从而改善和减轻 病态 的影响 2 对原方程组作一些预处理 如进行矩阵平衡 以降低矩阵的条件数 矩阵平衡就是给A的每一行 或每一列 分别乘以适当的常数 即找可逆的对角阵D1和D2 使方程组Ax b转化为 D1AD2y D1b D2y x 理论上应选择D1和D2 使Cond D1AD2 min 但实际上这很难实现 一般矩阵的平衡只是针对具体问题进行具体的处理 续 February16 2020 yfnie 45 关于病态方程组的求解 一种