1、2 三角分解法 /* Matrix Factorization */ 高斯消元法的矩陣形式 /* Matrix Form of G.E. */：Step 1:記 L1 =，則Step n 1:其中 Lk =2 Matrix Factorization Matrix Form of G.E.記為L單位下三角陣/* unitary lower-triangular matrix */記 U =A 的 LU 分解/* LU factorization */Hey hasnt GE given me enough headache? Why do I have to know its matrix f

2、orm?!When you have to solve 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.2 Matrix Factorization Matrix Form of G.E.證明：由1中定理可知，LU 分解存在。事實上,其中 形如其中 若A的所有順序主子式 /* determinant of lead

3、ing principal submatrices */ 均不為0，則 A 的 LU 分解唯一（其中 L 為單位下三角陣）。定理記為分塊形式顯然從而因此 即A有LU分解的充要條件是A的所有順序主子式非奇異。2 Matrix Factorization Matrix Form of G.E.其中 為 的k階順序主子陣， 為 的k階順序主子陣。2 Matrix Factorization Matrix Form of G.E.下面證明唯一性。若不唯一，則可設(shè) A = L1U1 = L2U2 ，推出Upper-triangularLower-triangularWith diagonal entri

4、es 1注： L 為一般下三角陣而 U 為單位上三角陣的分解稱為Crout 分解。 實際上只要考慮 A* 的 LU 分解，即 ，則 即是 A 的 Crout 分解。2 Matrix Factorization Doolittle 道立特分解法 /* Doolittle Factorization */： LU 分解的緊湊格式 /* compact form */反復(fù)計算,很浪費哦 通過比較法直接導(dǎo)出L 和 U 的計算公式。思路2 Matrix Factorization Doolittle固定 i :對 j = i, i+1, , n 有l(wèi)ii = 1a將 i ，j 對換，對 j = i, i

5、+1, , n 有b Algorithm: Doolittle FactorizationStep 1: u1j = a1j; lj1 = aj1 / u11; ( j = 1, , n )Step 2: compute and for i = 2, , n1;Step 3: ab一般采用列主元法增強穩(wěn)定性。但注意 也必須做相應(yīng)的行交換。2 Matrix Factorization Cholesky 平方根法 /* Choleskys Method */： 對稱 /* symmetric */ 正定 /* positive definite */ 矩陣的分解法回顧：對稱正定陣的幾個重要性質(zhì) A

6、1 亦對稱正定，且 aii 0若不然，則存在非零解，即存在非零解。對任意 , 存在 , 使得 ,即 。 其中第 i 位 A 的順序主子陣 /* leading principal submatrices */ Ak 亦對 稱正定對稱性顯然。對任意 有 , 其中 。 A 的特征值 /* eigen value */ i 0 設(shè)對應(yīng)特征值 的非零特征向量為 ，則 。 A 的全部順序主子式都有 det ( Ak ) 0因為定義一個矩陣 A = ( aij )nn 稱為對稱陣，如果 aij = aji 。定義一個矩陣 A 稱為正定陣，如果 對任意非零向量 都成立。2 Matrix Factorizat

7、ion Choleski將對稱 正定陣 A 做 LU 分解U =uij=u11uij / uii111u22unn記為 A 對稱即記 D1/2 =Why is uii 0?Since det(Ak) 0則 仍是下三角陣定理 設(shè)矩陣A對稱正定，則存在非奇異下三角陣 使得 。若限定 L 對角元為正，則分解唯一。注： 對于對稱正定陣 A ，從 可知對任意k i 有 。即 L 的元素不會增大，誤差可控，不需選主元。2 Matrix Factorization Cholesky Algorithm: Choleskys MethodTo factor the symmetric positive def

8、inite 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 n of L. Step 1 Set ;Step 2 For j = 2, , n, set ;Step 3 For i = 2, , n1, do steps 4 and 5Step 4 Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ;Step

9、 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP. 因為A 對稱，所以只需存半個 A，即其中運算量為 O(n3/6)， 比普通LU分解少一半，但有 n 次開方。用A = LDLT 分解，可省開方時間(p.50-51)。2 Matrix Factorization Tridiagonal System 追趕法解三對角方程組 /* Crout Reduction for Tridiagonal Linear System */Step 1: 對 A 作LU分解，比如（Crout 分解、Doolittle分解）直接比較等式兩邊的元素，可得到計

10、算公式（p.182）。Step 2: 追即解 ：Step 3: 趕即解 ：與G.E.類似，一旦i = 0 則算法中斷，故并非任何三對角陣都可以用此方法分解。2 Matrix Factorization Tridiagonal System定理 若 A 為對角占優(yōu) /* diagonally dominant */ 的三對角陣，且滿足 ，則追趕法可解以 A 為系數(shù)矩陣的方程組。注： 如果 A 是嚴格對角占優(yōu)陣，則不要求三對角線上的所有元素非零。 根據(jù)不等式 可知：分解過程中，矩陣元素不會過分增大，算法保證穩(wěn)定。 運算量為 O(6n)。2 Matrix Factorization Tridiago

11、nal SystemLab 06. Crout Reduction for Tridiagonal Linear SystemsApply Crout Reduction to solve a given nn tridiagonal linear systemInputThere are several sets of inputs. For each set:The 1st line contains an integer 100 n 0 which is the size of a matrix. n = 1 signals the end of file.The 2nd line co

12、ntains n1 real numbers .The 3rd line contains n real numbers .The 4th line contains n1 real numbers .The 5th line contains n real numbers .The numbers are separated by spaces.2 Matrix Factorization Tridiagonal SystemOutputEach entry of the solution is to be printed as in the C fprintf: fprintf(outfile, %16.8en, x ); If the method fails to give a solution, print the message “TheCroutmethodfailed.n”. /* here represents a space*/The outputs of two test cases must be seperated by a blank line.Sample Inpu