1第五章

解線性方程組的直接方法——矩陣三角分解法2直接三角分解法

MatrixFactorizationmethod

直接三角分解的基本思想如果將線性方程組Ax=b的系數矩陣A分解成兩個三角矩陣L和U，即A=LU（也稱為LU分解），則：

問題：對于一般非奇異矩陣是否存在LU分解？3LU分解

Gauss消去過程其實就是一個矩陣的三角分解過程則A(k)

與A(k+1)之間的關系式可以表示為：其中：(i=k+1,…,n)將Gauss消去過程中第k-1步消元后的系數矩陣記為：(k=1,…,n-1)4LU分解LU分解記：，則其中：L---單位下三角矩陣，U---上三角矩陣LU分解于是有：容易驗證：(k=1,…,n-1)(Doolittle分解)5LU分解存在唯一性LU分解存在高斯消去法不被中斷定理：若A的所有順序主子式不為零，則A存在唯一的LU分解所有順序主子式不為零6PLU分解列主元Gauss消去法對應的矩陣分解為PLU

分解定理：若A非奇異，則存在排列矩陣P，使得

PA=LU其中L

為單位下三角矩陣，U

為上三角矩陣7注

（1）

L

為單位下三角陣而U

為一般上三角陣的分解稱為Doolittle分解（2）

L

為一般下三角陣而U

為單位上三角陣的分解稱為Crout分解。

8計算LU分解利用矩陣乘法直接計算LU分解LU=A比較等式兩邊的第一行得：u1j=a1j比較等式兩邊的第一列得：比較等式兩邊的第二行得：比較等式兩邊的第二列得：(j=1,…,n)(i=2,…,n)(j=2,…,n)(i=3,…,n)U

的第一行L

的第一列U

的第二行L

的第二列9計算LU分解第k

步：此時U

的前k-1行和

L

的前k-1列已經求出比較等式兩邊的第k行得：比較等式兩邊的第k列得：直到第n

步，便可求出矩陣L

和U

的所有元素。(j=k,…,n

)(i=k+1,…,n

)10LU分解算法算法：(LU分解

)fork=1tonendj=k,…,ni=k+1,…,n運算量：(n3-n)/3為了節省存儲空間，通常用A

的絕對下三角部分來存放L(對角線元素無需存儲)，用

A

的上三角部分來存放U

11例：用矩陣的Doolittle分解解方程組解：設

1213為便于記憶，我們給出L、U分解緊湊格式:14求解三對角方程組的追趕法

Thomasmethodfortridiagonallinearsystem有一類方程組,在今后要學習的樣條插值,微分方程數值求解中等問題中有著重要的作用,即三對角線方程組,其形式為:15

定理：若A為對角占優三對角陣，且滿足則方程組有唯一的LU分解。16追趕法對角占優的三對角矩陣的LU分解

計算公式i=2,3,…,n-117追趕法A

三對角矩陣（對角占優）i=2,3,…,n算法：(追趕法

)i=n-1,…,2,1i=2,3,…,n-118計算量：5n-4

計算及的過程,稱為追的過程，計算方程組的解的過程稱為趕的過程，因此上述方法稱為追趕法。19functionpursue[A,b][n,m]=size(A);a=zeros(1,n);a(2:n)=diag(A,-1);c=diag(A,1);b=diag(A);ifb(1)==0error('主對角元素不能為0');return;endalpha(1)=b(1);beta(1)=c(1)/b(1);追趕法Matlab程序20fori=2:n-1alpha(i)=b(i)-a(i)*beta(i-1);ifalpha(i)==0error('錯誤:在解方程過程中α為0');return;endbeta(i)=c(i)/alpha(i);endy(1)=f(1)/b(1);fori=2:ny(i)=(f(i)-a(i)*y(i-1))/alpha(i);endX(n)=y(n);fori=n-1:-1:1X(i)=y(i)-beta(i)*X(i+1);end21對稱正定方程組的Cholesky方法

對稱正定矩陣概念：

若A為對稱正定矩陣，則：

1.A的所有順序主子矩陣Ak也是對稱正定陣；

2.A是非奇異陣，且A1也是對稱正定陣；

3.A的對角線元素aii>0(i=1,2,…,n)；

4.A的所有特征值>0；

5.A的所有順序主子式均為正數，即det(Ak)>0,22對稱正定矩陣Cholesky分解對稱正定矩陣的三角分解－－Cholesky

分解定理：設A

是對稱矩陣，若A

的所有順序主子式都不為0，則A

可唯一分解為其中L

為單位下三角陣，D

為對角矩陣A=LDLT定理：（Cholesky分解）若A

對稱正定，則A

可唯一分解為其中L

為下三角實矩陣，且對角元素都大于0A=LLT23計算Cholesky分解

Cholesky

分解的計算直接比較等式兩邊的元素

計算公式24Cholesky分解算法for

j=1tonendi=j+1,…,n算法：(Cholesky分解

)25平方根法A

對稱正定計算A

的Cholesky分解解方程：Ly=b

和LTx=yi=2,3,…,n算法：(解對稱正定線性方程組的平方根法

)i=n-1,…,2,126注

平方根法無需選主元，計算過程也是穩定的。

由于A的對稱性，平方根法的乘除運算量為n3/6數量級，約為直接分解法的一半。

上機計算時，所需存貯單元也少，只要存貯A的下三角部分和右端項b，計算中L存放于A的存貯單元，y,x存放在b的存貯單元。平方根法的不足之處在于需作n次開方運算。27改進的Cholesky分解計算公式改進的Cholesky

分解28改進的Cholesky分解for

j=1tonendi=j+1,…,n算法：(改進的Cholesky分解)

優點：避免開方運算29改進的平方根法A

對稱正定計算改進的Cholesky分解解方程：Ly=b

和DLTx=yi=2,3,…,n算法：(解對稱正定線性方程組的改進的平方根法

)i=n-1,…,2,130例：

解方程組試用平方根法,改進的平方根法分別解之.>>A=[610;141;0114]；

>>b=[624322]'；>>L=chol(A)