Testowanie, czy macierz jest półokreślona dodatnia

Mam listę macierzy symetrycznych, które muszę sprawdzić pod kątem dodatniej półokreśloności (tzn. Ich wartości własne są nieujemne).${\cal L}$

Powyższy komentarz sugeruje, że można to zrobić, obliczając odpowiednie wartości własne i sprawdzając, czy nie są one ujemne (być może trzeba zająć się błędami zaokrąglania).

Obliczanie wartości własnych jest dość drogie w moim scenariuszu, ale zauważyłem, że biblioteka, której używam, ma dość szybki test na pozytywną definitywność (to znaczy, jeśli wartości własne macierzy są ściśle dodatnie).

Stąd pomysł byłby taki, że biorąc pod uwagę macierz , sprawdza się, czy jest pozytywnie określony. Jeśli tak nie jest, nie jest dodatnim półokreślonym, w przeciwnym razie można obliczyć wartości własne aby upewnić się, że rzeczywiście jest dodatni półokreślony. B + ϵ I B $B \in {\cal L}$$B + \epsilon I$$B$$B$

Moje pytanie brzmi:

Czy istnieje bardziej bezpośredni i skuteczny sposób testowania, czy matryca jest półokreślona dodatnio, pod warunkiem, że podany jest skuteczny test na dodatnią jednoznaczność?

Jaka jest twoja robocza definicja „pozytywnego półfinału” lub „pozytywnego określonego”? W arytmetyki zmiennoprzecinkowej będziesz musiał określić pewną tolerancję.

Można to zdefiniować w kategoriach obliczonych wartości własnych macierzy. Należy jednak najpierw zauważyć, że obliczone wartości własne macierzy są skalowane liniowo z macierzą, tak że na przykład macierz, którą otrzymuję, mnożąc przez milion, ma swoje wartości własne pomnożone przez milion. Czy jest ujemną wartością własną? Jeśli wszystkie inne wartości własne macierzy są dodatnie i rzędu , to jest faktycznie 0 i nie powinno być traktowane jako ujemna wartość własna. Dlatego ważne jest, aby wziąć pod uwagę skalowanie. λ = - 1,0 10 30 λ = - $A$$\lambda=-1.0$$10^{30}$$\lambda=-1.0$

Rozsądnym podejściem jest obliczenie wartości własnych macierzy i zadeklarowanie, że macierz jest liczbowo dodatnia półfinałowa, jeśli wszystkie wartości własne są większe niż, gdzie jest największą wartością własną. $-\epsilon \left| \lambda_{\max} \right|$$\lambda_{\max}$

Niestety, obliczenie wszystkich wartości własnych macierzy jest dość czasochłonne. Innym powszechnie stosowanym podejściem jest to, że macierz symetryczna jest uważana za pozytywnie określoną, jeśli macierz ma współczynnik Choleskiego w arytmetyki zmiennoprzecinkowej. Obliczenie faktoryzacji Choleskiego jest o rząd wielkości szybsze niż obliczenie wartości własnych. Możesz to rozszerzyć do dodatniej półkompletności, dodając niewielką wielokrotność tożsamości do matrycy. Ponownie pojawiają się problemy ze skalowaniem. Jednym szybkim podejściem jest wykonanie symetrycznego skalowania macierzy, tak aby elementy ukośne miały wartość 1,0 i dodać do przekątnej przed obliczeniem faktoryzacji Choleskiego. $\epsilon$

Powinieneś jednak zachować ostrożność, ponieważ istnieją pewne problemy z podejściem. Na przykład, istnieją okoliczności, w których i są dodatnie określone w tym sensie, że mają zmiennoprzecinkowe rozkłady Choleskiego, ale nie mają rozkładów Choleskiego. Zatem zestaw „zmiennoprzecinkowych macierzy Cholesky'ego, które można podzielić na czynniki dodatnie”, nie jest wypukły! $A$$B$$(A+B)/2$

• Kerr, TH, „ Testowanie matryc pod kątem definitywności i przykładów zastosowań, które uzmysławiają potrzebę ”, AIAA Journal of Guidance , Control and Dynamics, t. 10, nr 5, str. 503-506, wrzesień-październik, 1987.

• Kerr, TH, „ O zniekształceniach testu pozytywnych półfinałów ”, AIAA Journal of Guidance, Control and Dynamics , t. 13, nr 3, str. 571-572, maj-czerwiec. 1990. (jak miało to miejsce w oprogramowaniu do nawigacji i śledzenia celów w latach 70. i 80. przy użyciu kontrprzykładów)

• Kerr, TH, „ Błędy w obliczeniowych testach macierzowej pozytywnej definityeness / semidefiniteness ”, IEEE Transactions on Aerospace and Electronic Systems , tom. 26, nr 2, str. 415-421, marzec 1990. [Wymienia błędne algorytmy, które autor rutynowo istnieje w oprogramowaniu do nawigacji okrętów podwodnych i sonobuoyu US Navy na przełomie lat 70. i 80. XX wieku, wykorzystując kontrprzykłady do wskazania problemów. ]

Python dla sugestii @Brian Borchers, spróbuj dekompozycji Cholesky'ego:

from sksparse.cholmod import cholesky, CholmodNotPositiveDefiniteError
    # https://scikit-sparse.readthedocs.io/en/latest/cholmod.html

def testposdef( A, beta=1e-6, pr="" ):
    """ try cholesky( a scipy.sparse matrix  + beta I )

    Why A + beta I, beta say 1e-6 ?
    If A has tiny eigenvalues, 0 to within machine precision,
    about half of these "zeros" may be negative -- tough on solvers.
    Also the condition number improves to ~ rho(A) / beta.
    """
    try:
        solve = cholesky( A, beta=beta )  # A + beta I
        if pr:
            print( "%s + %g I is positive-definite" % (pr, beta ))
        return solve  # x = solve( b )
    except CholmodNotPositiveDefiniteError:
        if pr:
            print( "%s + %g I is not positive-definite" % (pr, beta ))
        return False