MPSI 2
Info tronc commun
´
Equations
scalaires
Les deux probl`emes sont enti`erement ind´ependants. Le premier probl`eme traite du codage d’un
polynˆome par un tableau, et des m´ethodes usuelles pour r´esoudre de mani`ere approch´ee une
´equation du type f (x) = 0.
Le second probl`eme traite de la recherche d’une ligne ´equidistante entre deux lignes donn´ees.
Probl`
eme I : racines d’un polynˆ
ome
Dans toute la suite on supposera qu’on a import´e de mani`ere usuelle les modules numpy et
matplotlib.pyplot :
import numpy as np
import matplotlib.pyplot as plt
Un polynˆome P = c0 + C1 X + · · · + cn X n sera cod´e par le tableau numpy np.array([c0 , . . . , cn ]),
o`
u chaque ck sera de type float.
Dans toute la suite on effectuera les tests avec le polynˆome Pex = −5 + 6X + 5X 2 − X 3 , cod´e par
np.array([−5., 6., 5., −1.])
1) Pour ´evaluer un polynˆome P = c0 + C1 X + c2 X 2 + · · · + cn X n en x (o`
u x est une valeur
num´erique), le plus efficace est d’appliquer l’algorithme de Horner, qui permet de minimiser
le nombre d’op´erations `a effectuer, en remarquant que :
P (x) = c0 + x(c1 + x(· · · + x(cn−2 + x(cn−1 + x(cn + 0))) . . . )))
On applique donc l’algorithme suivant :
s ← 0.
Pour i = n en descendant juqu’`a 0 faire :
s ← x ∗ s + ci
Fin Pour i
Valeur de retour : s
V´erifier “`a la main” que cet algorithme permet bien de calculer P (x).
Programmer la fonction evalue (p, x) dont le premier param`etre est de type np.array et
dont le second est une valeur num´erique.
Tester : Pex (1) = 5 et Pex (2) = 19
´
2) Ecrire
une fonction derive (p) dont le param`etre est de type np.array et dont la valeur de
retour est de type np.array et code le polynˆome d´eriv´e du polynˆome pass´e en param`etre.
Test : v´erifier que si on appelle cette fonction avec le polynˆome Pex , on obtient bien
np.array([6., 10., −3.])
Lyc´ee Chateaubriand
1/7
MPSI 2
´
Equations
scalaires
Info tronc commun
3) Repr´esenter Pex sur l’intervalle [−2, 6].
y
40
= Pex(x)
30
20
10
0
−10
−2
−1
0
1
2
3
4
5
6
4) D´esormais nous allons essayer de calculer de mani`ere approch´ee les racines de Pex par
diff´erents algorithmes.
Programmer une fonction dichotomie (p, epsilon, a, b) qui cherche une racine de p
entre a et b par dichotomie. On arrˆete les calculs d`es que la longueur de l’intervalle de
recherche devient inf´erieure `a epsilon.
Test : v´erifier que l’appel dichotomie (p_ex, 1e-9, 0., 2.) renvoie la valeur 0.583065703
5) Programmer la m´ethode de Newton. La fonction sera de la forme newton (p, epsilon, x_init)
o`
u x_init correspond `a la valeur initiale de la suite (un ) des valeurs que l’on calcule, et o`
u
on arrˆete les calculs d`es que |un − un−1 | 6 epsilon.
Test : l’appel newton (p_ex, 1e-9, 6.) doit renvoyer la valeur 5.876258043
6) M´ethode de la s´ecante : le principe de la m´ethode de la s´ecante est de construire une suite
(un ) dont les valeurs initiales u0 et u1 sont pass´ees en param`etres, et dont un+1 est l’abscisse
de l’intersection de la corde passant par (un−1 , P (un−1)) et par (un , P (un )).
Iteration pour la methode de la secante
40
30
20
10
0
−10
−2
un
−1
un +1
0
un−1
1
2
3
4
5
6
P (un ) − P (un−1)
(x − un ) + P (un) on obtient (en
un − un−1
un P (un−1) − un−1P (un )
. On arrˆete les calculs d`es que
=
P (un−1) − P (un )
Puisque cette corde a pour ´equation y =
calculant x lorsque y = 0) un+1
Lyc´ee Chateaubriand
2/7
MPSI 2
´
Equations
scalaires
Info tronc commun
|un+1 − un | devient inf´erieur `a un param`etre epsilon > 0.
Programmer la fonction secante (p, epsilon, u, v) o`
u u et v correspondent aux deux
valeurs initiales u0 et u1 .
Test : les appels secante (p_ex, 1e-9, 0., -2.) et secante (p_ex, 1e-9, -2., 0.)
doivent renvoyer deux racines distinctes : −1.459323746 et 0.5830657032 ; expliquer ce
paradoxe.
Probl`
eme II : ligne ´
equidistante
D´eterminer la courbe des points `a mˆeme distance de deux courbes donn´ees est une probl´ematique
qui apparaˆıt dans diverses situations : par exemple d´eterminer les zones d’influence maritime de
deux pays s´epar´es par un bras de mer.
1.5
1.0
y = g(x)
P(x ,y )
0.5
0
y = f(x)
−0.5
0
Mx (x,f(x))
0.0
−1.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Dans ce TP nous allons ´etudier un cas un peu simplifi´e o`
u les deux courbes sont donn´ees par des
´equations de type y = f (x) et y = g(x), avec pour tout x, f (x) < g(x).
Une approche simpliste
Charger les modules suivants :
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import newton, minimize
1) D´efinir les fonctions f : x 7→ 0.15 cos(2x) − 0.2 et g : x 7→ 0.12 sin(3x) + 0.6
On utilisera les fonctions sin et cos du module numpy (avec np.sin et np.cos) et pas les
fonctions par d´efaut.
Toutes les ´etudes de fonctions de ce TP auront lieu sur le segment I = [0, 4]. D´efinir une
subdivision de I :
abscisse = np.linspace (0, 4, 200)
Lyc´ee Chateaubriand
3/7
MPSI 2
´
Equations
scalaires
Info tronc commun
1
2) On consid`ere la fonction µ = (f + g) et on consid`ere en premi`ere approche que la courbe
2
d’´equation y = µ(x) serait une approximation de la ligne ´equidistante recherch´ee.
Tracer les courbes repr´esentatives des fonctions f , g et µ simultan´ement sur le segment I.
0.8
0.6
0.4
0.2
0.0
−0.2
−0.4
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Comme on le v´erifiera sur cette figure, cette approximation est assez mauvaise (la vraie ligne
´equidistante est en tirets, la courbe repr´esentative de µ est trac´ee en pointill´es).
Recherche de la distance d’un point `
a une courbe
Fixons un point P de coordonn´ees (x0 , y0 ) avec x0 ∈ I et une fonction φ : R → R. On cherche a`
calculer la distance de P `a la courbe d’´equation y = φ(x), c’est–`a–dire :
o
np
min
(x − x0 )2 + (φ(x) − y0 )2 | x ∈ R
Pour ´eviter un calcul de racine carr´ee (inutile) on cherche `a calculer le carr´e de cette distance et
on d´efinit
cdist(φ, P ) = min{(x − x0 )2 + (φ(x) − y0 )2 | x ∈ R}
On adopte l’approche suivante : on fixe un r´eel strictement positif d “petit” (on pourra prendre
d = 0.1) et on approxime la courbe repr´esentative de φ au voisinage de x par la droite Dx passant
φ(x + d) − φ(x − d)
par le point Mx de coordonn´ees (x, φ) et de pente
.
2d
Remarquons que la droite Dx est dirig´ee par le vecteur d~x de coordonn´ees (2d, φ(x + d) − φ(x − d)).
−−−→
On consid`ere que la distance de P `a la courbe repr´esentative de φ est atteinte lorsque P Mx .d~x = 0
(voir le premier sch´ema). On d´etermine donc x en r´esolvant de mani`ere approch´ee l’´equation :
(E) : 2d(x − x0 ) + (φ(x + d) − φ(x − d)).(φ(x) − y0 ) = 0
3) On appliquera la m´ethode de Newton d´ej`a impl´ement´ee dans scipy.optimize. Regarder
l’aide en ligne concernant scipy.optimize.newton et l’utiliser pour ´ecrire la fonction cdist.
On partira en premi`ere approximation de x0 .
4) Fixons x0 ∈ I. Le point ´equidistant des courbes d’´equation y = f (x) et y = g(x) a` l’abscisse
x0 est obtenu en r´esolvant cdist(f, (x0 , y)) − cdist(g, (x0, y)) = 0.
Lyc´ee Chateaubriand
4/7
MPSI 2
Info tronc commun
´
Equations
scalaires
´
Ecrire
une fonction equidistante qui prend en param`etre x0 et qui calcule la valeur y
correspondante pour que le point de coordonn´ees (x0 , y) appartienne a` la ligne ´equidistante.
On utilisera encore la m´ethode de Newton.
5) Tracer sur un mˆeme graphique les courbes repr´esentatives de f , de g et la ligne ´equidistante.
Probl`
emes d’instabilit´
e
(
f (x) = 0.2 cos(3x) − 0.1x2 − 0.2
6) Red´efinir les fonctions f et g en posant
g(x) = 0.12 sin(8x) + 0.6
Essayer de tracer simultan´ement les courbes repr´esentatives de f , de g et de la courbe
´equidistante.
Normalement l’algorithme de Newton “plante” : il n’arrive pas a` converger en temps
raisonnable.
7) R´e´ecrire la fonction cdist en utilisant la fonction scipy.optimize.minimize pour chercher
`a minimiser (x − x0 )2 + (φ(x) − y0 )2 . Utiliser l’aide en ligne.
Attention : cette fonction n´ecessite l’utilisation d’une valeur initiale, qui donne une approximation de l’endroit o`
u la valeur minimum peut ˆetre atteinte. La valeur de retour de cette
fonction est une structure compos´ee, on acc`ede `a la valeur minimum avec le champ .fun, et
`a la liste des valeurs r´ealisant ce minimum avec le champ .x
Exemple : la fonction t 7→ t4 − t2 a pour minimum −0.25, ce minimum est atteint en
1
1
√ ≃ 0.707 et en − √ ≃ −0.707
2
2
>>>
>>>
>>>
>>>
>>>
import numpy as np
import scipy.optimize
def f (t) : return (t**4-t**2)
res = scipy.optimize.minimize (f, 1.)
res.fun
-0.25
>>> res.x
[0.70710655]
Si on ´etait parti de la valeur initiale −1. on aurait trouv´e un minimum atteint en −0.70710655
8) Effectuer maintenant le trac´e de la ligne ´equidistante. Constater la pr´esence de points
anguleux le long de cette ligne (en ces points la fonction equidistante n’est pas d´erivable).
Lyc´ee Chateaubriand
5/7
MPSI 2
´
Equations
scalaires
Info tronc commun
1.0
0.5
0.0
−0.5
−1.0
−1.5
−2.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Trac´
e des cercles aux points anguleux
´
9) Ecrire
une fonction qui permet de tracer un cercle dont les param`etres sont le rayon et les
coordonn´ees du centre.
Soit P le point d’abscisse 0.985 et ´equidistant des courbes d’´equation y = f (x) et y = g(x)
(c’est un des points anguleux). Calculer son ordonn´ee. Calculer la distance rP entre P
et la courbe d’´equation y = f (x). Rajouter au trac´e pr´ec´edent le cercle de centre P et
de rayon rP . Constater les trois points de contact. Attention : pour tracer des cercles et
pas des ellipses, il faut que le rep`ere soit orthonorm´e. On utilisera donc avant plt.show()
l’instruction plt.axis (’equal’)
1.0
0.5
PD
PG
P
0.0
−0.5
−1.0
−1.5
−2.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
On comprend mieux maintenant la pr´esence de ces points anguleux : ce cercle a deux points
de contact avec la courbe d’´equation y = g(x). Notons PG le point de contact de gauche
de PD le point de contact de droite. Si on part d’un point P ′ proche de P sur la ligne
´equidistante, on aboutirait `a un point de contact sur la courbe d’´equation y = g(x) proche
de PG si on prend P ′ `a gauche de P , et `a un point proche de PD si on part d’un point P ′ a`
droite de P .
10) Pour d´etecter tous les points anguleux, on proc`ede de la fa¸con suivante : on fait se d´eplacer
un point P le long de la ligne ´equidistante (l’abscisse de P parcourt le segment [0, 4]) ; on
Lyc´ee Chateaubriand
6/7
MPSI 2
´
Equations
scalaires
Info tronc commun
calcule (grˆace au champ .x de scipy.optimize.minimize) en fonction de l’abscisse t de P
l’abscisse xg (t) d’un point sur la courbe d’´equation y = g(x) qui minimise la distance a` P .
On calcule de mani`ere similaire xf (t) avec la courbe d’´equation y = f (x).
Les points anguleux de la ligne ´equidistante se trouvent aux discontinuit´es de t 7→ xf (t) et
t 7→ xg (t), c’est–`a–dire l`a o`
u xf (t) ou xg (t) varient “brutalement” lors d’une petite variation
de t.
Calculer tous ces points anguleux et tracer (de fa¸con automatique) tous les cercles correspondants. On doit trouver 6 points anguleux lorsque t parcourt [0, 4] : 1 discontinuit´e de xf
et 5 discontinuit´es de xg .
1.0
0.5
0.0
−0.5
−1.0
−1.5
−2.0
0.0
Lyc´ee Chateaubriand
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
7/7
© Copyright 2024 ExpyDoc
