Welche iterativen linearen Löser konvergieren für positive semidefinite Matrizen?

10

Ich möchte wissen , welche der klassischen linearen Löser (zB Gauss-Seidel, Jacobi, SOR) für das Problem zu Converge garantiert , wo A positiv ist halb bestimmte und natürlich b i m ( A )Ax=bAbim(A)

(Hinweis ist halbbestimmt und nicht eindeutig)A

Olamundo
quelle
1
Meinen Sie positive semidefinitive Matrizen?
Meawoppl
1
Was nützt es, ein lineares System mit einer solchen Matrix zu lösen? Wenn ich mich nicht irre, wenn Ihre positive semidefinite Matrix nicht singulär ist, dann ist sie einfach positiv definitiv.
Faleichik
1
Ja, ich bin sicher. Ich muss mein Gedächtnis für den tatsächlichen Beweis auffrischen, aber gemäß dem, was Sie gesagt haben - wenn der Nenner bei der Berechnung von Null ist, bedeutet dies, dass A P k Null ist, was bedeutet, dass alle "Suchrichtungen", in denen A ist nicht singulär, wurde erschöpft, und der Rest, den Sie übrig haben, liegt nicht in der Spanne von A (und somit ist dies die "optimale" Lösung). In dem Fall, dass tatsächlich b s p a n ( A ) ist , wird dies nicht passieren, da der Rest kurz vor dem ersten Mal Null erreicht. A P k = 0αAPkbspan(A)APk=0
olamundo
1
Setze . Dann ist A n b I m ( A ) . CG konvergiert aufgrund von x n A x n > 0 für alle 0 x nI m ( A ) . Mit anderen Worten, Sie verlassen niemals I m ( A ), für das A positiv bestimmt ist. x0=bAnbIm(A)xnAxn>00xnIm(A)Im(A)A
Todesatem
2
@faleichik: Matrizen mit reduzierter Dichte in der Quantenmechanik sind in sehr vielen Fällen positiv semidefinit.
Todesatem

Antworten:

8

Der konjugierte Gradientenalgorithmus arbeitet für semidefinite Probleme und erzeugt die minimale Normlösung.

Arnold Neumaier
quelle
Vielen Dank. Jede Idee über die "archaischen" Löser, zB SOR Gauss-Seidel usw.
Olamundo
Sie werden kaum noch benutzt und ich weiß nicht, wie sich diese verhalten.
Arnold Neumaier
Zur Verdeutlichung: CG funktioniert mit Sicherheit nicht in Vanilleform für semi-definierte Matrizen; es kann theoretisch funktionieren, wenn B im Bild von A ist; Es ist jedoch unwahrscheinlich, dass dies in der numerischen Praxis gut endet. Das sehr ähnliche MINRES auf Krylov-Basis ist hier eine viel bessere Wahl. Diese "archaischen" Löser werden auch häufig in Lösern vom Multigrid-Typ verwendet, um nur ein Beispiel zu nennen.
Eelco Hoogendoorn
1

bA

Das gleiche gilt sehr wenig für Jacobi; Was ist eine Schande, denn wer möchte sich mit Gauß-Seidel auf moderner Computerhardware beschäftigen? Wenn Ihr Problem in diagonal dominierende Blöcke aufgeteilt werden kann, haben Sie Glück. Sie können Jacobi-Aktualisierungen inkrementell nach Gauß-Seidel auf diese Blöcke anwenden und das Beste aus beiden für diese Art von semidefiniten Problemen herausholen.

Eelco Hoogendoorn
quelle