PDF《第五章》

11 ( 2, ..., ) i i m a a i n = = 设 ,计算 (2) (1) (1)

1 1 (2) (1) (1)

1 1 ij ij i j i i i a a m a b b m b = ? = ? 其中 ( , 2, ..., ) i j n = 记(1)

1 (1) (1) (1) (1) ( ) , ij n n n b A a A b b b * ? ? ? ? = = = = ? ? ? ? ? ? ? ,即(1) (1) , ij ij i i a a b b = = (1) (1) (1) (1)

11 12

1 1 n a a a b ? (2) (2)

22 2 (2) (2)

2 n n nn a a a a ? ? ? ? ? (2)

2 (2) n b b ? (2) A = 第1步:消第

1 列14 Gauss 消去法 依次将 A(2) 的第i行Cmi2 * 第2行,得 其中 ( , 3, ..., ) i j n = (1) (1) (1) (1) (1)

11 12

13 1

1 n a a a a b ? (3) (3)

33 3 (3) (3)

3 n n nn a a a a ? ? ? ? ? (3)

3 (3) n b b ? (3) A = 第2步:消第

2 列(2) (2)

2 2

22 ( 3, ..., ) i i m a a i n = = 设 ,计算 (2)

22 0 a ≠ (2) (2) (2) (2)

22 23

2 2 n a a a b ? (3) (2) (2)

2 2 (3) (2) (2)

2 2 ij ij i j i i i a a m a b b m b ? = ? ? = ? ?

15 Gauss 消去法 第k步:消第 k 列 依此类推,第k-1 步 后可得 (1) (1) (1) (1)

11 1

1 1 ? ? ? ? ? ? ? ? ? ? ? ? k n k k k k kk kn k k k k nk nn n a a a b A a a b a a b ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ( ) ( ) k k ik ik kk m a a = 设()0kkk a ≠ ( 1) ( 1) k k k ij ij ik kj k k k i i ik k a a m a b b m b + + = ? = ? ( i = k+1, …, n ) 先计算: 再计算: ( i = k+1, …, n ) ( 1) k A +

16 Gauss 消去法 第n-1 步后 (1) (1) (1) (1)

11 12

1 1

1 (2) (2) (2)

2 22

2 2 ( ) ( ) n n n n n n nn a a a b x x a a b x b a ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) n n A x b = 回代求解: ( ) ( ) n n n n nn x b a =

1 ( ) n i i i i i ij j ii j i x b a x a = + = ? ∑ ( i = n-1, …,

1 )

17 几点注记 ? 主元: ( 1, 2, ..., ) i n = ( ) i ii a ? Gauss 消去法能进行到底的条件:主元全不为

0 定理: (i = 1, 2, ..., n)的充要条件是 A 的顺序主 子式不为零,即()0iii a ≠

11 1

1 11

1 0, 0, 1,2, , i i i ii a a D a D i n a a ? ? ? ? ? ? 推论: (1) ( )

11 1

1 , , 2, , i ii i i a D a D D i n ? = = = ?

18 运算量 第k步:消第 k 列()()(1, ..., ) k k ik ik kk m a a i k n + = = 计算 计算 ( 1) ( 1) k k k ij ij ik kj k k k i i ik k a a m a b b m b + + = ? = ? ( i = k+1, …, n ) 回代求解: ( ) ( ) n n n n nn x b a =

1 ( ) n i i i i i ij j ii j i x b a x a = + = ? ∑ ( i = n-1, …, 2,1 ) n C k 次(n C k)2 次nCk次n(n+1)/2 次Gauss 消去法的乘除运算量为:

3 2

3 3 n n n + ? ? 乘除运算 的次数 ? 加减运算 的次数

3 2

5 3

2 6 n n n + ?

19 LU 分解 ? 换个角度看 Gauss 消去法 矩阵的三角分解过程 矩阵分解,即将一个较复杂的矩阵分解成若干结构简单的矩 阵的乘积,是矩阵计算中的一个很重要的技术.

20 LU 分解 则A(k) 与A(k+1) 之间的关系式可以表示为: ( 1) ( ) k k k A L A + = 其中: 1, ,

1 1

1 1 k k n k k m m L + ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ( ) ( ) k k ik ik kk m a a = ( i = k + 1, …, n ) 将Gauss 消去过程中第 k-1 步消元后的系数矩阵记为: (1) (1) (1)

11 1

1 ( ) ( ) k n k k k kk kn k k nk nn a a a A a a a a ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ( k = 1, …, n-1)

21 LU 分解 LU 分解 于是有: ( ) (1)

1 2

1 n n A L L L A ? = ?

1 )

1 (1) (

2 1 ( ) n n A L L A A L ? ? = = ? 容易验证: 1, ,

1 1

1 1

1 k k n k k m m L? + ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? ( k = 1, …, n-1) 且2,1 3,1 3,2 4,1 4,2 4,3 ,1 ,2 ,

1 1

1 1

2 3

1 ,

1 1

1 1

1 1 ? ? ? ? ? ? n n n n n n m m m m m m m m m m L L L ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ?