# Sur le couplage d'accélérateurs de convergence et de correcteurs itératifs

Jean-Marc M Cadou, Noureddine Damil, Michel Potier-Ferry

► To cite this version:

Jean-Marc M Cadou, Noureddine Damil, Michel Potier-Ferry. Sur le couplage d'accélérateurs de convergence et de correcteurs itératifs. 7e colloque national en calcul des structures, CSMA, May 2005, Giens, France. hal-01812900

HAL Id: hal-01812900

https://hal.science/hal-01812900v1

Submitted on 12 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC0 1.0 - Universal - International License
# Sur le couplage d'accélérateurs de convergence et de correcteurs itératifs

J.M. CADOUª, N. DAMILᵇ, M. POTIER-FERRYᶜ

RÉSUMÉ. Ce travail porte sur l'accélération de la convergence de correcteurs itératifs, tels que la méthode de Newton-Raphson modifié ou les correcteurs d'ordre élevé récemment définis dans la référence [DAM 99]. L'objectif est de diminuer le nombre d'itérations de ces correcteurs. Trois techniques d'accélération de la convergence sont étudiées : l'e-algorithme, une technique d'extrapolation (MMPE) et les approximants de Padé. Les tests numériques sont réalisés sur des exemples de flambage non-linéaire élastique de coques minces.

**ABSTRACT.** This work deals with the convergence acceleration of iterative correctors. Three techniques are evaluated on numerical examples from nonlinear elastic thin shell problems.

**MOTS-CLÉS :** Accélération de la convergence, correcteurs itératifs, approximants de Padé, e-algorithme, méthode d'extrapolation

**KEYWORDS:** Convergence acceleration, iterative correctors, Padé approximants, e-algorithm, extrapolation methods

<footnote>ª LG2M, Université de Bretagne Sud, Rue de Saint Maudé, B.P. 92116, 56321 Lorient Cedex - France.</footnote>

<footnote>jean-marc cadou@univ-ubs.fr</footnote>

<footnote>ᵇ LCSM, Faculté des Sciences Ben M'Sik Université Hassan II - BP 7955 Casablanca - Maroc, n.damil@univh2m.ac.ma</footnote>

<footnote>ᶜ LPMM, I.S.G.M.P., Université de Metz, Ile du Saulcy, 57045, Metz - France, potier-ferry@lpmm.univ-metz.fr</footnote>
# 1. Introduction

La résolution numérique de problèmes non-linéaires s’accompagne généralement de deux phases : une première dite de prédiction et une deuxième phase de correction. Dans des travaux récents [LAH 02], des méthodes de prédiction d’ordre élevé (basés sur la méthode asymptotique numérique) ont été couplées à des correcteurs d’ordre également élevé (basés sur des techniques d’homotopie et sur les approximants de Padé [DAM 99]). Parmi ces correcteurs, habituellement référencés L\*-algorithme, on peut discerner deux familles : une première qui s’appuie lors de la phase de correction sur une triangulation de matrice consistante (un correcteur de type Newton-Raphson d’ordre élevé : L\*-consistant) et qui conduit à une convergence rapide mais coûteuse en terme de temps CPU. La deuxième famille de correcteurs s’appuie elle sur une matrice de correction déjà triangulée (issue généralement de la phase de prédiction), qui ne conduit pas à des temps CPU importants mais qui, en contre partie, demandent un certain nombre d’itérations pour obtenir la qualité de solution demandée (L\*-itératif). Pour améliorer les performances de ces correcteurs, on peut alors les coupler à des techniques d’accélérations de la convergence.

L’objectif de ce travail est d’étudier le couplage entre les correcteurs d’ordre élevé et des techniques d’accélération de la convergence. Trois types d’accélérateurs de convergence seront étudés : les $\epsilon$-algorithme [JBI 00], les techniques d’extrapolation polynomiale [JBI 00] et les approximants de Padé [DAM 99]. Les applications présentées dans ce travail sont issues de problèmes de flambage non-linéaire de coques minces. On considère le problème non-linéaire suivant :

$$R(U, \lambda) = 0 \qquad [1]$$

avec $U$ le vecteur inconnu du problème (le déplacement et la contrainte) et $\lambda$ un paramètre de chargement. On suppose que suite à une étape de prédiction, le couple $(U_p, \lambda_p)$ ne satisfait pas le critère de qualité retenue, soit :

$$\|R(U_p, \lambda_p)\| > \qquad [2]$$

avec $\epsilon$ la valeur de la précision souhaitée. On utilise alors un correcteur, de telle manière à obtenir une solution corrigée qui vérifie :

$$\|R(U_c, \lambda_c)\| < \epsilon \text{ avec } (U_c, \lambda_c) = (U_p, \lambda_p) + \sum_{iter=1}^{niter} (\Delta U_i, \Delta \lambda_i) \qquad [3]$$

où $(\Delta U_i, \Delta \lambda_i)$ désigne les itérés $i$ du correcteur utilisé. Lorsque l’on utilise un correcteur de type Newton-modifié, ou bien un algorithme L\*-itératif [DAM 99], le nombre d’itérations pour satisfaire le critère de l’expression (3) peut devenir important. Pour diminuer ce nombre d’itérations, on propose dans ce travail de remplacer les séquences (3) (ou suites) soit :

- par la construction d’une nouvelle solution $(U_c^*, \lambda_c^*)$, pour le $\epsilon$-algorithme [JBI 00],

- par une nouvelle séquence comme les approximants de Padé [DAM 99] ou la méthode d’extrapolation [JBI 00],

et qui conduit à une solution de meilleure qualité que la suite originale.
## 2. Comparaisons numériques

Nos premiers essais de couplage de correcteurs itératifs et de méthodes d'accélération de la convergence concernent les méthodes de Newton-modifiées et les correcteurs d'ordre élevé de type L\*-itératif. Les tests numériques sont réalisés sur un exemple traditionnel de flambage élastique non-linéaire de coque : toit épais encastré sur deux côtés, libre sur ses deux autres et chargé en son milieu par une force verticale. Les caractéristiques géométriques et matérielles de cet exemple sont données dans la figure (1). La résolution se fait par la méthode des éléments finis, le maillage utilisé est constitué de 200 éléments triangulaires de type DKT, soit un nombre de degrés de liberté de 726. La courbe "prédiction" (figure 2) est obtenue avec la MAN et un

<figure><img src="image_2.png" /><figcaption>**Figure 1.** Caractéristiques de l'exemple présenté.</figcaption></figure>

approximant de Padé à l'ordre 25. Sur cette courbe prédiction, nous avons choisi un point (point 3 sur la courbe de la figure 2, le logarithme du vecteur résidu est égal à 0.45) pour évaluer les performances des accélérateurs de convergence. Nous présentons sur la figure 3 l'évolution de la norme du résidu en fonction du nombre d'itération pour les trois types d'accélérateurs étudiés. La méthode de correction utilisée dans ce cas est la méthode de Newton-modifiée. Les résultats présentés sur la figure 3 nous

<figure><img src="image_3.png" /><figcaption>**Figure 2.** Visualisation des points à corriger sur la courbe de réponse.</figcaption></figure>
montrent que les trois techniques étudiées améliorent considérablement la qualité de
la solution. En effet, la norme du vecteur résidu avec la méthode de Newton-modifiée
au bout de 30 itérations est environ égale à $10^{-1}$. Couplée à une méthode d'accélé-
ration de la convergence, cette norme du résidu est égale, après 30 itérations, à $10^{-5}$
pour le MMPE, $10^{-7}$ pour l'ε-algorithme et $10^{-9}$ pour les approximants de Padé.
Cette courbe montre également que la technique MMPE devient instable lorsque le
nombre d'itérations (i.e. le nombre de vecteurs) est important (vers la 15ième itéra-
tion, figure 3). En effet on peut remarquer sur la figure (3) que lorsque le nombre
d'itérations est supérieur à 15, cela ne conduit pas à une amélioration de la qualité
de la solution (le logarithme du vecteur résidu est proche de -5 pour les itérations 15
et 30). Dans certains cas (pour le point 2 de la figure (2) par exemple), augmenter le
nombre d'itérations conduit même à la déterioration de la solution. Cette instabilité
peut être évitée notamment en fixant le nombre maximum d'itérations du correcteur
et par conséquent le nombre maximum de vecteurs composant la suite (3). A partir
de ce nombre fixé de vecteurs, on construit un vecteur solution par une technique
d'accélération de la convergence (par exemple MMPE). Si la qualité de ce vecteur
n'est pas satisfaisante (le critère (3) n'est pas vérifié), une nouvelle phase de correc-
tion démarre avec comme nouveau point ($U_p, \lambda_p$) le point issu de la phase précédente
d'accélération. A noter cependant que cette technique de réinitialisation ne nécessite
par de nouvelle triangulation de matrice tangente. La matrice tangente utilisée pour
toutes les réinitialisations est celle qui a été construite et triangulée lors du calcul de
la première séquence (3). Cette technique, dite de réinitialisation, a été testée sur le
point 3 de la figure 3 et les résultats obtenus, pour le MMPE, sont présentés sur la

<figure><img src="image_4.png" /><figcaption>**Figure 3.** Evolution de la norme du résidu en fonction des itérations de Newton-modifié. Comparaison des trois méthodes d'accélération de la convergence.</figcaption></figure>

figure 4. Nous présentons sur cette courbe les évolutions du logarithme du vecteur résidu en fonction de l'itération pour 3 valeurs du paramètre de reinitialisation : après 5, 10 et 15 itérations. Nous présentons également sur cette courbe les résultats obtenus avec la technique des approximants de Padé (prise ici comme référence) ainsi que les résultats obtenus avec le MMPE sans réinitialisation. Cette figure montre que la réinitialisation a permis d'enlever les problèmes d'instabilités mis en évidence sur la figure 3. En effet, on obtient une norme du résidu inférieure à $10^{-10}$ en réinitiali-
<figure><img src="image_5.png" /><figcaption>**Figure 4.** Evolution de la norme du résidu en fonction des itérations de Newton-modifié. Trois essais de réinitialisation du MMPE : après 5,10 et 15 itérations.</figcaption></figure>

sant le processus après 5, 10 ou 15 itérations alors que sans réinitialisation la qualité de la solution stagne vers $10^{-5}$. La qualité de la solution obtenue par cette méthode est également meilleure que celle obtenue avec les approximants de Padé (figure 4). L'intérêt de réinitiliser la technique MMPE est double : elle permet en effet de stabiliser l'algorithme d'accélération de la convergence et elle conduit également à une diminution du nombre d'itérations nécessaires pour obtenir la précision souhaitée. Dans un travail récent [DAM 04], les auteurs ont montré qu'il existait une autre solution pour éliminer les instabilités qui apparaîssent avec le MMPE lorsque le nombre d'itérations devient important. En effet en intégrant, lors de la construction de la solution accélérée, une phase d'ortho-nomalisation des vecteurs on élimine alors ces instabilités. Dans ce travail, les auteurs ont également montré que grâce à cette phase d'ortho-normalisation, le MMPE et les approximants de Padé sont équivalents (voir [DAM 04]). Ces techniques d'accélérations de la convergence sont maintenant couplées à des correcteurs d'ordre élevé [DAM 99], communément appelés correcteurs L*-itératif. Ces techniques utilisent lors de la correction une matrice tangente non-consistante. Dans les exemples présentés dans ce travail, la matrice utilisée est celle qui a permis de calculer la courbe prédiction, et plus précisément la matrice tangente calculée au point (U = 0, λ = 0). La méthode de Newton-Raphson modifiée demande lors de la correction une triangulation de matrice lors de la première itération alors que le correcteur L*-itératif n'en nécessite aucune. Nous présentons dans le tableau 1 le nombre d'itérations nécessaires pour obtenir une norme du résidu inférieure à $10^{-8}$. Ces tests numériques sont également réalisés pour le point 3 de la figure 3. Nous considérons ici trois algorithmes L*-itératif : aux ordres 5,10 et 15. Ces trois algorithmes se distinguent essentiellement par le nombre de vecteurs seconds membres qui sont à calculer. L'ordre 5 signifie grossièrement que 5 seconds membres sont calculés et que cet algorithme nécessite 5 résolutions (5 montées/descentes d'un solveur linéaire). Ces algorithmes L*-itératif sont détaillés dans la référence [DAM 99]. Concernant le couplage de ces correcteurs avec les techniques d'accélérations de la convergence, le tableau 1 montre l'efficacité de ces associations. En effet sans accélération, les correcteurs L*-itératif à l'ordre 5,10 et 15 demandent respectivement 26, 16 et 16 itéra-
<table><caption>**Tableau 1.** Nombre d'itérations pour obtenir un résidu inférieur à $10^{-8}$ (point 3). Entre parenthèse le logarithme décimal obtenu après 30 itérations.</caption><thead><tr><th></th><th>Newton-Modifié</th><th>L*-itératif. ordre 5</th><th>L*-itératif. ordre 10</th><th>L*-itératif. ordre 15</th></tr></thead><tbody><tr><td>Sans accel.</td><td>(-1.38)</td><td>26</td><td>16</td><td>16</td></tr><tr><td>ε-algo.</td><td>(-7.44)</td><td>18</td><td>10</td><td>10</td></tr><tr><td>MMPE</td><td>(-5.16)</td><td>15</td><td>9</td><td>10</td></tr><tr><td>Padé</td><td>23</td><td>15</td><td>9</td><td>10</td></tr></tbody></table>

tions pour converger jusqu'à la précision souhaitée ($10^{-8}$) alors qu'en utilisant soit le MMPE, soit les approximants de Padé, ce nombre d'itérations devient 15, 9 et 10. Ce couplage conduit dans certains cas à une réduction du nombre d'itérations de presque 40 %. Le tableau 1 montre également que parmi ces trois techniques d'accélération de la convergence, ceci quel que soit le correcteur utilisé, le MMPE et les approximants de Padé semblent être les plus efficaces.

### 3. Conclusion

Dans ce travail on a montré qu'il était possible de diminuer le nombre d'itérations de correcteurs (Newton-modifié et correcteurs d'ordre élevé) et ceci pour un faible temps supplémentaire de calculs. L'utilisation des approximants de Padé pour accélérer la convergence de correcteurs itératifs est une originalité de ce travail. En effe cette technique est traditionnellement utilisée pour améliorer le rayon de convergence de séries de Taylor [DAM 99, LAH 02]. Les tests numériques réalisés dans cette étude semblent montrer que la méthode MMPE est la technique la plus efficace : temps de calculs moins importants pour une meilleure accélération de la convergence des itérés. La méthode $\epsilon$-algorithme est par contre assez difficile à utiliser dans un contexte éléments finis. En effet, la dimension des vecteurs à accélérer peut être importante et conduit alors à des temps CPU exceptionnellement grands. Ces méthodes d'accélérations de la convergence sont actuellement couplées à d'autres types de correcteurs.

### 4. Bibliographie

[DAM 99] DAMIL N.AND POTIER-FERRY M., NAJAH A., CHARI R., LAHMAM H., « An iterative method based upon Padé approximants », *Comm. Numer. Meth. Engng*, vol. 44(2), 1999, p. 155-176.

[DAM 04] DAMIL N.AND CADOU J., POTIER-FERRY M., « Mathematical and numerical connections between polynomial extrapolation and Padé approximants : applications in structural mechanics », *Comm. Numer. Meth. Engng*, vol. 20, 2004, p. 699-707.

[JBI 00] JBILOU K., SADOK H., « Vector extrapolation methods. Application and numerical comparison », *J. Comp. Appl. Math.*, vol. 122, 2000, p. 149-165.

[LAH 02] LAHMAM H., CADOU J., DAMIL N., POTIER-FERRY M., « High-order predictor-corrector algorithms », *Int. J. Numer. Meth. Engng*, vol. 55, 2002, p. 685-704.