05-矩阵三角分解法

一般线性方程组 -LU 分解与 PLU 分解 对称正定线性方程组 -Cholesky 分解 -- 平方根法 对角占优三对角线性方程组 -追赶法
展开查看详情

1.1 第五章 线性方程组直接解法 — 矩阵三角分解法

2.2 本讲内容 LU 分解与 PLU 分解 一般线性方程组 Cholesky 分解 -- 平方根法 对称正定线性方程组 追赶法 对角占优三对角线性方程组

3.3 LU 分解 将一个矩阵分解成结构简单的 三角矩阵的乘积 什么是矩阵的三角分解 矩阵的 LU 分解 矩阵的 LDR 分解 克洛脱 ( Crout ) 分解 Gauss 消去法对应的矩阵三角分解

4.4 矩阵的 LU 分解 LU 分解 --- 待定系数法( Doolittle 分解 ) 列主元 LU 分解

5.5 LU 分解 利用矩阵乘法直接计算 LU 分解 —— 待定系数法 L  U = A  比较等式两边的 第一行 得: u 1 j = a 1 j 比较等式两边的 第一列 得:  比较等式两边的 第二行 得: 比较等式两边的 第二列 得: ( j = 1,…, n ) ( i = 2,…, n ) ( j = 2,…, n ) ( i = 3,…, n ) U 的第一行 L 的第一列 U 的第二行 L 的第二列

6.6 计算 LU 分解 第 k 步:此时 U 的前 k -1 行和 L 的前 k -1 列已经求出 比较等式两边的 第 k 行 得: 比较等式两边的 第 k 列 得: 直到第 n 步,便可求出矩阵 L 和 U 的所有元素。 ( j = k , …, n ) ( i = k +1, …, n ) 这种计算 LU 分解的方法也称为 Doolittle 分解

7.7 LU 分解 算法 : ( LU 分解 ) for k = 1 to n end j = k , …, n i = k +1, …, n ex51.m 运算量: ( n 3 - n )/3 为了节省存储空间,通常用 A 的绝对下三角部分来存放 L ( 对角线元素无需存储),用 A 的上三角部分来存放 U

8.8 LU 分解算法 算法 : ( LU 分解求解方程组 ) % 先计算 LU 分解 for k = 1 to n end % 解三角方程组 Ly = b 和 Ux = y

9.9 PLU 分解 for k = 1 to n end i = k , k +1, …, n j = 1, 2, …, n i = k +1, …, n j = k +1, …, n 列主元 Gauss 消去法 —— PLU 分解 此算法可以用于计算矩阵的行列式和逆 Matlab 程序:上机练习

10.10 PLU 分解算法 for k = 1 to n end % 解三角方程组 Ly = Pb 和 Ux = y 算法 : ( P LU 分解求解方程组 )

11.11 对称正定矩阵 Cholesky 分解 平方根法 改进的平方根法

12.Cholesky 分解 对称正定矩阵的三角分解 —— Cholesky 分解 定理: ( Cholesky 分解 ) 若 A 对称正定,则 A 可唯一分解为 其中 L 为下三角矩阵,且对角元素都大于 0 A = LL T 证明 : 板书 定理: 设 A 是对称矩阵,若 A 的所有顺序主子式都不为 0 ,则 A 可唯一分解为 其中 L 为单位下三角阵, D 为对角矩阵 A = LDL T 证明 : 自行练习

13.13 计算 Cholesky 分解 如何计算 Cholesky 分解 —— 待定系数法

14.14 Cholesky 分解 算法 for j = 1 to n end i = j +1, …, n 算法 : ( Cholesky 分解 )

15.15 平方根法 A 对称正定 先计算 A 的 Cholesky 分解 然后解方程: Ly = b 和 L T x = y i = 2, 3, …, n 算法 : ( 解对称正定线性方程组的 平方根法 ) i = n- 1, …, 2, 1 用 Cholesky 分解求解线性方程组 —— 平方根法

16.16 改进 的 Cholesky 分解 改进的 Cholesky 分解

17.17 改进 的 Cholesky 分解 for j = 1 to n end i = j +1, …, n 算法 : ( 改进的 Cholesky 分解 ) 优点: 避免开方运算

18.18 改进的平方根法 A 对称正定 先计算 改进的 Cholesky 分解 然后解方程组: Ly = b 和 DL T x = y i = 2, 3, …, n 算法 : ( 解对称正定线性方程组的 改进的平方根法 ) i = n- 1, …, 2, 1 改进的平方根法

19.19 三对角矩阵 Crout 分解 追赶 法

20.20 三对角矩阵 LU 分解 计算过程 i = 2, 3, …, n -1 对角占优的 不可约 三对角矩阵的 Crout 分解 (1) 第一步: (2) 第二步: (3) 第三步: 为了编程方便,这里 a 的下标从 1 开始(教材是从 2 开始) 关于对角占优、不可约等性质,会在第六章详细讲述

21.21 追赶法 A 三对角矩阵(对角占优不可约) i = 2, 3, …, n 算法 : ( 追赶法 ) i = n- 1, …, 2, 1 i = 2, 3, …, n -1 运算量:约 5n+3n 三对角线性方程组的求解 —— 追赶法 追 追 赶

22.22 作业 1. 教材第 177 页: 8 , 9 , 10 注: 第 8 题的方程组改为 ,计算精确解。 第 9 题的方程组改为 ,计算精确解。 第 10 题的方程组改为 ,计算精确解。