高斯─約當法

本文的閱讀等級:初級

在解線性方程組的應用上,高斯─約當法[1] (Gauss-Jordan method) 是高斯消去法的延伸 (見“高斯消去法”),其目的要得到最簡約的列等價方程組。高斯消去法產生梯形矩陣後,我們可以繼續執行取代運算將軸元 (pivot) 上方的元悉數消去,並使用伸縮運算迫使軸元為 1。高斯─約當法產生的矩陣稱為簡約列梯形式 (reduced row echelon form),由下列四個條件定義 (前兩個條件即為梯形矩陣的性質):

  1. 零列置於矩陣最底下。
  2. 每列軸元的位置都位於其上方各列軸元的右側。
  3. 軸元等於 1
  4. 軸元其上方與下方的元皆為零。

下面列舉兩個簡約列梯形式。數字 1 表示軸元,每一軸元上方和下方的元皆為零,其他各元 (以 \square 表示) 可以是任意數:

\left[\!\begin{array}{ccccc}  1 & \square & 0 & 0 & \square \\  0 & 0 & 1 & 0 & \square \\  0 & 0 & 0 & 1 & \square \\  0 & 0 & 0 & 0 & 0  \end{array}\!\right],~~  \left[\!\begin{array}{ccccccc}  0 & 1 & 0 & \square & 0 & 0 & \square \\  0 & 0 & 1 & \square & 0 & 0 & \square \\  0 & 0 & 0 & 0 & 1 & 0 & \square \\  0 & 0 & 0 & 0 & 0 & 1 & \square  \end{array}\!\right]

Carl Friedrich Gauss (1777-1855) From Wikimedia

 
我們用一個例子說明高斯─約當法的計算過程。先使用高斯消去法將給定的增廣矩陣 (代表線性方程組) 化簡至梯形矩陣 (運算細節省略):

\left[\!\begin{array}{rrrrcr}  0 & 2 & -4 & 1 &\vline& -6 \\  -1 & 0 & -5 & 1 &\vline& -4 \\  1 & 2 & 1 & 0 &\vline& -2 \\  2 & -4 & 18 & -7 &\vline& 14  \end{array}\!\right]\to\left[\!\!\begin{array}{rrrrcr}  -1 & 0 & -5 & 1 &\vline& -4 \\  0 & 2 & -4 & 1 &\vline& -6 \\  0 & 0 & 0 & -3 &\vline& -6 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\!\right]

接著繼續對梯形矩陣執行基本列運算。以伸縮運算使最底下的軸元為 1,再消去該軸元以上的所有元,沿用此方式由下而上直到產生簡約列梯形式,如下:

\begin{array}{llll}  &\left[\!\begin{array}{rrrrcr}  -1 & 0 & -5 & 1 &\vline& -4 \\  0 & 2 & -4 & 1 &\vline& -6 \\  0 & 0 & 0 & -3 &\vline& -6 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\right]&\rightarrow &  \left[\!\begin{array}{rrrrcr}  -1 & 0 & -5 & 1 &\vline& -4 \\  0 & 2 & -4 & 1 &\vline& -6 \\  0 & 0 & 0 & 1 &\vline& 2 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\right] \\  &&\\  \rightarrow  &\left[\!\begin{array}{rrrrcr}  -1 & 0 & -5 & 1 &\vline& -4 \\  0 & 2 & -4 & 0 &\vline& -8 \\  0 & 0 & 0 & 1 &\vline& 2 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\right]&\rightarrow &  \left[\!\begin{array}{rrrrcr}  -1 & 0 & -5 & 0 &\vline& -6 \\  0 & 2 & -4 & 0 &\vline& -8 \\  0 & 0 & 0 & 1 &\vline& 2 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\right] \\  &&\\  \rightarrow  &\left[\!\begin{array}{rrrrcr}  -1 & 0 & -5 & 0 &\vline& -6 \\  0 & 1 & -2 & 0 &\vline& -4 \\  0 & 0 & 0 & 1 &\vline& 2 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\right]&\rightarrow &  \left[\!\begin{array}{ccrccr}  1 & 0 & 5 & 0 &\vline& 6 \\  0 & 1 & -2 & 0 &\vline& -4 \\  0 & 0 & 0 & 1 &\vline& 2 \\  0 & 0 & 0 & 0 &\vline& 0  \end{array}\!\right]  \end{array}

 
與高斯消去法得到的梯形矩陣比較,簡約列梯形式的主要價值在於不需要使用反向代入法,當下便可決定線性方程組的解。上例中,從簡約列梯形式具有完整的零列可斷定此方程組是一致的,第一、二、四行為軸行,故 x_1, x_2, x_4 是軸變數,x_3 是自由變數。寫出對應簡約列梯形式的線性方程組

\begin{aligned}  x_1+5x_3&=6\\  x_2-2x_3&=-4\\  x_4&=2.  \end{aligned}

x_3=\alpha,移項後立刻得到通解

\begin{aligned}  x_1&=-5\alpha+6\\  x_2&=2\alpha-4\\  x_3&=\alpha\\  x_4&=2.  \end{aligned}

 
對於任意給定矩陣,雖然存在許多不同的列等價梯形矩陣,但是萬法歸一,不論基本列運算的執行方式或次序為何,簡約列梯形式總是唯一的,這是因為簡約列梯形式與方程組的解具有一對一的關係 (證明見“簡約列梯形式的唯一性”)。就這層意義來說,列等價的簡約列梯形式是一種典型的矩陣形式。提醒讀者,如果我們的問題僅須解線性方程組,在一般情況下,使用高斯消去法再以反向代入求解的計算效率略優於高斯—約當法直接得到簡約列梯形式。雖然如此,高斯—約當法自有一個特別的應用──計算一個 n 階方陣的逆矩陣。

 
A=[a_{ij}]n\times n 階矩陣,b=[b_i]n 維向量,寫出增廣矩陣

\begin{bmatrix}  A\vert\mathbf{b}  \end{bmatrix}=\left[\!\!\begin{array}{cccccc}  a_{11}&a_{12}&\cdots&a_{1n}&\vline&b_1\\  a_{21}&a_{22}&\cdots&a_{2n}&\vline&b_2\\  \vdots&\vdots&\ddots&\vdots&\vline&\vdots\\  a_{n1}&a_{n2}&\cdots&a_{nn}&\vline&b_n  \end{array}\!\!\right]

A 是可逆的,則 A\mathbf{x}=\mathbf{b} 恆有唯一解,基本列運算最終可將增廣矩陣化簡為

\begin{bmatrix}  I\vert\mathbf{c}  \end{bmatrix}=\left[\!\!\begin{array}{cccccc}  1&0&\cdots&0&\vline&c_1\\  0&1&\cdots&0&\vline&c_2\\  \vdots&\vdots&\ddots&\vdots&\vline&\vdots\\  0&0&\cdots&1&\vline&c_n  \end{array}\!\!\right]

線性方程組 A\mathbf{x}=\mathbf{b} 的解即為最右行,x_i=c_ii=1,\ldots,n。若 A 的簡約列梯形式不等於單位矩陣 I,便可判定 A 是不可逆的。令 Xn\times n 階矩陣使得 AX=I,也就是說,XA 的逆矩陣 A^{-1}。將 XI 以行向量表示:X=\begin{bmatrix}  \mathbf{x}_1&\cdots&\mathbf{x}_n  \end{bmatrix}I=\begin{bmatrix}  \mathbf{e}_1&\cdots&\mathbf{e}_n  \end{bmatrix},其中 \mathbf{e}_i 代表第 i 元等於 1 的單位向量,則有

AX=A\begin{bmatrix}  \mathbf{x}_1&\cdots&\mathbf{x}_n  \end{bmatrix}=\begin{bmatrix}  A\mathbf{x}_1&\cdots&A\mathbf{x}_n  \end{bmatrix}=\begin{bmatrix}  \mathbf{e}_1&\cdots&\mathbf{e}_n  \end{bmatrix}=I

因此,矩陣方程 AX=I 可分解成 n 個線性方程 A\mathbf{x}_1=\mathbf{e}_1,\ldots,A\mathbf{x}_n=\mathbf{e}_n。分別對 n 個增廣矩陣 \begin{bmatrix}  A\vert\mathbf{e}_1  \end{bmatrix},\ldots,\begin{bmatrix}  A\vert\mathbf{e}_n  \end{bmatrix} 執行高斯─約當法,可得

\begin{aligned}  \begin{bmatrix}  A\vert\mathbf{e}_1  \end{bmatrix}&\xrightarrow[]{~~\mathrm{Gauss-Jordan}~~}\begin{bmatrix}  I\vert\mathbf{x}_1  \end{bmatrix}\\  &\vdots\\  \begin{bmatrix}  A\vert\mathbf{e}_n  \end{bmatrix}&\xrightarrow[]{~~\mathrm{Gauss-Jordan}~~}\begin{bmatrix}  I\vert\mathbf{x}_n  \end{bmatrix}.\end{aligned}

但因為這 n 個增廣矩陣 \begin{bmatrix}  A\vert\mathbf{e}_1  \end{bmatrix},\ldots,\begin{bmatrix}  A\vert\mathbf{e}_n  \end{bmatrix} 擁有相同的係數矩陣 A,我們可以將它們合併成一個大增廣矩陣 \begin{bmatrix}  A\!\!&\vert&\!\! I  \end{bmatrix}。直接以高斯─約當法化簡大增廣矩陣,即得

\begin{bmatrix}  A\!\!&\vert&\!\! I  \end{bmatrix}\xrightarrow[]{~~\mathrm{Gauss-Jordan}~~}\begin{bmatrix}  I\!\!&\vert&\!\! X  \end{bmatrix}

 
最後舉一例展示高斯—約當法於計算逆矩陣的應用。考慮

A=\left[\!\!\begin{array}{ccc}  1&1&0\\  2&3&3\\  2&2&1  \end{array}\!\!\right]

高斯─約當法計算逆矩陣 A^{-1} 的過程如下:

\begin{array}{rlll}  \begin{bmatrix}  A\!\!&\vert&\!\! I  \end{bmatrix}=&\left[\!\!\begin{array}{rrrcrrr}  1 & 1 & 0 &\vline& 1 &0& 0 \\  2 & 3 & 3 &\vline& 0 &1& 0 \\  2 & 2 & 1 &\vline& 0 &0& 1  \end{array}\!\!\right]&\rightarrow &  \left[\!\begin{array}{rrrcrrr}  1 & 1 & 0 &\vline& 1 &0& 0 \\  0 & 1 & 3 &\vline& -2 &1& 0 \\  0 & 0 & 1 &\vline& -2 &0& 1  \end{array}\!\right] \\  &&&\\  \rightarrow  &\left[\!\begin{array}{rrrcrrr}  1 & 1 & 0 &\vline& 1 &0& 0 \\  0 & 1 & 0 &\vline& 4 &1& -3 \\  0 & 0 & 1 &\vline& -2 &0& 1  \end{array}\!\right]&\rightarrow &  \left[\!\begin{array}{rrrcrrr}  1 & 0 & 0 &\vline& -3 &-1& 3 \\  0 & 1 & 0 &\vline& 4 &1& -3 \\  0 & 0 & 1 &\vline& -2 &0& 1  \end{array}\!\right]\end{array}

從最後一個矩陣可以判斷 A 是可逆的,

A^{-1}=\left[\!\!\begin{array}{rrr}  -3&-1&3\\  4&1&-3\\  -2&0&1  \end{array}\!\!\right]

 
註解
[1] 高斯─約當法的約當常被人誤認為是法國數學家 Marie Ennemond Camille Jordan (1838-1922),矩陣分析理論中 Jordan 典型形式即因他而名。事實上,高斯─約當法是由德國測地學家 Wihelm Jordan (1842-1899) 於公元1888年提出。

Advertisements
本篇發表於 線性方程, 線性代數專欄 並標籤為 , , , , 。將永久鏈結加入書籤。

4 則回應給 高斯─約當法

  1. 老羅 說道:

    增廣矩陣,
    \begin{bmatrix} 0 & 2 & -4 & 1 & -6 \\   -1& 0 & -5 & 1  & -4 \\  1 & 2 &1  & 0 &-2 \\  2 & -4 & 18 & 7 & 14 \end{bmatrix}
    高斯消去法後的梯型矩陣是,
    \begin{bmatrix} -1 & 0 & -5 & 1 & -4 \\  0 & 2 & -4 & 1 & -6 \\   0& 0 & 0 & 11 & -6 \\   0& 0 & 0 & 0 & 0 \end{bmatrix}

    \begin{bmatrix} 0 & 2 & -4 & 1 & -6 \\   -1& 0 & -5 & 1  & -4 \\  1 & 2 &1  & 0 &-2 \\  2 & -4 & 18 & -7 & 14 \end{bmatrix}
    的高斯消去法才是文中的梯形矩陣

  2. Yufeng 說道:

    周老師,有個小錯誤,“但因為這 n 個增廣矩陣 \begin{bmatrix}  A\vert\mathbf{e}_1  \end{bmatrix},\ldots,\begin{bmatrix}  A\vert\mathbf{e}_3  \end{bmatrix}”, 最後一個下標應為 n

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s