13

我有很多需要在 Matlab 中求逆的大型（大约 5000 x 5000）矩阵。我实际上需要倒数，所以我不能使用 mldivide 来代替，这对于仅解决一个 b 的 Ax=b 来说要快得多。

我的矩阵来自一个问题，这意味着它们具有一些不错的属性。首先，它们的行列式是 1，所以它们绝对是可逆的。但是，它们不可对角化，或者我会尝试对它们进行对角化，反转它们，然后将它们放回原处。他们的条目都是实数（实际上是有理数）。

我正在使用 Matlab 来获取这些矩阵，并且对于这些我需要处理它们的逆矩阵的东西，所以我更喜欢一种加快 Matlab 速度的方法。但是，如果我可以使用另一种更快的语言，请告诉我。我不懂很多其他语言（一点点C，一点点Java），所以如果它在其他语言中真的很复杂，那么我可能无法使用它。不过，请继续提出建议，以防万一。

4

3 回答 3

19
于 2011-06-28T16:18:40.963 回答
7

无论您使用什么语言，反转任意 5000 x 5000 矩阵在计算上都不容易。我建议研究近似值。如果你的矩阵是低秩的，你可能想尝试一个低秩近似 M = USV'

以下是数学溢出的更多想法：

https://mathoverflow.net/search?q=matrix+inversion+approximation

于 2011-06-28T16:03:45.357 回答
1

First suppose the eigen values are all 1. Let A be the Jordan canonical form of your matrix. Then you can compute A^{-1} using only matrix multiplication and addition by

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

where k < dim(A). Why does this work? Because generating functions are awesome. Recall the expansion

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

This means that we can invert (1-x) using an infinite sum. You want to invert a matrix A, so you want to take

A = I - X

Solving for X gives X = I-A. Therefore by substitution, we have

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

Here I've just used the identity matrix I in place of the number 1. Now we have the problem of convergence to deal with, but this isn't actually a problem. By the assumption that A is in Jordan form and has all eigen values equal to 1, we know that A is upper triangular with all 1s on the diagonal. Therefore I-A is upper triangular with all 0s on the diagonal. Therefore all eigen values of I-A are 0, so its characteristic polynomial is x^dim(A) and its minimal polynomial is x^{k+1} for some k < dim(A). Since a matrix satisfies its minimal (and characteristic) polynomial, this means that (I-A)^{k+1} = 0. Therefore the above series is finite, with the largest nonzero term being (I-A)^k. So it converges.

Now, for the general case, put your matrix into Jordan form, so that you have a block triangular matrix, e.g.:

A 0 0
0 B 0
0 0 C

Where each block has a single value along the diagonal. If that value is a for A, then use the above trick to invert 1/a * A, and then multiply the a back through. Since the full matrix is block triangular the inverse will be

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

There is nothing special about having three blocks, so this works no matter how many you have.

Note that this trick works whenever you have a matrix in Jordan form. The computation of the inverse in this case will be very fast in Matlab because it only involves matrix multiplication, and you can even use tricks to speed that up since you only need powers of a single matrix. This may not help you, though, if it's really costly to get the matrix into Jordan form.

于 2011-06-28T16:45:53.613 回答