Suite récurrente linéaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (août 2014).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

En mathématiques, on appelle suite récurrente linéaire d’ordre p toute suite à valeurs dans un corps commutatif K (par exemple ou ) définie pour tout par une relation de récurrence linéaire de la forme

, , … sont p scalaires fixés de K ( non nul).

Une telle suite est entièrement déterminée par la donnée de ses p premiers termes et par la relation de récurrence.

Les suites récurrentes linéaires d’ordre 1 sont les suites géométriques.

L'étude des suites récurrentes linéaires d'ordre supérieur se ramène à un problème d'algèbre linéaire. L'expression du terme général d'une telle suite est possible pour peu qu'on soit capable de factoriser un polynôme qui lui est associé, appelé polynôme caractéristique ; le polynôme caractéristique associé à une suite vérifiant la relation de récurrence ci-dessus est :

Son degré est ainsi égal à l'ordre de la relation de récurrence. En particulier, dans le cas des suites d'ordre 2, le polynôme est de degré 2 et peut donc être factorisé à l'aide d'un calcul de discriminant. Ainsi, le terme général des suites récurrentes linéaires d'ordre 2, peut être exprimé en utilisant seulement les deux premiers termes, quelques valeurs constantes, quelques opérations élémentaires de l'arithmétique (addition, soustraction, multiplication, exponentielle) et les fonctions sinus et cosinus (si le corps des scalaires est le corps des réels). Une des suites de ce type est la célèbre suite de Fibonacci, qui peut s'exprimer à partir de puissances faisant intervenir le nombre d'or.

Suite récurrente linéaire d’ordre 1[modifier | modifier le code]

Les suites récurrentes linéaires d'ordre 1 sont les suites géométriques.

Si la relation de récurrence est , le terme général est .

Suite récurrente linéaire d’ordre 2[modifier | modifier le code]

a et b étant deux scalaires fixés de K avec b non nul, la relation de récurrence est

On va prouver que le terme général d'une telle suite à valeurs dans K, est

  • si et sont deux racines distinctes (dans K) du polynôme ,
  • si est racine double du polynôme ,

avec paramètres dans K déterminés par les deux premières valeurs de la suite.

On va prouver de plus que dans le premier de ces deux cas, si les deux racines du polynôme sont deux complexes conjugués et , alors le terme général de la suite s'écrit également

  • avec A et B paramètres dans K déterminés par les deux premières valeurs de la suite.

On ne perd rien à la généralité de la suite en supposant que celle-ci est définie sur tout et pas seulement à partir de . En effet, l'étude d'une suite u qui n’est définie qu’à partir de se ramène à celle de la suite v définie sur ℕ par .

L’idée est alors de rechercher des suites géométriques vérifiant la récurrence (R). C’est-à-dire chercher des scalaires r tels que la suite vérifie (R). On démontre aisément que ce problème équivaut à résoudre l’équation du second degré . Le polynôme est alors appelé le polynôme caractéristique de la suite. Son discriminant est . Il faudra alors distinguer plusieurs cas, selon le nombre de racines du polynôme caractéristique.

Si le polynôme possède deux racines distinctes[modifier | modifier le code]

Soient et les deux racines distinctes. Les suites et vérifient (R) ainsi que toute suite dont le terme général serait (cela tient au caractère linéaire de la récurrence). A-t-on alors trouvé toutes les suites vérifiant (R) ? Une suite vérifiant (R) étant entièrement déterminée par la donnée de et , il suffit de prouver que l’on peut toujours trouver et solutions du système

Or ce système a pour déterminant non nul. Il est donc toujours possible d’exprimer une suite vérifiant (R) comme combinaison linéaire des suites et

Cette situation se produit pour toute suite à valeurs réelles pour laquelle le discriminant est strictement positif, ou pour toute suite à valeurs complexes pour laquelle le discriminant est non nul.

Si le polynôme possède une racine double[modifier | modifier le code]

Si le discriminant est nul, le problème est tout autre car on ne trouve qu’une seule valeur , donc une seule famille de suites géométriques vérifiant (R). L’idée consiste alors à rechercher les suites telles que, pour tout entier n, avec vérifiant (R). Cette méthode s’appelle la méthode de variation de la constante. On s’assure d’abord de l’existence de la suite en vérifiant que n’est jamais nul. La relation de récurrence sur se traduit par une relation de récurrence sur  :

En utilisant ensuite le fait que et que , on obtient la relation caractéristique de toute suite arithmétique :

La suite est donc une suite arithmétique de terme général

.

Les suites vérifiant (R) ont alors pour terme général :

.

Ce résultat s'applique pour des suites à valeurs réelles ou complexes pour lesquelles le discriminant du polynôme caractéristique est nul.

Cas particulier de deux racines distinctes conjuguées[modifier | modifier le code]

C'est le cas si le polynôme caractéristique est à coefficients réels et à discriminant strictement négatif. L’équation du second degré possède alors dans ℂ deux racines conjuguées

et , distinctes.

Le résultat du premier des deux cas ci-dessus s'applique : les suites complexes vérifiant (R) sont donc les suites de terme général , avec paramètres complexes. Par le changement de paramètres , ce sont aussi les suites de termes général avec A, B paramètres complexes.

Les suites réelles vérifiant (R) sont donc les suites de terme général

avec A et B paramètres réels. En effet, la condition sur les paramètres A, B (complexes a priori) pour que cette suite soit à valeurs réelles est que A et B soient réels : c'est immédiat dans un sens (si A, B sont réels alors la suite est réelle), et pour la réciproque il suffit de remarquer que et non nul (donc si sont réels alors A et B aussi).

Identités remarquables[modifier | modifier le code]

Si une suite u vérifie

alors, elle peut être étendue aux indices négatifs et reliée aux puissances de la matrice

(inversible puisque b ≠ 0) par :

Ceci permet de montrer que pour v égale à u ou à toute autre suite vérifiant la même relation de récurrence (R) et pour tous entiers i, j, k, l et r[1] :

En particulier :

Suite récurrente d’ordre p[modifier | modifier le code]

Sous-espace vectoriel de dimension p[modifier | modifier le code]

Si l'on appelle la relation de récurrence :

pour tout entier n,

et si l'on note , l’ensemble des suites à valeurs dans K et vérifiant , on démontre que est un sous-espace vectoriel de l'espace des suites à valeurs dans K. Cela tient à la linéarité de la relation de récurrence.

De plus, ce sous-espace est de dimension p. En effet, il existe un isomorphisme d'espaces vectoriels entre et  : à chaque suite u de , on associe le p-uplet . Il suffit alors de connaître une famille libre de p suites vérifiant , l’ensemble est alors engendré par cette famille libre.

Terme général[modifier | modifier le code]

La recherche du terme général et des suites particulières s’effectue en travaillant sur . À chaque suite on associe la suite définie par

La relation de récurrence sur induit une relation de récurrence sur

(A est la matrice compagnon du polynôme caractéristique de la suite).

Le terme général de la suite U est alors déterminé par[2]

Le problème semble alors terminé. Mais la réelle difficulté consiste alors à calculer … On préfère déterminer une base de .

Recherche d'une base[modifier | modifier le code]

Le polynôme caractéristique de la matrice A est . Ce n'est pas un hasard si on le retrouve pour caractériser les suites vérifiant .

On note f la transformation linéaire qui, à une suite associe la suite définie par . La condition « u vérifie  » se traduit alors par P(f)(u) = 0. L'ensemble est donc le noyau de P(f). Si P est un polynôme scindé dans K (ce qui est toujours vrai si K = ℂ), il existe k racines et k exposants tel que . Le noyau de P(f) est alors la somme directe des noyaux des . Il suffit donc de trouver une base de chacun de ces noyaux pour déterminer une base de .

On peut montrer que toute suite de terme général est élément du noyau de pour peu que le degré de Q soit inférieur strictement à . Cette démonstration se fait par récurrence sur . Comme les suites , pour j = 0 à forment une partie libre de éléments[3], la famille de toutes les suites , pour j = 0 à et pour i = 1 à k forme une famille libre de éléments de (de dimension p) donc une base de . Les éléments de sont donc des sommes de suites dont le terme général est avec degré de Q strictement inférieur à .

Retour à la récurrence d'ordre 2[modifier | modifier le code]

Si le polynôme caractéristique se scinde en alors les polynômes Q sont de degré 0 et les éléments de sont des suites dont le terme général est .

Si le polynôme caractéristique se scinde en alors les polynômes Q sont de degré 1 et les éléments de sont des suites dont le terme général est .

Notes et références[modifier | modifier le code]

  1. (en) Robert C. Johnson, « Fibonacci numbers and matrices », sur Université de Durham,‎ , p. 40 (A.10).
  2. Jean-Marie Monier, Algèbre et géométrie PC-PSI-PT : Cours, méthodes et exercices corrigés, Dunod, , 5e éd. (lire en ligne), p. 125.
  3. En réalité, ce résultat n'est vrai que si , mais le cas d'une racine nulle se traite aisément par décalage d'indice.

Articles connexes[modifier | modifier le code]