高斯消去法與高斯─約當法的運算量

本文的閱讀等級:初級

高斯消去法 (Gaussian elimination) 是當今普遍用於解線性聯立方程組的演算法。高斯─約當法 (Gauss-Jordan method) 是高斯消去法的一種變形,主要應用於計算逆矩陣。關於這兩個算法的詳細介紹,請見“高斯消去法”和“高斯─約當法”,本文僅討論它們耗費的運算量。

 
高斯消去法

考慮求解線性聯立方程組:

\displaystyle \begin{array}{rrrrrrr} x_1 &\!\!\! - &\!\!\! x_2 &\!\!\! + &\!\!\! x_3 &\!\!\! = &\!\!\! -2 \\ 4x_1&\!\!\! -&\!\!\! 2x_2 &\!\!\! + &\!\!\! x_3 &\!\!\!  = &\!\!\! -1 \\ x_1 &\!\!\! - &\!\!\! 3x_2 &\!\!\! + &\!\!\! 2x_3 &\!\!\! = &\!\!\! -7. \end{array}

為便利計算,我們以增廣矩陣儲存線性方程組的係數與等號右邊的常數。高斯消去法包含兩個步驟:(1) 利用基本列運算 (elementary row operation) 消去增廣矩陣主對角線下的所有元使成為梯形矩陣 (係數矩陣部分變成上三角矩陣),(2) 運用反向代入法解出未知數 x_i。基本列運算的消去過程如下:

\displaystyle\begin{aligned} \left[\!\!\begin{array}{crrcr} 1 & -1 & 1 & \vline & -2 \\ 4 & -2 & 1 & \vline & -1\\ 1 & -3 & 2 & \vline & -7 \end{array}\!\!\right]&\to\left[\!\!\begin{array}{crrcr} 1 & -1 & 1 & \vline & -2 \\ 0 & 2 & -3 & \vline & 7\\ 1 & -3 & 2 & \vline & -7 \end{array}\!\!\right]\\ &\to\left[\!\!\begin{array}{crrcr} 1 & -1 & 1 & \vline & -2 \\ 0 & 2 & -3 & \vline & 7\\ 0 & -2 & 1 & \vline & -5 \end{array}\!\!\right]\\ &\to\left[\!\!\begin{array}{crrcr} 1 & -1 & 1 & \vline & -2 \\ 0 & 2 & -3 & \vline & 7\\ 0 & 0 & -2 & \vline & 2 \end{array}\!\!\right]\end{aligned}

梯形增廣矩陣對應下列等價線性方程組:

\displaystyle \begin{array}{rrrrrrr} x_1 &\!\!\! - &\!\!\! x_2 &\!\!\! + &\!\!\! x_3 &\!\!\! = &\!\!\! -2 \\ &\!\!\! &\!\!\! 2x_2 &\!\!\! - &\!\!\! 3x_3 &\!\!\!  = &\!\!\! 7 \\  &\!\!\!  &\!\!\!  &\!\!\!  &\!\!\! -2x_3 &\!\!\! = &\!\!\! 2. \end{array}

接著使用反向代入法依序解出未知數:

\displaystyle\begin{aligned} x_3&=\frac{2}{-2}=-1\\ x_2&=\frac{3x_3+7}{2}=2\\ x_1&=x_2-x_3-2=1. \end{aligned}

 
下面解析高斯消去法應用於解線性方程 A\mathbf{x}=\mathbf{b} 的運算需求,其中 A 為一 n\times n 階矩陣,\mathbf{b} 為一 n 維常數向量。

(1) 正向消去法化簡 n\times (n+1) 階增廣矩陣 [A\vert\mathbf{b}] 至梯形矩陣:以第一個軸元 (pivot),即 (1,1) 元,消去該元底下的 (2,1) 元必須先算出乘數 (上例為 4/1=4,使用一次除法),再計算第二列 (row),即更新後的 (2,j) 元,2\le j\le n+1,共有 n 次乘法與 n 次加法。以下稱每一次除法與乘法─加法對為一次運算,故第一個軸元使用了 n+1 次運算。消去第一個軸元底下的 n-1 個元總共耗用 (n-1)(n+1)=n^2-1 次運算。類似地,第二個軸元,即 (2,2) 元,使用了 (n-1)^2-1 次運算。餘此類推,消去法將 [A\vert\mathbf{b}] 化簡至梯形矩陣所使用的運算量為

\displaystyle\begin{aligned} (1^2+2^2+\cdots+n^2)-(1+1+\cdots+1)&=\frac{1}{6}n(n+1)(2n+1)-n\\ &=\frac{1}{3}n^3+\frac{1}{2}n^2-\frac{5}{6}n,\end{aligned}

其中消去係數矩陣 A 的運算量是 \frac{1}{3}(n^3-n),消去常數向量 \mathbf{b} 的運算量是 \frac{1}{2}(n^2-n)。當 n 很大時,消去係數矩陣的運算量近似於 \frac{1}{3}n^3,消去常數向量的運算量近似於 \frac{1}{2}n^2

(2) 反向代入法解出未知向量 \mathbf{x}=(x_1,\ldots,x_n)^T:第一個未知數 x_n 需要一次運算,第二個未知數 x_{n-1} 使用二次運算,故可歸納運算量為

\displaystyle 1+2+\cdots+n=\frac{1}{2}n^2+\frac{1}{2}n

合併上面兩個步驟,當 n 很大時,應用高斯消去法於解 n 階線性系統的總運算量約為 \frac{1}{3}n^3 (不計兩個 \frac{1}{2}n^2)。

 
高斯─約當法

沿用上例說明,我們要計算

\displaystyle A=\left[\!\!\begin{array}{crc} 1 & -1 & 1 \\ 4 & -2 & 1 \\ 1 & -3 & 2  \end{array}\!\!\right]

的逆矩陣,也就是解出 AX=I,其中 I 是單位矩陣,X=A^{-1}。高斯─約當法將增廣矩陣 [A\vert I] 化約至 [I\vert E],其中 E 即為 A^{-1},過程如下:

\displaystyle\begin{aligned} \left[\!\!\begin{array}{crccccc} 1 & -1 & 1 &\vline&1&0&0\\ 4 & -2 & 1 &\vline&0&1&0\\ 1 & -3 & 2 &\vline&0&0&1 \end{array}\!\!\right]&\to\left[\!\!\begin{array}{crrcrcc} 1 & -1 & 1 &\vline&1&0&0\\ 0 & 2 & -3 &\vline&-4&1&0\\ 0 & -2 & 1 &\vline&-1&0&1 \end{array}\!\!\right]\\ &\to\left[\!\!\begin{array}{crrcrcc} 1 & -1 & 1 &\vline&1&0&0\\ 0 & 2 & -3 &\vline&-4&1&0\\ 0 & 0 & -2 &\vline&-5&1&1 \end{array}\!\!\right]\\ &\to\left[\!\!\begin{array}{crrcrrr} 1 & -1 & 0 &\vline&-\frac{3}{2}&\frac{1}{2}&\frac{1}{2}\\[0.3em] 0 & 2 & 0 &\vline&\frac{7}{2}&-\frac{1}{2}&-\frac{3}{2}\\[0.1em] 0 & 0 & -2 &\vline&-5&1&1 \end{array}\!\!\right]\\ &\to\left[\!\!\begin{array}{ccrcrrr} 1 & 0 & 0 &\vline&\frac{1}{4}&\frac{1}{4}&-\frac{1}{4}\\[0.3em] 0 & 2 & 0 &\vline&\frac{7}{2}&-\frac{1}{2}&-\frac{3}{2}\\[0.1em] 0 & 0 & -2 &\vline&-5&1&1 \end{array}\!\!\right]\\ &\to\left[\!\!\begin{array}{ccccrrr} 1 & 0 & 0 &\vline&\frac{1}{4}&\frac{1}{4}&-\frac{1}{4}\\[0.3em] 0 & 1 & 0 &\vline&\frac{7}{4}&-\frac{1}{4}&-\frac{3}{4}\\[0.3em] 0 & 0 & 1 &\vline&\frac{5}{2}&-\frac{1}{2}&-\frac{1}{2} \end{array}\!\!\right]\\ \end{aligned}

高斯─約當法的正向消去步驟與高斯消去法相同,目標是化簡係數矩陣 A 使成為上三角矩陣:

\displaystyle \left[\!\!\begin{array}{crccccc} 1 & -1 & 1 &\vline&1&0&0\\ 4 & -2 & 1 &\vline&0&1&0\\ 1 & -3 & 2 &\vline&0&0&1 \end{array}\!\!\right]\to\left[\!\!\begin{array}{crrcrcc} 1 & -1 & 1 &\vline&1&0&0\\ 0 & 2 & -3 &\vline&-4&1&0\\ 0 & 0 & -2 &\vline&-5&1&1 \end{array}\!\!\right]

 
對於 n\times n 階矩陣 AAX=I 可表示為 A\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_n \end{bmatrix}=\begin{bmatrix} \mathbf{e}_1&\cdots&\mathbf{e}_n \end{bmatrix},或分解成 n 個線性方程 A\mathbf{x}_j=\mathbf{e}_jj=1,\ldots,n,其中 \mathbf{e}_j 是第 jn 維標準單位向量 (第 j 元為 1,其餘元為 0)。以下假設 n 的數值很大。若以高斯消去法解 A\mathbf{x}_j=\mathbf{e}_jj=1,\ldots,n,則消去係數矩陣 A 使用 \frac{1}{3}n^3 次運算,消去 n 個常數向量 \mathbf{e}_1,\ldots,\mathbf{e}_n 使用 n(\frac{1}{2}n^2)=\frac{1}{2}n^3 次運算,反向代入解出 n 個未知向量 \mathbf{x}_1,\ldots,\mathbf{x}_n 使用 n(\frac{1}{2}n^2)=\frac{1}{2}n^3 次運算,故總量為 \frac{4}{3}n^3

 
不過,上述運算量略為高估,原因是標準單位向量 \mathbf{e}_j 具有特殊形式。值得注意的是,正向消去僅改變常數向量 \mathbf{e}_j 的底下 n-j 個元,其餘元維持不變,故運算量為 \frac{1}{2}(n-j)^2-\frac{1}{2}(n-j)\approx\frac{1}{2}(n-j)^2。因此,消去所有常數向量 \mathbf{e}_1,\ldots,\mathbf{e}_n 所需的運算量為

\displaystyle \sum_{j=1}^n\frac{1}{2}(n-j)^2=\frac{1}{2}\sum_{k=1}^{n-1}k^2\approx\frac{1}{6}n^3

再加上消去係數矩陣 A 的運算量 \frac{1}{3}n^3,以及反向代入法解出 n 個未知向量的運算量 \frac{1}{2}n^3,計算逆矩陣實際耗用的總運算量是

\displaystyle \frac{1}{6}n^3+\frac{1}{3}n^3+\frac{1}{2}n^3=n^3

這個結果可能讓許多讀者感到驚訝:當 n 很大時,運用高斯─約當法計算 n\times n 階逆矩陣的運算量等於兩個 n\times n 階矩陣乘法的運算量,也就是說,計算 A^{-1}A^2 使用相同的運算量。

相關閱讀:
This entry was posted in 線性代數專欄, 數值線性代數 and tagged , , . Bookmark the permalink.

2 則回應給 高斯消去法與高斯─約當法的運算量

  1. Meiyue Shao 說:

    “以下稱每一次除法與乘法─加法對為一次運算”——这个假设和通常的习惯(不论加减乘除,一步四则运算算做一次运算,flops都是按此依据计算的)不符,最好高亮显示,否则埋在段落中间容易忽略,这样一眼看去结论就差了两倍。
    当然我强烈建议不要采用和常用的惯例不一致的假设,尽管哪一个都不比另一个更合理。

    • ccjou 說:

      我了解你的意思。慣例隨時間改變,上文指稱的一次運算flop是早期的定義。我在EECS當研究生時,所有的老師都是這麼算的。

      下文節錄自Golub&Van Loan的Matrix Computations, 2nd edition, 1989, pp19:

      In the first edition of this book we defined a flop to be the amount of work associated with an operation of the form a_{ij}=a_{ij}+a_{ik}a_{kj}, i.e., a floating point add, a floating point multiply, and some subscripting. Thus, an “old flop" involves two “new flops." In defining a flop to be a single floating point operation we are opting for a more precise measure of arithmetic complexity. Moreover, new flops have replaced old flops in the supercomputing field to the delight of the manufacturers whose machines suddenly doubled in speed with the new technology! After some agonizing, we have decided to go along with the change.

      我很樂意採用新的定義,只是苦惱還要花時間修訂。

發表迴響

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

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s