算法の設計と解析
¿回目
月日
連立方程式の解法
個の未知数を持つ方程式が 個の連立次方程式を解くことを考える．行列で表すと以下となる．
ここで、 は × ， ，は 次元ベクトルである．この問題の解は
となることは明白である．
以下に逆行列を求める例を紹介する．
例 行列×の逆行列の求め方
ここで， とする．
例 行列 × の逆行列の求め方
余因子行列を使って， の逆行列を求める．
ここで， である． の余因子．
例における の計算の積の回数は回である．しかし，×の行列では， の行列式を解くのに積の 回数回，余因子の計算にそれぞれ回かかり，全体では 回かかる． × の行列ではなんと千万回以 上となる．これでは， が大きくなると計算量が爆発的に増加する．よって，一般に × の逆行列を求める場 合は，余因子を用いた方法は用いられない．
ここでは， の解の効率的に解くことを考える．ここでは，ガウスの消去法，分解を紹介する．
なぜ積の回数に注目するか？
計算機における加減乗除の四則演算では，乗除算は加減の繰り返しとして実行され，減法は負数の加法とみ なせる．従って，おおよその計算量としては加減の計算回数は無視し，乗除算の総数を見積もればよい．
ガウスの消去法
ガウスの消去法とは，逆行列 を求めることなく，連立次方程式を解くための計算方法である．ガウスの 消去法は行列 を行列の基本変形を用いて，に変形することである．このとき，が の解となっ ている．
行列の基本変形
行列 の行と行を入れ替える．
行の定数倍から行の定数倍を加える．
行に定数倍をかける．
つの例を示す．
例 のとき
ここで， とする．この連立方程式の解法は × ×とし，
となる．
例 のとき
行列に変換して，
次に，計算機上で，ガウスの消去法を行う場合，単純なアルゴリズムする必要がある．そのアルゴリズムを以 下に紹介する．
回目の行列の変形は
に従う．ここで， となる．この作業によって， は，上三角行列となり，
連立次方程式は
¼
¼
¼
¼
¼
¼
¼
¼
¼
となる．この式から一番下の式¼ ¼ により， が導かれ，順に が求まる．
ÄÍ分解
の行列 を の下三角行列，上三角行列に変換する．
とおくと，
となる． はそれぞれ下三角行列，上三角行列なので，式と同様に，まずが求まり，次に解が求まる．
の行列乗算
行列の乗算の高速化において， 法がある．以下に例を示す．
例
余因子行列を使って， の逆行列を求める．
通常の乗算では，乗算は回，加減は回となる．この 法では，乗算回，加減は回となって いる．
ユークリッド互除法
ユークリッド互除法とは，最大公約数を求めるアルゴリズムである． とし， の最大公約数を求め ることを考える．
以下に従って， の最大公約数を求める．
に対して、上式が成立する．
とし，
¼
¼
¼
¼
¼¼
¼¼
この作業を繰り返す．最終的に余りが のとき，前の余り が最高公約数となり，のときは，が最 大公約数となる．
例
