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

12

Mam listę macierzy symetrycznych, które muszę sprawdzić pod kątem dodatniej półokreśloności (tzn. Ich wartości własne są nieujemne).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 BBLB+ϵIBB

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ść?

Jernej
źródło
1
Test, który zauważyłeś w bibliotece, prawdopodobnie opiera się na twierdzeniu, że symetryczna macierz rzeczywista jest dodatnia, jeśli tylko i tylko wtedy, gdy każda wiodąca zasada drugorzędna daje dodatnią determinantę, coś, co można sprawdzić przez eliminację bez dokładnej arytmetyki. Subtelna trudność rozciągnięcia tego na półokreślony przypadek skłoniła wielu autorów do zniekształcenia. Wiem, że temat został poruszony w pytaniu Math.SE, więc postaram się podać link. A
hardmath
1
Dla tych bardziej kompetentnych ludzi - czy warto przesunąć spektrum na dodatnie, dodając dla dużego , a następnie znaleźć minimalną wartość własną przesuniętego układu (np. Z odwrotną iteracją), a następnie sprawdzić, czy najmniejsza wartość własna przesunięty system jest mniejszy niż przesunięcie ? Przesunięcie może być na przykład wartością własną największej wielkości, którą można szybko znaleźć. c c cB+cIccc
Nick Alger
Tak, możesz przesunąć wartości własne i obliczyć najmniejszą wartość własną, ale nadal masz problem z ustaleniem tolerancji na to, co zaakceptujesz (i upewnieniem się, że twoje wartości własne są obliczane przynajmniej do tej tolerancji!)
Brian Borchers
Nie jestem pewien, czy byłoby to pomocne, ale zauważ, że kiedy wiesz, że matryca nie jest pozytywnie określona, ​​aby sprawdzić, czy jest to dodatnia półfinał, wystarczy sprawdzić, czy jej jądro nie jest puste.
Abel Molina

Odpowiedzi:

23

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 λ = - 1,0Aλ=1.01030λ=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ą. ϵ|λmax|λ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. ϵ

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! AB(A+B)/2

Brian Borchers
źródło
Czy mógłbyś rozwinąć ten ostatni akapit lub zamieścić link do źródła? To dość dziwne.
Daniel Shapero
2
Klasycznym odniesieniem do tego skalowania jest A. van der Slui. Numery warunków i równowaga macierzy Numerische Mathematik 14 (1): 14-23, 1969. Jest również omawiany w podręcznikach takich jak Golub i van Loan. Fragment w ostatnim akapicie pochodzi z ciężko zdobytego osobistego doświadczenia w wyszukiwaniu linii kodowania w półfinałowym kodzie programowania - napotkałem sytuacje, w których i mają rozkład Cholesky'ego według LAPACK, ale nie ma faktoryzacji Cholesky'ego według LAPACK. Tego rodzaju problemy zaczynają się pojawiać, gdy jesteś prawie osobliwy. XX+αΔXX+0.95αΔX
Brian Borchers,
1
Nierzadko zdarza się również, że niektóre macierze mogą być uwzględnione w Cholesky'ego z rozszerzoną lub poczwórną precyzją, ale nie z regularną arytmetyką zmiennoprzecinkową podwójnej precyzji lub pojedynczej precyzji.
Brian Borchers,
3
Kilka pierwotnych podwójnych wewnętrznych kodów punktów dla SDP (CSDP, SDPT3, SDPA) zawsze zwraca macierze, które są dodatnio określone i mają rozkład Cholesky'ego, podczas gdy inny popularny solver (SeDuMi) wykorzystuje rozkład wartości własnych i zwróci rozwiązania, które mają bardzo małe ujemne wartości własne.
Brian Borchers,
3
Thomas H. Kerr III
źródło
5
Wygląda na to, że nazwa użytkownika w zasadzie ujawnia związek między autorem odpowiedzi a autorem artykułów. Przydałoby się trochę więcej informacji na temat tego, co zawiera artykuł; w każdym razie jest to bardzo interesujące i odpowiednie do listy pytań artykułów!
Anton Menshov
0

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
denis
źródło