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

De
Publié par

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? ?


Publié le : mardi 29 mai 2012
Lecture(s) : 23
Source : math.unice.fr
Nombre de pages : 4
Voir plus Voir moins
UniversitÉ de Nice Sophia Antipolis PrÉparation À l’ AgrÉgation de MathÉmatiques
Calcul dansMp
2010-2011
On veut calculer des rsultats d’oprations, des valeurs de fonctions dansMp. On a deux problmes : – lesarguments tant dansMples 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 dansMpavecp >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∈ Mpon sait calculery∈ Mpqui 0 approchef(x)qu’on ne sait pas calculer en gnral. Quel est le sens prcis deyapprochef(x)? my ey Si on se place dans le casy >0et on posey=p02alorsyapprochef(x)signifie que h i 2 my1my+1 eyey f(x)p2,02. 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. my1my+1 0eyey On supposepp >+ 1, on posey1=p02ety2=p2. On rappelle qu’on est dans le 0 2 2 cas positif. Les trois conditions quivalentes sont : 1.ρp(y1) =ρp(y2): les tronqus Àpchiffres dey1ety2sont gaux. C’est une condition facile À vrifier une fois qu’on a calculy, 2.]y1, y2]∩ Mp=: cette condition sert d’intermdiaire dans les quivalences, 0 3.y/Mpety2/Mp: ceci revient Ày6=ρp(y)c’est À diremyne se termine pas parpp 0 zros et de mmey26=ρp(y2)doncmy+ 1ne se termine pas parppzros c’est À dire 0 myne se termine pas parppuns. 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∈ Mpn’implique pas forcment quey1ety2appartiennent ÀMp. 0 0 2. Letexte parle de tronquer le dveloppement binaire aprs lep-me chiffre ce qui est peu emin clair. Par exemple0,01×2est tronqu en 0, peut-on parler dep-me chiffre? Si 0 p y∈ Mptronqueryrevient À tronquermyÀpchiffres et À remplacer le dnominateur2 0 p par2, sinon il vaut mieux appliquer la dfinitionρp(y) =max(Mp[0, y]). ++1eminemin1 3.min(MpR) =min(MpR) =2 =2. 0 2
0 p ep max 21emaxemax2 21emaxemax 4. Parcontremax(Mp) =p2 =2p> max(Mp) =p2 =20 0 0 2 22 e max 2emax p. Tous les deux sont <2. 2 5. Quelquesoity > max(Mp)on aρp(y) =max(Mp). emax 6. Enparticulier sif(x)>2alorsρp(f(x)) =max(Mp)mais on ne peut pas trouver y∈ Mpqui approchef(x). 0 0 0 p1p 7. Siy∈ Mpet2< my<21alorsy1ety2∈ Mpet sont dans l’intervalle des 0 0 lments deMpayant pour exposantey. 0 Que se passe-t-il quandyest au bord d’un tel intervalle ? voir les deux remarques suivantes. 0 0 0p1p p1 21ey22ey1 orsy1=0 8. Simy= 2alp2 =p02, 2 2 – siey6=eminalorsy1est l’avant dernier point de l’intervalle prcdent, +– siey=eminalorsy1< min(MpR)etρp(y1) = 0. 0 0 0 0p p1 p2ey2ey+1 9. Simy= 21alorsy2=p2 =p02, 0 2 2 – siey6=emaxalorsy2est le premier point de l’intervalle suivant, – siey=emaxalorsy2> max(Mp)etρp(y2) =max(Mp). 0
1.2 LadÉmonstration +On remarque d’abord que siy=min(MpR)aucune condition n’est vrifie (cf. re-0 marques 3. et 8.), par contre siy=max(Mp)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(y1) =max(Mp[0, y1])etρp(y2) =max(Mp[0, y2])et videmmenty1< y2. Doncρp(y1) =ρp(y2)implique que]y1, y2]∩ Mp=. 2.3.C’est vident. 0 3.1.Voir le dcryptage de la condition 3. : simyne se termine pas parppzros lui retrancher 1 ne changera pas lesppremiers bits demydoncρp(y1) =ρp(y). De mme si 0 myne se termine pas parppuns lui ajouter 1 ne changera pas lesppremiers bits de mydoncρp(y2) =ρp(y).
2 Construirede mauvais cas On cherche desx∈ Mptels quef(x)soit trs proche d’uny0∈ Mp. Ainsi lorsqu’on calcule 0 y∈ Mpapprochantf(x),y1ety2seront de part et d’autre dey0jusqu’Àpassez grand, donc 0 ρp(y1)6=ρp(y2)et le lemme 1 ne pourra pas s’appliquer. Remarque : sif(x)∈ Mple 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 entreeminetemaxle permette,emaxeminp, ce qui est le cas dans la p mx 1exp21exp 1 1 pratique, on prendx1=p2avecmx16= 21etx2=p2. 2 2 Soity=x1+x2dansM2palors sa mantisse s’critmy=mx111. . .1, doncmy1=mx111. . .10 | {z }| {z } |{z} |{z} pbitspbits pbitspbits etmy2=mx1+ 1 00. . .0ce qui ne permet pas de dterminer la troncature Àpbits dex1+x2. | {z } | {z } pbits pbits
Si maintenant on prendy=x1+x2dansM2p+1alors sa mantisse s’critmy=mx111. . .10, | {z } |{z} p+1bits pbits doncmy1=mx111. . .01etmy2=mx111. . .11ce qui permet de dterminer la troncature Àp | {z }| {z } |{z} |{z} p+1bitsp+1bits pbitspbits 0 bits dex1+x2:ρp(x1+x2) =x1. 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 nombresxetydansMptels quexy soit trs proche d’un nombre deMpsans 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. p1p On veut trouverxetyentiers dans l’intervalle[2,21]tels quexysoit trs proche d’un nombrezdeMp. 2p2p2p1p On axy[2,(21) ]etmz[2,21]. Donc 2p2 2p1p1 – soitxy[2,2 [,xyest un entier À2p1bits, doncxy= 2mz±kk est cherch petit non nul, 2p1p2p – soitxy[2,(21) ],xyest un entier À2pbits, doncxy= 2mz±kkest cherch petit non nul. Ètant donnsyimpair etkon peut trouver un candidatxen rsolvant 1p1 x=±ky)(mod 2dans le premier cas, mais alors la premire solutionx0n’est p1 pas dans le bon intervalle, il faut prendre la suivantex0+ 2, 1p x=±ky(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 p1p [2,21]tel quexxsoit trs proche d’un nombrezdeMp. 2p2p2p1p On axx[2,(21) ]etmz[2,21]. Donc 2p2 2p1p1 – soitxx[2,2 [,xxest un entier À2p1bits, doncxx= 2mz±kk est cherch petit non nul, 2p1p2p – soitxx[2,(21) ],xxest un entier À2pbits, doncxx= 2mz±kkest 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 2l1 12 2l2 tel quexy)= 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 12 22 22 22l On az= (x+ 2kxy+k y). On cherchex+ 2kxy+k y= 4k(mod 2). 4 2l1 2l Dexy= 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 xm2y 2 2l l2 = (k+kx y) +m2km2y 2l2 21 2l2 22l Or dexy(mod 2)= 1on ax y(mod 2)= 1et donck+kx y= 2k)(mod 2. ? l l2 2l Il restem2km2y(mod 2)= 0.   l l2l2l l2 m2km2y=m2xm2m2y l2 2l l2 =m2 (1x 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currentexn+1=xn+, oÙk >0etx0>0, 2xn converge verskdansR. f(xn) La mthode de Newton donne en gnral la suitexn+1=xn0et, applique À la f(xn)   2 1k fonctionf(x) =xk, la suitexn+1=xn+. 2xn Le lemme 2 montre la convergence quadratique de cette suite pour une distance qui dit 2 2l quexkest d’autant plus proche de zro quexk(mod 2 )= 0pourlgrand (distancep-adique).
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi