別再算逆矩陣了

本文的閱讀等級:初級

不知道從甚麼時候開始,“三階逆矩陣公式”經常雄踞本站「近期最多人點閱」表單的榜首,每日點閱該文的次數少則幾十,多則上百,下圖是過去一年以來的瀏覽次數統計 (主要的峰值所在的日期大致與台灣高等院校春秋二季期中和期末考試相吻合)。對於所見的逆矩陣風潮,我感到相當困惑:究竟出於甚麼樣的動機眾多年輕讀者願意不辭勞苦求算 (三階) 逆矩陣?如果尋覓逆矩陣公式的行動單純源於人類天生想要探索未知世界的好奇心,那我沒甚麼意見。不過,倘若只因為要解線性方程而計算逆矩陣,我可就忍不住要奉勸諸位:「省點力氣,別再算逆矩陣了!」

3by3 inverse

「三階逆矩陣公式」的瀏覽次數統計圖 (按圖放大)

 
A 為一 n\times n 階可逆矩陣。給定一 n 維向量 \mathbf{b},線性方程 A\mathbf{x}=\mathbf{b} 有唯一解 \mathbf{x}=A^{-1}\mathbf{b}。既然如此,先求逆矩陣 A^{-1},再計算 A^{-1}\mathbf{b} 有何不妥?理論上,這沒甚麼不對。現今,高斯─約當法是人們最常採用的逆矩陣算法,想法是以基本列運算 (elementary row operation) 將增廣矩陣 \begin{bmatrix}  A\vert I  \end{bmatrix} 化簡至簡約列梯形式 (reduced row echelon form) \begin{bmatrix}  I\vert E  \end{bmatrix},其中 E 即為 A^{-1} (見“高斯─約當法”)。高斯─約當法所需的浮點乘法運算量 (以下簡稱計算量) 為 n^3[1],另加上矩陣向量乘法 A^{-1}\mathbf{b} 使用的 n^2 次運算,故 \mathbf{x}=A^{-1}\mathbf{b} 的總運算量是 n^3+n^2。表面上看,n\times n 階逆矩陣的計算量與二個 n\times n 階矩陣乘法的運算量相同,對此還有甚麼好苛求的呢?別忘了,我們的目的要得到線性方程的解,而不是逆矩陣的每一個元。欲解出 A\mathbf{x}=\mathbf{b},我們可以運用基本列運算將係數矩陣 A 化簡成上三角矩陣,稱為高斯消去法,並把運算過程與結果儲存成 LU 分解 PA=LU,其中 P 是一排列 (permutation) 矩陣,L 是一下三角矩陣,其主對角元皆為 1U 是一上三角矩陣 (見“PA=LU 分解”)。因為 A\mathbf{x}=\mathbf{b} 等價於 PA\mathbf{x}=LU\mathbf{x}=P\mathbf{b},故可切分為二,如下:

\displaystyle\begin{aligned}  L\mathbf{y}&=P\mathbf{b}\\  U\mathbf{x}&=\mathbf{y}.  \end{aligned}

上式中,P\mathbf{b} 僅置換 \mathbf{b} 的元,不涉及乘法運算。LU 分解耗費的運算量約為 \frac{1}{3}n^3 (見“LU 分解”)。由於 LU 同是三角矩陣,採用正向迭代算出 \mathbf{y} 和反向迭代算出 \mathbf{x} 的運算量皆為 \frac{1}{2}n^2。合計後,LU 分解法的計算量是 \frac{1}{3}n^3+n^2。直接解 A\mathbf{x}=\mathbf{b} 比算出 A^{-1}\mathbf{b} 耗用較少的計算量,這意味你將擁有更多的閒暇致力於創造生命價值,實現人生夢想。

 
高斯─約當法和 LU 分解法的計算量有相同的數量級 O(n^3),這恐怕仍無法說服大家放棄計算逆矩陣。考慮下例,假設我們要解 A^k\mathbf{x}=\mathbf{b},其中 k 是正整數。直接算出 C=A^k 需要 k-1n\times n 階矩陣乘法,共 (k-1)n^3 次運算,故 C^{-1} 消耗的運算量為 kn^3。若採用 LU 分解 PA=LU,則 PA^k\mathbf{x}=PA(A^{k-1}\mathbf{x})=LU(A^{k-1}\mathbf{x})=P\mathbf{b} 推得 A^{k-1}\mathbf{x}=\mathbf{z},其中 \mathbf{z}LU\mathbf{z}=P\mathbf{b} 的解。重複上述步驟,A^k\mathbf{x}=\mathbf{b} 可用下列遞迴算法解得:設初始向量 \mathbf{b}_0=\mathbf{b},對於 j=1,2,\ldots,k

\displaystyle\begin{aligned}  &\text{Solve~} L\mathbf{y}=P\mathbf{b}_{j-1}\\  &\text{Solve~} U\mathbf{x}=\mathbf{y}\\  &\mathbf{b}_j\leftarrow\mathbf{x}  \end{aligned}

計算終止時,\mathbf{x} 即為所求。LU 分解法使用的計算總量是 \frac{1}{3}n^3+kn^2。當 k 增大時,LU 分解比逆矩陣更具優勢,不過這個方法仍有改善空間 (見例二)。

 
如果逆矩陣出現在一般算式中,LU 分解法依然有效嗎?是的。下面舉二個例子展示逆矩陣的計算如何轉移成線性方程的求解問題。

例一:假設我們要計算 s=\mathbf{c}^TA^{-1}\mathbf{d}。先求 PA=LU,再依序解開 L\mathbf{y}=P\mathbf{d}U\mathbf{x}=\mathbf{y},所求即為 s=\mathbf{c}^T\mathbf{x}

例二:若 A 可對角化為 A=SDS^{-1},其中 D=\text{diag}(\lambda_1,\ldots,\lambda_n) 是特徵值矩陣,S 是特徵向量矩陣 (見“可對角化矩陣與缺陷矩陣的判定”),則冪矩陣為 A^k=SD^kS^{-1}。在不確知 S^{-1} 的情況下,如何計算 SD^kS^{-1}?運用一點矩陣代數技巧,將方程式轉置使 S^{-1} 位在左側,(A^k)^T=(S^T)^{-1}D^kS^T。設 B=D^kS^T,問題變成要解一個大線性方程 S^TX=B,其中 X^T=A^k 就是我們要的答案。解法如下:先計算 PS^T=LU,將 XB 分別以行向量 (column vector) 表示為 X=\begin{bmatrix}  \mathbf{x}_1&\cdots&\mathbf{x}_n  \end{bmatrix}B=\begin{bmatrix}  \mathbf{b}_1&\cdots&\mathbf{b}_n  \end{bmatrix},待解的 n 個線性方程為 LU\mathbf{x}_j=P\mathbf{b}_jj=1,\ldots,n。若不計 B=D^kS^T,LU 分解法的計算量 \frac{1}{3}n^3+n\cdot n^2=\frac{4}{3}n^3 略少於 B^TS^{-1} (含逆矩陣和矩陣乘法) 的計算量 n^3+n^3=2n^3

 
2005年,斯蒂夫•喬布斯 (Steve Jobs) 在美國史丹佛大學畢業典禮上說[2]:「你們的時間有限,所以不要浪費時間活在別人的生活裡。」我想說的則是:「你們的時間有限,所以不要浪費時間在逆矩陣的計算上。」

 
參考來源:
[1] Gilbert Strang, Linear Algebra and its Applications, 3rd edition, 1988, pp 45.
[2] 原文是 “Your time is limited, so don’t waste it living someone else’s life.”

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

9 則回應給 別再算逆矩陣了

  1. edge 說:

    做數值的都盡量避免遇到逆矩陣

  2. Watt Lin 說:

    假設有位老師,出很多Ax=b的題目給學生練習,學生發現連續幾題的A完全相同,只是b有變化。
    在這種情況,先求出A的逆矩陣,分別乘上不同的b,得到對應的x,計算量會不會比較少?
    兩題A相同,值得這樣作嗎?
    相同A,出現幾題以上?才會值得先求A的逆矩陣以減少計算量。
    (三階,以及四階、五階、更高階的情況,會是如何?)
    如果周教授您有空,可否對這想像的狀況,作個簡單說明?

    • ccjou 說:

      假設 A 是一 n\times n 階矩陣,問題要解 Ax=b_jj=1,\ldots,k,兩種方法的運算量如下:
      1) 逆矩陣:n^3+kn^2
      2) LU 分解:\frac{1}{3}n^3+kn^2
      主要的差別在於 A^{-1} 需要 n^3 次運算,LU 分解則需要 \frac{1}{3}n^3 次運算。

    • Watt Lin 說:

      第一次讀文章,沒看仔細,因而問了問題。
      老師的回答,點出重要觀念。
      我把整篇文章詳細再讀一遍,終於認清LU分解,比逆矩陣更具優勢。

      • suehang 說:

        其实逆矩阵这个东西实际上还是要站在逆映射的角度来看,而LU分解就是一种基于矩阵自身的某种经验技术.因此,LU分解当然威力就会强大(因为本来就是为矩阵量身定制的)

  3. ccjou 說:

    2005年,Steve Jobs在Stanford University畢業典禮的演講

    講稿全文:
    http://news.stanford.edu/news/2005/june15/jobs-061505.html

  4. michael 說:

    老师,您好。关于高斯约旦的计算量(乘法):
    第一轮取代 (2n)*(n-1+n-2+…+1)
    第二轮取代(反向) (2n)*(n-1+n-2+…+1)
    第三轮缩放 (2n)*n
    *2n包括A和I两个矩阵。
    算下来是2倍n的三次方。是不是哪里算错了?

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s