Scribd
Importer
3 vues3 pages

Synthèse D'analyse Numérique: 1 Modèle Général D'un Schéma Itératif

Le document présente les méthodes itératives pour résoudre des systèmes linéaires, en commençant par le modèle général d'un schéma itératif et les conditions de convergence. Il décrit plusieurs méthodes classiques, telles que Jacobi, Gauss-Seidel et la méthode de relaxation, ainsi que l'algorithme du gradient conjugué et le préconditionnement. Chaque méthode est accompagnée de ses formules et propriétés essentielles pour assurer une convergence efficace.

Transféré par

bakolieutenant
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
3 vues3 pages

Synthèse D'analyse Numérique: 1 Modèle Général D'un Schéma Itératif

Le document présente les méthodes itératives pour résoudre des systèmes linéaires, en commençant par le modèle général d'un schéma itératif et les conditions de convergence. Il décrit plusieurs méthodes classiques, telles que Jacobi, Gauss-Seidel et la méthode de relaxation, ainsi que l'algorithme du gradient conjugué et le préconditionnement. Chaque méthode est accompagnée de ses formules et propriétés essentielles pour assurer une convergence efficace.

Transféré par

bakolieutenant
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Synthèse d’Analyse Numérique

Méthodes Itératives

1 Modèle général d’un schéma itératif


Principe général

Soit le système (S) : Ax = b avec A ∈ Mn×n (K) et b ∈ Kn . L’objectif est de générer une suite de
vecteurs (x(k) ) qui converge vers la solution A−1 b.

Forme de point fixe Le système (S) est transformé sous la forme :

x(k+1) = Bx(k) + c (1)

où B est la matrice d’itération et c un vecteur, choisis tels que I − B soit inversible et c = (I − B)A−1 b.

Théorème de convergence Les assertions suivantes sont équivalentes :


• La méthode itérative est convergente.

• limk→+∞ B k y = 0 pour tout y ∈ Kn .


• ρ(B) < 1, où ρ(B) désigne le rayon spectral de la matrice B.
• Il existe une norme matricielle subordonnée telle que ∥B∥ < 1.

Vitesse de convergence
• Taux moyen de convergence : Rk (B) = − ln(∥B k ∥1/k ).
• Taux asymptotique de convergence : R∞ (B) = − ln(ρ(B)).

• Propriété : Une méthode est d’autant plus rapide que ρ(B) est petit.

2 Méthodes itératives classiques


Toutes ces méthodes reposent sur la décomposition A = D − E − F où :
• D est la diagonale de A.
• E est la partie triangulaire inférieure stricte (ei,j = −ai,j si i > j).
• F est la partie triangulaire supérieure stricte (fi,j = −ai,j si i < j).

1
2.1 Méthode de Jacobi
Algorithme de Jacobi

• Décomposition : M = D et N = E + F .
• Matrice d’itération : BJ = D−1 (E + F ).
• Formule par composante :
 
n
(k+1) 1  X (k) 
xi = bi − ai,j xj (2)
ai,i
j=1,j̸=i

2.2 Méthode de Gauss-Seidel


Algorithme de Gauss-Seidel

• Décomposition : M = D − E et N = F .
• Matrice d’itération : BGS = (D − E)−1 F .
• Formule par composante :
 
i−1 n
(k+1) 1  X (k+1)
X (k)
xi = bi − ai,j xj − ai,j xj  (3)
ai,i j=1 j=i+1

2.3 Méthode de Relaxation


1 1−ω
• Décomposition : M = ω (D − ωE) et N = ω D + F.
• Propriété : Si ω = 1, on retrouve Gauss-Seidel.

3 Méthode du Gradient Conjugué


Définition : Matrice définie positive A est définie positive si pour tout x ̸= 0, xT Ax > 0.

Itérations du Gradient Conjugué

Pour x(0) donné, r(0) = b − Ax(0) :


(r (k) )T r (k)
• βk = (r (k−1) )T r (k−1)

• p(k) = r(k) + βk p(k−1)


(r (k) )T r (k)
• αk = (p(k) )T Ap(k)

• x(k+1) = x(k) + αk p(k)


• r(k+1) = r(k) − αk Ap(k)
Algorithme du Gradient Conjugué

Propriété fondamentale L’algorithme converge en au plus n itérations car les résidus sont orthogonaux
et les directions p(k) sont A-conjuguées.

2
4 Préconditionnement
Principe Remplacer Ax = b par un système mieux conditionné Ãx̃ = b̃ avec à = C −1 A(C −1 )T . Le
préconditionneur est la matrice M = CC T .

Formules de Cholesky Incomplet


v
u
u i−1
X
li,i = tai,i − 2
li,r
r=1

j−1
!
1 X
li,j = ai,j − li,r lj,r si ai,j ̸= 0
lj,j r=1
Exemple : Cholesky Incomplet

Vous aimerez peut-être aussi