全文

(1)

算法の設計と解析 

¿

回目

連立方程式の解法

個の未知数を持つ方程式が 個の連立次方程式を解くことを考える.行列で表すと以下となる.

ここで、 × , 次元ベクトルである.この問題の解

 

となることは明白である.

以下に逆行列を求める例を紹介する.

 行列×の逆行列の求め方

 

ここで, とする.

 行列 × の逆行列の求め方

余因子行列を使って, の逆行列を求める.

 

ここで, である. の余因子.

における   の計算の積の回数は回である.しかし,×の行列では, の行列式を解くのに積の 回数回,余因子の計算にそれぞれ回かかり,全体では 回かかる. × の行列ではなんと千万回以 上となる.これでは, が大きくなると計算量が爆発的に増加する.よって,一般に × の逆行列を求める場 合は,余因子を用いた方法は用いられない.

ここでは, の解の効率的に解くことを考える.ここでは,ガウスの消去法,分解を紹介する.

なぜ積の回数に注目するか?

計算機における加減乗除の四則演算では,乗除算は加減の繰り返しとして実行され,減法は負数の加法とみ なせる.従って,おおよその計算量としては加減の計算回数は無視し,乗除算の総数を見積もればよい.

(2)

ガウスの消去法

ガウスの消去法とは,逆行列   を求めることなく,連立次方程式を解くための計算方法である.ガウスの 消去法は行列 を行列の基本変形を用いて,に変形することである.このとき, の解となっ ている.

行列の基本変形

 行列 行と行を入れ替える.

行の定数倍から行の定数倍を加える.

行に定数倍をかける.

つの例を示す.

のとき

ここで, とする.この連立方程式の解法は × ×とし,  

 

 

 

となる.

のとき

行列に変換して,

次に,計算機上で,ガウスの消去法を行う場合,単純なアルゴリズムする必要がある.そのアルゴリズムを以 下に紹介する.

回目の行列の変形は

 

 

 

(3)

に従う.ここで, となる.この作業によって, は,上三角行列となり,

連立次方程式は

¼

¼

¼

¼

¼

¼

¼

¼

¼

となる.この式から一番下の式¼ ¼ により, が導かれ,順に     が求まる.

ÄÍ分解

の行列 の下三角行列,上三角行列に変換する.

とおくと,

となる. はそれぞれ下三角行列,上三角行列なので,式と同様に,まずが求まり,次に解が求まる.

の行列乗算

行列の乗算の高速化において, 法がある.以下に例を示す.

余因子行列を使って, の逆行列を求める.

通常の乗算では,乗算は回,加減は回となる.この 法では,乗算回,加減は回となって いる.

(4)

ユークリッド互除法

ユークリッド互除法とは,最大公約数を求めるアルゴリズムである. とし, の最大公約数を求め ることを考える.

以下に従って, の最大公約数を求める.

に対して、上式が成立する.

とし,

¼

¼

¼

¼

¼¼

¼¼

この作業を繰り返す.最終的に余り のとき,前の余り  が最高公約数となり,のときは,が最 大公約数となる.

Updating...

参照

Updating...

関連した話題 :