Mathématiques discrètes : Suites récurrentes
9
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
9
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Math´ematiques
discr`etes :
Suites r´ecurrentes
D´efinitions
R´ecurrence
lin´eaire
Math´ematiques discr`etes :´Equation de
partition
Suites r´ecurrentes
Remarques
Licence — Universit´e Lille 1
Pour toutes remarques : Alexandre.Sedoglavic@univ-lille1.fr
Semestre 3 — 2010-2011
V0 (09-01-2009) Math´ematiques Relations et suites r´ecurrentesdiscr`etes :
Suites r´ecurrentes
D´efinitions Une suite est un ensemble E d’´el´ements index´es par les
R´ecurrence entiers naturels. Elle peut ˆetre assimil´ee `a une application
lin´eaire
deN dans E.
´Equation de
partition
Les relations de r´ecurrence sont des r`egles de d´efinition de
Remarques
suites d’´el´ements : chaque ´el´ement ´etant d´efini en fonction
des pr´ec´edents.
Ces relations interviennent souvent dans l’estimation de la
complexit´e de r´esolution de probl`emes se ramenant `a celle de
cas de taille plus petite — du type diviser pour r´egner
comme les strat´egies `a base de dichotomie.
Ce cours traitera principalement des relations de r´ecurrence
lin´eaires.
V19 (09-01-2009) Math´ematiques Classification des relations de r´ecurrencediscr`etes :
Suites r´ecurrentes
D´efinitions
NotationR´ecurrence
lin´eaire Classiquement, on note une suite (u ) . Ainsi, unen n∈N
´Equation de
relation f de r´ecurrence se pr´esente sous la forme :partition
Remarques
u = f(u , . . . ,u ).n n−1 n−k
Les relations de r´ecurrence peuvent se classer suivant 3
crit`eres :
I les propri´et´es de la fonction f (lin´earit´e, etc).
I l’ordre k de la ...
Voir
discr`etes :
Suites r´ecurrentes
D´efinitions
R´ecurrence
lin´eaire
Math´ematiques discr`etes :´Equation de
partition
Suites r´ecurrentes
Remarques
Licence — Universit´e Lille 1
Pour toutes remarques : Alexandre.Sedoglavic@univ-lille1.fr
Semestre 3 — 2010-2011
V0 (09-01-2009) Math´ematiques Relations et suites r´ecurrentesdiscr`etes :
Suites r´ecurrentes
D´efinitions Une suite est un ensemble E d’´el´ements index´es par les
R´ecurrence entiers naturels. Elle peut ˆetre assimil´ee `a une application
lin´eaire
deN dans E.
´Equation de
partition
Les relations de r´ecurrence sont des r`egles de d´efinition de
Remarques
suites d’´el´ements : chaque ´el´ement ´etant d´efini en fonction
des pr´ec´edents.
Ces relations interviennent souvent dans l’estimation de la
complexit´e de r´esolution de probl`emes se ramenant `a celle de
cas de taille plus petite — du type diviser pour r´egner
comme les strat´egies `a base de dichotomie.
Ce cours traitera principalement des relations de r´ecurrence
lin´eaires.
V19 (09-01-2009) Math´ematiques Classification des relations de r´ecurrencediscr`etes :
Suites r´ecurrentes
D´efinitions
NotationR´ecurrence
lin´eaire Classiquement, on note une suite (u ) . Ainsi, unen n∈N
´Equation de
relation f de r´ecurrence se pr´esente sous la forme :partition
Remarques
u = f(u , . . . ,u ).n n−1 n−k
Les relations de r´ecurrence peuvent se classer suivant 3
crit`eres :
I les propri´et´es de la fonction f (lin´earit´e, etc).
I l’ordre k de la ...
Math´ematiques discre`tes: Suitesre´currentes
De´finitions Re´currence lin´eaire ´ Equation de partition Remarques
V0 (09-01-2009)
Math´ematiquesdiscre`tes: Suitesre´currentes
Licence—Universite´Lille1 Pour toutes remarques : Alexandre.Sedoglavic@univ-lille1.fr
Semestre 3 — 2010-2011
Math´ematiques discr`etes: Suitesre´currentes
D´efinitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Relationsetsuitesre´currentes
Unesuiteest un ensembleEemde’n´el´dex´tsinlrseseap entiersnaturels.Ellepeuteˆtreassimile´e`auneapplication deNdansE.
Lesnsior´deurecncreerleta suitesd’´el´ements:chaque despre´c´edents.
sontdesre`glesdede´finitionde e´le´ment´etantd´efinienfonction
Ces relations interviennent souvent dans l’estimation de la complexite´der´esolutiondeprobl`emesseramenant`acellede cas de taille plus petite — du typeividserpourr´egner commelesstrat´egiesa`basededichotomie.
Cecourstraiteraprincipalementdesrelationsdere´currence line´aires.
Math´ematiques discr`etes: Suitesre´currentes
De´finitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Classificationdesrelationsder´ecurrence
Notation Classiquement, on note une suite(un)n∈N. Ainsi, une relationfder´ecurrencesepre´sentesouslaforme:
un=f(un−1, . . . ,un−k).
Lesrelationsder´ecurrencepeuventseclassersuivant3 crit`eres: lespropri´ete´sdelafonctionftc).i´ne,´eear(ilt I l’ordrek.ceenucrrrae´dle I abscenceounondeparame`tredanslafonctionf I (relationhomoge`neounon).
Mathe´matiques discre`tes: Suitesre´currentes
De´finitions Re´currence lin´eaire ´ Equation de partition Remarques
V19 (09-01-2009)
Exemples
La suite (un)n∈Ndes puissances deu0efid´epnilaarets relationder´ecurrencelin´eaire,homoge`ne d’ordre 1 :un=u0un−1. La suite (un)n∈Nnieparlaests´dfiecaotirlesedfserbmon relationder´ecurrencenonlin´eaire,nonhomoge`ne d’ordre 1 :un=nun−1. m s (C’ordrem Les suiten)n∈Ndes coefficients binomiaux d sontd´efiniesparlesrelationsder´ecurrenceline´aires m m m−1 homoge`nesC=C+C. n n−1n−1
L’alge`brelin´eairenouspermetder´esoudretoutesles re´currencesline´aires.Nousneconsid´eronsdanslasuiteque descasparticuliersdelathe´orieg´en´erale.
Mathe´matiques discre`tes: Suitesre´currentes
D´efinitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Casline´aired’ordre1 constants
`acoefficients
Lecashomog`eneestleplussimple:
un=cun−1
n On obtient une forme closeun=c u0. Lecasinhomoge`necorrespond`alarelation:
un=cun−1+r(n)
On obtient une forme close : n X n n−i un=c u0+r(n)c, i=0
(si le second membrer(n) se simplifie).
Mathe´matiques discr`etes: Suitesre´currentes
De´finitions R´ecurrence lin´eaire ´ Equation de partition Remarques
V19 (09-01-2009)
Casline´airehomog`enea`coefficients constants ´ Etantdonne´eunerelationlin´eairehomoge`ned’ordrek:
un=c1un−1+∙ ∙ ∙+ckun−k.
et sonnˆomecaract´erisuqiteopyl P k k k−i associ´ep(x) =x−cix. i=1 Proposition L’ensemble des suites solutions de (1) forment un espace vectoriel V de dimension k. Si p(x)a k racines distinctes{r1, . . . ,rk}, alors les k n suites(r)n∈Npour i= 1. . .k forment une base de V . i Si p(x)a p racines distinctes{r1, . . . ,rp}de j n multiplicite´{m1, . . . ,mp}, alors les k suites(n r)n∈N i pour i= 1. . .p et j= 1. . .mi.forment une base de V
(1)
Mathe´matiques discre`tes: Suitesre´currentes
D´efinitions Re´currence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Casline´airenonhomoge`nea`coefficients constants
´ Etantdonn´eeunerelationlin´eairehomog`ened’ordrek:
un=c1un−1+∙ ∙ ∙+ckun−k+r(n).
Proposition L’ensemble des solutions de (2) est un espace affine de dimensionkdontl’espacevectorielassocie´estl’ensemble dessolutionsdel’e´quationhomoge`necorrespondante.
(2)
Enconse´quence,ilfautd´ej`ar´esoudrel’e´quationhomoge`ne ettrouverunesolutionparticuli`erede(2).
Mathe´matiques discr`etes: Suitesr´ecurrentes
D´efinitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
D´efinition Unerelationder´ecurrencedelaformeun=f(un/a)avec a constantestunee´quationdepartition.Elled´efinieunesuite re´currente(u)idme.reeueinanu`qi n n∈{a|i∈N}
L’e´tudedel’´equationdepartitionun=cun/a+d(n) se k+1 ram`ene`acelledelare´currencevk+1=cvk+d(a) par le changement de variablevn=u. k a
Mathe´matiques discre`tes: Suitesr´ecurrentes
De´finitions R´ecurrence line´aire ´ Equation de partition Remarques
V19 (09-01-2009)
Iln’yapasdeme´thodeg´ene´ralepourtraiterlesr´ecurrences lin´eaires´acoefficientsvariables. Cetteremarqueestvalablepourlesr´ecurrencesnonline´aires
