Plus petite valeur propre sans inverse

11

Supposons que ARn×n est une matrice définie symétrique positive. A est suffisamment grand pour qu'il soit coûteux de résoudre directement .Ax=b

Existe-t-il un algorithme itératif pour trouver la plus petite valeur propre de qui n'implique pas l'inversion de à chaque itération?AA

Autrement dit, je devrais utiliser un algorithme itératif comme les gradients conjugués pour résoudre , donc l'application répétée de A - 1 semble être une «boucle interne» coûteuse. Je n'ai besoin que d'un seul vecteur propre.Ax=bA1

Merci!

Justin Solomon
la source
1
Avez-vous essayé d'utiliser la décomposition Cholesky? Vous devez factoriser en L L T avec L étant une matrice triangulaire. Une fois que vous avez la factorisation (vous ne le faites qu'une seule fois), vous pouvez l'utiliser à chaque itération pour résoudre le système très rapidement par substitution avant et arrière. ALLTL
Juan M. Bello-Rivas
A est-il une matrice clairsemée?
Tolga Birdal
a une certaine structure de blocs, mais je préférerais ne pas jouer avec si je n'ai pas à le faire - alors je cherchais des "méthodes sans matrice". L'algorithme "LOBPCG" est prometteur, je pense! @Juan, la factorisation de Cholesky est encore assez chère. A
Justin Solomon
Si vous utilisez matlab ou octave, utilisez la eigsroutine. C'est une méthode itérative. Il existe des options pour spécifier la valeur propre que vous souhaitez, par exemple le plus petit réel .
sebastian_g
Je comprends et utilise en effet des eigs dans matlab. Mais si vous spécifiez des options comme « sm » dans GIEs, il nécessite l'inverse de plutôt que A . Consultez le tableau dans la documentation: mathworks.com/help/matlab/ref/eigs.htmlAA
Justin Solomon

Réponses:

13
  1. Calculez la valeur propre de plus grande amplitude de A (avec, disons ).λmaxAeigs('lm')

  2. Calculer alors la plus grande amplitude (négative) de valeurs propres λ m un x de M = A - λ m a x I (encore une fois, par un appel à la norme ).λ^maxM=AλmaxIeigs('lm')

  3. Observer que λ m a x + λ max = λ m i n ( A ) . La raison pour laquelle cela tient est expliquée ici .λ^max+λmax=λmin(A)

  4. Trouvez votre vecteur propre en résolvant ( A - λ m i n I ) v = 0 .v(AλminI)v=0

GoHokies
la source