Kleinster Eigenwert ohne Inverse

11

Angenommen, ist eine symmetrische, positiv definierte Matrix. ist groß genug, dass es teuer ist, direkt zu lösen . A A x = bARn×nAAx=b

Gibt es einen iterativen Algorithmus zum Finden des kleinsten Eigenwerts von , bei dem in jeder Iteration invertiert wird?A.AA

Das heißt, ich müsste einen iterativen Algorithmus wie konjugierte Gradienten verwenden, um zu lösen , sodass das wiederholte Anwenden von wie eine teure "innere Schleife" erscheint. Ich brauche nur einen einzigen Eigenvektor.A - 1Ax=bA1

Vielen Dank!

Justin Solomon
quelle
1
Haben Sie versucht, die Cholesky-Zerlegung zu verwenden? Sie müssten in wobei eine dreieckige Matrix ist. Sobald Sie die Faktorisierung haben (Sie tun dies nur einmal), können Sie sie in jeder Iteration verwenden, um das System sehr schnell durch Vorwärts- und Rückwärtssubstitution zu lösen. L L T L.ALLTL
Juan M. Bello-Rivas
Ist A eine spärliche Matrix?
Tolga Birdal
A hat eine Blockstruktur, aber ich würde es vorziehen, nicht damit herumzuspielen, wenn ich nicht muss - also habe ich mich mit "matrixfreien Methoden" befasst. Der "LOBPCG" -Algorithmus ist vielversprechend, denke ich! @ Juan, die Cholesky-Faktorisierung ist immer noch ziemlich teuer.
Justin Solomon
Wenn Sie Matlab oder Oktave verwenden, verwenden Sie die eigs-routine. Es ist eine iterative Methode. Es gibt Optionen, um anzugeben, welchen Eigenwert Sie möchten, z . B. den kleinsten Realwert .
sebastian_g
Ich verstehe und benutze tatsächlich Eigs in Matlab. Aber wenn man Optionen wie „sm“ in GIE angeben, dann erfordert es die Inverse von statt . Überprüfen Sie die Tabelle in der Dokumentation: mathworks.com/help/matlab/ref/eigs.htmlA.AA
Justin Solomon

Antworten:

13
  1. Berechnen Sie den Eigenwert mit der größten Größe von (z. B. mit ). A.λmaxAeigs('lm')

  2. Berechnen Sie dann den größten (negativen) Eigenwert von (erneut durch einen Standardaufruf an ).M=A-λmaxIλ^maxM=AλmaxIeigs('lm')

  3. Beachten Sie, dass . Der Grund, warum dies gilt, wird hier erklärt .λ^max+λmax=λmin(A)

  4. Finden Sie Ihren Eigenvektor durch Lösen von .( A - λ m i n I ) v = 0v(AλminI)v=0

GoHokies
quelle