查看“︁数值线性代数”︁的源代码

{{NoteTA
|G1 = Math
}}

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

数值线性代数试图利用精度有限的计算机解决连续的数学问题，因此在[[自然科学]]和[[社会科学]]中的应用同连续数学一样广泛。这些问题包括[[图像处理]]、[[信号处理]]、[[金融工程学]]、[[材料科学]]模拟、[[结构生物学]]、[[数据挖掘]]、[[生物信息学]]、[[流体动力学]]和其他很多领域。矩阵方法尤其用于[[有限差分法]]、[[有限元法]]和[[微分方程]]建模。{{le|尼克·特雷費森|Nick Trefethen}}和大衛·鮑三世（David Bau III）注意到数值线性代数的广泛应用，认为它“同微积分和微分方程一样是数学科学的基础”，<ref name = "tb397">{{cite book | last1 = Trefethen | first1 = Lloyd | last2 = Bau III | first2 = David | location=Philadelphia | isbn=978-0-89871-361-9 | year = 1997 | title = Numerical Linear Algebra | url = https://archive.org/details/numericallineara0000tref | publisher = SIAM | edition =  1st}}</ref>{{rp|x}}尽管是个相对较小的领域。<ref name = "golubhist">{{cite web |url=https://www.stat.uchicago.edu/~lekheng/courses/302/slides0.pdf |title=A History of Modern Numerical Linear Algebra |last=Golub |first=Gene H. |website=University of Chicago Statistics Department |access-date=2019-02-17 |archive-date=2022-03-02 |archive-url=https://web.archive.org/web/20220302043828/https://www.stat.uchicago.edu/~lekheng/courses/302/slides0.pdf |dead-url=no }}</ref>由于矩阵和向量的很多性质也适用于函数和算子，因此数值线性代数也可视作[[泛函分析]]中注重实用算法的一支。<ref name=tb397/>{{rp|ix}}
数值线性代数中的常见问题如[[LU分解]]、[[QR分解]]、[[奇异值分解]]、[[特征分解]]等，然后可用于解答常见的线性代数问题，如求解线性方程组、定位特征值、最小二乘优化等。数值线性代数的核心问题是开发在有限精度计算机上应用真实数据时不会引入误差的算法，这通常通过[[迭代]]法来实现，而非直接方法。

==历史==
数值线性代数是由[[约翰·冯·诺伊曼]]、[[艾伦·图灵]]、[[詹姆斯·哈迪·威尔金森]]、[[阿爾斯通·斯科特·豪斯霍爾德]]、{{le|喬治·福賽思|George Forsythe}}、{{le|海因茨·魯蒂紹爾|Heinz Rutishauser}}等计算机先驱开发的，目的是将最早的计算机应用于连续数学问题，如弹道问题与[[偏微分方程]]求解。<ref name=golubhist/>约翰·冯·诺依曼和{{le|赫爾曼·戈德斯坦|Herman Goldstine}}在1947年的工作中，首次认真尝试将算法应用于真实数据计算时的误差降至最低。<ref>{{cite journal |last1=von Neumann|first1=John |last2=Goldstine |first2=Herman H. |date=1947 |title=Numerical inverting of matrices of high order |journal=Bulletin of the American Mathematical Society |volume=53 |issue=11 |pages=1021–1099 |doi=10.1090/s0002-9904-1947-08909-6|s2cid=16174165 |doi-access=free }}</ref>随着技术发展，研究者越来越有能力在超大型高精度矩阵解决复杂问题，这一领域也在不断壮大，而一些数值算法也因[[并行计算]]等技术，使其成为解决科学问题的使用方法而日益突出。<ref name=golubhist/>

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

<syntaxhighlight lang="matlab">
for q = 1:n
  for p = 1:m
    y(p) = A(p,q)*x(q) + y(p)
  end
end
</syntaxhighlight>

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

===QR分解===
{{Main|QR分解}}
矩阵<math>A^{m \times n}</math>的QR分解是<math>Q^{m \times m}</math>与<math>R^{m \times n}</math>，使得<math>A=QR</math>，其中''Q''是[[正交矩阵]]，''R''是上[[三角矩阵]]。<ref name=tb397/>{{rp|50}}<ref name = "gvl96">{{cite book | last1 = Golub | first1 = Gene H. | last2 = Van Loan | first2 = Charles F. | location=Baltimore | isbn=0-8018-5413-X | year = 1996 | title = Matrix Computations | publisher = The Johns Hopkins University Press | edition =  3rd}}</ref>{{rp|223}}计算QR分解的两种主要算法是[[格拉姆-施密特正交化]]与[[豪斯霍德变换]]。QR分解常用于解决{{le|线性最小二乘|Linear least squares}}问题与特征值问题（通过迭代{{le|QR算法|QR algorithm}}）。

===LU分解===
{{Main|LU分解}}
矩阵''A''的LU分解由下三角矩阵''L''和上三角矩阵''U''构成，使得<math>A=LU</math>。矩阵''U''通过上三角化过程生成，涉及将''A''左乘一系列矩阵<math>M_1,\ldots,M_{n-1}</math>，以形成积<math>M_{n-1} \cdots M_1 A = U</math>，因此等价地<math>L = M_1^{-1} \cdots M_{n-1}^{-1}</math>。<ref name=tb397/>{{rp|147}}<ref name=gvl96/>{{rp|96}}

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

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

===线性方程组的解===
{{Further|线性方程组#其他方法与软件}}
数值线性代数通常将矩阵视作列向量的组合。对于求解线性方程组<math>x = A^{-1}b</math>，传统代数方法是将''x''理解为<math>A^{-1}</math>与''b''的积。数值线性代数则将''x''理解为''b''在''A''的列形成的基上现行展开的系数向量。<ref name=tb397/>{{rp|8}}

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

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

==条件和稳定性==
{{Main|数值分析#數值穩定性及良置問題}}
假设问题是函数<math>f: X \to Y</math>，其中''X''是数据的赋范向量空间，''Y''是解的赋范向量空间。对于数据点<math>x \in X</math>，若''x''的微小扰动会导致<math>f(x)</math>的值发生很大变化，则称之为病态的（ill-conditioned）。可以定义[[条件数]]量化之，代表问题的完备程度：
<math display="block">\widehat{\kappa} = \lim_{\delta \to 0} \sup_{\| \delta x \| \leq \delta} \frac{\| \delta f \|}{\| \delta x \|}.</math>

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

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

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

==软件==
有几种编程语言用数值线性代数优化技术，旨在实现数值线性代数算法。有[[MATLAB]]、[[Analytica]]、[[Maple]]和[[Mathematica]]。其他语言也有提供数值线性代数例程与优化的库，如[[C语言]]及[[Fortran]]有[[BLAS]]、[[LAPACK]]等库，[[Python]]有[[NumPy]]，[[Perl]]有[[Perl Data Language]]。[[R语言]]中的很多数值线性代数命令依赖于LAPACK这些更基本的库。<ref>{{cite web |url=https://www.r-bloggers.com/r-and-linear-algebra/ |title=R and Linear Algebra |last=Rickert |first=Joseph |website=R-bloggers |date=2013-08-29 |access-date=2019-02-17 |archive-date=2019-02-18 |archive-url=https://web.archive.org/web/20190218082053/https://www.r-bloggers.com/r-and-linear-algebra/ |dead-url=no }}</ref>

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

== 参考文献 ==
{{Reflist|30em}}

== 阅读更多 ==
* {{cite book |first1=Jack |last1=Dongarra |author-link=Jack Dongarra |first2=Sven |last2=Hammarling |chapter=Evolution of Numerical Software for Dense Linear Algebra |pages=[https://archive.org/details/bwb_O9-ADH-036/page/297 297]–327 |title=Reliable Numerical Computation |url=https://archive.org/details/bwb_O9-ADH-036 |editor-first=M. G. |editor-last=Cox |editor2-first=S. |editor2-last=Hammarling |location=Oxford |publisher=Clarendon Press |year=1990 |isbn=0-19-853564-3 }}

*{{cite book |last=Leader |first=Jeffery J. | title=Numerical Analysis and Scientific Computation |url=https://archive.org/details/numericalanalysi0000lead |year=2004 |publisher=Addison Wesley |location= |isbn= 0-201-73499-0 }}
* {{Cite book | last1=Bau III | first1=David | last2=Trefethen | first2=Lloyd N. | author2-link=Lloyd Nicholas Trefethen | title=Numerical linear algebra | url=https://archive.org/details/numericallineara0000tref | publisher=Society for Industrial and Applied Mathematics | location=Philadelphia | isbn=978-0-89871-361-9 | year=1997 | postscript=<!--None-->}}
* [[詹姆斯·哈迪·威尔金森|J. H. Wilkinson]] and C. Reinsch, "Linear Algebra, volume II of Handbook for Automatic Computation" SIAM Review 14, 658 (1972).
* [[Gene H. Golub|Golub, Gene H.]]; [[Charles F. Van Loan|van Loan, Charles F.]] (1996), Matrix Computations, 3rd edition, Johns Hopkins University Press, ISBN 978-0-8018-5414-9
==外部链接==
{{Commonscat}}
*[http://www.netlib.org/utk/people/JackDongarra/la-sw.html Freely available software for numerical algebra on the web] {{Wayback|url=http://www.netlib.org/utk/people/JackDongarra/la-sw.html |date=20100830153338 }}, composed by Jack Dongarra and Hatem Ltaief, University of Tennessee
*[http://www.nag.co.uk/numeric/fl/nagdoc_fl24/html/F/fconts.html NAG Library of numerical linear algebra routines] {{Wayback|url=http://www.nag.co.uk/numeric/fl/nagdoc_fl24/html/F/fconts.html |date=20180511150015 }}
*{{twitter|nla_grp|Numerical Linear Algebra Group}} (Research group in the United Kingdom)
*{{twitter|siagla|siagla}} (Activity group about numerical linear algebra in the [[Society for Industrial and Applied Mathematics]])
*[https://gammanla.wordpress.com/ The GAMM Activity Group on Applied and Numerical Linear Algebra]

{{应用数学}}
{{线性代数的相关概念}}

[[Category:数值线性代数|*]]
[[Category:计算领域研究]]