第三章 线性方程组的解法 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 因此可以推导出 U的第一行 ------(3.9) L的第一列 ------(3.10)
思考 U的第r行------(3.11) (逐行算出) L的第r列------(3.12) (逐列算出) 称上述(3.9) ~ (3.12)式所表示的分解过程为Doolittle分解 思考
对于线性方程组 系数矩阵非奇异,经过Doolittle分解后 Ax=L(Ux)=b可化为下面两个三角形方程组 消去 回代 L=
上述解线性方程组的方法称为三角(LU)分解的 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 ) 解:
所以
问题:在Doolittle法(包括LU分解紧凑格式)中,会反复用到公式 仍有可能为小主元做除数? 为此, 也应考虑在算法中加入选取列主元即紧凑格式的 Doolittle列主元法(略).
Doolittle法的特点:紧凑(无中间过程);内积计算(精度高) 说明:若计算没有舍入误差,用Gauss消去法和Doolittle法求得的结果应相同.但在计算机上计算,能产生不同的结果. 按矩阵三角分解法(Doolittle)的公式(3-9)~(3-12)中有内积计算Σxiyi,可以用双精度运算.当完成内积计算后再舍入成单精度.
3.3.3 矩阵求逆问题 常使用LU分解求解系列方程组 求解时分两步: 分解: A=LU 对j=1,…,m, 解: 比较:用Gauss消去法解(3-16),计算量约O(1/3mn3);用LU分解求解计算量约O(1/3n3+mn2);后者优于前者.
当A可逆,有AA-1=I. 若记A-1=(X1,X2,…,Xn), I= (e1,e2,…,en), (Xi€Rn)有 AXi=ei , (i=1,…,n) (3-17) 即A-1=( X1,X2,…,Xn)可从n个 AXi=ei 的解得到. (3-17)系数阵相同,右端项不同.利用LU分解求解A-1是 很好的方法. 实际中应尽量避免求逆矩阵的问题. 如:算A-1 b可化为Ax=b 的求解问题. 例3.5 不用求逆计算
本节习题 用LU分解法求解pp.89,1题