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

1. Créez une fonction suite_recurrente qui prend en argument

   • une fonction f utilisée pour la récurrence

   • un réel u0 utilisé pour initialisé la suite

   • un entier N et qui retourne la liste des N premiers termes de la suite définie par récurrence

2. 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 Hide 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 :

\[ f'(a) \approx_{h\to 0} \frac{f(a+h)-f(a)}{h} \approx_{h\to 0} \frac{f(a+h)-f(a-h)}{2h}. \]

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

1. Définissez une fonction f ainsi qu’une fonction df qui prennent en argument un réel x et qui retournent respectivement la valeur de \(f\) et de sa dérivée au point \(x\).

2. Calculez les deux approximations proposées pour \(h=2^{-k}\) avec \(k\in\lbrace2, 4, 6, \ldots, 98\rbrace\).

3. 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 |
     ...
     --------------------------------------------------------------------------------------

4. Décrivez et expliquez le comportement de ces deux suites ?

Show code cell source Hide 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 à

1. 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) ;

2. construire la suite \((z_n)\) définie par \(z_0=1\), \(z_{n+1}=z_n(2-yz_n)\) ;

3. 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) ;

4. 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éel x et un argument optionnel epsilon et qui retourne l’inverse de x approchée par l’algorithme précédent. La valeur de epsilon 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 :

\[ \exp(x) \sim \sum_{n=0}^{N} \frac{x^n}{n!}.\]

Questions

• Proposez une fonction exponentielle qui prend en argument un réel x et qui calcule l’approximation de exp(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 Hide 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

\[\begin{split} f(a_0) f(b_0) < 0, \quad c_n = \frac{a_n+b_n}{2}, \quad a_{n+1} = \left\lbrace\begin{aligned} c_n&\text{ si } f(a_n)f(c_n) \geq 0,\\ a_n&\text{ sinon}, \end{aligned}\right. \quad b_{n+1} = \left\lbrace\begin{aligned} c_n&\text{ si } f(b_n)f(c_n) \geq 0,\\ b_n&\text{ sinon}. \end{aligned}\right.\end{split}\]

Question

Proposez une fonction dichotomie qui prend en arguments

• une fonction f (argument requis)

• deux réels a et b (arguments requis)

• un réel epsilon optionnel (valeur par défaut epsilon=1.e-5)

• un booléen ret_val_f optionnel (valeur par défaut ret_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 Hide 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 Hide 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

1. Proposez une fonction rand qui prend en argument un entier N et qui retourne une liste de taille N contenant des réels de l’intervalle \([0, 1]\) (on pourra utiliser la fonction random du module random.

2. 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.

3. Testez votre algorithme.

4. 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.

5. Testez votre nouvelle version de l’algorithme.

Show code cell source Hide 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

1. 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ée

2. Testez votre fonction

3. Créez une fonction mon_min sur le même modèle que mon_max et qui utilise cette fonction d’après la formule \(\min(a, b) = - \max(-a, -b)\).

4. (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 Hide 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

1. 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.

2. 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 Hide 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