高絲消去法

高斯消去法，又稱高斯消元法，實際上就是我們俗稱的加減消元法。數學上，高斯消去法或稱高斯－約當消去法，由高斯和約當得名（很多人將高斯消去作為完整的高斯－約當消去的前半部分），它是線性代數中的一個算法，用於決定線性方程組的解，決定矩陣的秩，以及決定可逆方矩陣的逆。當用於一個矩陣時，高斯消去產生“行消去梯形形式”。高斯消去法，又稱高斯消元法，實際上就是我們俗稱的加減消元法。 數學上，高斯消去法或稱高斯－約當消去法，由高斯和約當得名（很多人將高斯消去作為完整的高斯－約當消去的前半部分），它是線性代數中的一個算法，用於決定線性方程組的解，決定矩陣的秩，以及決定可逆方矩陣的逆。當用於一個矩陣時，高斯消去產生“行消去梯形形式”。例如：一個二元一次方程組，設法對每個等式進行變形，使兩個等式中的同一個未知數的係數相等，這兩個等式相減，得到一個新的等式，在這個新的等式中，細數相等的未知數就被除去了（係數為0）。同樣的也適合多元多次方程組。

基本介紹

• 中文名：高絲消去法
• 別名：高斯消元法
• 俗稱：加減消元法
• 學科：數學

簡述

高斯消去法，又稱高斯消元法，實際上就是我們俗稱的加減消元法。數學上，高斯消去法或稱高斯－約當消去法，由高斯和約當得名（很多人將高斯消去作為完整的高斯－約當消去的前半部分），它是線性代數中的一個算法，用於決定線性方程組的解，決定矩陣的秩，以及決定可逆方矩陣的逆。當用於一個矩陣時，高斯消去產生“行消去梯形形式”。高斯消去法，又稱高斯消元法，實際上就是我們俗稱的加減消元法。
數學上，高斯消去法或稱高斯－約當消去法，由高斯和約當得名（很多人將高斯消去作為完整的高斯－約當消去的前半部分），它是線性代數中的一個算法，用於決定線性方程組的解，決定矩陣的秩，以及決定可逆方矩陣的逆。當用於一個矩陣時，高斯消去產生“行消去梯形形式”。例如：一個二元一次方程組，設法對每個等式進行變形，使兩個等式中的同一個未知數的係數相等，這兩個等式相減，得到一個新的等式，在這個新的等式中，細數相等的未知數就被除去了（係數為0）。同樣的也適合多元多次方程組。
高絲消去法 - 信息學方面的套用

歷史

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

例子

高斯消元法可用來找出下列方程組的解或其解的限制：

這個算法的原理是：

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

在剛才的例子中，我們將和相加，就可以將中的消除了。然後再將和相加，就可以將中的消除。

我們可以這樣寫：

結果就是：

現在將和相加，就可將中的消除：

其結果是：

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

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

然後就可以將代入中，立即就可得出第二個答案：

之後，將和代入之中，最後一個答案就出來了：

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

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

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

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

這矩陣叫做“行梯陣式”。

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

最後這矩陣叫做“簡化行梯陣式”，亦是高斯－約當消元法指定的步驟。

其他套用

找出逆矩陣

高斯消元法可以用來找出一個可逆矩陣的逆矩陣。設為一個的矩陣，其逆矩陣可被兩個分塊矩陣表示出來。將一個單位矩陣放在的右手邊，形成一個的分塊矩陣。經過高斯消元法的計算程式後，矩陣的左手邊會變成一個單位矩陣，而逆矩陣會出現在的右手邊。

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

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

計出秩的基本算法

高斯消元法可套用在任何的矩陣。在不可減去某數的情況下，我們都只有跳到下一行。以一個的矩陣作例，它可以變化為一個行梯陣式：

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

的秩是5，因為有5列非0的列；

的行的向量空間Col(A)，可從的第1、3、4、7和9行中得知，其數值在矩陣{\displaystyle T}之中；

矩陣中的*'表示了的列可怎樣寫為列中的數的組合。

分析

高斯消元法的算法複雜度是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。

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

隨著多核處理器的日益普及，現在的程式設計師可以利用執行緒級並行高斯消元算法來提高計算的速度。記憶體共享模式（而不是訊息交換模式）的偽代碼如下所示：

// Note this code sample has been mangled (missing attr init/scope? bad gauss() indentation?)...// What is original source?  Can we get valid C or else simplified pseudo code instead of this hybrid? 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)); }