數(shù)值計(jì)算方法第3章

第3章線性方程組求解的數(shù)值方法1n階線性代數(shù)方程組的一般形式解線性代數(shù)方程組的數(shù)值解法有：①直接法，②迭代法。在沒有舍入誤差的情況下，經(jīng)過有限次運(yùn)算可以得到方程組的精確解的方法。線性代數(shù)方程組的直接解法/*DirectMethodforSolvingLinearAlgebraicSystems*/求解Cramer法則:所需乘除法的運(yùn)算量大約為(n+1)!+nn=20時(shí)，每秒1億次運(yùn)算速度的計(jì)算機(jī)要算30多萬年！直接法§3.1Gauss消去與矩陣LU分解一Gauss消去1直接法的關(guān)鍵思想如果方程組是“上三角方程組”或“下三角方程組”就可以很容易地求出方程組的解。因此，直接法的關(guān)鍵思想就是如何把一般方程組約化為上/下三角方程。屬于解方程的直接法2上三角方程組與回代過程3下三角方程組與前推過程4Gauss消去過程則Gauss消去過程如下：該Gauss消去法為順序高斯消去法forforforGauss法的消元過程回代過程順序高斯消去法必須保證第k步的akk≠0，因?yàn)樗谙ミ^程和回代過程中起關(guān)鍵作用，所以稱它為主元素。例：用基本Gauss消元法求解下列方程組解：增廣矩陣

基本Gauss消元法的工作量消元過程：回代過程：加減法的次數(shù)乘除法的次數(shù)基本Gauss消元法的實(shí)現(xiàn)條件全不為零的充要條件是的順序主子式都不等于零，即小主元可能導(dǎo)致計(jì)算失敗例：在8位制計(jì)算機(jī)上解方程組要求用Gauss消去法計(jì)算。8個(gè)解：主元素要作除數(shù)，其絕對值相對于被除數(shù)過小會(huì)影響到計(jì)算的精度，所以，我們可以采用5、列主元Gauss消去法解方程組除了“列主元消去法”，還有“全主元消去法”，但后者計(jì)算量過大，一般不用。思想每次消元之前，在剩余元素中選擇絕對值最大的非零元素作為主元，然后經(jīng)過換行換到主元位置

列主元消去法/*ColumnPivotingStrategies*/Stepk：第k步首先選擇主元尋求滿足然后交換矩陣的第行和行，再進(jìn)行消元過程

算法:

Gauss列主元消去算法求方程組Ax=b

的解.輸入:增廣矩陣An

(n+1)=（A|b）.輸出:

近似解xk=ak,n+1(k=1,2,…,n)

或失敗信息.消元過程fork=1,2,…,n-1doStep1-Step4

Step1

尋找行號ik

,使得Step2

如果，則交換第k行和ik行；

否則轉(zhuǎn)Step7

算法:

Gauss列主元消去算法（續(xù)）Step3fori=k+1,…,n

計(jì)算

Step4forj=k+1,…,n+1

計(jì)算

回代過程Step5Step6fori=n-1,…,1

計(jì)算

Step7Output(系數(shù)矩陣奇異);/*不成功*/STOP.

例：用Gauss列主元消去法求解下列方程組解：首先寫出增廣矩陣Step1消元Step2消元

全主元消去法/*CompletePivotingStrategies*/Stepk：第k步選擇主元尋求和滿足然后交換矩陣的第行和行，第列和列記錄交換信息二LU分解1矩陣的三角分解對方程組Ax=b的順序Gauss消去過程的結(jié)果，就是把矩陣A分解成兩個(gè)三角距陣L和U的乘積：A=LU。利用這個(gè)特點(diǎn)可以進(jìn)行線性方程組的直接三角分解法。解方程組的直接三角分解法有3種形式：（1）A=LU（2）A=L’U’（3）A=LDU單位下三角陣上三角陣下三角陣單位上三角陣單位下三角陣對角陣單位上三角陣A的Doolittle分解A的Crout分解A的LDU分解2解方程組的直接三角分解法Ax=bLUx=bDoolittle分解法本質(zhì)它是基本Gauss消元法的一種等價(jià)變形

Gauss消元法的矩陣形式

/*MatrixForm*/

為上三角矩陣其中

為單位下三角矩陣分解為單位下三角和上三角矩陣的乘積課堂練習(xí)答案§3.2Cholesky分解該方法也稱為平方根法。思想

Cholesky分解的計(jì)算公式設(shè)由對應(yīng)元素相等得Cholesky分解公式因?qū)ΨQ性無需存儲(chǔ)Step1Step2Step3Stepn的計(jì)算過程:逐列計(jì)算元素仍然存放在矩陣的相應(yīng)位置上例：用Cholesky分解法求解下列方程組解：系數(shù)矩陣為Step1Step2Step3求解方程組求解方程組

Cholesky分解法求解方程組中需說明的幾個(gè)問題

工作量：約為分解的一半；

不必選主元：的正定性和穩(wěn)定性

穩(wěn)定性：是數(shù)值穩(wěn)定的；

缺陷：存在開平方運(yùn)算。forforfor計(jì)算的k列計(jì)算

的k+1行矩陣分解的實(shí)際計(jì)算公式：§3.3向量范數(shù)與矩陣范數(shù)一向量范數(shù)1定義設(shè)向量x∈Rn，若與x對應(yīng)的一個(gè)實(shí)值函數(shù)（并記為）||x||滿足：||x||>0，其中||x||=0當(dāng)且僅當(dāng)x=0,稱為正定性；||kx||=|k|||x||,k∈R,稱為齊次性；||x+y||≤||x||+||y||,且x,y∈Rn,稱為三角不等式。例：設(shè)x=(2,-4,3)T,求||x||1,||x||2和||x||∞稱為矩陣ATA的譜半徑例：給定矩陣求矩陣的1、2、

范數(shù)。若是實(shí)對稱矩陣，則矩陣的特征值為。，求例：設(shè)21||||,||||,||||4321AAAA￥ú?ùê?é--=§3.4古典迭代法的構(gòu)造一、解線性方程組迭代法的基本思想求解迭代法從一個(gè)初始向量出發(fā),按照一定的遞推格式,產(chǎn)生逼近方程組的近似解序列。迭代法是一種逐次逼近的方法,與直接法比較,具有:

程序簡單,存儲(chǔ)量小的優(yōu)點(diǎn)。特別適用于求解系數(shù)矩陣為大型稀疏矩陣

/*sparsematrices*/

的方程組。思路將方程組等價(jià)改寫成形式，從而建立迭代格式

，從出發(fā)，生成迭代序列二、Jacobi迭代法2J法的迭代矩陣B稱為迭代矩陣，f稱為常數(shù)項(xiàng)二Gauss-Seidel迭代2、GS法迭代矩陣一般情況下，迭代公式用來計(jì)算x的值和求迭代矩陣，迭代矩陣用來分析迭代是否收斂。J法適用于并行計(jì)算，GS法適用于串行計(jì)算，并且所需要的存儲(chǔ)空間較小。例：利用Jacobi和Gauss-Seidel迭代法求解方程組解：Jacobi迭代格式G-S迭代格式計(jì)算結(jié)果取初值Jacobi迭代法要求精度迭代次數(shù)

0.001

9(1.00025071.00006941.0002507)

0.0001

10(0.99995411.00012530.9999541)0.00001

14(0.99999811.00000200.9999981)方程組的

近似解計(jì)算結(jié)果Gauss-Seidel迭代法要求精度迭代次數(shù)

0.001

5(0.99979160.99984791.0000664)

0.0001

7(0.99999290.99999491.0000022)0.00001

8(1.00000131.00000090.9999996)方程組的

近似解取初值§3.5迭代法的分析由該定理可知,只要迭代矩陣的譜半徑小于1,則J法和GS法收斂.定理：如果方程組的系數(shù)矩陣A是嚴(yán)格對角占優(yōu)的，則對任意初始近似值，J法和GS法均迭代。課堂練習(xí)§3.6線性方程組的條件對方程組的右端b作一個(gè)”微小”變化如果對系數(shù)矩陣作”微小”改變||A-1||||A