Asi 3 Méthodes numériques pour l’ingénieur Résolution de systèmes d’équation non linéaires



Yüklə 445 b.
tarix02.11.2017
ölçüsü445 b.
#27785


ASI 3 Méthodes numériques pour l’ingénieur

  • Résolution de systèmes d’équation non linéaires

  • f(x)=0


Introduction

  • Comment résoudre le système suivant ?

    • Méthodes directes
    • Méthodes itératives


Introduction

  • Comment résoudre le système suivant ?

    • Méthodes directes : impossibles
    • Méthodes itératives


Résolution de f(x)=0

  • Soit une fonction f : Rn Rn

    • continue sur ...
    • Dérivable sur ...
  • Principe :

    • trouver une méthode itérative uk+1 = g(uk) qui converge vers la solution


Résolution de f(x)=0

  • Plusieurs méthodes

    • Newton
    • Quasi-Newton (sécante, Broyden, …)
    • Point fixe
    • Gradient
  • Problèmes ?

    • Convergence
    • Complexité


f(x)=0 lorsque n=1

  • Recherche par dichotomie

  • méthode de la séquente

  • méthode de point fixe

  • méthode de Newton-Raphson



Recherche dichotomique



Méthode de la séquente



La « fausse » bonne idée garder f(a) et f(b) de signe opposé



Méthode de Newton



Méthode de Newton

  • En dimension 1 :

    • on considère l'approximation affine :
    • on cherche h tel que f(uk+h)=0 soit si on néglige les terme en h2
    • et ainsi


Méthode de Newton

  • Illustration



Méthode de Newton

  • Illustration



Méthode de point fixe

  • Définition

  • f(x)=0 et le x = g(x)

  • exemple

  • convergence (suite de Cauchy)

  • théorème de convergence globale

  • théorème de convergence local

    • théorème du point fixe


Méthode du point fixe

  • Principe général :

    • trouver g en fonction de f telle que
      • f(û)=0  g(û)=û
      • la suite uk converge (si u0 est bien choisi)
    • conditions suffisantes sur g en dimension 1
      • g dérivable et |g'(û)| < 1
    • conditions suffisantes sur g en dimension n
      • g différentiable et [g(û)] < 1 ( = rayon spectral)


Méthode du point fixe

  • Convergence linéaire :

    • il existe C > 0 tel que
  • Inconvénient : choix de g de manière algébrique



Méthode du point fixe

  • Exemple en dimension 1

    • résolution de x2 - 2 = 0
    • choix de g :
      • g1(x) = 2/x g'1(x) = -2/x2 g'1(û) = -1
      • g2(x) = 2x - 2/x g'1(x) = 2+2/x2 g'1(û) = 3
      • g3(x) = x/2 + 1/x g'1(x) = 1/2-1/x2 g'1(û) = 0


Méthode du point fixe

  • Exemple en dimension 1

    • résolution de x2 - 2 = 0
    • choix de g :
      • g1(x) = 2/x g'1(x) = -2/x2 g'1(û) = -1
      • g2(x) = 2x - 2/x g'1(x) = 2+2/x2 g'1(û) = 3
      • g3(x) = x/2 + 1/x g'1(x) = 1/2-1/x2 g'1(û) = 0


résumé

  • Dichotomie

  • séquente

  • newton

  • Point fixe



Accélération de la convergence

  • Définition : l’ordre de la convergence

  • Motivation

  • Définition du principe de Aitken

  • Théorème de convergence quadratique

  • Aitken et Steffensen



Méthode de Newton

  • En dimension n :

    • une équation, n inconnues :
    • n équations, n inconnues :


Méthode de Newton

  • En dimension n :

    • on considère l'approximation affine :
    • on cherche h tel que f(uk+h)=0 soit système linéaire !
    • et ainsi


Méthode de Newton

  • Théorème :

    • s'il existe û tel que
      • f(û)=0
      • f est différentiable dans un voisinage de û
      • f(û) est inversible
    • alors il existe  > 0 tel que
      • si vérifie
      • alors la suite construite par la méthode de Newton converge vers û


Méthode de Newton

  • Avantage : convergence quadratique

    • il existe C > 0 tel que
  • Inconvénient : calcul de f(x) souvent difficile



Exemple



Méthodes de Quasi-Newton

  • Comment se passer du calcul de f(x) ?

  • En dimension 1 : méthode de la sécante

  • En dimension n :

    • le rapport précédent n'a aucun sens (u est un vecteur)
    • comment approcher f(uk+1) ?


Méthodes de Quasi-Newton

  • Approximation de f(uk+1) par la matrice Ak

    • Ak doit vérifier Ak(uk - uk-1)=f(uk) - f(uk-1)
    • Problème : il existe une infinité de Ak
  • Méthode de Broyden :

    • condition supplémentaire : Akz = Ak-1z si (uk - uk-1)'z = 0


Méthodes de Quasi-Newton

  • Méthode de Broyden : algorithme

    • initialisation de u0 et A0 (différences finies)
    • itération :


Méthodes de Quasi-Newton

  • Convergence de la méthode de Broyden :

    • "super-linéaire"
    • moins rapide que Newton


Méthode du point fixe

  • Principe général :

    • trouver g en fonction de f telle que
      • f(û)=0  g(û)=û
      • la suite uk converge (si u0 est bien choisi)
    • conditions suffisantes sur g en dimension 1
      • g dérivable et |g'(û)| < 1
    • conditions suffisantes sur g en dimension n
      • g différentiable et [g(û)] < 1 ( = rayon spectral)


Méthode du point fixe

  • Exemple en dimension 3



Méthode du point fixe

  • Exemple en dimension 3



Méthode du point fixe

  • Exemple en dimension 3 (suite)

    • valeurs initiales (x0=0.1 ; y0=0.1 ; z0=-0.1)
    • convergence vers (0.5 ; 0.0 ; -0.5236)
    • résultat théorique: (0.5 ; 0.0 ; -/6)


Méthode du point fixe

  • Comment essayer d'accélérer la convergence

    • remplacer les valeurs par leurs "dernières" estimations
      • (cf. Gauss-Siedel pour les systèmes linéaires)
    • exemple :


Conclusion

  • Méthodes

    • Newton :
      • inconvénient = calcul des dérivées
      • avantage = convergence quadratique
    • Quasi-Newton :
      • inconvénient = convergence super-linéaire
      • avantage = plus de calcul des dérivées
    • Point Fixe :
      • inconvénient = convergence linéaire
      • inconvénient = choix de g
  • Problème général : initialisation de la suite !



TD

  • Implémenter en Matlab :

    • Newton, Broyden, point fixe (+Gauss Siedel)
    • pour les problèmes suivants :
    • comparer le temps de convergence (pour un même seuil)


Yüklə 445 b.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin