Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
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 \mathbb C ou \R) définie pour tout n \geq n_0 par la relation de récurrence suivante :

a0, a1, …ap − 1 étant p scalaires fixés de K (a0 non nul), pour tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) 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 a0. Les suites récurrentes linéaires d’ordre 2 sont entièrement connues et leur terme général est déterminé en fonction des coefficients a0 et a1. Une des suites de ce type est la très célèbre suite de Fibonacci (Leonardo Fibonacci (Pise, v. 1170 - v. 1250) est un mathématicien italien. Fibonacci (de son nom moderne), connu à l'époque sous le nom de Leonardo Pisano...). L’étude des suites récurrentes linéaires d’ordre p fait appel à la notion d’espace vectoriel (En algèbre linéaire, un espace vectoriel est une structure algébrique permettant en pratique d'effectuer des combinaisons linéaires. Pour une introduction au concept de vecteur, voir l'article Vecteur.) et au calcul matriciel.

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...) d’ordre 1

  • Voir article détaillé : Suite géométrique

Si la relation de récurrence est un + 1 = qun, 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

un + 2 = aun + 1 + bun (R)

On va prouver que le terme général d'une telle suite est

  • \lambda r_1^n+ \mu r_2^n si r1 et r2 sont deux racines distinctes du polynôme (En mathématiques, un polynôme est la combinaison linéaire des puissances d'une variable, habituellement notée X. Ces objets sont largement utilisés en pratique,...) X2aXb
  • (\lambda + \mu n) r_0^n si r0 est racine double du polynôme X2aXb
  • (\lambda\cos(n\theta) + \mu\sin(n\theta))\rho^n\, pour une suite réelle quand ρeiθ et ρe iθ sont les deux racines complexes du polynôme X2aXb

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 n0. En effet, si une suite (u) n’est définie qu’à partir de n0, elle induit (L'induit est un organe généralement électromagnétique utilisé en électrotechnique chargé de recevoir l'induction de l'inducteur et de la transformer en électricité (générateur) ou en force (moteur).) 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 (En mathématiques, une équation est une égalité qui lie différentes quantités, généralement pour poser le problème de leur identité. Résoudre l'équation consiste...) du second degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) r^2- ar - b = 0\,. Le polynôme r^2- ar - b \, est alors appelé le polynôme caractéristique (En algèbre linéaire, à toute matrice carrée ou à tout endomorphisme d'un espace vectoriel de dimension finie est associé un polynôme appelé polynôme caractéristique. Il renferme d'importantes informations sur la matrice ou sur...) de la suite. Son discriminant est \Delta = a^2 + 4b\,. Il faudra alors distinguer plusieurs cas, selon que le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de racine du polynôme caractéristique.

Si le polynôme possède deux racines distinctes

Soient r1 et r2 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 u0 et u1, 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 r2r1 non nul. Il est donc toujours possible d’exprimer une suite vérifiant (R) comme combinaison (Une combinaison peut être :) linéaire des suites (r_1^n)_{n \in \mathbb N} et (r_2^n)_{n \in \mathbb N}

Cette situation (En géographie, la situation est un concept spatial permettant la localisation relative d'un espace par rapport à son environnement proche ou non. Il inscrit un lieu dans un cadre plus général...) 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 r0, 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 r0 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 a2 + 4b = 0 et que r_0 = \frac{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 (En mathématique, une suite arithmétique est une suite définie sur à valeurs dans un groupe additif E telle qu'il existe un élément de appelé raison pour lequel :) 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 discrimant du polynôme caractéristique est nul.

Si le polynôme ne possède pas de racine

C'est le cas pour les suites à valeurs réelles pour lesquelles le discriminant du polynôme caractéristique est 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}\,.

Les suites de terme général A\rho^n e^{in\theta} + B\rho^n e^{-in\theta}\, sont des suites complexes vérifiant (R). Parmi celles-ci, celles pour lesquelles A et B sont conjugués, sont des suites réelles . Donc les suites de terme général

u_n = (\lambda \cos(n\theta) + \mu \sin(n\theta))\rho^n \,

sont des suites réelles vérifiant (R) (on a pris A = λ / 2 − iμ / 2). 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 u0 et u1, il suffit de prouver que l’on peut toujours trouver λ et μ solutions du système

\begin{cases} \lambda  = u_0 \\ \lambda \rho \cos(\theta)+ \mu \rho \sin(\theta) = u_1 \end{cases}

Or ce système a pour déterminant ρsin(θ) non nul. Il est donc toujours possible d’exprimer une suite vérifiant (R) comme combinaison linéaire des suites (\rho^n\cos(n\theta))_{n \in \mathbb N} et (\rho^n\sin(n\theta))_{n \in \mathbb N}.

Suite récurrente d’ordre p

Sous-espace vectoriel de dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur,...) p

Si on appelle (Rp) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut...) des suites à valeurs dans K et vérifiant (Rp), 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 (Rp) , l’ensemble E_{R_p} est alors engendré par cette famille libre.

Terme général

La recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances...) du terme général et des suites particulières s’effectue en travaillant sur Kp . À 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}

Un + 1 = AUn
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

Un = AnU0

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 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 (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.) si on le retrouve pour caractériser les suites u = (u_n)_{n \in \mathbb N} vérifiant Rp.

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 vn = un + 1. La condition u vérifie Rp 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 (En mathématiques, une démonstration permet d'établir une proposition à partir de propositions initiales, ou précédemment démontrées à partir de...) 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 (Xr1)(Xr2) 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 (Xr0)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.

Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.