第三章 线性方程组的解法 3.3 LU分解与矩阵求逆.

Presentation on theme: "第三章 线性方程组的解法 3.3 LU分解与矩阵求逆."— Presentation transcript:

1 第三章 线性方程组的解法 3.3 LU分解与矩阵求逆

2 3.3 LU分解与矩阵求逆问题 3.3.1 LU分解 Gauss消去法的消元过程矩阵描述:消元的每一步等价于左乘初等下三角矩阵，即：k=1,有 行变换相 当于左乘 初等矩阵 其中

3 第k次消元 有 即

4 因此,消元完成后,有 从而 U=A(n-1) (3-6) 故

5 即 顺序主元 且

6 定义.称A=LU（3－7）式为矩阵A的LU分解或三角分解。当L为单位下三角矩阵时，称为Doolittle分解。当U为上三角矩阵时，称为Crout分解。
问题：矩阵A存在LU分解（即Gauss消去法可以执行）的条件是什么？ 解:由上述分析不难得到

7 Gauss消去法 可以执行 定理3.1 [证] 存在性证明见前； 唯一性证明（略）.

8 3.3.2 基本的三角分解法(Doolittle法)

9 上式可记为 导出U

10 同样,由 导出L

11 综合以上分析,有 U L 因此可以推导出 U的第一行 ------(3.9) L的第一列 ------(3.10)

12 思考 U的第r行------(3.11) (逐行算出) L的第r列------(3.12) (逐列算出)
称上述(3.9) ~ (3.12)式所表示的分解过程为Doolittle分解 思考

13 对于线性方程组 系数矩阵非奇异,经过Doolittle分解后 Ax=L(Ux)=b可化为下面两个三角形方程组 消去 回代 L=

14 上述解线性方程组的方法称为三角(LU)分解的 Doolittle法.

15 Doolittle法的特点:紧凑(无中间过程);内积计算(精度高)
逐行算出U的元素逐列算出L的元素

16 逐行算出U的元素逐列算出L的元素

17 Doolittle法在计算机上容易实现,但若按上述流程运算需要较大的存储空间:
A,b,x,L,U,y都需要单独存储,而从lij,uij的计算过程知:

18 因此可按下列方法存储数据:

19 直接三角分解的Doolittle法可以用以下过程表示:

20 存储单元(位置)

21 算法的数据组织 计算(3-9)~(3-14)得出的元素可按下框排列:
其中()为老值(A,b),外为新值(LU,y).计算顺序逐框进行:逐行算出U的元素uij;逐列算出L的元素lij.该分解又称为LU分解的紧凑格式(Doolittle分解).

22 例3.4 用紧凑格式的Doolittle法解方程组(例3.3 )
解:

23

24 所以

25 问题:在Doolittle法(包括LU分解紧凑格式)中,会反复用到公式
仍有可能为小主元做除数? 为此, 也应考虑在算法中加入选取列主元即紧凑格式的 Doolittle列主元法(略).

26 Doolittle法的特点:紧凑(无中间过程);内积计算(精度高)
说明:若计算没有舍入误差,用Gauss消去法和Doolittle法求得的结果应相同.但在计算机上计算,能产生不同的结果. 按矩阵三角分解法(Doolittle)的公式(3-9)~(3-12)中有内积计算Σxiyi,可以用双精度运算.当完成内积计算后再舍入成单精度.

27 3.3.3 矩阵求逆问题 常使用LU分解求解系列方程组 求解时分两步: 分解: A=LU 对j=1,…,m, 解: 比较:用Gauss消去法解(3-16),计算量约O(1/3mn3);用LU分解求解计算量约O(1/3n3+mn2);后者优于前者.

28 当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 不用求逆计算

29 本节习题 用LU分解法求解pp.89,1题