relation de récurrence

En mathématiques et en informatique , une relation de récurrence est une équation selon laquelle le terme n-ième d'une suite de nombres est égal à une combinaison des termes précédents. Souvent, seuls les termes précédents de la suite apparaissent dans l'équation, pour un paramètre n indépendant de n ; ce nombre est appelé l' ordre de la relation. Si les valeurs des premiers nombres de la suite sont connues, le reste de la suite peut être calculé en appliquant l'équation de manière itérative.

Dans les récurrences linéaires , le terme $fonction linéaire des termes précédents. Un exemple célèbre est la récurrence des nombres de Fibonacci, où l'ordre est deux et la fonction linéaire se contente d'additionner les deux termes précédents. Cet exemple est une récurrence linéaire à coefficients constants, car les coefficients de la fonction linéaire (1 et 1) sont des constantes indépendantes de n. Pour ces récurrences, on peut exprimer le terme général de la suite sous forme analytique . De même, les récurrences linéaires à coefficients polynomiaux dépendant de n sont également importantes, car de nombreuses fonctions élémentaires et spéciales courantes possèdent un développement en série de Taylor dont les coefficients satisfont une telle relation de récurrence (voir fonction holonome).$

Résoudre une relation de récurrence signifie obtenir une solution sous forme fermée : une fonction non récursive de .

Le concept de relation de récurrence peut être étendu aux tableaux multidimensionnels , c'est-à-dire aux familles indexées par des tuples de nombres naturels .

suite en fonction des éléments précédents. Plus précisément, lorsque seul l'élément immédiatement précédent est concerné, une relation de récurrence a la forme suivante :

0,"

0, {vous}_{n} = φ (n, {vous}_{n - 1}) pour n > 0,

où

est une fonction, où

Il est facile de modifier la définition pour obtenir des séquences commençant par le terme d'indice 1 ou supérieur.

Ceci définit une relation de récurrence du premier ordre . Une relation de récurrence d' ordre

où est une fonction qui fait intervenir

0,"

0, n! = n \cdot (n - 1)! pour n > 0,

et l'état initial

Il s'agit d'un exemple de récurrence linéaire avec des coefficients polynomiaux d'ordre 1, avec le polynôme simple (en

comme son seul coefficient.

Carte logistique

Un exemple de relation de récurrence est l' application logistique définie par

Pour une constante donnée, le comportement de la séquence dépend fortement de cette constante , mais reste stable lorsque la condition initiale varie.

Les nombres de Fibonacci

La récurrence d'ordre deux satisfaite par les nombres de Fibonacci est l'exemple canonique d'une relation de récurrence linéaire homogène à coefficients constants (voir ci-dessous). La suite de Fibonacci est définie à l'aide de la récurrence

avec des conditions initiales

Plus précisément, la récurrence donne les équations

etc.

On obtient la suite des nombres de Fibonacci, qui commence

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

La récurrence peut être résolue par les méthodes décrites ci-dessous, ce qui donne la formule de Binet , qui fait intervenir les puissances des deux racines du polynôme caractéristique ; la fonction génératrice de la suite est la fonction rationnelle

Coefficients binomiaux

Un exemple simple de relation de récurrence multidimensionnelle est donné par les coefficients binomiaux , qui dénombrent les façons de sélectionner des éléments parmi un ensemble d' éléments. Ils peuvent être calculés par la relation de récurrence.

avec les cas de base . L'utilisation de cette formule pour calculer les valeurs de tous les coefficients binomiaux génère un tableau infini appelé triangle de Pascal . Ces mêmes valeurs peuvent également être calculées directement par une autre formule qui n'est pas une récurrence, mais qui utilise les factorielles , la multiplication et la division, et non seulement les additions :

Les coefficients binomiaux peuvent également être calculés à l'aide d'une récurrence unidimensionnelle :

avec la valeur initiale (la division n'est pas affichée sous forme de fraction pour souligner qu'elle doit être calculée après la multiplication, afin d'éviter l'introduction de nombres fractionnaires). Cette récurrence est largement utilisée en informatique car elle ne nécessite pas la construction d'un tableau, contrairement à la récurrence bidimensionnelle, et n'implique pas de très grands entiers, contrairement à la formule avec les factorielles (dans ce cas, tous les entiers impliqués sont inférieurs au résultat final).

Opérateur de différence et équations de différenceopérateurqui transformedes séquencesen séquences, et, plus généralement,des fonctionsen fonctions. Il est généralement notéet est défini, ennotation fonctionnelle, comme suit :

Résolution

Résolution de relations de récurrence linéaire à coefficients constants

Résolution des relations de récurrence linéaires homogènes générales

De nombreuses relations de récurrence linéaires homogènes peuvent être résolues au moyen des séries hypergéométriques généralisées . Des cas particuliers de ces séries conduisent à des relations de récurrence pour les polynômes orthogonaux et de nombreuses fonctions spéciales . Par exemple, la solution de

est donné par

la fonction de Bessel , tandis que

est résolu par

Les séries hypergéométriques confluentes . Les suites qui sont solutions d' équations aux différences linéaires à coefficients polynomiaux sont dites P-récursives . Pour ces équations de récurrence spécifiques, il existe des algorithmes permettant de trouver des solutions polynomiales , rationnelles ou hypergéométriques .

Résolution de relations de récurrence linéaires non homogènes générales à coefficients constants

De plus, pour la relation de récurrence linéaire non homogène générale à coefficients constants, on peut la résoudre en se basant sur la variation du paramètre.

Résolution d'équations aux différences rationnelles du premier ordre

Stabilité

Stabilité des récurrences linéaires d'ordre supérieur

La récurrence linéaire d'ordre ,

possède l' équation caractéristique

La récurrence est stable , ce qui signifie que les itérations convergent asymptotiquement vers une valeur fixe, si et seulement si les valeurs propres (c'est-à-dire les racines de l'équation caractéristique), qu'elles soient réelles ou complexes, sont toutes inférieures à l'unité en valeur absolue.

Stabilité des récurrences matricielles linéaires du premier ordre

Stabilité des récurrences non linéaires du premier ordre

Considérons la récurrence non linéaire du premier ordre

Cette récurrence est localement stable , ce qui signifie qu'elle converge vers un point fixe à partir de points suffisamment proches de , si la pente de dans le voisinage de est inférieure à l'unité en valeur absolue : c'est-à-dire,

Une récurrence non linéaire peut avoir plusieurs points fixes, auquel cas certains points fixes peuvent être localement stables et d'autres localement instables ; pour une fonction f continue, deux points fixes adjacents ne peuvent pas être tous deux localement stables.

Une relation de récurrence non linéaire peut également présenter un cycle de période pour . Un tel cycle est stable, c'est-à-dire qu'il attire un ensemble de conditions initiales de mesure positive, si la fonction composée $1 k > 1$

avec des temps d'apparition est localement stable selon le même critère :

Où se situe un point quelconque sur le cycle ?

Dans une relation de récurrence chaotique , la variable reste dans une région bornée mais ne converge jamais vers un point fixe ni vers un cycle attractif ; tout point fixe ou cycle de l’équation est instable. Voir aussi application logistique , transformation dyadique et application en tente .

Lien avec les équations différentielles

Lorsqu'on résout numériquement une équation différentielle ordinaire , on rencontre généralement une relation de récurrence. Par exemple, lors de la résolution du problème de Cauchy.

avec la méthode d'Euler et un pas de discrétisation , on calcule les valeurs

par la récurrence

Les systèmes d'équations différentielles linéaires du premier ordre peuvent être discrétisés de manière analytique exacte en utilisant les méthodes présentées dans l' article sur la discrétisation .

Applications

biologie mathématique

Certaines des équations aux différences finies les plus connues trouvent leur origine dans la tentative de modéliser la dynamique des populations . Par exemple, les nombres de Fibonacci ont autrefois servi de modèle pour la croissance d'une population de lapins.

La carte logistique est utilisée soit directement pour modéliser la croissance démographique, soit comme point de départ pour des modèles plus détaillés de dynamique des populations. Dans ce contexte, des équations aux différences couplées sont souvent utilisées pour modéliser l'interaction de deux populations ou plus . Par exemple, le modèle de Nicholson-Bailey pour une interaction hôte- parasite est donné par :

avec représentant les hôtes et les parasites, à l'époque .

Les équations intégro-différentielles constituent une forme de relation de récurrence importante en écologie spatiale . Ces équations, ainsi que d'autres équations aux différences finies, sont particulièrement adaptées à la modélisation des populations univoltines .

L'informatique

Les relations de récurrence sont également d'une importance fondamentale dans l'analyse des algorithmes . Si un algorithme est conçu de manière à ce qu'il divise un problème en sous-problèmes plus petits ( diviser pour régner ), son temps d'exécution est décrit par une relation de récurrence.

Un exemple simple est le temps nécessaire à un algorithme pour trouver un élément dans un vecteur ordonné contenant des éléments, dans le pire des cas.

Un algorithme naïf effectuera une recherche de gauche à droite, élément par élément. Le pire scénario possible est celui où l'élément recherché est le dernier, auquel cas le nombre de comparaisons est égal à .

Un meilleur algorithme est appelé recherche binaire . Cependant, il nécessite un vecteur trié. Il vérifie d'abord si l'élément se trouve au milieu du vecteur. Si ce n'est pas le cas, il vérifie si l'élément du milieu est supérieur ou inférieur à l'élément recherché. À ce stade, la moitié du vecteur peut être ignorée et l'algorithme peut être réexécuté sur l'autre moitié. Le nombre de comparaisons est donné par

dont la complexité temporelle sera de .

traitement numérique du signal

En traitement numérique du signal , les relations de récurrence permettent de modéliser la rétroaction dans un système, où les sorties à un instant donné deviennent des entrées pour des instants ultérieurs. Elles apparaissent ainsi dans les filtres numériques à réponse impulsionnelle infinie (RII) .

Par exemple, l'équation d'un filtre en peigne IIR à anticipation de retard est :

où représente l'entrée à l'instant , la sortie à l'instant , et contrôle la quantité du signal retardé réinjectée dans la sortie. On peut donc en déduire que

etc.

Économie

taux d'intérêt , PIB réel , etc.) en fonction des valeurs passées et actuelles des autres variables.

Plus d articles de Worldlex Wiki

Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index