《数值分析》课程教学资源（PPT讲稿）第三章 解线性方程组的直接法（2/2）

§2三角分解法 Matrix Factorization >高斯消元法的矩阵形式/ Matrix Form of ge. Step 1: m=a/au(auto b 记L ,则L1[A0b m○ Step n-1: 2其中 LmLm-2.[A 6 1222 (

§2 三角分解法 /* Matrix Factorization */ ➢ 高斯消元法的矩阵形式 /* Matrix Form of G.E. */： Step 1: / ( 0) mi1 = ai1 a11 a11  记 L1 = 1 . . . 1 1 1 21 mn m − − ，则 [ ] = (1) (1) 1 L A b  (1) 1 (1) 1 (1) 11 a ... a b n (2) A (2) b  Step n − 1:                 = − − ( ) (2) 2 (1) 1 ( ) (2) 2 (2) 2 2 (1) 1 (1) 1 2 (1) 1 1 1 2 1 . . . . . . ... ... ... ... n n n nn n n n n b b b a a a a a a L L L A b  其中 Lk = 1 . . . 1 1 , 1, n k k k m m − − +

$2 Matrix Factorization-Matrix Form of GE 记为 k+1,k k air Factorize A first, then for every you only have to ix*/ 记U solve two simple triangular systems Ly=b and Ux=y m A的’U /*LU factor- n

§2 Matrix Factorization – Matrix Form of G.E. = −1 Lk 1 . . . 1 1 , 1, n k k k m m + = − − − − 1 1 1 2 1 1 ... L L Ln 1 1 1 mi, j 记为 L 单位下三角阵 /* unitary lower-triangular matrix */ 记 U = ( ) (2) 2 (2) 22 (1) 1 (1) 12 (1) 11 . . . ... ... ... n nn n n a a a a a a  A = LU A 的 LU 分解 /* LU factorization */ Hey hasn’t GE given me enough headache? Why do I have to know its matrix form??! When you have to solve the system for different with a fixed A. b  Could you be more specific, please? Factorize A first, then for every you only have to solve two simple triangular systems and . b  Ly b   = Ux y   =

$2 Matrix Factorization-Matrix Form of GE 定理若4的所有顺序主子式eng principal submatrices+均不为0,则A的LU分解唯—(其 中L为单位下三角阵)。 证明:由§1中定理可知,LU分解存在。下面证明唯一性。 若不唯一,则可设A=L1U1=L2U2,推出 L L2 U2U2=LL2=/ Lower-triangular Upper-triangular With diagonal entries 1 注:L为一般下三角阵而U为单位上三角阵的分解称为 Crout分解。 实际上只要考虑A*的LU分解,即4=LU,则 A=U*即是A的 Crout分解

§2 Matrix Factorization – Matrix Form of G.E. 定理 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则 A 的 LU 分解唯一（其 中 L 为单位下三角阵）。 证明：由§1中定理可知，LU 分解存在。下面证明唯一性。 若不唯一，则可设 A = L1U1 = L2U2 ，推出 = −1 U1 U2 2 1 1 1 2 2 2 1 L1 L U U L L − − − = Upper-triangular Lower-triangular With diagonal entries 1 = I ✓ 注： L 为一般下三角阵而 U 为单位上三角阵的分解称为 Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Crout 分解。 A LU ~ ~ * = * ~ * ~ A=U L

$2 Matrix Factorization-Doolittle >道立特分解法/ Doolittle Factorization: LU分解的紧凑格式/ compact form 思 比较法直接导出L和U的计算公式。 很浪费哦 11 min(i,j) →a ∑l

§2 Matrix Factorization – Doolittle ➢ 道立特分解法 /* Doolittle Factorization */： —— LU 分解的紧凑格式 /* compact form */ 反复计算, 很浪费哦 …… 通过比较法直接导出L 和 U 的计算公式。 思 路                           =               nn n n nn n n u u u l l a a a a . . . . . . ... ... ... 1 ... . . . 1 1 ... . . . . . . . . . . . . ... 1 1 1 1 2 1 1 1 1 1 = min( , ) 1 i j k i k uk j  = l ai j

=∑1 $2 Matrix Factorization-Doolittle 固定i 对j=;计+1,,n有a=∑l+ur k=1 →=ay-l(a k=1 将i,j对换,对j=,计1, 一般采用列主元 法增强稳定性。但注意 →=(a1-2u)b也必须做应的 k=1 行交换。 Algorithm: Doolittle Factorization Step l:u1i-aijijl JI/U n Step 2: compute(a)and (b fori=2,., n-1; S L…=〖 L

§2 Matrix Factorization – Doolittle = = min( , ) 1 i j k i j i k uk j a l 固定 i : 对 j = i, i+1, …, n 有 kj ij i k aij = l iku + u − = 1 1 l ii = 1 kj i k ui j ai j l i ku − =  = − 1 1 a 将 i ，j 对换，对 j = i, i+1, …, n 有 ki ji ii i k a ji = l jku + l u − = 1 1 i i i k l j i (a j i l j kuk i)/ u 1 1  − =  = − b Algorithm: Doolittle Factorization Step 1: u1j = a1j ; l j1 = aj1 / u11; ( j = 1, …, n ) Step 2: compute and for i = 2, …, n−1; Step 3: a b  − = = − 1 1 n k nn nn nkukn u a l 一般采用列主元 法增强稳定性。但注意 也必须做相应的 行交换。 b 

$2 Matrix Factorization-Choleski >平方根法/ Choleski's Method*: 对称/ symmetric*正定/ positive definite 矩阵的分解法 定义一个矩阵A=(an)mn称为对称阵,如果an=a。 定义一个矩阵A称为正定阵,如果xAx>0对任意非 零向量x都成立。 m回顾:对称正定阵的几个重要性质 中P亦对称定,且a120 中A的顺序主子阵/ eading principal submatrices*Ak亦对 称正定 中A的特征信6封mx 任意y 令A的全部顺序篮(竟类0∈R有 设对应特征值的非零特征向量 因为de(4)=24A1 =1

§2 Matrix Factorization – Choleski ➢ 平方根法 /* Choleski’s Method */： ——对称 /* symmetric */ 正定 /* positive definite */ 矩阵的分解法 定义 一个矩阵 A = ( aij )nn 称为对称阵，如果 aij = aji 。 定义 一个矩阵 A 称为正定阵，如果 对任意非 零向量 都成立。 x Ax  0 T  x  回顾：对称正定阵的几个重要性质  A−1 亦对称正定，且 aii > 0 若不然，则 0   Ax = 存在非零解，即 x Ax = 0 T  存在非零解。  1 1 1 1 , ( ) ( ) − − − − AA = I A A = I  A = A T T T  对任意 , 存在 , 使得 , 即 。 0   x  0   y  Ay x   = y A x  −1  = 0 1 1 = =  − − x A x y AA Ay y Ay T  T  T   a = x Ax  0 其中 T ii   T x = (0...1...0)  第 i 位  A 的顺序主子阵 /* leading principal submatrices */ Ak 亦对 称正定 对称性显然。对任意 有 , 其中 。 k xk  0 R   x A x = x Ax  0 T k k T k     k n R x x           = 0 0      A 的特征值 /* eigen value */ i > 0 设对应特征值  的非零特征向量 为 ，则 。 2 0 x Ax x x x T  T   x  =  =    A 的全部顺序主子式 det ( Ak ) > 0 因为 = = n i A i 1 det( ) 

$2 Matrix Factorization-Choleski 将对称正定阵A做LU分解 ua记为DU A对称→L=U即A=LDL 则L=L仍是下三角阵 记D12=4 A=LLT 定理「设矩阵对称正定,则存在非奇异下三角阵L∈R 使得gg若限定对角元为正,则分解唯 注:对于对称正定阵A,从m=∑l可知对任意ksi 有|l1k|sVa即L的元素不会增大,误差可控,不 需选主元

§2 Matrix Factorization – Choleski 将对称 正定阵 A 做 LU 分解 U = uij = u11 uij / uii 1 1 1 u22 unn 记为 DU ~ A 对称 T L U ~ = 即 T A = LDL 记 D1/2 = u11u22 unn Why is Since det( uiiA> 0? k ) > 0 ~ 1/ 2 则 L = LD 仍是下三角阵 T A LL ~~ = n n L R  定理 设矩阵A对称正定，则存在非奇异下三角阵  使得 。若限定 L 对角元为正，则分解唯一。 T A = L L 注： 对于对称正定阵 A ，从 可知对任意k  i 有 。即 L 的元素不会增大，误差可控，不 需选主元。  = = i k ii ik a l 1 2 ik aii | l | 

8 2 Matrix Factorization-Choleski Algorithm: Choleski's Method To factor the symmetric positive definite nxn matrix A into LL, where L is lower triangular Input: the dimension n; entries ai for lsi,jsnofa Output: the entries Li for lsjsiand 1s n of L Step i set HW: p 54 Sep2Forj=2,…,m.set #2,#5,#6 s3F因为A对称,所以只需存半个A,即 [a(n+1)/2]={a1,a21,a2, 其中 Step A[x(-1)2+ Sp6se运算量为O(n6),比普通LU Sp7d分解少一半,但有n次开方。用A=LDL STOP 分解,可省开方时间(p5051

§2 Matrix Factorization – Choleski Algorithm: Choleski’s Method To factor the symmetric positive definite nn matrix A into LLT, where L is lower triangular. Input: the dimension n; entries aij for 1 i, j  n of A. Output: the entries l ij for 1 j  i and 1 i  n of L. Step 1 Set ; Step 2 For j = 2, …, n, set ; Step 3 For i = 2, …, n−1, do steps 4 and 5 Step 4 Set ; Step 5 For j = i+1, …, n, set ; Step 6 Set ; Step 7 Output ( l ij for j = 1, …, i and i = 1, …, n ); STOP. 11 a11 l = 1 1 11 l a / l j = j  − = = − 1 1 2 i k ii ii ik l a l ( ) ii i k ji ji jk ik l a  l l l − = = − 1 1  − = = − 1 1 2 n k nn nn nk l a l 因为A 对称，所以只需存半个 A，即 其中 An(n+1)/ 2=  a11, a21, a22 , ..., an1 , ..., ann  a Ai i j ij = ( −1)/ 2 + 运算量为 O(n 3 /6)， 比普通LU 分解少一半，但有 n 次开方。用A = LDLT 分解，可省开方时间(p.50-51)。 HW: p.54 #2, #5, #6

82 Matrix Factorization-Tridiagonal System >追赶法解三对角方程组 Crout Reduction for Tridiagonal Linear System*/ 与GE类似,一旦 sep:对A作(a=0则算法中断,故并非任何 三对角阵都可以用此方法分解。 比较等式两边 的元素,可得到计 ∵n1算公式(p52)。 Yu a Step2:追—即解Ly=∫:y (f-rv-1) sep3:赶—即解Ux=j:xn=p,x=y-月x(=n-1,…,1

§2 Matrix Factorization – Tridiagonal System ➢ 追赶法解三对角方程组 /* Crout Reduction for Tridiagonal Linear System */                 =                                 − − − n n n n n n n f f f x x x a b a b c a b c b c 2 1 2 1 1 1 1 2 2 2 1 1 Step 1: 对 A 作Crout 分解                                 = − 1 1 1 1 2 1 n n n A       直接比较等式两边 的元素，可得到计 算公式（p.52）。 Step 2: 追——即解 L y f ：   = , 1 1 1  f y = ( 2, ... , ) ( ) 1 i n f r y y i i i i i = − = −  Step 3: 赶——即解U x y ：   = , ( 1, ... , 1) xn = yn xi = yi −  i xi+1 i = n− 与G.E.类似，一旦 i = 0 则算法中断，故并非任何 三对角阵都可以用此方法分解

8 2 Matrix Factorization -Tridiagonal System 定理若A为对角占优 / diagonally dominant*的三对角 阵,且满足|b|c1|>0,|bn|>an|>0,a1≠0,C1≠0,则追赶 法可解以A为系数矩阵的方程组 注 矿如果A是严格对角占优阵,则不要求三对角线上的 所有元素非零。 矿根据不等式|B|k1,|b1|-|a1|b1-yB1|<|b1|+|a1 可知:分解过程中,矩阵元素不会过分增大,算法 保证稳定。 ⑦运算量为O(6n)

§2 Matrix Factorization – Tridiagonal System 定理 若 A 为对角占优 /* diagonally dominant */ 的三对角 阵，且满足 ，则追赶 法可解以 A 为系数矩阵的方程组。 | b1 || c1 | 0, | bn || an | 0, ai  0 , ci  0 Hey, what does diagonally dominant mean??? It means that the diagonal entries of the matrix are very LARGE. Well, how large is LARGE? They satisfy the following inequality:    j i aii aij | | | | 注：  如果 A 是严格对角占优阵，则不要求三对角线上的 所有元素非零。  根据不等式 可知：分解过程中，矩阵元素不会过分增大，算法 保证稳定。  运算量为 O(6n)。 | | 1 , | | | | | | | | | | i  bi − ai  bi − i  i−1  bi + ai  