連立一次方程式 — 知識ノート

A x = b

数値計算で最も基本的な問題。

解き方#

x = A^{- 1} b ではなく L U x = b を前進・後退代入

python

np.linalg.solve(A, b)      # これ
np.linalg.inv(A) @ b       # これは避ける

LU 分解では、対角成分が 0 に近いと桁落ちする。行を入れ替えて絶対値の大きい要素を対角に持ってくる（部分ピボット選択）ことで、安定性が確保される。

これを省くと、理論上は解けても数値的に破綻する。 アルゴリズムの安定性が実装の細部で決まる典型例。

$n$ が $10^{6}$ を超えると直接法は使えない。共役勾配法などの反復法では、行列を陽に持たず $A v$ の計算だけできればよい（matrix-free）。収束の速さは条件数に依存し、前処理 (preconditioning) で改善する。

Lloyd N. Trefethen, David Bau III. Numerical Linear Algebra. SIAM, 1997. https://doi.org/10.1137/1.9780898719574
Gene H. Golub, Charles F. Van Loan. Matrix Computations, 4th ed. Johns Hopkins University Press, 2013. https://www.press.jhu.edu/books/title/10678/matrix-computations