Quel est le principe derrière la convergence des méthodes du sous-espace de Krylov pour résoudre des systèmes d'équations linéaires?

24

Si je comprends bien, il existe deux grandes catégories de méthodes itératives pour résoudre des systèmes linéaires d'équations:

  1. Méthodes stationnaires (Jacobi, Gauss-Seidel, SOR, Multigrid)
  2. Méthodes Krylov Subspace (Gradient Conjugué, GMRES, etc.)

Je comprends que la plupart des méthodes stationnaires fonctionnent en relaxant de manière itérative (lissage) les modes de Fourier de l'erreur. Si je comprends bien, la méthode du gradient conjugué (méthode du sous-espace de Krylov) fonctionne en "progressant" à travers un ensemble optimal de directions de recherche à partir des puissances de la matrice appliquées au n ème résiduel. Ce principe est-il commun à toutes les méthodes du sous-espace de Krylov? Sinon, comment caractérisons-nous le principe de la convergence des méthodes du sous-espace de Krylov, en général?

Paul
la source
2
Votre analyse des méthodes stationnaires est biaisée par de simples problèmes de modèle, car ceux-ci peuvent être analysés en termes de modes de Fourier. Il ignore également l'alternance de direction implicite (ADI) et de nombreuses autres méthodes. Le but de la plupart des "méthodes stationnaires" est de combiner de nombreux solveurs "partiels approximatifs" simples en un seul solveur itératif. Le but des méthodes de Krylov est d'accélérer (voire d'imposer) la convergence d'une itération linéaire stationnaire donnée.
Thomas Klimpel
4
Je pense qu'un document qui a été écrit pour répondre à vos questions est Ipsen et Meyer, L'idée derrière les méthodes de Krylov, Amer. Math. Mensuel 105 (1998) pp. 889-899. C'est un document merveilleusement bien écrit et clarifiant, disponible ici .
Andrew T.Barker
@ AndrewT.Barker: Génial! Merci Andrew! :)
Paul

Réponses:

21

En général, toutes les méthodes de Krylov recherchent essentiellement un polynôme qui est petit lorsqu'il est évalué sur le spectre de la matrice. En particulier, le ème résidu d'une méthode de Krylov (avec une supposition initiale nulle) peut être écrit sous la formen

rn=Pn(A)b

est un polynôme monique de degré n .Pnn

Si est diagonalisable, avec A = V Λ V - 1 , on aAA=VΛV1

rnVPn(Λ)V1b=κ(V)Pn(Λ)b.

Dans le cas où est normal (par exemple, symétrique ou unitaire), nous savons que GMRES construit un tel polynôme via l'itération Arnoldi, tandis que CG construit le polynôme en utilisant un produit interne différent (voir cette réponse pour plus de détails ). De même, BiCG construit son polynôme à travers le processus non symétrique de Lanczos, tandis que l'itération de Chebyshev utilise des informations préalables sur le spectre (généralement des estimations des valeurs propres les plus grandes et les plus petites pour les matrices définies symétriques).κ ( V ) = 1.Aκ(V)=1.

Comme exemple sympa (motivé par Trefethen + Bau), considérons une matrice dont le spectre est le suivant:

Spectre de matrice

Dans MATLAB, j'ai construit cela avec:

A = rand(200,200);
[Q R] = qr(A);
A = (1/2)*Q + eye(200,200);

Si nous considérons GMRES, qui construit des polynômes qui minimisent réellement le résidu sur tous les polynômes moniques de degré , nous pouvons facilement prédire l'historique résiduel en examinant le polynôme candidatn

Pn(z)=(1z)n

qui dans notre cas donne

|Pn(z)|=12n

pour dans le spectre de .AzA

Maintenant, si nous exécutons GMRES sur un RHS aléatoire et comparons l'historique résiduel avec ce polynôme, ils devraient être assez similaires (les valeurs polynomiales candidates sont plus petites que le résidu GMRES parce que ):b2>1

Antécédents résiduels

Reid.Atcheson
la source
Pourriez-vous clarifier ce que vous entendez par "petit sur le spectre de la matrice"?
Paul
2
Prise comme un polynôme complexe, le polynôme a faible module dans une région du plan complexe qui comprend le spectre de . Imaginez un tracé de contour superposé à un diagramme de dispersion des valeurs propres. Comment petit est petit? Cela dépend du problème, de savoir si est normal et du côté droitL'idée de base est cependant que la séquence de polynômes cherche à devenir de plus en plus petite sur le spectre de sorte que l'estimation résiduelle dans ma réponse tend vers . PnAAb.(Pn)0
Reid.Atcheson
@ Reid.Atcheson: Très bien dit. Puis-je recommander d'écrirecommeκ(V)VV1κ(V) et en mentionnant qu'il en est un pour les matrices normales?
Jack Poulson
Le Laplacien préconditionné par le SOR optimal a un spectre très similaire à cet exemple de matrice. Détails ici: scicomp.stackexchange.com/a/852/119
Jed Brown
A strictement parler, le CGNE est indépendant du spectre puisqu'il ne dépend que de valeurs singulières.
Jed Brown
17

Sur les normes

nthPn2

rn=Axnb=(Pn(A)1)bb=Pn(A)b.

AAA1

rnA1=rnTA1rn=(Aen)TA1Aen=enTAen=enA

où nous avons utilisé l'erreur

en=xnx=xnA1b=A1rn

AA1A2ATAA

Netteté des limites de convergence

Enfin, il existe une littérature intéressante concernant les différentes méthodes et subtilités de Krylov de la convergence GMRES, en particulier pour les opérateurs non normaux.

Jed Brown
la source
Vous avez laissé l'excellent livre d'Olavi Nevanlinna: books.google.com/…
Matt Knepley
11

Méthodes itératives en bref:

  1. Ax=bC

    x=x+CbCAx
    ICA<1CC=D1DA
  2. U,VCnx~UbAx~VUAVV=UV=AU

    Vx~UU

    UAx~

    Ceci est bien expliqué dans le livre de Youcef Saad sur les méthodes itératives .

Christian Clason
la source