Mathématiques discrètes : Suites récurrentes

Description

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 : [e-mail]
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 ...

Sujets

• Homonymie
• Équation de Laplace
• Partition héraldique
• Étant Donnés
• Coefficient binomial
• Mathématiques discrètes

Informations

• Publié par: Infyo
• Nombre de lectures: 138
• Langue: Français

Extrait

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 : [e-mail]

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(u n ) n∈N . Ainsi, une relationfder´ecurrencesepre´sentesouslaforme:

u n =f(u n−1 , . . . ,u n−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 (u n ) n∈N des puissances deu 0 efid´epnilaarets relationder´ecurrencelin´eaire,homoge`ne d’ordre 1 :u n =u 0 u n−1 . La suite (u n ) n∈N nieparlaests´dfiecaotirlesedfserbmon relationder´ecurrencenonlin´eaire,nonhomoge`ne d’ordre 1 :u n =nu n−1 . m s (C’ordrem Les suite n ) n∈N des coefficients binomiaux d sontd´efiniesparlesrelationsder´ecurrenceline´aires m m m−1 homoge`nesC=C+C. n n −1 n−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:

u n =cu n−1

n On obtient une forme closeu n =c u 0 . Lecasinhomoge`necorrespond`alarelation:

u n =cu n−1 +r(n)

On obtient une forme close : n X n n−i u n =c u 0 +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:

u n =c 1 u n−1 +∙ ∙ ∙+c k u n−k .

et sonnˆomecaract´erisuqiteopyl P k k k−i associ´ep(x) =x−c i x. 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{r 1 , . . . ,r k }, alors les k n suites(r) n∈N pour i= 1. . .k forment une base de V . i Si p(x)a p racines distinctes{r 1 , . . . ,r p }de j n multiplicite´{m 1 , . . . ,m p }, alors les k suites(n r) n∈N i pour i= 1. . .p et j= 1. . .m i .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:

u n =c 1 u n−1 +∙ ∙ ∙+c k u n−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´ecurrencedelaformeu n =f(u n/a )avec a constantestunee´quationdepartition.Elled´efinieunesuite re´currente(u) i dme.reeueinanu`qi n n ∈{a|i∈N}

L’e´tudedel’´equationdepartitionu n =cu n/a +d(n) se k+1 ram`ene`acelledelare´currencev k+1 =cv k +d(a) par le changement de variablev n =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