数值线性代数

数值线性代数（英語：numerical linear algebra），又稱應用線性代數（英語：applied linear algebra）是一门研究在计算机上进行线性代数计算，特别是矩阵运算算法的学科，是數值分析的一個分支。计算机用浮点数运算，无法精确表示无理数数据，因此计算机算法应用于数据矩阵时，有时会产生较大的误差。数值线性代数利用向量和矩阵的性质开发算法，以最大限度地减少这误差，同时还要确保算法尽可能高效。

数值线性代数试图利用精度有限的计算机解决连续的数学问题，因此在自然科学和社会科学中的应用同连续数学一样广泛。这些问题包括图像处理、信号处理、金融工程学、材料科学模拟、结构生物学、数据挖掘、生物信息学、流体动力学和其他很多领域。矩阵方法尤其用于有限差分法、有限元法和微分方程建模。Lloyd N. Trefethen和David Bau, III注意到数值线性代数的广泛应用，认为它“同微积分和微分方程一样是数学科学的基础”，^[1]^:{{{1}}}尽管是个相对较小的领域。^[2]由于矩阵和向量的很多性质也适用于函数和算子，因此数值线性代数也可视作泛函分析中注重实用算法的一支。^[1]^:{{{1}}} 数值线性代数中的常见问题如LU分解、QR分解、奇异值分解、特征分解等，然后可用于解答常见的线性代数问题，如求解线性方程组、定位特征值、最小二乘优化等。数值线性代数的核心问题是开发在有限精度计算机上应用真实数据时不会引入误差的算法，这通常通过迭代法来实现，而非直接方法。

历史

数值线性代数是由约翰·冯·诺伊曼、艾伦·图灵、詹姆斯·哈迪·威尔金森、Alston Scott Householder、George Forsythe、Heinz Rutishauser等计算机先驱开发的，目的是将最早的计算机应用于连续数学问题，如弹道问题与偏微分方程求解。^[2]约翰·冯·诺依曼和Herman Goldstine在1947年的工作中，首次认真尝试将算法应用于真实数据计算时的误差降至最低。^[3]随着技术发展，研究者越来越有能力在超大型高精度矩阵解决复杂问题，这一领域也在不断壮大，而一些数值算法也因并行计算等技术，使其成为解决科学问题的使用方法而日益突出。^[2]

矩阵分解

分割矩阵

对应用线性代数中的很多问题，将矩阵视作列向量的组合是很有用的。例如，求解线性系统 $x=A^{-1}b$ 时，与其将x理解为 $A^{-1}$ 与b的积，不如将x视作b在A的列形成的基上线性展开的系数向量。^[1]^:{{{1}}}将矩阵视作列之组合，也是矩阵算法的一种实用方法。这是因为矩阵算法常常包含两个嵌套的循环，一个是A的列循环，一个是A的行循环。例如，对于矩阵 $A^{m\times n}$ 和向量 $x^{n\times 1}$ 、 $y^{m\times 1}$ ，可以用列划分的方法计算 $y:=Ax+y$

for q = 1:n
  for p = 1:m
    y(p) = A(p,q)*x(q) + y(p)
  end
end

奇异值分解

矩阵 $A^{m\times n}$ 的奇异值分解是 $A=U\Sigma V^{\ast }$ ，其中U 、V是酉矩阵， $\Sigma$ 是对角矩阵。 $\Sigma$ 的对角项称作A的奇异值。由于奇异值是 $AA^{\ast }$ 特征值的平方根，所以奇异值分解同特征值分解有紧密联系。这意味着，计算奇异值分解的大多数方法都与特征值方法类似，^[1]^:{{{1}}}最常用的方法可能涉及豪斯霍德变换。^[1]^:{{{1}}}

QR分解

矩阵 $A^{m\times n}$ 的QR分解是 $Q^{m\times m}$ 与 $R^{m\times n}$ ，使得 $A=QR$ ，其中Q是正交矩阵，R是上三角矩阵。^[1]^:{{{1}}}^[4]^:{{{1}}}计算QR分解的两种主要算法是格拉姆-施密特正交化与豪斯霍德变换。QR分解常用于解决线性最小二乘问题与特征值问题（通过迭代QR算法）。

LU分解

矩阵A的LU分解由下三角矩阵L和上三角矩阵U构成，使得 $A=LU$ 。矩阵U通过上三角化过程生成，涉及将A左乘一系列矩阵 $M_{1},\ldots ,M_{n-1}$ ，以形成积 $M_{n-1}\cdots M_{1}A=U$ ，因此等价地 $L=M_{1}^{-1}\cdots M_{n-1}^{-1}$ 。^[1]^:{{{1}}}^[4]^:{{{1}}}

特征值分解

矩阵 $A^{m\times m}$ 的特征值分解是 $A=X\Lambda X^{-1}$ ，其中X的列是A的特征向量， $\Lambda$ 是对角矩阵，对角项是A的相应特征值。^[1]^:{{{1}}}目前还没有直接得到任意矩阵特征值分解的直接方法，因为程序不可能在有限时间内精确求得任意多项式的根，所以任何通用的特征值求解器必是迭代的。^[1]^:{{{1}}}

算法

高斯消元法

从数值线性代数的视角看，高斯消元法是将A进行LU分解的一种方法。高斯消元法通过将A与一系列矩阵 $L_{m-1}\cdots L_{2}L_{1}A=U$ 左乘来实现，直到U是上三角矩阵，L是下三角矩阵，且 $L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}$ 。^[1]^:{{{1}}}众所周知，高斯消元法极不稳定，用于有效数字较多的矩阵时误差巨大。^[2]最简单的解决方法是引入主元，从而得到更稳定的改进高斯消元法。^[1]^:{{{1}}}

线性方程组的解

数值线性代数通常将矩阵视作列向量的组合。对于求解线性方程组 $x=A^{-1}b$ ，传统代数方法是将x理解为 $A^{-1}$ 与b的积。数值线性代数则将x理解为b在A的列形成的基上现行展开的系数向量。^[1]^:{{{1}}}

格努矩阵A及向量x、b的特征，可以用很多不同的分解解决线性问题。若 $A=QR$ ，则等价于 $Rx=Q^{\ast }b$ 。这和矩阵分解一样容易计算。^[1]^:{{{1}}}将A进行特征分解： $A=X\Lambda X^{-1}$ ，并试图找到使 $b=Ax$ 的b，且 $b'=X^{-1}b,\ x'=X^{-1}x$ ，则有 $b'=\Lambda x'$ 。^[1]^:{{{1}}}这同使用奇异值分解求解线性系统密切相关，因为矩阵的奇异值是特征值的绝对值，也等价于格拉姆矩阵 $X^{*}X$ 特征值绝对值的平方根。将A进行LU分解得<matdh>A=LU</math>，则 $Ax=b$ 可用三角矩阵 $Ly=b,\ Ux=y$ 求解。^[1]^:{{{1}}}^[4]^:{{{1}}}

最小二乘优化

矩阵分解提出了许多解线性方程组 $r=b-Ax$ 的方法，其中我们寻求最小的r，如回归问题。QR算法计算A的既约QR分解并重排，得到 ${\widehat {R}}x={\widehat {Q}}^{\ast }b$ 。此上三角方程组可用于解x。SVD还提供了一种获得线性最小二乘的算法：计算既约SVD分解 $A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }$ ，并计算向量 ${\widehat {U}}^{\ast }b$ ，就可以将最小二乘问题简化为简单的对角方程组。^[1]^:{{{1}}}QR分解和SVD分解可以产生最小二乘解，这意味着除了用经典正规方程法解最小二乘问题外，还可用格拉姆-施密特法、豪斯霍德法等方法。

条件和稳定性

假设问题是函数 $f:X\to Y$ ，其中X是数据的赋范向量空间，Y是解的赋范向量空间。对于数据点 $x\in X$ ，若x的微小扰动会导致 $f(x)$ 的值发生很大变化，则称之为病态的（ill-conditioned）。我们可以通过定义条件数量化这一点，这代表了问题的完备成都： ${\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.$

不稳定性是指依赖浮点运算的计算机算法的结果与问题的精确解产生差距的趋势。矩阵包含多位有效数字的真实数据时，很多解线性方程组或最小二乘优化的算法可能会产生非常不准确的解。为病态问题创建稳定算法是数值线性代数的核心问题，例如豪斯霍德三角化是线性方程组的一种很稳健的解法，而解最小二乘法的正规方程法的不稳定性则是倾向于奇异值分解的一个原因。有些矩阵分解方法可能不稳定，但可以直接修改而变得稳定，例如格拉姆-施密特法可以很容易地改成改进格拉姆-施密特法。^[1]^:{{{1}}}另一个经典问题是，高斯消元法不稳定，引入主元后变得稳定。

迭代法

迭代法成为数值线性代数重要组成有两个原因。其一，很多重要的数值问题没有直接解，如求任意矩阵的特征值和特征向量。其二，对任意 $m\times m$ 矩阵的非迭代算法需要 $O(m^{3})$ 时间，而矩阵只含 $m^{2}$ 个数字，这个下限非常高。迭代法可利用矩阵的特点缩短时间。例如对稀疏矩阵，迭代算法可跳过很多直接方法必须的步骤，即便它们在矩阵高度结构化的情形下是多余的。

数值线性代数中，很多迭代法的核心是将矩阵投影到低维克雷洛夫子空间，这样就可从低维空间开始迭代计算类似矩阵的等效特征，依次向高维移动以逼近高维矩阵的特征。对对称的A，解线性方程 $Ax=b$ 时，经典迭代法是共轭梯度法。A若不对称，则迭代法有广义最小残量方法和CGN（正规方程共轭梯度法）。若A对称，则解特征值、特征向量问题时，可以用兰佐斯算法；A不对称时，可以用阿诺德迭代法。

软件

有几种编程语言用数值线性代数优化技术，旨在实现数值线性代数算法。有MATLAB、Analytica、Maple和Mathematica。其他语言也有提供数值线性代数例程与优化的库，如C语言及Fortran有BLAS、LAPACK等库，Python有NumPy，Perl有Perl Data Language。R语言中的很多数值线性代数命令依赖于LAPACK这些更基本的库。^[5]

参见

数值线性代数是数值分析的子领域。
高斯消去法，数值线性代数中一种重要的算法。
BLAS和LAPACK，高度优化的计算机程序库，以Fortran 程式語言寫成，可以实现数值线性代数中最基本的算法。
数值分析软件列表
数值程序库列表
高斯-賽德爾疊代
雅可比疊代

参考文献

^ ^1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 ^1.15 ^1.16 Trefethen, Lloyd; Bau III, David. Numerical Linear Algebra 1st. Philadelphia: SIAM. 1997. ISBN 978-0-89871-361-9.
^ ^2.0 ^2.1 ^2.2 ^2.3 Golub, Gene H. A History of Modern Numerical Linear Algebra (PDF). University of Chicago Statistics Department. [2019-02-17].
^ von Neumann, John; Goldstine, Herman H. Numerical inverting of matrices of high order. Bulletin of the American Mathematical Society. 1947, 53 (11): 1021–1099. S2CID 16174165. doi:10.1090/s0002-9904-1947-08909-6 .
^ ^4.0 ^4.1 ^4.2 Golub, Gene H.; Van Loan, Charles F. Matrix Computations 3rd. Baltimore: The Johns Hopkins University Press. 1996. ISBN 0-8018-5413-X.
^ Rickert, Joseph. R and Linear Algebra. R-bloggers. 2013-08-29 [2019-02-17].

外部链接

Freely available software for numerical algebra on the web （页面存档备份，存于互联网档案馆）, composed by Jack Dongarra and Hatem Ltaief, University of Tennessee
NAG Library of numerical linear algebra routines
Numerical Linear Algebra Group的X（前Twitter）帳戶 (Research group in the United Kingdom)
siagla的X（前Twitter）帳戶 (Activity group about numerical linear algebra in the Society for Industrial and Applied Mathematics)
The GAMM Activity Group on Applied and Numerical Linear Algebra

[tb397-1] 1.00 ^1.01 ^1.02 ^1.03 ^1.04 ^1.05 ^1.06 ^1.07 ^1.08 ^1.09 ^1.10 ^1.11 ^1.12 ^1.13 ^1.14 ^1.15 ^1.16 Trefethen, Lloyd; Bau III, David. Numerical Linear Algebra 1st. Philadelphia: SIAM. 1997. ISBN 978-0-89871-361-9.

[golubhist-2] 2.0 ^2.1 ^2.2 ^2.3 Golub, Gene H. A History of Modern Numerical Linear Algebra (PDF). University of Chicago Statistics Department. [2019-02-17].

[3] von Neumann, John; Goldstine, Herman H. Numerical inverting of matrices of high order. Bulletin of the American Mathematical Society. 1947, 53 (11): 1021–1099. S2CID 16174165. doi:10.1090/s0002-9904-1947-08909-6 .

[gvl96-4] 4.0 ^4.1 ^4.2 Golub, Gene H.; Van Loan, Charles F. Matrix Computations 3rd. Baltimore: The Johns Hopkins University Press. 1996. ISBN 0-8018-5413-X.

[5] Rickert, Joseph. R and Linear Algebra. R-bloggers. 2013-08-29 [2019-02-17].

[1]

[2]

[3]

[4]

[5]

查论编线性代数的相关概念
重要概念	标量向量向量空间向量子空间线性生成空间线性映射投影線性無關线性组合基標記列空间行空间零空间对偶空间正交特征值特征向量数量积内积空间点乘轉置格拉姆-施密特正交化线性方程组克萊姆法則
矩阵	矩阵矩陣乘法矩阵分解行列式子式和余子式矩阵的秩克萊姆法則逆矩阵高斯消去法线性变换分块矩阵
数值线性代数	浮点数数值稳定性基础线性代数程序集稀疏矩阵

历史