Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

E Annaba STI 2018/2019 Chapitre 1 Résolution d’Équations Non Linéaires 1- Intro

E Annaba STI 2018/2019 Chapitre 1 Résolution d’Équations Non Linéaires 1- Introduction La modélisation de certains phénomènes physiques mène parfois à des équations non linéaires de la forme f (x) = 0, mais parfois, une telle équation ne peut être résolue analytiquement. Par exemple : x5 + x4 −3x3 + x2 + x +1 = 0 ou encore ln(x) = arctan(x) On a alors recours à des méthodes numériques (Bissection, Point ﬁxe, Newton-Raphson,...) pour ap- procher la solution. Beaucoup de méthodes existent et le choix de la méthode à adopter est spéciﬁque à l’équation considérée, c’est à dire qu’il se peut qu’une méthode soit efﬁcace pour la résolution d’une équation, moins efﬁcace pour une deuxième et voire divergente pour d’autres. Si pour une équation, deux méthodes convergent; celle dont la vitesse de convergence est meilleure sera alors choisie. L’étude de convergence, la vitesse de convergence et la comparaison de quelques méthodes numé- riques de résolution d’équations non linéaires font l’objet du présent chapitre. On considère une fonction réelle f déﬁnie et continue sur un intervalle [a,b], a < b, et admet une racine uniquesur I =]a,b[, c’est à dire qu’il existe un unique r ∈I tel que f (r) = 0. 1.1- Position du problème. On veut résoudre une équation de la forme : f (x) = 0, x ∈[a,b] ⊂D f (1) Déﬁnition 1.1.1 : Une solution de l’équation (1) est appelée racine ou zéro de la fonction f et est notée r. Théorème 1.1.2 : [TVI] Soit f : [a,b] →R, une fonction continue sur l’intervalle [a,b]. Si f (a)× f (b) < 0, alors il existe au moins r ∈]a,b[ tel que f (r) = 0. Ce théorème garanti juste l’existence de la solution. L’unicité découle de la stricte monotonie de la fonction f dans l’intervalle [a,b]. Corollaire 1.1.3 : Soit f : [a,b] →R. Si 2ème année 1 Analyse Numérique E Annaba STI 2018/2019 • f est continue sur [a,b]. • f est strictement monotone sur [a,b]. • f (a)× f (b) < 0. Alors, il existe un unique r ∈]a,b[ tel que f (r) = 0. Le principe de toutes les méthodes itératives est de générer une suite (xn) convergente sous certaines conditions vers la solution recherchée (racine ou point ﬁxe). En cas de convergence, les termes de cette suite sont des approximations de cette solution, d’où l’appellation "méthodes des approxima- tions successives". 2- M´ ethodes de r´ esolution 2.1- Méthode de Bissection (Dichotomie). 2.1.1- Principe de la méthode. On considère une fonction f continue de [a,b] dans R. On suppose que f (a)× f (b) < 0 et que l’équa- tion f (x) = 0 admet une solution unique r ∈[a,b]. La méthode de Bissection consiste à construire une suite (xn) qui converge (toujours!) vers la racine "r", et ce en encadrant par le TVI cette racine dans des intervalles emboités de plus en plus ﬁns, dont les centres sont les termes de cette suite. On considère l’exemple suivant pour illustrer le principe de la méthode. Exemple.1 On voudrait calculer une valeur approchée de la racine de la fonction f déﬁnie par : f (x) = 10x −9e−x On vériﬁe facilement que cette fonction admet une racine unique r ∈]0,1[. ▷f est continue sur R (somme de deux fonctions continues), donc continue sur [0,1]. ▷f est strictement croissante sur R car f ′(x) = 10 + 9e−x > 0, donc strictement croissante sur [0,1]. ▷f (0)× f (1) < 0. 1ère étape : On note a0 = a = 0 et b0 = b = 1. Le premier terme de la suite (xn) est obtenu en calculant le point milieu de l’intervalle I0 = [a0,b0] : x0 = a0 +b0 2 = 0.5 2ème année 2 Analyse Numérique E Annaba STI 2018/2019 2ème étape : (Première itération) Puisque f (x0)× f (b0) < 0, donc la racine se trouve dans l’intervalle réduit ]0.5,1[. On note a1 = x0 = 0.5 et b1 = b0 = 1. Le deuxième terme de la suite (xn) est obtenu en calculant le point milieu de l’intervalle I1 = [a1,b1] : x1 = a1 +b1 2 = 0.75 3ème étape : (deuxième itération) Puisque f (a1)× f (x1) < 0, donc la racine se trouve dans l’intervalle réduit ]0.5,0.75[. On note a2 = a1 = 0.5 et b2 = x1 = 0.75. Le troisième terme de la suite (xn) est obtenu en calculant le point milieu de l’intervalle I2 = [a2,b2] : x2 = a2 +b2 2 = 0.625 Ainsi de suite.... Les six premières itérations sont données dans le tableau suivant : n an xn bn signe de an signe de xn signe de bn 0 0 0.5 1 - - + 1 0.5 0.75 1 - + + 2 0.5 0.625 0.75 - + + 3 0.5 0.5626 0.625 - + + 4 0.5 0.53125 0.5626 - + + 5 0.5 0.515625 0.53125 - - + 6 0.515625 0.5234375 0.53125 - - + Les étapes de la méthode sont résumées dans le schéma suivant : Ï Calculer le point milieu de l’intervalle In = [an,bn] donné par : xn = an+bn 2 Ï Si f (xn) = 0, alors xn = r Ï Si f (xn)× f (an) < 0, la solution r appartient à In+1 = [an+1,bn+1] = [an,xn] Ï Si f (xn)× f (bn) < 0, la solution r appartient à In+1 = [an+1,bn+1] = [xn,bn] Quand s’arrêter?! Dans notre exemple on s’est arrêté à la sixième itération, mais en pratique l’algorithme de Dichotomie s’arrête lorsqu’une précision ﬁxée à priori est atteinte; c’est à dire, lorsque En = |xn −r| < ε, où En est l’erreur à l’étape n et ε est une tolérence donnée. 2.1.2- Erreur et critères d’arrêt. 2ème année 3 Analyse Numérique E Annaba STI 2018/2019 Après avoir illustré le principe de la méthode de Bissection (Dichotomie), on se propose de donner une formule qui nous permet d’estimer l’erreur absolue entre la racine exacte r et l’approximation xn obtenue à la énième itération (En = |xn −r|). Tout d’abord, nous pouvons remarquer que En < |In| 2 , où |In| est la longueur de l’intervalle In. D’autre part, on a : |I0| = b −a |I1| = |I0| 2 = b −a 2 |I2| = |I1| 2 = b −a 4 par récurrence, on obtient : |In| = |In−1| 2 = ··· = b −a 2n d’où En = |xn −r| < b −a 2n+1 Si on revient à l’exemple précédent, on peut afﬁrmer que l’erreur commise est strictement inférieure à b−a 27 = 1−0 128 = 0.0078125 Ï De cette formule, on remarque que plus le nombre d’itérations est grand plus la précision est bonne. En langage mathématique, on dit que la suite (xn) converge vers r. Estimation du nombre d’itérations nécessaires pour avoir une précision donnée : Si on exige une erreur absolue inférieure à ε, on peut déterminer (estimer) le nombre d’itérations suf- ﬁsantes pour avoir cette précision comme suit : La précision est atteinte si En ≤ε, et comme En < b−a 2n+1 , il sufﬁt que b−a 2n+1 soit inférieure ou égal à ε. Cherchons n vériﬁant : b −a 2n+1 ≤ε ⇔ b −a 2ε ≤2n ⇔ n ≥ln (b −a)−ln (2ε) ln (2) (2) On en conclut alors que pour avoir une erreur absolue inférieure à ε donné, il sufﬁt d’effectuer n ité- rations avec n = h ln(b−a)−ln(2ε) ln(2) i +1. ([a] dénote la partie entière de a) Remarque 2.1.1. La formule précédente donne le nombre d’itérations garantissant une erreur ab- solue inférieure à la valeur ﬁxée, mais rien ne garanti que ce soit le nombre minimal d’itérations à 2ème année 4 Analyse Numérique E Annaba STI 2018/2019 effectuer! Exemple.2 Soit f (x) = ex −1 Trouver le nombre d’itérations garantissant une erreur absolue inférieure à 0.5×10−6 en partant avec un intervalle initial de longueur 1. En appliquant la formule (2), on obtient : n ≥ ln ¡ 106¢ ln (2) = 19.93.. Donc, en prenant n = 20 on est garanti d’avoir une précision inférieure à 0.5×10−6. Cependant, si on choisit l’intervalle [−0.5,0.5] comme intervalle de départ, on obtient x0 = 0 est la racine exacte de f , donc la précision est atteinte sans avoir fait aucune itération (n = 0). 2.2- Méthode de Point Fixe. Déﬁnition 2.2.1 La solution d’une équation de la forme g(x) = x est appelée point ﬁxe de g. (On le nomme ainsi car ce point reste invariant par rapport à la fonction g) 2.2.1- Principe de la méthode. Soit f une fonction continue de [a,b] dans R. Il est toujours possible de transformer l’équation f (x) = 0 en une équation équivalente de la forme g(x) = x. Approcher la racine de la fonction f se ramène donc à l’approximation du point ﬁxe de la fonction g, et ce, en construisant la suite recurrente : ½ xn+1 = g(xn) x0 ∈[a,b] (3) Remarque 2.2.2 La transformation de l’équation f (x) = 0 en une équation équivalente uploads/Geographie/ eqnonlin-cours 1 .pdf