目录 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根

Transcription

1 线性方程组的直接解法

2 目录 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

3 线性方程组的求解问题是一个古老的数学问题 九章算术 : 详细记载了消元法 9 世纪初, 西方有了 Gauss 消去法求解大型线性方程组则是在 20 世纪计算机问世后才成为可能

4 线性方程组数值解法的分类 直接法 迭代法

5 直接法 定义 : 在没有舍入误差的情况下经过有限次运算可求得精确解的方法 举例 : 高斯消去法 平方根法 追赶法 适用范围 : 低阶稠密矩阵方程组 某些大型稀疏方程组 ( 如大型带状方程组 )

6 迭代法 定义 : 采取逐次逼近的方法, 亦即从一个初始向量出发, 按照一定的计算格式, 构造一个无穷序列, 其极限才是方程组的精确解, 只经过有限次运算得不到精确解 举例 : Jacobi 迭代 Gauss-Seidel 迭代 超松弛迭代 适用范围 : 大型稀疏方程组

7 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

8 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 选主元三角分解 平方根法及改进的平方根法 追赶法

9 2.. 顺序消去法 定义 ( 顺序消去法 ) 在逐步消元的过程中, 把系数矩阵约化成上三角矩阵, 从而将原方程组约化为容易求解的等价三角方程组, 再通过回代过程逐一求出各未知数

10 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), () a () 2 x + a () 22 x 2 + a () 23 x 3 = b () 2, (2) a () 3 x + a () 32 x 2 + a () 33 x 3 = b () 3. (3) a() 2 (2) + () a () ================== (3) + () a() 3 a () a (2) i j = a () i j + a () 设 a () 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), j b (2) i = b () i + b () a() i a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a () a() i a (), i, j = 2, 3,, i = 2, 3.

11 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), () a () 2 x + a () 22 x 2 + a () 23 x 3 = b () 2, (2) a () 3 x + a () 32 x 2 + a () 33 x 3 = b () 3. (3) a() 2 (2) + () a () ================== (3) + () a() 3 a () a (2) i j = a () i j + a () 设 a () 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), j b (2) i = b () i + b () a() i a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a () a() i a (), i, j = 2, 3,, i = 2, 3.

12 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), () a () 2 x + a () 22 x 2 + a () 23 x 3 = b () 2, (2) a () 3 x + a () 32 x 2 + a () 33 x 3 = b () 3. (3) a() 2 (2) + () a () ================== (3) + () a() 3 a () a (2) i j = a () i j + a () 设 a () 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), j b (2) i = b () i + b () a() i a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a () a() i a (), i, j = 2, 3,, i = 2, 3.

13 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), () a () 2 x + a () 22 x 2 + a () 23 x 3 = b () 2, (2) a () 3 x + a () 32 x 2 + a () 33 x 3 = b () 3. (3) a() 2 (2) + () a () ================== (3) + () a() 3 a () a (2) i j = a () i j + a () 设 a () 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), j b (2) i = b () i + b () a() i a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a () a() i a (), i, j = 2, 3,, i = 2, 3.

14 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), () a () 2 x + a () 22 x 2 + a () 23 x 3 = b () 2, (2) a () 3 x + a () 32 x 2 + a () 33 x 3 = b () 3. (3) a() 2 (2) + () a () ================== (3) + () a() 3 a () a (2) i j = a () i j + a () 设 a () 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), j b (2) i = b () i + b () a() i a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a () a() i a (), i, j = 2, 3,, i = 2, 3.

15 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), (3) + (2) a (2) 22 ================== a(2) 32 a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a (3) 33 = a(2) 33 + a(2) b (3) 3 = b (2) 3 + b (2) 设 a (2) 22 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, 23 a(2) 32, 2 a (2) 22 a(2) 32 a (2) 22 a (3) 33 x 3 = b (3) 3..

16 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), (3) + (2) a (2) 22 ================== a(2) 32 a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a (3) 33 = a(2) 33 + a(2) b (3) 3 = b (2) 3 + b (2) 设 a (2) 22 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, 23 a(2) 32, 2 a (2) 22 a(2) 32 a (2) 22 a (3) 33 x 3 = b (3) 3..

17 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), (3) + (2) a (2) 22 ================== a(2) 32 a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a (3) 33 = a(2) 33 + a(2) b (3) 3 = b (2) 3 + b (2) 设 a (2) 22 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, 23 a(2) 32, 2 a (2) 22 a(2) 32 a (2) 22 a (3) 33 x 3 = b (3) 3..

18 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), (3) + (2) a (2) 22 ================== a(2) 32 a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a (3) 33 = a(2) 33 + a(2) b (3) 3 = b (2) 3 + b (2) 设 a (2) 22 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, 23 a(2) 32, 2 a (2) 22 a(2) 32 a (2) 22 a (3) 33 x 3 = b (3) 3..

19 2.. 顺序消去法 a () x + a () 2 x 2 + a () 3 x 3 = b (), (3) + (2) a (2) 22 ================== a(2) 32 a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, a (2) 32 x 2 + a (2) 33 x 3 = b (2) 3. a (3) 33 = a(2) 33 + a(2) b (3) 3 = b (2) 3 + b (2) 设 a (2) 22 0 a () x + a () 2 x 2 + a () 3 x 3 = b (), a (2) 22 x 2 + a (2) 23 x 3 = b (2) 2, 23 a(2) 32, 2 a (2) 22 a(2) 32 a (2) 22 a (3) 33 x 3 = b (3) 3..

20 2.. 顺序消去法 一般情形 考察 n 元线性方程组 A () X = b (), 其中 A () = a () a () 2 a () n a () 2 a () 22 a () 2n.. a () n a () n2 a () nn., X = x x 2. x n, b () = b () b () 2. b () n

21 2.. 顺序消去法 若约化的主元 a (k) kk 0 (k =, 2,, n), 则经过 for k =, 2,, n- for i = k+,, n l ik = a (k) ik / a(k) kk, for j = k+,, n+ a (k+) i j = a (k) i j l ik a (k) k j end end end 顺序消元法 可得 a () a () 2 a () n 0 a (2) 22 a (2) 2n a (n) nn. x x 2. x n = b () b (2) 2. b (n) n

22 2.. 顺序消去法 x n = b (n) n / a (n) nn for i = n-, n-2,, n end x i = b(i) i a (i) i j x j j=i+ / ai ii 回代公式

23 2.. 顺序消去法 若遇到 a (k) kk = 0, 则消去过程无法进行 若 a (k) kk 不为零但很小, 尽管消去过程可以进行下去, 但用其做除数, 会引起计算结果的严重失真 x + 2x 2 = 2, x + x 2 = 3.

24 2.. 顺序消去法 若遇到 a (k) kk = 0, 则消去过程无法进行 若 a (k) kk 不为零但很小, 尽管消去过程可以进行下去, 但用其做除数, 会引起计算结果的严重失真 x + 2x 2 = 2, x + x 2 = 3.

25 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 选主元三角分解 平方根法及改进的平方根法 追赶法

26 2..2 列主元消去法 定义 ( 列主元消去法 ) 在消元过程中, 每次选主元时, 仅依次按列选取绝对值最大的元素作为主元素, 它只进行行交换, 而不产生未知数次序的调换 列主元消去法能有效地避免顺序消元过程中的两个问题, 它是直接法中最常用的一种方式

27 2..2 列主元消去法 定义 ( 列主元消去法 ) 在消元过程中, 每次选主元时, 仅依次按列选取绝对值最大的元素作为主元素, 它只进行行交换, 而不产生未知数次序的调换 列主元消去法能有效地避免顺序消元过程中的两个问题, 它是直接法中最常用的一种方式

28 2..2 列主元消去法 例 用列主元消去法求解 2x + x 2 + 2x 3 = 5, 5x x 2 + x 3 = 8, x 3x 2 4x 3 = 4.

29 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

30 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

31 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

32 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

33 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

34 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

35 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

36 2..2 列主元消去法 解 : 增广矩阵为 r r 2 ======= r r ======== r 3 5 r r 2 r 3 ======= r r 2 ========

37 2..2 列主元消去法 列主元消去法 for k =, 2,, n- find i k k,, n s.t. a (k) i k,k = max k i n a (k) ik ; interchage the k, i k th rows in [A (k), b (k) ] ; for i = k+,, n l ik = a (k) ik / a(k) kk ; for j = k+,, n+ a (k+) i j = a (k) i j l ik a (k) k j ; end end end

38 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 选主元三角分解 平方根法及改进的平方根法 追赶法

39 2..3 全主元消去法 定义 ( 全主元消去法 ) 全主元消去法选主元的范围更大, 对于 ( ) A () b () 来说, 在整个系数矩阵中选主元, 即将绝对值最大的元素经过行列变换使其置于 a () 的位置, 然后进行消元过程得到 ( ) A (2) b (2) 接下来在该矩阵中划掉第一行第一列后剩余的 n 阶子系数矩阵中选主元, 并通过行 列交换置其于 a (2) 22 的位置, 然后进行消元 ;

40 2..3 全主元消去法 例 用全主元消去法求解 2x + x 2 + 2x 3 = 5, 5x x 2 + x 3 = 8, x 3x 2 4x 3 = 4.

41 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

42 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

43 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

44 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

45 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

46 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

47 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

48 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

49 2..3 全主元消去法 解 : 增广矩阵为 x x 2 x r r 2 ======= x x 2 x r r ======== r 3 5 r x x 2 x x x 3 x 2 r 2 r ====== c 2 c r r 2 ========= x x 3 x /3 /3

50 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 选主元三角分解 平方根法及改进的平方根法 追赶法

51 2..4 选主元消去法的应用求逆矩阵 应用一 : 求逆矩阵 ( ) A E Gauss Jordan Elimination =================== ( ) E A

52 2..4 选主元消去法的应用求逆矩阵 例 求矩阵 3 2 A = 的逆矩阵.

53 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

54 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

55 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

56 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

57 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

58 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

59 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

60 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

61 2..4 选主元消去法的应用求逆矩阵 r r, r r =================== r ( 23) r r 2 ======= r r 2, r r 2 ======================== r (2.26) r r 3, r r 3 ======================== r (.09)

62 2..4 选主元消去法的应用求行列式 应用二 : 求行列式 设有矩阵 a a 2 a n a 2 a 22 a 2n A =... a n a n2 a nn 用主元消去法将其化为上三角矩阵, 并设对角元素为 b, b 22,, b nn, 故 A 的行列式为 det(a) = ( ) m b b 22 b nn, 其中 m 为所施行的行 列交换的次数

63 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

64 2. 高斯消去法 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 追赶法

65 2.2. 三角方程组的解法 下三角形方程组 考察 Ly = b () 其中 b = (b,, b n ) T R n 已知,y = (y,, y n ) T R n 未知, 而 且 l ii 0, i =, 2,, n. L = l l 2 l 22 l 3 l 32 l 33, l n l n2 l n3 l nn

66 2.2. 三角方程组的解法 由方程组 () 的第一个方程 l y = b 得 2 由方程组 () 的第二个方程 y = b l. l 2 y + l 22 y 2 = b 2 得 y 2 = b 2 l 2 y l 22.

67 2.2. 三角方程组的解法 3 一般地, 若已求得 y,, y i, 则由方程组 () 的第 i 个方程 l i y + l i2 y l i,i y i + l ii y i = b i 得 y i = b i i j= l i jy j l ii.

68 2.2. 三角方程组的解法 解下三角形方程组 : 前代法 for j = :n- b(j) = b(j) / L(j, j) b(j+: n) = b(j+: n) - b(j)l(j+:n, j) end b(n) = b(n) / L(n, n) 该算法所需加 减 乘 除的次数 : n (2i ) = n 2, 即该算法的运算量为 n 2. i=

69 2.2. 三角方程组的解法 解下三角形方程组 : 前代法 for j = :n- b(j) = b(j) / L(j, j) b(j+: n) = b(j+: n) - b(j)l(j+:n, j) end b(n) = b(n) / L(n, n) 该算法所需加 减 乘 除的次数 : n (2i ) = n 2, 即该算法的运算量为 n 2. i=

70 2.2. 三角方程组的解法 前代法 (matlab 代码 :fs.m) function b = fs(l, b, n) 2 for j = :n- 3 b(j) = b(j) / L(j,j); 4 b(j+: n) = b(j+: n) - b(j) * L(j+:n, j); 5 end 6 b(n) = b(n) / L(n,n); 7 end

71 2.2. 三角方程组的解法 上三角形方程组 考察 Ux = y (2) 其中 y = (y,, y n ) T R n 已知,x = (x,, x n ) T R n 未知, 而 U = 且 u ii 0, i =, 2,, n. u u 2 u 3 u n u 22 u 23 u n u 33 u 3n.... u nn,

72 2.2. 三角方程组的解法 由方程组 (2) 的第 n 个方程 u nn x n = y n 得 2 由方程组 (2) 的第 n 个方程 x n = y n u nn. u n,n x n + u n,n x n = y n 得 x n = y n u n,n x n u nn.

73 2.2. 三角方程组的解法 3 一般地, 若已求得 x n,, x i+, 则由方程组 (2) 的第 i 个方程 u ii x i + u i,i+ x i+ + + u i,n x n = y i 得 x i = y i n j=i+ u i j x j u ii.

74 2.2. 三角方程组的解法 解上三角形方程组 : 回代法 for j = n-:-:2 y(j) = y(j) / U(j, j) y(:j-) = y(:j-) - y(j)u(:j-, j) end y() = y() / U(, ) 该算法的运算量也为 n 2.

75 2.2. 三角方程组的解法 解上三角形方程组 : 回代法 for j = n-:-:2 y(j) = y(j) / U(j, j) y(:j-) = y(:j-) - y(j)u(:j-, j) end y() = y() / U(, ) 该算法的运算量也为 n 2.

76 2.2. 三角方程组的解法 回代法 (matlab 代码 :bs.m) function y = bs(u, y, n) 2 for j = n:-:2 3 y(j) = y(j) / U(j,j); 4 y(:j-) = y(:j-) - y(j) * U(:j-, j); 5 end 6 y() = y() / U(,); 7 end

77 2.2. 三角方程组的解法 一般线性方程组 考察 Ax = b (3) 其中 A R n n, x, b R n 若 A = LU, 即 A 能分解成一个下三角阵 L 和一个上三角阵 U 的乘积, 则 (3) 的解 x 可由以下两步得到 : 用前代法解 Ly = b 得 y; 2 用回代法解 Ux = y 得 x

78 2.2. 三角方程组的解法 一般线性方程组 考察 Ax = b (3) 其中 A R n n, x, b R n 若 A = LU, 即 A 能分解成一个下三角阵 L 和一个上三角阵 U 的乘积, 则 (3) 的解 x 可由以下两步得到 : 用前代法解 Ly = b 得 y; 2 用回代法解 Ux = y 得 x

79 2. 高斯消去法 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 追赶法

80 2.2.2 Gauss 变换 定义 ( 矩阵三角分解 ) 将矩阵 A 分解为一个下三角阵 L 和一个上三角阵 U 的乘积, 最自然的做法是通过一系列初等变换, 逐步将 A 约化为上三角阵, 并且保证这些初等变换的乘积是一个下三角阵

81 2.2.2 Gauss 变换方式一 :Gauss 变换 定义 (Gauss 变换 ( 矩阵 )) L k =... l k+,k.... l n,k I l k e T k l k = (0,, 0, l k+,k,, l nk ) T Gauss 向量

82 2.2.2 Gauss 变换方式一 :Gauss 变换 定义 (Gauss 变换 ( 矩阵 )) L k =... l k+,k.... l n,k I l k e T k l k = (0,, 0, l k+,k,, l nk ) T Gauss 向量

83 2.2.2 Gauss 变换方式一 :Gauss 变换 对于 x = (x,, x n ) T R n, L k x = (x,, x k, x k+ l k+,k x k,, x n l nk x k ) T. 取 便有 l ik = x i x k, i = k +,, n, x k 0 L k x = (x,, x k, 0,, 0) T.

84 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 ( L k ) L k 的逆为 L k = I + l k e T k 证明. e T k l k = 0, (I + l k e T k )(I l ke T k ) = I l k e T k l k e T k = I.

85 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 ( L k ) L k 的逆为 L k = I + l k e T k 证明. e T k l k = 0, (I + l k e T k )(I l ke T k ) = I l k e T k l k e T k = I.

86 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 (2 L k ) L k A = (I l k e T k )A = A l k(e T k A), e T k A 为 A 的第 k 行 类似地,Ae k 为 A 的第 k 列 例 =

87 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 (2 L k ) L k A = (I l k e T k )A = A l k(e T k A), e T k A 为 A 的第 k 行 类似地,Ae k 为 A 的第 k 列 例 =

88 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 (3 L k ) 若 j < k, 则 L j L k = (I l j e T j )(I l ke T k ) = I l je T j l k e T k. 证明. 因为当 j < k 时, 有 e T j l k = 0 例 = 2 3 4

89 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 (3 L k ) 若 j < k, 则 L j L k = (I l j e T j )(I l ke T k ) = I l je T j l k e T k. 证明. 因为当 j < k 时, 有 e T j l k = 0 例 = 2 3 4

90 2.2.2 Gauss 变换方式一 :Gauss 变换 性质 (3 L k ) 若 j < k, 则 L j L k = (I l j e T j )(I l ke T k ) = I l je T j l k e T k. 证明. 因为当 j < k 时, 有 e T j l k = 0 例 = 2 3 4

91 2.2.2 Gauss 变换 } {{ } A L } {{ } L A L 2 L 3 } {{ } L 2 L A } {{ } L 3 L 2 L A

92 2.2.2 Gauss 变换 } {{ } A L } {{ } L A L 2 L 3 } {{ } L 2 L A } {{ } L 3 L 2 L A

93 2.2.2 Gauss 变换 } {{ } A L } {{ } L A L 2 L 3 } {{ } L 2 L A } {{ } L 3 L 2 L A

94 2.2.2 Gauss 变换 } {{ } A L } {{ } L A L 2 L 3 } {{ } L 2 L A } {{ } L 3 L 2 L A

95 2.2.2 Gauss 变换 L A = A = =

96 2.2.2 Gauss 变换 L A = A = =

97 2.2.2 Gauss 变换 L 2 L A = L A = =

98 2.2.2 Gauss 变换 L 2 L A = L A = =

99 2.2.2 Gauss 变换 L 2 L A = L 3 L 2 L A = = = U.

100 2.2.2 Gauss 变换 L 2 L A = L 3 L 2 L A = = = U.

101 2.2.2 Gauss 变换 L = 2 4 3, L2 = } {{ } A L L 2 L 3 = = } {{ } L, L3 = } {{ } U

102 2.2.2 Gauss 变换 L = 2 4 3, L2 = } {{ } A L L 2 L 3 = = } {{ } L, L3 = } {{ } U

103 2.2.2 Gauss 变换 L = 2 4 3, L2 = } {{ } A L L 2 L 3 = = } {{ } L, L3 = } {{ } U

104 2.2.2 Gauss 变换 对于一般矩阵 A, 记 A () = A, 则 A (2) = L A () A (3) = L 2 A (2) = L 2 L A (). A (k) = L k L A () = A (k) A (k) 2 A (k) 22 其中 A (k) 是 k 阶上三角阵,A (k) 22 为 A (k) 22 = a (k) kk a (k) kk.. a (k) nk a (k) nn

105 2.2.2 Gauss 变换 若 a (k) kk 0, 则可确定一个 Gauss 变换 L k, 使得 L k A (k) 第 k 列的最后 n k 个元素为 0 取 L k = I l k e T k, 则 其中 A (k+) 是 k 阶上三角阵 l k = (0,, 0, l k+,k,, l nk ) T, l ik = a (k) ik /a(k) kk, i = k +,, n A (k+) = L k A (k) = A (k+) A (k+) 2 A (k+) 22 如此进行 n 步, 最终所得矩阵 A (n) 即为所要求的上三角形式

106 2.2.2 Gauss 变换 若 a (k) kk 0, 则可确定一个 Gauss 变换 L k, 使得 L k A (k) 第 k 列的最后 n k 个元素为 0 取 L k = I l k e T k, 则 其中 A (k+) 是 k 阶上三角阵 l k = (0,, 0, l k+,k,, l nk ) T, l ik = a (k) ik /a(k) kk, i = k +,, n A (k+) = L k A (k) = A (k+) A (k+) 2 A (k+) 22 如此进行 n 步, 最终所得矩阵 A (n) 即为所要求的上三角形式

107 2.2.2 Gauss 变换 上述步骤可描述为 L n L A = A (n). 令 L = (L n L ) 及 U = A (n), 则 A = LU, 其中 L 是一个单位上三角阵 事实上, 由于 e T j l i = 0 ( j < i), 则 L = L L 2 L n = (I + l e T )(I + l 2e T 2 ) (I + l n e T n ) = I + l e T + l 2e T 2 + l n e T n.

108 2.2.2 Gauss 变换 A (k+) = L k A (k) = (I l k e T k )A(k) = A (k) l k e T k A(k). A (k+) 与 A (k) 的前 k 行元素相同 因为 e T k A(k) 是 A (k) 的第 k 行,l k 的前 k 个分量为 0 A (k+) 中第 k + 到 n 行元素需要更新 a (k+) i j a (k+) ik = 0, i = k +,, n, = a (k) ik l ika (k) k j, i, j = k +,, n

109 2.2.2 Gauss 变换 A (k+) = L k A (k) = (I l k e T k )A(k) = A (k) l k e T k A(k). A (k+) 与 A (k) 的前 k 行元素相同 因为 e T k A(k) 是 A (k) 的第 k 行,l k 的前 k 个分量为 0 A (k+) 中第 k + 到 n 行元素需要更新 a (k+) i j a (k+) ik = 0, i = k +,, n, = a (k) ik l ika (k) k j, i, j = k +,, n

110 2.2.2 Gauss 变换 A (k+) = L k A (k) = (I l k e T k )A(k) = A (k) l k e T k A(k). A (k+) 与 A (k) 的前 k 行元素相同 因为 e T k A(k) 是 A (k) 的第 k 行,l k 的前 k 个分量为 0 A (k+) 中第 k + 到 n 行元素需要更新 a (k+) i j a (k+) ik = 0, i = k +,, n, = a (k) ik l ika (k) k j, i, j = k +,, n

111 2.2.2 Gauss 变换 存储方式 : A (k) 中第 k + n 行元素在计算出 A (k+) 以后不再有用, 故 A (k) 中相应位置上的元素可用新值更新 由于 A (k+) 中的第 k 列对角线以下的元素均为 0, 无需存储, 故这些位置可用于存储 l k 中的非 0 元

112 2.2.2 Gauss 变换 算法 ( 计算三角分解 :Gauss 消去法 ) for k = :n- A(k+:n, k) = A(k+:n, k) / A(k, k) A(k+:n, k+: n) = A(k+:n, k+: n) - A(k+:n, k) A(k, k+: n) end 运算次数 : n [(n k) + 2(n k) 2 ] = k= n(n ) 2 + = 2 3 n3 + O(n 2 ) n(n )(2n ) 3

113 2.2.2 Gauss 变换 算法 ( 计算三角分解 :Gauss 消去法 ) for k = :n- A(k+:n, k) = A(k+:n, k) / A(k, k) A(k+:n, k+: n) = A(k+:n, k+: n) - A(k+:n, k) A(k, k+: n) end 运算次数 : n [(n k) + 2(n k) 2 ] = k= n(n ) 2 + = 2 3 n3 + O(n 2 ) n(n )(2n ) 3

114 2.2.2 Gauss 变换 LU 分解的 matlab 代码 function A = GsLU(A) [m n] = size(a); for k = :n- A(k+:n, k) = A(k+:n, k) / A(k, k); A(k+:n, k+: n) = A(k+:n, k+: n) - A(k+:n, k) * A(k, k+: n); end end

115 2.2.2 Gauss 变换 a (k) kk (k =,, n ) 称作主元 三角分解的条件 当且仅当主元 a (k) kk (k =,, n ) 均不为 0 时, 算法 才能进行到底

116 2.2.2 Gauss 变换 定理 主元 a (i) ii (i =,, k) 均不为 0 A 的 i 阶顺序主子阵 A i (i =,, k) 非奇异 证明 当 k = 时,a () 0 A 非奇异 2 假设定理直到 k 成立, 下证 : 若 A,, A k 非奇异, 则 A k 非奇异 a (k) kk 0

117 2.2.2 Gauss 变换 定理 主元 a (i) ii (i =,, k) 均不为 0 A 的 i 阶顺序主子阵 A i (i =,, k) 非奇异 证明 当 k = 时,a () 0 A 非奇异 2 假设定理直到 k 成立, 下证 : 若 A,, A k 非奇异, 则 A k 非奇异 a (k) kk 0

118 2.2.2 Gauss 变换 定理 主元 a (i) ii (i =,, k) 均不为 0 A 的 i 阶顺序主子阵 A i (i =,, k) 非奇异 证明 当 k = 时,a () 0 A 非奇异 2 假设定理直到 k 成立, 下证 : 若 A,, A k 非奇异, 则 A k 非奇异 a (k) kk 0

119 2.2.2 Gauss 变换 证明 由归纳假设,a (i) ii 0(i =,, k ), 故 A (k) = L k L A = A (k) A (k) 2 A (k) 22 其中 A (k) 是 k 阶上三角阵, 而 A (k) 的 k 阶顺序主子阵形如 A (k) a (k) kk

120 2.2.2 Gauss 变换 证明. 记 L,, L k 的 k 阶顺序主子阵为 (L ) k,, (L k ) k, 则 A (k) (L k ) k (L ) k A k = a (k) kk = det A k = a (k) kk det A(k) = A k 非奇异当且仅当 a (k) kk 0

121 2.2.2 Gauss 变换 证明. 记 L,, L k 的 k 阶顺序主子阵为 (L ) k,, (L k ) k, 则 A (k) (L k ) k (L ) k A k = a (k) kk = det A k = a (k) kk det A(k) = A k 非奇异当且仅当 a (k) kk 0

122 2.2.2 Gauss 变换 证明. 记 L,, L k 的 k 阶顺序主子阵为 (L ) k,, (L k ) k, 则 A (k) (L k ) k (L ) k A k = a (k) kk = det A k = a (k) kk det A(k) = A k 非奇异当且仅当 a (k) kk 0

123 2.2.2 Gauss 变换 定理 ( 矩阵三角分解的条件 ) A 的各阶顺序主子阵均非奇异 = 存在唯一的单位下三角阵 L 和上三角阵 U, 使得 A = LU.

124 2. 高斯消去法 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 追赶法

125 2.2.3 Doolittle 分解方式二 :Doolittle 分解 a a 2 a n a 2 a 22 a 2n a n a n2 a nn 图 : Doolittle 分解 l 2 =..... l n l n2 u u 2 u n u 22 u 2n.... u nn

126 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

127 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

128 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

129 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

130 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

131 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

132 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

133 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

134 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

135 2.2.3 Doolittle 分解方式二 :Doolittle 分解 图 : Doolittle 分解运算次序 : 先行后列, 先 U 后 L u u 2 u 3 u,n u n l 2 u 22 u 23 u 2,n u 2n l 3 l 32 u 33 u 3,n u 2n l n, l n,2 l n,3 u n,n u n,n l n l n2 l n3 l n,n u nn

136 2.2.3 Doolittle 分解方式三 :Crout 分解 a a 2 a n a 2 a 22 a 2n a n a n2 a nn 图 : Crout 分解 l l 2 l 22 =..... l n l n2 l nn u 2 u n u 2n....

137 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

138 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

139 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

140 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

141 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

142 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

143 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

144 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

145 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

146 2.2.3 Doolittle 分解方式三 :Crout 分解 图 : Crout 分解运算次序 : 先列后行, 先 L 后 U l u 2 u 3 u,n u n l 2 l 22 u 23 u 2,n u 2n l 3 l 32 l 33 u 3,n u 2n l n, l n,2 l n,3 l n,n u n,n l n l n2 l n3 l n,n l nn

147 2.2.3 Doolittle 分解方式二 :Doolittle 分解 n a i j = l ik u k j i, j =, 2,, n k= l ii =, l i j = 0( j > i), u i j = 0(i > j) = 先算 U 的第 k 行 ( j k) n k k a k j = l kr u r j = l kr u r j = l kr u r j + l kk u k j r= r= r= k = u k j = a k j l kr u r j r= 再算 L 的第 k 列 (i > k) n k k a ik = l ir u rk = l ir u rk = l ir u rk + l ik u kk r= r= r= = l ik = a ik k r= l kru r j u kk

148 2.2.3 Doolittle 分解方式二 :Doolittle 分解 n a i j = l ik u k j i, j =, 2,, n k= l ii =, l i j = 0( j > i), u i j = 0(i > j) = 先算 U 的第 k 行 ( j k) n k k a k j = l kr u r j = l kr u r j = l kr u r j + l kk u k j r= r= r= k = u k j = a k j l kr u r j r= 再算 L 的第 k 列 (i > k) n k k a ik = l ir u rk = l ir u rk = l ir u rk + l ik u kk r= r= r= = l ik = a ik k r= l kru r j u kk

149 2.2.3 Doolittle 分解方式二 :Doolittle 分解 n a i j = l ik u k j i, j =, 2,, n k= l ii =, l i j = 0( j > i), u i j = 0(i > j) = 先算 U 的第 k 行 ( j k) n k k a k j = l kr u r j = l kr u r j = l kr u r j + l kk u k j r= r= r= k = u k j = a k j l kr u r j r= 再算 L 的第 k 列 (i > k) n k k a ik = l ir u rk = l ir u rk = l ir u rk + l ik u kk r= r= r= = l ik = a ik k r= l kru r j u kk

150 2.2.3 Doolittle 分解方式二 :Doolittle 分解 n a i j = l ik u k j i, j =, 2,, n k= l ii =, l i j = 0( j > i), u i j = 0(i > j) = 先算 U 的第 k 行 ( j k) n k k a k j = l kr u r j = l kr u r j = l kr u r j + l kk u k j r= r= r= k = u k j = a k j l kr u r j r= 再算 L 的第 k 列 (i > k) n k k a ik = l ir u rk = l ir u rk = l ir u rk + l ik u kk r= r= r= = l ik = a ik k r= l kru r j u kk

151 2.2.3 Doolittle 分解方式二 :Doolittle 分解 n a i j = l ik u k j i, j =, 2,, n k= l ii =, l i j = 0( j > i), u i j = 0(i > j) = 先算 U 的第 k 行 ( j k) n k k a k j = l kr u r j = l kr u r j = l kr u r j + l kk u k j r= r= r= k = u k j = a k j l kr u r j r= 再算 L 的第 k 列 (i > k) n k k a ik = l ir u rk = l ir u rk = l ir u rk + l ik u kk r= r= r= = l ik = a ik k r= l kru r j u kk

152 2.2.3 Doolittle 分解方式二 :Doolittle 分解 先行后列 for k = : n for j = k,, n % 计算第 k 行 u k j = a k j k r= l lru r j end for i = k+,, n % 计算第 k 列 l ik = (a ik k r= l iru rk )/u kk end end

153 例 利用 Doolittle 分解求解线性方程组 x x 2 x 3 x 4 = 5 0 7

154 计算 U 的第一行,L 的第一列, 得 u =, u 2 = 2, u 3 = 3, u 4 = 4, l 2 = a 2 u = 3, l 3 = a 3 u = 2, l 3 = a 3 u = 4.

155 2 计算 U 的第二行,L 的第二列, 得 u 22 = a 22 l 2 u 2 = 2, u 23 = a 23 l 2 u 3 = 3, u 24 = a 24 l 2 u 4 =, l 32 = a 32 l 3 u 2 u 22 = 3, l 42 = a 42 l 4 u 2 u 22 = 3.

156 3 计算 U 的第三行,L 的第三列, 得 u 33 = a 33 l 3 u 3 l 32 u 23 = 3, u 34 = a 34 l 3 u 4 l 32 u 24 = 2, l 43 = a 43 l 4 u 3 l 42 u 23 u 33 = 2. 4 计算 U 的第四行, 得 u 44 = a 44 l 4 u 4 l 42 u 24 l 43 u 34 = 4,

157 3 计算 U 的第三行,L 的第三列, 得 u 33 = a 33 l 3 u 3 l 32 u 23 = 3, u 34 = a 34 l 3 u 4 l 32 u 24 = 2, l 43 = a 43 l 4 u 3 l 42 u 23 u 33 = 2. 4 计算 U 的第四行, 得 u 44 = a 44 l 4 u 4 l 42 u 24 l 43 u 34 = 4,

158 2.2.3 Doolittle 分解方式二 :Doolittle 分解 =

159 2.2.3 Doolittle 分解方式二 :Doolittle 分解 = y y 2 y 3 y 4 = 求得 Y = ( 2,, 7, 6) T.

160 2.2.3 Doolittle 分解方式二 :Doolittle 分解 = x x 2 x 3 x 4 = 7 6 求得 X = (, 2, 3, 4) T.

161 2.2.3 Doolittle 分解对称矩阵的三角分解 定理若 A 为 n 阶对称矩阵, 且 A 的各阶顺序主子式都不为 0, 则 A 可惟一分解为 A = LDL T, 其中 L 为单位下三角阵,D 为对角阵 证明 : 由 A = l l n l n2 u u 2 u n u 22 u 2n.... u nn

162 2.2.3 Doolittle 分解对称矩阵的三角分解 定理若 A 为 n 阶对称矩阵, 且 A 的各阶顺序主子式都不为 0, 则 A 可惟一分解为 A = LDL T, 其中 L 为单位下三角阵,D 为对角阵 证明 : 由 A = l l n l n2 u u 2 u n u 22 u 2n.... u nn

163 2.2.3 Doolittle 分解对称矩阵的三角分解 因为 u ii 0(i =,, n), 故 U 可分解为 u u 22 U =... u 2 u u n u u 2n u = DU u nn 其中 D 为对角矩阵,U 为单位上三角阵 于是 A = LDU = L(DU ), 因为 A 为对称阵, 故 A = A T = U T DT L = U T (DLT ). 由 A 的 LU 分解的惟一性即得 L = U T.

164 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

165 2.3 选主元三角分解 例 求 的 LU 分解 A = [ 0 ] A 非奇异, 但 Gauss 消去第一步就会失效

166 2.3 选主元三角分解 例 求 的 LU 分解 A = [ 0 ] A 非奇异, 但 Gauss 消去第一步就会失效

167 2.3 选主元三角分解 例 求 的 LU 分解 A = [ 0 20 ] [ L = 设 ɛ machine 0 6, 则 [ L = LŨ = ] [ ] 0 20, U = ] [ ] 0 20, Ũ = [ ]

168 2.3 选主元三角分解 例 求 的 LU 分解 A = [ 0 20 ] [ L = 设 ɛ machine 0 6, 则 [ L = LŨ = ] [ ] 0 20, U = ] [ ] 0 20, Ũ = [ ]

169 2.3 选主元三角分解 例 求 的 LU 分解 A = [ 0 20 ] [ L = 设 ɛ machine 0 6, 则 [ L = LŨ = ] [ ] 0 20, U = ] [ ] 0 20, Ũ = [ ]

170 2.3 选主元三角分解 例 设 求 A = [ 0 20 Ax = b ] [, b = 0 ], 近似解 : [ 0 x = ] 精确解 : x [ ]

171 2.3 选主元三角分解 例 设 求 A = [ 0 20 Ax = b ] [, b = 0 ], 近似解 : [ 0 x = ] 精确解 : x [ ]

172 2.3 选主元三角分解 交换方程次序 [ ] [ ] [ x = x 近似解 ˆL = [ 0 ], Û = ˆx [ [ ] ] ]

173 2.3 选主元三角分解 图 : 置换矩阵 I pq = p q = p q ( ) e e p e q e p+ e q e p e q+ e n

174 2.3 选主元三角分解具体步骤 假定消去过程已经进行到了 k 步, 即已经确定了 k 个 Gauss 变换 L,, L k R n n 和 2(k ) 个初等置换矩阵 P,, P k, Q,, Q k R n n 使得 A (k) = L k P k L P A Q Q k A (k) A (k) 2 = 0 A (k) 22

175 2.3 选主元三角分解具体步骤 2 第 k 步 : 选 a (k) pq = max { a (k) : k i, j n} 若 a (k) pq = 0, 则 R(A) = k, 停止! i j 若 a (k) pq 0, 交换 A (k) 的第 k p 行及第 k q 列, 记交换后的 A (k) 22 为 ã (k) kk ã (k) kn à (k) 22 =. ã (k) nk ã (k) nn.

176 2.3 选主元三角分解具体步骤 2 第 k 步 : 选 a (k) pq = max { a (k) : k i, j n} 若 a (k) pq = 0, 则 R(A) = k, 停止! i j 若 a (k) pq 0, 交换 A (k) 的第 k p 行及第 k q 列, 记交换后的 A (k) 22 为 ã (k) kk ã (k) kn à (k) 22 =. ã (k) nk ã (k) nn.

177 2.3 选主元三角分解具体步骤 2 第 k 步 : 选 a (k) pq = max { a (k) : k i, j n} 若 a (k) pq = 0, 则 R(A) = k, 停止! i j 若 a (k) pq 0, 交换 A (k) 的第 k p 行及第 k q 列, 记交换后的 A (k) 22 为 ã (k) kk ã (k) kn à (k) 22 =. ã (k) nk ã (k) nn.

178 2.3 选主元三角分解具体步骤 2 第 k 步 : 选 a (k) pq = max { a (k) : k i, j n} 计算 Gauss 变换 i j L k = I l k e T k l k = (0,, 0, l k+,k,, l n,k ) T l i,k = ã (k) ik /ã(k) kk, i = k +,, n. 则 A (k+) = L k P k A (k ) Q k A (k+) A (k+) 2 = 0 A (k+) 22 其中 A (k+) 为 k 阶上三角阵,P k = I kp, Q k = I kq R n n

179 2.3 选主元三角分解具体步骤 2 第 k 步 : 选 a (k) pq = max { a (k) : k i, j n} 计算 Gauss 变换 i j L k = I l k e T k l k = (0,, 0, l k+,k,, l n,k ) T l i,k = ã (k) ik /ã(k) kk, i = k +,, n. 则 A (k+) = L k P k A (k ) Q k A (k+) A (k+) 2 = 0 A (k+) 22 其中 A (k+) 为 k 阶上三角阵,P k = I kp, Q k = I kq R n n

180 2.3 选主元三角分解具体步骤 2 第 k 步 : 选 a (k) pq = max { a (k) : k i, j n} 计算 Gauss 变换 i j L k = I l k e T k l k = (0,, 0, l k+,k,, l n,k ) T l i,k = ã (k) ik /ã(k) kk, i = k +,, n. 则 A (k+) = L k P k A (k ) Q k A (k+) A (k+) 2 = 0 A (k+) 22 其中 A (k+) 为 k 阶上三角阵,P k = I kp, Q k = I kq R n n

181 2.3 选主元三角分解 全主元 Gauss 消去法的矩阵表述 存在置换矩阵 P k, Q k 和初等下三角阵 L k, k =,, n, 使得 为上三角阵 令 L n P n L P A Q Q r = U Q = Q Q n P = P n P L = P(L n P n L P ) 则有 PAQ = LU 以下说明 L 为一个单位下三角阵

182 2.3 选主元三角分解 全主元 Gauss 消去法的矩阵表述 存在置换矩阵 P k, Q k 和初等下三角阵 L k, k =,, n, 使得 为上三角阵 令 L n P n L P A Q Q r = U Q = Q Q n P = P n P L = P(L n P n L P ) 则有 PAQ = LU 以下说明 L 为一个单位下三角阵

183 2.3 选主元三角分解 } {{ } P =I 4 A = A () = } {{ } A (), } {{ } Q =I 3 = } {{ } Ã () } {{ } L } {{ } Ã () = } {{ } A (2)

184 2.3 选主元三角分解 } {{ } P =I 4 A = A () = } {{ } A (), } {{ } Q =I 3 = } {{ } Ã () } {{ } L } {{ } Ã () = } {{ } A (2)

185 2.3 选主元三角分解 } {{ } P =I 4 A = A () = } {{ } A (), } {{ } Q =I 3 = } {{ } Ã () } {{ } L } {{ } Ã () = } {{ } A (2)

186 2.3 选主元三角分解 } {{ } P 2 =I 23 A (2) = } {{ } A (2) } {{ } Q 2 =I 24, = } {{ } Ã (2) } {{ } L } {{ } Ã (2) = } {{ } A (3)

187 2.3 选主元三角分解 } {{ } P 2 =I 23 A (2) = } {{ } A (2) } {{ } Q 2 =I 24, = } {{ } Ã (2) } {{ } L } {{ } Ã (2) = } {{ } A (3)

188 2.3 选主元三角分解 } {{ } P 2 =I 23 A (2) = } {{ } A (2) } {{ } Q 2 =I 24, = } {{ } Ã (2) } {{ } L } {{ } Ã (2) = } {{ } A (3)

189 2.3 选主元三角分解 A (3) = , } {{ } P 3 =I } {{ } A (3) 0.2 } {{ } L } {{ } Q 3 =I 34 } {{ } Ã (3) = = } {{ } Ã (3) } {{ } A (4)

190 2.3 选主元三角分解 A (3) = , } {{ } P 3 =I } {{ } A (3) 0.2 } {{ } L } {{ } Q 3 =I 34 } {{ } Ã (3) = = } {{ } Ã (3) } {{ } A (4)

191 2.3 选主元三角分解 A (3) = , } {{ } P 3 =I } {{ } A (3) 0.2 } {{ } L } {{ } Q 3 =I 34 } {{ } Ã (3) = = } {{ } Ã (3) } {{ } A (4)

192 2.3 选主元三角分解 将上述步骤合并, 即得 L 3 P 3 L 2 P 2 L P A Q Q 2 Q 3 = A (4) = A Q = (L 3 P 3 L 2 P 2 L P ) A (4) = P L P 2 L 2 P 3 L 3 A (4) = P 3 P 2 P } {{ } P A Q }{{} Q = P 3 P 2 L P 2 L2 P 3 L3 } {{ } L A (4) }{{} U

193 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

194 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

195 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

196 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

197 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

198 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

199 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

200 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

201 2.3 选主元三角分解 观察 L = P 3 (P 2 L P 2 L 2 )P 3L 3, 设 P 2 = I 23, P 3 = I 34 以及 L = L P 3 = P 2 = , L2 = P 2 = P 3 = 由此可以看出 L L 3 = # 4 L2 === L3 === # 4

202 2.3 选主元三角分解 定理 L 是一个单位下三角阵 = P n P (L n P n L P ) = P n P 2 L P 2L2 P nln

203 2.3 选主元三角分解 定理存在置换矩阵 P, Q 以及单位下三角阵 L 和上三角阵 U, 使得 PAQ = LU, 且 l i j,u 的非零对角元的个数正好等于 A 的秩

204 2.3 选主元三角分解 算法.2.( 全主元三角分解 ) for k = :n- 确定 p, q(k<=p, q<=n) 使得 A(p,q) = max{ A(i,j) : i=k:n, j=k:n} A(k,:n) <-> A(p,:n) A(:n,k) <-> A(:n,q) u(k)=p v(k)=q if A(k,k)!=0 A(k+:n,k) = A(k+:n,k)/ A(k,k) A(k+:n,k+: n) = A(k+:n,k+: n) - A(k+:n,k)* A(k,k+: n) else stop end end

205 2.3 选主元三角分解 例 对如下矩阵进行全主元三角分解 2 A = ,

206 2.3 选主元三角分解 A =, = } {{ }} {{ }} {{ } P A (0) Ã (0) = } {{ }} {{ }} {{ } L Ã A ()

207 2.3 选主元三角分解 A =, = } {{ }} {{ }} {{ } P A (0) Ã (0) = } {{ }} {{ }} {{ } L Ã A ()

208 2.3 选主元三角分解 A =, = } {{ }} {{ }} {{ } P A (0) Ã (0) = } {{ }} {{ }} {{ }

209 2.3 选主元三角分解 A () =, = } {{ }} {{ }} {{ } P 2 A () Ã () } {{ } L = } {{ }} {{ }

210 2.3 选主元三角分解 A () =, = } {{ }} {{ }} {{ } P 2 A () Ã () } {{ } L = } {{ } Ã () } {{ } A (2)

211 2.3 选主元三角分解 A () =, = } {{ }} {{ }} {{ } P 2 A () Ã () } {{ } L = } {{ } Ã () } {{ } A (2)

212 2.3 选主元三角分解 0 } {{ } P } {{ } L A (2) =, } {{ } A (2) } {{ } Ã (2) 7 4 = = } {{ } Ã (2) } {{ } A () 3

213 2.3 选主元三角分解 0 } {{ } P } {{ } L A (2) =, } {{ } A (2) } {{ } Ã (2) 7 4 = = } {{ } Ã (2) } {{ } A () 3

214 2.3 选主元三角分解 0 } {{ } P } {{ } L A (2) =, } {{ } A (2) } {{ } Ã (2) 7 4 = = } {{ } Ã (2) } {{ } A () 3

215 2.3 选主元三角分解 算法.2.( 列主元三角分解 ) for k = :n- 确定 p(k<=p<=n) 使得 A(p,k) = max{ A(i,j) : i=k:n, j=k:n} A(k,:n) <-> A(p,:n) u(k)=p if A(k,k)!=0 A(k+:n,k) = A(k+:n,k)/ A(k,k) A(k+:n,k+: n) = A(k+:n,k+: n) - A(k+:n,k)* A(k,k+: n) else stop end end

216 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

217 2. 高斯消去法 三角形方程组和三角分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

218 2.4. 平方根法对称正定矩阵 适用对象 : 对称正定矩阵方程组 定义 ( 对称正定矩阵 ) 设 A 是 n 阶实对称矩阵, 若 0 x R n, 恒有 x T Ax > 0, 则称 A 为对称正定矩阵

219 2.4. 平方根法对称正定矩阵的性质 性质若 A 对称正定, 则 A 非奇异 2 任一主子矩阵 A k, k =, 2,, n 必正定 3 a ii > 0, i =, 2,, n 4 λ i (A) > 0, i =, 2,, n 5 det(a) > 0

220 2.4. 平方根法 定理 对称矩阵 A 正定 A 的各阶顺序主子式 det (A i ) > 0, i =, 2,, n.

221 2.4. 平方根法 定理 (Cholesky 分解 ) 对称矩阵 A 正定 = 存在惟一的主对角元皆正的下三角阵 L, 使得 A = LL T.

222 2.4. 平方根法 证明. A 对称正定 A 各阶顺序主子式 > 0 = A = LD L T, L : 单位下三角阵 L T 非奇异 = 存在惟一的向量 x R n 使得 L T x = e i 于是 所以 0 < x T Ax = x T LD L T x = ( L T x) T D L T x = e T i De i = d i. A = LD L T = LD /2 D /2 L T = (D /2 L) T D /2 L LL T

223 2.4. 平方根法 a a 2 a n a 2 a 22 a 2n =... a n a n2 a nn l l 2 l l n l n2 l nn l l 2 l n l 22 l n2.... l nn

224 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

225 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

226 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

227 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

228 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

229 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

230 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

231 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

232 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

233 2.4. 平方根法方式二 :Doolittle 分解 图 : 平方根法运算次序 l l 2 l 22 l 3 l 32 l l n, l n,2 l n,n l n l n2 l n,n l nn

234 2.4. 平方根法方式二 :Doolittle 分解 由矩阵乘法 a i j = n l ik u k j = k= 注意到 l i j = 0( j > i), 知计算第 j 行时 当 i = j 时, k= a j j = n l ik l jk (i, j =, 2,, n), k= j j l 2 jk = l j j = a j j l jk l jk k= 当 i > j 时, j j a i j = l ik l jk = l i j l j j = a i j l ik l jk = l i j = a i j j k= l ikl jk l j j k= k= /2

235 2.4. 平方根法方式二 :Doolittle 分解 由矩阵乘法 a i j = n l ik u k j = k= 注意到 l i j = 0( j > i), 知计算第 j 行时 当 i = j 时, k= a j j = n l ik l jk (i, j =, 2,, n), k= j j l 2 jk = l j j = a j j l jk l jk k= 当 i > j 时, j j a i j = l ik l jk = l i j l j j = a i j l ik l jk = l i j = a i j j k= l ikl jk l j j k= k= /2

236 2.4. 平方根法方式二 :Doolittle 分解 由矩阵乘法 a i j = n l ik u k j = k= 注意到 l i j = 0( j > i), 知计算第 j 行时 当 i = j 时, k= a j j = n l ik l jk (i, j =, 2,, n), k= j j l 2 jk = l j j = a j j l jk l jk k= 当 i > j 时, j j a i j = l ik l jk = l i j l j j = a i j l ik l jk = l i j = a i j j k= l ikl jk l j j k= k= /2

237 2.4. 平方根法方式二 :Doolittle 分解 由矩阵乘法 a i j = n l ik u k j = k= 注意到 l i j = 0( j > i), 知计算第 j 行时 当 i = j 时, k= a j j = n l ik l jk (i, j =, 2,, n), k= j j l 2 jk = l j j = a j j l jk l jk k= 当 i > j 时, j j a i j = l ik l jk = l i j l j j = a i j l ik l jk = l i j = a i j j k= l ikl jk l j j k= k= /2

238 2.4. 平方根法方式二 :Doolittle 分解 由矩阵乘法 a i j = n l ik u k j = k= 注意到 l i j = 0( j > i), 知计算第 j 行时 当 i = j 时, k= a j j = n l ik l jk (i, j =, 2,, n), k= j j l 2 jk = l j j = a j j l jk l jk k= 当 i > j 时, j j a i j = l ik l jk = l i j l j j = a i j l ik l jk = l i j = a i j j k= l ikl jk l j j k= k= /2

239 2.4. 平方根法方式二 :Doolittle 分解 由矩阵乘法 a i j = n l ik u k j = k= 注意到 l i j = 0( j > i), 知计算第 j 行时 当 i = j 时, k= a j j = n l ik l jk (i, j =, 2,, n), k= j j l 2 jk = l j j = a j j l jk l jk k= 当 i > j 时, j j a i j = l ik l jk = l i j l j j = a i j l ik l jk = l i j = a i j j k= l ikl jk l j j k= k= /2

240 2.4. 平方根法方式二 :Doolittle 分解 for j =, 2,, n j /2 l j j = a j j l 2 jk k= for i = j+, j+2,, n j l i j = a i j l ik l jk /l j j end end k= 平方根法

241 2.4. 平方根法 例 用平方根法求解 x x 2 x 3 = 0 2 3, L = l l 2 l 22 l 3 l 32 l 33

242 2.4. 平方根法 例 用平方根法求解 x x 2 x 3 = 0 2 3, L = l l 2 l 22 l 3 l 32 l 33 解验证 A 的对称正定性 : a = > 0, = 8 4 > 0, = 6 > 0

243 2.4. 平方根法 例 用平方根法求解 解 x x 2 x 3 = 0 2 3, L = l l 2 l 22 l 3 l 32 l 33 l = a =, l 2 = a 2 = 2 l l 3 = a 3 = l l 22 = a 22 l 2 2 = 2 l 32 = a 32 l 3 l 2 l 22 = l 33 = a 33 l 2 3 l2 32 = 2

244 2.4. 平方根法 例 用平方根法求解 解 x x 2 x 3 = 0 2 3, L = 求解 LY = b, 得 3 求解 L T X = Y, 得 Y = (0,, 2) T. X = (,, ) T.

245 2. 高斯消去法 三角形方程组和三角分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

246 2.4.2 改进的平方根法 平方根法的局限 计算 l i j 时需要用到开方运算 只能求解对称正定线性方程组 而在很多工程问题中, 经常得到的是一个系数矩阵对称但不一定正定的线性方程组 为了避免开方运算和求解这类方程组, 可采用改进平方根法

247 2.4.2 改进的平方根法 平方根法的局限 计算 l i j 时需要用到开方运算 只能求解对称正定线性方程组 而在很多工程问题中, 经常得到的是一个系数矩阵对称但不一定正定的线性方程组 为了避免开方运算和求解这类方程组, 可采用改进平方根法

248 2.4.2 改进的平方根法 平方根法的局限 计算 l i j 时需要用到开方运算 只能求解对称正定线性方程组 而在很多工程问题中, 经常得到的是一个系数矩阵对称但不一定正定的线性方程组 为了避免开方运算和求解这类方程组, 可采用改进平方根法

249 2.4.2 改进的平方根法 平方根法的局限 计算 l i j 时需要用到开方运算 只能求解对称正定线性方程组 而在很多工程问题中, 经常得到的是一个系数矩阵对称但不一定正定的线性方程组 为了避免开方运算和求解这类方程组, 可采用改进平方根法

250 2.4.2 改进的平方根法 A = LDL T = l l n l n2 d d 2... d n l 2 l n l n2....

251 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

252 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

253 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

254 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

255 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

256 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

257 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

258 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

259 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

260 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

261 2.4.2 改进的平方根法存储方式及运算次序 a a 2 a 22 a 3 a 32 a a n, a n,2 a n,n a n a n2 a n,n a nn d l 2 d 2 l 3 l 32 d l n, l n,2 d n l n l n2 l n,n d n

262 2.4.2 改进的平方根法 由矩阵乘法 a i j = 注意到 l i j = 0( j > i), 知计算第 j 列时当 i = j 时, n l ik d k l jk k= j j j a j j = d k l 2 jk = d k l 2 jk + d j = d j = a j j d k l 2 jk k= k= k= 当 i > j 时, a i j = j j l ik d k l jk = l i j d j l j j = a i j l ik d k l jk = l i j = a i j j k= l ikd k l jk d j k= k=

263 2.4.2 改进的平方根法 由矩阵乘法 a i j = 注意到 l i j = 0( j > i), 知计算第 j 列时当 i = j 时, n l ik d k l jk k= j j j a j j = d k l 2 jk = d k l 2 jk + d j = d j = a j j d k l 2 jk k= k= k= 当 i > j 时, a i j = j j l ik d k l jk = l i j d j l j j = a i j l ik d k l jk = l i j = a i j j k= l ikd k l jk d j k= k=

264 2.4.2 改进的平方根法 由矩阵乘法 a i j = 注意到 l i j = 0( j > i), 知计算第 j 列时当 i = j 时, n l ik d k l jk k= j j j a j j = d k l 2 jk = d k l 2 jk + d j = d j = a j j d k l 2 jk k= k= k= 当 i > j 时, a i j = j j l ik d k l jk = l i j d j l j j = a i j l ik d k l jk = l i j = a i j j k= l ikd k l jk d j k= k=

265 2.4.2 改进的平方根法 由矩阵乘法 a i j = 注意到 l i j = 0( j > i), 知计算第 j 列时当 i = j 时, n l ik d k l jk k= j j j a j j = d k l 2 jk = d k l 2 jk + d j = d j = a j j d k l 2 jk k= k= k= 当 i > j 时, a i j = j j l ik d k l jk = l i j d j l j j = a i j l ik d k l jk = l i j = a i j j k= l ikd k l jk d j k= k=

266 2.4.2 改进的平方根法 由矩阵乘法 a i j = 注意到 l i j = 0( j > i), 知计算第 j 列时当 i = j 时, n l ik d k l jk k= j j j a j j = d k l 2 jk = d k l 2 jk + d j = d j = a j j d k l 2 jk k= k= k= 当 i > j 时, a i j = j j l ik d k l jk = l i j d j l j j = a i j l ik d k l jk = l i j = a i j j k= l ikd k l jk d j k= k=

267 2.4.2 改进的平方根法 由矩阵乘法 a i j = 注意到 l i j = 0( j > i), 知计算第 j 列时当 i = j 时, n l ik d k l jk k= j j j a j j = d k l 2 jk = d k l 2 jk + d j = d j = a j j d k l 2 jk k= k= k= 当 i > j 时, a i j = j j l ik d k l jk = l i j d j l j j = a i j l ik d k l jk = l i j = a i j j k= l ikd k l jk d j k= k=

268 2.4.2 改进的平方根法 改进平方根法 for j =, 2,, n j d j = a j j l 2 jk d k end end k= for i = j+, j+2,, n j l i j = a i j l ik d k l jk /d j k=

269 2.4.2 改进的平方根法 等价于 find Y s.t. LY = b; find X s.t. DL T X = Y. AX = b 即 for i =, 2,, n i y i = b i l ik y k k= end for i = n, n-,, x i = y n i l ki x k d i k=i+ end

270 2.4.2 改进的平方根法 例 用改进平方根法求解 x x 2 x 3 x 4 = 2 2

271 2.4.2 改进的平方根法 例 用改进平方根法求解 d = a = x x 2 x 3 x 4 = 2 2 l 2 = a 2 d = 4/5 l 3 = a 3 d = /5 l 4 = a 4 d = 0 d 2 = a 22 d l 2 2 = 2.8 l 32 = a 32 l 3 d l 2 d 2 =.4286 l 42 = a 4 l 4 d l 2 d 2 =

272 2.4.2 改进的平方根法 例 用改进平方根法求解 x x 2 x 3 x 4 = 2 2 d 3 = a 33 d l 2 3 d 2l 2 32 = l 43 = a 43 l 4 d l 3 l 42 d 2 l 32 d 3 = 4 d 4 = a 44 d l 2 4 d 2l 2 42 d 3l 2 43 = 5

273 2.4.2 改进的平方根法 5 求 LY = b 得 Y = (2, 0.6, , ) T 6 求 DL T X = Y 得 X = (.00002,.00003,.00004,.00002) T

274 2. 高斯消去法 2.. 顺序消去法 2..2 列主元消去法 2..3 全主元消去法 2..4 选主元消去法的应用 三角形方程组和三角分解 2.2. 三角方程组的解法 Gauss 变换 Doolittle 分解 选主元三角分解 平方根法及改进的平方根法 2.4. 平方根法 改进的平方根法 追赶法

275 2.5 追赶法 适用范围 : 三对角线性方程组 b c a 2 b 2 c 2 a 3 b 3 c a n b n c n a n b n x x 2 x 3. x n x n = d d 2 d 3. d n d n 系数矩阵 A 是三对角矩阵, 它常常是按行严格对角占优的, 即 b > c > 0, b i a i + c i, a i 0, c i 0, i = 2, 3,, n, b n > a n > 0.

276 2.5 追赶法 适用范围 : 三对角线性方程组 b c a 2 b 2 c 2 a 3 b 3 c a n b n c n a n b n x x 2 x 3. x n x n = d d 2 d 3. d n d n 系数矩阵 A 是三对角矩阵, 它常常是按行严格对角占优的, 即 b > c > 0, b i a i + c i, a i 0, c i 0, i = 2, 3,, n, b n > a n > 0.

277 2.5 追赶法 b c a 2 b 2 c 2 a 3 b 3 c 3 = l 2 l 3 u c u 2 c 2 u 3 c a n b n l n u n () u = b

278 2.5 追赶法 b c a 2 b 2 c 2 a 3 b 3 c 3 = l 2 l 3 u c u 2 c 2 u 3 c a n b n l n u n (2) l 2 u = a 2 = l 2 = a 2 u l 2 c + u 2 = b 2 = u 2 = b 2 l 2 c

279 2.5 追赶法 b c a 2 b 2 c 2 a 3 b 3 c 3 = l 2 l 3 u c u 2 c 2 u 3 c a n b n l n u n (2) l 2 u = a 2 = l 2 = a 2 u l 2 c + u 2 = b 2 = u 2 = b 2 l 2 c

280 2.5 追赶法 b c a 2 b 2 c 2 a 3 b 3 c 3 = l 2 l 3 u c u 2 c 2 u 3 c a n b n l n u n (3) l 3 u 2 = a 3 = l 3 = a 3 u 2 l 3 c 2 + u 3 = b 3 = u 3 = b 3 l 3 c 2

281 2.5 追赶法 b c a 2 b 2 c 2 a 3 b 3 c 3 = l 2 l 3 u c u 2 c 2 u 3 c a n b n l n u n (3) l 3 u 2 = a 3 = l 3 = a 3 u 2 l 3 c 2 + u 3 = b 3 = u 3 = b 3 l 3 c 2

282 2.5 追赶法 b c u c a 2 b 2 c 2 l 2 u 2 c 2 a 3 b 3 c 3 = l 3 u 3 c a n b n l n u n u = b, 递推关系 l i = a i, u i i = 2, 3,, n u i = b i l i c i

283 2.5 追赶法 例 求解微分方程 u xx = f, u(a) = u(b) = 0. x (a, b), 解 网格剖分 : a = x 0 < x < < x n = b, h = b a n 2 差分离散 : u xx (x i ) u i+ 2u i + u i h 2, i =, 2,, n

284 2.5 追赶法 例 求解微分方程 u xx = f, u(a) = u(b) = 0. x (a, b), 解 网格剖分 : a = x 0 < x < < x n = b, h = b a n 2 差分离散 : u xx (x i ) u i+ 2u i + u i h 2, i =, 2,, n

285 2.5 追赶法 例 求解微分方程 u xx = f, u(a) = u(b) = 0. x (a, b), 解 网格剖分 : a = x 0 < x < < x n = b, h = b a n 2 差分离散 : u xx (x i ) u i+ 2u i + u i h 2, i =, 2,, n

286 2.5 追赶法 解 3 生成矩阵 : u u 2. u n 2 u n = f f 2. f n 2 f n

287 2.5 追赶法 解 4 用追赶法求解线性方程组 /2 = 2/3 3/4 4/5 2 3/2 4/3 5/4 6/5

288 2.5 追赶法 存储方式 系数矩阵与右端项的存储用四个 n 维向量 a, b, c, d 分别来存储三条对角线上的元素及右端项的值 2 l 与 u 的存储 l 的各元素存储在 a 对应的元素位置,u 的各元素存储在 b 对应的元素位置上 3 未知量 x 的存储 x 的各元素存储在 d 对应的元素位置