[科普中國]-高斯消元法

簡介

數(shù)學(xué)上，高斯消元法（或譯：高斯消去法），是線性代數(shù)規(guī)劃中的一個算法，可用來為線性方程組求解。但其算法十分復(fù)雜，不常用于加減消元法，求出矩陣的秩，以及求出可逆方陣的逆矩陣。不過，如果有過百萬條等式時，這個算法會十分省時。一些極大的方程組通常會用迭代法以及花式消元來解決。當(dāng)用于一個矩陣時，高斯消元法會產(chǎn)生出一個“行梯陣式”。高斯消元法可以用在電腦中來解決數(shù)千條等式及未知數(shù)。亦有一些方法特地用來解決一些有特別排列的系數(shù)的方程組。

歷史該方法以數(shù)學(xué)家高斯命名，由拉布扎比.伊丁特改進(jìn)，發(fā)表于法國但最早出現(xiàn)于中國古籍《九章算術(shù)》，成書于約公元前150年。1

原理內(nèi)容消元法是將方程組中的一方程的未知數(shù)用含有另一未知數(shù)的代數(shù)式表示，并將其代人到另一方程中，這就消去了一未知數(shù)，得到一解；或?qū)⒎匠探M中的一方程倍乘某個常數(shù)加到另外一方程中去，也可達(dá)到消去一未知數(shù)的目的。消元法主要用于二元一次方程組的求解。

核心1)兩方程互換，解不變；

2)一方程乘以非零數(shù)k，解不變；

3)一方程乘以數(shù)k加上另一方程，解不變2。

求逆矩陣具體例子例如，考慮下面的矩陣

為了找到這個矩陣的逆矩陣，擴(kuò)充以下矩陣：

通過計算，可以將增廣矩陣轉(zhuǎn)換為簡化行階梯形式，即把左邊轉(zhuǎn)化為單位矩陣：

求得B為A的逆矩陣。

其他應(yīng)用找出逆矩陣高斯消元法可以用來找出一個可逆矩陣的逆矩陣。設(shè)A 為一個N * N的矩陣，其逆矩陣可被兩個分塊矩陣表示出來。將一個N * N單位矩陣 放在A 的右手邊，形成一個N * 2N的分塊矩陣B = [A,I] 。經(jīng)過高斯消元法的計算程序后，矩陣B 的左手邊會變成一個單位矩陣I ，而逆矩陣A ^(-1) 會出現(xiàn)在B 的右手邊。

假如高斯消元法不能將A 化為三角形的格式，那就代表A 是一個不可逆的矩陣。

應(yīng)用上，高斯消元法極少被用來求出逆矩陣。高斯消元法通常只為線性方程組求解。

計出秩的基本算法高斯消元法可應(yīng)用在任何m * n的矩陣A。在不可減去某數(shù)的情況下，我們都只有跳到下一行。以一個6 * 9的矩陣作例，它可以變化為一個行梯陣式：

1 * 0 0 * * 0 * 0

0 0 1 0 * * 0 * 0

0 0 0 1 * * 0 * 0

0 0 0 0 0 0 1 * 0

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 0

而矩陣中的 *' 是一些數(shù)字。這個梯陣式的矩陣T 會有一些關(guān)于A的資訊：

A 的秩是5，因?yàn)門 有5行非0的行；

A 的列的向量空間，可從A 的第1、3、4、7和9列中得知，其數(shù)值在矩陣T 之中；

矩陣中的 *' 表示了A 的列可怎樣寫為列中的數(shù)的組合。1

分析高斯消元法的算法復(fù)雜度是；這就是說，如果系數(shù)矩陣的是n × n，那么高斯消元法所需要的計算量大約與成比例。

高斯消元法可用在任何域中。

高斯消元法對于一些矩陣來說是穩(wěn)定的。對于普遍的矩陣來說，高斯消元法在應(yīng)用上通常也是穩(wěn)定的，不過亦有例外。1

偽代碼高斯消元法的其中一種偽代碼:

i=1j=1while(i≤mandj≤n)doFind pivot in column j,starting in row i:maxi:=ifork:=i+1tomdoifabs(A[k,j])>abs(A[maxi,j])thenmaxi:=kendifendforifA[maxi,j]≠0thenswap rows i and max i,but do not change the value of iNow A[i,j]will contain the old value of A[maxi,j].divide each entry in row i by A[i,j]Now A[i,j] will have the value 1.foru:=i+1tomdosubtractA[u,j]*rowifromrowuNowA[u,j]willbe0,sinceA[u,j]-A[i,j]*A[u,j]=A[u,j]-1*A[u,j]=0.endfori=i+1endifj=j+1endwhileoutput subtractA[u,j]這個算法和之前談及的有點(diǎn)兒不同，它由絕對值最大的部分開始做起，這樣可以改善算法上的穩(wěn)定性。將經(jīng)過調(diào)換后的第一列作為起點(diǎn)，這算法由左至右地計算。每作出以下兩個步驟，才跳到下一列：

1.定出每列的最后一個非0的數(shù)，將每行的數(shù)字除以該數(shù)，使到每行的第一個數(shù)成為1；

2.將每行的數(shù)字減去第一行的第一個數(shù)的某個倍數(shù)。

所有步驟完成后，這個矩陣會變成一個行梯陣式，再用代入法就可解決這個方程組。

線性方程組其實(shí)是相當(dāng)容易解決的，基本的思想就是消元。但是當(dāng)未知數(shù)較多時，解起來也蠻頭疼的。在這里向大家介紹高斯消元法。例如解如下四元一次方程組：

除去各未知數(shù)，將各數(shù)排在一起，成為矩陣：

為方便起見，用r2+r1表示把第一行各數(shù)加到第二行對應(yīng)數(shù)上。

r2-2*r1, r3-3*r1, r4-4*r1,r3+4*r2, r4+3*r2,r4-2*r3, 可得：

化為方程組形式則為：

從而，可得：

X4=4

X3=3

X2=2

X1=1.

說明：對于矩陣采取的變換的合理性，可對照相應(yīng)方程組的變換加以理解。1