Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated

Résumé : Parmi les suites qui vérifient une récurrence de type diviser pour régner, les suites qui sont rationnelles dans une base de numération sont les plus simples et les plus fondamentales. Cependant, jusqu'à récemment, cette classe particulière de suites n'a pas fait l'objet d'une étude systématique du point de l'analyse asymptotique. Nous rappelons comment un procédé régulier, mis au point par l'auteur, permet de calculer le développement asymptotique d'une telle suite. Le procédé est basé sur l'algèbre linéaire et utilise le calcul d'une forme de Jordan et d'un rayon spectral ainsi que la résolution d'équations de dilatation. La contribution principale du présent article est la comparaison entre notre méthode algébrique et l'approche classique issue de la théorie analytique des nombres. De plus nous mettons au point de nouvelles manières de calculer les séries de Fourier des fonctions périodiques qui apparaissent dans les développements. L'article est assorti d'une importante bibliographie.
Liste complète des métadonnées

https://hal.inria.fr/hal-01065761
Contributeur : Philippe Dumas <>
Soumis le : jeudi 18 septembre 2014 - 15:30:10
Dernière modification le : jeudi 17 mai 2018 - 12:52:03
Document(s) archivé(s) le : vendredi 19 décembre 2014 - 13:45:52

Fichiers

Identifiants

Collections

Citation

Philippe Dumas. Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated. Theoretical Computer Science, Elsevier, 2014, 548, pp.25-53. 〈http://ac.els-cdn.com/S0304397514004964/1-s2.0-S0304397514004964-main.pdf?_tid=c5ec30fc-3f32-11e4-bbf3-00000aab0f27&acdnat=1411044983_8c7f04781e9d4b97d4f694639f19ebac〉. 〈10.1016/j.tcs.2014.06.036〉. 〈hal-01065761〉

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

241