反饋

高斯消元法

數學上，高斯消元法（或譯：高斯消去法），是線性代數規劃中的一個算法，可用來為線性方程組求解。但其算法十分複雜，不常用於加減消元法，求出矩陣的秩，以及求出可逆方陣的逆矩陣。不過，如果有過百萬條等式時，這個算法會十分省時。一些極大的方程組通常會用迭代法以及花式消元來解決。當用於一個矩陣時，高斯消元法會產生出一個“行梯陣式”。高斯消元法可以用在電腦中來解決數千條等式及未知數。亦有一些方法特地用來解決一些有特別排列的係數的方程組。^[1]

中文名: 高斯消元法
外文名: GaussianElimination
命名: 高斯

最早出現: 《九章算術》
類別: 線性代數算法
其他應用: 找出逆矩陣

高斯消元法定義簡介

高斯消元法定義歷史

圖示

該方法以數學家高斯命名，由拉布扎比.伊丁特改進，發表於法國但最早出現於中國古籍《九章算術》，成書於約公元前150年。^[1]

高斯消元法定義原理

內容

消元法是將方程組中的一方程的未知數用含有另一未知數的代數式表示，並將其代入到另一方程中，這就消去了一未知數，得到一解；或將方程組中的一方程倍乘某個常數加到另外一方程中去，也可達到消去一未知數的目的。消元法主要用於二元一次方程組的求解。

核心

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

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

3)一方程乘以數k加上另一方程，解不變^[2] 。

高斯消元法舉例説明

例如，考慮下面的矩陣

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

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

求得B為A的逆矩陣。

高斯消元法其他應用

找出逆矩陣

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

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

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

計出秩的基本算法

高斯消元法可應用在任何m * n的矩陣A。在不可減去某數的情況下，我們都只有跳到下一行。以一個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

而矩陣中的 *' 是一些數字。這個梯陣式的矩陣T 會有一些關於A的資訊：

A 的秩是5，因為T 有5行非0的行；

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

矩陣中的 *' 表示了A 的列可怎樣寫為列中的數的組合。^[1]

高斯消元法應用分析

高斯消元法的算法複雜度是

；這就是説，如果係數矩陣的是n × n，那麼高斯消元法所需要的計算量大約與

成比例。

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

高斯消元法對於一些矩陣來説是穩定的。對於普遍的矩陣來説，高斯消元法在應用上通常也是穩定的，不過亦有例外。^[1]

高斯消元法偽代碼

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

i=1
j=1
while(i≤mandj≤n)do
Find pivot in column j,starting in row i:
maxi:=i
fork:=i+1tomdo
ifabs(A[k,j])>abs(A[maxi,j])then
maxi:=k
endif
endfor
ifA[maxi,j]≠0then
swap rows i and max i,but do not change the value of i
Now 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+1tomdo
subtractA[u,j]*rowifromrowu
NowA[u,j]willbe0,sinceA[u,j]-A[i,j]*A[u,j]=A[u,j]-1*A[u,j]=0.
endfor
i=i+1
endif
j=j+1
endwhile
output subtractA[u,j]

這個算法和之前談及的有點兒不同，它由絕對值最大的部分開始做起，這樣可以改善算法上的穩定性。將經過調換後的第一列作為起點，這算法由左至右地計算。每作出以下兩個步驟，才跳到下一列：

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