DYNAMICAL SYSTEMS TRANSFER OPERATORS

pages

Documents

2010

Écrit par
Brigitte Vallée

Publié par
profil-urra-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Ebook

2010

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-urra-2012

Publié le

01 octobre 2010

Nombre de lectures

DYNAMICAL SYSTEMS, TRANSFER OPERATORS and FUNCTIONAL ANALYSIS Brigitte Vallee, Laboratoire GREYC (CNRS et Universite de Caen) Seminaire CALIN, LIPN, 5 octobre 2010

euclidean algorithm

probabilistic analysis

seminaire calin

analytical properties

generating function

transfer operator

universite caen

dynamical analysis

Voir

Publié par

profil-urra-2012

Publié le

01 octobre 2010

Nombre de lectures

DYNAMICALSYSTEMS,TRANSFEROPERATORS

andFUNCTIONALANALYSIS

Brigitte
Valle´e
,LaboratoireGREYC

(CNRSetUniversite´deCaen)

Se´minaireCALIN,LIPN,5octobre2010

mhtiroglAnaedilcuEehtfosisylanacitsilibaborP⇓noitcnufgnitarenegehtfoseitreporplacitylanA⇓rotareporefsnartehtfoesrevnI-isauQehtfoseitreporplacitylanA⇓rotareporefsnartehtfoseitreporplartcepS⇓sehcnarbehtfoseitreporpcirtemoeG⇓noisividehtfoseitreporpcitemhtirA⇓mhDynamical

tanalysis

ifo

oEuclidean

gAlgorithm
.

lAnaedilcuEA
edilcuEehtfosisylanacitsilibaborP⇓noitcnufgnitarenegehtfoseitreporplacitylanA⇓rotareporefsnartehtfoesrevnI-isauQehtfoseitreporplacitylanA⇓rotareporefsnartehtfoseitreporplartcepS⇓sehcnarbehtfoseitreporpcirtemoeGAEuclideanAlgorithm

⇓

Arithmetic

properties

eht

division

Dynamical
analysis
ofaEuclidean
Algorithm
.

mhtiroglAna
mhtiroglAnaedilcuEehtfosisylanacitsilibaborP⇓noitcnufgnitarenegehtfoseitreporplacitylanA⇓transferoperator

Analytical
propertiesofthe
Quasi-Inverse
ofthe

⇓

Spectral
propertiesofthe
transferoperator

⇓

Geometric
propertiesofthe
branches

AEuclideanAlgorithm

⇓

Arithmetic
propertiesofthe
division

Dynamical
analysis
ofaEuclidean
Algorithm
.

AEuclideanAlgorithm

⇓

Arithmetic
propertiesofthe
division

⇓

Geometric
propertiesofthe
branches

⇓

Spectral
propertiesofthe
transferoperator

⇓

Analytical
propertiesofthe
Quasi-Inverse
ofthe

transferoperator

⇓

Analytical
propertiesofthe
generatingfunction

⇓

Probabilisticanalysis
oftheEuclidean
Algorithm

input
(
u,v
)
,itcomputesthe
gcd
of
u
and
v
,

ehtnO

together

htiw

eht

deunitnoC

rFnoitca

noisnapxE

.v/u

ehT

(standard)EuclidAlgorithm:thegrandfatherofallthealgorithms.

,pm1+...1+2m1+1m1=vu:vufoEFC.htpedehtsip.stigidehteras’imeht,vdnaufodcgehtsipu0=1+pu0+pupm=1−pu1−pu<pu<0pu+1−pu1−pm=2−pu+...=...2u<3u<03u+2u2m=1u1u<2u<02u+1u1m=0u1u≥0u;u=:1u;v=:0u
The(standard)EuclidAlgorithm:thegrandfatherofallthealgorithms.

Ontheinput
(
u,v
)
,itcomputesthe
gcd
of
u
and
v
,

togetherwiththe
ContinuedFractionExpansion
of
u/v

.v/ufonoisnapxEnoitcarFdeunitnoC

u=:u;v=:uu;100

u
0
=
m
1
u
1
+
u
2


u
1
=
m
2
u
2
+
u
3
...
=
...
+

u
p
−
2
=
m
p
−
1
u
p
−
1
+
u
p
u
p
−
1
=
m
p
u
p
+0

u
p
isthe

≥u1

0
<u
2
<u
1
0
<u
3
<u
2



0
<u
p
<u
p
−
1

u
p
+1
=0


.stigidehteras’meht,vdnaufodcg.htpedehtsipi

FCEfouv:uv=m1+m21+.1..1+1mp,
The(standard)EuclidAlgorithm:thegrandfatherofallthealgorithms.

Ontheinput
(
u,v
)
,itcomputesthe
gcd
of
u
and
v
,

togetherwiththe
ContinuedFractionExpansion
of
u/v

unitnoC.v/ufonoisnapxEnoitcarFde

u
0
:=
v
;
u
1
:=
u
;
u
0
≥
u
1

u
0
=
m
1
u
1
+
u
2


u
1
=
m
2
u
2
+
u
3
...
=
...
+

u
p
−
2
=
m
p
−
1
u
p
−
1
+
u
p
u
p
−
1
=
m
p
u
p
+0


0
<u
2
<u
1
0
<u
3
<u
2



0
<u
p
<u
p
−
1

u
p
+1
=0


u
p
isthe
gcd
of
u
and
v
,the
m
i
’sarethe
digits
.
p
isthe
depth
.

uCFEof:
v

1u,=1v+m11+m21...+mp

.mhtiroglaehtfonoisnetxesuounitnocasimetsyslacimanydehT.0sehcaertahtyrotcejarta=)T,]1,0[(metsySlacimanyDehtfoyrotcejartlanoitarA=)0,...,)x(2T,)x(T,x(mhtiroglAnaedilcuEehtfonoitucexenA0=)0(T,0=6xrofx1−x1=:)x(T,]1,0[→−]1,0[:Terehw,)ix(T=1+ixroix1−ix1=1+ixsanettirwnehtsi1+iu+iuim=1−iunoisividehT.1−iuiu=:ixlanoitarehtyb)1−iu,iu(riapregetniehtecalpeRTheunderlyingEuclideandynamicalsystem(I).

(
u
1
,u
0
)
is:

ThetraceoftheexecutionoftheEuclidAlgorithmon

(
u
1
,u
0
)
→
(
u
2
,u
1
)
→
(
u
3
,u
2
)
→
...
→
(
u
p
−
1
,u
p
)
→

(
u
p
+1
,u
p
)=

(0
,u
p
)

.mhtiroglaehtfonoisnetxesuounitnocasimetsyslacimanydehT.0sehcaertahtyrotcejarta=)T,]1,0[(metsySlacimanyDehtfoyrotcejartlanoitarA=)0,...,)TheunderlyingEuclideandynamicalsystem(I).

xfor
x
6
=0
,T
(0)=0

(11T
:[0
,
1]
−→
[0
,
1]
,T
(
x
):=
x
−
x

211x
i
+1
=
x
−
x
or
x
i
+1
=
T
(
x
i
)
,
where
ii