线性方程组的数值解法.ppt

n阶线性代数方程组的一般形式为 第三章线性方程组的数值解法 问题的提出 写成矩阵 向量形式 若矩阵非奇异 即的行列式 根据克莱姆 Gramer 法则 方程组有唯一解 其中为系数矩阵 为解向量 为右端常向量 其中表示 表示中第列换成后所得的行列式 当阶数较高时用这种方法求解是不现实的 阶行列式有项 每项又是个数的乘积 对较大的 其计算量之大 是一般计算机难以完成的 而且 这时的舍入误差对计算结果的影响也较大 例如 求解一个20阶线性方程组 用加减消元法需3000次乘法运算 而用克莱姆法则要进行次运算 如用每秒1亿次乘法运算的计算机要30万年 直接法 经过有限步算术运算 可求得方程组的精确解的方法 若在计算过程中没有舍入误差 迭代法 用某种极限过程去逐步逼近线性方程组精确解的方法迭代法具有占存储单元少 程序设计简单 原始系数矩阵在迭代过程中不变等优点 但存在收敛性及收敛速度等问题 3 1消去法 消去法的基本思想 是通过将一个方程乘或除以某个常数 以及将两个方程相加减 逐步减少方程中的变元数 最终使每个方程只含一个变元 从而得出所求的解 消去法在线性代数中已有详细的讨论 在此只给出一些说明以及算法的具体描述 高斯消去法属于直接法 一般由 消元过程 和 回代过程 两部分组成 先举几个简单实例 再对一般n阶方程组说明高斯消去法的基本思想 消去法 3 1高斯消去法 按自然顺序进行的消元法 例1用高斯消元法求解方程组 解用第一个方程削去后两个方程中的得 再用第2个方程消去第3个方程中的得 最后 经过会代求得原方程组的解为 例2解方程组 解 消元 回代得 消去法 下面讨论一般n阶线性方程组的高斯消去法 记为 和的元素分别记为和 系数上标代表第1次消元之前的状态 第1次消元时 设对每行计算乘数 用乘以第1个方程 加到第个方程 消去第2个方程到第个方程的未知数 得即 其中 第次消元时 设第次消元已完成 即有其中 设 计算乘数 只要 消元过程就可以进行下去 直到经过消元之后 消元过程结束 得也即 这是一个与原方程组等价的上三角形方程组 把经过n 1次消元将线性方程组化为上三角形方程组的计算过程称为消元过程 当时 对上三角形方程组自下而上逐步回代解方程组 计算 即 称为各次消元的主元素 主元素所在的行称为主行 高斯消去法的计算步骤为 1 消元过程设 对 计算2 回代过程 综上所述 高斯消去法的框图如图3 1所示 从中可看出高斯消去法的计算机运算和存储方式的特点 1 按消元规则进行运算后 对角线以下元素为0 故对于对角线以下元素不用作计算 减小了计算量 3 对角线以上元素和常数变换后的元素仍放在原来的位置以节省存储单元 4 回代后的数值仍放在常数项存储单元这时单元中存放的就是输出值 定理2Ax b可用高斯消元法求解的充分必要条件是 系数矩阵A的各阶顺序主子式均不为零 高斯消元法的条件 定理1如果在消元过程中A的主元素 k 1 2 n 则可通过高斯消元法求出Ax b的解 引理A的主元素 k 1 2 n 的充要条件是矩阵A的各阶顺序主子式不为零 即 定理 高斯消去法求解阶线性方程组共需乘除法次数近似为 证明 见书P64 高斯消去法的计算量 例1解方程组 解法一用高斯消元法求解 取5位有效数字 用第一个方程消去第二个方程中的 3 1 2高斯主元素消元法 因而再回代 得 而精确值为显然该解与精确值相差太远 为了控制误差 采用另一种消元过程 解法二为了避免绝对值很小的元素作为主元 先交换两个方程 得到 再回代 解得 结果与准确解非常接近 这个例子告诉我们 在采用高斯消元法解方程组时 用做除法的小主元素可能使舍入误差增加 主元素的绝对值越小 则舍入误差影响越大 固应避免采用绝对值小的主元素 同时选主元素尽量的大 可使该法具有较好的数值稳定性 为避免上述错误 可在每一次消元之前增加一个选主元的过程 将绝对值大的元素交换到主对角线的位置 根据交换的方法可分成全选主元和列选主元两种方法 列主元素消元法 列选主元是当变换到第k步时 从k列的及以下的各元素中选取绝对值最大的元素 然后通过行交换将其交换到的位置上 交换系数矩阵中的两行 包括常数项 相当于两个方程的位置交换了 例 求解线性方程组 解法一 用列主元素消元法 方程组增广矩阵为 交换1 3行 列选主 消元 消元 回代计算解为 选主元 全选主元素消元法 全选主元是当变换到第k步时 从右下角n k 1阶子阵中选取绝对值大的元素 然后通过行交换与列交换将其交换到akk的位置上 并且保留交换的信息 以供后面调整解向量中分量的次序时使用 交换1 3行交换1 3列 回代计算得 从而原方程的解为 消元 消元 比较而言 Gauss顺序消去法条件苛刻 且数值不稳定 Gauss全主元消去法工作量偏大 算法复杂 对于Gauss Jordan消去法形式上比其他消元法简单 且无回代求解 但计算量大 因此从算法优化的角度考虑 Gauss列主元消去法比较好 消去法小节 3 2矩阵三角分解法 3 2 1矩阵三角分解原理应用高斯消去法解阶线性方程经过步消去后得出一个等价的上三角形方程组 对上三角形方程组用逐步回代就可以求出解来 这个过程也可通过矩阵分解来实现 将非奇异阵分解成一个下三角阵和上三角阵的乘积 称为对矩阵的三角分解 又称分解 高斯消去法解线性代数方程组的一种变形解法 杜里特尔分解 把分解成一个单位下三角阵和一个上三角阵的乘积 克劳特分解 把分解成一个下三角阵和一个单位上三角阵的乘积 杜里特尔分解A LU 杜里特尔分解 杜里特尔分解 一般算法 由矩阵乘法规则 即 由此可得的第一行元素和的第一列元素 当已得出的前行元素和的前列元素 则对于 由 又可得计算的第行元素和的第列元素的公式 所以 矩阵三角分解算法总结 有了矩阵A的LU分解计算公式 当求解线性方程组时 等价于求解 这时可归结为利用递推计算相继求解两个三角形方程组 系数矩阵为三角矩阵 用顺代 由求出 再利用回代 由求出 3 2 2解线性方程组的三角分解法 用杜里特尔三角分解法解线性方程组的计算方法 克劳特分解求方程组步骤 略 其它矩阵分解法求解特殊的线性方程组 平方根法 主要用于求解正定矩阵的线性方程组追赶法 主要用于求解特殊矩阵的三对角方程组见书P78 P87 用LU直接分解的方法求解线性方程组的计算量为 和高斯消去法的计算量的数量级基本相同 消去法和矩阵三角分解法比较 当方程组系数矩阵不变 只有右侧向量b变化时 用LU分解法比消去法速度快 因为右侧向量b的改变不影响LU的变化 高斯消去法和LU分解法是等价的 其关键是把一般方程组变为三角方程组 只是实现途径不同 向量收敛的定义 3 6迭代法 生成向量序列 x k 若 迭代法基本思想 将方程组Ax b A 0 转化为与其等价的方程组 x Bx f 雅可比迭代法 对线性方程组可以建立不同的迭代格式 下面介绍构造迭代格式的几种常用方法 雅克比迭代法和高斯 塞德尔迭代法 设方程组 分别从上式n个方程中分离出n个变量 如下 等价方程组 建立迭代格式 称为雅可比 Jacobi 迭代法又称简单迭代法 高斯 塞德尔迭代法 或缩写为 称为高斯 塞德尔 Gauss Seidel 迭代法 例1用雅可比迭代法解方程组 雅克比迭代格式 Gauss Seidel 迭代格式为 例2用Gauss Seidel迭代法解上题 取x 0 0 0 0 T计算如下 以上介绍的两种迭代法 一般地说 高斯 塞德尔比雅克比要好 但也不完全是这样 关于迭代法的一些问题 为了使迭代法计算加速 可采用松弛法 略 迭代法存在收敛性问题 略 3 3向量与矩阵的范数 问题的提出 向量范数概念是三维欧氏空间中向量长度概念的推广 在数值分析中起着重要作用 为了研究线性方程组近似解的误差估计和迭代法的收敛性 我们需要对 n维向量空间 中向量及 维矩阵空间 中矩阵的 大小 及 距离 引进某种度量 向量与矩阵范数的概念 平面向量x大小 用距离反映 3 3向量与矩阵的范数 引入范数的目的 实数大小 用绝对值反映 复数大小 用模反映 高维空间向量x 大小 用反映 将度量长度数值的计算方法引入高维空间 用来反映空间向量的大小 就是范数的概念 为了研究线性方程组近似解的误差估计和迭代法的收敛性等 3 3 1向量的范数 由定义可知 向量的范数是按一定规律与对应的实数 该实数的值没有确定 但只要满足这三个条件 这个实数就是向量的一种范数 因此定义中的三个条件称为范数公理 当时 向量范数有如下性质 证 利用条件 有 证 它们分别叫做向量的 范数 1 范数 2 范数 p 范数 0 p p 范数是以上范数的统一表达形式 常用的向量范数 满足定义的范数不是唯一的 设x x1 x2 xn T 常用的向量范数有 对于 范数 有 当时 有 只有当时 才有 对任意实数 因为 所以 对任意向量 有 因此是n维空间的一种范数 例 范数的证明 不难证明这几种范数满足下述关系 事实上 对Rn上任意两种向量范数 x x 都存在与x无关的正常数c1 c2使 这种性质称为向量范数的等价性 按不同方式规定的范数 其值一般不同 但在各种范数下考虑向量序列收敛性的结论是一致的 即向量序列如对某一种范数收敛则对其它范数也收敛 且有相同的极限 这样 在研究某一具体问题时 可以选择一较易简单的范数 矩阵范数是用于定义矩阵 大小 的量 由于在大多数与估计误差有关的问题中 矩阵和向量的乘积经常出现 所以希望引进一种矩阵的范数 它与向量范数有某种关系 3 3 2矩阵的范数 矩阵范数的性质 且仅当时 对任意实数 对同维方阵 有 相容性条件 由矩阵范数的定义可直接得到 即有 称为相容性条件 即所给的矩阵范数与向量范数是相容的 证明p92 矩阵范数与向量范数的关系 证明 矩阵范数与向量范数的关系 常用的矩阵范数有 矩阵范数的求取 它们分别叫做矩阵的 范数 1 范数 解 验证相容性 3 4方程组的性态 3 4 1方程组的性态和矩阵的条件数 例1解方程组其中 现用绝对精确的计算 即不带任何舍入误差的计算 求解 可以看出 此时 我们发现对于两组不同的自由项 它的差只有 而所得解与之差却是 两组不同的右端其分量之差不过是可是解的差高达之1860倍像这样的方程组或矩阵A就叫做病态的 定义1若方程组Ax b的系数矩阵A或右端向量b的微小变化 小扰动 引起解产生巨大变化 则称此方程组为病态方程组 A称为病态矩阵 否则称为良态方程组 A称为良态矩阵 定理 设非奇异 且则 为了定量地刻划方程组的 病态 程度 下面就一般方程组进行讨论 首先考察右端项b的扰动对解的影响 证 设x为Ax b的准确解 当方程组右端有小扰动 b而A准确时 受扰解为x x 即A x x b b因为Ax b所以 x A 1 b 因此 所以 此不等式表明 解的相对误差不超过b的相对误差的 A A 1 倍 矩阵的条件数与范数有关 通常使用的条件数有 例求矩阵A的条件数 其中 解 于是从而 所以A是病态的 由于计算条件数涉及到计算逆矩阵 很麻烦 因此实际计算中一般通过可能产生病态的现象来判断 若在消元过程中出现小主元 则A可能是病态矩阵 但病态矩阵未必一定有这种小主元 若解方程组时出现很大的解 则A可能是病态矩阵 但病态矩阵也可能有一个小解 从矩阵本身看 若元素间数量级相差很大且无一定规律 或者矩阵的某些行或列近似相关 这样的矩阵则有可能是病态矩阵 3 4 2直接法的精度分析 定理 设是方程组的一个近似解 其精确解记为 为的余量 则有 该定理给出了方程组近似解的相对误差界 即相对误差的事后估计 要求熟练掌握的内容 高斯消去法原理 算法 计算步骤 主元消去法的意义 算法 计算步骤 矩阵三角分解法解方程组的意义 算法 计算步骤向量和矩阵范数的定义 性质和计算方法 矩阵条件数的定义 并能估计直接法的误差 要求掌握的内容 采用雅可比迭代解线性方程组 采用高斯塞德尔迭代解线性方程组 本章要求 逆阵的求法 代数余子式 用消去法求逆阵 AI IB 高斯 约当消去法 在工程实际中 线性方程组大多数的系数矩阵为对称正定这一性质 因此利用对称正定矩阵的三角分解式 即乔累斯基分解 是求解对称正定方程组的一种有效方法 其分解过程无需选主元 且计算量比高斯消去法 LU分解法要小 还有良好的数值稳定性 3 3对称正定矩阵的乔累斯基分解 了解内容 A对称 AT AA正定 A的各阶顺序主子式均大于零 即 定义 对称正定矩阵 定理 设A为对称正定矩阵 则存在唯一分解这种分解称为乔累斯基分解 其中L为具有主对角元素为正数的下三角矩阵 缺点 存在开方运算 可能会出现根号下负数 证明 分解方法 略 乔累斯基分解 利用乔累斯基分解求解对称正定方程组称为平方根法 A LDLT L为单位下三角矩阵 改进乔累斯基分解 利用改进乔累斯基分解求解对称正定方程组称为改进平方根法 利用改进平方根法求方程组 计算公式