線性方程組的解法上

1在自然科學(xué)和工程技術(shù)中很多問(wèn)題的解決常常歸結(jié)為解線性方程組。這些方程組的系數(shù)矩陣大致分為兩種：(1)低階稠密矩陣〔通常階數(shù)≤150〕(2)大型稀疏矩陣〔即矩陣階數(shù)高且零元素較多〕3.1引例及問(wèn)題綜述3.1.1引例P161引例1:電路問(wèn)題〔電網(wǎng)絡(luò))3.1.2問(wèn)題綜述線性方程組1.2克萊姆〔Cramer〕法那么：如果，那么方程組有唯一解2.用這種方法解一個(gè)n元方程組,要算n+1個(gè)n階行列式的值，總共需要(n+1)n!(n-1)次乘法。當(dāng)n較大時(shí)，計(jì)算量相當(dāng)驚人。如：n=20時(shí)，(n+1)n!(n-1)≈9.7*1020工作量太大，不適用在計(jì)算機(jī)上求解高維方程組。3.4直接法就是經(jīng)過(guò)有限步算術(shù)運(yùn)算，可求得方程組精確解的方法〔假設(shè)計(jì)算過(guò)程中沒(méi)有舍入誤差〕。但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解。這類(lèi)算法中最根本的高斯消去法及其某些變形。這類(lèi)方法是解低階稠密矩陣方程組的有效方法，近十幾年來(lái)直接法在求解某些大型稀疏矩陣方程組方面取得了較大進(jìn)展。線性方程組的數(shù)值解法一般分為直接法和迭代法兩類(lèi)。4.5

迭代法根本思想與解一元非線性方程的迭代法類(lèi)似。從任意給定的初始近似解向量出發(fā)，按照某種方法逐步生成近似解序列，使解序列的極限為方程組的解。迭代法就是用某種極限過(guò)程去逐步逼近線性方程組精確解的方法，可以用有限步運(yùn)算算出具有指定精確度的近似解。迭代法主要有：雅可比〔Jacobi)迭代法；高斯-賽德?tīng)枴睪auss-Seidel)迭代法。迭代法具有需要計(jì)算機(jī)的存貯單元較少、程序設(shè)計(jì)簡(jiǎn)單、原始系數(shù)矩陣在計(jì)算過(guò)程中始終不變等優(yōu)點(diǎn)，但存在收斂性及收斂速度問(wèn)題。迭代法是解大型稀疏矩陣方程組〔尤其是由微分方程離散后得到的大型方程組〕的重要方法。5.63.2線性方程組的直接解法有3種方程的解可以直接求出：①n次運(yùn)算②(n＋1)n/2次乘除運(yùn)算對(duì)角矩陣下三角矩陣回代過(guò)程6.③(n＋1)n/2次乘除運(yùn)算消元法就是對(duì)方程組做些等價(jià)的變換，變?yōu)槲覀兊?種類(lèi)型之一，而后求根上三角矩陣回代過(guò)程7.8對(duì)方程組，作如下的變換，解不變①交換兩個(gè)方程的次序②一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0的數(shù)③一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0數(shù)，加到另一個(gè)方程對(duì)應(yīng)的對(duì)增廣矩陣(A,b)，作如下的變換，解不變①交換矩陣的兩行②某一行乘以一個(gè)非0的數(shù)③某一個(gè)乘以一個(gè)非0數(shù)，加到另一行〔同解變換〕〔矩陣的初等行變換〕8.93.2.1高斯消去法的根本思想高斯消去法是一個(gè)古老的求解線性方程組的方法，但由它改進(jìn)、變形得到的選主元素消去法、三角分解法仍然是目前計(jì)算機(jī)上常用的有效方法。思路首先將A化為上三角陣，再回代求解。=9.10例1

用高斯消去法解方程組解第1步：將方程〔1〕乘上〔-3/2〕加到方程〔2〕上去，將方程〔1〕乘上〔-1/2〕加到方程〔3〕上去，那么得到與原方程組等價(jià)的方程組3.2.1高斯消去法的基本思想（續(xù)）P163〔消元x1〕10.11其中方程（4），（5）已消去了未知數(shù)x1。

第2步：將方程〔4〕乘上2加到方程〔5〕，消去〔5〕式中未知數(shù)x2，得到與原方程組等價(jià)的三角形方程組3.2.1高斯消去法的基本思想（續(xù)）〔消元x2〕11.123.2.1高斯消去法的基本思想（續(xù)）最后由上述方程組，用回代的方法，即可求得原方程組的解。

x3=0，x2=1，x1=-1/2這種求解過(guò)程，稱(chēng)為具有回代的高斯消去法。12.13用高斯消去法解方程組的根本思想是用矩陣行的初等變換將系數(shù)矩陣A約化為具有簡(jiǎn)單形式的矩陣〔如：上三角陣〕，而三角形方程組是很容易解的——〔回代〕3.2.1高斯消去法的基本思想（續(xù)）增廣矩陣13.14通常把這種按照先消元，再回代兩個(gè)步驟求解線性方程組的方法稱(chēng)為高斯〔Gauss)消去法。3.2.2高斯消去法的算法構(gòu)造設(shè)有n個(gè)未知數(shù)的線性方程組

(3.1)14.15引進(jìn)記號(hào)

(3.1)可用矩陣形式表示

(3.2)為了討論方便，記，假設(shè)A為非奇異矩陣（即設(shè)det(A)≠0）。

3.2.2高斯消去法的算法構(gòu)造（續(xù)）滿(mǎn)秩矩陣，有唯一解15.16第1步〔k=1〕：設(shè)計(jì)算乘數(shù)：用mi1乘上第一個(gè)方程，加到第i〔i=2，…，n〕個(gè)方程上去〔即施行行的初等變換Ri←Ri+mi1*R1，i=2，…，n〕，消去第2個(gè)方程～第n個(gè)方程的未知數(shù)x1，得到等價(jià)方程組

3.2.2高斯消去法的算法構(gòu)造（續(xù)）(1)消元過(guò)程16.17記為:A(2)x=b(2)

；其中3.2.2高斯消去法的算法構(gòu)造（續(xù)）17.183.2.2高斯消去法的算法構(gòu)造（續(xù)）第2步〔k=2〕：對(duì)線性方程組(3.3)中的第2，3，…，n個(gè)方程組成的n-1元方程組做類(lèi)似于第1步的處理，消去除第一個(gè)方程之外的變?cè)獂2，得到第2步消元后的線性方程組18.19式中19.20第k步：〔k=1，2，…，n-1〕繼續(xù)上述消去過(guò)程，設(shè)第1步～第k-1步計(jì)算已經(jīng)完成，得到與原方程組等價(jià)的方程組記為A(k)x=b(k)；現(xiàn)進(jìn)行第k步消元計(jì)算，設(shè)，計(jì)算乘數(shù)用〔mik〕乘上式的第k個(gè)方程加到第i個(gè)方程，消去第i個(gè)方程的未知數(shù)xk，得到與原方程組等價(jià)的方程組3.2.2高斯消去法的算法構(gòu)造（續(xù)）第i行第k行〔i=k+1，…，n〕20.21簡(jiǎn)記為A(k＋1)x=b(k＋1)；其中A(k＋1)，b(k＋1)元素計(jì)算公式為：3.2.2高斯消去法的算法構(gòu)造（續(xù)）21.22最后，重復(fù)上述約化過(guò)程，即k=1，2，…，n-1且設(shè)（k=1，2，…，n-1）共完成n-1步消元計(jì)算，得到與原方程組（3.1）等價(jià)的三角形方程組

3.2.2高斯消去法的算法構(gòu)造（續(xù)）消元過(guò)程22.233.2.2高斯消去法的算法構(gòu)造（續(xù)）第1步在方程〔3.4〕的最后一個(gè)方程中解出xn，得〔2〕回代過(guò)程23.243.2.2高斯消去法的算法構(gòu)造（續(xù)）第3步依次繼續(xù)下去，一般可得xk的計(jì)算公式第2步將xn的值代入式〔3.4〕的倒數(shù)第二個(gè)方程，解出xn-1，得當(dāng)k=1時(shí)，就完成了回代過(guò)程，得到所求的解。(k=n-1,n-2,…,1)24.25將〔3.1)約化為(3.4)的過(guò)程稱(chēng)為消元過(guò)程，〔3.4〕的求解過(guò)程稱(chēng)為回代過(guò)程由消元過(guò)程和回代過(guò)程求解線性方程組的方法稱(chēng)為高斯消去法。3.2.2高斯消去法的算法構(gòu)造（續(xù)）25.26①消元計(jì)算k=1，2，…，n-13.2.2高斯消去法的算法構(gòu)造（續(xù)）定理3.1設(shè)線性方程組Ax=b，其中A∈Rn×n(Rn×n表示n階方陣的集合〕。（1）如果則可通過(guò)高斯消去法將Ax=b化為等價(jià)的上三角方程組，且有計(jì)算公式：26.27②回代計(jì)算

(2)如果A為非奇異矩陣時(shí)，可能有某，則在第k列存在有元素，于是可能通過(guò)交換（A，b）的第k行和第ik行元素，將調(diào)到（k，k）位置，然后再進(jìn)行消元計(jì)算。于是，在A為非奇異矩陣時(shí)，只要引進(jìn)行交換，則高斯消去法可將化為上三角方程組，且通過(guò)回代即可求得方程組解。

3.2.2高斯消去法的算法構(gòu)造（續(xù)）27.28高斯消去法要求第k步消元的主元素3.2.2高斯消去法的算法構(gòu)造（續(xù)）判斷主元素

的一個(gè)充要條件：定理3.2對(duì)矩陣A=(aij)n×n消元時(shí)，主元素的一個(gè)充要條件是矩陣的各階順序主子式28.293.2.2高斯消去法的算法構(gòu)造（續(xù)）即29.303.2.3高斯消去法算法分析

消元過(guò)程的計(jì)算量，高斯消去法消去過(guò)程分n-1步第k步的計(jì)算工作量為：1〕計(jì)算乘數(shù)：需要作〔n-k〕次除法運(yùn)算；2〕消元：需作(n-k)2次乘法運(yùn)算和(n-k)2次加減法運(yùn)算；3〕計(jì)算b(k)：需作〔n-k〕次乘法運(yùn)算和(n-k)次加減法運(yùn)算；k=1，2，…，n-1〔1〕高斯消去法的計(jì)算量〔n-k〕行,〔n-k〕列〔n-k〕行〔n-k〕列30.31乘除法運(yùn)算加減法運(yùn)算于是完成n-1步運(yùn)算全部消元計(jì)算共需要作求和公式3.2.3高斯消去法算法分析(續(xù)）31.32〔2〕回代計(jì)算：共需要作n(n+1)/2乘除法運(yùn)算，n,…,1n(n-1)/2加減法運(yùn)算，n-1,…,1用高斯消去法解（其中A∈Rn×n）的計(jì)算量為共需作乘除法運(yùn)算加減法運(yùn)算3.2.3高斯消去法算法分析(續(xù)）32.33在計(jì)算機(jī)上用高斯消去法解低階稠密矩陣線性方程組時(shí)要注意幾點(diǎn)：（1）要用一個(gè)二維數(shù)組A(n,n)存放系數(shù)矩陣A的元素，用一維數(shù)組b(n)存放常數(shù)項(xiàng)b分量。（2）需要輸入的數(shù)據(jù)：A，b。（3）約化的中間結(jié)果A(k)元素沖掉A元素，b(k)沖掉b。例如，計(jì)算（a）mik←-A(i,k)/A(k,k)，（i=k+1，…，n）；（b）A(i,j)←A(i,j)+mik*A(k,j)，(i=k+1,…,n；j=k+1,…,n）;（c）b(i)←b(i)+mik*b(k)，（i=k+1，…，n）。（4）如果不存在ik，使，輸出方程沒(méi)有唯一解的信息。

3.2.3高斯消去法算法分析(續(xù)）〔2〕高斯消去法的矩陣解釋33.343.2.4列主元高斯消去法

用高斯消去法解Ax=b時(shí)，其中設(shè)A為非奇異矩陣，可能出現(xiàn)情況，這時(shí)必須進(jìn)行帶行交換的高斯消去法。但在實(shí)際計(jì)算中即使但其絕對(duì)值很小時(shí)，用作除數(shù)，會(huì)導(dǎo)致中間結(jié)果矩陣A(k)元素?cái)?shù)量級(jí)嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，使得最后的計(jì)算結(jié)果不可靠。

34.35例3.2設(shè)有方程組解[方法1]用高斯消去法求解〔用具有舍入的4位浮點(diǎn)數(shù)進(jìn)行運(yùn)算〕。3.2.4列主元高斯消去法（續(xù)）

35.36回代，求得解x2=1.000，x1=0.000不滿(mǎn)足原方程：錯(cuò)誤3.2.4列主元高斯消去法（續(xù)）

36.37[方法2]用具有行交換的高斯消去法〔防止小主元〕。m21=-10-4x2=1.00，x1=1.00

方法1計(jì)算失敗的原因，是用了一個(gè)絕對(duì)值很小的數(shù)作除數(shù)，乘數(shù)很大，引起約化中間結(jié)果數(shù)量很?chē)?yán)重增長(zhǎng)，再舍入就使得計(jì)算結(jié)果不可靠了。

精確解為或x*=(0.9998999，1.00010001)T3.2.4列主元高斯消去法（續(xù)）

37.對(duì)同一個(gè)數(shù)值問(wèn)題，用不同的計(jì)算方法，得到的結(jié)果的精度大不一樣。一個(gè)計(jì)算方法，如果用此方法的計(jì)算過(guò)程中舍入誤差得到控制，對(duì)計(jì)算結(jié)果影響較小，稱(chēng)此方法為數(shù)值穩(wěn)定的；否那么，如果用此計(jì)算方法的計(jì)算過(guò)程中舍入誤差增長(zhǎng)迅速，計(jì)算結(jié)果受舍入誤差影響較大稱(chēng)此方法為數(shù)值不穩(wěn)定。應(yīng)選擇和使用數(shù)值穩(wěn)定的計(jì)算方法，否那么，如果使用數(shù)值不穩(wěn)定的計(jì)算方法去解數(shù)值計(jì)算問(wèn)題，就可能導(dǎo)致計(jì)算失敗。383.2.4列主元高斯消去法（續(xù)）

38.39在采用高斯消去法解方程組時(shí)，小主元可能導(dǎo)致計(jì)算失敗，故在消去法中應(yīng)防止采用絕對(duì)值很小的主元素。對(duì)一般矩陣方程組，需要引進(jìn)選主元的技巧，即在高斯消去法的每一步應(yīng)該選取系數(shù)矩陣或消元后的低階矩陣中絕對(duì)值最大的元素作為主元素，保持乘數(shù)|mik|≤1，以便減少計(jì)算過(guò)程中舍入誤差對(duì)計(jì)算解的影響。3.2.4列主元高斯消去法（續(xù)）

完全主元消去法：行列均采用最大主元系數(shù)調(diào)整39.40列主元消去法完全主元素消去法是解低階稠密矩陣方程組的有效方法，但完全主元素消去法在選取主元時(shí)要花費(fèi)一定的計(jì)算機(jī)時(shí)間?，F(xiàn)介紹一種在實(shí)際計(jì)算中常用的局部選主元〔即列主元〕消去法。列主元消去法即是每次選主元時(shí)，僅依次按列選取絕對(duì)值最大的元素作為主元素，且僅交換兩行，再進(jìn)行消元計(jì)算。3.2.4列主元高斯消去法（續(xù)）

40.413.2.4列主元高斯消去法（續(xù)）

設(shè)有線性方程組Ax=b，其中設(shè)A為非奇異矩陣。方程組的增廣矩陣為然后交換〔A，b〕的第1行與第l行元素，再進(jìn)行消元計(jì)算。第1步〔k=1〕：首先在A的第一列中選取絕對(duì)值最大的元素al1，作為第一步的主元素:41.42設(shè)列主元素消去法已經(jīng)完成第1步到第k-1步的按列選主元，交換兩行，消元計(jì)算得到與原方程組等價(jià)的方程組A(k)x=b(k)

第k步選列主元區(qū)域3.2