Accueil › Cours › Approximation et optimisation
Approximation de π et e, dichotomie, point fixe, aires, optimisation
Calcule π et e à une précision donnée, trouve le zéro d'une fonction, une aire sous une courbe, et la meilleure solution d'un problème.
Les leçons de ce chapitre
- Valeurs approchées de π et de e
- Le zéro d'une fonction et le point fixe
- Calcul d'aires : rectangles et trapèzes
- Problèmes d'optimisation
Leçon 20.1 : Valeurs approchées de π et de e
Certaines constantes s'obtiennent comme la somme d'une infinité de termes de plus en plus petits. On ne peut pas tout additionner : on s'arrête quand le terme devient plus petit qu'une précision eps (par exemple 0.0001). Comme on ne connaît pas le nombre de tours à l'avance, on utilise Tant que.
- π (série de Leibniz) : π / 4 = 1 − 1/3 + 1/5 − 1/7 + … Le signe change à chaque terme.
- e : e = 1 + 1/1! + 1/2! + 1/3! + … Chaque terme s'obtient à partir du précédent :
terme ← terme / k.
Astuce : Calculer chaque terme à partir du précédent évite de recalculer une factorielle à chaque tour : c'est plus rapide.
Attention : Une précision plus fine (eps plus petit) demande beaucoup plus de tours. La série de Leibniz est lente : pour eps = 0.0001, il faut 5000 termes.
En Python
Valeur approchée de e : on ajoute les termes 1/k! tant qu'ils dépassent eps.
eps = 0.000001
s = 1
terme = 1
k = 1
while terme > eps:
terme = terme / k
s = s + terme
k = k + 1
print("e vaut environ", s)
print("Termes ajoutés :", k - 1)En algorithme
Les variables s et terme sont des réels.
Algorithme ValeurDeE
Début
eps ← 0.000001
s ← 1
terme ← 1
k ← 1
Tant que terme > eps Faire
terme ← terme / k
s ← s + terme
k ← k + 1
FinTantQue
Ecrire("e vaut environ ", s)
Ecrire("Termes ajoutés : ", k - 1)
Fin
TDO
Objet | Type/Nature
eps, s, terme | Réel
k | EntierLeçon 20.2 : Le zéro d'une fonction et le point fixe
Pour résoudre f(x) = 0 sur un intervalle [a, b] où f change de signe, la dichotomie coupe l'intervalle en deux : on calcule le milieu m, et on garde la moitié où le signe change encore (f(a) × f(m) ≤ 0 : la solution est dans [a, m]). On s'arrête quand b − a est plus petit que eps.
Le point fixe d'une fonction g est un x tel que g(x) = x. On part d'une valeur x0 et on répète x ← g(x) jusqu'à ce que deux valeurs successives soient presque égales (|x − ancien| < eps).
Astuce : La fonction f s'écrit une seule fois comme une fonction (DEF FN f), puis on l'appelle autant que nécessaire.
En Python
Zéro de f(x) = x³ + x − 1 sur [0, 1] à 0.001 près.
def f(x):
return x ** 3 + x - 1
a = 0
b = 1
eps = 0.001
while b - a > eps:
m = (a + b) / 2
if f(a) * f(m) <= 0:
b = m
else:
a = m
print("Zéro proche de", (a + b) / 2)En algorithme
La fonction f est un module : DEF FN f (x : Réel) : Réel.
DEF FN f (x : Réel) : Réel
Début
Retourner x ^ 3 + x - 1
Fin
Algorithme Dichotomie
Début
a ← 0
b ← 1
eps ← 0.001
Tant que b - a > eps Faire
m ← (a + b) / 2
Si f(a) * f(m) ≤ 0 Alors
b ← m
Sinon
a ← m
FinSi
FinTantQue
Ecrire("Zéro proche de ", (a + b) / 2)
Fin
TDO
Objet | Type/Nature
a, b, eps, m | RéelLeçon 20.3 : Calcul d'aires : rectangles et trapèzes
Pour calculer l'aire sous la courbe de f entre a et b, on découpe [a, b] en n bandes de largeur h = (b − a) / n, et on additionne des aires simples.
- Rectangles (à gauche) : S = h × (f(a) + f(a + h) + … + f(a + (n − 1) h)).
- Trapèzes : S = h × ((f(a) + f(b)) / 2 + f(a + h) + … + f(a + (n − 1) h)). Plus précis pour le même n.
Astuce : Plus n est grand, plus le résultat est proche de l'aire exacte. Pour f(x) = x² sur [0, 1], l'aire exacte est 1/3.
En Python
Aire sous f(x) = x² sur [0, 1] par les rectangles, avec n = 100.
def f(x):
return x * x
a = 0
b = 1
n = 100
h = (b - a) / n
s = 0
for i in range(n):
s = s + f(a + i * h)
print("Aire (rectangles) :", s * h)En algorithme
La boucle Pour va de 0 à n − 1 : un rectangle par bande.
DEF FN f (x : Réel) : Réel
Début
Retourner x * x
Fin
Algorithme Rectangles
Début
a ← 0
b ← 1
n ← 100
h ← (b - a) / n
s ← 0
Pour i de 0 à n - 1 Faire
s ← s + f(a + i * h)
FinPour
Ecrire("Aire (rectangles) : ", s * h)
Fin
TDO
Objet | Type/Nature
a, b, h, s | Réel
n, i | EntierLeçon 20.4 : Problèmes d'optimisation
Un problème d'optimisation cherche la meilleure solution parmi toutes les possibles : le moins de pièces, la plus grande aire, le coût le plus bas…
- Essayer toutes les possibilités et garder la meilleure (avec une variable « meilleur », comme pour un maximum).
- Ou une méthode gloutonne : à chaque étape, prendre ce qui paraît le meilleur tout de suite. Pour rendre la monnaie en dinars, on prend toujours la plus grosse pièce possible.
Astuce : On compte l'argent en millimes (entiers) : 1 DT = 1000 millimes. Les entiers évitent les erreurs d'arrondi des réels.
En Python
Rendre une somme (en millimes) avec le moins de pièces et billets possible.
pieces = [20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10]
reste = int(input())
nb = 0
for i in range(len(pieces)):
while reste >= pieces[i]:
reste = reste - pieces[i]
nb = nb + 1
print(pieces[i])
print("Nombre de pièces et billets :", nb)En algorithme
Le tableau P contient les valeurs, de la plus grande à la plus petite.
Algorithme Monnaie
Début
P[1] ← 20000
P[2] ← 10000
P[3] ← 5000
P[4] ← 2000
P[5] ← 1000
P[6] ← 500
P[7] ← 200
P[8] ← 100
P[9] ← 50
P[10] ← 20
P[11] ← 10
Lire(reste)
nb ← 0
Pour i de 1 à 11 Faire
Tant que reste ≥ P[i] Faire
reste ← reste - P[i]
nb ← nb + 1
Ecrire(P[i])
FinTantQue
FinPour
Ecrire("Nombre de pièces et billets : ", nb)
Fin
TDO
Objet | Type/Nature
P | Tableau de 11 Entiers
reste, nb, i | EntierS'entraîner gratuitement
Chaque leçon a 3 exercices gratuits avec indices pour appliquer ce chapitre avec Hannibot.
← Chapitre précédent : Interfaces graphiques avec Qt · Chapitre suivant : La récursivité →
Tous les chapitres · Voir les devoirs corrigés de 2ème TI
Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.