Université de Nice Sophia Antipolis Préparation l' Agrégation de Mathématiques

Sophia Antipolis

Description

Niveau: Supérieur
Université de Nice Sophia Antipolis Préparation à l' Agrégation de Mathématiques 2010-2011 Calcul dans Mp On veut calculer des résultats d'opérations, des valeurs de fonctions dans Mp. On a deux problèmes : – les arguments étant dans Mp les résultats n'ont aucune raison d'y être, – on ne sait en général pas calculer les résultats exacts (dans R). On suppose pouvoir calculer avec une plus grande précision c'est à dire dans Mp? avec p? > p, ensuite on arrondira les résultats à p chiffres. Dans le texte l'arrondi utilisé, noté ?p, est la troncature à p chiffres pour des raisons de simplicité (mais il est affirmé que les problèmes que l'on va voir se produisent aussi avec des arrondis plus subtiles). Étant donné une fonction f on suppose que pour tout x ? Mp on sait calculer y ? Mp? qui approche f(x) qu'on ne sait pas calculer en général. Quel est le sens précis de y approche f(x) ? Si on se place dans le cas y > 0 et on pose y = my 2p? 2ey alors y approche f(x) signifie que f(x) ? [ my?1 2p? 2ey , my+1 2p? 2ey ] . Se pose alors la question de savoir à quelle condition, pour quelle valeur de p? qu'on souhaite la moins grande possible, ce calcul de y permet de déterminer la troncature à p chiffres de f(x) noté ?p(f(x)).

• arrondi du produit des mantisses


• équation x2


• p?1 ·mz ±


• point de l'intervalle précédent


• p? ?


• décryptage de la condition


• mp? ?

Sujets

• Antipolis
• Universidad de Niza Sophia Antipolis

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 18
• Langue: Français

Extrait

UniversitÉ de Nice Sophia Antipolis PrÉparation À l’ AgrÉgation de MathÉmatiques

Calcul dansM p

2010-2011

On veut calculer des rsultats d’oprations, des valeurs de fonctions dansM p . On a deux problmes : – lesarguments tant dansM p les rsultats n’ont aucune raison d’y tre, – onne sait en gnral pas calculer les rsultats exacts (dansR). 0 On suppose pouvoir calculer avec une plus grande prcision c’est À dire dansM p avecp >p, 0 ensuite on arrondira les rsultats Àpchiffres. Dans le texte l’arrondi utilis, notρ p , est la troncature Àpchiffres pour des raisons de simplicit (mais il est affirm que les problmes que l’on va voir se produisent aussi avec des arrondis plus subtiles). Ètant donn une fonctionfon suppose que pour toutx∈ M p on sait calculery∈ M p qui 0 approchef(x)qu’on ne sait pas calculer en gnral. Quel est le sens prcis deyapprochef(x)? m y e y Si on se place dans le casy >0et on posey= p 0 2alorsyapprochef(x)signifie que h i 2 m y −1m y +1 e y e y f(x)∈ p 2, 0 2. 0 p 2 2 0 Se pose alors la question de savoir À quelle condition, pour quelle valeur depqu’on souhaite la moins grande possible, ce calcul deypermet de dterminer la troncature Àpchiffres def(x) notρ p (f(x)). Le lemme 1 nous propose 3 conditions quivalentes qu’on va expliciter avant de dmontrer leur quivalence. m y −1m y +1 0e y e y On supposepp >+ 1, on posey 1 = p 0 2ety 2 = p 2. On rappelle qu’on est dans le 0 2 2 cas positif. Les trois conditions quivalentes sont : 1.ρ p (y 1 ) =ρ p (y 2 ): les tronqus Àpchiffres dey 1 ety 2 sont gaux. C’est une condition facile À vrifier une fois qu’on a calculy, 2.]y 1 , y 2 ]∩ M p =∅: cette condition sert d’intermdiaire dans les quivalences, 0 3.y∈/M p ety 2 ∈/M p : ceci revient Ày6=ρ p (y)c’est À direm y ne se termine pas parp−p 0 zros et de mmey 2 6=ρ p (y 2 )doncm y + 1ne se termine pas parp−pzros c’est À dire 0 m y ne se termine pas parp−puns. Cette condition donne une ide des mauvais cas. Si l’on sait vrifier l’une de ces trois conditions alorsρ p (f(x)) =ρ p (y).

1 DÉmonstrationdu lemme 1 1.1 Quelquesremarques Pour simplifier on se place sur les positifs. 1.y∈ M p n’implique pas forcment quey 1 ety 2 appartiennent ÀM p . 0 0 2. Letexte parle de tronquer le dveloppement binaire aprs lep-me chiffre ce qui est peu e min clair. Par exemple0,01×2est tronqu en 0, peut-on parler dep-me chiffre? Si 0 p y∈ M p tronqueryrevient À tronquerm y Àpchiffres et À remplacer le dnominateur2 0 p par2, sinon il vaut mieux appliquer la dfinitionρ p (y) =max(M p ∩[0, y]). +∗+∗ 1 e min e min−1 3.min(M p ∩R) =min(M p ∩R) =2 =2. 0 2

0 p ep max 2−1 e max e max 2 2−1 e max e max 4. Parcontremax(M p ) = p 2 =2− p > max(M p ) = p 2 =2− 0 0 0 2 2 2 e max 2 e max p . Tous les deux sont <2. 2 5. Quelquesoity > max(M p )on aρ p (y) =max(M p ). e max 6. Enparticulier sif(x)>2alorsρ p (f(x)) =max(M p )mais on ne peut pas trouver y∈ M p qui approchef(x). 0 0 0 p−1p 7. Siy∈ M p et2< m y <2−1alorsy 1 ety 2 ∈ M p et sont dans l’intervalle des 0 0 lments deM p ayant pour exposante y . 0 Que se passe-t-il quandyest au bord d’un tel intervalle ? voir les deux remarques suivantes. 0 0 0 p−1p p− 1 2−1 e y 2−2 e y −1 orsy 1 = 0 8. Sim y = 2al p 2 = p 0 2, 2 2 – sie y 6=e min alorsy 1 est l’avant dernier point de l’intervalle prcdent, +∗ – sie y =e min alorsy 1 < min(M p ∩R)etρ p (y 1 ) = 0. 0 0 0 0 p p−1 p 2 e y 2 e y +1 9. Sim y = 2−1alorsy 2 = p 2 = p 0 2, 0 2 2 – sie y 6=e max alorsy 2 est le premier point de l’intervalle suivant, – sie y =e max alorsy 2 > max(M p )etρ p (y 2 ) =max(M p ). 0

1.2 LadÉmonstration +∗ On remarque d’abord que siy=min(M p ∩R)aucune condition n’est vrifie (cf. re- 0 marques 3. et 8.), par contre siy=max(M p )les trois conditions sont vrifies (cf. remarques 0 4. et 9.). On suppose queyn’est aucun de ces nombres limites alors –1.⇒2.On revient À la dfinition deρ p :ρ p (y 1 ) =max(M p ∩[0, y 1 ])etρ p (y 2 ) =max(M p ∩ [0, y 2 ])et videmmenty 1 < y 2 . Doncρ p (y 1 ) =ρ p (y 2 )implique que]y 1 , y 2 ]∩ M p =∅. –2.⇒3.C’est vident. 0 –3.⇒1.Voir le dcryptage de la condition 3. : sim y ne se termine pas parp−pzros lui retrancher 1 ne changera pas lesppremiers bits dem y doncρ p (y 1 ) =ρ p (y). De mme si 0 m y ne se termine pas parp−puns lui ajouter 1 ne changera pas lesppremiers bits de m y doncρ p (y 2 ) =ρ p (y).

2 Construirede mauvais cas On cherche desx∈ M p tels quef(x)soit trs proche d’uny 0 ∈ M p . Ainsi lorsqu’on calcule 0 y∈ M p approchantf(x),y 1 ety 2 seront de part et d’autre dey 0 jusqu’Àpassez grand, donc 0 ρ p (y 1 )6=ρ p (y 2 )et le lemme 1 ne pourra pas s’appliquer. Remarque : sif(x)∈ M p le lemme 1 ne pourra jamais s’appliquer mais on s’en fiche : on n’a pas À arrondirf(x)!

2.1 Pourl’addition Pourvu que l’cart entree min ete max le permette,e max −e min ≥p, ce qui est le cas dans la p m x 1 e x p 2−1 e x −p 1 1 pratique, on prendx 1 = p 2avecm x 1 6= 2−1etx 2 = p 2. 2 2 Soity=x 1 +x 2 dansM 2p alors sa mantisse s’critm y =m x1 11. . .1, doncm y 1 =m x1 11. . .10 | {z }| {z } |{z} |{z} pbitspbits pbitspbits etm y 2 =m x1 + 1 00. . .0ce qui ne permet pas de dterminer la troncature Àpbits dex 1 +x 2 . | {z } | {z } pbits pbits

Si maintenant on prendy=x 1 +x 2 dansM 2p+1 alors sa mantisse s’critm y =m x1 11. . .10, | {z } |{z} p+1bits pbits doncm y 1 =m x1 11. . .01etm y 2 =m x1 11. . .11ce qui permet de dterminer la troncature Àp | {z }| {z } |{z} |{z} p+1bitsp+1bits pbitspbits 0 bits dex 1 +x 2 :ρ p (x 1 +x 2 ) =x 1 . Il faut donc aller jusqu’Àp= 2p+ 1. On peut construire de mauvais cas analogues pour la soustraction.

2.2 Pourla multiplication Le problme est plus intressant. On cherche des nombresxetydansM p tels quex∙y soit trs proche d’un nombre deM p sans lui tre gal. On remarque que les exposants ne nous intressent pas, ce qui nous intresse est l’arrondi du produit des mantisses. p−1p On veut trouverxetyentiers dans l’intervalle[2,2−1]tels quex∙ysoit trs proche d’un nombrezdeM p . 2p−2p2p−1p On ax∙y∈[2,(2−1) ]etm z ∈[2,2−1]. Donc 2p−2 2p−1p−1 – soitx∙y∈[2,2 [,x∙yest un entier À2p−1bits, doncx∙y= 2∙m z ±koÙk est cherch petit non nul, 2p−1p2p – soitx∙y∈[2,(2−1) ],x∙yest un entier À2pbits, doncx∙y= 2∙m z ±koÙkest cherch petit non nul. Ètant donnsyimpair etkon peut trouver un candidatxen rsolvant −1p−1 –x=±k∙y)(mod 2dans le premier cas, mais alors la premire solutionx 0 n’est p−1 pas dans le bon intervalle, il faut prendre la suivantex 0 + 2, −1p –x=±k∙y(mod 2 )dans le second cas et vrifier quexest dans le bon intervalle.

2.3 Pourla racine carrÉe En fait le texte propose une mthode pour construire de mauvais cas pour le carr dont on pourra dduire de mauvais cas pour la racine carre. On veut trouverxentier dans l’intervalle p−1p [2,2−1]tel quex∙xsoit trs proche d’un nombrezdeM p . 2p−2p2p−1p On ax∙x∈[2,(2−1) ]etm z ∈[2,2−1]. Donc 2p−2 2p−1p−1 – soitx∙x∈[2,2 [,x∙xest un entier À2p−1bits, doncx∙x= 2∙m z ±koÙk est cherch petit non nul, 2p−1p2p – soitx∙x∈[2,(2−1) ],x∙xest un entier À2pbits, doncx∙x= 2∙m z ±koÙkest cherch petit non nul. Le texte propose une mthode une mthode itrative pour construire de telsx. 2l On choisitk(mod 8)= 1, on suppose avoir calculxtel quex=k(mod 2 ), on calculey 2l− 1 1 2 2l−2 tel quex∙y)= 1(mod 2, alorsz= (x+ky)vrifiez=k)(mod 2. 2 En effetkest impair doncxest impair doncyexiste et est impair,x+kyest pair,zest bien un entier. ? 2 1 2 22 22 22l On az= (x+ 2kxy+k y). On cherchex+ 2kxy+k y= 4k(mod 2). 4 2l−1 2l Dex∙y= 1(mod 2)on a2kxy= 2k)(mod 2. ? 2 22 2l Il restex+k y= 2k)(mod 2. 2l2l Commex=k(mod 2 )on posex=k+m2, alors   2 22l2l2 x+k y=k+m2 +k x−m2y 2 2l l2 = (k+kx y) +m2−km2y 2l−2 21 2l2 22l Or dex∙y(mod 2)= 1on ax y(mod 2)= 1et donck+kx y= 2k)(mod 2. ? l l2 2l Il restem2−km2y(mod 2)= 0.   l l2l2l l2 m2−km2y=m2−x−m2m2y l2 2l l2 =m2 (1−x y) +m2m2y . 2l = 0(mod 2)

Remarques : 2 1. Sik6(mod 8)= 1l’quationx=k(mod 8)n’a pas de solution, 2 2. l’quationx(mod 8)= 1a pour solutions 1, 3, 5, 7,   1k 3. Cecipeut vous rappeler que la suite rcurrentex n+1 =x n +, oÙk >0etx 0 >0, 2x n √ converge verskdansR. f(x n ) La mthode de Newton donne en gnral la suitex n+1 =x n − 0 et, applique À la f(x n )   2 1k fonctionf(x) =x−k, la suitex n+1 =x n +. 2x n Le lemme 2 montre la convergence quadratique de cette suite pour une distance qui dit 2 2l quex−kest d’autant plus proche de zro quex−k(mod 2 )= 0pourlgrand (distancep-adique).