LU矩阵分解.ppt

算法的数据组织 本节习题 * * 华长生制作 华长生制作 第三章 线性方程组的解法 3.3 LU分解与矩阵求逆 3.3 LU分解与矩阵求逆问题 3.3.1 LU分解 行变换相 当于左乘 初等矩阵 Gauss消去法的消元过程矩阵描述:消元的每一步等价于左乘初等下三角矩阵，即：k=1,有 其中 第k次消元 有 即 因此,消元完成后,有 故 从而 U=A(n-1) (3-6) 即 且 顺序主元 定义.称A=LU（3－7）式为矩阵A的LU分解或三角分解。当L为单位下三角矩阵时，称为Doolittle分解。当U为上三角矩阵时，称为Crout分解。 解:由上述分析不难得到 问题：矩阵A存在LU分解（即Gauss消去法可以执行）的条件是什么？ Gauss消去法 可以执行 定理3.1 [证] 存在性证明见前； 唯一性证明（略）. 3.3.2 基本的三角分解法(Doolittle法) 上式可记为 导出U 同样,由 导出L 综合以上分析,有 因此可以推导出 U的第一行 L的第一列 ------(3.9) ------(3.10) U L U的第r行------(3.11) (逐行算出) L的第r列------(3.12) (逐列算出) 称上述(3.9) ~ (3.12)式所表示的分解过程为Doolittle分解 思考 对于线性方程组 系数矩阵非奇异,经过Doolittle分解后 Ax=L(Ux)=b可化为下面两个三角形方程组 消去 回代 L= 上述解线性方程组的方法称为三角(LU)分解的 Doolittle法. Doolittle法的特点:紧凑(无中间过程);内积计算(精度高) 例3. 3 用Doolittle法解方程组 解:由Doolittle分解 逐行算出U的元素逐列算出L的元素 逐行算出U的元素逐列算出L的元素 Doolittle法在计算机上容易实现,但若按上述流程运算需要较大的存储空间: A,b,x,L,U,y都需要单独存储,而从lij,uij的计算过程知: 因此可按下列方法存储数据: 直接三角分解的Doolittle法可以用以下过程表示: 存储单元(位置) 计算(3-9)~(3-14)得出的元素可按下框排列: 其中()为老值(A,b),外为新值(LU,y).计算顺序逐框进行:逐行算出U的元素uij;逐列算出L的元素lij.该分解又称为LU分解的紧凑格式(Doolittle分解). 例3.4 用紧凑格式的Doolittle法解方程组(例3.3 ) 解: