線性方程組的直接方法迭代法市公開課獲獎?wù)n件

1、第六章 解線性方程組的直接方法1 引言第1頁第1頁第2頁第2頁第3頁第3頁2 Gauss消去法一 Gauss消去法第4頁第4頁第5頁第5頁第6頁第6頁第7頁第7頁第8頁第8頁第9頁第9頁第10頁第10頁第11頁第11頁第12頁第12頁第13頁第13頁二 矩陣的三角分解第14頁第14頁第15頁第15頁第16頁第16頁第17頁第17頁第18頁第18頁第19頁第19頁三 Guass消去法的計算量第20頁第20頁第21頁第21頁用Gauss消去法解AX=b時，設(shè)A非奇異，但也許出現(xiàn) 這時必須進(jìn)行行互換Gauss消去法，但在實際計算中即使 但其絕對值很小時，用 作除數(shù)，會造成中間結(jié)果矩陣 元素數(shù)量級嚴(yán)重

2、增長和舍入誤差擴散，使最后結(jié)果不可靠。例：設(shè)有方程組 辦法一：用Gauss消去法求解。（用含有舍入3位浮點數(shù)進(jìn)行運算）解：方程組解3 Gauss主元素消去法第22頁第22頁辦法二：用含有行互換Gauss消去法（避免小主元） 這個解對于含有舍入3位浮點數(shù)進(jìn)行計算，是一個較好結(jié)果。回代得解 =1.00 =0.00 ，與準(zhǔn)確解比較，這結(jié)果很差。 這個例子告訴我們，在采用高斯消去法解方程組時，小主元也許造成計算失敗，故在消去法中應(yīng)避免采用絕對值很小主元素。 辦法1計算失敗原因，是用了一個絕對值很小數(shù)作除數(shù)，乘數(shù)很大，引起約化中間結(jié)果數(shù)量誤差很嚴(yán)重增長，再舍入就使得計算結(jié)果不可靠了。第23頁第23頁 這

3、個例子還告訴我們，對同一個數(shù)值問題，用不同計算方法，得到精度大不同，一個計算方法，假如用此方法計算過程中舍入誤差得到控制，對計算結(jié)果影響較小，稱此方法為數(shù)值穩(wěn)定；不然，假如用此計算方法計算過程中舍入誤差增加快速，計算結(jié)果受舍入誤差影響較大，稱此方法為數(shù)值不穩(wěn)定。因此，我們解數(shù)值問題時，應(yīng)選擇和使用數(shù)值穩(wěn)定計算方法，不然，假如使用數(shù)值不穩(wěn)定計算方法去解數(shù)值計算問題，就可能造成計算失敗。對普通矩陣方程組，需要引進(jìn)主元技巧，即在高斯消去法每一步應(yīng)當(dāng)選取系數(shù)矩陣或消元后低階矩陣中絕對值最大元素作為主元素，保持乘數(shù) ，以便減少計算過程中舍入誤差對計算解影響。第24頁第24頁一 完全主元素消去法第25頁第

4、25頁第26頁第26頁（1）選主元素：選取 使于是第k步計算：對于k=1，2，.n-1做到（3）第k步選主元區(qū)域第27頁第27頁（4）回代求解。 通過上面過程，即從第1步到第n-1步完畢選主元，交 換兩行，交 換兩列，消元計算，原方程組約化為 ：第28頁第28頁二 列主元素消去法(1)第29頁第29頁 完全主元素消去法是解低階稠密矩陣方程組有效辦法，但完全主元素辦法在選主元時要花費一定期間。現(xiàn)簡介一個在實際計算中慣用部分選主元，（即列主元）消去法。列主元消去法，即是每次選主元時，僅依次按列選取絕對值最大元素作為主元素，且僅互換兩行，再進(jìn)行消元計算。第k步選主元區(qū)域 設(shè)列主元消去法已經(jīng)完畢第1步

5、到第k-1步按列選主元，互換兩行，消元計算得到與原方程組等價方程組： ，其中第30頁第30頁 第k步計算下列： 對于k=1，2.，n-1做到（4）（1）按列選主元，即擬定 使 （3）假如 ，則互換 第 行第k行元素（2）假如 =0，則A為奇異矩陣，停止計算。（4）消元計算：*第31頁第31頁解：準(zhǔn)確解為（舍入值）：例：用列主元消去法去解方程組計算解 在常數(shù)項內(nèi) 得到（5）回代計算：第32頁第32頁 本例是含有舍入4位浮點數(shù)進(jìn)行運算，所得計算解還是比較準(zhǔn)確。 下面是完全主元素消去法框圖（圖6-1）第33頁第33頁圖（6-1）stop輸入n,A,b,cI(Z) I(I=1,2,.n)k=1,2.n

6、是輸出detA=0否互換行是否轉(zhuǎn)下頁 第34頁第34頁消元計算 互換列且接上頁否 Stop 第35頁第35頁第36頁第36頁*第二步，選4.12為列主元，不需換行，*由*回代求解得：解：第一步，選5.00為主列元，將 對凋位置，第37頁第37頁 與原方程組準(zhǔn)確解 比較，可知，本題用3位有效數(shù)字計算列元素法是相稱準(zhǔn)確。 大量實踐表明：列主元法為解線性方程組準(zhǔn)確辦法。 完全主元素消去法在選主元素時要花費多機器時間。下面簡介另一個慣用辦法即列主元素消去法，它僅考慮依次按列選主元素，然后換行使之變到主元素位置上，再進(jìn)行消元計算。設(shè)用列主元素消去法解Ax=b已完畢k-1步計算。即有：二 列主元素消去法(

7、2)第38頁第38頁第39頁第39頁列主元素消去法環(huán)節(jié)：設(shè)Ax=b。對于含有行互換列主元素消去法，消元結(jié)果沖掉A，乘數(shù)mij沖掉aij，計算解X沖掉常數(shù)項b,行列式存在det. 1, 1det, k=1 （對k=1n-1 做27步。） 3， 若aik,k=0, 則 0det. 計算終止。 5， 計算乘數(shù)mik, mik= aik/ akkaik.(i=k+1n) (| mik|1)第40頁第40頁6, 消元計算： aij - mik aij aij (i,j=k+1,n) bi - mik bk bi (i=k+1,n)下面用矩陣運算來描述列主元素法。記 是初等排列陣（由互換單位矩陣I第k行與

8、ik行所得）。則列主元素法為：第41頁第41頁其中Lk元素滿足 |mik|1（k=1,2,n-1）,由得：第42頁第42頁則由排列陣性質(zhì)（左乘矩陣是對矩陣進(jìn)行行變換。） 這表明：對Ax=b 應(yīng)用列主元素法相稱于對（A|b）先進(jìn)行一系列行互換后對PAX=Pb再應(yīng)用Gauss消去法。在實際計算中我們只能在計算過程中做行變換。有結(jié)論：定理：（列主元素三角分解定理） 若A為非奇異性矩陣，則存在排列矩陣P使 PA=LU。其中L為單位下三角陣，U為上三角陣。 L存儲在A下三角部分， U存儲在A上三角部分。由整數(shù)型數(shù)組IP（n）統(tǒng)計可知P情況。（例子見前）第43頁第43頁 Gauss消去法總是消去對角線下方

9、元素?，F(xiàn)考慮一個修正，即消去對角線下方和上方元素。這即為Gauss-Jordan（G-J）消去法。三 Gauss-Jordan消去法第44頁第44頁 在第k步計算時，考慮對上述矩陣第k行上、下都進(jìn)行消元計算（k=1,2n）2，換行（當(dāng)ikk）。互換A,b第k行與第ik行元素。3，計算乘數(shù) mik = -aik/akk (i=1n,i k), mkk =1/ akk (mik可存儲在aik單元中) （| mik |1） 第45頁第45頁上述過程所有執(zhí)行完后有： 這表明用GJ辦法將A約化為單位矩陣，計算解就在常數(shù)項位置得到，因此用不著回代求解。用GJ辦法接方程組計算量大約需要 次乘除法，要比Gau

10、ss消去法大些。但用GJ辦法求一個矩陣逆矩陣還是比較適當(dāng)。第46頁第46頁定理第47頁第47頁例解：第48頁第48頁第49頁第49頁故第50頁第50頁4 Gauss消去法的變形一 直接三角分解法（A) 不選主元的三角分解法第51頁第51頁第52頁第52頁第53頁第53頁第54頁第54頁（B) 選主元的三角分解法第55頁第55頁第56頁第56頁第57頁第57頁二 平方根法第58頁第58頁第59頁第59頁第60頁第60頁第61頁第61頁第62頁第62頁第63頁第63頁第64頁第64頁第65頁第65頁例解:第66頁第66頁在一些實際問題中常有解三對角線性方程組Ax=f問題，即：三 追趕法第67頁第6

11、7頁 對于含有條件（2）方程組（1），我們簡介下面追趕法求解。追趕法含有計算量少，辦法簡樸，算法穩(wěn)定特點。定理：設(shè)有三對角線性方程組Ax=f，且A滿足條件（2），則A為非奇異矩陣。證實：用歸納法證實。顯然n=2時，有：第68頁第68頁 現(xiàn)假設(shè)定理對n-1階滿足條件（2）三對角矩陣成立，求證對滿足條件（2）n階三對角矩陣定理亦成立。由條件 ，則利用消元法第1步有：第69頁第69頁證實：由于A是滿足條件（2）n階三對角陣。因此A任一個順序主子式 亦滿足條件（2）n階三對角矩陣。由上一個定理第70頁第70頁依據(jù)這一結(jié)論以及三角分解定理知，這種矩陣A可進(jìn)行三角分解：A=LU。在這里尤其有：第71頁第7

12、1頁第72頁第72頁上面已經(jīng)驗證(5)對i=1成立?，F(xiàn)設(shè)(5)對i-1成立。求證(5)對i成立。由假設(shè)，再由(4)及假設(shè)條件(2)有:由(4)可知: 可見由A假設(shè)條件,我們完全求出了 實現(xiàn)了對ALU分解。從而求解Ax=f 等價于求解兩個三角方程組:第73頁第73頁由此可得求解三對角線性方程組追趕法:1.計算 遞推公式:2.求解 Ly=f 公式:3.求解 Ux=y 公式:第74頁第74頁 我們將計算 及 過程稱為追過程。計算方程組解 過程稱為趕過程。追趕法求解 Ax=f 僅需5n-4次乘除運算。工作量較小。 在計算機上，只需用3個一維數(shù)組分別存儲A系數(shù) 以及兩個一維數(shù)組保留計算中間結(jié)果 和 或

13、.例:用追趕法求解:解：（1）計算 ：第75頁第75頁（2）計算 ：對于追趕法，由于已證實:（3）計算 ： 因此追趕法中不會出現(xiàn)中間結(jié)果快速增長和全入誤差產(chǎn)生積累現(xiàn)象。第76頁第76頁需要對 （n維 列向量空間）中向量及 中矩陣引進(jìn)某種度量，即引進(jìn)向量或矩陣范數(shù)概念。范數(shù)是長度概念推廣 為了對方程組計算解進(jìn)行誤差分析，為了討論迭代法收斂性，5 向量和矩陣范數(shù) 一 向量范數(shù) 定義1：（向量范數(shù)） 第77頁第77頁 |x+y| |y| |x|第78頁第78頁 易證實：它們均滿足向量范數(shù)定義1。且前三種向量范數(shù)均為第四種向量范數(shù)特例第79頁第79頁二 矩陣范數(shù)第80頁第80頁 這就是矩陣Froben

14、ius范數(shù), 明顯它滿足上面定義。 在大多數(shù)與估算相關(guān)問題中，矩陣和向量會同時參與討論，因此希望引進(jìn)一個矩陣范數(shù)。它和向量范數(shù)相聯(lián)系且和向量范數(shù)是相容，即：第81頁第81頁在計算上，（1），（2）比較容易，而（3）比較困難，但（3）在理論分析上十分有用。第82頁第82頁第83頁第83頁第84頁第84頁 由于A(或b)元素是測量得到，或者是計算結(jié)果，在第一個情況A（或b）常帶一些測量誤差。在后一個情況A(或b)又有舍入誤差。 因此我們處理實際矩是 A+A(或b+b)。 Ax=b. A為非奇異陣。設(shè)x為方程組準(zhǔn)確解。 下面考察方程組數(shù)據(jù)A(或b)微小誤差對解影響。即預(yù)計 x-y。 其中 y 為（A

15、+A）y=b 解。例：設(shè)有方程組下列， 其準(zhǔn)確解為 一 矩陣的條件數(shù)6 誤差分析第85頁第85頁 可見 方程組常數(shù)項分量只有微小改變（1%），而方程組解卻有較大改變。即方程組解對常數(shù)項b很靈敏。這樣方程組稱為病態(tài)方程組。定義: 假如矩陣A或常數(shù)項b微小改變引起方程組Ax=b解巨大改變。則稱此方程組為“病態(tài)”方程組，矩陣A稱為“病態(tài)”矩陣。不然稱此方程組為“良態(tài)”方程組，矩陣A稱為“良態(tài)”矩陣。 現(xiàn)考慮常數(shù)項有微小誤差 即 bb+b= 其中b= .得到一個擾動方程組：. 矩陣“病態(tài)”性質(zhì)是矩陣本身特性。下面我們希望找出刻劃矩陣“病態(tài)”性質(zhì)量。第86頁第86頁先考察常數(shù)項b微小誤差對解影響。設(shè)A是

16、準(zhǔn)確，且為非奇異矩陣，b有誤差（或擾動）b。x為Ax=b 準(zhǔn)確解。 方程組 解與 x 差記為： 從而 |x| | | *|b| 即 又 Ax=b0 則 |b|A| * |x| 即： A(x+x) =b+ x ， 即： A(x)=b.（假設(shè)Ax=b0)第87頁第87頁 式闡明：當(dāng)b有一定相對誤差時，引起解Ax=b解改變相對誤差上界由給出。解相對誤差是常數(shù)項相對誤差 倍。由得下面結(jié)論:定理 (b擾動對解影響)設(shè)： 1） 設(shè)Ax=b0 ，x 為準(zhǔn)確解，detA 0 ； 2）且設(shè) A(x+x)=b+b 則有:再考察矩陣 A 擾動對 Ax=b 解 x 影響設(shè)A有微小擾動A，即AA+A，b是準(zhǔn)確。記（A+

17、A) (x+x)=b第88頁第88頁 A+A=A(I+ )為非奇異性矩陣 且:設(shè) ， 則由上一節(jié)最后定理可知:定理：(A擾動對解影響) 設(shè)Ax=b, A非奇異矩陣, x 為準(zhǔn)確解，且（A+A)(x+x)=b.以及|A| ,則由A微小擾動引起解相對誤差滿足預(yù)計式。由 x=-(A+A)-1 (A) x ， 則由 得：由Ax=b0 有： （A+A)x=(A)x 第89頁第89頁 、均闡明：b或A微小擾動對解相對誤差與 相關(guān)，因而 數(shù)大小刻劃了方程組解對數(shù)據(jù)A(或b)靈敏程度。定義：設(shè)A為非奇異矩陣，稱數(shù)為矩陣A條件數(shù)，（=1，2或）。 可見矩陣條件數(shù)與范數(shù)相關(guān)。A條件數(shù)越大，方程組病態(tài)就越嚴(yán)重。也就

18、越難得到方程組比較準(zhǔn)確解。慣用條件數(shù)有：2） A譜條件當(dāng)A為對稱矩陣時， 其中1、n為 A 絕對值最大和最小特性值。第90頁第90頁 條件數(shù)性質(zhì):對任何非奇異陣A，有： Cond(A)v1 由于:設(shè)A為非奇異陣 且c0（常數(shù)）,則 Cond(cA)v =Cond(A)v若A為正交矩陣，則Cond(A)2=1 ， 若A為非奇異陣，R為正交矩陣，則Cond(RA)2= Cond(AR)2= Cond(A)2第91頁第91頁例：已知Hilbert矩陣：計算H3條件數(shù)。解：下面計算H3條件數(shù)同樣可計算 ，普通Hn矩陣當(dāng)n越大時，病態(tài)越嚴(yán)重。則：第92頁第92頁再考察方程組設(shè)H3與b有微小誤差（取3位有

19、效數(shù)字）有：第93頁第93頁 若在A三角約化時（尤其是用元素消去法解Ax=b時）出現(xiàn)小元，對大多數(shù)矩陣來說，A是病態(tài)矩陣。 比如用選主元素直接三角分解法求解方程組(*)(用雙精度累加計算aibi,結(jié)果舍入為3位浮點數(shù))。則： 這表明H3與b相對誤差不超出0.2%，而引起解相對誤差超出50%。要判斷一個矩陣是否病態(tài)，需計算矩陣條件數(shù)： ，而計算 是比較費力。那么在實際中如何發(fā)覺病態(tài)情況呢？下面分幾種情況考慮： 第94頁第94頁 若A最大特性值和最小特性值之比(按照絕對值)較大，則 A 是病態(tài)。A特性值：|1|2| |n |0 即使：|1|A|，1/|n| | 因而 。 系數(shù)矩陣行列式值相對很小，

20、或系數(shù)矩陣一些行近似線性相關(guān)，這時A也許為病態(tài)。 系數(shù)矩陣A元素間數(shù)量級相差很大，而且無一定規(guī)則，A可能病態(tài)。 對于病態(tài)方程組，用選主元素法求解難找到準(zhǔn)確解。能夠考慮迭代改進(jìn)法。對Ax=b， detA0 ，若方程組不過度病態(tài)。設(shè)用Gauss消去法(或部分選主元素法)求得計算解 x1 (精度不變)，我們希望取得方程組高精度解?？刹扇∠率龅倪M(jìn)法來改進(jìn)解x1精度。第95頁第95頁若計算 r1 及 d1 均無誤差。則 x2 為方程組 Ax=b 準(zhǔn)確解。(Ax2=A(x1+d1)=Ax1+Ad1=Ax1+r1=b) 但在實際計算中由于有舍入誤差，因此x2仍為一個近似解（要求用雙精度計算r），對 x2

21、 再重復(fù)上述過程（1）（3），就求得 r2, d2, x3。 如此可得一個近似解序列xn。當(dāng) Ax=b 不是過度病態(tài)時，通常xn能夠不久收斂列方程組解 。例：用迭代法解 第96頁第96頁因此方程組為病態(tài)。 則（1）用Gauss消元法Ax=b (用含有舍入4位浮點數(shù)進(jìn)行計算）第97頁第97頁用Gauss消去法或列主之法求計算解 ，且實現(xiàn)分解（求解兩個三角形方程組）；第98頁第98頁 另外也可采用高精度算術(shù)運算技術(shù)或者預(yù)處理辦法來處理病態(tài)問題，即將 Ax=b 化為一個等價方程組: 即選擇非奇異陣 P, Q使 Cond(PAQ)Cond(A)，普通選擇P，Q為對角陣或三角陣。當(dāng)A 元素改變較大時，對A行（或列）引進(jìn)適當(dāng)百分比因子（使矩陣A所有行或例按 范數(shù)大體上有相同長度，使A系數(shù)均衡）