option C 2013/2014 UJF

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

option C 2013/2014 UJF

Message par parisse » mer. sept. 18, 2013 12:02 pm

Cours du 11/9:
Presentation rapide du programme de l'option C de l'agreg, lien vers le programme, le rapport du jury, la page agreg de Xcas.

Chapitre I: representation des objets mathematiques, algorithmes fondementaux.
1/ entiers machine, precision limitee. Entiers long, lien avec les polynomes, cout des operations de base + - * (algorithme naif) et comparaison avec la taille du resultat, algorithmes meilleurs pour la multiplication, etude detaillee de Karatsuba degre<2^n -> temps en 9*3^n-8*2^n, existence d'un seuil pour multiplication naive puis Karatsuba.
Illustration avec la session Exemples>arit>multpoly de Xcas.
2/ algorithmes fondementaux:
a/ PGCD, temps en O(n^2) pour entiers longs de taille n,
b/ identite de Bezout pour a>=b>0 a*u-b*v=_/-pgcd(a,b) calcul de u et v avec u_0=1, u_1=0, v_0=0, v_1=1, et pour verifier
a*u_n-b*v_n=(-1)^n*r_n
on definit u_n et v_n par recurrence
u_(n+2)=u_n+q_(n+2)*u_(n+1)
v_(n+2)=v_n+q_(n+2)*v_(n+1)
ou r_(n+2)=r_n-q_(n+2)*u_(n+1)
On a v_n*r_(n+1)+v_(n+1)*r_n=a, v_n strictement croissantes, au cran apres Bezout, on a v_n*pgcd(a,b)=a d'ou la suite v_n est majoree par a et v<a. De meme pour u<b.
Remarque (non demontree) Lien avec les reduites du developpement en fraction continue de a/b, ce sont les v_n/u_n pour n>=2.
c/ applications de Bezout: inverse modulaire pour au+nv=1, le calcul de u_n suffit, restes chinois

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. oct. 02, 2013 3:59 pm

18/09: pas de cours (stage des agrégatifs à Autrans).

25/09: TP de prise en main et debut des exercices du chapitre 1 http://www-fourier.ujf-grenoble.fr/~par ... regtp1.pdf

02/10: Cours no 2
* entier modulo p: représentation symétrique dans ]-p/2,p/2]
* reconstruction d'un rationel a/b donné par q mod p (a=b*q mod p)
S'il existe un rationnel a/b tel que a/b=q mod p tel que |a|<p/2 et 1<=b<p/2, si a'/b' est un autre rationnel tel que a'/b'=q mod p, |a'|<=p et 1<=b'<=p, alors a/b=a'/b'. De plus a/b est déterminé par l'algorithme de Bézout appliqué à q et p, avec arrêt au 1er rang n tel que r_n<=p (b=u_n et a=(-1)^n*r_n).
* puissance modulaire rapide, algorithme récursif et itératif. Applications
1/ test de Miller-Rabin. Complexité en O(ln(p)^3) si on multiplie les entiers naivement. Exercice: comparer avec la complexité du test par "trial division" (essayer la divisibilité par les entiers impairs inférieurs ou égaux à sqrt(p))
2/ extraction de racine carrée mod p pour p premier. Si p+1=0 mod 4, alors un carré a non nul mod p vérifie powmod(a,(p-1)/2,p)=1, on en déduit que b=powmod(a,(p+1)/4,p) est un racine carrée de a mod p. Si p+1=2 mod 4, c'est plus compliqué, on peut par exemple choisir un entier r au hasard, calculer le pgcd de (x+r)^(p-1)/2-1 mod p,x^2-a (obtenu par powmod) et de x^2-a mod p.
Un mot sur la racine carrée entière (sans démonstration).

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. oct. 22, 2013 6:55 am

9/10: suite du TP

16/10: Representation des objets mathematiques sur machine, suite
* entier modulo n: représentation symétrique dans ]-n/2,n/2]
* flottants m*b^e ou b=base (en général 2 ou 10), mantisse m, exposant e. Dans Xcas, si Digits>14 on utilise des flottants multiprécision (m entier long de taille fixée paramétrée par Digits), sinon des flottants "double"
* rationnels: couple d'entiers
* complexes: couple des précédents
* polynomes à 1 variable: représentation dense par la liste des coefficients (par ordre décroissant dans Xcas). Representation creuse (par ex. pour x^1000-1).
* polynome à plusieurs variables, représentation creuse, ordre des monomes (ex. ordre lexicographique), multiplication en O(n*m*ln(taille du produit)), discussion sur la densité (formule comb(n+d,n) pour le nombre de monomes possibles d'un polynome de degre total d en n variables)
* variable affectee ou non et expression symbolique, evaluation
* liste/vecteurs, liste de listes de meme taille=matrice
* autres types : sequences (pas de profondeur), tables, attention aux tables vs listes,
* Corps finis non premiers: instruction GF, representation par un polynome en fonction d'un generateur.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » ven. nov. 08, 2013 7:55 am

23/10: fin du 1er TP

6/11: Construction d'un corps fini.
-> démonstration de la formule X^(p^n)-X=produit des irreductibles de degré divisant n modulo p.
Dans un sens, on utilise que si A est irréductible de degré k, alors Z/pZ[X]/A est un corps ayant p^k éléments donc alpha^p^k=alpha pour tout alpha dans le corps, d'où on déduit que X^p^k-X est divisible par A, et X^p^k=X mod A entraint X^p^n=X mod A en réitérant "prendre à la puissance p^k" n/k fois.
Dans l'autre sens on utilise Bézout sur le degré k de A et n, on en déduit que X^pgcd(n,k)=X mod A et cela entraine que pgcd(n,k)=k sinon il y a trop de racines pour X^pgcd(n,k)=X dans le corps Z/pZ[X]/A
-> on en déduit une majoration du nombre de polynôme irréductibles de degré n, puis une minoration, en raisonnant sur les degrés. Pour p pas trop petit, on a environ une chance sur n de tomber sur un irréductible en prenant un unitaire de degré n à coefficients aléatoires.
-> Déf. de polynôme irréductible primitif: X doit engendrer le groupe cyclique K*. Pour en construire un, on part d'un élément cyclique d'un corps fini et on calcule son polynôme minimal.
Il y a euler_phi(card(K*)) éléments cycliques dans K*, si card(K*)=p^n-1=produit des p_i^r_i, la proba de tomber sur un cyclique est produit(1-1/p_i)
-> Représentation multiplicative (on prend l'exposant entier d'un générateur fixé, et -1 ou p^n-1 pour 0 de K), adaptée à * et inverse rapides, mais il faut une table pour repasser en représentation additive pour faire + et -. Exemple petits corps fini, en particulier de caractéristique 2 où + et - sont un ou exclusif sur des entiers (représentant des polynômes, en écrivant l'entier en base 2, les bits sont les coefficients du polynôme), et la construction de table est très rapide, pour avoir le représentant additif de X^(j+1)=X^j*X on décale d'un cran le réprésentant additif de X^j, on regarde s'il a un terme de degré X^n si oui on fait le ou exclusif avec l'entier représentant le polynôme irréductible primitif en base 2.

-> Extension algébrique de Q: comme pour Z/pZ, on a un couple de polynomes B/A où A est irréductible sur Q, et B/A représente B(alpha) avec A(alpha)=0 (alpha racine complexe de A). Il faut choisir une des racines si on veut faire des évaluations numériques, mais ce n'est pas nécessaire tant qu'on ne fait que du calcul algébrique.

-> Chapitre 2: PGCD, Bezout, résultant.
Début:
Polynome sur Z[X]: déf. de contenu (pgcd des coeffs entiers), partie primitive (une fois divisé par le contenu)
Proposition: Le produit de 2 polynômes primitifs est primitif. Si A et B sont primitifs et B divise A dans Q[X] alors il divise A dans Z[X].
Définition du pgcd de 2 polynomes primitifs dans Z[X], on prend un pgcd dans Q[X], on multiplie par le ppcm des dénominateurs, on prend la partie primitive, on change de signe si le coeff dominant est négatif. Unicité car si A et B sont primitifs et multiples dans Q[X], alors le coeff multiplicateur est un entier inversible donc est 1 ou -1.
Pour 2 polynomes quelconques, on multiplie par le pgcd des contenus.
Proposition: si p est un premier ne divisant pas le pgcd des coeff dominants de A et B, le degré du pgcd dans Z/pZ[X] est >= à celui dans Z[X], avec égalité sauf pour un nombre fini de premiers. En particulier si le degré dans Z/pZ[X] est nul, les polynômes sont premiers entre eux dans Z[X].

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. nov. 20, 2013 6:05 pm

13/6: TP sur les GF
-> Trouver un polynome irr\'eductible P de degr\'e 5 sur \Z/7\Z. En deduire une representation de GF(7,5). Factoriser le polynome P sur votre representation de GF(7,5) (on pourra utiliser l'application x -> x^7).
-> Determiner le polynome minimal de quelques elements de GF(7,5) en utilisant votre representation ou celle de Xcas. Meme question mais en degre 4 avec la repr\'esentation de Xcas.
-> Factoriser avec Xcas x^{16}-x modulo 2 (on pourra utiliser
factors(), % 2 et % 0). En deduire les polynomes irreductibles de degre 4 sur
Z/2\Z, d\'eterminez les polynomes irreductibles primitif de degre 4, pour l'un d'entre eux construire une table entre representation multiplicative et additive de GF(2,4).
-> Ecrire une fonction permettant de determiner si un polynome A est irreductible modulo p, en utilisant le PGCD avec les x^{p^k}-x modulo p. Quelle est sa complexite
si A est irreductible de degre d ?

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. nov. 20, 2013 6:16 pm

20/11:
Algorithme de PGCD modulaire:
Si le degre du pgcd modulo p est nul, on conclut. Sinon, il faut reconstruire un multiple entier connu du pgcd, on prend le multiple de lcoeff g. On normalise le pgcd mod p pour avoir lcoeff=g. Si p est assez grand et de bonne réduction, alors le pgcd dans Z est le reconstruit symétrique du pgcd modulo p. Pour tester on vérifie que le reconstruit symétrique divise A et B dans Z[X]. Mais cela nécessite un p souvent grand (attention, la norme inf du pgcd n'est pas toujours inférieure à la norme inf de A et B!) avec un risque de tomber sur un p de mauvaise réduction, on préfère calculer modulo plusieurs premiers et reconstruire via les restes chinois avec les p donnant le degré minimal de pgcd, lorsque le reconstruit symétrique se stabilise on teste la divisibilité de A et de B, si divisible c'est le PGCD (égalité dans la proposition).
Illustration avec un exemple simple, illustration de l'intérêt en comparant avec Euclide sur Q ou sur Z (cf. la session Aide->Exemples->poly->pgcd.xws)

Estimation sur les racines complexes d'un polynome P a coefficients complexes:
|z| < 1+max(abs(coeffs de P))/abs(lcoeff(P))
On en déduit une majoration des coefficients du PGCD de A et B en développant son écriture factorisée et en utilisant que les racines du PGCD sont racines communes de A et B. Pour une majoration plus fine, cf. par exemple Cohen (borne de Landau-Mignotte).

Complexité de l'algorithme modulaire en O(n^3) dans le cas le pire (grand degré de PGCD), la plupart du temps c'est en O(n^2) (si degré nul ou petit).

Application du PGCD: algorithme de Yun pour écrire un polynôme comme produit de puissances de polynômes sans facteur carré et premiers entre eux, présenté si les coefficients sont dans un corps de caractéristique 0.

Définition du résultant par l'identité de Bézout:
C'est le déterminant du système
A*U+B*V=C
où A, B, C donnés, U et V inconnus (coefficients dans un anneau intègre unitaire commutatif inclus dans un corps, par exemple Z dans Q ou Z[Y,Z,T...] dans le corps des fractions en Y,Z,T...), degré(U)<degré(B) et degré(V)<degré(A) et degré(C)<degré(A)+degré(B).
Prop: resultant(A,B)=0 si et seulement si A et B ne sont pas premiers entre eux.
Exemple: discriminant(A)=resultant(A,A')/lcoeff(A) exemple en dim2 et 3.
Observation: si A et B sont premiers entre eux et si les coefficients de C sont multiples du résultant alors U et V ont leurs coefficients dans l'anneau.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. déc. 11, 2013 1:01 pm

4/12: 1er entrainement (en temps non limite) sur les 2 textes du jury suivants:
1/ Cryptographie et factorisation
2/ Moyenne arithmetico-geometrique et application au calcul d'integrales elliptiques.
Conseils: attention a ne pas paraphraser le texte, il n'est pas necessaire de parler de tout, on peut faire un ou plusieurs developpements mathematiques dans les suggestions (souvent il s'agira de completer une preuve esquissee dans le texte). Presenter en 1 minute ou 2 un plan en debut (I, II, III...) et indiquer ou il y aura des illustrations informatiques.
S'attendre a se voir poser des questions sur la complexite des programmes des illustrations s'il y en a et si on n'en a pas parle soi-meme. Il n'est pas indispensable qu'il y ait des programmes dans les illustrations, une utilisation judicieuse des instructions du logiciel peut tres bien suffire, et c'est ce qu'on a souvent interet a faire avant d'avoir les parties mathematiques de l'expose bien au point, en particulier ne pas perdre trop de temps a mettre au point un programme, si ca ne marche toujours pas en 5 minutes avec debug() laissez le programme en l'etat, le jury vous aidera eventuellement a le corriger lors du passage.
En temps limite, il peut arriver que vous passiez completement a cote du texte (certains textes sont difficiles). Essayez alors de faire quand meme un expose mettant en valeur les connaissances au programme sur le theme du texte, mieux vaut finir avec 5 ou 6 que 1 ou 2...

Exemples de sessions Xcas d'illustration:
- Pollard: http://www-fourier.ujf-grenoble.fr/~par ... ollard.xws
- Moyenne arithmetico-geometrique http://www-fourier.ujf-grenoble.fr/~par ... _agreg.xws

Exemples de points que l'on peut developper:
- crypto/factorisation: methode RSA (on peut utiliser les instructions euler, inv(a % b), powmod, et si on veut coder des messages sous forme de chaine asc/char, convert pour les grouper), temps necessaire pour coder/decoder un message par RSA (lien avec la puissance rapide), equivalence de la connaissance de phi(n) et de n=p*q si p et q sont premiers, theoreme des anniversaires et methode de Pollard, temps necessaire pour factoriser un entier de n digits par factorisation naive en O(sqrt(n)*ln(n)^2), par Pollard-rho en O(n^(1/4)*ln(n)^2), autres methodes de factorisation et tests de primalite ou de cryptage/decryptage si on en connait.
- moyenne arit-geo: montrer que les suites sont adjacentes, montrer une estimation a priori sur |a_n-b_n|<=constante^(2^n-1)*|a_0-b_0|^(2^n), et en deduire la complexite du calcul de la moyenne arithmetico-geometrique avec k digits. On peut comparer la complexite avec celle qui serait issue d'une quadrature usuelle (avec romberg ou gaussquad dans Xcas). Sur les parametrisations, on peut montrer que toute conique admet un parametrage rationnel en utilisant une droite passant par un point de la conique de pente m et l'autre point d'intersection, et expliquer comment on peut ainsi calculer les integrales de racines carrees de fraction rationnelles en x et en un polynome du second degre en x (sans utiliser des sin/cos, sinh/cosh mais en se ramenant directement a des fractions rationnelles). On peut effectuer comme suggere par le texte certains des calculs algebriques avec Xcas. On peut enfin exposer le paragraphe qui explique pourquoi une cubique ne peut pas se parametrer rationnellement.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. déc. 11, 2013 7:41 pm

11/12:
Résultants suite.
Si A et B sont premiers entre eux et si C=résultant(A,B) alors U et V ont leurs coefficients dans l'anneau.
Preuve: par les formules de Cramer.
Conséquence: si A(X,Y,Z,...) et B(X,Y,Z,...) s'annulent en x,y,z,... alors resultant en X de A,B s'annule en y,z,...
Application: élimination, résolution d'un système polynomial de n équations à n inconnues, on prend le résultant 2 à 2 par rapport à Xn de (P1, Pn), de (P2, Pn), etc. (Pn-1,Pn) on obtient un système polynomial de n-1 équations à n-1 inconnues (si les polynomes sont premiers entre eux, cas générique), etc. jusqu'à se ramener à une équation polynomiale en 1 inconnue, dont on peut calculer les solutions (éventuellement de manière approchée), puis on revient au système précédent: 2 équations en 2 inconnues, on remplace X1 par une des racines on prend le PGCD des 2 polynomes en la variable restante, on cherche les racines, etc.

Exemple de système 2x2 tiré du TP 16 de Frédéric Han http://www.math.jussieu.fr/~han/agreg12 ... C/TP16.pdf, exercice IV: intersection de x*y=4 ou (x-2)^2+y^2=4 et de y^2=(x-3)*(x^2-16)

Proposition: si A et B sont de degré total a et b, partiel par rapport à X n et m alors le degré total du résultant par rapport à X de A et B est <= a*b, en fait il est <= a*b-(a-n)*(b-m), il y a égalité si les polynômes sont homogènes (si le résultant est non nul).
Preuve par développement du déterminant avec les permutations.

Conséquence: théorème de Bézout sur le nombre d'intersection de 2 courbes algébriques sans composante commune, ce nombre est inférieur au produit des 2 degrés des polynomes équations des 2 courbes.
Preuve en 2 étapes: on commence à montrer que le nombre est fini, puis on change de repère par rotation pour que 2 racines distinctes n'aient jamais la même projection sur Ox, et on applique la proposition sur le degré du résultant.

Exemples: exercice IV du TP16 ci-dessus, qui met en évidence comment on peut perdre des points d'intersection par rapport au produit des degrés des 2 courbes:
* points à coordonnées complexes et les points d'intersection ayant une multiplicité (se traduit par une tangence des courbes au point d'intersection), cas du cercle inter la cubique
* point à l'infini: (0,1,0) pour l'hyperbole inter la cubique:
Si on fait le résultant en x ou en y en coordonnées "normales", on a un résultant de degré 5 et non 6. En coordonnées homogènes, le résultant est de degré 5 en y et 6 en x (correspond à a*b-(a-n)*(b-m) pour a=2, b=3 et n=1,m=2 ou n=1 et m=3), avec un coefficient en y^6 nul pour le résultant en x de x*y-4t^2 et de y^2*t-(x-3t)*(x^2-16t^2), donc t=0 est racine du résultant. Le point à l'infini se trouve en posant t=0 donc x*y-4t^2=0 devient x*y=0 et y^2*t-(x-3t)*(x^2-16t^2) devient x^3=0 d'où x=0, d'où (0,y,0)=y(0,1,0) est dans l'intersection.

Autre application: calcul de l'équation cartésienne d'une courbe paramétrée par des fonctions rationnelles, exercice I du TP16. Pour les sin/cos il faut réécrire en fonction de u=tan(t/2) par exemple.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » lun. déc. 16, 2013 9:31 am

16/12: oral blanc en temps limite. Textes proposes:
- sommation de series alternees
- geometrie d'une molecule.
Exemples d'illustrations: menu Aide->Exemples->analyse->series_alt.xws,
http://www-fourier.ujf-grenoble.fr/~par ... hexane.xws

Suggestion series alternees: on peut montrer le theoreme 2 en appliquant le thm de convergence dominee. Attention, il n'y a pas convergence simple en 1, il faut donc montrer que la mesure du singleton {1} est nulle, ce qu'on peut faire en la majorant par an pour tout n et en faisant tendre n vers l'infini.
On peut montrer la relation de recurrence entre P_n, P_n+1 et P_n+2 en posant X=sin(t)^2 soit
cos(2n+4)t=2*(1-2sin(t)^2)*cos(2n+2)t-cos(2nt) qu'on obtient par exemple en linearisant cos(2t)*cos(2n+1)t.
On peut remarquer que les c_k et d_n s'obtiennent a partir des p_k par l'algorithme de Horner. Il n'est donc pas necessaire de calculer d_n comme indique dans le texte.
Sinon d_n se calcule avec la relation de recurrence en X=-1, par rsolve dans Xcas ou par recherche de suites geometriques solutions.
On peut s'interesser a la complexite des calculs. Combien de decimales et d'iterations faut-il calculer S a une precision donnee si on fait les calculs en flottants multiprecision? Et bien sur on peut faire le meme calcul de complexite en calculant les p_k comme des entiers.
On peut aussi comparer la complexite du calcul d'un P_n(X) ou de tous les P_k pour k<=n par la relation (2), par la recurrence entre les p_k, ou par la relation de recurrence entre P_n, P_n+1 et P_n+2.
Et bien sur illustrer le paragraphe 6 comme indique dans les suggestions.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mer. janv. 15, 2014 9:51 am

14/1: Autres exemples d'utilisation du resultant
-> Integration de fractions rationnelles:
etape 0: on se ramene a une fraction propre (degre numerateur<degre denominateur), la partie entiere de la fraction s'integre facilement (polynome)
etape 1: factorisation squarefree (par l'algorithme de Yun) puis decomposition en elements simples selon cette factorisation par Bezout -> on se ramene a integrer A/B^i, B sans racine multiple
etape 2: si i>1 on fait Bezout pour A=U*B+V*B' et on integre par parties V*B'/B^i, ceci permet de se ramener a une fraction A/B
etape 3: int(A/B)=somme([racines en t du resultant(B(x),A(x)-t*B'(x),x)]*ln(gcd(B,A-t*B'))
On montre que le coefficient de la decomposition en elements simples de 1/(x-z) est A/B'(z) pour z racine de B, c'est donc le coefficient du ln(x-z) correspondant. On regroupe ensuite les ln correspondant au meme coefficient. Les coefficients possibles sont bien racines du resultant puisque z est racine commune de B(x) et A(x)-(A/B')(z)*B(x), et l'ensemble des racines correspondant au meme coefficient de ln va donner le facteur ln(gcd(B,A-t*B')) apres regroupement.
Exercice: detailler le calcul de int((x^6+2)/(x^3+1)^2), int((1-x^2)/(1+x^4))
-> Extensions algebriques Q[alpha,beta]: exemple ecrire Q[sqrt(2),sqrt(3)] comme un Q[gamma]
On suppose que le polynome minimal de beta sur Q est encore irreductible sur Q[alpha], par ex. x^2-3 est irreductible sur Q[sqrt(2)]. Alors l'extension est de degre le produit des degres. On peut chercher un generateur sous la forme alpha+k*beta avec k entier, par exemple k=1, on cherche donc gamma=alpha+beta. On a A(alpha)=0 et B(beta)=0 donc B(gamma-alpha)=0, on elimine alpha en prenant resultant(A(x),B(gamma-x),x) qui s'annule car alpha est racine commune. On factorise le resultant, s'il est irreductible et du bon degre (cas generique), c'est le polynome minimal de gamma et Q[gamma]=Q[alpha,beta]
Exercice: traiter le cas de Q[sqrt(2),sqrt(3)]
-> Parametrisation rationnelle d'une conique a*x^2+b*x*y+c*y^2+d*x+e*y+f=0, a,b,c non tous nuls.
On suppose connu un point de la conique (pour une conique non vide). On cherche alors la 2eme intersection de la conique avec la droite y-y0=t*(x-x0) (l'equation est de degre 2 en x, mais on connait une solution x0, donc on garde (x-x0) factorise, l'autre solution s'obtient avec le 2eme facteur).
Exemples: ellipse de foyer A(-1,0) et B(1,0) passant par C(2,0),
conique x^2+y^2+6*x*y-3=0
La parametrisation rationnelle permet de se ramener a des calculs polynomiaux, par exemple pour faire l'intersection des 2 coniques ci-dessus, on peut prendre la parametrisation de l'une et remplacer dans l'autre (ou bien sur faire le resultant des 2 equations cartesiennes).

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. janv. 21, 2014 6:29 pm

21/1: Autour de la factorisation.
-> Rappel majoration des racines complexes par M=1+linfnorm(P)/|lcoeff(P)|
-> localisation des racines réelles.
Suites de Sturm pour P polynome à coeff réels sans racines multiples on pose
R_0=P, R_1=P', R_{n+2}=-rem(R_n,R_ {n+1}), ..., R_N=dernier reste non nul (constant)
Alors le nombre de racines de P sur ]a,b] est la différence entre s(P,a) et s(P,b) où s(P,x) est le nombre de changements de signe de R_n(x) en ignorant les 0.
Corollaire: localisation à epsilon près des racines réelles, on commence par compter le nombre de racines dans [-M,M], si c'est 0 c'est fini, si c'est 1 on passe à la dichotomie usuelle, sinon on coupe en 2 et on recommence sur chaque intervalle de longueur moitié.
Nombre d'opérations: en arithmétique flottante O(deg(P)^2) opérations pour calculer la suite des R_n, puis O(deg(P)) pour calculer S(P,x) en x (en utilisant la récurrence pour évaluer R_n(x) en fonction des 2 précédents)
Commandes dans Xcas: sturm, sturmab, realroot
N.B.: il existe un algorithme un peu concurrent qui permet d'isoler des racines plus efficacement, cf. la commande VAS dans Xcas.
-> Un mot sur les méthodes numériques: Newton qui permet d'affiner très rapidement une racine connue grossièrement, décomposition de Schur sur la matrice companion du polynôme pour estimer les racines simultanément. Commande Xcas: proot.
-> Racines rationnelles: algorithme de recherche par essais des quotients diviseur du coeff de plus bas degré/coeff dominant. Peu efficace, car nécessite de factoriser des entiers peut-etre grands et la liste des diviseurs peut être très grande.
Algorithme p-adique (voir Manuel->Algorithmes). Commandes Xcas: rationalroot, crationalroot.
-> différents sens de factor : à 1 variable sur R, C (coeffs approx->factorisation approx), Q, Q (coeffs exacts -> factorisation en irréductibles sur le corps des coefficients), Q[alpha] (factorisation sur une extension algébrique, on passe alpha en 2ème argument de factor, on peut éventuellement trouver alpha avec solve). On peut aussi factoriser sur Z/pZ (factor(polynome % nombre premier)) ou sur un corps fini (mettre le générateur du GF en 2ème argument de factor).
A plus de 2 variables: sur Q, Q, Q[alpha] implémenté. Notion de factorisation absolue: on recherche une éventuelle extension algébrique pour que la factorisation soit maximale (la même que sur C).

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. févr. 11, 2014 4:57 pm

28/1: texte sur la molécule.
Compléments sur la géométrie interactive 2-d et 3-d, exemple de preuve en géométrie analytique formelle avec le théorème de Napoléon. Réalisation de la figure en cliquant les 3 points en mode approché puis exact (cocher ou décocher le ~ en haut de la figure), conjecture en approché, preuve dans ce cas en exact. Puis passage en coordonnées formelles (clic droit sur le point et cocher symb, ou menu Edit ajouter paramètre).

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. févr. 11, 2014 5:06 pm

4/2: texte sur la factorisation
http://www-fourier.ujf-grenoble.fr/~par ... texte1.pdf
En complément:
-> La visualisation des racines d'un polynome dans le plan complexe
point(proot(x^3+x-3),affichage=epaisseur_point_3)
-> La localisation des racines dans C peut se faire en se ramenant au réel avec
P(x+i*y)=R(x,y)+i*I(x,y)
puis étude de resultant(R,I,x) et resultant(R,I,y) par exemple avec Sturm. Mais c'est très inefficace sauf si n est petit, en effet chaque résultant est génériquement de degré n^2, avec des gros coefficients, et il faut ensuite recombiner n^2*n^2=n^4 intervalles possibles pour trouver n rectangles d'isolation des racines.
-> Les racines complexes approchées peuvent servir à trouver une factorisation exacte en recombinant plusieurs racines: si elles correspondent à un facteur de Z[X] alors lcoeff(P)*somme de ces racines doit être très proche d'un entier. Mais pour un degré n grand, prouver l'irréductibilité de cette manière nécessite de tester énormément de combinaisons (O(2^n)).

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » mar. févr. 11, 2014 5:11 pm

11/2: TP exercices 1 à 3 sur les résultants du poly Aide->Algorithmes.
Remarque sur rootof: le solver de Xcas factorise les polynômes de degré 2 en introduisant des racines carrées, pour le degré 3 il cherche une extension algébrique qui permet d'exprimer toutes les racines, en général elle est de degré 6 (2ème argument du rootof), au-delà il affiche un warning extension algébrique non implémentée et renvoie vide ou une valeur approchée.

parisse
Messages : 5734
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: option C 2013/2014 UJF

Message par parisse » ven. févr. 21, 2014 1:20 pm

18/2: Algebre lineaire
Pivot de Gauss et variantes
Algorithme du pivot de Gauss pour réduire une matrice de taille L,C.
On initialise l et c à 1.
Tant que l<=L et c<=C faire
- si tous les coefficients sont nuls dans la colonne c à partir de la ligne l, incrémenter c et passer à l'itération suivante
- sinon on échange le cas échéant la ligne avec la ligne l pour avoir un pivot non nul en ligne l, on crée des 0 soit en-dessous de la ligne l (réduction sous-diagonale) soit sur toutes les lignes sauf la ligne l (réduction complète) par des manipulations de type L_k <- L_k - m_{k,c}/m_{l,c} L_l, incrémenter l et c et passer à l'itération suivante.
Décomposition PA=LU pour une matrice à coefficients dans un corps fini. L est triangulaire inférieure avec des 1 sur la diagonale, et les coefficients de la manipulation créant le 0: L_i <- L_i - l_{i,j} L_j si on réduit avec la ligne c (en général la colonne c), P matrice de permutation correspond aux inversions pour mettre le coeff non nul de la colonne c en ligne l.
Applications de LU: résolution de système, inverse de matrice n,n par résolution de n systèmes, déterminant.
Autres applications de Gauss: inverse par réduction complète de (matrice|identité), calcul du noyau (réduction sous-diagonale de (transposée de matrice|identité) ou par réduction complète de la matrice et insertion de lignes de 0 pour mettre les pivots 1 sur la diagonale, puis on ajoute ou enlève des lignes de 0 pour avoir une matrice carrée, puis extraction des colonnes ayant des 0 sur la diagonale et remplacement par -1 qui donnent une base du noyau).
Variante de Gauss-Bareiss pour rester à coefficients dans l'anneau: on remplace la manipulation L_k <- L_k - m_{k,c}/m_{l,c} L_l par L_k <- (m_{l,c} *L_k - m_{k,c}*L_l)/pivot_utilisé_pour_réduire_la_colonne_précédente.
Nombre d'opérations O(n^3) dans le corps. Pour Gauss-Bareiss, cela donne un O(n^5*ln(n)^2) avec multiplication naive des entiers (si la matrice est bornée en norme infinie par une constante M). Moins bon que des méthodes modulaires pour calculer le déterminant, mais plus général.

Variante du pivot partiel: on prend l'element dans la colonne de module maximal en calcul numerique pour limiter les erreurs (car alors le coefficient de la combinaison lineaire est en module <=1). En calcul exact, on choisira plutot le pivot le plus simple possible (type ou valeur)

Reduction de Hermite: pour faire des operations elementaires inversibles dans Z (ou plus generallement un anneau euclidien), on ne peut pas faire L_k <- (m_{l,c} *L_k - m_{k,c}*L_l, on fait simultanement 2 operations de lignes en utilisant l'identite de Bezout entre a=m_{l,c} et b=m_{k,c}, a*u+b*v=d=pgcd(a,b)
L_k <- a/d*L_k - b/d*L_l et L_l <- v*L_k + u*L_l.
Comme pour le pivot de Gauss, on arrive ainsi a une forme reduite triangulare superieure, mais cette fois-ci en multipliant a gauche par une matrice de GL(Z) (de determinant 1 ou -1). On peut reduire au-dessus de la diagonale en effectuant la division euclidienne du coefficient par le pivot et L_k <- L_k -q *L_l mais cela ne donne en general pas des 0.
Cette forme peut servir a calculer une Z-base d'un noyau et permet ainsi de resoudre des equations diophantiennes. On pose A la matrice dont on cherche le noyau, on calcule la forme de Hermite B de tran(A): U*tran(A)=B avec U inversible, on prend les lignes de U correspondant aux lignes nulles de B, elles forment une Z-base du noyau, cela vient de A*tran(U)=tran(B), les colonnes de tran(U) correspondant a des colonnes de B nulles sont bien dans le noyau, ces colonnes sont a coeff entiers, independantes (U est inversible), il y en a le bon nombre et si Av=0 alors A*tran(U)*tran(U^-1)v=0 donc B*tran(U^-1)v=0 donc les coordonnees du debut de tran(U^-1)v sont nulles, les autres sont entieres puisque tran(U^-1) est a coeff dans Z, on en deduit que v est combinaison lineaire a coeff entiers des colonnes de la fin de tran(U).

Répondre