Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Suite de Fibonacci La suite de Fibonacci est une suite d'entiers très connue. E

Suite de Fibonacci La suite de Fibonacci est une suite d'entiers très connue. Elle doit son nom au mathématicien italien Leonardo Pisano, plus connu sous le pseudonyme de Fibonacci (1175 - 1250). Dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, Fibonacci décrit la croissance d'une population de lapins : « Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? » Ce problème est à l'origine de la suite dont le -ème terme correspond au nombre de paires de lapins au -ème mois. Dans cette population (idéale), on suppose que : • le premier mois, il y a juste une paire de lapereaux ; • les lapereaux ne sont pubères qu'à partir du deuxième mois ; • chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapereaux ; • les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante). Présentation mathématique Formule de récurrence Notons le nombre de couples de lapins au mois . Jusqu’à la fin du deuxième mois, la population se limite à un couple (ce qu'on note : ). Dès le début du troisième mois, le couple de lapins a deux mois et il engendre un autre couple de lapins. On note alors . Plaçons-nous maintenant au mois et cherchons à exprimer ce qu'il en sera deux mois plus tard : désigne la somme des couples de lapins au mois et des couples nouvellement engendrés. Or, n'engendrent au mois que les couples pubères, c'est-à-dire ceux qui existent deux mois auparavant. On a donc : . Nous obtenons ainsi la forme récurrente de la suite de Fibonacci : chaque terme de cette suite est la somme des deux termes précédents ; pour obtenir chacun de ces deux termes, il faut faire la somme de leurs termes précédents… et ainsi de suite, jusqu'à ce que ces deux termes soient les deux termes initiaux, et , qui sont connus. Nombres de Fibonacci Les termes de cette suite sont appelés nombres de Fibonacci (suite A000045 de l’OEIS) : 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 159 7 258 4 418 1 676 5 1094 6 1771 1 2865 7 4636 8 7502 5 ... Expression fonctionnelle On souhaite établir une expression fonctionnelle de la suite de Fibonacci, c'est-à-dire une expression telle que le calcul du nombre de couples pour une valeur de donnée ne présuppose la connaissance d’aucun nombre de couples pour une quelconque autre valeur de , ce que ne permet pas la formule de récurrence. Comme la suite de Fibonacci est récurrente d’ordre deux, on peut écrire son équation caractéristique. On obtient une équation du second degré : . Le calcul du discriminant de cette équation donne les deux solutions du polynôme : et . ( est le nombre d'or). Les suites et engendrent alors l'espace vectoriel des suites vérifiant un + 2 = un + 1 + un. Il en résulte que : ( et sont des constantes à déterminer à partir de et .) Les conditions initiales et conduisent au système suivant : Ce qui donne le résultat suivant : et . Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de formule de Binet : . Il existe d'autres démonstrations telles que la transformation en Z et la technique des fonctions génératrices. Remarquons qu'une fois découverte cette formule se démontre aussi par récurrence. La suite pour les nombres négatifs En général, on n'étudie pas les nombres de Fibonacci pour des valeurs négatives de n, bien qu'ils existent et soient facilement déterminables avec la formule récurrente. Il existe ainsi une règle très simple pour calculer ces nombres quand n < 0 : • si n est pair alors • si n est impair alors Ainsi, autour de 0, la séquence est : Limite des quotients Comme l'a remarqué Johannes Kepler, le taux de croissance des nombres de Fibonacci, c'est-à-dire , converge vers le nombre d'or, noté . Mathématiquement, le résultat s'obtient ainsi : (en simplifiant par ) (comme , ) Plus précisément, quand tend vers l'infini, le second terme tend vers zéro car , ainsi les nombres de Fibonacci se comportent comme une exponentielle multipliée par le facteur , soit . En fait, dès le rang , le deuxième terme est assez petit pour que les nombres de Fibonacci puissent être obtenus uniquement à partir du premier terme, en arrondissant à l'entier le plus proche. Bases et espaces vectoriels • La dénomination de « suite de Fibonacci généralisée » est attribuée plus généralement à toute fonction définie sur vérifiant pour tout entier naturel , . Ces fonctions sont précisément celles pour lesquelles il existe des nombres a et b, tels que pour tout entier naturel n, . Ainsi, l'ensemble des suites de Fibonacci est un espace vectoriel, et les suites et en forment une base. • Le nombre d'or est la racine positive de l'équation du second degré , ainsi . Si on multiplie les deux côtés par , on obtient , donc la fonction est une suite de Fibonacci. La racine négative de l'équation du second degré, , possède les mêmes propriétés, et les deux fonctions linéairement indépendantes et , forment une autre base de l'espace vectoriel. Algorithmes de calcul des nombres de Fibonacci Avec la formule de Binet Calculer les nombres de Fibonacci à partir du nombre d'or est une possibilité très pratique. Néanmoins, la précision de calcul de la racine carrée génère des erreurs d'arrondis pour des valeurs assez grandes dépendant du système utilisé. En général, on obtient les bonnes valeurs jusqu’à , sur ordinateur ou sur calculatrice. Notons qu’au-delà de , les calculs dépassent les possibilités de calcul en notation entière, et sont alors représentés en notation scientifique. Les premiers chiffres significatifs sont alors de nouveau bien représentés par cette formule. Détail d’un exemple d'application faisable à partir d'une calculatrice : Calcul de . Le nombre d’or vaut : Appliquons la formule de Binet, (en ne retenant que le terme significatif) soit : Arrondissons à l’entier le plus proche soit : Algorithme récursif naïf L'implémentation récursive naïve qui suit la définition de la suite de Fibonacci est immédiate. En Python, cela donne : def fibo(n): if (n <= 1): # cas de base return n # si n=0 return 0, si n=1 return 1 else: # récurrence return fibo(n - 1) + fibo(n - 2) Ce n'est cependant pas une façon judicieuse de calculer la suite de Fibonacci, car on calcule de nombreuses fois les mêmes valeurs (à moins d'employer une technique de mémoization). Le temps de calcul s'avère exponentiel. Algorithme linéaire [modifier] Un moyen bien plus efficace de calculer la suite de Fibonacci consiste à calculer simultanément deux valeurs consécutives de la suite, c'est-à-dire en commençant avec les deux premières valeurs 0 et 1, et en remplaçant répétitivement le premier nombre par le second, et le second nombre par la somme des deux. En Python, un tel algorithme itératif donne : def fibo(n): f_n_1 = 1 # F_{-1} = 1 f_n = 0 # F_0 = 0 for i in range(n): # n fois f_n_1, f_n = (f_n, f_n + f_n_1) return f_n De manière équivalente, on peut écrire une fonction récursive terminale : def fibo(n, f_n_1 = 1, f_n = 0): # (n, F_{n-1}, F_n) if (n == 0): # cas de base return f_n else: # récurrence return fibo(n - 1, f_n, f_n + f_n_1) Le temps de calcul est à chaque fois proportionnel à n et l'espace mémoire occupé constant. Algorithme logarithmique En utilisant la relation matricielle suivante, que l'on montre par récurrence : ou avec les #Propriétés de la suite de Fibonacci, on obtient : En prenant bien soin de ne pas calculer deux fois les mêmes éléments, on obtient alors un algorithme dont le temps de calcul est proportionnel au logarithme de n. Voici un exemple de programme en Python : def fibo2(n): """Renvoie F_{n-1}, F_n""" if (n == 0): # cas de base return 1, 0 # F_{-1}, F_0 else: # récurrence f_k_1, f_k = fibo2(n//2) # F_{k-1}, F_k avec k = n/2 f2_k = f_k**2 # F_k^2 if n%2 == 0: # n pair return f2_k + f_k_1**2, f_k*f_k_1*2 + f2_k # F_{2k-1}, F_{2k} else: # n impair return f_k*f_k_1*2 + f2_k, (f_k + f_k_1)**2 + f2_k # F_{2k}, F_{2k+1} def fibo(n): """Renvoie F_n""" return fibo2(n)[1] En retravaillant les relations de récurrence pour le cas pair on obtient : Et donc : Curiosité algorithmique Une façon particulièrement curieuse d'obtenir la suite de Fibonacci est la suivante. On considère la liste de fractions [23/95, 57/23, 17/39, 130/17, 11/14, 35/11, 19/13, 1/19, 35/2, 13/7, 7]. Si on part d'un entier de la forme 2F(n − 1)3F(n) et si on le multiplie itérativement par la première fraction qui redonne un résultat entier, alors le premier nombre entier de la suite ainsi obtenue qui uploads/s3/ suite-de-fibonacci.pdf