D..2 連立1次方程式の解法概説
コンピューターで行われる数値計算の時間の 90% は連立1次方程式を解いて
いる時間だという説があるくらい、連立1次方程式は頻出する問題である。例え
ば微分方程式の問題も、離散化 (有限次元近似) された後は連立1次方程式を解
くことに帰着されることが多い19。ところがこのように工学的な応用で、連
立1次方程式を解くために実際に利用されている方法は (ほとんどの) 線形代数
の本には載っていない。
実際に利用される解法は色々あるが、大きく次の二つに分類される
(直接法以外知らない、見当もつかない人が多いと思われるが、
それで構わない)。
以下では直接法について、やや詳しく説明する。
- 直接法 (exact method)
- もし個々の演算に丸め誤差がなければ、有限回の演算で解が得られる方法
- Gauss の消去法 (LU 分解),
対称な問題に対する Cholesky 分解法,
QR 分解に基づく方法などある。
- 反復法 (iterative method)
- 有限回の演算では真の解が得られないかもしれないが、
反復するごとに近似解の精度を上げて行き、
十分な精度が得られたところで打ち切る方法
- 古くからある定常反復法 (Jacobi 法, Gauss-Seidel 法, SOR 法など) と
非定常反復法 (CG 法とその改良版, 親類) に
分類される20。
- 計算のためには行列
の成分そのものを知る必要はなく、
任意に与えたベクトル
との積
が分かれば良いという特徴を持ち、
行列の疎性21を利用しやすい。
桂田 祐史
2017-06-19