Suite récurrente linéaire

En mathématiques, on appelle suite récurrente linéaire d’ordre p, toute suite à valeurs dans un corps commutatif K (généralement $\mathbb C$ ou $\R$ ) définie pour tout $n \geq n_0$ par la relation de récurrence suivante :

$a 0$ , $a 1$ , … $a p - 1$ étant p scalaires fixés de K ( $a 0$ non nul), pour tout $n \geq n_0$ , on a

$u_{n+p} = a_0u_n + a_1u_{n+1} + \cdots + a_{p-1}u_{n+p-1}$

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 s’appellent plus simplement des suites géométriques de raison $a 0$ .

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 :

$P(X) = X^p - \sum_{i = 0}^{p-1}a_iX^i=X^p-a_{p-1}X^{p-1}-a_{p-2} X^{p-2}-\dots-a_1 X-a_0.$

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 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 $u_{n+1}=q\,u_{n}$ , le terme général est $u_n = u_{n_{0}}q^{n-n_{0}}$

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

u n + 2 = a u n + 1 + b u n

(R)

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

$\lambda r_1^n+ \mu r_2^n$ si $r 1$ et $r 2$ sont deux racines distinctes (dans K) du polynôme $X 2 - a X - b$ ,
$(\lambda + \mu n) r_0^n$ si $r 0$ est racine double du polynôme $X 2 - a X - 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 $r 1, r 2$ du polynôme $X 2 - a X - b$ sont deux complexes conjugués $ρ e i θ$ et $ρ e - i θ$ , alors le terme général de la suite s'écrit également

$\rho^n(A\cos(n\theta) + B\sin(n\theta))\,$ 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 $\mathbb N$ et pas seulement à partir de $n 0$ . En effet, si une suite (u) n’est définie qu’à partir de $n 0$ , elle induit la création d’une suite (v) définie sur $\mathbb N$ en posant $v_n = u_{n + n_0}$ .

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 $(r^n)_{n \in \mathbb N}$ vérifie (R). On démontre aisément que ce problème équivaut à résoudre l’équation du second degré $r^2- ar - b = 0\,$ . Le polynôme $r^2- ar - b \,$ est alors appelé le polynôme caractéristique de la suite. Son discriminant est $\Delta = a^2 + 4b\,$ . 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

Soient $r 1$ et $r 2$ les deux racines distinctes. Les suites $(r_1^n)_{n \in \mathbb N}$ et $(r_2^n)_{n \in \mathbb N}$ vérifient (R) ainsi que toute suite dont le terme général serait $\lambda r_1^n + \mu r_2^n$ (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 $u 0$ et $u 1$ , il suffit de prouver que l’on peut toujours trouver $λ$ et $μ$ solutions du système

$\begin{cases} \lambda + \mu = u_0 \\ \lambda r_1 + \mu r_2 = u_1 \end{cases}$

Or ce système a pour déterminant $r 2 - r 1$ non nul. Il est donc toujours possible d’exprimer une suite vérifiant (R) comme combinaison linéaire des suites $(r_1^n)_{n \in \mathbb N}$ et $(r_2^n)_{n \in \mathbb N}$

Cette situation se produit pour toute suite à valeurs réelles pour laquelle le discriminant $\Delta = a^2 + 4b\,$ 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 $r 0$ , donc une seule famille de suites géométriques $(\lambda r_0^n)_{n \in \mathbb N}$ vérifiant (R) . L’idée consiste alors à rechercher les suites $(\lambda_n)_{n \in \mathbb N}$ telles que, pour tout entier n, $u_n = \lambda_n r_0^n$ avec $(u_n)_{n \in \mathbb N}$ 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 $(\lambda_n)_{n \in \mathbb N}$ en vérifiant que $r 0$ n’est jamais nul . La relation de récurrence sur $(u_n)_{n \in \mathbb N}$ se traduit par une relation de récurrence sur $(\lambda_n)_{n \in \mathbb N}$ :

$r_0^2\lambda_{n+2} =ar_0\lambda_{n+1} + b\lambda_n$

En utilisant ensuite le fait que $a 2 + 4 b = 0$ et que $r_0 = \dfrac{a}{2}$ , on obtient la relation caractéristique de toute suite arithmétique :

λ n + 2 - λ n + 1 = λ n + 1 - λ n

La suite $(\lambda_n)_{n \in \mathbb N}$ est donc une suite arithmétique de terme général

λ n = λ + μ n

Les suites $(u_n)_{n \in \mathbb N}$ vérifiant (R) ont alors pour terme général :

$u_n =(\lambda + \mu n)r_0^n$ .

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

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 $\mathbb C$ deux racines conjuguées.

$r_1= \rho e^{i\theta}\,$ et $r_2= \rho e^{-i\theta}\,$ , 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 $\lambda\rho^n e^{in\theta} + \mu\rho^n e^{-in\theta}\,$ , avec $λ,μ$ paramètres complexes. Par le changement de paramètres $A=\lambda+\mu,\; B=i(\lambda-\mu)~$ , ce sont aussi les suites de termes général $u_n = \rho^n (A\cos(n\theta) + B\sin(n\theta))\,$ avec A, B paramètres complexes.

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

$u_n = \rho^n (A\cos(n\theta) + B\sin(n\theta))\,$

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 $u 0 = A$ , $u 1 = A ρcos θ + B ρsin θ$ , et $ρsin θ$ non nul (donc si $u 0, u 1$ sont réels alors A, B aussi).

Suite récurrente d’ordre p

Sous-espace vectoriel de dimension p

Si on appelle $(R p)$ la relation de récurrence :

pour tout entier n, $u_{n+p} = a_0u_n + a_1u_{n+1} + \cdots + a_{p-1}u_{n+p-1}$

et si on appelle $E_{R_p}$ , l’ensemble des suites à valeurs dans K et vérifiant $(R p)$ , on démontre que $E_{R_p}$ est un sous-espace vectoriel de l’ensemble 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 $E_{R_p}$ et l’ensemble $K^p\,$ : à chaque suite (u) de $E_{R_p}$ , on associe le p_uplet $(u_0, u_1, \cdots,u_{p-1})$ . Il suffit alors de connaître une famille libre de p suites vérifiant $(R p)$ , l’ensemble $E_{R_p}$ est alors engendré par cette famille libre.

Terme général

La recherche du terme général et des suites particulières s’effectue en travaillant sur $K p$ . À chaque suite $(u_n)_{n \in \mathbb N}$ on associe la suite $(U_n)_{n \in \mathbb N}$ telle que

$U_n = (u_n, u_{n + 1},\cdots, u_{n+p-1})$

La relation de récurrence sur $(u_n)_{n \in \mathbb N}$ induit une relation de récurrence sur $(U_n)_{n \in \mathbb N}$

U n + 1 = A U n

où

$A = \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \ddots & \ddots & \cdots & \vdots \\ 0 & \cdots & \cdots & 0 & 1 \\ a_0 & a_1 & \cdots & \cdots & a_{p-1} \end{pmatrix}$

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

U n = A n U 0

(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 $A n$ ... On préfère plutôt déterminer une base de $E_{R_p}$ .

Recherche d'une base

Le polynôme caractéristique de la matrice A est $P(X) = X^p - \sum_{i = 0}^{p-1}a_iX^i$ . Ce n'est pas un hasard si on le retrouve pour caractériser les suites $u = (u_n)_{n \in \mathbb N}$ vérifiant $R p$ .

On note f la transformation linéaire qui, à une suite $u = (u_n)_{n \in \mathbb N}$ associe la suite $v = (v_n)_{n \in \mathbb N}$ définie par $v n = u n + 1$ . La condition u vérifie $R p$ se traduit alors par P(f)(u) = 0. L'ensemble $E_{R_p}$ est donc le noyau de P(f). Si P est un polynôme scindé dans K (ce qui est toujours vrai si $K = \mathbb C$ ), il existe k racines $r_1, r_2, \cdots, r_k$ et k exposants $\alpha_1, \alpha_2, \cdots, \alpha_k$ tel que $P = \prod_{i=1}^k(X - r_i)^{\alpha_i}$ . Le noyau de P(f) est alors la somme directe des noyaux des $(f - r_iId)^{\alpha_i}$ . Il suffit donc de trouver une base de chacun de ces noyaux pour déterminer une base de $E_{R_p}$ .

On peut montrer que toute suite de terme général $Q(n)r_i^n$ est élément du noyau de $(f - r_iId)^{\alpha_i}$ 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 $(n^jr_i^n)_{n \in \mathbb N}$ , pour j = 0 à $α i - 1$ forment une partie libre de $α i$ éléments, la famille de toutes les suites $(n^jr_i^n)_{n \in \mathbb N}$ , pour j = 0 à $α i - 1$ et pour i = 1 à k forme une famille libre de $\alpha_1 + \alpha_2 + \cdots + \alpha_k = p$ éléments de $E_{R_p}$ (de dimension p) donc une base de $E_{R_p}$ . Les éléments de $E_{R_p}$ sont donc des sommes de suites dont le terme général est $Q(n)r_i^n$ 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 - r 1)(X - r 2)$ alors les polynômes Q sont de degré 0 et les éléments de $E_{R_2}$ sont des suites dont le terme général est $\lambda_1r_1^n + \lambda_2r_2^n$ .

Si le polynôme caractéristique se scinde en $(X - r 0) 2$ alors les polynômes Q sont de degré 1 et les éléments de $E_{R_2}$ sont des suites dont le terme général est $(\lambda_1n +\lambda_2)r_0^n$ .

Portail de l'analyse

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Suite récurrente linéaire de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

Suite recurrente lineaire — Suite récurrente linéaire En mathématiques, on appelle 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 … Wikipédia en Français
Suite récurrente linéaire d'ordre 1 — Suite récurrente linéaire En mathématiques, on appelle 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 … Wikipédia en Français
Suite de padovan — Construction d une suite de Padovan à l aide de triangles équilatéraux La suite de Padovan est une suite d entiers définie par récurrence par , pour tout entier n C est une … Wikipédia en Français
Suite (mathématiques) — Pour les articles homonymes, voir Suite. En mathématiques, une suite[1] est une famille d éléments indexée par les entiers naturels. Une suite finie est une famille indexée par les entiers strictement positifs inférieurs ou égaux à un certain… … Wikipédia en Français
Suite définie par récurrence — En mathématiques, une suite définie par récurrence est une suite définie par son premier terme et par une relation de récurrence, qui définit chaque terme à partir du précédent ou des précédents lorsqu ils existent. Une relation de récurrence est … Wikipédia en Français
Suite de Padovan — Construction d une suite de Padovan à l aide de triangles équilatéraux La suite de Padovan est une suite d entiers définie par récurrence par , pour tout entier n C est une suite récurrente linéaire qui ressemble dans sa forme à l … Wikipédia en Français
Suite de Fibonacci — La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à Leonardo Fibonacci, dit Leonardo Pisano, un mathématicien italien du XIIIe siècle qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci,… … Wikipédia en Français
Registre à décalage à rétroaction linéaire — Un registre à décalage à rétroaction linéaire, ou LFSR (acronyme de l anglais linear feedback shift register), est un dispositif électronique ou logiciel qui produit une suite récurrente linéaire, initialement sur le corps fini à 2 élements (0 et … Wikipédia en Français
Suite de fibonacci — La suite de Fibonacci est une suite d entiers très connue. Elle doit son nom à un mathématicien italien connu sous le nom de Leonardo Fibonacci qui, dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, décrit la croissance d… … Wikipédia en Français
Equation lineaire — Équation linéaire Une équation à coefficients réels ou complexes est dite linéaire quand elle peut être présentée sous la forme a.x=b, où x est l inconnue, a et b sont deux nombres donnés. Si a est différent de zéro, la seule solution est le… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Suite récurrente linéaire

Sommaire

Suite récurrente linéaire d’ordre 1

Suite récurrente linéaire d’ordre 2