option C-2014/15

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

Modérateur : xcasadmin

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

Re: option C-2014/15

Message par parisse » mar. janv. 20, 2015 3:09 pm

20/1:
Localisation des racines d'un polynome (suite)
* cas reel: il existe des methode alternative a Sturm: algorithme VAS implemente par realroot dans Xcas
* cas complexe:
idee 1: P(x+i*y)=R(x,y)+i*I(x,y)=0 donne un systeme polynomial a 2 variables qu'on peut resoudre avec le resultant. Inefficace car le degre du resultant est generiquement deg(P)^2
idee 2: suites de Sturm complexes, voir le texte d'entrainement http://www-fourier.ujf-grenoble.fr/~par ... texte1.pdf
idee 3: factoriser numeriquement (par exemple en diagonalisant la matrice companion) puis certifier l'existence de racines en utilisant :
Si delta=module(P(z)/P'(z)), alors le disque B(z,n*delta) contient au moins une racine.
Preuve: P'/P=dérivée log de P=somme sur les n racines de 1/(z-racine)
et on raisonne par l'absurde.
On peut ainsi certifier l'existence de racines d'un polynôme, en prenant pour z un rationnel proche d'une racine approchée calculée par proot ou tout autre méthode numérique (voir la commande exact). Par exemple P:=x^4+3x+1; L:=proot(P); z:=exact(L[0]); d:=horner(P,z)/horner(P',z);

Pour localiser les racines, il n'est pas necessaire de factoriser le polynome en produit d'irreductibles, sauf l'etape de factorisation squarefree.

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).
A plus de 2 variables, notion de factorisation absolue: on recherche une éventuelle extension algébrique pour que la factorisation soit maximale (la même que sur C). Voir dans Aide>Exemples>poly>afactor.xws
Un mot sur la factorisation dans Q: on se ramene a Z, puis on cherche sur Z/nZ pour n premier en esperant "remonter" la factorisation.
Presentation de l'algorithme de Berlekamp pour factoriser dans Z/nZ[X] un polynome sans facteur multiple :
on considère l'application lineaire phi de l'espace vectoriel sur Z/nZ des poly de degré inférieur à degré(P) sur lui-même qui envoie un poly A sur A^n-A mod P. Théorème dim Ker phi=nombre de facteurs irréductibles de P.
Les facteurs irréductibles de P s'obtiennent en calculant une base (1,T2,T3...) de Ker(phi) par réduction de Gauss sur la matrice de phi dans la base canonique puis en calculant des pgcd(T2-alpha,P), pgcd(T3-alpha,P) pour alpha de 0 à n-1.
Exemple dans Aide>Exemples>poly>berle.xws

Interpolation de Lagrange: calcul par les differences divisees en O(n^2) operations sur le corps, et evaluation du polynome interpolateur donne par sa suite de differences divisees en 3n operations sur le corps.
Exemple d'application: calcul du polynome caracteristique d'une matrice de taille n a coefficients dans un corps fini de cardinal >n en O(n^4) operations en interpolant lamba_i,det(A-lambda_i*I) pour n+1 elements distincts du corps.

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

Re: option C-2014/15

Message par parisse » mer. févr. 04, 2015 10:21 am

27/1: Point singulier d'une courbe parametrique dependant d'un parametre avec le resultant: exercice 6.3.6 dans Aide>Manuel>Algorithmes,
TP factorisation: section 16.9 exos 1, 2, 3.

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

Re: option C-2014/15

Message par parisse » mer. févr. 04, 2015 10:29 am

3/2: Texte sur la geometrie d'une molecule.
Exemples d'illustrations: http://www-fourier.ujf-grenoble.fr/~par ... hexane.xws
Attention, le nombre de solutions pour le cyclohexane est infini, contrairement a ce que pourrait laisser penser l'etude du systeme P(u,v)=0, P(v,w)=0, P(u,w)=0 avec le resultant...
Parametrisation rationnelle d'une ellipse, application au calcul d'integrales avec une racine carree de polynome du second degre.
Equation 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 translate le repere en ce point ce qui revient a prendre f=0.
On cherche alors la 2eme intersection de la conique avec la droite y=t*x : l'equation est de degre 2 en x, mais on connait une solution x=0, l'autre solution s'obtient avec le 2eme facteur qui donne x en fonction de t puis y=t*x.
L'etude des branches asymptotiques comme courbe parametrique de x,y redonne les differents cas pour une conique (etude des racines du denominateur a+b*t+c*t^2 en fonction de a,b,c et des asymptotes eventuelles en ces racines: si delta=b^2-4ac<0 pas de branches donc ellipse, si racine double une branche parabolique de direction y=racine*x, sinon 2 asymptotes de pente les 2 racines).
Cas particulier: si (d*x+e*y) divise a*x^2+b*x*y+c*y^2, on obtient 2 droites (la fraction rationnelle donnant x et y en fonction de t se simplifie).

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

Re: option C-2014/15

Message par parisse » mar. févr. 17, 2015 2:32 pm

10/2: Texte du jury sur les series alternees
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.

TP programmation du calcul des differences divisees et de l'evaluation du polynome d'interpolation en 3n operations a partir des points d'interpolation, des differences divisees, et du point ou on evalue.

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

Re: option C-2014/15

Message par parisse » mar. févr. 24, 2015 5:20 pm

24/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).

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 U, mais cette fois-ci en multipliant a gauche par une matrice de GL(Z) (de determinant 1 ou -1), on notera cette matrice L (attention, elle n'est pas triangulaire inférieure, mais son analogue pour le pivot de Gauss le serait).
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 U de tran(A): L*tran(A)=U avec L inversible, on prend les lignes de L correspondant aux lignes nulles de U, elles forment une Z-base du noyau, cela vient de A*tran(L)=tran(U), les colonnes de tran(L) correspondant a des colonnes de tran(U) nulles sont bien dans le noyau, ces colonnes sont a coeff entiers, independantes (L est inversible), il y en a le bon nombre et si Av=0 alors A*tran(L)*tran(L^-1)v=0 donc tran(U)*tran(L^-1)v=0 donc les coordonnees du debut de tran(L^-1)v sont nulles, les autres sont entieres puisque tran(L^-1) est a coeff dans Z, on en deduit que v est combinaison lineaire a coeff entiers des colonnes de la fin de tran(L).

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

Re: option C-2014/15

Message par parisse » mar. mars 03, 2015 3:22 pm

3/3:
Reduction de Smith et application aux groupes abeliens de type fini. On fait Hermite sur les lignes puis sur les colonnes puis a nouveau sur les lignes etc., le processus finit par s'arreter (pour i,j fixes, regarder comment evoluent a_ii, a_jj, a_ij et a_ji si l'un des non diagonaux est non nul, a l'etape suivante on en prend le pgcd avec a_ii ou a_jj et l'autre coeff non diagonal devient plus petit, d'un facteur 2 si on choisit le reste symetrique pour l'etape finale de reduction de Hermite au-dessus de la diagonale par quotient euclidien).
Exemple recherche de la structure du groupe abelien defini par les generateurs x1 et x2 et les relations 2x1+4x2=0 et -2x1+6x2=0, on pose A:=[[2,4],[-2,6]] puis U,B,V:=ismith(A), on en deduit que les diviseurs elementaires sont 2 et 10 donc G est isomorphe a Z/2*Z/10, avec comme generateurs V^(-1)*[x1,x2] soit y1=x1+2x2 et y2=x2 (on a bien 2y1=0 et 10y2=0).
Utilisation en calcul formel: le plus grand facteur invariant de A apparait au denominateur des composantes de la solution de Ax=b, il donne en general un gros facteur de det(A), la resolution de Ax=b permet d'accelerer sensiblement le calcul de det(A) pour A a coefficients entiers.

Reduction des endomorphismes:
a/ Rappel: interpolation de Lagrange si le cardinal du corps est > n la dimension de la matrice. O(n^4) opérations au lieu de O(n^3) opérations ... mais sur K[X] (c'est mieux car multiplication naive sur K[X] est en O(n^2))
b/ Recherche du polynome minimal relatif à un vecteur aléatoire, il divise le polynome minimal de la matrice donc le polynome caractéristique de la matrice, donc s'il est de degré n, on en déduit que les 3 sont égaux (une fois normalisés). On cherche le noyau de la matrice dont les colonnes sont v_0=v, ..., v_{k+1}=Av_k, ..., v_n=Av_{n-1}. Algorithme en O(n^3) mais ne marche pas toujours (-> Hessenberg marche par contre toujours en O(n^3) cf. Cohen)
c/ Algorithme de Fadeev : (x*I-A)*B(x)=det(x*I-A) I, B(x) transposée de la comatrice de x*I-A. On calcule les coefficients en puissance décroissante de B par une méthode à la Horner, en utilisant une relation supplémentaire pour calculer simultanément les coefficients de det(xI-A) qui est
trace(B(x))=derivée de det(x*I-A)
Algorithme en O(n^4), qui donne en plus B(x) qui peut servir à calculer les espaces propres puisque si x0 est valeur propre simple alors (x0*I-A)*B(x0)=0 et B(x0) n'est pas nul (sinon on divise B(x) par x-x0 et en x0 on a (x0*I-A)*B(x)/(x-x0)=det(x*I-A)/(x-x0)I est inversible alors que (x0*I-A) ne l'est pas). On calcule seulement la 1ere colonne de B(x0) par Horner, si elle est nulle, la 2eme etc. en general on trouve l'espace propre en O(n^2) operations par espace propre (au lieu de O(n^3)).

TP: programmation de la recherche du polynome minimal relatif a un vecteur aleatoire

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

Re: option C-2014/15

Message par parisse » mar. mars 17, 2015 6:17 pm

10/3: pas de séance (semaine des écrits)

17/3: TP algèbre linéaire
1/ compléter v:=[2,3,5] en une Z-base de Z^3. On calcule G,U:=ihermite(tran(v))
Comme le contenu de v est 1, U est le vecteur colonne [1,0,0], comme G*tran(v)=U, la 1ère colonne de G^-1 est tran(v) donc les 2 autres colonnes de G complètent la base.
2/ résolution de l'équation diophantielle 2x+3y+5z=1, le calcul ci-dessus donne v*tran(G)=tran(U), on en déduit immédiatement une solution particulière, la 1ère colonne de tran(G) et 2 solutions de l'équation homogène les 2 autres colonnes de tran(G)
Résolution d'un système du type 2x+3y+5z=1 et 7x+5y-3z=2, on calcule
G,U:=ihermite(tran(A:=[[2,3,5],[7,5,-3]])
on a G*tran(A)=U donc A*tran(G)=tran(U), le système A*X=tran([1,2]) devient tran(U)*Y=tran([1,2]) en posant X=tran(G)*Y, la résolution en Y est triviale, on en déduit X.
3/ Groupe abélien donné par 3 générateurs m1, m2, m3 vérifiant des relations
2m1+3m2+5m3=0 et 7m1+3m2-5m3=0 soit A*M=0
On calcule la forme de Smith de A: U,B,V:=ismith(A), on a U*A*V=B, donc U*A*M=0 devient B*N=0 avec M=V*N (N le vecteur colonne n1,n2,n3). On en déduit que les nouveaux générateurs n1, n2, n3 vérifient n1=0, 15n2=0, donc le coefficient de n2 est dans Z/15Z, celui de n3 est un entier quelconque, et G est isomorphe à Z/15Z+Z.

4/ Programmation de l'algorithme de Faddeev

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

Re: option C-2014/15

Message par parisse » mar. mars 24, 2015 5:29 pm

24/3:
texte sur les carrés magiques (éléments de correction dans le manuel Amusements de xcas).

Compléments:
* certificat de primalité de N
Si N-1 se factorise partiellement comme produit de p_i^{e_} * f avec f<sqrt(N) et si pour chaque p_i on peut trouver a_i tel que a_i^(N-1)=1 mod N (Fermat) et a_i^{(N-1)/p_i}-1 est premier avec N, alors N est premier.
Le certificat de primalité est la lliste des (p_i,a_i).
Preuve: sinon il existe un facteur v premier<=sqrt(N), on considère b_i=a_i^{(N-1)/p_i^{e_i}}, on a b_i^{p_i^{e_i}}=1 mod N donc mod v, et b_i^{p_i^{e_i-1}}!=1 mod v (seconde hypothèse) donc b_i est d'ordre p_i^{e_i} donc p_i^{e_i} divise v-1 donc v=1 mod p_i^{e_i} donc par les restes chinois v=1 modulo le produit p_i^{e_i} ce qui est absurde car v est un facteur premier de N <=sqrt(N)
La commande isprime(,1) de Xcas renvoie un certificat de primalité de ce type mais en utilisant un énoncé plus fort (il suffit de savoir factoriser partiellement jusque N^(1/3)).
D'autres certificats existent utilisant d'autres théorèmes.
* méthode de Pollard-rho: théorème des anniversaires, la proba d'avoir n nombres entre 0 et N-1 distincts 2 à 2 est équivalente pour N grand à exp(-n^2/(2*N)) si n^2/N tend vers une limite non nulle (on calcule ln(P), on le voit comme une méthode des rectangles sur une fonction monotone).
Pour l'appliquer à un entier x à factoriser, N est le plus petit facteur premier de x. On génère les n entiers par une suite récurrente u_{n+1}=f(u_n), avec typiquement f(x)=x^2+1. Comme on ne connait pas N, on teste l'égalité modulo N par gcd(u_k-u_k',x) non trivial. On ne teste pas toutes les paires k,k', mais seulement k'=2k, en effet la suite est ultimement périodique (d'où le nom rho de la méthode). Il faut de l'ordre de O(sqrt(N)) termes pour trouver le facteur N.
Ce type de méthode de factorisation a une complexité qui dépend de la taille du plus petit facteur de x, comme la division. Il diffère des méthodes comme le crible quadratique dont la complexité dépend de x. On utilise en général d'abord des méthodes comme Pollard-rho pour détecter les "petits" facteurs d'un entier x (de taille jusqu'à 10^18 environ pour Pollard-rho), avant de passer à des méthodes du type du crible quadratique.

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

Re: option C-2014/15

Message par parisse » jeu. avr. 02, 2015 6:43 pm

31/3, 7/4, 21/4, 28/4: séances sur le thème crypto, codes correcteurs faites par une collègue.
Documentation de Xcas correspondant:
Aide>Manuel>Programmation>Codage
Aide>Manuel>Algorithmes>chapitre 14.4
RSA et codage dans http://www-fourier.ujf-grenoble.fr/~par ... egint.html
Sessions: Aide>Exemple>crypto

Répondre