Approximation numérique par balayage

L'approximation numérique est un vaste champ d'application de l'informatique. L'objectif est d'obtenir une estimation d'un résultat difficile et parfois impossible à obtenir par des méthodes mathématiques exactes.

Dans cette leçon allons nous allons déterminer des approximations de $\sqrt{2}$ , la solution positive de l'équation $x^2 = 2$ .

D'après la représentation graphique de la fonction carrée ci-dessous, on a $f(1{,}4)\approx 2$ donc l'antécédent de 2 est approximativement 1,4. Ça nous donne un point de départ ainsi qu'un encadrement : le nombre que l'on cherche est clairement entre 1 et 1,8.

La fonction

f(x)=x^2

1
Pour commencer, défini dans l'éditeur la fonction f qui prend un argument x en entrée et renvoie son carré
Solution

On définit la fonction carrée en utilisant ** pour la puissance
```
def f(x):
	return x ** 2
```
2
On va calculer les valeurs $f(1)$ , $f(1{,}1)$ , $f(1{,}2)$ , $f(1{,}3)$ etc. On appelle ça faire un « balayage » des valeurs.

Comme la fonction $f$ est strictement croissante, pour les abscisses inférieures à $\sqrt{2}$ on a $f(x) \lt 2$ et cette inégalité est fausse pour les abscisses supérieures à $\sqrt{2}$ .

$x$ $f(x) \lt 2$

1.2 Vrai
1.3 Vrai
1.4 Vrai

1.5 Faux

Cette observation nous donne un critère pour déterminer la valeur approchée : c'est la plus grande valeur pour laquelle l'inégalité est vraie.

Comme on ne sait pas combien de valeurs il faut calculer avant que la condition soit fausse on va utiliser une boucle while. L'idée du code est donc la suivante :
```
1. Prendre une abscisse initiale pour laquelle f(a) < 2
2. Tant que f(a) < 2  incrémenter l'abscisse de 0.1 en 0.1
			et s'arrêter dès que l'inégalité est fausse
3. Renvoyer la plus grande abscisse trouvée
			
```
Défini une fonction balayage qui implémente la logique précédente : dans le corps de la fonction initialise une variable a à 1. C'est une abscisse de départ qui vérifie $f(a) \lt 2$ . Puis crée une boucle while qui incrémente l'abscisse a de 0.1 tant que l'inégalité est vraie. Enfin renvoie l'abscisse trouvée.
Solution

En-dessous de la fonction f on définit la fonction balayage. Elle ne prend pas d'argument pour le moment.

Tout d'abord cette fonction initialise une variable a à 1. C'est l'abscisse de départ. Ensuite, la boucle while : tant que l'abscisse vérifie la condition $f(a) \lt 2$ on incrémente sa valeur de 0.1

Comme la fonction est strictement croissante, la condition $f(a) \lt 2$ finit par ne plus être vérifiée, et la boucle while s'arrête. On renvoie alors l'abscisse a trouvée.
```
def f(x):
    return x**2

def balayage():
    a = 1
    while f(a) < 2:
        a =  a + 0.1
    return a
```
3
On dit que la fonction de la question précédente réalise un balayage d'amplitude 0,1. On appelle également ce nombre le pas, c'est l'écart entre les différentes abscisses calculées.

Pour améliorer la fonction balayage et obtenir une approximation aussi précise que l'on veut, on va faire varier le pas.

Modifie la fonction balayage pour qu'elle prenne un argument qui correspond au pas, et adapte l'algorithme pour incrémenter l'abscisse de ce pas à chaque itération.
Solution

On donne un argument à la fonction balayage par exemple pas. Ensuite dans la boucle while on incrémente a de cette quantité
```
def f(x):
    return x**2

def balayage(pas):
    a = 1
    while f(a) < 2:
        a =  a + pas
    return a
```
4
Il ne reste plus qu'à utiliser la fonction balayage pour obtenir des approximations de $\sqrt{2}$ .

Appelle la fonction balayage dans la console avec un pas de 10**-1 puis 10**-2 puis 10**-3 et observe l'amélioration des approximations.
Solution

On appelle la fonction balayage avec un pas de 0,1 puis 0,01 puis 0,001
```
>>> balayage(10**-1) 
1.5000000000000004
>>> balayage(10**-2) 
1.4200000000000004
>>> balayage(10**-3) 
1.4149999999999543
```
5
Lorsqu'on crée un algorithme, le temps qu'il met à faire les calculs est un paramètre important : plus il est rapide mieux c'est ! Car s'il est rapide on obtient facilement de bonnes approximations.

Pour comprendre le temps de calcul pris par la fonction balayage on va compter combien de fois la boucle while s'exécute. Cela nous permettra de déterminer comment le temps de calcul augmente lorsque le pas diminue, et nous donnera un moyen de comparer cet algorithme avec celui de la leçon suivante.

Dans la fonction balayage initialise une variable compteur à 0 et incrémente ce compteur de 1 à chaque itération de la boucle while. Enfin, renvoie la valeur de ce compteur ainsi que la valeur approchée de $\sqrt{2}$ . Pour renvoyer plusieurs valeurs tu peux les séparer par une virgule. Renvoie l'approximation en premier, le compteur en deuxième.
Solution

On initialise compteur à zéro avant la boucle while, puis à chaque itération on incrémente ce compteur de 1. Enfin on renvoie cette variable avec a en les séparant par une virgule.
```
def f(x):
    return x**2

def balayage(pas):
    a = 1
    compteur = 0
    while f(a) < 2:
        a =  a + pas
        compteur = compteur + 1
    return a, compteur
```
6
Appelle la fonction balayage dans la console pour connaître le nombre d'itérations lorsque le pas diminue, en commençant à $10^{-1}$ puis $10^{-2}$ jusqu'à $10^{-6}$
Solution

On constate que la boucle while fait 5 itérations lorsque le pas est de $10^{-1}$ , elle en fait 42 avec un pas de $10^{-2}$ , et elle en fait 415 avec un pas de $10^{-3}$ etc.
```
>>> balayage(10**-1)
1.5000000000000004,5
>>> balayage(10**-2)
1.4200000000000004,42
>>> balayage(10**-3)
1.4149999999999543,415
```
7
Généralisation : ton code peut être adapté pour trouver d'autres approximations !

Par exemple, modifie le code de la fonction balayage pour calculer des approximations numériques de $\sqrt{5}$ puis appelle ta fonction dans la console pour déterminer $\sqrt{5}$ à $10^{-3}$ près.
Solution

Il faut modifier la condition d'arrêt de la boucle while qui doit s'exécuter tant que $f(x)\lt 5$ .
```
def f(x):
    return x**2

def balayage(pas):
    a = 1
    compteur = 0
    while f(a) < 5:
        a =  a + pas
				compteur = compteur + 1
    return a, compteur
```
Il ne reste plus qu'à déterminer la valeur approchée de $\sqrt{5}$ à $10^{-3}$ près
```
>>> balayage(10**-3)
2.2369999999998638,1237
```

$x$	$f(x) \lt 2$
1.2	Vrai
1.3	Vrai
1.4	Vrai
1.5	Faux

Comment améliorer cet algorithme ? Il faudrait faire des « sauts » pour diminuer le nombre d'itérations et éviter de trop de calculs. Dans la leçon suivante nous allons justement voir un algorithme beaucoup plus rapide qui implémente ce genre de stratégie : l'algorithme de dichotomie.