Relation réccurente - Recurrence relation

En mathématiques , une relation de récurrence est une équation qui définit de manière récursive une séquence ou un tableau multidimensionnel de valeurs, une fois qu'un ou plusieurs termes initiaux de la même fonction sont donnés ; chaque autre terme de la séquence ou du tableau est défini en fonction des termes précédents de la même fonction.

Le terme équation de différence parfois (et pour les besoins de cet article) fait référence à un type spécifique de relation de récurrence. Cependant, « équation de différence » est fréquemment utilisée pour désigner toute relation de récurrence.

Définition

Une relation de récurrence est une équation qui exprime chaque élément d'une séquence en fonction des précédents. Plus précisément, dans le cas où seul l'élément immédiatement précédent est impliqué, une relation de récurrence a la forme

est une fonction, où X est un ensemble auquel doivent appartenir les éléments d'une séquence. Pour tout , cela définit une séquence unique avec comme premier élément, appelé la valeur initiale .

Il est facile de modifier la définition pour obtenir des séquences à partir du terme d'indice 1 ou supérieur.

Ceci définit la relation de récurrence du premier ordre . Une relation de récurrence d' ordre k a la forme

où est une fonction qui implique k éléments consécutifs de la séquence. Dans ce cas, k valeurs initiales sont nécessaires pour définir une séquence.

Exemples

Factorielle

La factorielle est définie par la relation de récurrence

et la condition initiale

Carte logistique

Un exemple de relation de récurrence est la carte logistique :

avec une constante r donnée ; étant donné le terme initial x 0, chaque terme suivant est déterminé par cette relation.

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

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 en utilisant la récurrence

avec conditions initiales

Explicitement, 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 donnant la formule de Binet , qui fait intervenir les puissances des deux racines du polynôme caractéristique t 2  =  t  + 1 ; la fonction génératrice de la suite est la fonction rationnelle

Coefficients binomiaux

Un exemple simple d'une relation de récurrence multidimensionnelle est donné par les coefficients binomiaux , qui comptent le nombre de façons de sélectionner k éléments parmi un ensemble de n é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 . Les mêmes valeurs peuvent également être calculées directement par une formule différente qui n'est pas une récurrence, mais qui nécessite une multiplication et pas seulement une addition pour calculer :

Relation aux équations aux différences étroitement définies

Étant donné une séquence ordonnée de nombres réels : la première différence est définie comme

La deuxième différence est définie comme

qui peut être simplifié en

Plus généralement : la k -ième différence de la suite a n écrite as est définie récursivement comme

(La séquence et ses différences sont liées par une transformation binomiale .) La définition la plus restrictive de l' équation aux différences est une équation composée d' un n et de ses k e différences. (Une définition plus large largement utilisée traite "l'équation de différence" comme synonyme de "relation de récurrence". Voir par exemple l'équation de différence rationnelle et l' équation de différence matricielle .)

En fait, on voit facilement que,

Ainsi, une équation aux différences peut être définie comme une équation qui implique un n , un n -1 , un n -2 etc. (ou de manière équivalente un n , un n +1 , un n +2 etc.)

Étant donné que les équations aux différences sont une forme très courante de récurrence, certains auteurs utilisent les deux termes de manière interchangeable. Par exemple, l'équation de différence

équivaut à la relation de récurrence

Ainsi, on peut résoudre de nombreuses relations de récurrence en les reformulant en équations aux différences, puis en résolvant l'équation aux différences, de manière analogue à la façon dont on résout les équations différentielles ordinaires . Cependant, les nombres d'Ackermann sont un exemple de relation de récurrence qui ne correspond pas à une équation aux différences, et encore moins à des points sur la solution d'une équation différentielle.

Voir le calcul de l'échelle de temps pour une unification de la théorie des équations aux différences avec celle des équations différentielles .

Les équations de sommation se rapportent aux équations aux différences comme les équations intégrales se rapportent aux équations différentielles.

Des séquences aux grilles

Les relations de récurrence à une variable ou à une dimension concernent des séquences (c'est-à-dire des fonctions définies sur des grilles à une dimension). Les relations de récurrence multivariables ou à n dimensions concernent des grilles à n dimensions. Les fonctions définies sur les n-grilles peuvent également être étudiées avec des équations aux différences partielles .

Résoudre

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

Racines du polynôme caractéristique

Une récurrence linéaire homogène d'ordre d à coefficients constants est une équation de la forme

où les d coefficients c i (pour tout i ) sont des constantes, et .

Une séquence constante-récursive est une séquence satisfaisant une récurrence de cette forme. Il existe d degrés de liberté pour les solutions à cette récurrence, c'est-à-dire que les valeurs initiales peuvent être considérées comme n'importe quelles valeurs, mais ensuite la récurrence détermine la séquence de manière unique.

Les mêmes coefficients donnent le polynôme caractéristique (également "polynôme auxiliaire" ou "polynôme compagnon")

dont les racines d jouent un rôle crucial dans la recherche et la compréhension des séquences satisfaisant la récurrence. Si les racines r 1 , r 2 , ... sont toutes distinctes, alors chaque solution de la récurrence prend la forme

où les coefficients k i sont déterminés pour s'adapter aux conditions initiales de la récurrence. Lorsque les mêmes racines apparaissent plusieurs fois, les termes de cette formule correspondant à la deuxième occurrence et aux occurrences ultérieures de la même racine sont multipliés par des puissances croissantes de n . Par exemple, si le polynôme caractéristique peut être factorisé comme ( xr ) 3 , avec la même racine r apparaissant trois fois, alors la solution prendrait la forme

Outre les nombres de Fibonacci , d'autres suites constantes-récursives comprennent les nombres de Lucas et les suites de Lucas , les nombres de Jacobsthal , les nombres de Pell et plus généralement les solutions de l'équation de Pell .

Pour l'ordre 1, la récurrence

a la solution a n  =  r n avec a 0  = 1 et la solution la plus générale est a n  =  kr n avec a 0  =  k . Le polynôme caractéristique égal à zéro (l' équation caractéristique ) est simplement t  −  r  = 0.

Des solutions à de telles relations de récurrence d'ordre supérieur sont trouvées par des moyens systématiques, en utilisant souvent le fait que a n  =  r n est une solution pour la récurrence exactement lorsque t  =  r est une racine du polynôme caractéristique. Cela peut être abordé directement ou à l'aide de fonctions génératrices ( séries entières formelles ) ou de matrices.

Considérons, par exemple, une relation de récurrence de la forme

Quand a-t-il une solution de la même forme générale que a n = r n ? En substituant cette supposition ( ansatz ) dans la relation de récurrence, nous trouvons que

doit être vrai pour tout  n  > 1.

En divisant par r n −2 , on obtient que toutes ces équations se réduisent à la même chose :

qui est l'équation caractéristique de la relation de récurrence. Résolvez pour r pour obtenir les deux racines λ 1 , λ 2 : ces racines sont appelées racines caractéristiques ou valeurs propres de l'équation caractéristique. Différentes solutions sont obtenues selon la nature des racines : Si ces racines sont distinctes, on a la solution générale

tandis que s'ils sont identiques (quand A 2 + 4 B = 0 ), on a

C'est la solution la plus générale ; les deux constantes C et D peuvent être choisies sur la base de deux conditions initiales données a 0 et a 1 pour produire une solution spécifique.

Dans le cas de valeurs propres complexes (ce qui donne également lieu à des valeurs complexes pour les paramètres de solution C et D ), l'utilisation de nombres complexes peut être supprimée en réécrivant la solution sous forme trigonométrique. Dans ce cas, nous pouvons écrire les valeurs propres sous la forme Alors on peut montrer que

peut être réécrit comme

Ici E et F (ou de manière équivalente, G et δ) sont des constantes réelles qui dépendent des conditions initiales. En utilisant

on peut simplifier la solution donnée ci-dessus comme

a 1 et a 2 sont les conditions initiales et

De cette façon, il n'est pas nécessaire de résoudre pour λ 1 et λ 2 .

Dans tous les cas—valeurs propres réelles distinctes, valeurs propres réelles dupliquées et valeurs propres conjuguées complexes—l'équation est stable (c'est-à-dire que la variable a converge vers une valeur fixe [en particulier, zéro]) si et seulement si les deux valeurs propres sont inférieures à un dans valeur absolue . Dans ce cas du second ordre, cette condition sur les valeurs propres peut être montrée équivalente à | A | < 1 −  B  < 2, ce qui équivaut à | B | < 1 et | A | < 1 −  B .

L'équation de l'exemple ci-dessus était homogène , en ce sens qu'il n'y avait pas de terme constant. Si l'on part de la récurrence non homogène

avec un terme constant K , cela peut être converti en forme homogène comme suit : L' état stationnaire est trouvé en fixant b nb n −1b n −2b * pour obtenir

Alors la récurrence non homogène peut être réécrite sous forme homogène comme

qui peut être résolu comme ci-dessus.

La condition de stabilité énoncée ci-dessus en termes de valeurs propres pour le cas du second ordre reste valable pour le cas général du n ième ordre : l'équation est stable si et seulement si toutes les valeurs propres de l'équation caractéristique sont inférieures à une en valeur absolue.

Étant donné une relation de récurrence linéaire homogène avec des coefficients constants d'ordre d , soit p ( t ) le polynôme caractéristique (également "polynôme auxiliaire")

de telle sorte que chaque c i correspond à chaque c i dans la relation de récurrence d' origine (voir la forme générale ci - dessus). Supposons que est une racine de p ( t ) ayant une multiplicité r . C'est-à-dire que ( t −λ) r divise p ( t ). Les deux propriétés suivantes sont valables :

  1. Chacune des r séquences satisfait la relation de récurrence.
  2. Toute séquence satisfaisant à la relation de récurrence peut être écrit de façon unique comme une combinaison linéaire des solutions construites dans la partie 1 que λ varie sur toutes les racines distinctes de  p ( t ).

En conséquence de ce théorème, une relation de récurrence linéaire homogène à coefficients constants peut être résolue de la manière suivante :

  1. Trouvez le polynôme caractéristique p ( t ).
  2. Trouvez les racines de la multiplicité de comptage p ( t ).
  3. Écrivez un n comme une combinaison linéaire de toutes les racines (en comptant la multiplicité comme indiqué dans le théorème ci-dessus) avec des coefficients inconnus b i .
    C'est la solution générale de la relation de récurrence d'origine. ( q est la multiplicité de λ * )
  4. Égalisez chacun de la partie 3 (en branchant n = 0, ..., d dans la solution générale de la relation de récurrence) avec les valeurs connues de la relation de récurrence d'origine. Cependant, les valeurs a n de la relation de récurrence d'origine utilisée ne doivent généralement pas être contiguës : à l'exception des cas exceptionnels, seuls d sont nécessaires (c'est-à-dire que pour une relation de récurrence linéaire homogène d'origine d'ordre 3, on pourrait utiliser les valeurs a 0 , un 1 , un 4 ). Ce processus produira un système linéaire de d équations avec d inconnues. Résoudre ces équations pour les coefficients inconnus de la solution générale et reconnecter ces valeurs à la solution générale produira la solution particulière de la relation de récurrence d'origine qui correspond aux conditions initiales de la relation de récurrence d'origine (ainsi que toutes les valeurs ultérieures de la relation de récurrence d'origine ).

La méthode de résolution des équations différentielles linéaires est similaire à la méthode ci-dessus - la "conjecture intelligente" ( ansatz ) pour les équations différentielles linéaires avec des coefficients constants est e λ x où λ est un nombre complexe qui est déterminé en substituant la conjecture dans l'équation différentielle .

Ce n'est pas une coïncidence. Considérant la série de Taylor de la solution d'une équation différentielle linéaire :

on voit que les coefficients de la série sont donnés par la dérivée n ème de f ( x ) évaluée au point a . L'équation différentielle fournit une équation de différence linéaire reliant ces coefficients.

Cette équivalence peut être utilisée pour résoudre rapidement la relation de récurrence pour les coefficients de la solution en série puissance d'une équation différentielle linéaire.

La règle empirique (pour les équations dans lesquelles le polynôme multipliant le premier terme est différent de zéro à zéro) est que :

et plus généralement

Exemple : La relation de récurrence pour les coefficients de la série de Taylor de l'équation :

est donné par

ou alors

Cet exemple montre comment les problèmes généralement résolus à l'aide de la méthode de résolution des séries entières enseignée dans les classes d'équations différentielles normales peuvent être résolus de manière beaucoup plus simple.

Exemple : L'équation différentielle

a une solution

La conversion de l'équation différentielle en une équation aux différences des coefficients de Taylor est

Il est facile de voir que la dérivée n de e ax évaluée à 0 est un n .

Résolution par algèbre linéaire

Une suite linéairement récursive y d'ordre n

est identique à

Développée avec n −1 identités de genre , cette équation d'ordre n est traduite en un système d' équations aux différences matricielles de n équations linéaires du premier ordre,

Observez que le vecteur peut être calculé par n applications de la matrice d'accompagnement , C , au vecteur d'état initial, . Ainsi, la n- ième entrée de la séquence recherchée y est la composante supérieure de .

La décomposition propre , en valeurs propres, , et vecteurs propres, , est utilisée pour calculer . Grâce au fait crucial que le système C décale dans le temps chaque vecteur propre, e , en mettant simplement ses composantes à l'échelle λ fois,

qui est la version décalée dans le temps de vecteur propre, e , a des composantes de les fois plus grand, les composantes de vecteurs propres sont des puissances de λ , et, par conséquent, la solution de l' équation linéaire homogène récurrente est une combinaison de fonctions exponentielles, . Les composants peuvent être déterminés à partir des conditions initiales :

Résolution des coefficients,

Cela fonctionne également avec des conditions aux limites arbitraires , pas nécessairement les conditions initiales,

Cette description n'est vraiment pas différente de la méthode générale ci-dessus, mais elle est plus succincte. Cela fonctionne également bien pour des situations comme

où il y a plusieurs récurrences liées.

Résoudre avec les transformations z

Certaines équations aux différences, en particulier les équations aux différences à coefficients constants linéaires , peuvent être résolues à l'aide des transformations z . Les transformations z sont une classe de transformations intégrales qui conduisent à des manipulations algébriques plus pratiques et à des solutions plus simples. Il existe des cas dans lesquels l'obtention d'une solution directe serait pratiquement impossible, mais la résolution du problème via une transformation intégrale judicieusement choisie est simple.

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

Si la récurrence n'est pas homogène, une solution particulière peut être trouvée par la méthode des coefficients indéterminés et la solution est la somme de la solution des solutions homogènes et particulières. Une autre méthode pour résoudre une récurrence non homogène est la méthode de différenciation symbolique . Par exemple, considérons la récurrence suivante :

Il s'agit d'une récidive non homogène. Si on substitue nn +1, on obtient la récurrence

Soustraire la récurrence d'origine de cette équation donne

ou équivalent

Il s'agit d'une récurrence homogène, qui peut être résolue par les méthodes expliquées ci-dessus. En général, si une récurrence linéaire a la forme

où sont des coefficients constants et p ( n ) est l'inhomogénéité, alors si p ( n ) est un polynôme de degré r , alors cette récurrence non homogène peut être réduite à une récurrence homogène en appliquant la méthode de différenciation symbolique r fois.

Si

est la fonction génératrice de l'inhomogénéité, la fonction génératrice

de la récidive non homogène

à coefficients constants c i est dérivé de

Si P ( x ) est une fonction génératrice rationnelle, A ( x ) en est aussi une. Le cas discuté ci-dessus, où p n = K est une constante, apparaît comme un exemple de cette formule, avec P ( x ) = K /(1− x ). Un autre exemple, la récurrence avec inhomogénéité linéaire, se pose dans la définition des nombres schizophrènes . La solution des récurrences homogènes est incorporée comme p = P = 0.

Résolution de relations de récurrence non homogènes du premier ordre à coefficients variables

De plus, pour la relation générale de récurrence linéaire non homogène du premier ordre à coefficients variables :

il y a aussi une bonne méthode pour le résoudre:

Laisser

Puis

Si nous appliquons la formule à et prenons la limite h→0, nous obtenons la formule pour les équations différentielles linéaires du premier ordre à coefficients variables ; la somme devient une intégrale et le produit devient la fonction exponentielle d'une intégrale.

Résolution des relations de récurrence linéaire homogène générale

De nombreuses relations de récurrence linéaire homogènes peuvent être résolues au moyen de la série hypergéométrique généralisée . Des cas particuliers de ceux-ci 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

la série hypergéométrique confluente . Les suites qui sont les solutions d' équations aux différences linéaires à coefficients polynomiaux sont appelées P-récursives . Pour ces équations de récurrence spécifiques, on connaît des algorithmes qui trouvent des solutions polynomiales , rationnelles ou hypergéométriques .

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

Une équation aux différences rationnelles du premier ordre a la forme . Une telle équation peut être résolue en écrivant comme une transformation non linéaire d'une autre variable qui elle-même évolue linéairement. Ensuite, des méthodes standard peuvent être utilisées pour résoudre l'équation de différence linéaire dans .

Stabilité

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

La récurrence linéaire d'ordre d ,

a l' équation caractéristique

La récurrence est stable , c'est-à-dire 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

Dans l'équation de différence matricielle du premier ordre

avec le vecteur d'état x et la matrice de transition A , x converge asymptotiquement vers le vecteur stationnaire x * si et seulement si toutes les valeurs propres de la matrice de transition A (qu'elle soit réelle ou complexe) ont une valeur absolue inférieure à 1.

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 , c'est-à-dire qu'elle converge vers un point fixe x * à partir de points suffisamment proches de x *, si la pente de f au voisinage de x * 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 f continue deux points fixes adjacents ne peuvent pas être tous les deux localement stables.

Une relation de récurrence non linéaire pourrait également avoir un cycle de période k pour k > 1. Un tel cycle est stable, ce qui signifie qu'il attire un ensemble de conditions initiales de mesure positive, si la fonction composite

avec f apparaissant k fois est localement stable selon le même critère :

x * est un point quelconque du cycle.

Dans une relation de récurrence chaotique , la variable x reste dans une région bornée mais ne converge jamais vers un point fixe ou un cycle attractif ; tous les points fixes ou cycles de l'équation sont instables. Voir aussi la carte logistique , la transformation dyadique et la carte des tentes .

Relation avec les équations différentielles

Lors de la résolution numérique d' 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 la valeur initiale

avec la méthode d' Euler et un pas h , 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 exactement analytiquement en utilisant les méthodes présentées dans l' article sur la discrétisation .

Applications

La biologie

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

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

avec N t représentant les hôtes, et P t les parasites, au temps  t .

Les équations d'intégrodifférence sont une forme de relation de récurrence importante pour l' écologie spatiale . Ces équations aux différences et d'autres 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 à diviser 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 qu'un algorithme prend pour trouver un élément dans un vecteur ordonné avec des éléments, dans le pire des cas.

Un algorithme naïf recherchera de gauche à droite, un élément à la fois. Le pire scénario possible est lorsque l'élément requis est le dernier, donc le nombre de comparaisons est .

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

dont la complexité temporelle sera .

Traitement des signaux numériques

Dans le traitement du signal numérique , les relations de récurrence peuvent modéliser la rétroaction dans un système, où les sorties à un moment donné deviennent des entrées pour le temps futur. Ils se présentent ainsi dans les filtres numériques à réponse impulsionnelle infinie (IIR) .

Par exemple, l'équation d'un filtre en peigne IIR « feedforward » de retard T est :

où est l'entrée à l'instant t , est la sortie à l'instant t , et contrôle la quantité de signal retardé réinjectée dans la sortie. De là, nous pouvons voir que

etc.

Économie

Les relations de récurrence, en particulier les relations de récurrence linéaire, sont largement utilisées en économie théorique et empirique. En particulier, en macroéconomie, on pourrait développer un modèle de divers grands secteurs de l'économie (le secteur financier, le secteur des biens, le marché du travail, etc.) dans lequel les actions de certains agents dépendent de variables retardées. Le modèle serait ensuite résolu pour les valeurs actuelles des variables clés ( taux d'intérêt , PIB réel , etc.) en termes de valeurs passées et actuelles d'autres variables.

Voir également

Les références

Notes de bas de page

Bibliographie

Liens externes