Suite récurrente linéaire
En mathématiques, on nomme suite récurrente linéaire d'ordre p, toute suite à valeurs dans un corps K définie pour tout par la relation de récurrence suivante ...
Page(s) en rapport avec ce sujet :
- Chapitre 3 : Suites Récurrentes Linéaires. L'objectif est de déterminer l'ensemble des suites \left (u_{n}\right) _{n\in qui vérifient... (source : c.caignaert.free)
En mathématiques, on nomme suite récurrente linéaire d'ordre p, toute suite à valeurs dans un corps K (généralement ou
) définie pour tout
par la relation de récurrence suivante :
a0, a1, …ap − 1 étant p scalaires fixés de K (a0 non nul), pour tout , on a
Une telle suite est entièrement déterminée par la donnée des p premiers termes de la suite et par la relation de récurrence.
Les suites récurrentes linéaires d'ordre 1 se nomment plus simplement des suites géométriques de raison a0.
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 envisageable pour peu qu'on soit capable de factoriser un polynôme qui lui est associé, nommé 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. Surtout, dans le cas des suites d'ordre 2, le polynôme est de degré 2 et peut par conséquent être factorisé avec un calcul de discriminant. Ainsi, le terme général des suites récurrentes linéaires d'ordre 2, peut être exprimé en utilisant uniquement 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 très 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
- Voir article détaillé : Suite géométrique
Si la relation de récurrence est , le terme général est
Suite récurrente linéaire d'ordre 2
a et b étant deux scalaires fixés de K avec b non nul, la relation de récurrence est
- un + 2 = aun + 1 + bun (R)
On va prouver que le terme général d'une telle suite à valeurs dans K, est
si r1 et r2 sont deux racines différentes (dans K) du polynôme X2 − aX − b,
si r0 est racine double du polynôme X2 − aX − b,
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 r1, r2 du polynôme X2 − aX − b sont deux complexes conjugués ρeiθ et ρe − iθ, alors le terme général de la suite s'écrit aussi
avec A, 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 uniquement à partir de n0. En effet, si une suite (u) n'est définie qu'à partir de n0, elle induit la création d'une suite (v) définie sur
en posant
.
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 facilement que ce problème équivaut à résoudre l'équation du second degré
. Le polynôme
est alors nommé 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 différentes
Soient r1 et r2 les deux racines différentes. Les suites et
vérifient (R) mais aussi 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é l'ensemble des suites vérifiant (R) ? Une suite vérifiant (R) étant entièrement déterminée par la donnée de u0 et u1, il suffit de prouver qu'on peut toujours trouver λ et μ solutions du dispositif
Or ce dispositif a pour déterminant r2 − r1 non nul. Il est par conséquent toujours envisageable 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
Si le discriminant est nul, le problème est tout autre car on ne trouve qu'une seule valeur r0, par conséquent 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 se nomme la méthode de variation de la constante. On s'assure en premier lieu de l'existence de la suite
en vérifiant que r0 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 a2 + 4b = 0 et que , on obtient la relation caractéristique de toute suite arithmétique :
- λn + 2 − λn + 1 = λn + 1 − λn
La suite est par conséquent une suite arithmétique de terme général
- λn = λ + μn.
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 spécifique de deux racines différentes conjuguées
C'est le cas si le polynôme caractéristique est à cœfficients réels ainsi qu'à discriminant strictement négatif. L'équation du second degré possède alors dans deux racines conjuguées.
et
, différentes.
Le résultat du premier des deux cas ci-dessus s'applique : les suites complexes vérifiant (R) sont par conséquent 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 par conséquent les suites de terme général
avec A, 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, 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 u0 = A, u1 = Aρcosθ + Bρsinθ, et ρsinθ non nul (donc si u0, u1 sont réels alors A, B aussi).
Suite récurrente d'ordre p
Sous-espace vectoriel de dimension p
Si on nomme (Rp) la relation de récurrence :
- pour tout entier n,
et si on nomme , la totalité des suites à valeurs dans K et vérifiant (Rp) , on démontre que
est un sous-espace vectoriel de la totalité des suites à valeurs dans K. Cela tient à la linéarité de la relation de récurrence.
De plus, ce sous espace vectoriel est de dimension p. En effet, il existe un isomorphisme d'espace vectoriel entre et la totalité
: à chaque suite (u) de
, on associe le p_uplet
. Il suffit alors de connaître une famille libre de p suites vérifiant (Rp) , la totalité
est alors génèré par cette famille libre.
Terme général
La recherche du terme général et des suites spécifiques s'effectue en œuvrant sur Kp. À chaque suite on associe la suite
telle que
La relation de récurrence sur induit une relation de récurrence sur
- Un + 1 = AUn où
Le terme général de la suite U est alors déterminé par
- Un = AnU0 (A est la matrice compagnon du polynôme caractéristique de la suite).
Le problème semble alors terminé. Mais la réelle difficulté consiste alors à calculer An... On préfère plutôt déterminer une base de .
Recherche d'une base
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 Rp.
On note f la transformation linéaire qui, à une suite associe la suite
définie par vn = un + 1. La condition u vérifie Rp se traduit alors par P (f) (u) = 0. La totalité
est par conséquent le noyau de P (f). Si P est un polynôme scindé dans K (ce qui est toujours vrai si
), il existe k racines
et k exposants
tel que
. Le noyau de P (f) est alors la somme directe des noyaux des
. Il suffit par conséquent 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 à αi. Cette démonstration se fait par récurrence sur αi. Comme les suites
, pour j = 0 à αi − 1 forment une partie libre de αi éléments, la famille de l'ensemble des suites
, pour j = 0 à αi − 1 et pour i = 1 à k forme une famille libre de
éléments de
(de dimension p) par conséquent une base de
. Les éléments de
sont par conséquent des sommes de suites dont le terme général est
avec degré de Q strictement inférieur à αi.
Retour à la récurrence d'ordre 2
Si le polynôme caractéristique se scinde en (X − r1) (X − r2) 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 (X − r0) 2 alors les polynômes Q sont de degré 1 et les éléments de sont des suites dont le terme général est
.
Recherche sur Amazon (livres) : |
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.