Asi 3 Méthodes numériques pour l’ingénieur Résolution de systèmes d’équation non linéaires
Yüklə
445 b.
tarix
02.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 :
R
n
R
n
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
h
2
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
u°
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ə
Dərs
Dərslik
Guide
Kompozisiya
Mücərrəd
Mühazirə
Qaydalar
Referat
Report
Request
Review
yükləyin