5.4矩陣三角分解法

1、一、直接法概述,直接法是將原方程組化為一個(gè)或若干個(gè)三角形方程組的方法，共有若干種．,對(duì)于線性方程組,,,其中,系數(shù)矩陣,未知量向量,常數(shù)項(xiàng),根據(jù)Cramer(克萊姆)法則,若,,,若用初等變換法求解,則對(duì)其增廣矩陣作行初等變換:,,,,,,,,同解,,,即,以上求解線性方程組的方法稱為Gauss消去法,,,則,,,都是三角形方程組,上述方法稱為直接三角形分解法,§2 Matrix Factorization – Dooli

2、ttle,? 道立特分解法 /* Doolittle Factorization */： —— LU 分解的緊湊格式 /* compact form */,,,,反復(fù)計(jì)算,很浪費(fèi)哦 ……,§2 Matrix Factorization – Doolittle,固定 i :對(duì) j = i, i+1, …, n 有,lii = 1,,,,,a,固定 j ，對(duì) i = j, j+1, …, n 有,,,,,b,,

3、,,,,,,,,,,,,,,上述解線性方程組的方法稱為直接三角分解法的 Doolittle法,例1. 用Doolittle法解方程組,解:,由Doolittle分解,,,,,,,,,,,,,,,,Doolittle法在計(jì)算機(jī)上實(shí)現(xiàn)是比較容易的,但如果按上述流程運(yùn)算仍需要較大的存儲(chǔ)空間:,,,,,,,,因此可按下列方法存儲(chǔ)數(shù)據(jù):,,,,,直接三角分解的Doolittle法可以用以下過程表示:,存儲(chǔ)單元(位置),,,,,緊湊格式的Do

4、olittle法,,,例2. 用緊湊格式的Doolittle法解方程組(例1),解:,,,,,,,,,,,,,,,,,,,,所以,,,Matrix Factorization – Choleski,? 平方根法 /* Choleski’s Method */： ——對(duì)稱 /* symmetric */ 正定 /* positive definite */ 矩陣的分解法

5、,?回顧：對(duì)稱正定陣的幾個(gè)重要性質(zhì),? A?1 亦對(duì)稱正定，且 aii > 0,?,若不然，則,,?,,?,對(duì)任意 , 存在 , 使得 ,即 。,?,? A 的順序主子陣 /* leading principal submatrices */ Ak 亦對(duì) 稱正定,對(duì)稱性顯然。對(duì)任意 有

6、 , 其中 。,? A 的特征值 /* eigen value */ ?i > 0,設(shè)對(duì)應(yīng)特征值 ? 的非零特征向量為 ，則 。,? A 的全部順序主子式 det ( Ak ) > 0,因?yàn)?,,,,,,一、對(duì)稱正定矩陣的三角分解(Cholesky分解),記為,,,,Diagonal:對(duì)角,,,,,,,,,因此

7、,所以,,綜合以上分析,,則有,,,定理1. (Cholesky分解),且該分解式唯一,這種關(guān)于對(duì)稱正定矩陣的分解稱為Cholesky分解,,,,,,,,,,,,,,,,,,,二、對(duì)稱正定線性方程組的解法,線性方程組,則線性方程組(10)可化為兩個(gè)三角形方程組,,,,對(duì)稱正定方程組的平方根法,例1.,用平方根法解對(duì)稱正定方程組,解:,,,,即,,三、平方根法的數(shù)值穩(wěn)定性,用平方根法求解對(duì)稱正定方程組時(shí)不需選取主元,由,可知,因此,平方

8、根法是數(shù)值穩(wěn)定的,事實(shí)上,對(duì)稱正定方程組也可以用順序Gauss消去法求解,而不必加入選主元步驟,§2 Matrix Factorization – Tridiagonal System,? 追趕法解三對(duì)角方程組 /* Crout Reduction for Tridiagonal Linear System */,Step 1: 對(duì) A 作Crout 分解,直接比較等式兩邊的元素，可得到計(jì)算公式。,Step 2: