Méthode du gradient biconjugué

Méthode du gradient biconjugué

En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d'équations linéaires

A x= b.\,

Contrairement à la méthode du gradient conjugué, cet algorithme ne nécessite pas que la matrice A soit auto-adjointe, en revanche, la méthode requiert des multiplications par la matrice adjointe A * .

L'algorithme

  1. Choisir x0, y0, un préconditionneur régulier M (on utilise fréquemment M − 1 = 1) et c;
  2. r_0 \leftarrow b-A x_0, s_0 \leftarrow c-A^* y_0\,;
  3. d_0 \leftarrow M^{-1} r_0, f_0 \leftarrow M^{-*} s_0\,;
  4. for k=0, 1, \dots\, do
  5. \alpha_k \leftarrow {s^*_k M^{-1} r_k \over f_k^* A d_k}\,;
  6. x_{k+1} \leftarrow x_k+ \alpha_k d_k\, \left( y_{k+1} \leftarrow y_k + \overline{\alpha_k} f_k \right)\,;
  7. r_{k+1} \leftarrow r_k- \alpha_k A d_k \,, s_{k+1} \leftarrow s_k- \overline{\alpha_k} A^* f_k \, (rk = bAxk et sk = cA * yk sont le résidus);
  8. \beta_k \leftarrow {s_{k+1}^* M^{-1} r_{k+1} \over s^*_k M^{-1} r_k}\,;
  9. d_{k+1} \leftarrow M^{-1} r_{k+1} + \beta_k d_k\,, f_{k+1} \leftarrow M^{-*} s_{k+1} + \overline{\beta_k} f_k\,.

Discussion

La méthode est numériquement instable, mais on y remédie par la méthode stabilisée du gradient biconjugué (en), et elle reste très importante du point de vue théorique : on définit l'itération par x_k:=x_j+ P_k A^{-1}\left(b - A x_j \right) et y_k:=y_j+A^{-*}P_k^*\left(c-A^* y_j \right) (j < k) en utilisant les projections suivantes :

P_k:= \mathbf{u_k} \left(\mathbf{v_k}^* A \mathbf{u_k} \right)^{-1} \mathbf{v_k}^* A,

Avec \mathbf{u_k}=\left(u_0, u_1, \dots u_{k-1} \right) et \mathbf{v_k}=\left(v_0, v_1, \dots v_{k-1} \right). On peut irérer les projections elles-mêmes, comme

P_{k+1}= P_k+ \left( 1-P_k\right) u_k \otimes {v_k^* A\left(1-P_k \right) \over v_k^* A\left(1-P_k \right) u_k}.

Les nouvelles directions de descente d_k:= \left(1-P_k \right) u_k et f_k:= \left( A \left(1- P_k \right) A^{-1} \right)^* v_k sont alors orthogonales aux résidus : v_i^* r_k= f_i^* r_k=0 et s_k^* u_j = s_k^* d_j= 0, qui satisfont aux-même r_k= A \left( 1- P_k \right) A^{-1} r_j et s_k= \left( 1- P_k \right) ^* s_j(i,j < k).

La méthode du gradient biconjugué propose alors le choix suivant :

uk: = M − 1rk et vk: = M − * sk.

Ce choix particulier permet alors d'éviter une évaluation directe de Pk et A − 1, et donc augmenter la vitesse d'execution de l'algorithme.

Propriétés

  • En dimensions finies xn = A − 1b, au plus tard quand Pn = 1 : La méthode du gradient biconjugué rend la solution exacte après avoir parcouru tout l'espace et est donc une méthode directe.
  • La suite produite par l'algorithme est biorthogonale (en) : f_i^* A d_j = 0 et s_i^* M^{-1} r_j=0 pour i \ne j.
  • SI pj' est un polynôme avec deg\left( p_{j'} \right) +j <k , alors s_k^* p_{j'}\left(M^{-1} A \right) u_j=0. L'algorithme est donc composé de projections sur des sous-espaces de Krylov (en) ;
  • SI pi' est un polynôme avec i+deg\left( p_{i'} \right) <k , alors v_i^* p_{i'}\left(A M^{-1} \right) r_k=0.



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode du gradient biconjugué de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Methode du gradient biconjugue — Méthode du gradient biconjugué En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d équations linéaires Contrairement à la méthode du gradient conjugué …   Wikipédia en Français

  • Méthode Du Gradient Biconjugué — En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d équations linéaires Contrairement à la méthode du gradient conjugué, cet algorithme ne nécessite… …   Wikipédia en Français

  • Methode du gradient conjugue — Méthode du gradient conjugué En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d équations linéaires dont la matrice est symétrique et définie positive. Cette méthode est une méthode itérative. La… …   Wikipédia en Français

  • Méthode Du Gradient Conjugué — En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d équations linéaires dont la matrice est symétrique et définie positive. Cette méthode est une méthode itérative. La méthode du gradient… …   Wikipédia en Français

  • Méthode du gradient conjugué — En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d équations linéaires dont la matrice est définie positive (et par conséquent symétrique). Cette méthode, imaginée en 1950 simultanément par… …   Wikipédia en Français

  • Gradient conjugué — Méthode du gradient conjugué En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d équations linéaires dont la matrice est symétrique et définie positive. Cette méthode est une méthode itérative. La… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Stabilité numérique — En analyse numérique, une branche des mathématiques, la stabilité numérique est une propriété globale d’un algorithmique numérique, une qualité nécessaire pour espérer obtenir des résultats ayant du sens. Une définition rigoureuse de la stabilité …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”