線性方程組的解法上

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

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

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

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

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

(3.1)14.15引進記號

(3.1)可用矩陣形式表示

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

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

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

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

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

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

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

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

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

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

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

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

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

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

方法1計算失敗的原因，是用了一個絕對值很小的數(shù)作除數(shù)，乘數(shù)很大，引起約化中間結(jié)果數(shù)量很嚴重增長，再舍入就使得計算結(jié)果不可靠了。

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

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

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

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

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

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

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