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

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

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

直接法 (exact method)

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

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

反復法 (iterative method)

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

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