Testen, ob eine Matrix positiv semidefinit ist

Ich habe eine Liste symmetrischer Matrizen, die ich auf positive Halbbestimmtheit prüfen muss (dh ihre Eigenwerte sind nicht negativ). ${\cal L}$

Der obige Kommentar impliziert, dass man dies tun könnte, indem man die jeweiligen Eigenwerte berechnet und prüft, ob sie nicht negativ sind (möglicherweise muss man sich um Rundungsfehler kümmern).

Das Berechnen der Eigenwerte ist in meinem Szenario ziemlich teuer, aber ich habe festgestellt, dass die Bibliothek, die ich verwende, einen ziemlich schnellen Test auf positive Bestimmtheit hat (dh wenn die Eigenwerte einer Matrix streng positiv sind).

Daher wäre die Idee, dass man bei einer Matrix testet, ob positiv definitiv ist. Wenn dies nicht der Fall ist, ist nicht positiv semidefinit, andernfalls kann man die Eigenwerte von berechnen , um sicherzustellen, dass es tatsächlich positiv semidefinit ist. $B \in {\cal L}$ $B + \epsilon I$ $B$ $B$

Meine Frage ist jetzt:

Gibt es eine direktere und effizientere Methode, um zu testen, ob eine Matrix positiv semidefinit ist, vorausgesetzt, es wird ein effizienter Test für die positive Bestimmtheit durchgeführt?

linear-algebra eigenvalues Jernej
quelle

Der Test, den Sie in der Bibliothek bemerkt haben, basiert wahrscheinlich auf der Annahme, dass die symmetrische reelle Matrix genau dann positiv definit ist, wenn jedes führende Nebenprinzip eine positive Determinante ergibt, was durch Eliminierung überprüft werden könnte, ohne in exakter Arithmetik zu schwenken. Die subtile Schwierigkeit, dies auf einen halbbestimmten Fall auszudehnen, hat viele Autoren zu falschen Angaben verleitet. Ich weiß, dass das Thema in einer Math.SE-Frage angesprochen wurde, daher werde ich versuchen, einen Link bereitzustellen.

A

$A$

Hardmath

math.stackexchange.com/questions/753825/…

Hardmath

Für diejenigen, die hier mehr wissen - würde es funktionieren, das Spektrum durch Addition von für großes positiv zu verschieben , dann den minimalen Eigenwert des verschobenen Systems zu finden (z. B. mit inverser Iteration) und dann zu prüfen, ob der kleinste Eigenwert von verschobenes System ist kleiner als die Verschiebung ? Die Verschiebung könnte zum Beispiel der größte Eigenwert sein, der schnell gefunden werden kann.

B + c I

$B + cI$

c

$c$

c

$c$

c

$c$

Nick Alger

Ja, Sie können die Eigenwerte verschieben und den kleinsten Eigenwert berechnen, aber Sie haben immer noch das Problem, eine gewisse Toleranz für das festzulegen, was Sie akzeptieren (und sicherzustellen, dass Ihre Eigenwerte mindestens dieser Toleranz entsprechen!)

Brian Borchers

Sie sind sich nicht sicher, ob dies hilfreich wäre, aber beachten Sie, dass Sie, sobald Sie wissen, dass eine Matrix nicht eindeutig positiv ist, nur überprüfen müssen, ob ihr Kernel nicht leer ist, um zu überprüfen, ob sie positiv semidefinit ist.

Abel Molina

Antworten:

Was ist Ihre Arbeitsdefinition von "positiv semidefinit" oder "positiv definit"? In der Gleitkomma-Arithmetik müssen Sie hierfür eine Toleranz angeben.

Sie können dies anhand der berechneten Eigenwerte der Matrix definieren. Sie sollten jedoch zuerst beachten, dass die berechneten Eigenwerte einer Matrix linear mit der Matrix skalieren, so dass beispielsweise bei der Matrix, die ich durch Multiplizieren von mit einem Faktor von einer Million erhalte, die Eigenwerte mit einer Million multipliziert werden. Ist ein negativer Eigenwert? Wenn alle anderen Eigenwerte Ihrer Matrix positiv sind und in der Größenordnung von , ist effektiv 0 und sollte nicht als negativer Eigenwert behandelt werden. Daher ist es wichtig, die Skalierung zu berücksichtigen. $A$ $\lambda=-1.0$ $10^{30}$ $\lambda=-1.0$

Ein vernünftiger Ansatz besteht darin, die Eigenwerte Ihrer Matrix zu berechnen und zu erklären, dass die Matrix numerisch positiv semidefinit ist, wenn alle Eigenwerte größer als, wobei der größte Eigenwert ist. $-\epsilon \left| \lambda_{\max} \right|$ $\lambda_{\max}$

Leider ist die Berechnung aller Eigenwerte einer Matrix ziemlich zeitaufwändig. Ein anderer häufig verwendeter Ansatz besteht darin, dass eine symmetrische Matrix als positiv definitiv angesehen wird, wenn die Matrix eine Cholesky-Faktorisierung in der Gleitkomma-Arithmetik aufweist. Die Berechnung der Cholesky-Faktorisierung ist eine Größenordnung schneller als die Berechnung der Eigenwerte. Sie können dies auf eine positive Halbwertszeit erweitern, indem Sie der Matrix ein kleines Vielfaches der Identität hinzufügen. Auch hier gibt es Skalierungsprobleme. Ein schneller Ansatz besteht darin, eine symmetrische Skalierung der Matrix durchzuführen, sodass die diagonalen Elemente 1,0 sind, und der Diagonale hinzuzufügen , bevor die Cholesky-Faktorisierung berechnet wird. $\epsilon$

Sie sollten jedoch vorsichtig sein, da es einige Probleme mit dem Ansatz gibt. Zum Beispiel gibt es Umstände, in denen und in dem Sinne positiv sind, dass sie Gleitkomma-Cholesky-Faktorisierungen haben, jedoch keine Cholesky-Faktorisierung. Somit ist die Menge der "Gleitkomma-Cholesky-faktorisierbaren positiven bestimmten Matrizen" nicht konvex! $A$ $B$ $(A+B)/2$

Brian Borchers
quelle

Könnten Sie diesen letzten Absatz näher erläutern oder einen Link zu einer Quelle veröffentlichen? Das ist ziemlich bizarr.

Daniel Shapero

Ein klassischer Hinweis auf diese Skalierung ist A. van der Slui. Bedingungsnummern und Äquilibrierung von Matrizen Numerische Mathematik 14 (1): 14-23, 1969. Es wird auch in Lehrbüchern wie Golub und van Loan diskutiert. Das Bit im letzten Absatz stammt aus hart erarbeiteten persönlichen Erfahrungen bei der Suche nach Codierungszeilen in einem semidefiniten Programmcode. Ich habe Situationen erlebt, in denen und Cholesky-Faktorisierungen nach LAPACK haben, hat laut LAPACK keine Cholesky-Faktorisierung. Diese Art von Problemen tritt auf, wenn Sie fast einzigartig sind.

X

$X$

X + α Δ X

$X+\alpha \Delta X$

X + 0.95 α Δ X

$X+0.95 \alpha \Delta X$

Brian Borchers

Es ist auch nicht ungewöhnlich zu entdecken, dass einige Matrizen mit erweiterter oder vierfacher Genauigkeit Cholesky-faktorisiert werden können, jedoch nicht mit regulärer Gleitkomma-Arithmetik mit doppelter Genauigkeit oder einfacher Genauigkeit.

Brian Borchers

Einige der primär-dualen inneren Punktcodes für SDP (CSDP, SDPT3, SDPA) geben immer Matrizen zurück, die positiv definitiv sind und Cholesky-Faktorisierungen aufweisen, während ein anderer beliebter Löser (SeDuMi) eine Eigenwertzerlegung verwendet und Lösungen zurückgibt, die sehr klein negativ sind Eigenwerte.

Brian Borchers

Kerr, TH, " Testen von Matrizen auf Bestimmtheit und Anwendungsbeispiele, die den Bedarf hervorbringen ", AIAA Journal of Guidance , Control and Dynamics, Vol. 3, No. 5, S. 503-506, Sept.-Okt. 1987.
Kerr, TH, " Über falsche Angaben des Tests für positive semidefinite Matrizen ", AIAA Journal of Guidance, Control and Dynamics , Vol. 3 , No. 3, S. 571-572, May-Jun. 1990. (wie in der Navigations- und Zielverfolgungssoftware in den 1970er und 1980er Jahren unter Verwendung von Gegenbeispielen)
Kerr, TH, " Irrtümer bei der rechnergestützten Prüfung von Matrix-positiver Bestimmtheit / Semidefinitität ", IEEE Transactions on Aerospace and Electronic Systems , Vol. 3 , No. 26, No. 2, S. 415-421, März 1990. [Listet trügerische Algorithmen auf, die der Autor in den späten 1970er und frühen 1980er Jahren routinemäßig in der U-Boot-Navigations- und Sonobuoy-Software der US Navy gefunden hat, und verwendet Gegenbeispiele, um auf die Probleme hinzuweisen. ]]

Thomas H. Kerr III
quelle

Scheint, als ob der Benutzername die Beziehung zwischen dem Autor der Antwort und dem Autor der Papiere ziemlich offenbart. Ein bisschen mehr Informationen darüber, was in der Zeitung enthalten ist, wären nett; Trotzdem ist es sehr interessant und relevant für die Fragenliste der Papiere!

Anton Menshov