當前位置: 華文星空 > 知識

為什麽在套用上高斯消元法很少被用來求逆矩陣?

2021-06-20知識

「高斯消元法很少被用來求逆矩陣」這種說法是錯誤的。

維基上資料雖然品質不錯,但那說的是英文維基而不是中文維基。說這話的人的意思大概是:為了求解一個線性方程式組 Ax=b ,人們很少(也不推薦)先去算矩陣的逆 A^{-1} ,然後再用矩陣乘法計算 x=A^{-1}b 。

1、英文維基的介紹

為什麽說這種說法是錯的呢?在中文維基上,確實寫著「(在)套用上,高斯消元法極少被用來求出逆矩陣。高斯消元法通常只為線性方程式組求解」。但我們看一下英文維基是怎麽寫的:「This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix」。

當然這還沒涉及到「很少被用來」的問題。我們再看看專門介紹求矩陣逆的維基頁面:

第一個方法就是高斯消元法,第二個方法是與其性質不同的牛頓法(前者屬於直接法,後者屬於叠代法),後面還有一些其他方法,有些只適用於特殊情況,有些則只有理論價值還不會用於計算(比如使用克雷姆法則)。

2、標準庫是怎麽實作的

當然,光看這些百科介紹說服力還不強。下面我們就來看看最流行的數值計算軟體 Matlab 是用什麽演算法計算矩陣的逆的。

上面 Matlab 官方網站是這樣介紹矩陣求逆演算法 inv 的:

inv performs an LU decomposition of the input matrix (or an LDL decomposition if the input matrix is Hermitian). It then uses the results to form a linear system whose solution is the matrix inverse inv(X). For sparse inputs, inv(X) creates a sparse identity matrix and uses backslash, X\speye(size(X)).

也就是說,對於稠密矩陣矩陣來說,inv 函式使用的方法就是高斯消元法(其矩陣表示形式被稱為 LU 分解),對於稀疏矩陣來說,它則使用其他方法。

如果覺得 Matlab 還不夠高大上(Matlab 一般只用於快速實作想法,而不用於真正的工業級計算,因為它的效率非常低),那我們再參考一下計算數學的業界標準 Lapack(用 Fortran 語言實作的):

它的說明文件說寫道:

DGETRI computes the inverse of a matrix using the LU factorization
computed by DGETRF.

This method inverts U and then computes inv(A) by solving the system
inv(A)*L = inv(U) for inv(A).

這說明連業界標準 Lapack 都使用高斯消元法計算矩陣的逆。

連 Matlab 和 Fortran 的標準函式都使用高斯消元法,這是不是直接否定了中文維基上說的「高斯消元法很少被用來求逆矩陣」?

3、為什麽要避免不必要的求逆

那中文維基上說的這句話大概是什麽意思呢?其實就是在一般情況下,如果不是必須要求矩陣的逆,不要輕易去計算它。為什麽呢?因為你計算 Ax=b 只是用了一次高斯消元法,而在計算 AX=I 時卻用了 n 次高斯消元法(假設 A 為 n \times n 的矩陣, I 為 n \times n 的單位陣),因為你相當於對 I 的每一列都作了一次高斯消元法。所以如果你先求逆,再做乘法,那耗費的計算量是「 n 次高斯消元法外加一次乘法」,然而結果事實上還不如直接用一次高斯消元法去求解 Ax=B ,因為更長「路徑」的計算會造成舍入誤差的累積。因此,為了求解線性方程式組 Ax=B ,直接用高斯消元法是「多快好省」的辦法,而先求逆再做乘法,則是「傻大笨粗」的辦法。

這當然不意味著求逆在計算中就永遠沒有用,否則標準庫也不會提供相應的函式。假如我們要處理即時的數據 Ax=b_i , A 是一個 1000 \times 1000 的固定矩陣,但我們一天要處理好幾萬個 b_i ,那先算出來 A^{-1} 不是就很方便嗎?這會大大增加即時處理的速度。

所以使用什麽演算法最好,要根據情況實際分析。該算的必須算,不需要算的東西堅決不算。