当前位置: 华文星空 > 知识

为什么在应用上高斯消元法很少被用来求逆矩阵?

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} 不是就很方便吗?这会大大增加实时处理的速度。

所以使用什么算法最好,要根据情况实际分析。该算的必须算,不需要算的东西坚决不算。