Clefs n°70 mars 2020
Clefs n°70 mars 2020
  • Prix facial : gratuit

  • Parution : n°70 de mars 2020

  • Périodicité : annuel

  • Editeur : CEA

  • Format : (230 x 280) mm

  • Nombre de pages : 52

  • Taille du fichier PDF : 7,8 Mo

  • Dans ce numéro : sacrées mathématiques !

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 26 - 27  |  Aller à la page   OK
Pages suivantes >
26 27
LES OUTILS ANALYSE NUMÉRIQUE PAR ISABELLE RAMIÈRE (Direction de l’énergie nucléaire) Isabelle Ramière est ingénieur-chercheur en méthodes numériques, au Département d’études des combustibles du CEA, à Cadarache. Fig. 1  : exemple de problème de point fixe arrivant lors de la résolution d’un couplage multi-physique. Boucle multi-physique MODELE 1 MODELE 2 MODELE 3 temps t temps t + dt [1]C. Brezinski and M. Redivo Zaglia. Extrapolation Methods  : Theory and Practice. North Holland, 1991. [2] A.C. Aitken. On bernouilli’s numerical solution of algebraic equations. Proc. Roy. Soc. Edinburgh, 46  : 289–305, 1926. [3] Y. Nievergelt. Aitken’s and Steffensen’s accelerations in several variables. Numerische Mathematik, 59(1)  : 295–310, 1991. [4] A. Quarteroni, R. Sacco, and F. Saleri. Numerical Mathematics. Springer, 2007. 26 - Sacrées mathématiques ! X 1 = F 1 (X 1, X 2, X 3) X 2 = F 2 (X 1, X 2, X 3) X 3 = F 3 (X 1, X 2, X 3) Accélération de convergence pour les suites vectorielles de point fixe Les problèmes de type point fixe sont fréquemment rencontrés en simulation numérique. La résolution par itérations de point fixe a l’avantage majeur d’être simple et facilement mise en œuvre mais, quand elle est obtenue, la convergence est souvent seulement linéaire et lente. Les méthodes d’accélération de convergence (aussi appelées méthodes d’extrapolation) permettent alors d’améliorer la vitesse de convergence et parfois aussi d’éviter la divergence. Les problèmes de point fixe s’écrivent sous la forme générale suivante (1)  : X = F(X), où X est un vecteur de réels de dimension d (X ∈ R d). On les rencontre dans un nombre varié de problèmes numériques (couplage multi-physique, décomposition de domaine... voir Fig. 1) mais également lors de la résolution de problèmes non-linéaires (structure électronique, transfert de chaleur, mécanique non-linéaire...). En effet, il y a une dualité naturelle entre les problèmes de point fixe et les problèmes non-linéaires puisque tout problème non-linéaire de la forme G(X) = 0 est équivalent à un problème de point fixe de type (1). Un choix trivial, qui n’est souvent pas le meilleur, est de prendre F(X) = G(X)+X. La méthode de résolution naturelle d’un problème de point fixe est de construire une suite de point fixe générée par les itérations suivantes, parfois appelées itérations de Picard, à partir d’un X 0  : (2) X (n+1) =F(X n) , où n désigne le numéro d’itération, jusqu’à convergence de la suite, détectée numériquement lorsque —F(X n) - X n — ≤ ∈ avec ∈ un réel positif petit et —. — une norme donnée. La construction des itérations de point fixe présente l’avantage majeur d’être simple et facilement mise en œuvre informatiquement. En particulier, elle ne nécessite pas la construction de la dérivée de F (ou Jacobienne de F dans le cas vectoriel), ce qui la rend très attrayante vis-à-vis des méthodes de type Newton très connues pour la résolution de problèmes nonlinéaires (mais souvent très coûteuses et difficiles à mettre en œuvre de façon générale). En contrepartie, la convergence de la suite de point fixe vers la solution du problème (1) n’est a priori pas garantie (car elle s’appuie sur des propriétés de F autour du point solution, a priori inconnu !) et souvent linéaire (erreur qui décroît de façon linéaire) avec une vitesse de convergence lente. Aussi les numériciens ont-ils cherché à développer des méthodes d’accélération de convergence, qui consistent à générer une nouvelle suite qui converge plus vite vers la solution que la suite initiale. Certaines méthodes d’accélération permettent également d’augmenter l’ordre de convergence (super-linéaire, quadratique...) et même d’atteindre la convergence quand la suite de point fixe diverge. Accélérer la convergence L’accélération de la convergence de suites est un domaine à part entière de l’analyse numérique. La littérature sur ce sujet est vaste mais un point d’entrée possible est le livre de Brezinski et Zaglia [1]. Les méthodes d’accélération de convergence consistent de manière générale à définir les itérés de la suite accélérée comme une fonction des derniers itérés de la suite initiale  : (3) Yn = ψ(Xn, X n-1, X n-2 …) telle que lim Y n - X =0 np∞ X n -X où X est la limite de la suite (X n) n. Cette dernière équation permet de constater que la suite (Y n) n converge plus vite vers la solution que la suite initiale (X n) n (puisque le numérateur tend plus vite vers 0 que le dénominateur). En pratique, on utilise l’accélération de convergence de manière dynamique  : le nouvel itéré sera directement l’itéré accéléré X n+1 = Yn. Pour les suites scalaires (d = 1), la méthode d’accélération de suites la plus connue et la plus performante reste la méthode du Δ 2 (« delta carré ») d’Aitken [2]. Son adaptation en dynamique pour les suites de point fixe est la méthode de Steffensen [3] qui converge quadratiquement et permet une convergence même lorsque la suite de point fixe diverge. Cependant, cette méthode nécessite deux évaluations successives de la fonction F par itération, ce qui en réduit l’efficacité. D’autres méthodes très connues, avec un seul appel à F, sont donc souvent utilisées, comme la méthode de la sécante et celle de relaxation [4]. Les voix de la recherche - #70 - Clefs
Residu F(Xn) -Xn 1e-01 1e-02 1e-03 1e-04 1e-05 1e-06 1e-07 1e-08 1e-09 Cependant, dans les cas pratiques d’utilisation, ce sont des suites vectorielles qui sont générées. On trouve d’ailleurs beaucoup de méthodes d’accélération de suites vectorielles dans la littérature. La plupart d’entre elles sont des extensions de méthodes d’accélération de suites scalaires. D’autres méthodes sont, au contraire, directement construites pour des suites vectorielles. Elles sont dans ces cas-là généralement basées sur un processus de minimisation. Construire un cadre commun Le but de la formulation proposée [5] par notre équipe du Département d’études des combustibles, à la Direction de l’énergie nucléaire du CEA, est d’introduire un cadre commun pour construire de nouvelles méthodes d’accélération de suites vectorielles mais également pour retrouver sous un même formalisme les méthodes d’accélérations vectorielles les plus populaires et efficaces. D’un point de vue pratique, ce formalisme commun permet de tester facilement différentes méthodes d’accélération. Le principe de la méthode est de générer une nouvelle suite (Y n) n telle que  : (4) Y n =X n – ∑ M i=1 et ∀i ∈ [1., M]  : λ n Zn, avec 1 ≤ M ≤ d un entier, i i λ n ∈ R, (Z n) ∈ R d tel que lim Z n = 0. i i i np∞ On voit immédiatement que lorsque les n ne dépendent pas des itérations (donc de n), la suite (Y n) n converge vers la même limite que la suite (X n) n. En pratique, comme les n varient avecn, cette convergence vers la même limite ne peut être garantie pour toutes les suites (Y n) n générées (la limite des () n ne doitnnpas tendre vers l’infini). ANALYSE NUMÉRIQUE À partir de cette expression, les sont choisis de sorte à minimiser —Y n+1 - Y n — et ainsi garantir l’accélération de convergence vis-à-vis de la suite (X n) n. Pour la norme euclidienne, l’expression des peut être obtenue en utilisant la solution de l’équation normale résultant d’une minimisation des moindres carrés. Lors de l’application dynamique de ce procédé d’accélération de convergence aux suites de point fixe, nous disposons de deux suites  : la suite des (X n) n et celle des (F(X n) )n. Il en découle deux classes de méthodes d’accélérations vectorielles  : les méthodes de suites croisées et de suites alternées. Avec elles, on retrouve la majorité des méthodes d’accélération vectorielles connues (pour M = 1  : méthodes de sécante multidimensionnelle [6], Irons & Tuck [7] - généralisation de Steffensen ; pour M > 1  : méthode d’Anderson [8], interface quasi-Newton [9]...) et on peut en construire une multitude d’autres. Nous avons montré que pour la résolution d’un problème non-linéaire, ce type de méthodes d’accélérations vectorielles de point fixe à convergence linéaire concurrence la méthode de Newton (à convergence quadratique) en termes d’itérations sans avoir à évaluer la matrice Jacobienne (Fig. 2). Elles constituent donc une stratégie de résolution très intéressante. Différentes méthodes d’accélération tirées de ce formalisme général ont été, depuis lors, utilisées avec succès dans la littérature pour des applications diverses telles que le couplage multi-physique ou multi-champs, la résolution mécanique non-linéaire par transformée de Fourier rapide, la réduction de modèle pour des procédés de soudage, la distribution de population... 1e-10 0 5 10 15 20 25 30 35 Nombre d’iterations Point fixe Secante croisée Secante alternée Irons Tuck Newton LES OUTILS [5] I. Ramière and Th. Helfer. Iterative residual-based vector methods to accelerate fixed point iterations. Computers & Mathematics with Applications, 70(9)  : 2210 – 2226, 2015. [6] H. Fang and Y. Saad. Two classes of multisecant methods for nonlinear acceleration. Numerical Linear Algebra with Applications, 16  : 197–221, 2009. [7] B. M. Irons and R.C. Tuck. A version of the Aitken accelerator for computer iteration. International journal of numerical methods in engineering, 1  : 275–277, 1969. [8] D. G. Anderson. Iterative procedures for nonlinear integral equations. Journal of the Association for Computing Machinery, 12(4)  : 547–560, 1965. [9] U. Küttler and W. A. Wall. Fixed-point fluid-structure interaction solvers with dynamic relaxation. Computational Mechanics, 43  : 61–72, 2008. Fig. 2  : exemple de résolution d’un problème non-linéaire par différentes méthodes  : Newton, Point fixe standard, Point fixe accéléré avec le formalisme proposé (Sécante croisée, Sécante alternée, Irons et Tuck). Seuil de convergence ∈ = 10 -8. On voit ici la convergence très lente de la méthode de point fixe standard (autour de 1000 itérations). Les méthodes d’accélération de convergence de point fixe améliorent bien la vitesse de convergence. Les méthodes de type suites croisées semblent avoir un comportement moins monotone (toujours décroissant) que celles de type suites alternées. La méthode de Newton converge en 5 itérations (avec des premières itérations chaotiques), soit seulement une itération de moins que la méthode de sécante alternée. Clefs - #70 - Les voix de la recherche Sacrées mathématiques ! - 27



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :