第二章數(shù)值代數(shù)

第二章數(shù)值代數(shù)

§2.1Gauss消去法§2.2直接三角分解法

§2.3范數(shù)和誤差分析

引言

快速、高效地求解線性方程組是數(shù)值線性代數(shù)研究中的核心問(wèn)題，也是目前科學(xué)計(jì)算中的重大研究課題之一。各種各樣的科學(xué)和工程問(wèn)題，往往最終都要?dú)w結(jié)為求解一個(gè)線性方程組。線性方程組的數(shù)值解法有：直接法和迭代法。直接法：在假定沒(méi)有舍入誤差的情況下，經(jīng)過(guò)有限次運(yùn)算可以求得方程組的精確解；迭代法：從一個(gè)初始向量出發(fā)，按照一定的迭代格式，構(gòu)造出一個(gè)趨向于真解的無(wú)窮序列。引例：Cramer法則不可行Cramer法則n>20時(shí)，計(jì)算量太大，現(xiàn)實(shí)上不可行.Cramer法則數(shù)學(xué)理論上很重要，但計(jì)算上無(wú)價(jià)值問(wèn)題：可以用x=A-1b來(lái)求解嗎？§2.1Gauss消去法（GaussEliminationMethod）

1理論基礎(chǔ)

2順序Gauss消去法

3選主元技術(shù)

（Pivoting）4追趕法

（Tridiagonalmatrixalgorithm）10德國(guó)馬克的紙幣1.理論基礎(chǔ)引理2.1同解2.順序高斯(Gauss)消去法順序高斯消去法的主要思路：將增廣陣[A|b]中的系數(shù)矩陣A化為上三角矩陣，然后回代求解。分為消元過(guò)程(elimination)和回代過(guò)程(backwardsubstitution)考慮n階線性方程組：矩陣形式=增廣陣形式舉例（一）解：消元過(guò)程：例：用順序高斯消去法求解回代過(guò)程:不要化簡(jiǎn)！消元過(guò)程(第1步)用矩陣初等行變換化系數(shù)矩陣為上三角形消元過(guò)程(第2步)消元過(guò)程(第k步)編程用計(jì)算公式消元過(guò)程(結(jié)果)上三角方程組回代回代過(guò)程計(jì)算量(乘除法次數(shù))消元

回代

總和計(jì)算量主要在消元比較Cramer法則，Gauss消去法快很多3.選列主元高斯消去法

順序高斯消去法有效的條件是：主元如果某個(gè)主元為0，則導(dǎo)致高斯消去法求解失敗。選列主元高斯消去法：在第k步消元時(shí)①先選取列主元（Pivoting）

：②ifik

k

then交換第k行和第ik行；列主元高斯消去法比順序高斯消去法要多一些比較運(yùn)算，但比順序高斯消去法穩(wěn)定。③消元全主元高斯消去法全主元高斯消去法：第k步消元時(shí)選A(k)中絕對(duì)值最大的元素為主元，即①先選取全主元：ifik

k

then交換第k行和第ik

行；

ifjk

k

then交換第k列和第jk

列；③消元列交換改變了

xi

的順序，須記錄交換次序，解完后再換回來(lái)。全主元高斯消去法具有很好的穩(wěn)定性，但選全主元比較費(fèi)時(shí)，故在實(shí)際計(jì)算中很少使用。例(選列主元素Gauss消去法)回代:舉例（二）解：

例：取8位有效數(shù)字，分別用Gauss消去法和列主元Gauss消去法求解線性方程組:精確解為，8個(gè)08個(gè)9順序Gauss消去法：9個(gè)0小主元可能導(dǎo)致計(jì)算失敗。舉例（二）續(xù)列主元Gauss消去法：例：但列主元高斯消去法有時(shí)也會(huì)導(dǎo)致求解失敗。4追趕法

（Tridiagonalmatrixalgorithm）三對(duì)角方程組

Gauss消去法應(yīng)用于三對(duì)角線性方程組得到所謂追趕法，其中消元過(guò)程為“追”，回代過(guò)程為“趕”。4追趕法增廣陣：4追趕法追

k=2,,n

趕

k=n-1,,1如果不令則有6n-5次乘除法計(jì)算量追趕法不對(duì)零元素計(jì)算，只有5n-4次乘除法計(jì)算量放假通知?jiǎng)趧?dòng)節(jié)：2013年4月29日至5月1日放假調(diào)休，共3天。4月27日(星期六)上第10周4月29日（星期一）的課程。4月28日(星期日)上第10周4月30日（星期二）的課程。

雙周的數(shù)值分析課被放假。端午節(jié)：2013年6月10日至12日放假調(diào)休，共3天。6月8日(星期六)上第16周6月10日（星期一）的課程。6月9日(星期日)上第16周6月12日（星期三）的課程。

§2.2直接三角分解法高斯消去法的矩陣表示LU分解法(LUDecomposition)平方根法(CholeskyDecomposition)改進(jìn)的平方根法矩陣三角分解

將一個(gè)矩陣分解成結(jié)構(gòu)簡(jiǎn)單的三角形矩陣的乘積稱為矩陣的三角分解。順序高斯消去法其實(shí)就是一個(gè)矩陣的三角分解過(guò)程。LU分解A=LU(Doolittle分解)用LU分解求解方程組先求解y再求解x則A(k)

與A(k+1)之間的關(guān)系式可以表示為：其中：(i=k+1,…,n),將Gauss消去過(guò)程中第k-1步消元后的系數(shù)矩陣記為：(k=1,…,n-1)LU分解記：，則其中：L---單位下三角矩陣，U---上三角矩陣LU分解于是有：容易驗(yàn)證：(k=1,…,n-1)(杜利脫爾Doolittle分解)LU

分解的存在唯一性LU分解存在順序高斯消去法不被中斷?定理

順序高斯消去法求解方程組Ax=b時(shí)，所有主元

的充要條件是：A的所有順序主子式不為零。定理若A的所有順序主子式不等于0，則A存在唯一的LU分解。(LU分解的唯一性

)證：存在性由上面的定理可得；唯一性可用反證法證明。類似分解定理若A的所有順序主子式不等于0,則(1)A存在唯一的LDR

分解：A=LDR，其中：L

是單位下三角矩陣，D

是對(duì)角矩陣，R

是單位上三角矩陣(2)A存在唯一的克洛脫(Crout)分解：

，其中：L

是下三角矩陣，U

是單位上三角矩陣LU分解緊湊方式直接利用矩陣乘法來(lái)計(jì)算LU分解(待定系數(shù)法)比較等式兩邊的第一行得：u1j=a1j比較等式兩邊的第一列得：比較等式兩邊的第二行得：比較等式兩邊的第二列得：(j=1,…,n)(i=2,…,n)(j=2,…,n)(i=3,…,n)U的第一行L的第一列U的第二行L的第二列LU分解計(jì)算順序

待定系數(shù)法LU分解緊湊算法（續(xù)）第k

步：此時(shí)U的前k-1行和L的前k-1列已經(jīng)求出比較等式兩邊的第k行得：比較等式兩邊的第k列得：直到第n

步，便可求出矩陣L和U的所有元素。(j=k,…,n

)(i=k+1,…,n

)LU分解緊湊算法（續(xù)）LU分解的算法：Fork=1,2,...,nEndForj=k,…,ni=k+1,…,n為了節(jié)省存儲(chǔ)空間，通常用A的絕對(duì)下三角部分來(lái)存放L(對(duì)角線元素?zé)o需存儲(chǔ))，用A的上三角部分來(lái)存放U。運(yùn)算量：(n3-n)/3Crout分解的緊湊算法Crout分解的算法：Fork=1,2,...,nEndFori=k,…,nj=k+1,…,n運(yùn)算量：(n3-n)/3平方根法(SPD的Cholesky分解)

A=LLT(Cholesky分解)(其中)解法：求A=LLT用待定系數(shù)法為什么對(duì)稱正定矩陣有這樣的分解呢？平方根法(SPD的Cholesky分解)

若A是對(duì)稱正定矩陣(SymmetricPositiveDefinite)AT=A

LDR分解唯一設(shè)D=diag(d1,,dn)A對(duì)稱正定：di>0，(i=1,…,n)

令SPD的Cholesky分解設(shè)Cholesky分解幾點(diǎn)說(shuō)明：(1)L

為對(duì)角線元素全為正的下三角矩陣；(2)只有對(duì)稱正定矩陣(SPD)才存在Cholesky分解；書(shū)上P24利用順序主子式先求對(duì)角元素好嗎？只適合于手算！實(shí)際上，數(shù)值計(jì)算行列式用LU分解。定理對(duì)稱正定矩陣的Cholesky分解存在，且滿足的解唯一。Cholesky分解實(shí)現(xiàn)算法直接利用矩陣乘法來(lái)計(jì)算分解(待定系數(shù)法)Fork=1,2,...,n算法5.3：(Cholesky

分解，按列)EndFori=k+1,…,n運(yùn)算量：n3/6

+n2/2+n/3

改進(jìn)的平方根法A=LDLT,據(jù)此可逐行計(jì)算

運(yùn)用這種矩陣分解方法,方程組Ax=b可歸結(jié)為求解兩個(gè)三角方程組即:和其計(jì)算公式分別為:

和上述算法稱為改進(jìn)的平方根法。這種方法總的計(jì)算量約為，即僅為高斯消去法計(jì)算量的一半。改進(jìn)在哪里？(1)避免了開(kāi)方運(yùn)算;(2)計(jì)算的可行性條件減弱為A對(duì)稱非奇異。有可能某個(gè)改進(jìn)的平方根法§2.3范數(shù)和誤差分析1范數(shù)和條件數(shù)

(NormandConditionNumber)2數(shù)據(jù)擾動(dòng)分析(PerturbationAnalysis)1范數(shù)和條件數(shù)引例

病態(tài)方程組：數(shù)據(jù)小擾動(dòng)解大誤差。注意：兩組解都是相應(yīng)方程組的精確解，沒(méi)有計(jì)算誤差二元病態(tài)方程組的幾何意義在二元情況下，“求兩條直線的交點(diǎn)”的問(wèn)題是否不穩(wěn)定，取決于這兩條直線是否接近于平行(系數(shù)矩陣A的行向量線性相關(guān))。良態(tài)方程組病態(tài)方程組向量范數(shù)

(VectorNorms)

定義：Rn上實(shí)值函數(shù)||.||,對(duì)于任意滿足正定性||x||0,且||x||=0x=0齊次性||x||=||||x||三角不等式

||x+y||||x||+||y||常用向量范數(shù)矩陣范數(shù)

(MatrixNorms)定義：Rn×n上實(shí)值函數(shù)||.||,對(duì)于任意滿足正定性||A||0,且||A||=0A=0齊次性||A||=||||A||三角不等式

||A+B||||A||+||B||相容性||AB||

||A||||B||與向量范數(shù)相容||Ax||

||A||||x||常用矩陣范數(shù)

相容性：

||Ax||v

||A||v

||x||v,v=1,2,||Ax||2

||A||F

||x||2范數(shù)的等價(jià)性

|