13

Matlab で反転する必要がある大きな (約 5000 x 5000) 行列がたくさんあります。実際には逆が必要なので、代わりに mldivide を使用することはできません。これは、1 つの b について Ax=b を解くのにはるかに高速です。

私のマトリックスは、いくつかの優れたプロパティがあることを意味する問題から来ています。まず、それらの行列式は 1 なので、間違いなく可逆です。ただし、それらは対角化できません。または、それらを対角化して反転させ、元に戻そうとします。それらのエントリはすべて実数 (実際には有理数) です。

私はこれらの行列を取得するために Matlab を使用しており、このために逆行列を処理する必要があるため、Matlab を高速化する方法が望ましいと考えています。しかし、もっと速く使える別の言語があれば教えてください。私は他の多くの言語 (C は少し、Java は少しだけ) を知らないので、他の言語で非常に複雑な場合は、使用できない可能性があります。ただし、場合によっては、先に進んで提案してください。

4

3 に答える 3

19
于 2011-06-28T16:18:40.963 に答える
7

任意の 5000 x 5000 行列を反転することは、使用している言語に関係なく計算上簡単ではありません。近似値を調べることをお勧めします。行列のランクが低い場合は、低ランクの近似 M = USV' を試してください。

以下は、math-overflow からのいくつかのアイデアです。

https://mathoverflow.net/search?q=行列+反転+近似

于 2011-06-28T16:03:45.357 に答える
1

まず、固有値がすべて であるとします1。Aあなたの行列のヨルダン標準形にしましょう。A^{-1}次に、行列の乗算と加算のみを使用して計算できます

A^{-1} = I + (I-A) + (I-A)^2 + ... + (I-A)^k

どこでk < dim(A)。なぜこれが機能するのですか？生成関数は素晴らしいからです。展開を思い出す

(1-x)^{-1} = 1/(1-x) = 1 + x + x^2 + ...

これは(1-x)、無限和を使用して反転できることを意味します。行列を反転しAたいので、

A = I - X

を解くとXが得られますX = I-A。したがって、代入により、

A^{-1} = (I - (I-A))^{-1} = 1 + (I-A) + (I-A)^2 + ...

Iここでは、 number の代わりに恒等行列を使用してい1ます。ここで対処すべき収束の問題がありますが、これは実際には問題ではありません。Aはジョルダン形式で、すべての固有値が に等しいという仮定により、は対角線上にすべての s を持つ上三角で1あることがわかります。したがって、対角線上にすべての s を持つ上三角形です。したがって、 のすべての固有値はであるため、その特性多項式はであり、その最小多項式は一部のです。行列はその最小 (および特性) 多項式を満たすため、これは. したがって、上記の級数は有限であり、最大の非ゼロ項は次のとおりです。A1I-A0I-A0x^dim(A)x^{k+1}k < dim(A)(I-A)^{k+1} = 0(I-A)^k. それで収束します。

ここで、一般的なケースとして、行列を Jordan 形式に変換して、ブロック三角行列を作成します。たとえば、次のようになります。

A 0 0
0 B 0
0 0 C

各ブロックは、対角線に沿って単一の値を持ちます。その値がaの場合A、上記のトリックを使用して を反転し1/a * A、逆を乗算しaます。完全な行列はブロック三角行列であるため、逆行列は次のようになります。

A^{-1} 0      0
0      B^{-1} 0
0      0      C^{-1}

ブロックが3つあることに特別なことはないので、これはいくつあっても機能します。

このトリックは、Jordan 形式のマトリックスがある場合はいつでも機能することに注意してください。この場合の逆行列の計算は、行列の乗算のみを含むため、Matlab では非常に高速です。単一の行列の累乗のみが必要なため、トリックを使用して高速化することもできます。ただし、行列を Jordan 形式にするのに非常にコストがかかる場合は、これは役に立たないかもしれません。

于 2011-06-28T16:45:53.613 に答える