Savoir si la matrice est définie positive avec numpy

J'ai besoin de savoir si la matrice est définie positive. Ma matrice est numpy de la matrice. Je m'attendais à trouver toute méthode dans numpy bibliothèque, mais sans succès.
J'apprécie toute l'aide.

InformationsquelleAutor Zygimantas Gatelis | 2013-04-28
  1. 48

    Vous pouvez aussi vérifier si toutes les valeurs propres de la matrice sont positifs, si la matrice est définie positive:

    import numpy as np

def is_pos_def(x):
    return np.all(np.linalg.eigvals(x) > 0)
    • Vous pouvez utiliser np.linalg.eigvals au lieu de cela, qui ne calcule les valeurs propres. Même alors, il est beaucoup plus lent que @NPE l'approche de (3x pour 10x10 matrices, 40x pour 1000x1000).
    • J'ai mis à jour ma réponse pour tenir compte de votre suggestion, je vous remercie. Merci pour l'info sur le temps ainsi.
    • <pédant>Il n'est pas vrai en général que toutes les valeurs propres positives implique positif précision, sauf si vous savez que la matrice est symétrique (cas réel) ou Hermitian (cas complexe). Par exemple, A = array([[1, -100],[0, 2]]) n'est pas définie positive. Certains pourraient inclure symétrique ou Hermitian dans le cadre de la définition de "définie positive", mais ce n'est pas universelle.</pédant>
    • Oups, c'est vrai, pas pédant! En fait, la vérification de la symétrie est également nécessaire si vous utilisez np.linalg.cholesky (il n'a pas le vérifier et peut retourner un résultat faux, que votre exemple montre également). Je me demande comment vérifier si un non symétrique de la matrice est définie positive peut être fait numériquement...
    • Vous pouvez faire np.all(x-x.T==0) pour vérifier la symétrie
    • C'est terriblement inefficace! Pour des matrices de taille supérieure à environ 6 ou 7 lignes/colonnes, l'utilisation de cholesky comme l'a souligné NPE ci-dessous. La de cholesky de la route se sent moins pratique (interception d'une exception, etc), mais il est beaucoup moins de gaspillage.

    InformationsquelleAutor Akavall
  2. 44

    Vous pouvez essayer de calcul de la décomposition de Cholesky (numpy.linalg.cholesky). Cela contribuera à accroître la LinAlgError si la matrice est définie positive.

    • Merci beaucoup, varie pas élégant mais qui fonctionne!
    • Cela devrait être sensiblement plus efficace que la valeur propre solution.
    • Juste une remarque que, dans la semi-définie positive cas, numériquement parlant, on peut aussi ajouter un peu de l'identité de la matrice (donc changer toutes les valeurs propres d'une petite quantité par exemple un peu de temps à la machine de précision), puis utilisez la méthode de cholesky comme d'habitude.
    InformationsquelleAutor NPE
  3. 11

    Il semble y avoir une petite confusion dans toutes les réponses ci-dessus (au moins sur la question).

    Pour les matrices réelles, les tests positifs de valeurs propres et les principaux termes de la np.linalg.cholesky ne s'applique que si la matrice est symétrique. Alors d'abord on a besoin de tester si la matrice est symétrique et ensuite appliquer l'une de ces méthodes (valeurs propres positives ou décomposition de Cholesky).

    Par exemple:

    import numpy as np

#A nonsymmetric matrix
A = np.array([[9,7],[6,14]])

#check that all eigenvalues are positive:
np.all(np.linalg.eigvals(A) > 0)

#take a 'Cholesky' decomposition:
chol_A = np.linalg.cholesky(A)

    La matrice A n'est pas symétrique, mais les valeurs propres sont positives et Numpy renvoie une décomposition de Cholesky de ce qui est mauvais. Vous pouvez vérifier que:

    chol_A.dot(chol_A.T)

    est différent de celui de A.

    Vous pouvez également vérifier que toutes les fonctions python ci-dessus serait un test positif pour "positif la précision'. Cela pourrait être un sérieux problème si vous essayez d'utiliser la décomposition de Cholesky pour calculer l'inverse, depuis:

    >np.linalg.inv(A)
array([[ 0.16666667, -0.08333333],
   [-0.07142857,  0.10714286]])

>np.linalg.inv(chol_A.T).dot(np.linalg.inv(chol_A))
array([[ 0.15555556, -0.06666667],
   [-0.06666667,  0.1       ]])

    sont différents.

    En résumé, je voudrais suggérer l'ajout d'une ligne à l'une des fonctions ci-dessus pour vérifier si la matrice est symétrique, par exemple:

    def is_pos_def(A):
    if np.array_equal(A, A.T):
        try:
            np.linalg.cholesky(A)
            return True
        except np.linalg.LinAlgError:
            return False
    else:
        return False

    Vous voudrez peut-être remplacer np.array_equal(A, A. T) dans la fonction ci-dessus pour les np.allclose(A, A. T) pour éviter des différences qui sont dues à virgule flottante erreurs.

    • Pinailler: vous devriez probablement vérifier numpy.linalg.LinAlgError à moins que vous importez avec from numpy.linalg import LinAlgError, ce qui n'est pas une chose que je voudrais faire si je ne l'attraper cette exception spécifique une fois ou deux fois dans mon code.
    • Merci! J'ai corrigé le code ci-dessus.
    • Si l'on travaille avec des matrices complexes, cela peut conduire à l'erreur (à savoir si l'Une est complexe définie positive, donc hermitian avec des valeurs propres strictement positives, la cholesky truc, c'est encore correct mais il ne passera pas le premier if déclaration pour np.allclose(A, A.T)). À l'aide de np.allclose(A, A.H) va corriger cela (l'OP dit qu'il travaille avec numpy matrice, si l'on travaille avec ndarray, utilisez A.conj().T au lieu de .H
    InformationsquelleAutor Daniel Garza
  4. 4

    Je ne sais pas pourquoi la solution de NPE est donc sous-estimée. C'est le meilleur moyen pour ce faire. J'ai trouvé sur Wkipedia que la complexité est cubique.

    En outre, il est dit qu'il est plus numériquement stable que la décomposition Lu. Et la décomposition Lu est plus stable que la méthode de recherche de toutes les valeurs propres.

    Et, il est très élégante, une solution, parce que c'est un fait :

    Une matrice a une décomposition de Cholesky si et seulement si elle est symétrique positive.

    Alors pourquoi ne pas utiliser les mathématiques ? Peut-être que certaines personnes de peur de la relance de l'exception, mais il a fait trop, il est très utile pour programmer avec des exceptions.

    • À partir de la même page Wikipedia, il semble que votre énoncé est faux. La page dit " Si la matrice A est Hermitian et semi-définie positive, alors qu'il a encore une décomposition de la forme A = LL* si la diagonale des entrées de L sont autorisés à zéro.[3]" Donc une matrice avec une décomposition de Cholesky n'implique pas la matrice est symétrique définie positive, car il pourrait juste être semi-définie. Suis-je interpréter ce mal? Aussi, il semble que vous avez tout simplement jetés "symétrique" à travers l'implication. c'est à dire ne devrait-elle pas être tous les Hermitian matrice définie positive a unique décomposition de Cholesky?
    InformationsquelleAutor InfiniteLooper
  5. 3

    Pour illustrer @NPE, en réponse à certaines de prêt-à-utiliser le code:

    import numpy as np

def is_pd(K):
    try:
        np.linalg.cholesky(K)
        return 1 
    except np.linalg.linalg.LinAlgError as err:
        if 'Matrix is not positive definite' in err.message:
            return 0
        else:
            raise
    • Vous pourriez également demandé à @NPE ajouter le code à sa réponse originale à cette question.
    InformationsquelleAutor MarcoMag
  6. 0

    Pour une véritable matrice $A$, nous avons $x^Impôt=\frac{1}{2}(x^T(A+A^T)x)$, et $A+A^T$ est symétrique réelle de la matrice. Si $A$ est définie positive ssi $A+A^T$ est définie positive, le forum de toutes les valeurs propres de $A+A^T$ sont positifs.

    import numpy as np

def is_pos_def(A):
    M = np.matrix(A)
    return np.all(np.linalg.eigvals(M+M.transpose()) > 0)
    InformationsquelleAutor Martin Wang