Suites récurrentes
Un classique…
Générer des suites avec des formules de récurrence
Vous devriez pouvoir proposer deux programmes assez différents qui prennent en argument une fonction $f:\mathbf{X}\to\mathbf{X}$, une valeur $a\in\mathbf{X}$ et un entier naturel $n\in\mathbf{N}$, et qui renvoie la valeur de $u_n$ défini par: \[ \left\{\begin{array}{rcl} u_0 & = & a \\ u_{n+1} & = & f(u_n) \end{array}\right. \] (et pour ça, vous n’avez pas vraiment besoin de connaître l’ensemble $\mathbf{X}$).
'''Retourne la valeur de `u(n)` défini par `u(0)==a` et `u(n+1)==f(u(n))`,
calculée récursivement.'''
…
'''Retourne la valeur de `u(n)` défini par `u(0)==a` et `u(n+1)==f(u(n))`,
calculée par itération (grâce à une boucle).'''
…
Vous pouvez tester que ça fonctionne, en vérifiant que:
== 100
et
== 100
Si vous ne comprenez pas le lambda x: x+1, allez voir ce qu’est une
fonction anonyme.
Et maintenant, redéfinissez les deux fonctions avec seulement deux arguments,
pour que suite_recursion(f, a) et suite_iteration(f, a) renvoient une
nouvelle fonction qui calcule la suite.
Vous pouvez tester:
=
== True
(voir la spécification de all() si nécessaire).
Fibonacci
On rappelle que la suite de Fibonacci \( (F_n)_{n\in\mathbf N} \) vérifie:
\[
\left\{\begin{array}{rcl}
F_0 & = & 0 \\
F_1 & = & 1 \\
F_{n+2} & = & F_{n+1}+F_{n}
\end{array}\right. \ .
\]
Sur le même modèle que précédemment, définissez deux fonctions
fibonaci_recursion(n) et fibonacci_iteration(n) avec le sens évident.
Et maintenant testez:
==
Comment aurait-on pu utiliser suite_recursion et suite_iteration
plutôt que les définir à la main?
Et maintenant testez:
==
==
Comprenez-vous ce qui se passe dans chaque cas?
Formule de Binet
La suite de Fibonacci est une suite récurrente linéaire d’ordre 2, pour lesquelles on peut obtenir une expression explicite de manière standard.
On pose donc \( G_n = (F_n,F_{n+1}) \) pour obtenir: \[ \left\{\begin{array}{rcl} G_0 & = & \left(\begin{array}{c}0\\1\end{array}\right) \\ G_{n+1} & = & \left(\begin{array}{cc}0&1\\1&1\end{array}\right) G_n \end{array}\right. \] et donc $ G_{n} = A^n G_{0} $ où $ A = \left(\begin{array}{cc}0&1\\1&1\end{array}\right) $.
Le polynome caractéristique de $ A $ est $ X^2-X-1 $ dont les racines sont le nombre d’or $ φ = \frac{1+\sqrt{5}}{2} $ et son inverse $ \bar{φ} = \frac{-1+\sqrt{5}}{2} $. Donc (est-clair pour vous?) on peut écrire $ F_n = λφ^n + μ\bar φ^n $. Un calcul rapide donne \[ F_n = \frac{φ^n-\bar φ^n}{\sqrt{5}} \] (c’est la formule de Binet).
Définissez une fonction fibonacci_binet(n) utilisant cette formule.
Et maintenant testez:
==
et commentez…