• 締切済み

行列の掛け算と逆行列にて最も少ない計算量は?

宜しくお願い致します。 行列の計算の評価を探しています。 n×n実行列A,Bの掛け算ABと逆行列A^-1を計算するのに一番少ない計算法はどのくらいで評価できるのでしょうか? Time(ABの計算)=O(??), Time(A^-1の計算)=O(??) よろしければそのサイトもご紹介頂けましたら有難いです。

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

ちょろっと検索して出てきた現状: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

回答No.1

ABはシュトラッセンの方法がn^2.8 だけど、手間がかかりすぎて使われて いません(係数が大きい)。単純に定義通り掛けるだけの 方法は０(n^3) 逆行列は私の知る限りLU分解が最速(係数が小さい)。 Ｏ(n^3)

AkiTamura
質問者

お礼

有難うございます。 シュトラッセンの方法とLU分解を使うと,AとBを掛けて,ABの逆行列を求める計算量は Time((AB)^-1)=O(n^2.8)+O(n^3)=O(n^3) とO(n^3)で評価できるのですね。

AkiTamura
質問者

補足

すいません。もし, A,Bの成分が高々ln(k)ビット長なら, Time(AB)とTime(A^-1)は何で評価できるのでしょうか? Time(AB)=O(n^2ln(k)) とTime(A^-1)=O(n^2ln(k)) ですか?

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ｍ×ｎ行列の逆行列

    m×n 行列の逆行列に相当する概念として一般逆行列がありますが, m×n 行列 A に対して, n×m 行列 B がAB=Em(Emはm次の単位行列)かつBA=En(Enはn次の単位行列) を満たすとき, B を A の逆行列と定義しないのはなぜでしょうか ?

  • 逆行列の計算

    こんばんは。 逆行列の計算についてどうしてもわからない所があるので教えてください。 行列（B＋C*Rt）があります。(Rtは行列Rの転置) ここで、B=[B11 ０; B21 B22]{;は改行}の構造化行列で次元は,（行＊列）の順番でB11がn+n,０がn*m(０は０行列),B21がm*n,B22がm*mです。 行列Cに関しては、C=[B21;０]でB21がn*m,０がm*mの０行列。 行列Rtに関しては、Rt=[０ Iq]で０がm*nの０行列、Iqがm*mの単位行列です。 この時（B＋C*Rt）の逆行列がわかりません。 答えは、B~-B~*{C*(Iq+Rt*B~*C)~*Rt}*B~になると思うのですが・・・(~は逆行列です) どなたか解かる方お願いします。

  • フォートランで行列の計算

    ｎ×ｎ行列同士の掛け算をする文が書けません。ｄａｔａ文を使わないで、ｒｅａｄ文を使って、次元ｎと行列Ａ，Ｂを入力したいんですが、どなたか教えて下さい。

  • 逆行列は存在するの？

    Ａの逆行列をＡ（－１）と表してみます。 高校生のとき不思議だったのが、 　　Ａ、Ｂに逆行列が存在するとき、 　　　（ＡＢ）（－１）＝Ｂ（－１）Ａ（－１） という性質でした。これ自体に疑問を持ったのではなく、ＡＢの逆行列の存在を無条件に受け入れている様に思うからです。だって、＝で結ばれているということは右から左に変形できてもよさそうじゃないですか。 そこで質問ですが、この状態でＡＢという行列の逆行列は必ず存在するのでしょうか。高校の先生は「うーん。これは、左辺は右辺の計算をすれば出てくるという式だ」というだけで、私には理解できませんでした。分かりやすく教えてください。

  • ３×３の逆行列の計算

    ３×３の逆行列の計算 吐き出し法以外の逆行列の計算の仕方をすっかり忘れてしまいました・・・。 0.4　0.708　-0.081 -0.226　1.165　0.046 0　0　0.918 これの逆行列を求めたいのですが、吐き出し法でできる気がしません・・・。 どうやればいいのでしょうか？ よろしくお願いします。

  • 行列の計算

    お恥ずかしいながら、行列の計算でてこずっております。 以下の問題です。 行列A、Bをn×n行列とする。 また行列Aのi,j成分をa(i,j)とし、行列Bのi,j成分をb(i,j)とする。 ここで a(i,j) = {n-i+1 (1≦j≦i), n-j+1(i+1≦j≦n)} b(i,j) = {1(i=j=1), 0(i≠j-1, j, j+1), -1(i=j-1, j+1), 2(j=k)} である。 このとき、行列A×Bのi,j成分を求めよ。 という問題です。 答えはi=jのとき1,i≠jのとき0 (つまり、A×B=I(n×nの単位行列)) なのですが、そこまでの計算のプロセスが分かりません。 分かり易いご解答をお待ちしております。

  • 積と逆行列

    行列の証明問題です。よろしくお願いいたします。 問題は、 次のことを証明せよ A,Bが逆行列をもつとき、ABも逆行列をもち、(AB)^(-1)= B^(-1) A^(-1) です。 解答は、 (AB)（B^(-1) A^(-1)）＝AB B^(-1) A^(-1)=(AEA)^(-1)= AA^(-1)=E （B^(-1) A^(-1)）(AB)＝B^(-1) A^(-1)AB=(B)^(-1)EB=B^(-1)B=E よって、ABは逆行列をもち、(AB)^(-1)= B^(-1) A^(-1) （証明終） となっています。 ですが、私はどうしてこの二つで証明できるのかわかりません。 私は、(AB) (AB)^(-1)=E=(AB)^(-1) (AB)を証明すべきだと思います。 そこで質問なのですが、どうして解答のような方法で、証明したことになるのでしょうか？ よろしくお願いいたします。

  • (Ａの逆行列)^nとＡ^nを掛けてＥになりますか？

    高校生です。来年受験です。 自分なりに導いた回答に自信がないので正しいかよろしくおねがいします。また別解でもかまいません。 『行列Ａは2×2行列(すべて実数)。ab‐bc≠0のとき、すべての自然数ｎについてＡ^n=０時ならばＡ^n≠Oを示せ。』という問題です。 私は背理法を用いました。 ad‐bc≠0のとき、Ａ≠0で行列が存在する。 ある自然数nについて、Ａ^n=0と仮定する。(←背理)両辺に(Ａ^-１)^nをかけるとＥ=0となり矛盾。よって… (省略) としました。 これは正しいでしょうか？ そもそも ｛(Ａ^-１)^n｝×Ａ^n=Ｅとして大丈夫でしょうか？ つまり、(Ａの逆行列)^nとＡ^nを掛けてＥになるのかどうかが不安な部分です。 見にくくてすみません。どうかよろしくおねがいします。

  • 行列の中に行列がある行列式の計算について

    A、Bをn次の行列としたとき、 行列式　 　　｜A　B｜ 　　｜B　A｜　　 は｜A+B||A－B|　になるのはよく知られていると思いますが、Cもn次の行列として、 　　　｜A　B　C｜ 　　　｜B　A　B｜ 　　　｜C　B　A｜ とかも計算の公式はあるのでしょうか。 ホントに知りたいのは、上でB=I(単位行列)、C=０（零行列）の場合です。

  • Excel 2007 ＜マクロで逆行列を求めたい＞

    Excel 2007 ＜マクロで逆行列を求めたい＞ 任意のn次の正方行列の逆行列をシートを介さずマクロ上のみで求めたいのです。 たとえば Option Base 1 Sub test() 　dim a() as single 　dim b() as single 　n=5 　redim a(n,n) '行列A 　redim b(n,n) '行列B 　 　for i=1 to n 　　for j=1 to n 　　　....'a(i,j)に値が入る 　　next j 　next i 　 　.... 　.... 'Aの逆行列の要素がBの要素になる。 End Sub　 というマクロです。 （行列Aは逆行列を持つという前提で話を進めます） 以下のサイトより、シートに値があれば、Rangeオブジェクト及びWorksheetFunctionを用いて逆行列を求められることが分かりました。 http://makotowatana.ld.infoseek.co.jp/vba_cell.html そこでもう一歩踏み込んで、シートを介さずして逆行列の要素を、取得したいのですが、可能でしょうか？ ご存知の方よろしくお願いします。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する