LU分解法的与特殊方程组的解法.ppt

LU分解法的与特殊方程组的解法 假定我们能把矩阵A写成下列两个矩阵相乘的形式 A LU其中L为下三角矩阵 U为上三角矩阵 这样我们可以把线性方程组Ax b写成Ax LU x L Ux bLy b令Ux y 则原线性方程组Ax bUx y于是可首先求解向量y使Ly b然后求解Ux y 从而求解线性方程组Ax b的目的 LU分解法的基本思想 内容 LU分解 关键词 1 LU分解 将系数矩阵A转变成等价两个矩阵L和U的乘积 其中L和U分别是下三角和上三角矩阵 而且要求U的对角元素都是1 2 紧凑格式 由于可以把L和U两个矩阵压缩到一个数组中 而且还可以存储在原来的系数矩阵A的数组中 这种LU分解常被称为紧凑格式 由LU A及对L和U的要求可以得到分解的计算公式 根据下式 Doolittle分解 1l211l31l321 ln1ln2 lnn 11 u11u12u13 u1nu22u23 u2n un 1nu n 1 nunn a ann LU 第j个分量 第i个分量 根据矩阵乘法及相等的定义 有 得公式u1j a1jj 1 2 nli1 ai1 u11i 2 3 n 在计算机程序中常常用这种方法解线性代数方程组 它的优点是存储量很省 L和U中的三角零元素都不必存储 就是U的对角元素也因为都是1没有必要再记录在程序中 这样只用一个n阶方阵就可以把L和U贮存起来 即 下三角 包括对角元 存储L各元素而上三角存储U的元素 再考察公式S会发现A中任一元素aij只在计算lij ji 中用到一次以后就不再出现了 因而完全可以利用原始数组A的单元 一个个逐次贮存L或U中的相应元素 即 a11a12a13 a1nu11u12u13 u1na21a22a23 a2nl21u22u23 u2na31a32a33 a3nl31l32u33 u3nan1an2an3 annln1ln2ln3 unn 1 3 5 2n 1 2 4 6 2n 采用LU分解有如下特点 1 LU分解与右端向量无关 先分解 后回代 一般说来 分解的运算次数正比于n回代求解正比与n 求遇到多次回代时 分解的工作不必重新做 这样节省计算时间 2 分解按步进行 前边分解得到的信息为后边所用 3 A 阵的存储空间可利用 节省存储 3 2 特殊方程组的解法 1 追赶法2 LDLT分解法 1 追赶法 追赶法与稀疏线性方程组追赶法仍然保持LU分解特性 它是一种特殊的LU分解 充分利用了系数矩阵的特点 而且使之分解更简单 得到对三对角线性方程组的快速解法 因三对角矩阵的非零元素呈 带状 我们也因此将它叫做带状矩阵 三对角线性方程组 设有方程组Ax d 其中A为三对角矩阵 假设系数矩阵A满足条件 对A作Crout分解形式为 第i个分量 第j个分量 追赶法计算公式 定理如果上带宽为q 下带宽为p的n阶带状矩阵A有Doolittle分解 A LU 则L是下带宽为p的单位下三角矩阵 U是上带宽为q的上三角矩阵 下面举实例用追赶法来解三对角方程组 实际问题中 当求解方程组的系数矩阵是对称矩阵时 则用下面介绍的LDLT分解法可以简化程序设计并减少计算量 从定理可知 当矩阵A的各阶顺序主子式不为零时 A有唯一的Doolittle分解A LU 此时 当然有 所以矩阵U的对角线元素uii 0 i 1 2 n 将矩阵U的每行依此提出uii 2 LDLT分解法 由A AT 得由分解的唯一性有 即 于是可得下面的结论 定理3 若对称矩阵A各阶顺序主子式不为零时 则A可以唯一分解为A LDLT 这里 LT为L的转置矩阵 当A有LDLT分解时 利用矩阵运算法则及相等原理易得计算ljk及dk的公式为 k 1 2 n j k 1 k 2 n 为减少乘法次数 引入辅助量ujk ljkdk 则上面公式可写成 平方根法设A为正定矩阵 则它的各阶顺序主子式均为