Université de Nice Sophia Antipolis Préparation l' Agrégation de Mathématiques
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
4
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
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)).
Voir
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? ?
UniversitÉ de Nice Sophia Antipolis PrÉparation À l’ AgrÉgation de MathÉmatiques
Calcul dansMp
2010-2011
On veut calculer des rsultats d’oprations, des valeurs de fonctions dansMp. On a deux problmes : – lesarguments tant dansMples rsultats n’ont aucune raison d’y tre, – onne sait en gnral pas calculer les rsultats exacts (dansR). 0 On suppose pouvoir calculer avec une plus grande prcision c’est À dire dansMpavecp >p, 0 ensuite on arrondira les rsultats Àpchiffres. Dans le texte l’arrondi utilis, notρp, est la troncature Àpchiffres pour des raisons de simplicit (mais il est affirm que les problmes 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 gnral. Quel est le sens prcis deyapprochef(x)? my ey Si on se place dans le casy >0et on posey=p02alorsyapprochef(x)signifie que h i 2 my−1my+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 dterminer la troncature Àpchiffres def(x) notρp(f(x)). Le lemme 1 nous propose 3 conditions quivalentes qu’on va expliciter avant de dmontrer leur quivalence. my−1my+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 tronqus Àpchiffres dey1ety2sont gaux. C’est une condition facile À vrifier une fois qu’on a calculy, 2.]y1, y2]∩ Mp=∅: cette condition sert d’intermdiaire dans les quivalences, 0 3.y∈/Mpety2∈/Mp: ceci revient Ày6=ρp(y)c’est À diremyne se termine pas parp−p 0 zros et de mmey26=ρp(y2)doncmy+ 1ne se termine pas parp−pzros c’est À dire 0 myne se termine pas parp−puns. Cette condition donne une ide des mauvais cas. Si l’on sait vrifier 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 forcment quey1ety2appartiennent ÀMp. 0 0 2. Letexte parle de tronquer le dveloppement binaire aprs 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 dnominateur2 0 p par2, sinon il vaut mieux appliquer la dfinitionρp(y) =max(Mp∩[0, y]). +∗+∗1eminemin−1 3.min(Mp∩R) =min(Mp∩R) =2 =2. 0 2
0 p ep max 2−1emaxemax2 2−1emaxemax 4. Parcontremax(Mp) =p2 =2−p> max(Mp) =p2 =2− 0 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 p−1p 7. Siy∈ Mpet2< my<2−1alorsy1ety2∈ Mpet sont dans l’intervalle des 0 0 lments deMpayant pour exposantey. 0 Que se passe-t-il quandyest au bord d’un tel intervalle ? voir les deux remarques suivantes. 0 0 0p−1p p−1 2−1ey2−2ey−1 orsy1=0 8. Simy= 2alp2 =p02, 2 2 – siey6=eminalorsy1est l’avant dernier point de l’intervalle prcdent, +∗ – siey=eminalorsy1< min(Mp∩R)etρp(y1) = 0. 0 0 0 0p p−1 p2ey2ey+1 9. Simy= 2−1alorsy2=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(Mp∩R)aucune condition n’est vrifie (cf. re-0 marques 3. et 8.), par contre siy=max(Mp)les trois conditions sont vrifies (cf. remarques 0 4. et 9.). On suppose queyn’est aucun de ces nombres limites alors –1.⇒2.On revient À la dfinition 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 dcryptage de la condition 3. : simyne se termine pas parp−pzros lui retrancher 1 ne changera pas lesppremiers bits demydoncρp(y1) =ρp(y). De mme si 0 myne se termine pas parp−puns 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 trs 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,emax−emin≥p, ce qui est le cas dans la p mx 1exp2−1ex−p 1 1 pratique, on prendx1=p2avecmx16= 2−1etx2=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 dterminer 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 dterminer 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 problme est plus intressant. On cherche des nombresxetydansMptels quex∙y soit trs proche d’un nombre deMpsans lui tre gal. On remarque que les exposants ne nous intressent pas, ce qui nous intresse est l’arrondi du produit des mantisses. p−1p On veut trouverxetyentiers dans l’intervalle[2,2−1]tels quex∙ysoit trs proche d’un nombrezdeMp. 2p−2p2p−1p On ax∙y∈[2,(2−1) ]etmz∈[2,2−1]. Donc 2p−2 2p−1p−1 – soitx∙y∈[2,2 [,x∙yest un entier À2p−1bits, doncx∙y= 2∙mz±koÙk est cherch petit non nul, 2p−1p2p – soitx∙y∈[2,(2−1) ],x∙yest un entier À2pbits, doncx∙y= 2∙mz±koÙkest cherch petit non nul. Ètant donnsyimpair etkon peut trouver un candidatxen rsolvant −1p−1 –x=±k∙y)(mod 2dans le premier cas, mais alors la premire solutionx0n’est p−1 pas dans le bon intervalle, il faut prendre la suivantex0+ 2, −1p –x=±k∙y(mod 2 )dans le second cas et vrifier quexest dans le bon intervalle.
2.3 Pourla racine carrÉe En fait le texte propose une mthode pour construire de mauvais cas pour le carr dont on pourra dduire de mauvais cas pour la racine carre. On veut trouverxentier dans l’intervalle p−1p [2,2−1]tel quex∙xsoit trs proche d’un nombrezdeMp. 2p−2p2p−1p On ax∙x∈[2,(2−1) ]etmz∈[2,2−1]. Donc 2p−2 2p−1p−1 – soitx∙x∈[2,2 [,x∙xest un entier À2p−1bits, doncx∙x= 2∙mz±koÙk est cherch petit non nul, 2p−1p2p – soitx∙x∈[2,(2−1) ],x∙xest un entier À2pbits, doncx∙x= 2∙mz±koÙkest cherch petit non nul. Le texte propose une mthode une mthode itrative pour construire de telsx. 2l On choisitk(mod 8)= 1, on suppose avoir calculxtel quex=k(mod 2 ), on calculey 2l−1 12 2l−2 tel quex∙y)= 1(mod 2, alorsz= (x+ky)vrifiez=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 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 rcurrentexn+1=xn+, oÙk >0etx0>0, 2xn √ converge verskdansR. f(xn) La mthode de Newton donne en gnral la suitexn+1=xn−0et, applique À la f(xn) 2 1k fonctionf(x) =x−k, la suitexn+1=xn+. 2xn Le lemme 2 montre la convergence quadratique de cette suite pour une distance qui dit 2 2l quex−kest d’autant plus proche de zro quex−k(mod 2 )= 0pourlgrand (distancep-adique).
