數值分析(研究生)第四章線性方程組的直接解法一

第四章線性方程組的直接解法（一）第一節(jié)實際問題的導入第三節(jié)矩陣的三角分解法第二節(jié)高斯消去法第四節(jié)解三對角方程組的追趕法求解§1實際問題的導入

Cramer法則：計算量太大.線性方程組的系數矩陣可分為：

低階稠密矩陣——階數不超過500，零元素很少；

大型稀疏矩陣——階數高且零元素多.解線性方程組的方法：

直接法——系數矩陣是低階稠密矩陣的線性方程組及某些大型稀疏矩陣的線性方程組；

迭代法——系數矩陣是大型稀疏矩陣的線性方程組.§2高斯消去法一、高斯消去法思路首先將A化為上三角陣，再回代求解.=消元記Step1：設，計算因子將增廣矩陣第i行mi1

第1行，得到其中Stepk：設，計算因子且計算共進行？步n

1回代定理若A的所有順序主子式均不為0，則高斯消元無需換行即可進行到底，得到唯一解.注：事實上，只要A

非奇異，即A1

存在，則可通過逐次消元及行交換，將方程組化為三角形方程組，求出唯一解.二、選主元消去法例1單精度解方程組/*精確解為和*/8個8個用高斯消元法計算：8個小主元可能導致計算失敗.

全主元消去法每一步選絕對值最大的元素為主元素，保證.Stepk:①選?、贗fik

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

列;③消元.注：列交換改變了xi

的順序，須記錄交換次序，解完后再換回來.列主元消去法省去換列的步驟，每次僅選一列中最大的元.例2注：列主元法沒有全主元法穩(wěn)定.例3注意：這兩個方程組在數學上嚴格等價.標度化列主元消去法對每一行計算。為省時間，si

只在初始時計算一次.以后每一步考慮子列中最大的aik

為主元.注：穩(wěn)定性介于列主元法和全主元法之間.實際應用中直接調用高斯消元法解3階線性方程組的結果：結合全主元消去后的結果：高斯-若當消去法與高斯消元法的主要區(qū)別：

每步不計算mik

，而是先將當前主元akk(k)

變?yōu)?;把akk(k)

所在列的上、下元素全消為0;運算量由于計算機中乘除運算的時間遠遠超過加減運算的時間，故估計某種算法的運算量時，往往只估計乘除的次數，而且通常以乘除次數的最高次冪為運算量的數量級.高斯消元法:Stepk：設，計算因子且計算共進行n

1步(nk)次(nk)2

次(nk)次(nk)(nk+2)

次消元乘除次數：1次(ni+1)次回代乘除次數：高斯消元法的總乘除次數為，運算量為級.全主元消去法:比高斯消元法多出，保證穩(wěn)定，但費時.列主元消去法:比高斯消元法只多出，略省時，但不保證穩(wěn)定.標度化列主元消去法:比高斯消元法多出除法和，比列主元法穩(wěn)定.但若逐次計算si(k)，則比全主元法還慢.高斯-若當消去法:運算量約為.故通常只用于求逆矩陣，而不用于解方程組.求逆矩陣即.§3

矩陣的三角分解法高斯消元法的矩陣形式：Step1:記L1=，則Stepn

1:其中

Lk=一、矩陣的LU分解記為L單位下三角陣記

U=定理若A的所有順序主子式均不為0，則A

的

LU

分解唯一（其中L

為單位下三角陣）.證明：由§1中定理可知，LU分解存在.下面證明唯一.若不唯一，則可設A=L1U1=L2U2

，推出一般上三角陣單位下三角陣注：L

為一般下三角陣而U

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

實際上只要考慮A*的LU

分解，即

，則即是A的Crout分解.道立特分解法：

——LU

分解的緊湊格式反復計算,很浪費哦……通過比較法直接導出L和

U的計算公式.思路固定i:對j=i,i+1,…,n

有l(wèi)ii=1a將i

，j對換，對j=i,i+1,…,n有b

算法:道立特分解法Step1:u1j=a1j;lj1=aj1/u11;(j=1,…,n)Step2:計算和，從i=2,…,n1;Step3:ab一般采用列主元法增強穩(wěn)定性.但注意也必須做相應的行交換.對稱

正定矩陣的分解法定義一個矩陣A=(aij)nn

稱為對稱陣，如果aij=aji.定義一個矩陣A

稱為正定陣，如果對任意非零向量都成立.回顧：對稱正定陣的幾個重要性質

A1

亦對稱正定，且aii>0若不然，則存在非零解，即存在非零解。對任意,存在,使得,即.其中第i

位

A

的順序主子陣Ak

亦對稱正定對稱性顯然。對任意有

,其中.

A

的特征值i

>0

設對應特征值的非零特征向量為，則.

A

的全部順序主子式

det(Ak

)>0因為二、平方根法將對稱

正定陣

A

做LU

分解U=uij=u11uij/uii111u22unn記為

A對稱即記D1/2=則仍是下三角陣定理設矩陣A對稱正定，則存在非奇異下三角陣使得.若限定L對角元為正，則分解唯一.注：對于對稱正定陣A，從可知對任意ki

有.即L

的元素不會增大，誤差可控，不需選主元.P126Step1:對A作Crout分解直接比較等式兩邊的元素，可得到計算公式（p130）.Step2:追——即解：Step3:趕——即解：與G.E.類似，一旦i=0

則算法中斷，故并非任何三對角陣都可以用此方法分解.§4

解三對角方程組的追趕法定理若A

為對角占優(yōu)的三對角