查看“︁高斯消去法”︁的源代码

{{NoteTA
|G1=Math
|G2=IT
|1=zh-tw:約旦;zh-hk:若爾當;zh-hans:若尔当;
|2=zh-hans:迭代;zh-hant:疊代;
|3=zh-hans:消元法;zh-hant:消去法;
}}
{{Distinguish2|'''[[高斯-若爾當消元法|{{Forceconvert|高斯-若爾當消元法}}]]'''}}

'''高斯消去法'''（{{lang-en|Gaussian Elimination}}）是[[线性代数]]中的一个[[算法]]，可以把[[矩阵]]转化为[[阶梯形矩阵|行阶梯形矩阵]]。<ref>{{cite book|author=Steven J. Leon|title=''Linear Algebra With Applications''|year=2014|publisher=[[培生教育]]|isbn=9781292025148|pages=第13頁}}</ref>高斯消去法可用來為[[線性方程組求解]]，求出[[矩陣的秩]]，以及求出可逆[[方塊矩陣|方陣]]的[[逆矩陣]]。

== 历史 ==
高斯消去法最早出现在中国数学典籍《[[九章算术]]》第八章〈方阵〉中，尽管书中未对其提供正式的证明<ref>{{cite book| title=《九章算术》| year=150bc| chapter=第八章 方程| chapterurl=http://www.math.tku.edu.tw/chinese/mathhall/mathinfo/lwymath/ninechapterBOT.htm#bookmark08| url=http://www.math.tku.edu.tw/chinese/mathhall/mathinfo/lwymath/ninechapterBOT.htm| deadurl=yes| archiveurl=https://web.archive.org/web/20090419225313/http://www.math.tku.edu.tw/chinese/mathhall/mathinfo/lwymath/ninechapterBOT.htm| archivedate=2009年4月19日}}</ref>。该方法在十八道题目中有所应用，处理的联立方程组数量介于二至五个之间。根据历史记载，此书最早的确切引用可追溯至公元 179 年，但其中部分内容可能早在公元前 150 年左右便已撰写完成<ref>{{Cite web |title=Documenta Mathematica, Vol. Extra Volume: Optimization Stories (2012), 9-14 |url=https://www.emis.de/journals/DMJDMV/vol-ismp/10_yuan-ya-xiang.html |access-date=2022-12-02 |website=www.emis.de}}</ref><ref name="princeton">{{cite book | author1=Timothy Gowers | author2=June Barrow-Green | author3=Imre Leader | title=The Princeton Companion to Mathematics |url=https://archive.org/details/princetoncompanio00gowe|date=8 September 2008|publisher=Princeton University Press|isbn=978-0-691-11880-2|page=607}}<!-- |access-date=28 September 2012 --></ref>。到了三世纪，[[刘徽]]为其作注解。

根据 Grcar 的研究，透过消去法求解线性方程组的概念在欧亚大陆的多个文化中独立发展，最早可追溯至古代。在欧洲，[[文艺复兴]]晚期（16 世纪 50 年代）便已有明确记载该方法的应用。当时，数学家可能已将其视为基础知识，因此未特意加以说明，这也使得我们难以确切还原其详细的发展历程，仅能确定该方法在当时的欧洲多个地区已被广泛使用。

在欧洲，高斯消去法的发展可追溯至[[艾萨克·牛顿]]的笔记。 1670 年，牛顿指出，他所知的代数书籍中皆缺少求解联立方程组的相关内容，于是他亲自补充了这一部分。[[剑桥大学]]最终于 1707 年出版了这些笔记，书名为《{{le|通用算术|Arithmetica Universalis}}》，当时牛顿已经离开学术界。该书的内容被广泛仿效，使得（现今所称的）高斯消去法在 18 世纪末成为代数教科书中的标准课程。 1810 年，[[卡尔·弗里德里希·高斯|卡尔·高斯]]设计了一种用于对称消去的记号，并在 19 世纪被专业[[计算员]]采用，以求解最小二乘问题的法方程。然而，直到 1950 年代，由于对该方法历史的误解，这一演算法才被命名为「高斯消去法」。

部分学者将「高斯消去法」仅用于指将矩阵化为梯形（阶梯）形式的过程，而将「[[高斯－约旦消去法]]」用于指将矩阵进一步化为简化梯形（最简）形式的完整过程。之所以使用这一名称，是因为该方法是高斯消去法的变体，由{{le|威廉·乔丹 (大地测量学家)|Wilhelm Jordan (geodesist)|威廉·乔丹}}于 1888 年加以描述。然而，同一年克拉森（Clasen）发表的文章中也提出了这种方法，因此乔丹与克拉森很可能是独立发现高斯－约旦消去法的<ref>{{Citation | last1=Althoen | first1=Steven C. | last2=McLaughlin | first2=Renate | title=Gauss–Jordan reduction: a brief history | doi=10.2307/2322413 | year=1987 | journal=[[American Mathematical Monthly|The American Mathematical Monthly]] | issn=0002-9890 | volume=94 | issue=2 | pages=130–142 | jstor=2322413 | publisher=Mathematical Association of America}}</ref>。

== 例子 ==
高斯消去法可用來找出下列方程組的解或其解的限制：
<math>
\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.
</math>

這個算法的原理是：

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

在剛才的例子中，我們將<math>\frac{3}{2}L_1</math>和<math>L_2</math>相加，就可以將<math>L_2</math>中的<math>x</math>消除了。然後再將<math>L_1</math>和<math>L_3</math>相加，就可以將<math>L_3</math>中的<math>x</math>消除。

我們可以這樣寫：
:<math>L_2 + \frac{3}{2}L_1 \rightarrow L_2</math>
:<math>L_3 + L_1 \rightarrow L_3</math>

結果就是：
:<math>2x + y - z = 8 \, </math>
:<math>\frac{1}{2}y + \frac{1}{2}z = 1 \, </math>
:<math>2y + z = 5 \, </math>

現在將<math>-4L_2</math>和<math>L_3</math>相加，就可將<math>L_3</math>中的<math>y</math>消除：
:<math>L_3 + -4L_2 \rightarrow L_3</math>

其結果是：
:<math>2x + y - z = 8 \, </math>
:<math>\frac{1}{2}y + \frac{1}{2}z = 1 \, </math>
:<math>-z = 1 \, </math>

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

第二步，就是由尾至頭地將已知的答案代入其他等式中的未知數。第一個答案就是：
: <math>z = -1 \quad (L_3)</math>

然後就可以將<math>z</math>代入<math>L_2</math>中，立即就可得出第二個答案：
: <math>y = 3 \quad (L_2)</math>

之後，將<math>z</math>和<math>y</math>代入<math>L_1</math>之中，最後一個答案就出來了：
: <math>x = 2 \quad (L_1)</math>
就是這樣，這個方程組就被高斯消去法解決了。

這種算法可以用來解決所有線性方程組。即使一個方程組不能被化為一個三角形的格式，高斯消去法仍可找出它的解。例如，如果在第一步化簡後，<math>L_2</math>及<math>L_3</math>中沒有出現任何<math>y</math>，沒有三角形的格式，照著高斯消去法而產生的格式仍是一個-{zh-hans:行; zh-hant:列;}-阶梯形矩阵。這情況之下，這個方程組會有超過一個解，當中會有至少一個[[自由變數和約束變數|變數]]作為答案。每當變數被鎖定，就會出現一個解。
 
通常人或[[電腦]]在應用高斯消去法的時候，不會直接寫出方程組的等式來消去未知數，反而會使用[[矩陣]]來計算。以下就是使用矩陣來計算的例子： 
:<math>
\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array} \right]
</math>
 
跟著以上的方法來運算，這個矩陣可以轉變為以下的樣子：
:<math>
\left[ \begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
0 & \frac{1}{2} & \frac{1}{2} & 1 \\
0 & 0 & -1 & 1
\end{array} \right]
</math>
這矩陣叫做「[[阶梯形矩阵|-{zh-hans:行; zh-hant:列;}-阶梯形矩阵]]」。
 
最後，可以利用同樣的算法產生以下的矩陣，便可把所得出的解或其限制簡明地表示出來：
:<math>
\left[ \begin{array}{ccc|c}
1 & 0 & 0 & 2 \\
0 & 1 & 0 & 3 \\
0 & 0 & 1 & -1
\end{array} \right]
</math>
最後這矩陣叫做「[[阶梯形矩阵|簡化-{zh-hans:行; zh-hant:列;}-阶梯形矩阵]]」，亦是[[高斯-若爾當消元法]]指定的步驟。<ref>{{cite book|author=Steven J. Leon|title=''Linear Algebra With Applications''|year=2014|publisher=[[培生教育]]|isbn=9781292025148|pages=第17頁}}</ref>

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

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

應用上，高斯消去法極少被用來求出逆矩陣。高斯消去法通常只為[[線性方程組求解]]。<ref>Atkinson, 1989年，第514頁</ref>

=== 計出秩和基底的基本算法 ===
高斯消去法可應用在任何<math>m \times n</math>的[[矩陣]]<math>A</math>。在不可減去某數的情況下，我們都只有跳到下一行。以一個<math>6 \times 9</math>的矩陣作例，它可能可以變化為一個-{zh-hans:行; zh-hant:列;}-阶梯形矩阵：
:<math>
\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}
</math>
而矩陣中的*是一些數字。這個-{zh-hans:行; zh-hant:列;}-阶梯形矩阵<math>T</math>會有一些關於<math>A</math>的資訊：
* <math>A</math>的[[矩陣的秩|秩]]是5，因為<math>T</math>有5行非0的行；
* <math>A</math>的[[行空間|列空間]]Col(A)，將以<math>A</math>的第1、3、4、7和9行為[[基底]]，就是那些在矩陣<math>T</math>之中擁有[[主元]]的行；
* 矩陣中的*表示了<math>A</math>的該行如何寫為上述基底的[[線性組合]]。

== 分析 ==
高斯消去法的[[計算複雜性理論|算法复杂度]]是[[大O符號|O]](''n''<sup>3</sup>)；这就是说，如果系數矩阵的是''n'' × ''n''，那么高斯消去法所需要的计算量大约与''n''<sup>3</sup>[[成比例]]。

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

高斯消去法可用在任何[[域 (數學)|域]]中。

高斯消去法對於一些[[矩陣]]來說是[[數值穩定性|穩定]]的。對於普遍的矩陣來說，高斯消去法在應用上通常也是穩定的，不過亦有例外。<ref>Golub and Van Loan, §3.4.6</ref>

== 伪代码 ==
高斯消去法的其中一种[[伪代码]]：
<syntaxhighlight lang="c">
 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
</syntaxhighlight>

这个算法和之前谈到的有点不同，它由[[绝对值]]最大的部分开始做起，这样可以改善算法的稳定性。本算法由左至右地计算，每作出以下三个步骤，才跳到下一行和下一列：
# 定出每行的绝对值最大的一个非0的数，将第一列的值与该列交换，使得第一列拥有这一行的最大值；
# 将第一行的数字除以该数，使得该列的第一个数成为1；
# 對每一列減去第一列乘以每一列的第一個數，使得每一列的第一個數變為0。
所有步骤完成后，这个[[矩阵]]会变成一个-{zh-hans:行; zh-hant:列;}-阶梯形矩阵，再用代入法就可以求解该方程组。


随着多核处理器的日益普及，现在的程序员可以利用[[线程]]级并行高斯消元算法来提高计算的速度。内存共享模式（而不是消息交换模式）的伪代码如下所示：

<syntaxhighlight lang="c">
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));
}
</syntaxhighlight>

== 參考文獻 ==
{{reflist}}
* 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頁

== 參見 ==
* [[高斯－約當消去法]]
* [[阶梯形矩阵|-{zh-hans:行; zh-hant:列;}-阶梯形矩阵]]
* [[線性方程組求解]]
* [[四元玉鑒]]

== 外部链接 ==
* [http://www.stat.nctu.edu.tw/MISG/SUmmer_Course/C_language/Ch06/GaussElimination.htm 高斯消去法] {{Wayback|url=http://www.stat.nctu.edu.tw/MISG/SUmmer_Course/C_language/Ch06/GaussElimination.htm |date=20190908125557 }}
* [https://web.archive.org/web/20060812215904/http://www25.brinkster.com/denshade/GaussElimination.html java applet高斯消去法]，只能取自然数。
* [https://web.archive.org/web/20070402231833/http://users.powernet.co.uk/kienzle/octave/matcompat/scripts/linear-algebra/rref.m matlab octave的高斯约当消去法]
* [http://elonen.iki.fi/code/misc-notes/python-gaussj/index.html python语言的高斯消去法] {{Wayback|url=http://elonen.iki.fi/code/misc-notes/python-gaussj/index.html |date=20201028165528 }}
* [https://web.archive.org/web/20070927024949/http://library.mit.edu.tw:8080/Content.asp?ID=43573 中國大百科智慧藏-消元法]

{{线性代数的相关概念}}

[[Category:数值线性代数|G]]
[[Category:带有伪代码示例的条目]]