6.2 Résolution numérique du problème électronique
151
où
n
1 ≤
n
2 ≤ · · · ≤
n
N sont les N plus petites valeurs propres de
F (D n−1 )Φ = SΦ
et où les colonnes de C n sont des vecteurs propres S-orthogonaux associés.
Cet algorithme est connu sous le nom d’algorithme de Roothaan [196]. Notons
qu’il s’écrit aussi sous la forme compacte (voir exercice 6.4)
D n = arginf {Tr(F (D n−1 )D), D ∈ P N } .
Cet algorithme fonctionne correctement sur des systèmes chimiques simples
(composés de trois ou quatre atomes de la première ligne du tableau périodique : Hydrogène, Carbone, Azote, Oxygène, ...) à condition d’utiliser des
bases de petite taille. Toutes les simulations effectuées dans les premiers temps
de la chimie computationnelle s’effectuaient dans ce cadre, et c’est la raison
pour laquelle l’algorithme de Roothaan a été utilisé pendant une vingtaine
d’années sans que cela pose trop de problèmes. Quand les ordinateurs ont
permis de faire tourner des calculs plus importants, l’algorithme de Roothaan
s’est révélé insuffisant : en général, il ne converge pas. Plusieurs algorithmes
ont été proposés pour tenter de remédier à cette situation, qu’on peut classer
en deux catégories :
1. les algorithmes consistant, comme celui de Roothaan, à résoudre les équations d’Euler-Lagrange (6.14) par une méthode de point fixe ; c’est la
stratégie employée dans la quasi-totalité des codes antérieurs à ce jour ;
2. les algorithmes consistant à résoudre directement le problème d’optimisation sous contrainte (6.8).
Dans la première catégorie, mentionnons l’algorithme de level-shifting [201]
(voir ci-dessous), l’algorithme de damping [233] et surtout l’algorithme DIIS
[184], qui est encore à l’heure actuelle le plus utilisé. L’algorithme DIIS
converge vite quand il converge mais ne converge pas toujours et converge dans
de nombreux cas vers un minimum local non global. Dans la seconde catégorie, citons l’algorithme de steepest descent [166] (il s’agit d’une méthode de
gradient projeté), l’algorithme de Bacskay [10] (réécriture du problème (6.8)
sous la forme d’un problème d’optimisation sans contrainte et mise en œuvre
de l’algorithme de Newton), ainsi que ses variantes de type quasi-Newton
[69, 87], et l’algorithme de Shepard [209] (méthode de Hessien réduit pour
résoudre (6.8)). Les algorithmes de la seconde catégorie convergent toujours
vers un minimum local mais ce minimum local est rarement le minimum global pour les systèmes et/ou les bases de grande taille. Tous ces algorithmes
sont décrits en détail dans [50], sections 29 et 30.
Au Chapitre 8, nous étudions en détail les propriétés de convergence des algorithmes de Roothaan et de level shifting, ce dernier étant défini par
⎧
⎨
⎩
(F (D n−1 ) − bD n−1 ) C n = SC n E n
E n = Diag(
n
1 , · · · , ,
n
N )
C
T
n SC n = I N
D n = C n C
T
n
151
où
n
1 ≤
n
2 ≤ · · · ≤
n
N sont les N plus petites valeurs propres de
F (D n−1 )Φ = SΦ
et où les colonnes de C n sont des vecteurs propres S-orthogonaux associés.
Cet algorithme est connu sous le nom d’algorithme de Roothaan [196]. Notons
qu’il s’écrit aussi sous la forme compacte (voir exercice 6.4)
D n = arginf {Tr(F (D n−1 )D), D ∈ P N } .
Cet algorithme fonctionne correctement sur des systèmes chimiques simples
(composés de trois ou quatre atomes de la première ligne du tableau périodique : Hydrogène, Carbone, Azote, Oxygène, ...) à condition d’utiliser des
bases de petite taille. Toutes les simulations effectuées dans les premiers temps
de la chimie computationnelle s’effectuaient dans ce cadre, et c’est la raison
pour laquelle l’algorithme de Roothaan a été utilisé pendant une vingtaine
d’années sans que cela pose trop de problèmes. Quand les ordinateurs ont
permis de faire tourner des calculs plus importants, l’algorithme de Roothaan
s’est révélé insuffisant : en général, il ne converge pas. Plusieurs algorithmes
ont été proposés pour tenter de remédier à cette situation, qu’on peut classer
en deux catégories :
1. les algorithmes consistant, comme celui de Roothaan, à résoudre les équations d’Euler-Lagrange (6.14) par une méthode de point fixe ; c’est la
stratégie employée dans la quasi-totalité des codes antérieurs à ce jour ;
2. les algorithmes consistant à résoudre directement le problème d’optimisation sous contrainte (6.8).
Dans la première catégorie, mentionnons l’algorithme de level-shifting [201]
(voir ci-dessous), l’algorithme de damping [233] et surtout l’algorithme DIIS
[184], qui est encore à l’heure actuelle le plus utilisé. L’algorithme DIIS
converge vite quand il converge mais ne converge pas toujours et converge dans
de nombreux cas vers un minimum local non global. Dans la seconde catégorie, citons l’algorithme de steepest descent [166] (il s’agit d’une méthode de
gradient projeté), l’algorithme de Bacskay [10] (réécriture du problème (6.8)
sous la forme d’un problème d’optimisation sans contrainte et mise en œuvre
de l’algorithme de Newton), ainsi que ses variantes de type quasi-Newton
[69, 87], et l’algorithme de Shepard [209] (méthode de Hessien réduit pour
résoudre (6.8)). Les algorithmes de la seconde catégorie convergent toujours
vers un minimum local mais ce minimum local est rarement le minimum global pour les systèmes et/ou les bases de grande taille. Tous ces algorithmes
sont décrits en détail dans [50], sections 29 et 30.
Au Chapitre 8, nous étudions en détail les propriétés de convergence des algorithmes de Roothaan et de level shifting, ce dernier étant défini par
⎧
⎨
⎩
(F (D n−1 ) − bD n−1 ) C n = SC n E n
E n = Diag(
n
1 , · · · , ,
n
N )
C
T
n SC n = I N
D n = C n C
T
n