數值線性代數

數值線性代數（英語：numerical linear algebra），又稱應用線性代數（英語：applied linear algebra）是一門研究在計算機上進行線性代數計算，特別是矩陣運算算法的學科，是數值分析的一個分支。計算機用浮點數運算，無法精確表示無理數數據，因此計算機算法應用於數據矩陣時，有時會產生較大的誤差。數值線性代數利用向量和矩陣的性質開發算法，以最大限度地減少這誤差，同時還要確保算法儘可能高效。

數值線性代數試圖利用精度有限的計算機解決連續的數學問題，因此在自然科學和社會科學中的應用同連續數學一樣廣泛。這些問題包括圖像處理、信號處理、金融工程學、材料科學模擬、結構生物學、數據挖掘、生物信息學、流體動力學和其他很多領域。矩陣方法尤其用於有限差分法、有限元法和微分方程建模。尼克·特雷費森（英語：Nick Trefethen）和大衛·鮑三世（David Bau III）注意到數值線性代數的廣泛應用，認為它「同微積分和微分方程一樣是數學科學的基礎」，^[1]:x儘管是個相對較小的領域。^[2]由於矩陣和向量的很多性質也適用於函數和算子，因此數值線性代數也可視作泛函分析中注重實用算法的一支。^[1]:ix 數值線性代數中的常見問題如LU分解、QR分解、奇異值分解、特徵分解等，然後可用於解答常見的線性代數問題，如求解線性方程組、定位特徵值、最小二乘優化等。數值線性代數的核心問題是開發在有限精度計算機上應用真實數據時不會引入誤差的算法，這通常通過迭代法來實現，而非直接方法。

歷史

數值線性代數是由約翰·馮·諾伊曼、艾倫·圖靈、詹姆斯·哈迪·威爾金森、阿爾斯通·斯科特·豪斯霍爾德、喬治·福賽思（英語：George Forsythe）、海因茨·魯蒂紹爾（英語：Heinz Rutishauser）等計算機先驅開發的，目的是將最早的計算機應用於連續數學問題，如彈道問題與偏微分方程求解。^[2]約翰·馮·諾依曼和赫爾曼·戈德斯坦（英語：Herman Goldstine）在1947年的工作中，首次認真嘗試將算法應用於真實數據計算時的誤差降至最低。^[3]隨着技術發展，研究者越來越有能力在超大型高精度矩陣解決複雜問題，這一領域也在不斷壯大，而一些數值算法也因並行計算等技術，使其成為解決科學問題的使用方法而日益突出。^[2]

矩陣分解

更多資訊：矩陣分解

分割矩陣

主條目：分塊矩陣

對應用線性代數中的很多問題，將矩陣視作列向量的組合是很有用的。例如，求解線性系統${\displaystyle x=A^{-1}b}$時，與其將x理解為${\displaystyle A^{-1}}$與b的積，不如將x視作b在A的列形成的基上線性展開的係數向量。^[1]:8將矩陣視作列之組合，也是矩陣算法的一種實用方法。這是因為矩陣算法常常包含兩個嵌套的循環，一個是A的列循環，一個是A的行循環。例如，對於矩陣${\displaystyle A^{m\times n}}$和向量${\displaystyle x^{n\times 1}}$、${\displaystyle y^{m\times 1}}$，可以用列劃分的方法計算${\displaystyle y:=Ax+y}$

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

奇異值分解

主條目：奇異值分解

矩陣${\displaystyle A^{m\times n}}$的奇異值分解是${\displaystyle A=U\Sigma V^{\ast }}$，其中U 、V是酉矩陣，${\displaystyle \Sigma }$是對角矩陣。${\displaystyle \Sigma }$的對角項稱作A的奇異值。由於奇異值是${\displaystyle AA^{\ast }}$特徵值的平方根，所以奇異值分解同特徵值分解有緊密聯繫。這意味着，計算奇異值分解的大多數方法都與特徵值方法類似，^[1]:36最常用的方法可能涉及豪斯霍德變換。^[1]:253

QR分解

主條目：QR分解

矩陣${\displaystyle A^{m\times n}}$的QR分解是${\displaystyle Q^{m\times m}}$與${\displaystyle R^{m\times n}}$，使得${\displaystyle A=QR}$，其中Q是正交矩陣，R是上三角矩陣。^{[1]:50[4]:223}計算QR分解的兩種主要算法是格拉姆-施密特正交化與豪斯霍德變換。QR分解常用於解決線性最小二乘問題與特徵值問題（通過迭代QR算法）。

LU分解

主條目：LU分解

矩陣A的LU分解由下三角矩陣L和上三角矩陣U構成，使得${\displaystyle A=LU}$。矩陣U通過上三角化過程生成，涉及將A左乘一系列矩陣${\displaystyle M_{1},\ldots ,M_{n-1}}$，以形成積${\displaystyle M_{n-1}\cdots M_{1}A=U}$，因此等價地${\displaystyle L=M_{1}^{-1}\cdots M_{n-1}^{-1}}$。^{[1]:147[4]:96}

特徵值分解

主條目：特徵值分解

矩陣${\displaystyle A^{m\times m}}$的特徵值分解是${\displaystyle A=X\Lambda X^{-1}}$，其中X的列是A的特徵向量，${\displaystyle \Lambda }$是對角矩陣，對角項是A的相應特徵值。^[1]:33目前還沒有直接得到任意矩陣特徵值分解的直接方法，因為程序不可能在有限時間內精確求得任意多項式的根，所以任何通用的特徵值求解器必是迭代的。^[1]:192

算法

高斯消元法

主條目：高斯消元法

從數值線性代數的視角看，高斯消元法是將A進行LU分解的一種方法。高斯消元法通過將A與一系列矩陣${\displaystyle L_{m-1}\cdots L_{2}L_{1}A=U}$左乘來實現，直到U是上三角矩陣，L是下三角矩陣，且${\displaystyle L\equiv L_{1}^{-1}L_{2}^{-1}\cdots L_{m-1}^{-1}}$。^[1]:148眾所周知，高斯消元法極不穩定，用於有效數字較多的矩陣時誤差巨大。^[2]最簡單的解決方法是引入主元，從而得到更穩定的改進高斯消元法。^[1]:151

線性方程組的解

更多資訊：線性方程組 § 其他方法與軟件

數值線性代數通常將矩陣視作列向量的組合。對於求解線性方程組${\displaystyle x=A^{-1}b}$，傳統代數方法是將x理解為${\displaystyle A^{-1}}$與b的積。數值線性代數則將x理解為b在A的列形成的基上現行展開的係數向量。^[1]:8

格努矩陣A及向量x、b的特徵，可以用很多不同的分解解決線性問題。若${\displaystyle A=QR}$，則等價於${\displaystyle Rx=Q^{\ast }b}$。這和矩陣分解一樣容易計算。^[1]:54將A進行特徵分解：${\displaystyle A=X\Lambda X^{-1}}$，並試圖找到使${\displaystyle b=Ax}$的b，且${\displaystyle b'=X^{-1}b,\ x'=X^{-1}x}$，則有${\displaystyle b'=\Lambda x'}$。^[1]:33這同使用奇異值分解求解線性系統密切相關，因為矩陣的奇異值是特徵值的絕對值，也等價于格拉姆矩陣${\displaystyle X^{*}X}$特徵值絕對值的平方根。將A進行LU分解得<matdh>A=LU</math>，則${\displaystyle Ax=b}$可用三角矩陣${\displaystyle Ly=b,\ Ux=y}$求解。^{[1]:147[4]:99}

最小二乘優化

主條目：線性最小二乘數值方法

矩陣分解提出了許多解線性方程組${\displaystyle r=b-Ax}$的方法，其中我們尋求最小的r，如回歸問題。QR算法計算A的既約QR分解並重排，得到${\displaystyle {\widehat {R}}x={\widehat {Q}}^{\ast }b}$。此上三角方程組可用於解x。SVD還提供了一種獲得線性最小二乘的算法：計算既約SVD分解${\displaystyle A={\widehat {U}}{\widehat {\Sigma }}V^{\ast }}$，並計算向量${\displaystyle {\widehat {U}}^{\ast }b}$，就可以將最小二乘問題簡化為簡單的對角方程組。^[1]:84QR分解和SVD分解可以產生最小二乘解，這意味着除了用經典正規方程法解最小二乘問題外，還可用格拉姆-施密特法、豪斯霍德法等方法。

條件和穩定性

主條目：數值分析 § 數值穩定性及良置問題

假設問題是函數${\displaystyle f:X\to Y}$，其中X是數據的賦范向量空間，Y是解的賦范向量空間。對於數據點${\displaystyle x\in X}$，若x的微小擾動會導致${\displaystyle f(x)}$的值發生很大變化，則稱之為病態的（ill-conditioned）。可以定義條件數量化之，代表問題的完備程度： $${\displaystyle {\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.}$$

不穩定性是指依賴浮點運算的計算機算法的結果與問題的精確解產生差距的趨勢。矩陣包含多位有效數字的真實數據時，很多解線性方程組或最小二乘優化的算法會產生不準確的解。為病態問題創建穩定算法是數值線性代數的核心問題，例如豪斯霍德三角化是線性方程組的很穩健的解法，而解最小二乘法的正規方程法不穩定，是奇異值分解更常用的一個原因。有些矩陣分解方法可能不穩定，但可以直接修改而變得穩定，例如格拉姆-施密特法可以很容易地改成改進格拉姆-施密特法；^[1]:140高斯消元法不穩定，引入主元後變得穩定。

迭代法

主條目：迭代法

迭代法成為數值線性代數重要組成有兩個原因。其一，很多重要的數值問題沒有直接解，如求任意矩陣的特徵值和特徵向量。其二，對任意${\displaystyle m\times m}$矩陣的非迭代算法需要${\displaystyle O(m^{3})}$時間，而矩陣只含${\displaystyle m^{2}}$個數字，這個下限非常高。迭代法可利用矩陣的特點縮短時間。例如對稀疏矩陣，迭代算法可跳過很多直接方法必須的步驟，即便它們在矩陣高度結構化的情形下是多餘的。

數值線性代數中，很多迭代法的核心是將矩陣投影到低維克雷洛夫子空間，這樣就可從低維空間開始迭代計算類似矩陣的等效特徵，依次向高維移動以逼近高維矩陣的特徵。對對稱的A，解線性方程${\displaystyle 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. Trefethen, Lloyd; Bau III, David. Numerical Linear Algebra 1st. Philadelphia: SIAM. 1997. ISBN 978-0-89871-361-9.
2. Golub, Gene H. A History of Modern Numerical Linear Algebra (PDF). University of Chicago Statistics Department. [2019-02-17]. （原始內容存檔 (PDF)於2022-03-02）.
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 .
4. 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]. （原始內容存檔於2019-02-18）.

閱讀更多

• Dongarra, Jack; Hammarling, Sven. Evolution of Numerical Software for Dense Linear Algebra. Cox, M. G.; Hammarling, S. (編). Reliable Numerical Computation. Oxford: Clarendon Press. 1990: 297–327. ISBN 0-19-853564-3.

• Leader, Jeffery J. Numerical Analysis and Scientific Computation. Addison Wesley. 2004. ISBN 0-201-73499-0.
• Bau III, David; Trefethen, Lloyd N. Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics. 1997. ISBN 978-0-89871-361-9.
• J. H. Wilkinson and C. Reinsch, "Linear Algebra, volume II of Handbook for Automatic Computation" SIAM Review 14, 658 (1972).
• Golub, Gene H.; van Loan, Charles F. (1996), Matrix Computations, 3rd edition, Johns Hopkins University Press, ISBN 978-0-8018-5414-9

外部連結

• 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