1、4 三角分解法 /* Matrix Factorization */, 高斯消元法的矩陣形式 /* Matrix Form of G.E. */：,Step 1:,4 Matrix Factorization Matrix Form of G.E.,單位下三角陣 /* unitary lower-triangular matrix */,A 的 LU 分解 /* LU factorization */,Hey hasnt GE given me enough headache? Why do I have to know its matrix form?!,When you have to s

2、olve the system for different with a fixed A.,Could you be more specific, please?,Factorize A first, then for every you only have to solve two simple triangular systems and .,4 Matrix Factorization Matrix Form of G.E.,證明：由2中定理可知，LU 分解存在。下面證明唯一性。,若不唯一，則可設(shè) A = L1U1 = L2U2 ，推出,Upper-triangular,Lower-tr

3、iangular With diagonal entries 1,注： L 為一般下三角陣而 U 為單位上三角陣的分解稱為Crout 分解。 實(shí)際上只要考慮 AT 的 LU 分解，即 ，則 即是 A 的 Crout 分解。,4 Matrix Factorization Doolittle, 道立特分解法 /* Doolittle Factorization */： LU 分解的緊湊格式 /* compact form */,反復(fù)計(jì)算, 很浪費(fèi)哦 ,4 Matrix Factorization Doolittle,固定 i : 對(duì) j = i, i+1, , n 有,lii = 1,a,將 i

4、，j 對(duì)換，對(duì) j = i, i+1, , n 有,b,一般采用列主元 法增強(qiáng)穩(wěn)定性。但注意 也必須做相應(yīng)的 行交換。,例：,解：,再求第一列,先求第一行,4 Matrix Factorization Doolittle,例 用直接三角分解法求解,解：用分解公式計(jì)算得,求解,，得,，得,4 Matrix Factorization Doolittle,4 Matrix Factorization Choleski, 平方根法 /* Choleskis Method */： 對(duì)稱 /* symmetric */ 正定 /* positive definite */ 矩陣的分解法,回顧：對(duì)稱正定陣

5、的幾個(gè)重要性質(zhì), A1 亦對(duì)稱正定，且 aii 0,若不然，則,對(duì)任意 , 存在 , 使得 , 即 。, A 的順序主子陣 /* leading principal submatrices */ Ak 亦對(duì) 稱正定,對(duì)稱性顯然。對(duì)任意 有 , 其中 。, A 的特征值 /* eigen value */ i 0,設(shè)對(duì)應(yīng)特征值 的非零特征向量 為 ，則 。, A 的全部順序主子式 det ( Ak ) 0,因?yàn)?4 Matrix Factorization Choleski,將對(duì)稱 正定陣 A 做 LU 分解,即,Why is uii 0?,Since det(Ak) 0,則 仍是下三角陣,注：

6、 對(duì)于對(duì)稱正定陣 A ，從 可知對(duì)任意k i 有 。即 L 的元素不會(huì)增大，誤差可控，不需選主元。,4 Matrix Factorization Choleski,Algorithm: Choleskis Method To factor the symmetric positive definite nn 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 lij for 1 j i and 1 i

7、n of L. Step 1 Set ; Step 2 For j = 2, , n, set ; Step 3 For i = 2, , n1, do steps 4 and 5 Step 4 Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ; Step 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP.,因?yàn)锳 對(duì)稱，所以只需存半個(gè) A，即 其中,運(yùn)算量為 O(n3/6)， 比普通LU 分解少一半，但有 n 次開方。用A = LDLT 分解，可省開方時(shí)間(p.173)。,HW: p.20

8、3 #9, #10, #11,4 Matrix Factorization Tridiagonal System, 追趕法解三對(duì)角方程組 /* Crout Reduction for Tridiagonal Linear System */,Step 1: 對(duì) A 作Crout 分解,直接比較等式兩邊的元素，可得到計(jì)算公式。,Step 2: 追即解 ：,Step 3: 趕即解 ：,與G.E.類似，一旦 i = 0 則算法中斷，故并非任何 三對(duì)角陣都可以用此方法分解。,4 Matrix Factorization Tridiagonal System,Hey, what does diagona

9、lly dominant mean?,It means that the diagonal entries of the matrix are very LARGE.,Well, how large is LARGE?,They satisfy the following inequality:,注： 如果 A 是嚴(yán)格對(duì)角占優(yōu)陣，則不要求三對(duì)角線上的所有元素非零。 根據(jù)不等式 可知：分解過程中，矩陣元素不會(huì)過分增大，算法保證穩(wěn)定。 運(yùn)算量為 O(6n)。,5 線性方程組的誤差分析 /* Error Analysis for Linear system of Equations */,求解 時(shí)，

10、A 和 的誤差對(duì)解 有何影響？, 設(shè) A 精確， 有誤差 ，得到的解為 ，即,絕對(duì)誤差放大因子,又,相對(duì)誤差放大因子,5 Error Analysis for ., 設(shè) 精確，A有誤差 ，得到的解為 ，即,Wait a minute Who said that ( I + A1 A ) is invertible?,大,(只要 充分小，使得,5 Error Analysis for ., cond (A) 取決于A，與解題方法無關(guān)。,常用條件數(shù)有：,cond (A)1,cond (A),cond (A)2,特別地，若 A 對(duì)稱，則,條件數(shù)的性質(zhì)： A可逆，則 cond (A)p 1； A可逆，

11、 R 則 cond ( A) = cond (A) ； A正交，則 cond (A)2=1； A可逆，R正交，則 cond (RA)2 = cond (AR)2 = cond (A)2 。,5 Error Analysis for .,精確解為,例：,計(jì)算cond (A)2 。,A1 =,解：考察 A 的特征根,39206 1, 測(cè)試病態(tài)程度：,此時(shí)精確解為,2.0102 200%,5 Error Analysis for .,cond (H2) =,27,cond (H3) ,748,cond (H6) =,2.9 106,cond (Hn) as n ,注：一般判斷矩陣是否病態(tài)，并不計(jì)算A1，而由經(jīng)驗(yàn)得出。 行列式很大或很?。ㄈ缒承┬小⒘薪葡嚓P(guān)）； 元素間相差大數(shù)量級(jí)，且無規(guī)則； 主元消去過程中出現(xiàn)小主元； 特征值相差大數(shù)量級(jí)。,5 Error Analysis for .