B..2 連立1次方程式の解法概説

コンピューターで行われる数値計算の時間の 90% は、 連立1次方程式を解いている時間である、という説があるくらい、 連立1次方程式は頻出する問題である。例えば微分方程式の問題も、 離散化 (有限次元近似) された後は連立1次方程式を解くことに帰着されることが多い ¹⁵。 ところがこのように工学的な応用で、 連立1次方程式を解くために実際に利用されている方法は (ほとんどの) 線形代数の本には載っていない。

実際に利用される解法は色々あるが、大きく次の二つに分類される (直接法以外知らない、見当もつかない人が多いと思われるが、 それで構わない)。 以下では直接法について、やや詳しく説明する。

直接法 (exact method)

もし個々の演算に丸め誤差がなければ、有限回の演算で解が得られる方法

• Gauss の消去法 (LU 分解), 対称な問題に対する Cholesky 分解法, QR 分解に基づく方法などある。

反復法 (iterative method)

有限回の演算では真の解が得られないかもしれないが、 反復するごとに近似解の精度を上げて行き、 十分な精度が得られたところで打ち切る方法

• 古くからある定常反復法 (Jacobi 法, Gauss-Seidel 法, SOR 法など) と非定常反復法 (CG 法とその改良版, 親類) に分類される¹⁶。
• 計算のためには行列 $A$ の成分そのものを知る必要はなく、 任意に与えたベクトル $x$ との積 $Ax$ が分かれば良いという特徴を持ち、 行列の疎性¹⁷を利用しやすい。