算法帝國的重要成員
——初等行變換算法

焦華

（貴州商學(xué)院，貴陽 550014）

0 引言

“算法”其實早已深入到人類社會及人類生活的各個方面，只是大多數(shù)人對此一無所知而已。小到十字路口的交通紅綠燈和地鐵站里的無人自動售票機(jī)，大到滬深股市每天幾千億甚至上萬億資金股票的交易及載人航天的探月工程，都與算法分不開。算法對人類社會影響的深度、廣度、遠(yuǎn)度，遠(yuǎn)遠(yuǎn)超出了一般人的想象及認(rèn)知[1]P26。

隨著大數(shù)據(jù)時代的到來以及人工智能研究與應(yīng)用的再度復(fù)蘇，智能機(jī)器人、智能家電、無人駕駛飛機(jī)和汽車等話題越來越受到人們的關(guān)注。而這一切都與“算法”息息相關(guān)！甚至有專家提出“算法”將統(tǒng)治世界、算法帝國已經(jīng)形成！[1]P58

從古老的歐幾里得算法、割圓術(shù)算法到后來的搜索算法、排序算法等，“算法”已從數(shù)學(xué)概念轉(zhuǎn)變?yōu)橛嬎銠C(jī)概念。數(shù)學(xué)的研究一直是計算機(jī)數(shù)值算法豐饒的源泉。在“算法”熱得發(fā)紫的今天，我們重新審視一下算法帝國從古到今的重要成員，初等行變換算法應(yīng)當(dāng)入列。這是因為初等行變換算法是線性代數(shù)中貫穿始終的算法。而線性代數(shù)是自然科學(xué)、社會科學(xué)、工程技術(shù)、經(jīng)濟(jì)與管理等領(lǐng)域應(yīng)用非常廣泛的數(shù)學(xué)學(xué)科[4]。

在線性代數(shù)中，初等行變換是指三種基本的變換：交換矩陣的某兩行；矩陣的某一行乘以一個非零的數(shù)；把矩陣某一行的倍數(shù)加到另一行。定義這三種基本變換的想法應(yīng)當(dāng)來源于對線性方程組的研究。理論上已證明可將任一矩陣通過初等行變換化為行階梯形，進(jìn)一步化為行最簡形。（如果再進(jìn)行初等列變換，可化為標(biāo)準(zhǔn)形。）初等行變換算法是以上具體步驟的描述，且已變成了計算機(jī)程序，我們也就可用MATLAB來解決線性代數(shù)問題。以下是初等行變換算法在線性代數(shù)各分支中的應(yīng)用[2]P65。

1 初等行變換算法在矩陣中的應(yīng)用

在計算矩陣的逆矩陣時，有兩種常用方法：伴隨矩陣法和初等行變換法，相比較而言，初等行變換法更簡潔。（當(dāng)然從定義出發(fā)的待定系數(shù)法也算一種方法，只是太繁瑣了。）

實例1證明 A可逆，并求A-1。

解：這里只給出初等行變換法，(A,E)→(E,A-1)，當(dāng)把左邊的A變成了E，右邊的E也就變成了A-1。

從而得到A可逆，且

用MATLAB驗算如下：（可看出結(jié)果是一致的）[3]P15-17

>>A=[0-2 1;1 3-2;-2 3 0];

>>inv（A）

ans=

6.00003.00001.0000

4.0000 2.00001.0000

9.0000 4.00002.0000

>>A^-1

ans=

6.0000 3.00001.0000

4.00002.00001.0000

9.0000 4.00002.0000

利用初等行變換法求矩陣秩的方法：通過初等行變換把矩陣變成它的行階梯形，行階梯形矩陣中的非0行的行數(shù)即是該矩陣的秩。

實例2設(shè)矩陣其中λ為參數(shù)，求矩陣A的秩。

解：對A作初等行變換，得：

當(dāng)λ=3時，r(A)=2；當(dāng)λ≠3時，r(A)=3。[2]P76-78

求向量組的極大無關(guān)組的方法：以向量組中各向量作為列向量組成矩陣后，只允許作初等行變換將此矩陣化為行階梯形矩陣，（如果問題需要，可進(jìn)一步化為行最簡形矩陣。）之后可直接寫出所求向量組的極大無關(guān)組。這種方法的理論依據(jù)是：初等行變換不改變矩陣列向量之間的線性關(guān)系；即矩陣行的初等變換將保持列向量間的線性相關(guān)性或線性無關(guān)性。

實 例3求 向 量 組α1=(1 ,1,1)T，α2=(1 ,1,0)T，α3=(1 ,0,0)T，α4=(1 ,2,-3)T的一個極大無關(guān)組，并將其余向量用此極大無關(guān)組線性表示。[2]P104-105

解：由于問題需要將其余向量用極大組線性表示，因此初等行變換的目標(biāo)不局限于行階梯形矩陣，而需進(jìn)一步化為行最簡形矩陣。

向量組的秩為3，α1，α2，α3是向量組的一個極大無關(guān)組，且 α4=-3α1+5α2-α3。

2 初等行變換算法在線性方程組中的應(yīng)用

線性方程組的初等變換是指這三種變換：交換某兩個方程的位置；某方程的兩邊同時乘以一個非零的數(shù)；把某一個方程的適當(dāng)倍數(shù)加到另一個方程上。線性方程組經(jīng)過初等變換會將它變成另一個同解的方程組，高斯消去法的目標(biāo)就是通過初等變換將原有的線性方程組化為階梯形方程組、進(jìn)一步化為最簡形方程組，最終得到方程組的解。高斯消去法的產(chǎn)生是基于逐步消去（減少）未知量的思想。線性方程組與它的增廣矩陣一一對應(yīng)，高斯消去法的過程也就與初等行變換法的過程一一對應(yīng)。在人類的認(rèn)知歷程中，應(yīng)當(dāng)先有高斯消去法，之后才有初等行變換法。后者是前者從方程組到矩陣的映像，但后者更具備廣泛的應(yīng)用性！20世紀(jì)計算機(jī)的出現(xiàn)比數(shù)學(xué)家高斯所處的19世紀(jì)晚1個世紀(jì)，初等行變換算法是高斯消去法思想結(jié)合計算機(jī)編程的發(fā)揚(yáng)光大！相比較其他算法而言，比如克萊姆法則，初等行變換算法時間復(fù)雜度小。尤其是線性方程組規(guī)模龐大時，比如方程個數(shù)及未知量個數(shù)都是幾千個或幾萬個時，其優(yōu)勢更加明顯。[2]P84-85

線性方程組是線性代數(shù)的核心，是各分支的匯流處，是有廣泛的應(yīng)用背景的。

實例1有大米、黃豆、玉米、小麥各一袋共38元，若購大米3袋，黃豆5袋，玉米4袋，小麥2袋共需120元；若購大米4袋，黃豆3袋，玉米1袋，小麥1袋共需84元，若購大米2袋，黃豆4袋，玉米2袋，小麥4袋共需122元，問大米、黃豆、玉米、小麥每袋各多少元？

解：設(shè)大米、黃豆、玉米、小麥每袋各為x1,x2,x3,x4元，則：

可用克萊姆法則求解，但要計算5個4階行列式的值，運(yùn)算量大。克萊姆法則只具備理論價值。也可用消元法和代入法相結(jié)合的初等方法求解。這種方法靈活大，但不適宜計算機(jī)編程計算，這里采用初等行變換算法。

將線性方程組對應(yīng)的增廣矩陣用初等行變換化為行階梯形、行最簡形：

答：大米每袋10元、黃豆每袋8元、玉米每袋5元、小麥每袋15元。

用MATLAB驗算如下：[3]P17-19

>>A=[1 1 1 1;3 5 4 2;4 3 1 1;2 4 2 4];

>>b=[38;120;84;122];

>>x=A

x=

10.0000

8.0000

5.0000

15.0000

>>det（A）

ans=

-22

若已知答案（大米每袋10元、黃豆每袋8元、玉米每袋5元、小麥每袋15元）去構(gòu)造問題：（顯然是修改原題的某些數(shù)據(jù)，用紅色標(biāo)注。）

1、有大米、黃豆、玉米、小麥各1袋共38元，若購大米3袋，黃豆1袋，玉米2袋，小麥2袋共需78元；若購大米2袋，黃豆3袋，玉米1袋，小麥1袋共需64元，若購大米4袋，黃豆2袋，玉米4袋，小麥2袋共需106元，問大米、黃豆、玉米、小麥每袋各多少元？

用MATLAB驗算如下：[3]P16

>>A=[1 1 1 1;3 1 2 2;2 3 1 1;4 2 4 2];

>>b=[38;78;64;106];

>>x=A

x=

10

8

5

15

可以看出構(gòu)造問題的解與原問題的解是一樣的，構(gòu)造時要注意必須得到4個獨立的線性方程，從而得到唯一解。

下面的實例是對無窮多解的討論，用初等行變換算法求解。

實例2求齊次線性方程組的基礎(chǔ)解系及通解。[2]P118

解：

實例3設(shè)矩陣X滿足方程AX=BT，求X。

解：這是一個解不是向量而是矩陣的矩陣方程，用初等行變換算法求解。[2]P71-72

從而得到:

用MATLAB驗算如下：[3]P16-18

>>A=[1 1 2;2 2 3;4 3 3];

>>B=[1 0 0;2 1 1;-1 2 2];

>>X=AB'

X=

34-7

-6-814

23-4

>>X=inv（A）*B'

X=

34-7

-6-814

23-4

3 初等行變換算法在行列式中的應(yīng)用

行列式的計算有兩種常用的算法：“三角化”算法與降階算法。由于三角形行列式的值等于它的主對角線元素的乘積，因此“三角化”算法的目標(biāo)就是通過行列式的初等行變換及初等列變換（對應(yīng)矩陣）將原行列式化為上三角行列式。需要注意的有兩點：1、不局限于初等行變換，允許進(jìn)行初等列變換，更加方便靈活。2、第一種初等行變換（交換兩行）行列式要變號；第二種初等行變換（某行乘以某非0數(shù)）行列式就要除以該非0數(shù)；第三種初等行變換（某行適當(dāng)?shù)谋稊?shù)加到另一行）行列式的值不變。這三種變換結(jié)果實質(zhì)是行列式的三條性質(zhì)。可以看出，“三角化”算法是初等行變換算法在行列式中的應(yīng)用推廣。

實例1計算

解：從第4行起，后面一行減去前面一行，達(dá)到最大限度的化繁為簡，這里只采用初等行變換，過程如下：

實例2計算

解：其實可以初等行變換及初等列變換一起結(jié)合使用，但在此僅采用初等行變換，這是為了更好地突出本文的主題思想。

用MATLAB驗算如下：[3]P19

>>D=[3 1-1 2;-5 1 3-4;2 0 1-1;1-5 3-3];

>>det（D）

ans=

40

綜上所述，初等行變換算法的確是線性代數(shù)中貫穿始終的算法。由于是成熟算法，我們沒有用高級語言寫出代碼，只是在實例中用MATLAB驗算結(jié)果。馬云說：“人算不如天算，天算是什么？天算就是云計算。”。現(xiàn)代人們可通過電腦或手機(jī)等方式接入云數(shù)據(jù)中心，體驗到每秒10萬億次以上的云計算能力！明天很美好，未來有無限可能，古老的數(shù)學(xué)也將煥發(fā)出勃勃生機(jī)！[4]

[1]（美）克里斯托弗·斯坦納.算法帝國[M].人民郵電出版社，2014.

[2]吳贛昌.線性代數(shù)（經(jīng)管類第四版）[M].中國人民大學(xué)出版社，2011.

[3]于潤偉.MATLAB基礎(chǔ)及應(yīng)用（第三版）[M].機(jī)械工業(yè)出版社，2011.

[4]焦華.用計算機(jī)軟件輔助數(shù)學(xué)教學(xué)是大數(shù)據(jù)時代的需要[J].科技展望，2017（08）：177-178.