Existe-t-il un moyen rapide d'inverser une matrice dans Matlab?

J'ai beaucoup de grande taille (autour de 5000 x 5000) des matrices dont j'ai besoin pour inverser dans Matlab. J'ai réellement besoin de l'inverse, donc je ne peux pas utiliser mldivide au lieu de cela, ce qui est beaucoup plus rapide pour résoudre Ax=b pour juste un b.

Mon matrices sont à venir à partir d'un problème qui signifie qu'ils ont des belles propriétés. Tout d'abord, leur déterminant est 1, donc ils ne sont certainement inversible. Ils ne sont pas diagonalizable, bien que, ou je voudrais essayer de diagonlize, inverser, et ensuite les mettre en arrière. Leurs entrées sont des nombres réels (en fait rationnelle).

Je suis à l'aide de Matlab pour l'obtention de ces matrices et pour ça j'ai besoin de faire avec leurs inverses, donc je préfère une façon de vitesse de Matlab. Mais si il y a un autre langage que je peux utiliser sera plus rapide, alors s'il vous plaît laissez-moi savoir. Je ne connais pas beaucoup d'autres langues (un peu, mais de C et un peu de Java), donc si c'est vraiment compliqué dans une autre langue, alors je risque de ne pas être en mesure de l'utiliser. S'il vous plaît aller de l'avant et de le suggérer, bien que, dans le cas.

source d'informationauteur Daniel

  1. 19

    J'ai réellement besoin de l'inverse, donc je ne peux pas utiliser mldivide au lieu de cela,...

    Ce n'est pas vrai, parce que vous pouvez toujours utiliser mldivide pour obtenir l'inverse. Notez que A-1 = A-1 * I. Dans MATLAB, c'est l'équivalent de 

    invA = A\speye(size(A));

    Sur ma machine, cela prend environ 10,5 secondes pour un 5000x5000 de la matrice. Notez que MATLAB possède un inv fonction pour calculer l'inverse d'une matrice. Bien que cela prendra environ la même quantité de temps, il est moins efficace en termes de précision numérique (plus d'info dans le lien).

    Tout d'abord, leur déterminant est 1, donc ils ne sont certainement inversible

    Plutôt que det(A)=1c'est le condition numéro de votre matrice qui dicte comment exacte ou stable, l'inverse sera. Notez que det(A)=∏i=1:n λi. Mettez donc de λ1=Mλn=1/M et λi≠1,n=1 vous donnera det(A)=1. Cependant, comme M → ∞cond(A) = M2 → ∞ et λn → 0ce qui signifie que votre matrice est à l'approche de la singularité et il y aura de grandes erreurs numériques dans le calcul de l'inverse.

    Mon matrices sont à venir à partir d'un problème qui signifie qu'ils ont des belles propriétés.

    Bien sûr, il existe d'autres algorithmes plus efficaces qui peuvent être utilisés si votre matrice est creuse ou a d'autres propriétés favorables. Mais sans plus d'infos sur votre problème spécifique, il n'y a rien de plus à dire.

    Je préfère une façon de vitesse Matlab jusqu'

    MATLAB utilise élimination de Gauss pour calculer l'inverse d'une matrice (classement complet, non fragmentée, sans propriétés particulières) à l'aide de mldivide et c'est Θ(n3)où n est la taille de la matrice. Donc, dans votre cas, n=5000 et il y a 1.25 x 1011 d'opérations en virgule flottante. Ainsi, sur un raisonnable machine avec environ 10 Gflops de puissance de calcul, vous allez besoin d'au moins 12,5 secondes pour calculer l'inverse et il n'y a aucun moyen de sortir de cette, à moins d'exploiter les "caractéristiques particulières" (si elles sont exploitables)

  2. 7

    De l'inversion de l'arbitraire 5000 x 5000 matrice n'est pas de calcul facile quelle que soit la langue que vous utilisez. Je recommande à la recherche dans des approximations. Si votre matrices sont de faible rang, vous voudrez peut-être essayer un faible rang approximation M = USV'

    Voici quelques idées de mathématiques-débordement:

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

  3. 1

    Première suppose que les propres valeurs sont toutes 1. Laissez A être la Jordanie forme canonique de votre matrice. Ensuite, vous pouvez calculer A^{ -1} en utilisant uniquement de la matrice de multiplication et d'addition par

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

    où k < dim(A). Pourquoi ce travail? Parce que les fonctions génératrices sont impressionnantes. Rappel de l'expansion

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

    Cela signifie que nous pouvons inverser (1-x) à l'aide d'une somme infinie. Vous souhaitez inverser une matrice Asi vous voulez prendre

    A = I - X

    Des problèmes pour X donne X = I-A. Par conséquent, la substitution, nous avons

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

    Ici, j'ai simplement utilisé la matrice identité I à la place du numéro 1. Maintenant, nous avons le problème de la convergence à traiter, mais ce n'est pas réellement un problème. Par l'hypothèse que A est en Jordanie et a tous propres valeurs égales à 1nous savons que A est triangulaire supérieure avec tous les 1s sur la diagonale. Donc I-A est triangulaire supérieure avec tous les 0s sur la diagonale. Par conséquent, tous les propres valeurs de I-A sont 0de sorte que son polynôme caractéristique est x^dim(A) et son polynôme minimal est x^{k+1} pour certains k < dim(A). Depuis une matrice satisfait à son minimum (et caractéristique) polynôme, ce qui signifie que (I-A)^{k+1} = 0. Par conséquent, la série ci-dessus est finisavec la plus grande valeur non nulle en terme de (I-A)^k. Donc elle converge.

    Maintenant, pour le cas général, de mettre votre matrice en forme de la Jordanie, de sorte que vous avez un bloc triangulaire de la matrice, par exemple:

    A 0 0
0 B 0
0 0 C

    Où chaque bloc a une valeur unique le long de la diagonale. Si cette valeur est a pour Apuis utilisez l'astuce ci-dessus pour inverser 1/a * Apuis multiplier le a. Puisque la matrice est bloc triangulaire, l'inverse sera

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

    Il n'y a rien de spécial à propos de trois blocs, de sorte que cela fonctionne, peu importe combien vous en avez.

    Noter que cette astuce fonctionne à chaque fois que vous avez une matrice en forme de la Jordanie. Le calcul de l'inverse dans ce cas sera très rapide dans Matlab, car il s'agit uniquement de multiplication de matrice, et vous pouvez même utiliser des astuces pour la vitesse que depuis vous avez seulement besoin de puissances d'une matrice. Cela ne peut pas vous aider, mais, si c'est vraiment coûteux d'obtenir la matrice en Jordanie formulaire.