数値線形代数

数値線形代数（応用線形代数とも呼ばれる）は、行列演算を用いて、連続数学における問題に対して効率的かつ正確に近似解を提供するコンピュータアルゴリズムを作成する方法を研究する分野です。数値解析のサブ分野であり、線形代数の一種です。コンピュータは浮動小数点演算を使用するため、無理数を正確に表現することはできません。そのため、コンピュータアルゴリズムをデータ行列に適用すると、コンピュータに格納されている数値と、それが近似値である真の数値との差が大きくなることがあります。数値線形代数は、ベクトルと行列の特性を利用して、コンピュータによって生じる誤差を最小限に抑えるコンピュータアルゴリズムを開発し、アルゴリズムの効率性を最大限に高めることにも重点を置いています。

数値線形代数は、有限精度コンピュータを使用して連続数学の問題を解決することを目的としており、自然科学や社会科学への応用は連続数学の応用と同じくらい広範です。これは、画像処理や信号処理、電気通信、計算金融、材料科学シミュレーション、構造生物学、データマイニング、バイオインフォマティクス、流体力学、計算統計学など、工学や計算科学の問題の基本的な部分であることがよくあります。行列法は、特に有限差分法、有限要素法、微分方程式のモデリングで使用されます。数値線形代数の幅広い応用に注目して、ロイド N. トレフェセンとデイビッド バウ III は、比較的小さな分野ではあるものの、「微積分や微分方程式と同じくらい数学科学にとって基本的である」と主張しています^{[ 1 ] : x 。 [ 2 ]}行列やベクトルの多くの性質は関数や演算子にも当てはまるため、数値線形代数は実用的なアルゴリズムに特に重点を置いた関数解析の一種とみなすこともできる。 ^{[ 1 ]： ix}

数値線形代数における一般的な問題には、特異値分解、QR分解、LU分解、固有値分解などの行列分解を求めることが含まれます。これらの行列分解は、線形方程式系の解法、固有値の探索、最小二乗最適化といった一般的な線形代数問題に答えるために使用できます。数値線形代数の中心的な課題は、有限精度コンピュータ上で実データに適用した際に誤差を生じさせないアルゴリズムを開発することであり、これは直接的な方法ではなく反復的な方法によって達成されることが多いです。

数値線形代数は、ジョン・フォン・ノイマン、アラン・チューリング、ジェームズ・H・ウィルキンソン、アルストン・スコット・ハウスホルダー、ジョージ・フォーサイス、ハインツ・ルティシャウザーといったコンピュータの先駆者たちによって、弾道問題や偏微分方程式系の解法など、連続数学の問題に初期のコンピュータを適用するために開発されました。^{[ 2 ]}アルゴリズムを実データに適用する際のコンピュータの誤差を最小限に抑えるための最初の本格的な試みは、1947年のジョン・フォン・ノイマンとハーマン・ゴールドスタインの研究です。 ^{[ 3 ]}技術の進歩により、研究者は極めて大きな高精度行列上の複雑な問題を解決できるようになり、並列コンピューティングなどの技術によって数値アルゴリズムが科学的問題への実用的なアプローチとなったことで、この分野は成長してきました。^{[ 2 ]}

問題を関数とみなす${\displaystyle f:X\to Y}$ここで、Xはデータのノルムベクトル空間、Yは解のノルムベクトル空間である。あるデータ点について${\displaystyle x\in X}$xの小さな摂動がf ( x )の値に大きな変化をもたらす場合、問題は悪条件であると言われます。これを定量化するために、問題の条件の良し悪しを表す 条件数を定義します。条件数は次のように定義されます。$${\displaystyle {\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}.}$$

不安定性とは、浮動小数点演算に依存するコンピュータアルゴリズムが、問題の正確な数学的解から大きく異なる結果を生成する傾向のことです。行列に多くの有効桁を持つ実数データが​​含まれる場合、線形方程式系や最小二乗最適化などの問題を解くための多くのアルゴリズムは、非常に不正確な結果を生成する可能性があります。条件の悪い問題に対する安定したアルゴリズムを作成することは、数値線形代数における中心的な課題です。たとえば、ハウスホセラー三角化の安定性により、線形システムに対して特に堅牢な解法となりますが、最小二乗問題を解くための正規方程式法の不安定性は、特異値分解などの行列分解法を好む理由となります。一部の行列分解法は不安定ですが、簡単に修正して安定させることができます。たとえば、不安定なグラム・シュミット法は、簡単に修正して安定した修正グラム・シュミット法を作成できます。^{[ 1 ] : 140}数値線形代数におけるもう 1 つの古典的な問題は、ガウス消去法が不安定であるが、ピボットの導入により安定するという発見である。

反復アルゴリズムが数値線形代数の重要な部分を占める理由は2つあります。第一に、多くの重要な数値問題には直接解法がないため、任意の行列の固有値と固有ベクトルを求めるには反復法を用いるしかありません。第二に、任意の行列に対する非反復アルゴリズムは、${\displaystyle m\times m}$マトリックスは必要${\displaystyle O(m^{3})}$時間、行列には${\displaystyle m^{2}}$数値。反復的なアプローチでは、一部の行列のいくつかの特徴を利用してこの時間を短縮できます。たとえば、行列が疎行列の場合、反復アルゴリズムは、直接的なアプローチでは必然的に実行される多くの手順を省略できます。たとえ、高度に構造化された行列では冗長な手順であってもです。

数値線形代数における多くの反復法の核心は、行列を低次元のクリロフ部分空間に射影することであり、これにより、低次元空間から始めて、類似の行列の等価な特徴を反復的に計算し、順次高次元へと移動することで、高次元行列の特徴を近似することができます。Aが対称行列で、線形問題Ax = bを解きたい場合、古典的な反復法は共役勾配法です。Aが非対称行列の場合、線形問題の反復解法の例としては、一般化最小残差法とCGN があります。A が対称行列の場合、固有値と固有ベクトル問題を解くには、ランチョス法を使用できます。A が非対称行列の場合は、アーノルディ反復法を使用できます。

いくつかのプログラミング言語は数値線形代数の最適化技術を使用しており、数値線形代数アルゴリズムを実装するように設計されています。これらの言語には、MATLAB、Analytica、Maple、Mathematicaなどがあります。数値線形代数用に明示的に設計されていない他のプログラミング言語には、数値線形代数のルーチンと最適化を提供するライブラリがあります。CとFortran にはBasic Linear Algebra SubprogramsやLAPACKなどのパッケージがあり、Python にはNumPyライブラリがあり、Perl にはPerl Data Languageがあります。Rの多くの数値線形代数コマンドは、LAPACKなどのこれらのより基本的なライブラリに依存しています。^{[ 5 ]}より多くのライブラリは、数値ライブラリのリストで見つけることができます。

• Dongarra, Jack ; Hammarling, Sven (1990). 「密な線形代数のための数値計算ソフトウェアの進化」. Cox, MG; Hammarling, S. (編) 『信頼性の高い数値計算』所収. Oxford: Clarendon Press. pp. 297–327 . ISBN  0-19-853564-3。
• Claude Brezinski、Gérard Meurant、Michela Redivo-Zaglia (2022):数値線形代数の歴史を巡る旅、SIAM、ISBN 978-1-61197-722-6。

• Demmel, JW (1997):応用数値線形代数、SIAM。
• Ciarlet, PG、Miara, B.、Thomas, JM (1989):数値線形代数と最適化入門、ケンブリッジ大学出版局。
• トレフェセン、ロイド；バウ III、デイビッド (1997)：数値線形代数（第 1 版）、SIAM、ISBN 978-0-89871-361-9
• Golub, Gene H.; Van Loan, Charles F. (1996):行列計算（第3版）、ジョンズ・ホプキンス大学出版局。ISBN 978-0-8018-5413-2
• GW Stewart (1998):行列アルゴリズム第1巻：基本分解、SIAM、ISBN 978-0-89871-414-2
• GW Stewart (2001): Matrix Algorithms Vol II: Aigensystems、SIAM、ISBN 978-0-89871-503-3
• Varga, Richard S. (2000):行列反復解析、Springer。
• Yousef Saad (2003)  : Iterative Methods for Sparse Linear Systems、第2版、SIAM、ISBN 978-0-89871534-7
• Raf Vandebril、Marc Van Barel、Nicola Mastronardi (2008):行列計算と半分離行列、第 1 巻: 線形システム、Johns Hopkins Univ. Press、ISBN 978-0-8018-8714-7
• Raf Vandebril、Marc Van Barel、Nicola Mastronardi (2008):行列計算と半分離行列、第2巻：固有値法と特異値法、Johns Hopkins Univ. Press、ISBN 978-0-8018-9052-9
• Higham, NJ (2002):数値アルゴリズムの精度と安定性、SIAM。
• Higham, NJ (2008):行列の関数: 理論と計算、SIAM。
• David S. Watkins (2008):行列の固有値問題: GR と Krylov 部分空間法、SIAM。
• Liesen, J.、および Strakos, Z. (2012): Krylov 部分空間法: 原理と解析、Oxford Univ. Press。

• テネシー大学のジャック・ドンガラとハテム・ルタイエフが作成した、ウェブ上で無料で利用できる数値代数ソフトウェア。
• NAGライブラリ：数値線形代数ルーチン集
• Xに関する数値線形代数グループ（英国の研究グループ）
• X上のsiagla (産業応用数学会における数値線形代数に関する活動グループ)
• 応用および数値線形代数に関するGAMM活動グループ