[PDF] Calcul formel dans la base des polynômes unitaires de Chebyshev

View - Download Calcul formel dans la base des polynômes unitaires de Chebyshev

Previous PDF

Next PDF

Université Paris VII -

Denis DiderotUniversité Pierre et Ma-

rie Curie École Doctorale de Science Mathématiques de Paris Centre

Thèse de doctorat

Discipline : Mathématiques

présentée par `ÂNCalcul formel dans la base des polynômes unitaires de Chebyshevdirigée par Pierre-VincentKoseleff&FabriceRouillier Soutenue le 09 octobre 2015 devant le jury composé de :

M. AlinBostanINRIA SaclayˆIle-de-France

M. Pierre-VincentKoseleffIMJ-PRG

M. SylvainLazardINRIA Nancy Grand Est rapporteur

M meArianeMézardIMJ-PRG

M. DanielPeckerIMJ-PRG

M. FabriceRouillierINRIA Paris-Rocquencourt

M meAnnickValibouzeLIP6 M. Jacques-ArthurWeilXLIM, Université de Limoges rapporteur 2

Institut de Mathématiques de Jussieu -

Paris Rive Gauche

4, place Jussieu

75 005 ParisUPMC

École Doctorale de Sciences

Mathématiques de Paris Centre

4 place Jussieu

75252 Paris Cedex 05

Boite courrier 290

23 octobre 2015

Kính ta

.ng B´ô.

Remerciements

Je tiens tout d"abord à exprimer ma gratitude à mes directeurs de thèse Monsieur Pierre-Vincent Koseleff et Monsieur Fabrice Rouillier. Je les remercie pour leur confiance, ainsi que leur soutien permanent depuis mon arrivée à l"IMJ-PRG. Ils se sont toujours montrés extrêmement disponibles et m"ont guidé avec beaucoup d"enthousiasme, de com- préhension et de professionnalisme. Ils ont su me donner de précieux renseignements depuis mes premiers pas en Calcul Formel avec compétence et patience. Je remercie Messieurs Sylvain Lazard et Jacques-Arthur Weil pour avoir accepté de

rapporter cette thèse, pour les remarques constructives et pour l"intérêt qu"ils ont porté

à mes travaux. Je tiens également à remercier Mesdames Annick Valibouze et Ariane Mézard, Messieurs Alin Bostan et Daniel Pecker pour avoir accepté de faire partie de mon jury. Mes remerciements vont également à tout le personnel de l"équipe Analyse Algébrique qui a su apporter des réponses à mes questions, qui a toujours su être disponible pour

discuter et résoudre mes problèmes, qui a contribué significativement à mes développe-

ments. Je n"oublie pas les thésards dans le couloir 15-16 : Thibaud, Malick, Rafael, Martin,

Andrés, Hóa, Viê

.t, ... Un grand merci à tout ceux à l"IMJ-PRG, qui m"ont aidé pendant ma thèse. remercie pour ton aide dans mes recherches ainsi que ton accompagnement dans ma vie.

Je pense également au groupe "viê

.t-upmc" et les autres amis vietnamiens que je n"ai pas

cités. Mes remerciements les plus sincères vont à vous qui avez partagé mes joies ainsi que

mes difficultés dans la vie en France. Je pense maintenant à ma femme, mes enfants B´ôp et Bông qui m"ont toujours encou-

ragé et soutenu dans les moments difficiles. J"ai vécu, grâce à eux, des années inoubliables

en France. Enfin, j"ai toujours pu compter sur l"affection et le soutien de ma famille au Vietnam. Je pense à mes parents et à mon frère, que je ne remercierai jamais assez.

Résumé

Résumé

Nous proposons des méthodes simples et efficaces pour manipuler des expressions tri- gonométriques de la formeF=?dk=0fkcoskπn ,fk?Zoùd < nfixé. Nous utilisons les polynômes unitaires de Chebyshev qui forment une base deZ[x]avec laquelle toutes

les opérations arithmétiques peuvent être exécutées aussi rapidement qu"avec le base de

monômes, mais également déterminer le signe et une approximation deF, calculer le po- lynôme minimal deF. Dans ce cadre nous calculons efficacement le polynôme minimal de 2cos πn et aussi le polynôme cyclotomiqueΦn. Nous appliquons ces méthodes au calcul des diagrammes de noeuds de Chebyshev.

Mots-clefs

polynôme de Chebyshev, multiplication rapide, polynôme minimal,cosπn , polynôme cyclotomique, noeuds de Chebyshev,Fast computing with the Chebyshev"s monic polynomial

Abstract

We propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the formF=?dk=0fkcoskπn ,fk?Zwhered < nfixed. We make use of the monic Chebyshev polynomials as a basis ofZ[X]. We can perform arithmetic opera- tions (multiplication, division, gcd) on polynomials expressed in a Chebyshev basis (with the same bit-complexity as in the monomial basis), compute the sign ofF, evaluate it numerically and compute its minimal polynomial inQ[X]. We propose simple and effi- cient algorithms for computing the minimal polynomial of2cosπn and also the cyclotomic polynomialΦn. As an application, we give a method to determine the Chebyshev knot"s diagrams.

Keywords

Chebyshev"s monic polynomial, fast multiplication, minimal polynomial,cosπn , cyclo- tomic polynomial, Chebyshev knots

Table des matières

Introduction

9

1 Polynômes

15

1.1 Le polynôme unitaire de Chebyshev

15

1.2 Le polynôme cyclotomique

19

1.3 L"application Doublage

26

1.4 Le polynôme minimal de2cosπn

28

2 Opérations rapides avec les formes de Chebyshev

33

2.1 Résultats utiles ou classiques

34

2.2 La multiplication et la division de formes de Chebyshev

39

2.3 Stratégie "Diviser pour régner"

44

2.4 Changement de base

49

3 Calcul des polynômes minimaux

59

3.1 Calcul du polynôme cyclotomique

60

3.2 Calcul du polynôme minimal de2cosπn

63

4 Évaluation des expressions trigonométriques

69

4.1 Évaluation d"une expression trigonométrique

69

4.2 Calcul dans l"anneauZ[x]/?Mn?. . . . . . . . . . . . . . . . . . . . . . . . .78

4.3 Le polynôme minimal d"un élément deZ[2cosπn

]. . . . . . . . . . . . . . .81

5 Applications aux diagrammes de noeuds de Chebyshev87

5.1 Introduction

88

5.2 Calcul du polynôme caractéristique

90

5.3 Calculer les racines réelles deRa,b,c. . . . . . . . . . . . . . . . . . . . . . .96

5.4 Calculer les diagrammes des noeuds. . . . . . . . . . . . . . . . . . . . . . . 101

A Calculs faits avec Maple 18

105
A.1 Le paquetageChebUnit. . . . . . . . . . . . . . . . . . . . . . . . . . . . .105

A.2 Trouver la forme de Chebyshev

105

A.3 Minorer une somme de cosinus

107

Table des figures

115

Bibliographie

119

Index des notations

123

Introduction

Motivation

Les polynômes de Chebyshev sont utilisés dans de nombreux domaines des mathéma- tiques, notamment dans le secteur de l"Analyse Numérique. Une remarque attribuée à de nombreux mathématiciens et numériciens, citée au début de [ MH03 ], témoigne de cette importance :?Chebyshev polynomials are everywhere dense in numerical analysis.? Il est possible de lister plusieurs secteurs des mathématiques où les polynômes de Che- byshev jouent des rôles importants : théorie de l"interpolation, polynômes orthogonaux, théorie des approximations, intégration numérique, analyse numérique, théorie d"ergo- dique, etc. [ Riv90 , Préface]. Mais aussi en théorie des noeuds où il est démontré que :tous les noeuds sont des noeuds de Chebyshev[KP11]. Le point de départ du travail effectué dans cette thèse est :déterminer le signe d"une expression trigonométrique de la formeF=?dk=0ˆfkcoskπn ,ˆfk?Q,pourd < nfixé dansZ>0.Bien entendu, cette question est classique et il s"agit de l"évaluation du nombre algébrique réelcosπn en un polynôme de degréd. Nous traitons d"une question plus générale qui est celle de manipuler de telles expres- sions. Il apparaˆıt rapidement que le nombre algébrique2cosπn est plus adapté quecosπn car son polynôme minimalMnest unitaire à coefficients entiers. Il convient alors de considérer plutôt les polynômes unitaires de ChebyshevTn(2cosx) = 2cosnxet l"expression à étudier devient alorsF=f0+? kfkTk(2cosπn Les polynômes unitaires de Chebyshev forment une base deZ[x]qui est particulière- ment adaptée au calcul du polynôme minimalMnde2cosπn . Nous montrons que nous pouvons effectuer les opérations arithmétiques usuelles deZ[x](multiplication, division, pgcd) avec la même complexité qu"avec la base des monômes. Dans ce contexte, nous montrons que nous pouvons décider de la nullité deFen?O(n2τ) opérations binaires et que nous pouvons calculer le polynôme minimal deFen?O(n3τ) opérations binaires, oùτest la taille binaire desfk. Ces résultats sont ensuite utilisés pour étudier les diagrammes des noeuds de Cheby- shev. Il s"agit de décider si la courbe gaucheC(a,b,c,φ) :x=Ta(t),y=Tb(t),z=Tc(t+φ) admet des points multiples, et dans la négative, de déterminer son diagramme.

Contributions et plan de la thèse

La thèse comporte cinq parties.

Dans la première partie, nous décrivons les polynômes unitaires de Chebyshev, les polynômes cyclotomiques et certaines de leurs propriétés. Nous introduisons l"application Det ces propriétés, mettons en évidence le lien entre le polynôme minimalMnde2cosπn

12Table des matièreset le polynôme cyclotomiqueΦ2n. Nous rappelons que les sommes de Newton deΦnsont

aussi des sommes de Ramanujan. La famille des polynômes unitaires de Chebyshev forme une base orthogonale deZ[x] et elle a l"avantage de rendre les calculs beaucoup plus concis que fait dans la base des polynômes de Chebyshev de type original. Avec cette base nous pouvons exécuter toutes les opérations arithmétiques dansZ[x]aussi rapidement qu"avec la base de monômes, ce que nous décrivons dans la seconde partie.

En introduisant l"applicationdoublage

quotesdbs_dbs29.pdfusesText_35

[PDF] centrale mp 2015

[PDF] centrale mp 2013

[PDF] centrale mp 2014 physique corrigé

[PDF] schema centrale thermique a flamme

[PDF] controle physique 3eme production d électricité

[PDF] centrale thermique nucléaire

[PDF] fonctionnement centrale hydraulique

[PDF] centrale hydraulique en france

[PDF] centrale hydraulique edf

[PDF] centrale hydraulique huile

[PDF] centrale pc 2009 maths 2 corrigé

[PDF] centrale pc 2014 physique 1 corrigé

[PDF] rapport centrale pc 2015

[PDF] centrale pc 2014 physique 2 corrigé

[PDF] centrale pc 2014 maths 1 corrigé