行列の最大固有値をべき乗法で求めたい。

Question

Ｃ言語です。
大](9048fc62bf27d21959d62153fecfa787.png)学の課題で行列の最大固有値をべき乗法で数値的に求めるという課題が出ましたが、アルゴリズムを見てもまったくわかりませんでした。どなたか分かる方いますか？

Answer 1

示されているアルゴリズムの内容は，
DxD の行列 A に対して，以下の手続きを十分な回数繰り返せ，という話．

z(t) = A y(t)
λ(t) = y(t)・z(t)
y(t+1) = z(t) / |z(t)|

ただし，y(0) は「適当な初期ベクトル」とされる．

---

ここまで具体的に示されているのだから，やるべきことは明確．
以下のような事柄を，ただただやっていけばいい．

(1) ベクトルと行列の表現方法を決める

話には ベクトル と 行列 が出てくるので，こいつらをどうやって扱うかを決める．
どんな形でもいい．「俺はこうするぜ！」という強い意志を持って決めればいい．

例えば，以下のような形だと決めてしまえばいい．

//D は define で与えられるということにするぜ！
#define D (5)
//これがベクトルと行列だオラァ！
typedef struct Vec {	double v[D];	} Vec;  //ベクトル
typedef struct Mat {	Vec row[D];	} Mat;  //行列．行ベクトルがD個．

この形が何らかの意味で良くないと思うなら，自身が良いと思う別の形に決めればいい．
必要なデータを表すことができるならＯＫなのだ．自由に決めよう．

(2) 必要な演算を実装する

アルゴリズムに示されている式を見れば，以下の演算が必要そうである．

• 行列とベクトルの乗算　（１つ目の式より）
• ベクトルの内積　（２つ目の式より）
• ベクトルのノルム計算　（３つ目の式より）
• ベクトルのスカラー倍　（３つ目の式より）

そしたらもう，これらを実装すればいい．関数４個だ．淡々と用意しよう．
前記(1)で定めた型に見合う形で実装すればいいだけだ．

このコード例↓だと関数の中身は全部３行になった．簡単すぎる．

//内積
double IP( const Vec *a, const Vec *b )
{
	double ip=0;
	for( int i=0; i<D; ++i ){	ip += a->v[i]*b->v[i];	}
	return ip;
}

//ベクトルのL2ノルム
double L2Norm( const Vec *V )
{
	double SqNorm = 0;
	for( int i=0; i<D; ++i ){	SqNorm += (V->v[i] * V->v[i]);	}
	return sqrt(SqNorm);
}

//ベクトルのスカラー倍
Vec MulS( const Vec *V, double s )
{
	Vec Ret;
	for( int i=0; i<D; ++i ){	Ret.v[i] = V->v[i]*s;	}
	return Ret;
}

//ベクトルに行列を乗じる．（縦ベクトルVに対して，M*V を求む）
Vec Mul( const Mat *M, const Vec *V )
{
	Vec Ret;
	for( int i=0; i<D; ++i ){	Ret.v[i] = IP( &(M->row[i]), V );	}
	return Ret;
}

(3)アルゴリズムを指定通りに実装する

必要な型と処理関数は全て揃ったから，あとはそれらを使う形で「手続きを十分な回数繰り返す」処理を書くだけだ．
main()関数に殴り書きすりゃいいだろう．
自明すぎるからここのサンプルコードは示さない．

他に残っている些細な事柄と言えば，以下の２点くらいであろう．

• 「適当な初期ベクトル」とは何か？

式を見れば明らかに　零ベクトルはアウト　だとわかるが，それ以外ならとりあえず何でもいいんじゃない？
「適当」と言われているんだから，てきとーに与えればよい．

• 「十分な回数」とは何か？

こっちも「てきとーな回数」でいいだろう．
10回とか100回とかてきとーな回数で動かしてみて，足りなそうだったら増やせばいいんじゃない？
反復回数が足りてるかどうかは検算してれみればわかる話（得られた結果が「固有値と固有ベクトルの組」として妥当か否かをチェックしてみればいい）．

Comments

[fana]

この程度の課題をやるときには，
(1)のところでグダグダと悩んでないで，さっさと「これが俺のやり方だ！」って決めてしまえばいいと思うの．
勢いが大切．

あなたが決めた形で書くのはあなただけなのであり，
それで誰に迷惑かけるわけでもないのだから（しいて言うなら，提出された側が読み難いくらいか）．

それでやってみて途中で「あ，これだと×××だ」とか何か不都合が生じたならば，そのコードを捨ててまた別の形でやればいい．
その経験で何か「押さえるべき点」が明確になったならそれを活かせばいい．

Answer 2

一通りしらべてみたのですが分かりませんでした。
以下はアルゴリズムです。

Comments

[fana]

> 一通りしらべてみた

｛何について，どのような必要性があって｝調べた　という話ですか？
調べた結果としてどのような情報が得られたのですか？

話の内容とその疑似コードまでが示されている状態にあるのならば，その状態において調べねばならない事柄とは何なのか？という点が他者には全く不明です．
とりあえず課題をこなすだけであれば，単にそこに書かれている話をそのまま実装してやればよいだけの話に見えます．

[tackle.8]

コードについて調べてみたのですが、資料のような方法はみつからず、自分の勉強不足のせいで参考にならなかったのでお聞きしました。どうやって実装すれば良いのかすらわからない状態です。

[Zuishin]

まずすべきことは、言語を覚えることです。そこを飛ばしているのが、どうやって実装すれば良いかわからない原因です。

[fana]

とりあえず疑似コードを見れば for でループさせることくらいしか示されていないので，
ご利用の言語（質問についているタグから察するにC言語かな）で for なるものを使えるくらいには復習が必要でしょうけど，あとは特に厄介事はないように見えます．
（5x5の行列なんて，変数を25個用意すれば表現できるのだし）

[fana]

（他の質問を見るに，Cが全く書けないとかいう状態でもないようだが…？　であれば，なおさらに，何に行き詰っているのかがわからないな…）