高斯消去法

  提示：此條目的主題不是高斯-若爾當消元法。

高斯消去法（英語：Gaussian Elimination）是線性代數中的一個算法，可以把矩陣轉化為行階梯形矩陣。高斯消去法可用來為線性方程組求解，求出矩陣的秩，以及求出可逆方陣的逆矩陣。

歷史

該方法以數學家卡爾·高斯命名，但最早出現於中國古籍《九章算術》，成書於約公元前150年。

例子

高斯消去法可用來找出下列方程組的解或其解的限制： $\left\{{\begin{matrix}2x+y-z=8\quad (L_{1})\\-3x-y+2z=-11\quad (L_{2})\\-2x+y+2z=-3\quad (L_{3})\\\end{matrix}}\right.$

這個算法的原理是：

首先，要將$L_{1}$以下的等式中的$x$消除，然後再將$L_{2}$以下的等式中的$y$消除。這樣可使整個方程組變成一個三角形似的格式。之後再將已得出的答案一個個地代入已被簡化的等式中的未知數中，就可求出其餘的答案了。

在剛才的例子中，我們將${\frac {3}{2}}L_{1}$和$L_{2}$相加，就可以將$L_{2}$中的$x$消除了。然後再將$L_{1}$和$L_{3}$相加，就可以將$L_{3}$中的$x$消除。

我們可以這樣寫：

$L_{2}+{\frac {3}{2}}L_{1}\rightarrow L_{2}$

$L_{3}+L_{1}\rightarrow L_{3}$

結果就是：

$2x+y-z=8\,$

${\frac {1}{2}}y+{\frac {1}{2}}z=1\,$

$2y+z=5\,$

現在將$-4L_{2}$和$L_{3}$相加，就可將$L_{3}$中的$y$消除：

$L_{3}+-4L_{2}\rightarrow L_{3}$

其結果是：

$2x+y-z=8\,$

${\frac {1}{2}}y+{\frac {1}{2}}z=1\,$

$-z=1\,$

這樣就完成了整個算法的初步，一個三角形的格式（指：變數的格式而言，上例中的變數各為3,2,1個）出現了。

第二步，就是由尾至頭地將已知的答案代入其他等式中的未知數。第一個答案就是：

$z=-1\quad (L_{3})$

然後就可以將$z$代入$L_{2}$中，立即就可得出第二個答案：

$y=3\quad (L_{2})$

之後，將$z$和$y$代入$L_{1}$之中，最後一個答案就出來了：

$x=2\quad (L_{1})$

就是這樣，這個方程組就被高斯消去法解決了。

這種算法可以用來解決所有線性方程組。即使一個方程組不能被化為一個三角形的格式，高斯消去法仍可找出它的解。例如，如果在第一步化簡後，$L_{2}$及$L_{3}$中沒有出現任何$y$，沒有三角形的格式，照著高斯消去法而產生的格式仍是一個列階梯形矩陣。這情況之下，這個方程組會有超過一個解，當中會有至少一個變數作為答案。每當變數被鎖定，就會出現一個解。

通常人或電腦在應用高斯消去法的時候，不會直接寫出方程組的等式來消去未知數，反而會使用矩陣來計算。以下就是使用矩陣來計算的例子：

$\left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$

跟著以上的方法來運算，這個矩陣可以轉變為以下的樣子：

$\left[{\begin{array}{ccc|c}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$

這矩陣叫做「列階梯形矩陣」。

最後，可以利用同樣的算法產生以下的矩陣，便可把所得出的解或其限制簡明地表示出來：

$\left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

最後這矩陣叫做「簡化列階梯形矩陣」，亦是高斯-若爾當消元法指定的步驟。

其他應用

找出逆矩陣

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

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

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

計出秩和基底的基本算法

高斯消去法可應用在任何$m\times n$的矩陣$A$。在不可減去某數的情況下，我們都只有跳到下一行。以一個$6\times 9$的矩陣作例，它可能可以變化為一個列階梯形矩陣：

${\begin{bmatrix}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\end{bmatrix}}$

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

• $A$的秩是5，因為$T$有5行非0的行；
• $A$的列空間Col(A)，將以$A$的第1、3、4、7和9行為基底，就是那些在矩陣$T$之中擁有主元的行；
• 矩陣中的*表示了$A$的該行如何寫為上述基底的線性組合。

分析

高斯消去法的算法複雜度是O(n³)；這就是說，如果系數矩陣的是n × n，那麼高斯消去法所需要的計算量大約與n³成比例。

高斯消去法可以用在電腦中來解決數千條等式及未知數。不過，如果有過百萬條等式時，這個算法會十分費時。一些極大的方程組通常會用迭代法來解決。亦有一些方法特地用來解決一些有特別排列的係數的方程組。

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

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

偽代碼

高斯消去法的其中一種偽代碼：

 i = 1
 j = 1
 while (i ≤ m and j ≤ n) do
   Find pivot in column j, starting in row i    // 从第i行(row)开始，找出第j列(column )中的最大值（i、j值应保持不变）  #台湾与大陆的列、行定义相反。台湾列为row行为column，大陆列为column行为row。
   maxi = i
   for k = i+1 to m do
     if abs(A[k,j]) > abs(A[maxi,j]) then
       maxi = k   // 使用交换法找出最大值（绝对值最大）
     end if
   end for
   if A[maxi,j] ≠ 0 then  // 判定找到的绝对值最大值是否为零：若不为零就进行以下操作；若为零则说明该列第(i+1)列以下（包括第(i+1)列）均为零，不需要再处理，直接跳转至第(j+1)行第(i+1)列
     swap rows i and maxi, but do not change the value of i   // 将第i行与找到的最大值所在行做交换，保持i值不变（i值记录了本次操作的起始行）
     Now A[i,j] will contain the old value of A[maxi,j].
     divide each entry in row i by A[i,j]    // 将交换后的第i列归一化（第i列所有元素分别除以A[i,j]）
     Now A[i,j] will have the value 1.
     for u = i+1 to m do    // 第j行中，第(i+1)列以下（包括第(i+1)列）所有元素都减去A[i,j]，直到第j行的i+1列以後元素均為零
       subtract A[u,j] * row i from row u
       Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
     end for
     i = i + 1   
   end if
   j = j + 1  // 第j行中，第(i+1)列以下（包括第(i+1)列）所有元素均为零。移至第(j+1)行，从第(i+1)列开始重复上述步骤。
 end while

這個算法和之前談到的有點不同，它由絕對值最大的部分開始做起，這樣可以改善算法的穩定性。本算法由左至右地計算，每作出以下三個步驟，才跳到下一行和下一列：

1. 定出每行的絕對值最大的一個非0的數，將第一列的值與該列交換，使得第一列擁有這一行的最大值；
2. 將第一行的數字除以該數，使得該列的第一個數成為1；
3. 對每一列減去第一列乘以每一列的第一個數，使得每一列的第一個數變為0。

所有步驟完成後，這個矩陣會變成一個列階梯形矩陣，再用代入法就可以求解該方程組。

隨着多核處理器的日益普及，現在的程序員可以利用線程級並行高斯消元算法來提高計算的速度。內存共享模式（而不是消息交換模式）的偽代碼如下所示：

void parallel(int num_threads,int matrix_dimension)
{
	int i;
	for(i=0; i<num_threads; i++)
		create_thread(&threads[i],i);
	pthread_attr_destroy(&attr); // Free attribute and wait for the other threads
	for(i=0; i<p; i++)
		pthread_join(threads[i],NULL);
}
void *gauss(int thread_id)
{
	int i,k,j;
	for(k=0; k<matrix_dimension-1; k++)
	{
		if(thread_id==(k%num_thread))  //interleaved-row work distribution
		{
			for(j=k+1; j<matrix_dimension; j++)
				M[k][j]=M[k][j]/M[k][k];
			M[k][k]=1;
		}
		barrier(num_thread,&mybarrier);      //wait for other thread finishing this round
		for(i=k+1; i<matrix_dimension; i=i+1)
			if(i%p==thread_id)
			{
				for(j=k+1; j<matrix_dimension; j++)
					M[i][j]=M[i][j]-M[i][j]*M[k][j];
				M[i][k]=0;
			}
		barrier(num_thread,&mybarrier);
	}
	return NULL;
}
void barrier(int num_thread, barrier_t * mybarrier)
{
	pthread_mutex_lock(&(mybarrier->barrier_mutex));
	mybarrier->cur_count++;
	if(mybarrier->cur_count!=num_thread)
		pthread_cond_wait(&(mybarrier->barrier_cond),&(mybarrier->barrier_mutex));
	else
	{
		mybarrier->cur_count=0;
		pthread_cond_broadcast(&(mybarrier->barrier_cond));
	}
	pthread_mutex_unlock(&(mybarrier->barrier_mutex));
}

參考文獻

• Atkinson, Kendall A. An Introduction to Numerical Analysis, 第二版, John Wiley & Sons, New York, 1989年 ISBN 978-0-471-50023-0
• Golub, Gene H., and Van Loan, Charles F. Matrix computations, 第三版, Johns Hopkins, Baltimore, 1996年 ISBN 978-0-8018-5414-9
• Lipschutz, Seymour, and Lipson, Mark. Schaum's Outlines: Linear Algebra, Tata McGraw-hill edition.Delhi 2001年, 第69-80頁

參見

• 高斯－約當消去法
• 列階梯形矩陣
• 線性方程組求解
• 四元玉鑒

外部連結

• 高斯消去法 （頁面存檔備份，存於網際網路檔案館）
• java applet高斯消去法，只能取自然數。
• matlab octave的高斯約當消去法
• python語言的高斯消去法 （頁面存檔備份，存於網際網路檔案館）
• 中國大百科智慧藏-消元法