3. Les fonctions#
3.1. Exercice 1#
Nous souhaitons calculer des suites numériques définies par récurrence \(u_{n+1}=f(u_n)\) où \(f\) est une fonction donnée.
Questions
Créez une fonction
suite_recurrente
qui prend en argumentune fonction
f
utilisée pour la récurrenceun réel
u0
utilisé pour initialisé la suiteun entier
N
et qui retourne la liste desN
premiers termes de la suite définie par récurrence
Testez votre fonction en calculant et affichant les 10 premiers termes de la suite définie par
\[ u_0=0.75, \quad u_{n+1} = 2 u_n (1-u_n), \quad n\geq0.\]
Show code cell source
def suite_recurrente(f, u0, N):
"""
calcule les N premiers termes de la suite définie par récurrence
u_0 donné, u_{n+1} = f(u_n)
Parameters
----------
f: function
la fonction qui définie la récurrence
u0: float
la donnée initiale
N: int
le nombre de termes calculés
Returns
-------
list
la liste des termes de la suite
"""
u = [u0]
for k in range(N):
u.append(f(u[-1]))
return u
f = lambda x: 2*x*(1-x)
u = suite_recurrente(f, 0.75, 9)
for k, uk in enumerate(u):
print(f"u[{k:1d}] = {uk}")
u[0] = 0.75
u[1] = 0.375
u[2] = 0.46875
u[3] = 0.498046875
u[4] = 0.49999237060546875
u[5] = 0.4999999998835847
u[6] = 0.5
u[7] = 0.5
u[8] = 0.5
u[9] = 0.5
3.2. Exercice 2#
Dans cet exercice, nous allons calculer une dérivée numérique. Supposons que l’on souhaite calculer la dérivée d’une fonction \(f\) (sans connaître son expression). Il est alors possible de calculer une valeur approchée en utilisant les taux d’accroissement :
Nous allons étudier numériquement la qualité de cette approximation lorsque \(h\) tend vers 0. Nous prendrons pour ce faire la fonction \(f : x\mapsto \sqrt{x}\) et le point \(a=2\).
Questions
Définissez une fonction
f
ainsi qu’une fonctiondf
qui prennent en argument un réelx
et qui retournent respectivement la valeur de \(f\) et de sa dérivée au point \(x\).Calculez les deux approximations proposées pour \(h=2^{-k}\) avec \(k\in\lbrace2, 4, 6, \ldots, 98\rbrace\).
Affichez vos résultats selon le format suivant
--------------------------------------------------------------------------------------
| k | h | (f(a+h)-f(a))/h | erreur | (f(a+h)-f(a-h))/(2h) | erreur |
--------------------------------------------------------------------------------------
| 2 | 2.5000E-01 | 0.34314575 | 1.041E-02 | 0.35424869 | 6.953E-04 |
| 4 | 6.2500E-02 | 0.35083359 | 2.720E-03 | 0.35359657 | 4.318E-05 |
| 6 | 1.5625E-02 | 0.35286554 | 6.878E-04 | 0.35355609 | 2.697E-06 |
| 8 | 3.9062E-03 | 0.35338093 | 1.725E-04 | 0.35355356 | 1.686E-07 |
...
--------------------------------------------------------------------------------------
Décrivez et expliquez le comportement de ces deux suites ?
Show code cell source
from math import sqrt
liste_cas = [
{
'name': "f(x) = x^2 | f'(1) = 2",
'f': lambda x: x*x,
'df': lambda x: 2*x,
'a': 1,
}, {
'name': "f(x) = sqrt(x) | f'(2) = 1/(2sqrt(2))",
'f': lambda x: sqrt(x),
'df': lambda x: .5/sqrt(x),
'a': 2,
},
]
taille = 86
for cas in liste_cas[1:]:
f, df, a = cas['f'], cas['df'], cas['a']
print("*"*taille)
print(cas['name'])
print("-"*taille)
print("| k | h | (f(a+h)-f(a))/h | erreur | (f(a+h)-f(a-h))/(2h) | erreur |")
print("-"*taille)
for k in range(2, 100, 2):
h = 2**(-k)
a0 = (f(a+h) - f(a)) / h
e0 = abs(a0 - df(a))
a1 = (f(a+h) - f(a-h)) / (2*h)
e1 = abs(a1 - df(a))
print(f"| {k:2d} | {h:10.4E} | {a0:10.8f} | {e0:10.3E} | {a1:10.8f} | {e1:10.3E} |")
print("-"*taille)
print("*"*taille)
**************************************************************************************
f(x) = sqrt(x) | f'(2) = 1/(2sqrt(2))
--------------------------------------------------------------------------------------
| k | h | (f(a+h)-f(a))/h | erreur | (f(a+h)-f(a-h))/(2h) | erreur |
--------------------------------------------------------------------------------------
| 2 | 2.5000E-01 | 0.34314575 | 1.041E-02 | 0.35424869 | 6.953E-04 |
| 4 | 6.2500E-02 | 0.35083359 | 2.720E-03 | 0.35359657 | 4.318E-05 |
| 6 | 1.5625E-02 | 0.35286554 | 6.878E-04 | 0.35355609 | 2.697E-06 |
| 8 | 3.9062E-03 | 0.35338093 | 1.725E-04 | 0.35355356 | 1.686E-07 |
| 10 | 9.7656E-04 | 0.35351024 | 4.315E-05 | 0.35355340 | 1.054E-08 |
| 12 | 2.4414E-04 | 0.35354260 | 1.079E-05 | 0.35355339 | 6.585E-10 |
| 14 | 6.1035E-05 | 0.35355069 | 2.697E-06 | 0.35355339 | 4.099E-11 |
| 16 | 1.5259E-05 | 0.35355272 | 6.743E-07 | 0.35355339 | 2.788E-12 |
| 18 | 3.8147E-06 | 0.35355322 | 1.686E-07 | 0.35355339 | 2.788E-12 |
| 20 | 9.5367E-07 | 0.35355335 | 4.214E-08 | 0.35355339 | 2.788E-12 |
| 22 | 2.3842E-07 | 0.35355338 | 1.071E-08 | 0.35355339 | 2.788E-12 |
| 24 | 5.9605E-08 | 0.35355338 | 6.051E-09 | 0.35355339 | 4.629E-10 |
| 26 | 1.4901E-08 | 0.35355338 | 6.051E-09 | 0.35355339 | 1.400E-09 |
| 28 | 3.7253E-09 | 0.35355335 | 3.585E-08 | 0.35355338 | 6.051E-09 |
| 30 | 9.3132E-10 | 0.35355330 | 9.546E-08 | 0.35355341 | 2.375E-08 |
| 32 | 2.3283E-10 | 0.35355282 | 5.723E-07 | 0.35355330 | 9.546E-08 |
| 34 | 5.8208E-11 | 0.35354996 | 3.433E-06 | 0.35355186 | 1.526E-06 |
| 36 | 1.4552E-11 | 0.35354614 | 7.248E-06 | 0.35355377 | 3.814E-07 |
| 38 | 3.6380E-12 | 0.35351562 | 3.777E-05 | 0.35354614 | 7.248E-06 |
| 40 | 9.0949E-13 | 0.35351562 | 3.777E-05 | 0.35363770 | 8.430E-05 |
| 42 | 2.2737E-13 | 0.35351562 | 3.777E-05 | 0.35351562 | 3.777E-05 |
| 44 | 5.6843E-14 | 0.35156250 | 1.991E-03 | 0.35351562 | 3.777E-05 |
| 46 | 1.4211E-14 | 0.34375000 | 9.803E-03 | 0.35156250 | 1.991E-03 |
| 48 | 3.5527E-15 | 0.31250000 | 4.105E-02 | 0.34375000 | 9.803E-03 |
| 50 | 8.8818E-16 | 0.25000000 | 1.036E-01 | 0.37500000 | 2.145E-02 |
| 52 | 2.2204E-16 | 0.00000000 | 3.536E-01 | 0.50000000 | 1.464E-01 |
| 54 | 5.5511E-17 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 56 | 1.3878E-17 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 58 | 3.4694E-18 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 60 | 8.6736E-19 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 62 | 2.1684E-19 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 64 | 5.4210E-20 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 66 | 1.3553E-20 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 68 | 3.3881E-21 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 70 | 8.4703E-22 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 72 | 2.1176E-22 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 74 | 5.2940E-23 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 76 | 1.3235E-23 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 78 | 3.3087E-24 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 80 | 8.2718E-25 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 82 | 2.0680E-25 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 84 | 5.1699E-26 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 86 | 1.2925E-26 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 88 | 3.2312E-27 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 90 | 8.0779E-28 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 92 | 2.0195E-28 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 94 | 5.0487E-29 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 96 | 1.2622E-29 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
| 98 | 3.1554E-30 | 0.00000000 | 3.536E-01 | 0.00000000 | 3.536E-01 |
--------------------------------------------------------------------------------------
**************************************************************************************
3.3. Exercice 3#
Dans cet exercice, nous allons supposer que l’ordinateur ne sait faire que des additions et des multiplications (ce sont des algorithmes simples qui sont depuis longtemps optimisés) et nous allons fabriquer à la main des fonctions qui calculent des divisions (ou des inverses), des factorielles. Puis nous allons simuler la fonction exponentielle.
Pour calculer l’inverse d’un nombre \(x\), un algorithme efficace basé sur l’algorithme de Newton consiste à
remettre \(x\) à l’échelle en trouvant \(y, c\) tel que \(x=cy\), \(y\in[0.5, 1]\) et \(c\) est une puissance de 2 (positive ou négative) ;
construire la suite \((z_n)\) définie par \(z_0=1\), \(z_{n+1}=z_n(2-yz_n)\) ;
la suite \((z_n)\) converge (rapidement) vers \(1/y\), on défini \(z\) la limite numérique de cette suite (le critère d’arrêt pourra être que la différence entre deux termes consécutifs est petite) ;
retourner \(z/c\) qui est alors une approximation de l’inverse de \(x\). Notez que l’on doit aussi calculer l’inverse de \(c\) en faisant seulement des multiplications par \(2\) ou par \(0.5\).
Questions
Proposez une fonction
inverse
qui prend en argument un réelx
et un argument optionnelepsilon
et qui retourne l’inverse dex
approchée par l’algorithme précédent. La valeur deepsilon
pourra être utilisée pour stopper le calcul de la suite lorsque la précision sera atteinte.Testez votre algorithme en calculant l’inverse de différents nombres (petits, grands, négatifs ou positifs).
La fonction exponentielle peut également être approchée par le calcul d’une série entière tronquée :
Questions
Proposez une fonction
exponentielle
qui prend en argument un réelx
et qui calcule l’approximation deexp(x)
en calculant la somme finie proposée au-dessus (vous essayerez d’estimer le nombre de termes nécessaires).Testez votre algorithme en calculant l’exponentielle de différents nombres (petits, grands, négatifs ou positifs).
Show code cell source
def scaling(x):
"""remet à l'échelle le nombre x entre 0.5 et 1"""
assert(x > 0)
coeff, icoeff = 1, 1
while x > 1:
coeff *= 2
icoeff *= 0.5
x *= 0.5
while x < 0.5:
coeff *= 0.5
icoeff *= 2
x *= 2
return x, coeff, icoeff
def inverse(x, epsilon=1.e-10):
"""calcul l'inverse de x"""
assert(x != 0)
xx = x if x > 0 else -x
xx, coeff, icoeff = scaling(xx)
ixx = 1
ixx_old = ixx - max(1, 2*epsilon)
n, nmax = 0, 100
while abs(ixx - ixx_old) > epsilon and n < nmax:
ixx_old = ixx
ixx *= 2 - xx*ixx
n += 1
if n == nmax:
print("ATTENTION : inverse non convergée")
ix = ixx * icoeff if x > 0 else -ixx * icoeff
return ix
def exponentielle(x, epsilon=1.e-10):
"""calcul de l'exponentielle de x"""
xn, ifactn = 1., 1
y = 1.
n, nmax, dy = 1, 10000, 1.
while abs(dy) > epsilon*abs(y) and n < nmax:
ifactn *= inverse(n)
xn *= x
dy = xn*ifactn
y += dy
n += 1
if n == nmax:
print("ATTENTION : exponentielle non convergée")
return y
x = 17.3
ix = inverse(x)
print(ix, ix - 1./x)
from math import exp
ex = exponentielle(x)
print(f"exp({x}) = {ex} --- erreur : {ex - exp(x)}")
0.057803468208092484 0.0
exp(17.3) = 32605775.719667178 --- erreur : -0.001328691840171814
3.4. Exercice 4#
Dans cet exercice, nous souhaitons trouver une valeur approchée de la solution de \(f(x)=0\) par la méthode de la dichotomie. Nous rappelons que la dichotomie consiste à construire 3 suites \((a_n)\), \((b_n)\) et \((c_n)\) telles que
Question
Proposez une fonction dichotomie
qui prend en arguments
une fonction
f
(argument requis)deux réels
a
etb
(arguments requis)un réel
epsilon
optionnel (valeur par défautepsilon=1.e-5
)un booléen
ret_val_f
optionnel (valeur par défautret_val_f=False
)
et qui retourne un réel c
si ret_val_f
est faux ou deux réels c
et f(c)
si ret_val_f
est vrai. L’algorithme de la dichotomie sera utilisé pour calculer les trois suites et devra s’arréter lorsque \(\vert b_n-a_n\vert\leq 2\epsilon\), ce qui garantie que la valeur c
proposée est une approximation de la solution à \(\epsilon\) près.
La fonction devra également vérifier que les valeurs initiales a
et b
proposées par l’utilisateur vérifient la condition nécessaire \(f(a)f(b)\leq0\).
Essayez de minimiser le nombre d’appel à la fonction (c’est la partie qui peut coûter cher dans l’algorithme).
Show code cell source
def dichotomie(f, a, b, epsilon=1.e-5, ret_val_f=False):
"""
calcule une solution de f(x)=0 sur [a, b] par la méthode de la dichotomie
retourne une valeur approchée à epsilon près
Parameters
----------
f: function
fonction dont on cherche le 0
a: float
borne gauche de l'intervalle de recherche
b: float
borne droite de l'intervalle de recherche
epsilon: float (optional)
critère d'arrêt (default 1.e-5)
ret_val_f: bool (optional)
si True retourne également la valeur de la fonction (default False)
Returns
-------
c: float
la valeur approchée à epsilon près du 0
fc: float
la valeur de f(c) seulement si ret_val_f == True
"""
a, b = min(a, b), max(a, b)
fa, fb = f(a), f(b)
if fa*fb > 0:
print("Erreur dans dichotomie :")
print(f"a = {a}, f(a) = {fa}")
print(f"b = {b}, f(a) = {fb}")
return (None, None) if ret_val_f else None
c = .5*(a+b)
fc = f(c)
while b-a > 2*epsilon:
if fa*fc >= 0:
a, fa = c, fc
if fb*fc >= 0:
b, fb = c, fc
c = .5*(a+b)
fc = f(c)
return (c, fc) if ret_val_f else c
Question
Testez votre fonction dichotomie
pour calculer \(\sqrt{2}\) en cherchant le zéro de la fonction \(x^2-2\) qui se trouve entre \(0\) et \(2\). Vous testerez avec soin que toutes les erreurs potentielles de l’uilisateurs sont bien prises en compte (erreur de données initiales, valeurs par défaut ou non des paramètres…)
Show code cell source
from math import sqrt
f = lambda x: x*x-2
epsilon = 1.e-7
c = dichotomie(f, 0, 2, epsilon=epsilon)
print(f"Valeur de sqrt(2) à {epsilon:10.3e} près : {c} (erreur = {abs(c-sqrt(2)):10.3e})")
Valeur de sqrt(2) à 1.000e-07 près : 1.4142135977745056 (erreur = 3.540e-08)
3.5. Exercice 5#
Dans cet exercice, nous souhaitons programmer une fonction qui tri une liste selon un critère. Nous prendrons des listes de nombres réels pour simplifier.
Le tri par sélection consiste pour un tableau de taille \(N\), à faire une boucle sur tous les indices du tableau. Pour l’indice \(i\), on cherche le minimum du tableau d’indices entre \(i\) et \(N-1\) puis on échange ce minimum pour le mettre à la place d’indice \(i\).
Question
Proposez une fonction
rand
qui prend en argument un entierN
et qui retourne une liste de tailleN
contenant des réels de l’intervalle \([0, 1]\) (on pourra utiliser la fonctionrandom
du modulerandom
.Proposez une fonction
tri_selection
qui prend en argument une liste et qui retourne la liste triée selon l’algorithme du tri par sélection.Testez votre algorithme.
Modifiez votre fonction pour qu’elle accepte un argument optionnel qui sera une fonction d’ordre. Par défaut, vous prendrez la fonction
lambda x, y: True if x < y else False
.Testez votre nouvelle version de l’algorithme.
Show code cell source
from random import random
def rand(N):
"""retourne une liste de taille N contenant des réels alétoires entre 0 et 1"""
l = []
for _ in range(N):
l.append(random())
return l
def tri_selection(T, f=lambda x, y: True if x < y else False):
"""tri par sélection"""
for j in range(len(T)): # tri du j-eme élément
# on cherche le minimum dans le tableau T[j:]
p, val = j, T[j]
for i in range(j+1, len(T)):
if f(T[i], val):
p, val = i, T[i]
# on permute les deux éléments
T[j], T[p] = T[p], T[j]
return T
T = rand(5)
print(T)
print(tri_selection(T))
print(tri_selection(T, lambda x, y: True if x > y else False))
[0.8231700888157593, 0.13732502481132391, 0.9813123957802576, 0.45385245147905795, 0.9988153294769578]
[0.13732502481132391, 0.45385245147905795, 0.8231700888157593, 0.9813123957802576, 0.9988153294769578]
[0.9988153294769578, 0.9813123957802576, 0.8231700888157593, 0.45385245147905795, 0.13732502481132391]
3.6. Exercice 6#
Question
Créez une fonction
mon_max
qui prend en argument un nombre arbitraire de paramètres, chacun de ces paramètres est soit une liste, soit un réel et qui retourne le maximum des éléments en entréeTestez votre fonction
Créez une fonction
mon_min
sur le même modèle quemon_max
et qui utilise cette fonction d’après la formule \(\min(a, b) = - \max(-a, -b)\).(plus dur) Essayez de généraliser vos fonctions pour qu’elles acceptent également des listes de listes… jusqu’à pouvoir mettre en paramètres un nombre arbitraire de niveau de listes et de tuples…
Indication
Pour savoir si un objet l
est une liste, vous pouvez utiliser la commande isinstance(l, list)
.
Indication
Vous pouvez également avoir besoin de créer un nombre plus petit que tous les autres en utilisant la commande -math.inf
du module math
.
Show code cell source
from math import inf
def mon_max(*args):
"""calcule le maximum des éléments passés en paramètres"""
M = -inf
for argk in args:
if isinstance(argk, (list, tuple)):
Mk = mon_max(*argk)
if M < Mk:
M = Mk
else:
if M < argk:
M = argk
return M
def moins(*args):
"""ajoute un moins devant tous les paramètres (récursion sur les niveaux)"""
l = []
for argk in args:
if isinstance(argk, (list, tuple)):
l.append(moins(*argk))
else:
l.append(-argk)
return l
def mon_min(*args):
"""calcule le minimum des éléments passés en paramètres"""
return - mon_max(moins(*args))
print(mon_max([1, (4, 3.2), 3], 67))
print(mon_min(1, 4, [3.2, 3], (67, 0.5), [[1, 2, 3], (-5, 2, 3)]))
67
-5
3.7. Exercice 7#
Question
Créez une fonction
composition
qui prend en argument un nombre arbitraire de fonctions \(f_0, \ldots, f_n\) et qui retourne la fonction \(f = f_0\circ \ldots \circ f_n\) où \(\circ\) est la composition.Testez votre fonction
composition
en calculant \(f\circ g\) où \(g:x\mapsto x^2\) et \(f:x\mapsto\sqrt{x}\). La fonction obtenue doit être la fonction valeur absolue.
Show code cell source
def composition(*args):
"""composition de fonctions"""
def f(x):
y = 1.*x
for arg in args[::-1]:
y = arg(y)
return y
return f
from math import sqrt
f1 = lambda x: x**2
f2 = lambda x: sqrt(x)
f = composition(f2, f1)
print(f(-1.5))
1.5