III. Les méthodes de Krylov

3.1 Qu’est-ce que l’espace de Krylov d’ordre p associé au point initial x₀ ?

Soit x₀ ∈ ℝⁿ, on note r₀ = A x₀ − b. L’espace de Krylov d’ordre p associé est défini par :
K(p) = vect{ r₀, A r₀, … , A^(p−1) r₀ }

3.2 Que dit le lemme sur la stabilité de l’espace de Krylov ? (truc à démontrer de krylov)

3.3 Qu'indique le lemme sur la suite des espaces de Krylov ?

3.4 Quelle condition décrit l’appartenance de la solution à un espace affine ?

Donner l'algorithme d'ortonormalisation d'Arnoldi?

Que dit la proposition admise sur l’ensemble vi formé par l’orthonormalisation d’Arnoldi ?

L’ensemble (vᵢ)ᵢ₌₁,ₚ forme une base orthonormale de K(p)

A quoi correspondent V(p), et (H(p+1, p))_ji ?

Image

Term

Definition

Quelles sont les relations entre A, V(p), V(p+1) et H(p), H(p+1,p) ?

• AV(p) = V(p+1) H(p+1, p)

• V(p)ᵗ A V(p) = H(p)

où H(p) = matrice p×p (égale à H(p+1, p)) obtenue en retirant la dernière ligne de

Qu’est-ce que la matrice H(p) et à quoi correspond-elle ?

Qu’est-ce qu’une méthode de Krylov et quels sont les deux éléments qui la définissent ?

Une méthode de Krylov consiste à construire itérativement (en p) une solution x_p ∈ x₀ + K(p). Elle est définie par :
• le choix de la base de K(p) qu’on utilise
• le critère d’optimalité qu’on souhaite optimiser

3.7 Définition (GMRES) - Qu’est-ce que la méthode GMRES et quels sont les deux éléments qui la définissent ?

3.8 Quelle relation fondamentale avons nous pour la méthode GMRES ?

3.9 - Donner la définition (matrice de rotation plane ou de Givens)

3.10 - Quelle est la spécificité concernant la matrice R₀(k,θ) ?

La matrice R₀(k,θ) est orthogonale.

Donner l'Algorithme de Givens (Décomposition QR)

Donner l'Algorithme GMRES

3.12 - Que peut-on dire du vecteur rₚ = A xₚ − b par rapport à Krylov ?

3.13 - A quoi est égal Gᵗ(p) A G(p) ?

3.11 - Quelle est la définition du (Gradient conjugué) et de sa méthode ?

Donner l'algorithme du gradient conjugué

2.10 Que dit le théorème concernant l’erreur de la solution approchée obtenue par CG ?

Soit xₚ la solution approchée obtenue par CG.

On a : ‖xₚ − x‖₂ ≤ Cᵗᵉ ( (√cond₂(A) − 1) / (√cond₂(A) + 1) )ᵏ ‖x₀ − x‖₂