A^nの計算

質問

0 -1 -1
-1 0 -1
-1 -1 0

という行列Aのn乗を求めたいのですが，どのような方法がありますか？

A^2=-A+2E
という関係に気づき，A^n=aA+bEとかけることより求まったのですが，
他にもっとよい方法がある気がします．

回答No.3

alice_44 · ベストアンサー

A をジョルダン標準化する手間がメンドなので、
そんなことするくらいなら、
ケイリー・ハミルトンでも使ったほうがいいし、
貴方のように最小多項式を使えば更によいかと。

お礼

なるほど．
高校数学偉大ですね．

回答No.2

alice_44

A = E - B (E は単位行列) と置いて、
A の n 乗を二項定理で展開する。
E と B は可換だし、BB = 3B だからね。

お礼

なるほど．
簡単にできそうです．やってみます．
ジョルダン標準形を用いた解法はありますか？

回答No.1

sagamit

一般化して考えると n を 2 の倍数の和に分解する方法があります。
たとえば n が 13 だとした場合を例にとると

A^13
= A^(1+4+8)
= A + A^4 + A^8

となります。

A^2 を計算するのは単なる A*A なので計算は簡単です。
更に A^4 は (A^2)^2 ですからもう一回かけ算するだけです。
その要領で二乗を繰り返した数列を作ると
A, A^2, A^4, A^8 をそれぞれ求めるのはかけ算3回で済みます。
この数列から必要なものを抜き出して A + A^4 + A^8 とすれば良いので 3 回の足し算です。
ビッグオー記法で表すと最大で O(log n) となりますので単純に n 回のかけ算をした場合の O(n) に比べて計算量が少なくなります。

A にも n にも特殊な性質を必要としません。

お礼

A^13
= A^(1+4+8)
= A + A^4 + A^8
間違っていませんか？