Gilbert Strang 經典線代課程心得

來自MIT的經典線代課程－－Gilbert Strang

第二課：消元法與回帶 ( Elimination and Back－substitution )

先談談何謂消元法，這其實不是什麼多麼嶄新或是具有創意性的想法，當我們最一開始解線性方程組時就已經學習過了這個方法，在台灣，這個方法有個更廣為人知的名稱──加減消去法，只是消元法相較於加減消去法有些限制，在消除未知數的順序上沒有那麼自由，但本質上這兩個方法的原理是相同的

這邊有個有趣的知識，一般來說在數學界，命名這件事一直以來都是先搶先贏，當時「卡爾·弗里德里希·高斯（Carl Friedrich Gauss）」在十九世紀初，將這種消元過程應用於計算行星軌道，並將其系統化、形式化，使其成為一個嚴謹的演算法，因此這個方法才最終以他命名。

不過這個方式其實可以追溯到中國的《九章算術 ( 公元前 100 年 ) 》中就有類似的系統化解法，也就是說，就算你比高斯早出生，並有一定名氣，然後也將此法寫進自己的著作中，並且在資訊不發達的年代沒有因為政權更迭或是戰亂失傳，並且通過貿易與多國語言傳播到世界，那消元法的創始者才可能換個人當了

所謂的先到先得沒那麼公平哈哈哈，抱歉有點離題了

話說回消元法，我們同樣會以線性方程組 ( 如下圖 ) 輔助理解

x＋2y＋z＝2 | 3x＋8y＋z＝12 | 4y＋z＝2

將上述線性方程組改以矩陣運算形式 A x ＝ b 表示，則如下圖

A ＝［1 , 2 , 1；3 , 8 , 1；0 , 4 , 1］| x ＝［x；y；z］| b ＝［2；12；2］

讓我們開始談談「高斯消元法」，所謂的「高斯消元法」可以簡單分為兩個部分，即步驟 1 到 4 的「消元 ( Elimination ) 」與最終得出答案的「回代」，以下將簡單說明細項

將首行首列 ( a₁₁ ) 定義為「選定主元 ( Working pivot ) 」
將「選定主元」下方的所有元定義為「消元目標數」
通過「消元目標數」與「選定主元」的比值得出「消元數 ( Multiplier , t _i ) 」
使用「基本列運算」配合「消元數」使同行的所有「消元目標數」成為零
換到下一行列( a₂₂ )定義下一個「選定主元」
重複執行，直到將所有「消元目標數」都變成零
得出「列梯形形式 (Row Echelon Form, REF)」
執行「回代 ( Back－substitution ) 」得出方程組解

補充：「選定主元」不代表最終消元完成時的矩陣主元，且沒有這個名詞，應該說很多名詞都是為了口語化說明而自設的，詳細共識還是參閱課本或是教授的講義

此處我們稍微取了一點巧，即定義「選定主元」時，假定「選定主元」總會出現非零元，取巧的原因是因為一開始就討論太完善沒什麼太多意義，讀者只需要記住接下來的「範例」是一個「便於理解的特例」，而「主對角線 ( Main diagonal ) 」上令人討厭的零的解決方式在這堂課的尾部會提到，還請安心地繼續看下去

從矩陣 A 中我們可以看出首個「選定主元 ( a₁₁ ) 」為 1 ，同行的「消元目標數」分別是「 3 ( a₂₁ ) 」與「 0 ( a₃₁ ) 」，因為「 a₃₁ ＝ 0 」，所以使用「步驟 3 」僅會得出「消元數 t₁」為

t₁＝ 3 / 1 ＝ 3

將「首列 ( Row₁ ) 」中的所有元都乘上「 t₁」後，經由「基本列運算」過後得出的「第二列 ( Row_2* )」定義為

Row_2(new)＝ Row₂－ 3 × Row₁

使用矩陣描述可寫作

完成第一行的消元後，將觀察第二個「選定主元 ( a₂₂ ) 」為「 2 」，同行的「消元目標數」是「 4 ( a₃₂ ) 」，使用「步驟 3 」僅會得出「消元數 t₂ 」為

t₂＝ 4 / 2 ＝ 2

將「次列 ( Row₂ ) 」中的所有元都乘上「 t₂」後，經由「基本列運算」過後得出的「第三列 ( Row_3** )」定義為

Row_3(new)＝ Row₃－ 2 × Row₂

使用矩陣描述可寫作

當「消元」完成後，位於「主對角線 ( Main diagonal ) 」上的元 { 1 , 2 , 5 } 便是最終的「矩陣主元 ( Pivot ) 」，而第 k 列的「主元」也被稱為「第 k 主元 ( k^th pivot ) 」

當滿足「消元目標數」皆為零的矩陣出現時，我們會此結構稱為「列梯形形式 (Row Echelon Form, REF)」，在這個範例中，最終矩陣的結構有著另一個更好更有用的結構名稱－－「上三角矩陣 (Upper triangular matrix, U)」

特別注意：我們消元的目的是讓矩陣變成 REF，如果在這個過程中 A → U 自然是最好，但不是所有的 REF 能成為真正定義上 U，這點務必要牢記於心，既然我們現在都是新手，為了方便課程說明，接下來的範例或敘述中都會使用結構更好的 U 進行說明

至此「高斯消元法 ( Gaussian Elimination ) 」的消元步驟便算是完成了，說白了就是按照順序做加減消去法，別想得太過複雜。

當我們得出主元 { 1 , 2 , 5 } 時，便能通過主元進行「回代 (Back-substitution)」便能完成「高斯消元法」，但你知道的，數學很少一路一路順遂，比人生崎嶇多了哈哈

因此我不得不先打斷消元法，並向讀者提出一個令人討厭的問題：

「如果過程中出現 a_kk = 0 且 akk 下方存在非零元素，該怎麼辦？」

例如出現下方的矩陣

經過剛剛的練習我們能知道，這個 B 是沒辦法進行消元的，且顯而易見這並不是一個REF 形式的矩陣，也就是說，我們剛剛學到的東西是拿 B 毫無辦法的 ( 真是令人難過 )，但這不是我們放棄 B 的理由，說實話，B的結構也很棒對吧！單行單列僅一元有值，如果能稍微妝點一下，勢必能使其煥然一新

為了拯救 B 並解決這種結構帶給數學家的折磨，我們需要好好的處理這個問題，該怎麼做呢？好吧，我想解決方法再顯而易見不過了，即

「列交換 ( Row exchange ) 」

什麼是「列交換 ( Row exchange ) 」？所謂的「列交換」是「基本列運算」的其中一種運算，功能也很直白，即「將不同的列進行交換」

對 B 進行「列交換」便可將 Row₂ 與 Row₃ 進行互換後便可得出矩陣 B'( 如下 )

在數學上，「列交換」有著更加「學術性質」的名稱－－「置換 ( Permutation ) 」，「置換」這個名稱出現在矩陣運算時，意味著有行列需要搬家了，不過關於「置換」如何轉換為矩陣是後面的內容與其相關的有趣性質，這裡不會有過多描述

讀者只需要知道看到 B 這類型矩陣時，我們有救了！

BUT！縱使我們有了名為「置換」的好工具，也存在一種狀況我們必須得放棄治療，那就「非滿秩 ( Not full rank ) 」的矩陣，像是下面這個 C

例子中的 C 滿足 REF 結構，但「 c₂₂ 」是零，且我們拿他毫無辦法，一點辦法都沒有，往好處想，此時的 C 因為滿足 REF 結構，因此第二主元我們尚且能夠定義在「 c₂₃ 」上 ( 真是令人哀傷 ) ，不過別太擔心～至少這節課裡，像這樣令人束手無策的情形不會再次出現，當我們回歸消元法時，一切噩夢皆如過往雲煙般消散，消元結果只會是美麗的「上三角矩陣」U

因此就結論而言，我們不希望使用消元法時出現主元為零的情況，因為這會影響到解的生成，但是這些內容要後面一段時間才會說到

此外，主元為零時，我們會說 A 是不可逆矩陣 ( 這是下次課程內容 )

===================================================================

好了，我們要進入「回代 ( Back－substitution ) 」的部分了

先將進度推回到消元開始前的 A ，我們要將 b 視為一個「額外行 ( Extra column ) 」放入 A 使其成為一個「增廣矩陣( Augmented matrix )」，我們將 Aug ( A ) 定義為

Aug ( A ) ＝ [ A | b ]

此時再進行「消元」，這時的列運算需要將「額外行」內部的元一併考慮進去 ( 其實就是多一個元需要運算 )，過程如下圖

經過消元運算的 Aug ( A )中的「額外行」，我們將其記做 c，此時原先的矩陣運算

「A x ＝ b 」

便能改寫為

「 U x ＝ c 」

並且這兩組矩陣方程式等價

看到這裡你可能會感到些許疑惑，憑什麼進行「列運算」後的矩陣方程式可以與消元前的矩陣方程式掛上等價？明明就是不同的矩陣組合啊！

沒錯，這是一個好問題，一個曾經困擾著數學系畢業的我 ( 教授上課沒認真聽，不要學 )三年的好問題，之所以拖三年是因為一方面是強者我朋友全都把線代還教授了，另一方面是就算不知道也不影響考試 ( 嘖嘖 )

但是現在你有充分的耐心看我的文章到現在，你便能無償得到這個問題的答案 ( 雖然只要你問 AI 的方式正確，也能得到更詳細的答案就是了 )

有些離題了，當我們將「 U x ＝ c 」還原成方程式時，便可得到下圖的聯立方程組

x＋2y＋z＝2 | 2y－2z＝6 | 5z＝－10

此時只要將未知數由 Z 至 X 依序解得即可得出

至此「高斯消元法」的完整流程便結束了，但是有個問題擺在我們面前

「要用什麼紀錄過程？」

總不能用文字敘述吧？那可太累人了，所以接著要說明如何使用矩陣運算進行消元過程，也就是能夠描述「基本列運算」的指令矩陣──「消元矩陣 ( Elimination matrix )」

在學習新知之前，我們可以先回顧一下上次上課的內容，在矩陣乘法中，我們將其視為一種「行線性組合( Linear combination of the column )」

[Column1 , Column2 , Column3][ x；y；z ] ＝ x (Column1) ＋ y (Column2) ＋ z (Column3)

在這個基礎上，通過改變矩陣相對的位置就能寫出「列線性組合( Linear combination of the row )」的規則了

[ x , y , z ][ Row1；Row2；Row3 ] ＝ x ( Row1) ＋ y ( Row2) ＋ z ( Row3)

而對於這兩種組合規則的靈活運用，亦是線性代數的核心邏輯之一，而我們對於 A 進行的消元法所得到的 U，便是對矩陣各列進行線性組合，所以我們要借助「列線性組合」完成消元矩陣」的建構

不知道這時你有沒有知識串起來的感覺，如果沒有，好好想想以下三個問題

現在如何理解矩陣乘法對於矩陣結構的再構成？
如何以此概念說明單位矩陣的構成？
結合上述問題，要怎麼用這個方式建構消元矩陣？

這裡留下我的想法給個索引，或許你的理解方式與我不同，如果是這樣，那可真是太好了！希望你能留下你的想法，那我們就開始吧！

首先可以注意到，當 A 乘上單行矩陣時，得出的矩陣大小與 A 的行向量相同，而單列矩陣乘上 A 時，得出的矩陣大小與 A 的列向量相同，也就是說如果我們要進行的是「列的線性組合」，則在 A 的前方乘上單列矩陣協助進行建構或許是一個好的開始

此時單列矩陣中的元便是線性組合的「乘數」，也能夠理解為一種運算指令，用以進行多列的線性組合建構 ( 如下 )

只看規則可能有些難理解，因此我們引入單位矩陣進行說明，單位矩陣 I 具有 A I = I A = A 的性質，如果我們使用「列線性組合」的角度來分析

有看出來具體的使用方法嗎？當我們將「組合指令」以「線性組合乘數」列出時，便能選定實際參與組合的列以及消元數，這一切只需要我們明白單位向量在線性組合上的應用便能進行推廣！不瞞各位讀者，當我第一次認識兩者的連接時我非常激動，太有趣了！太精簡了！順帶一提，這個知識也是我開始打這篇心得的原因

現在回到消元問題「A x ＝ b 」，我們需要對 A 進行消元運算，只是這次我們不再是使用口語或是記號表示「消元」指令，而是將其轉換成能夠實現等量公理的「消元矩陣」運算

( 1 , 2 )， t₁＝3
( 2 , 3 )， t₂＝2

首先定義「( 1 , 2 )， t₁＝3」，可以轉化為「消元矩陣 E₂₁」( 如下 )，這時的下標表示這個矩陣消除掉的「消元目標數」的位置

[ 1 , 0 , 0；－3 , 1 ,0；0 , 0 , 1 ]

使 A₁＝ ( E₂₁) A ，寫作

接著定義「( 2 , 3 )， t₂＝2 」，可以轉化為「消元矩陣 E₃₂」( 如下 )

[ 1 , 0 , 0；0 , 1 , 0；0 , －2 , 1 ]

使 U ＝ ( E₃₂) ( A₁)，寫作

若是將「消元過程」以矩陣乘法表示便可得出下式

( E₂₃) [ ( E₁₂) A ] ＝ U

且因矩陣乘法運算具有「乘法結合律 ( Associative law) 」，故可調整運算順序得出下式

[ ( E₂₃) ( E₁₂) ] A ＝ U

為了方便列式，我們會將 [ ( E₂₃) ( E₁₂) ] 這類型的「消元矩陣乘積」統一表示為

「初等 / 基本矩陣 ( Elementary matrix , E ) 」

需要留意的是，「初等矩陣」並不僅僅涵蓋「消元矩陣乘積」，而是所有「基本列運算」都能以「 E 」表示，只是我們大多用來描述「消元矩陣」，若是害怕自己閱讀時誤解，也可以將「 E 」進一步表示為「 E_total 」協助自己理解

至此，消元法至此結束了嗎？

很遺憾，並沒有，別忘了還有「列交換指令」需要處理，一樣的問題，我們不希望執行交換時需要用文字進行說明，並使推論過程滿足等量公理

有趣的問題出現了，所謂的「置換 ( Permutation ) 」是否跟「消元」一樣，使用矩陣表示指令呢？

當然可以！這個問題的答案是「置換矩陣 ( Permutation metrix , P ) 」，一種可以用來表示「行列交換」指令的矩陣，雖然這堂課不會說明 ( 你應該也要花不少時先消化內容吧？ )，不妨就把這個問題留在讀者身上吧！

小提示：回憶一下我們剛剛是如何建構「消元矩陣」的。

是通過「列線性組合」配合「單位矩陣」進行說明與生成對吧？現在我們不進行組合只進行交換，此時應該怎麼建構 P 呢？

可能有用的小知識：單位矩陣也是一種「置換矩陣」

在這堂課我們花了非常多心思在「消元」、「列交換」、「消元矩陣」、「置換矩陣」等等運算中，按照剛剛學習到的內容，只要能夠找到「 E 」使得「 E A ＝ U 」，並在原方程式「A x ＝ b 」左右同乘 E，便能得出「 U x ＝ c 」，再使用「 U 」進行回代就能得到方程組的解了

看似一切都塵埃落定了對嗎？數學老師這麼問的時候大抵都是不對的，就像明明離下課只剩三分鐘就硬要再講一題的「認真」老師一樣

( 你一定在想「馬的怎麼還有」，相信我，我也是這樣想的，快7000字了好累阿嗚嗚嗚 )

在執行「高斯消元法」的過程中，我們談論到了如何以「消元矩陣」表示「消元」過程，也就是「 A 變成 U 」的過程，而我們也能所有的方程組都能依此法得到解

但是有個小小小問題，這不是最有效的方式 ( ~~該死的效率主義~~ )

執行「高斯消元法」的過程中，數學家們最感興趣的地方並不是

「Ｅ」長什麼樣子？

而是

「如何將 U 如何變回 A 」

這部分的內容會需要先借助「逆反矩陣 ( Inverse metrix ) 」，而這個主題是下一個課程的核心，所以我們對於消元法的討論目前正處於一個未完待續的狀態

與上一次的心得一樣，教授用了剩餘的幾分鐘幫我們預習了下堂課的內容，所以就讓我們簡單認識「逆反矩陣」吧，如同字面意義一般，這個矩陣的功能白話來說就是「還原 / 退回上一步」，現在我們用一個簡單但不是那麼嚴謹地舉例

若 A B ＝ C 而 C D ＝ A，可視為「由 A 變 C 」使用 B 作為指令，由「 C 變 A 」使用 D 作為指令，則我們稱 B D 互為逆反矩陣，且 B D ＝D B ＝ I ，數學上會借助指數表示為「 D ＝B^－1」以及「 B ＝D^－1」

具體要如何操作？剛學到的「消元矩陣」恰好適合用來說明，看回剛剛的「 E₁₂」這個以矩陣形式表示的指令，若將該指令以文字敘述，則會是「將第一列的元乘上 ( －3 )，並按對應行加到第二列的對應元」

所以我們還原回去的指令應該要是「將第一列的元乘上 ( 3 )，並按對應行加到第二列的對應元」，所以生成出來的「初等矩陣」可以自然而然的表示為下方的矩陣

［1 , 0 , 0；3 , 1 , 0；0 , 0 , 1］

以上便是「逆反矩陣」的簡單說明，是不是有點感覺了呢？知道「逆反矩陣」的概念後應該能意識到，所謂的「將 U 變回 A 」實際上要找的過程便是「消元矩陣乘積」的「逆反矩陣」，可是憑什麼我們要對「逆反矩陣」更感興趣呢？那就是下堂課的核心問題了 ( 下課了！大家可以回家了 )

感謝你的觀看，希望我們能夠在下一篇的心得碰面 88