INSA Département GM : Équations non linéaires

Exercices 2. (Application) Considérons une antenne dont la portée p(x, y) est donnée
par :
2 2
p (x, y) = e−T ((x−x0 ) +(y−y0 ) )
x0 ,y0
Exercice 1 (Point fixe) : On cherche à déterminer la racine d’un nombre
a > 0 en se ramenant à la recherche de 0 de la fonction f (x) = x2 − a. Pour où T > 0 est un paramètre et (x0 , y0 ) représente la position de l’antenne
résoudre l’équation f (x) = 0, on va écrire cette équation sous la forme d’une dans le plan. Étant donné N villes positionnées en (xi , yi )i=1,··· ,N , on note par
équation de point fixe : pi = px0 ,y0 (xi , yi ) la couverture dans la ville i. L’objectif est de déterminer
f (x) = 0 ⇔ g(x) = x (1) la position optimale (x∗0 , y0∗ ) de l’antenne pour avoir la meilleure couverture
totale.
où g(x) devra être bien choisi.
a) Formaliser ce problème comme un problème de minimisation.
1. (Méthode de Héron) Considérons le choix de fonction g(x) suivant :
b) Proposer une méthode de résolution et faite le lien avec la question 1.a).
a
x+ x
g(x) =
2
a) Montrer l’équivalence (1) pour ce choix de fonction g.
b) Montrer que l’algorithme de point fixe converge. Préciser son ordre. Exercice 3 (Ordre méthode fausse position) : Soit une fonction f : R →
c) (Bonus) À quel algorithme correspond ce choix de fonction g(x) ? R. On suppose que f est C ∞ , admet un unique 0 en x∗ et vérifie f 0 (x∗ ) 6= 0.

2. Reprenons l’étude mais dans la situation où on choisit :

1. Rappeler l’algorithme de la fausse position. Peut-on écrire cette algorithme
g(x) = x2 + x − a sous la forme d’un algorithme de point fixe xn+1 = g(xn ) ?

a) Montrer l’équivalence (1) pour ce choix de fonction g. 2. a) Réécrire l’algorithme sous la forme xn+1 = g(xn , xn−1 ).
b) La méthode converge-t-elle ? Si oui, à quel ordre ? b) À l’aide d’un D.L. de g à l’ordre 1 montrer que :

|xn+1 − x∗ | = O((xn − x∗ )2 ) + O((xn−1 − x∗ )2 )

et déduire que la méthode est convergente si on l’initialise avec x0 et x1

Exercice 2 (Newton vectoriel) : Soit F : R2 → R2 . On souhaite déterminer suffisamment proche de x∗ .
un point de coordonnées (x0 , y0 ) annulant la fonction F . c) À l’aide d’un D.L. de g à l’ordre 2 montrer que l’ordre de la méthode est
√
1+ 5
2 .
1. a) Écrire l’algorithme de Newton dans ce cas.
b) Que se passe-t-il si F est une application linéaire ?

1
Exercice 4 (Gauss-Newton) : Soit f (x) : Rn → Rp où on suppose p ≥ n.
On cherche à résoudre numériquement le problème de minimisation :

Trouver min kf (x)k22 (2)

x∈Rn

1. a) Justifier que si f est différentiable, alors F (x) = kf (x)k22 est aussi diffé-
rentiable.
b) Donner l’équation satisfaite par les points critiques de F (x) en fonction de
f (x) et de sa différentielle.
c) Déduire une méthode pour résoudre le problème de minimisation (2) à
l’aide de la méthode de Newton.

2. Une seconde approche consiste à s’inspirer des méthodes de descente de gra-

dient. Pour ce faire, l’idée est de linéarisé f (x) au voisinage de x0 .

a) Étant donné x1 proche de x0 , donner une approximation linéaire de f (x1 )

en fonction de f (x0 ), dx0 f et x1 − x0 .
b) En s’inspirant de la méthode de descente de gradient à pas constant pro-
poser un algorithme pour résoudre (2).
c) En s’inspirant cette fois de la méthode de Newton proposer un algorithme
similaire à l’algorithme de gradient à pas optimale pour résoudre (2).

2
Exercices de révision Exercice 3 (Méthode d’ordre supérieure) : On cherche ici à construire une
méthode d’ordre r donné pour résoudre l’équation f (x) = 0 via une méthode de
Exercice 1 (TVI et dichotomie) : Soit f (x) : R → R une fonction continue. point fixe. Posons :
r
L’objectif de cet exercice est de revoir le Théorème des Valeurs Intermédiaires et X
comment il permet de déterminer un zéro de f . g(x) = x + ai (x)f i (x)
i=1

1. Dans le cas où pour a < b on a f (a) < 0 et f (b) > 0, rappeler le théorème. L’objectif sera de déterminer les fonctions ai (x) pour que la suite xn+1 = g(xn )
soit d’ordre r. On supposera que f (x∗ ) = 0 et les dérivées f (i) (x∗ ) 6= 0 pour tout
2. On définit les suites (an )n et s(bn )n comme suit : i ≥ 1.

cn si f (cn ) < 0

cn si f (cn ) > 0 1. Justifier que si x∗ est un point fixe de g(x) alors c’est un 0 de f (x).
an+1 = bn+1 =
an sinon bn sinon
2. a) Rappeler la condition que doit vérifier g(x) et ses dérivés pour que la suite
an +bn
soit d’ordre r.
et an+1 = bn+1 = cn si f (cn ) = 0 où cn = 2 .
b) Déduire a1 (x) pour que la méthode soit au moins d’ordre 2. Quel méthode
a) Montrer que (an )n est une suite croissante et (bn )n est décroissante. retrouve-t-on ?
c) Déduire a2 (x) pour que la méthode soit au moins d’ordre 3.
b) Que dire de la limite de la différence bn − an ?
c) Conclure en donnant un algorithme permettant d’obtenir un zéro de f . 3. (Application) Reprendre l’exemple de l’exercice 2 sur le calcul de racine et
proposer une méthode plus performante que la méthode de Héron.

Exercice 2 (Point fixe) : Soit f (x) = 2x4 − x − 2. On cherche à déterminer

le ou les 0 de f (x).

1. Donner le tableau de variations de f et déduire le ou les 0 de f .

2. Considérons la suite xn+1 = 2x4n − 2.

a) Si la suite converge, justifier qu’elle converge vers un 0 de f (x).

b) La suite converge-t-elle ?

3. Déterminer une fonction Φ(x) t.q. la suite xn+1 = Φ(xn ) soit convergente et
converge vers le 0 de f .

3
 rx
Applications et programmation • Le modèle prédateurs / proies R(x) = où la population est
1 + (x/K)2
Pour cette section, je vous invite à faire les programmes en Python à l’aide soumise à une prédation d’autant plus forte que le nombre d’individus est
des modules NumPy et MatPlotLib. L’avantage est que ces outils sont gratuits et grand.
multiplate-forme (et sont ceux utilisés en TP !). Il est également possible de faire Dans chacun de ces cas, on cherche à déterminer les situations stationnaires, c’est
ces programmes en Matlab (payant), Scilab (gratuit et aussi multiplate-forme), à dire t.q. x∗ = x∗ R(x∗ ). Déterminer ces points stationnaires dans les différents
ou même en C / C++ ( les outils de visualisation étant moins facile à mettre en cas à l’aide de la méthode de Newton.
place).

Exercice 1 (Newton vs F.P.) : L’objectif de cet exercice est de comparer les

méthodes de Newton de de la fausse position. On considèrera à titre d’exemple Exercice 3 (identification de paramètres) : Reprenons l’exemple du cours :
le calcul de la racine de 2 avec comme fonction f (x) = x2 − 2. On suppose qu’on connait la trajectoire (x(t), y(t)) d’un projectile à certain ins-
tant (tn )n . L’objectif est de déterminer les paramètres (x0 , y0 ), position initial,
1. Rappeler les ordres théoriques des méthodes dans ce cas.
(P, θ), puissance et angle de tir, du projectile sachant qu’il obéit aux lois de
2. a) Implémenter la méthode de Newton et vérifier à l’aide d’un programme test Newton :
la méthode. −g 2
√ x(t) = P cos(θ)t + x0 et y(t) = t + P sin(θ)t + y0
Représenter dans un graphique le log(|xn+1 − 2|) en fonction de log(|xn −
b) √ m
2|). Comment retrouver l’ordre à l’aide de ce graphique ?
1. Écrire ce problème comme un problème de minimisation.
3. Procéder de même pour la méthode de la fausse position.
2. a) Écrire une fonction générant des positions (xn , yn )n d’une trajectoire étant
donnée les paramètres choisis. On perturbera les valeurs de xn et yn par
une légère incertitude afin de simuler une imprécision sur les mesures.
b) Implémenter et tester la méthode de Gauss-Newton proposée à l’exercice
Exercice 2 (évolution de population) : On s’intéresse ici à l’évolution d’une 4.
population, où plus précisément à son comportement en temps long. On suppose
que d’une année à l’autre, la population évolue ainsi :

xn+1 = R(xn )xn

où R(xn ) représente la proportion d’individus xn survivants. Divers modèles

existent dans la littérature :

• Le modèle de Malthus R(x) = r > 0 correspondant à une situation où

aucune contrainte n’est imposée à la population.
r
• Le modèle de Verhulst R(x) = où l’évolution est ralenti si la po-
1 + Kx
pulation est grande, ce qui représente une situation de resources limitée.