[問題3]直接法と反復法
問題
連立一次方程式の解法は、直接法と反復法に分けることができる。次の4つのうち反復法はどれか。
- LU分解
- GMRES法
- SSOR法
- スカイライン法
解き方
本問は暗記問題です。わりきって、連立一次方程式の解法を覚えるしかありません。
直接法
ガウス消去法:行列の要素を操作して、上三角行列を作成し、後退代入によって解を求める。この方法は、LU分解と密接に関連しており、ピボット選択を行うことで数値安定性を向上させることができる。
LU分解:行列を下三角行列(L)と上三角行列に分解し、連立方程式を2つの三角方程式として解く。一度分解すれば、即座に解を求めることができる。
コレスキー分解法:対称正定値行列の場合に適用できるLU分解の亜種で、行列を下三角行列と転置に分解する。対称正値行列に対しては、通常のLU分解法よりも高速に解くことができる。
スカイライン法:疎行列の格納方法を効率化するアルゴリズムで、特に有限要素法によって得られる対称バンド行列に対して効果的とされる。行列の非ゼロ要素のみを格納し、計算効率を向上。
反復法
ガウス-ザイデル法:既知の値をしようして解を反復的に更新し、収束するまで繰り返す。
ヤコビ法:ガウス-ザイデル法と同様の考え方だが、更新された解をすぐに使わずに、1反復中のすべての変数を更新した後で、次の反復に使用する。
共役勾配法:対称正定値行列に対して効率的な反復法で、最適な探索方向を使用して収束速度を向上させる。非対称行列に対しては、共役勾配法を一般化した手法(たとえば、BiCG、BiCGSTAB)が利用される。
GMRES法:非対称行列に対して効果的な反復法で、Krylov部分空間において残差を最小化する解を求める。収束速度が速いことが多いですが、メモリ使用量が反復回数に比例して増加するため、再計算が必要になることがある。
SOR法:ガウスザイデル法を改良したおので、過剰緩和パラメータを用いて収束速度を向上させることができる。パラメータの選択が重要。
SSOR法:SOR法を前進・後退の両方向で適用し、対称性を利用して収束速度を向上させる手法です。 これらの反復法は、大規模な線型方程式
したがって、反復法はGMRES法とSSOR法になります。