Xcas

Cette page contient des informations utiles aux candidats pour l'épreuve d'oral de modélisation de l'agrégation de mathématiques (options A, B ou C) qui envisagent d'utiliser Xcas, certaines parties peuvent également servir aux candidats pensant utiliser d'autres logiciels, à savoir les parties décrivant la documentation en ligne (manuels, exemples de petits programmes) en relation avec le programme, les algorithmes utilisés par Xcas et les exemples de texte.

Quelques raisons de choisir Xcas :

• Si vous passez l'agrégation interne, vous pouvez mutualiser l'apprentissage de Xcas pour la deuxième épreuve orale de l'agreg interne (dite d'exercices) et la modélisation de l'agreg externe.
• L'apprentissage de Xcas peut ou pourra vous servir avec vos classes de lycée où l'usage de Xcas est maintenant assez répandu pour faire un peu de calcul formel ou pour enseigner l'algorithmique.
• La prise en main de Xcas est rapide (des milliers de lycéens l'utilisent...). On peut choisir de programmer avec une syntaxe en francais ou compatible Python.
• Xcas dispose d'une aide en ligne rapide, description courte en 2 lignes de la commande et exemples recopiables (menu Aide->Index ou début de commande puis touche de tabulation), on peut ensuite cliquer sur Details pour lire une documentation plus complète entièrement rédigée en francais (moins de risque d'erreur d'interprétation le jour du concours en situation de stress!). Les menus permettent d'accéder aux commandes par thèmes ce qui permet de les (re)trouver facilement.
  La documentation en francais comprend un manuel d'algorithmes de calcul formel et numérique, un manuel d'algorithmique et des exemples faciles à adapter pour la présentation sur ordinateur (dans les manuels ou depuis le menu Aide, Exemples), on peut chercher un mot-clef (F12) pour trouver les pages d'aides correspondantes.
• Vous trouverez sur cette page de nombreuses informations relatives à l'utilisation de Xcas pour la modélisation pour les 3 options (contrairement à certains logiciels de calcul formel interprétés, Xcas est écrit en C++ et compilé donc aussi efficace pour faire du calcul numérique ou de la simulation qu'un logiciel spécialisé pour peu que les fonctions nécéssaires soient incluses).
  Vous pouvez poser vos questions (en francais!) sur la section agreg du forum de Xcas.
• Xcas affiche les zones de parenthèses, crochets ou accolades correspondantes, ce qui facilite la recherche d'erreurs de parenthèsage par exemple. Les mots clefs du language sont affichés en couleur et les commandes dans une autre couleur.
• Xcas possède un débuggueur interactif permettant l'exécution d'un programme ligne à ligne et la visualisation de l'évolution du contenu des variables, ce qui facilite la mise au point d'une fonction bugguée.
• Vous pouvez facilement installer Xcas sur votre ordinateur personnel, aussi bien sous Linux (l'OS du concours) que sous Windows et Mac (téléchargement de taille raisonnable - moins de 200 Mo -, installation semblable à d'autres logiciels, cf. le paragraphe suivant).

Si je vous ai convaincus que Xcas mérite un essai, voici maintenant des informations relatives à son installation et à son utilisation pour l'oral de modélisation à l'agrégation.

Télechargement de Giac/Xcas

Vous pouvez

• installer la version stable de Xcas depuis la page d'installation
• ou vous pourrez charger sur le site de jury agregOS permettant d'avoir sur un PC avec VirtualBox la même configuration qu'à l'oral.

Une fois Xcas installé, vous pouvez vous familiariser à son utilisation avec le tutoriel en ligne (menu Aide, Débuter en calcul formel) ou ce document TP agreg 1 pour l'option C. Vous pouvez aussi ajouter dans votre navigateur un lien vers le forum.

Attention:

• N'oubliez pas de vérifier le style de programmation lorsque vous lancez Xcas (bouton d'état au centre en haut de la session)
• Dans le mode par défaut (syntaxe Xcas), les vecteurs/matrices ont des indices commençant à 0 si on utilise des délimiteurs [] ou à 1 si on utilise des délimiteurs () en lecture, mais pas en écriture s'il y a ambiguité avec une définition de fonction. Pour utiliser des indices commençant à 1 sans risque d'ambiguité, on peut utiliser des double-crochets, par exemple v[[1]] (ou v[0]), M[[1,2]] (ou M[0,1]).

---

Méthodes numériques (chapitre 13)

Une grande partie du programme du chapitre 13 provient de parties traitées auparavant en modélisation option B. On peut sans doute supposer que le degré de maitrise des aspects modélisation attendu sera plus grand pour les candidats à l'option B que pour les candidats des autres options, mais on peut imaginer que les textes des autres options qui s'y pretent peuvent faire usage d'une méthode de ce programme.

Systèmes d'équations linéaires

Notion de conditionnement. Théorème de Gershgörin-Hadamard. Pivot de Gauss, décomposition LU. Méthodes itératives (par exemple méthode de Jacobi, méthode de Gauss-Seidel) ; analyse de convergence : normes subordonnées, rayon spectral. Décomposition en valeurs singulières. Exemple de la matrice de discrétisation par différences finies du laplacien 1D.

• Les commandes correspondantes sont : lu, linsolve, jacobi_linsolve, gauss_seidel_linsolve, matrix_norm, rref, ker, inv, cond, svl, conjugate_gradient, laplacian. Voir le chapitre Algèbre linéaire de la documentation de Xcas (menu Aide, Manuels, Algorithmes).
• Factorisation LU
  La première valeur renvoyée par lu est une permutation que l'on peut convertir en matrice avec permu2mat, par exemple
  A:=ranm(10,10,0..1); p,L,U:=lu(A); P:=permu2mat(p); P*A-L*U On peut utiliser le résultat de lu pour résoudre en O(n^2) un systeème linéaire Ax=b par p,L,U:=lu(A); linsolve(p,L,U,b)
• Si une matrice A est inversible, on peut calculer pour une norme de matrice (subordonnée à une norme sur les vecteurs) le produit |||A||| * |||A^(-1)|||, appelé conditonnement de la matrice (cond(A) ou cond(A,2) ou cond(A,inf) en Xcas selon qu'on utilise la norme L1 ou L2 ou Linfinie pour mesurer les erreurs sur les vecteurs). Plus ce produit est grand, plus il sera intrinsèquement difficile de trouver une solution précise au système Ax=b, les erreurs relatives sont multipliéee au plus par ce facteur lorsqu'on résoud un système linéaire.
  Par exemple avec Xcas: a:=[[1001,1000],[1000,1001]]; b1:=[1.,1.]; x1:=inv(a)*b1; b2:=[.99,1.01]; x2:=inv(a)*b2; l2norm(b2-b1)/l2norm(b1); l2norm(x2-x1)/l2norm(x1); l'erreur relative sur la solution est multipliée par 2000 environ (rapport entre la valeur propre la plus grande et la plus petite de la matrice symétrique a). Voir dans Aide, Manuels, Algorithme le chapitre 11.6 ou par exemple le chapitre 9 du cours de L2 de M. Eisermann.
• svl(A) renvoie la liste des valeurs singulières de la matrice, on en prend le quotient de la plus grande par la plus petite pour avoir le conditionnement L2.
• laplacian(n) renvoie la matrice du laplacien 1d discret.

Résolution de systèmes d'équations non linéaires.

Cas des systèmes linéaires : méthodes itératives. Recherche d’éléments propres : méthode de la puissance. Optimisation de fonctions convexes en dimension finie, méthode du gradient à pas constant, moindres carrés. Problèmes non linéaires réels et vectoriels : méthode de dichotomie, méthode de Picard, méthode de Newton, vitesse de convergence et estimation de l’erreur.

• Systèmes linéaires: voir item précédent.
• Recherche des valeurs propres : méthode de la puissance.
  Commandes utiles : eigenvalues, eigenvectors, qr, SCHUR.
  Exemple, analyse, pui: programme simple de la méthode de la puissance. On peut appliquer divers variantes comme récurrence à 2 crans (pour les couples de valeurs propres conjuguées en restant dans le réel), itérations inverses, élimination, cf. la section Réduction approchée des endomorphismes du manuel Algorithmes de Xcas.
  La méthode qr consiste à itérer l'opération factorisation QR de la matrice A, calcul de RQ, ce qui donne une matrice semblable à A dont on peut montrer dans certains cas qu'elle converge vers une matrice triangulaire supérieure. La convergence peut etre plus rapide en "shiftant" la matrice A par un coefficient lambda proche d'une valeur propre, on travaille sur A-lambda*identite au lieu de A. Si on a au préalable effectué une tridiagonalisation (Hessenberg), une itération se fait en O(n^2) opérations arithmétiques au lieu de O(n^3), on peut meme faire des itérations en restant dans les réels pour les couples de valeurs propres conjuguées (algorithme de Francis, commande SCHUR de Xcas).
• Méthode du gradient pour les systèmes linéaires définis positifs
  Il s'agit de résoudre Ax=b, où A est définie positive. La commande conjugate_gradient(A,b) permet de faire ce calcul, on peut préciser une valeur initiale de recherche x0 et une précision eps en tapant conjugate_gradient(A,b,x0,eps)
  Si on a une base orthogonale pour le produit scalaire induit par A, on peut calculer la j-ième coordonnèe de x dans cette base en faisant le produit scalaire de Ax=b par le j-ième vecteur de la base. On construit donc petit à petit une base orthogonale pour A par un procédé à la Gram-Schmidt, mais on ne part pas de la base canonique : on construit cette famille orthogonale pour A en meme temps qu'on calcule les composantes de x.
  On pose x_0=0, à la i-ième itération si Ax_i-b=0 on a terminé, sinon r_i=Ax_i-b est linéairement indépendant des éléments de la famille orthogonale dejà construite, on complète la famille orthogonale avec un nouveau vecteur, on calcule la i+1-ième composante de x sur la famille orthogonale, et on ajoute le tout à x_i pour obtenir x_{i+1}. On s'arrete en au plus la dimension itérations lorsque la famille orthogonale est devenue une base. Voir Example, analyse, gradconj.
• Moindres carrés linéaires (sans contraintes)
  La commande LSQ(A,b) (LSQ pour Least SQuare) permet de résoudre un système linéaire Ax=b au sens des moindres carrés. Pour un système sous-déterminé, la norme du vecteur inconnu est minimisée ; (par projection de 0 sur l'espace affine des solutions de direction ker(A)). Pour un système sur-déterminé, la norme de Ax-b est minimisée (par projection orthogonale de b sur image(A))
  Les instructions utiles pour illustrer une régression linéaire
  • linear_regression(liste_x,liste_y) régression linéaire des valeurs de y en fonction des valeurs de x
  • linear_regression_plot(liste_x,liste_y): trace la droite de régression linéaire, affiche l'équation de la droite ainsi que R^2 (corrélation au carré) qui mesure la qualité de la régression. Pour tracer le nuage de points correspondant, utiliser scatterplot avec les mêmes arguments.
  • d'autres régressions se ramenant à des régressions linéaires se trouvent dans le menu Cmds, Proba-stats, 2d.
  • Pour effectuer des régressions multi-linéaires, voir par exemple ici. On remarquera que la matrice à inverser est symétrique définie positive, on peut donc utiliser cholesky pour en trouver l'inverse.
  Vous pouvez entrer des valeurs dans un niveau tableur de Xcas (menu Tableur nouveau tableur) et utliser le menu Tableur pour faire une régression linéaire ou tracer des nuages de points sur les données de 2 colonnes du tableur à sélectionner à la souris.
• Méthode de Newton
  Commandes utiles: newton, fsolve. Voir le manuel Algorithmes de Xcas, section Suites récurrentes et applications (menu Aide, Manuels, Algorithmes)
  La commande fsolve dispose d'options pour spécifier l'algorithme. Ainsi les options hybrid*solver de fsolve sur des systèmes d'équations utilisent des méthodes combinant la méthode de Newton avec des méthodes de descente de gradient. Pour les systémes polynomiaux à coefficients exacts, la commande fsolve utilisée sans point de départ utilise les bases de Groebner et la représentation univariée rationnelle, ce qui permet de trouver toutes les racines réelles ou complexes approchéees.
  Une illustration se trouve dans Aide, Exemples, analyse, newton. La méthode de Newton se programme facilement avec Xcas en dimension 1 (F12, indiquer Newton comme mot-clef) car on dispose de la dérivée formelle de la fonction de départ et de son inverse.
  En dimension plus grande, il y a un peu plus de syntaxe. On prendra garde en particulier au fait que diff(vecteur,liste_variables) renvoie la transposée de la matrice jacobienne.
  Par exemple si on a une fonction de 2 variables, disons
  F(x,y):=[(x-y)^2+4y^2-4,2x^2+y^2-x*y-5]
  on en calcule la dérivée
  invF1:=unapply(inv(tran(diff(F,[x,y]),x,y)))
  puis on initialise un point de départ xy:=[.2,.3], alors xy:=xy-invF1(op(xy))*F(op(xy)) effectue une itération de Newton (on peut exécuter plusieurs fois l'instruction en mode interactif ou la programmer).
  En dimension plus grande que 3 environ ou si F a des coefficients numériques, le calcul de l'inverse formel est déconseillé, il vaut mieux le faire à chaque itération une fois que x a une valeur (on peut aussi conserver l'inverse pour quelques itérations, mais on perd alors la convergence quadratique, on peut aussi utiliser la décomposition LU ou linsolve pour calculer la solution du système). Ce qui pourrait donner
  F(x):=[(x[0]-x[1])^2+4*x[1]^2-4,2*x[0]^2+x[1]^2-x[0]*x[1]-5]
  purge(x); F1:=unapply(tran(diff(F(x),[x[0],x[1]])),x)
  x:=[1.2,2.3]
  pour j de 1 jusque 100 faire x:=x-inv(F1(x))*F(x); si l2norm(F(x))<1e-12 alors break; fsi; fpour;
  

Intégration numérique

Méthode des rectangles, estimation de l’erreur. Méthode de Monte-Carlo : vitesse de convergence, application au calcul d’intégrales multiples.

• Quadratures
  Commandes utiles: int, area, gaussquad, romberg. Documentation: voir le manuel Algorithmes de Xcas section intégration numérique (menu Aide, Manuels, Algorithmes), ou le livre de Demailly ou les polys de Hairer, où on trouvera aussi des infos sur les quadratures gaussiennes et les estimations d'erreurs.
  La commande area de Xcas admet en paramètre rectangle_droit, rectangle_gauche, trapezoid, simpson. On peut facilement les coder
  rect(f,a,b,n):=(b-a)/n*sum(f(a+(b-a)/n*j),j,0,n-1)
  trap(f,a,b,n):=(b-a)/n*(1/2*(f(a)+f(b))+sum(f(a+(b-a)/n*j),j,1,n-1))
  sim(f,a,b,n):=(b-a)/n*(1/6*(f(a)+f(b))+1/3*sum(f(a+(b-a)/n*j),j,1,n-1)+2/3*sum(f(a+(b-a)/n*(j+1/2)),j,0,n-1))
  puis par exemple tester avec rect(x->1/x,1.,2.,100); trap(x->1/x,1.,2.,100); sim(x->1/x,1.,2.,100) et comparer à ln(2.) Les commandes d'intégration numérique de Xcas sont gaussquad, romberg (appelée par evalf(Int())) on utilise d'abord une méthode adaptative avec une quadrature gaussienne à 15 points (d'ordre 29, ou 30 selon la définition de Hairer), ou la méthode des trapèzes accélérée par l'algorithme de Richardson-Romberg.
• Méthode de Monte-Carlo
  En dimension 1, voir la session example du menu Aide,Exemples,proba ou ici.
  Si f est la fonction a integrer avec n arguments sur [0,1]^n, par exemple pour estimer un volume f(x,y,z):=x^2+y^2+z^2<1; n:=3
  alors N:=1000; F:=evalf(seq(f(op(randvector(n,0..1))),j,1,N));
  crée un echantillon de N images par f de points aleatoires. Il suffit ensuite de taper
  m:=mean(F); s:=stddev(F)/sqrt(N)
  pour avoir une estimation de l'integrale et de l'ecart-type ([m-2s,m+2s] est alors un intervalle de confiance à 95% pour le volume pour N assez grand ce qui est le cas ici).
  On peut visualiser la convergence vers l'intégrale en tracant l'histogramme de plusieurs évaluations, par exemple 300 (on trace des classes commençant à 0.47 et de largeur 0.01). Ici la valeur est pi/6, et l'écart type théorique est sqrt(pi/6*(1-pi/6))/sqrt(N).
  E:=seq(mean(evalf(seq(f(op(randvector(n,0..1))),j,1,N))),k,1,300);
  histogram(E,0.47,0.01); plot(normald(pi/6,sqrt(pi/6*(1-pi/6))/sqrt(N),x),x=0.4..0.6)

Approximation de fonctions numériques

• Interpolation de Lagrange
  lagrange renvoie le polynome interpolateur de Lagrange, il est écrit sous forme "à la Horner" tel qu'obtenu par l'algorithme des différences diviséees, permettant une évaluation efficace en 3n opérations. Une session Xcas illustrant l'erreur d'interpolation pour des points equirepartis sur -10..10 (menu Aide, Exemples, analyse, lagrange_err). Une autre session illustrant la constante de Lebesgue en des points equirepartis ou de Tchebychef.

Equations différentielles ordinaires

Aspects numériques du problème de Cauchy: méthode d’Euler explicite, consistance, stabilité, convergence, ordre.

• Equations différentielles ordinaires (EDO)
  La fonction desolve permet de résoudre exactement certaines EDO scalaires (c'est assez rare, comme pour trouver une primitive, mais ca peut servir à tester des méthodes numériques). Pour les systémes différentiels à coefficients constants, on peut utiliser la transformation de Laplace directe et inverse (laplace et invlaplace).
  La commande odesolve permet de résoudre numériquement des EDO (scalaires ou vectorielles). Elle utilise une méthode adaptative (Prince-Dormand) qui estime l'erreur en comparant deux méthodes d'ordre différent et adapte le pas en conséquence. On peut lui faire renvoyer les points intermédiaires avec l'option curve pour pouvoir faire soi-meme un tracé, par exemple odesolve(sin(t*y),[t,y],[0,1],2,curve).
  La commande plotode permet de tracer une solution, dans le plan pour une équation scalaire. Elle se fait par défaut l'espace pour un système en dimension 2, on peut spécifier l'option plan pour ne pas voir la dépendance en temps, par exemple pour représenter dans l'espace des phases un système ne dépendant pas du temps.
• Précision du schéma numérique d’Euler explicite à pas constant.
  Cf. par exemple Demailly. La session Aide, exemples, analyse, euler_ode donne un programme simple de la méthode d'Euler explicite (et implicite, cette dernière n'est au programme que de l'option B).
• Espace de phases. Étude qualitative. Stabilité des points critiques.
  La commande plotfield permet de tracer le champ des tangentes. En ouvrant un niveau de géométrie, l'assistant Champ des tangentes du menu Graphe permet facilement d'obtenir le champ des tangentes d'un systéme autonome, on peut alors cliquer sur la figure pour faire tracer la courbe intégrale passant par le point cliqué (voir aussi plotode(.,plan) ci-dessus pour la représentation d'une solution).
  On peut déterminer les points critiques d'un système différentiel Y'=f(Y) en résolvant f(Y)=0, ceci peut se faire exactement si f est polynomiale (avec solve) ou de manière approchée sinon (fsolve). La stabilité des points critiques dépend alors du signe de la partie réelle des valeurs propres de F:=subst(diff(f,variables),variables=Y_critique) que l'on peut déterminer avec eigenvalues(evalf(F)) (attention, diff(f,variables) renvoie la transposée de la matrice jacobienne, mais cela ne change pas les valeurs propres).
  Voir aussi Exemple, analyse, ode.
• Aspects numériques du problème de Cauchy. Méthodes d’Euler explicite et implicite : consistance, stabilité, convergence, ordre.
  Option B: Utilisation de la méthode de Runge-Kutta 4.
  Pour la théorie, cf. par exemple Demailly ou/et Hairer. Un programme simple illustrant Euler explicite et implicite se trouve dans Exemple, analyse, euler_ode.
  Un exemple de programmes Xcas d'Euler explicite et de Runge-Kutta pour les proies-prédateurs par Y. Duron et K. Tribut session Xcas, explications.

Transformée de Fourier

Transformée de Fourier discrète sur un groupe abélien fini. Transformée de Fourier rapide. La commande fft calcule une transformée de Fourier discrète, ifft calcule l'inverse. Pour un calcul approché sur C, on passe en argument une liste des nombres.
Exemple
v:=randvector(2^14,uniform,0,1):; w:=fft(v):; maxnorm(ifft(w)-v);
Pour un calcul exact sur Z/pZ, on passe en argument une liste de taille n d'entiers compris entre 0 et p-1, un entier a racine primitive n-ieme de 2 modulo p et p.
Exemple avec p=35969
p:=35969; n:=2^7; a:=22798;
v:=randvector(n,p):;
powmod(a,n,p); powmod(a,n/2,p);
w:=fft(v,a,p):;
ifft(w,a,p)-v;

---

Option A (probabilités)

Remarques préliminaires :

• si vos données sont exactes, Xcas utilisera des algorithmes de calcul formel lorsque c'est possible et non des algorithmes numériques. Ce n'est pas toujours le plus judicieux, en particulier pour la rapidité des simulations. Pour eviter ce problème, vous pouvez configurer Xcas en mode approx (menu Cfg, configuration du Cas, cocher approx) puis sauvegarder la configuration. Si vous voulez aussi faire des calculs exacts, ouvrez un autre onglet et configurez-y Xcas en mode exact.
• le menu Outils, Proba contient la plupart des instructions nécessaires. Les instructions graphiques se trouvent dans le menu Graphe, Proba. D'autres instructions utiles sont dans le menu Prg, Liste.
• le menu Xcas, Aide, Exemple, proba contient une dizaine de sessions montrant Xcas en action sur des problèmes du niveau de la Terminale S à la préparation à l'agrégation.

Probabilités discrètes: tirages uniformes, échantillons

La fonction rand permet de générer un entier ou réel (pseudos)-aléatoires selon la loi uniforme. La fonction ranm permet de générer une matrice d'entiers ou réels aléatoires selon plusieurs lois dont la loi uniforme,

• rand(n) renvoie un entier aléatoire entre 0 et n-1.
  ranm(l,c,n) renvoie une matrice d'entiers aléatoires entre 0 et n-1.
  floor(ranm(l,c,uniform,a,b)) renvoie une matrice d'entiers aléatoires entre a et b-1.
• rand(a,b) renvoie un réel aléatoire entre a et b.
  ranm(l,c,uniform,a,b) renvoie une matrice de réels aléatoire entre a et b.
• on peut utiliser la fonction seq pour générer une séquence de nombres aléatoires (simulation d'un échantillon) ; par exemple seq(rand(0,1),k,1,100) génère 100 réels aléatoires entre 0 et 1 (la variable muette k n'est pas utilisée). Pour de gros échantillons, il est plus rapide d'utiliser ranv avec les bons paramètres.
• On peut aussi générer des nombres selon des lois non uniformes (par exemple, loi normale avec randnorm, loi exponentielle avec randexp, ...) voir le paragraphe Distributions pour l'option A.

Chaînes de Markov

• On peut créer de petites matrices de transition à directement en ligne de commande, ou en utilisant le tableur de Xcas (menu Tableur, nouveau tableur) en donnant un nom de variable au tableur.
• randmarkov permet de créer une matrice de transition aléatoire d'une chaine de Markov dont on précise le nombre de composantes fortement connexes du graphe. Le premier argument est une liste d'entiers qui sont les cardinaux des composantes fortements connexes (états récurrents positifs), le deuxiè argument est un entier qui indique le nombre d'états transients. Par exemple M:=randmarkov([2,3],4), les états 0 et 1 forment une composante fortement connexe (cardinal 2), les états 2, 3 et 4 forment une composante fortement connexe (cardinal 3), et les états 5 à 8 sont transients.
• randmarkov(M,i,n) permet aussi de simuler une chaine de Markov si on lui passe en premier argument la matrice de transition, en deuxième argument l'é initial i (numéroté à partir de 0) et en troisième argument le nombre d'étapes. On peut donner une liste d'états pour i.
• markov(M) détermine pour une matrice de transition de chaine de Markov ses éléments propres: composantes fortement connexes récurrentes positives et probabilités; invariantes associées, états transients, et probabilité de terminer dans une des composantes fortement connexe récurrente selon le point de départ.
• La commande plotproba() permet d'afficher le graphe d'une petite matrice de transition.
• Voir un exemple simple dans le menu Aide, exemples, demo, graphe_proba et l'exemple des urnes d'Ehrenfest dans Aide, exemples, proba.

Distributions préprogrammées.

Les distributions à support continu ont leur noms terminant par d uniformd, normald, exponentiald, chisquared, studentd, fisherd, cauchyd, weibulld, contrairement aux distributions à support discret binomial, negbinomial, poisson, geometric.
Les fonctions de répartition (en anglais cumulated distribution function ou distributions cumulées) s'obtiennent avec le suffixe _cdf, leurs inverses avec le suffixe _icdf. Les paramètres se mettent en premier, puis la variable.
Certaines commandes de Xcas reconnaissent ces distributions, par exemple les générateurs de nombres aléatoires (voir ci-dessous), la commande plot pour représenter graphiquement une distribution (graphe ou histogramme selon la loi), plot_cdf pour représenter graphiquement la distribution cumulée, pour représenter l'inverse de la fonction de répartition, on peut utiliser plot et la fonction de suffixe _icdf pour les lois continues, ou tout simplement prendre la symétrique par rapport à la 1ère bissectrice, par exemple
symetrie(droite(y=x),plot_cdf(binomial,10,.4))
Vous pouvez bien sur étendre ces distributions avec d'autres lois, mais elles ne seront pas reconnues par plot_cdf, ranv/ranm ou les tests d'adéquation. Vous devrez alors compléter, par exemple pour la génération de valeurs distribuées selon cette loi, vous pouvez utiliser l'algorithme du rejet (voir par exemple la session Aide, Exemples, proba, rejet), ou si la loi est à densité et que son intégrale peut se calculer à la main ou avec Xcas calculer la fonction de répartition inverse (éventuellement en utilisant la fonction fsolve).

Simulation

• Pour simuler des échantillons distribués selon une loi donnée préprogrammée, on utilise la commande ranv pour un vecteur ou ranm pour une matrice, on donne la ou les dimensions, puis le nom de la distribution d comme densité), puis les paramètres de la distribution. Par exemple M:=ranm(500,1000,binomial,100,.4) crée une matrice de un demi million d'entiers entre 0 et 100 distribué selon la loi binomiale de paramètres n=100 et p=0.4, ce qui permettra d'effectuer par exemple 500 simulations, chaque simulation est un échantillon de 1000 valeurs stockée dans une ligne de la matrice M.
• Pour faire de la simulation, il est souvent nécessaire de travailler sur de grands vecteurs ou de grandes matrices. Pour profiter de la vitesse des instructions programmées (qui sont compilées), il peut être nécessaire de stocker les données dans une matrice et d'utiliser des instructions travaillant directement dessus alors qu'il serait plus naturel de faire une boucle sur des éléments d'une liste. Par exemple, utiliser les instructions .+ .- .* ./ .^ opérant élément par élément, ou des fonctions de liste (sort, cumsum, apply, count, count_eq, count_inf, count_sup, find, ...)
• Si vous utilisez l'affectation par :=, Xcas effectue une copie du vecteur ou de la matrice, dont le temps est proportionnel à la taille du vecteur (ou au nombre de lignes de la matrice). Pour des raisons d'efficacité, vous pouvez remplacer := par l'affectation en place =< mais il faut prendre quelques précautions, comme par exemple initialiser la matrice avec une formule (seq) ou par copie avec copy.

Un mot sur les algorithmes utilisés par Xcas pour générer des échantillons selon une loi. On utilise d'abord un générateur entier, le Tiny Mersenne Twister (127 bit internal state, de Mutsuo Saito (Hiroshima University) et Makoto Matsumoto (The University of Tokyo)). On en déduit facilement un générateur d'entiers selon la loi uniforme sur un intervalle. Puis un générateur de flottants selon la loi uniforme. Pour les autres lois

• pour la loi exponentielle de paramètre lambda, on renvoie -ln(1-u)/lambda ou u est un flottant entre 0 et 1. Pour la loi géométrique, on arrondit à l'entier supérieur.
• pour la loi normale sqrt(-2*ln(u))*cos(2*pi*d) où u, d sont deux flottants selon la loi uniforme dans ]0,1[.
• pour la loi binomiale, pour de petits échantillons on utilise binomial_icdf(u) avec u flottant selon la loi uniforme dans ]0,1[. Pour de grands échantillons on construit la table des valeurs de binomial_cdf, et on cherche la position de u par dichotomie.
• pour la loi de Poisson de paramètre lambda, on fait comme pour la loi binomiale en se restreignant aux entiers inférieurs à 2*lambda+53.
• pour la loi du Chi2 à k degrés de liberté, on fait la somme de k carrés de réels selon la loi normale
• pour la loi de Student, on fait le quotient d'un réel selon la loi normale par la racine carrée d'un réel selon la loi du Chi2.
• pour la loi de Fisher, on fait le quotient de deux Chi2
• sinon on utilise la distribution cumulée inverse (ce qui est notablement plus lent)

Représentations graphiques

Pour représenter graphiquement les distributions préprogrammées et leurs fonctions de répartition (et inverses) voir ci-dessus.
Le menu Graphe, Proba contient plusieurs instructions de représentation graphique: histogram (données rangées par classes), diagramme_batons, plotlist, moustache statistiques 1-d, scatterplot, polygonplot, polygonscatterplot statistiques 2-d ainsi que tous les graphes de régression linear_regression_plot, exponential_regression_plot .... On peut aussi citer plot qui permet de tracer des graphes de fonction.

Tests

Xcas propose 4 tests préprogrammés (nom de la loi suivi du suffixe t):

• les tests d'égalité (hypothèse nulle) de 2 moyennes suivant une loi normale normalt et de Student studentt. On donne en premier argument soit une liste contenant la moyenne et le nombre de données dont elle est issue, soit une liste de données, en deuxième argument on donne la moyenne de la distribution de référence ou une deuxième liste de donnée, on peut spécifier de manière optionnelle en 3ème argument l'écart type de la distribution de référence, on donne ensuite une hypothèse alternative parmi 3 '!='différent ou '<' inférieur ou '>' supérieur et on peut terminer par un dernier argument qui est le seuil de rejet de l'hypothèse nulle, par défaut 0.05 (si la probabilité d'observer les 2 moyennes en supposant qu'elles suivent la même loi -normale ou de Student - est inférieure au seuil, alors le test renvoie 0 pour faux).
• le test d'adéquation du Chi2 chisquaret entre 2 distributions. L'hypothèse nulle est l'adéquation, l'alternative est la non adéquation. Ce test se présente sous plusieurs formes
  • Adéquation multinomiale
    si le deuxième argument est une liste de probabilités, le premier argument est alors une liste d'entiers, qui sont des effectifs (même longueur de listes) ou des données (numérotées à partir de 0) d'un échantillon,
  • Adéquation de deux échantillons
    on donne deux listes d'effectifs des classes des deux échantillons
  • Adéquation à une distribution
    le premier argument est la liste de données de l'échantillon, le deuxième une loi suivie de ses paramètres.
  On peut donner en dernier argument un seuil (le seuil par défaut est 0.05). Le test renvoie 1 (vrai, on ne peut rejeter l'adéquation au seuil donné) ou 0 (faux, on rejete l'adéquation).
• Le test d'adéquation de Kolmogorov-Smirnov kolmogorovt à une distribution continue. On donne en premier argument la liste de données de l'échantillon, en deuxième argument soit la distribution (dont le nom doit terminer par d puisque ce doit être une densité), soit la liste de données d'un autre échantillon. L'hypothèse nulle est l'adéquation entre les 2 distributions, l'hypothèse alternative (non spécifiée) est la non adéquation. Le test renvoie une liste de 6 éléments, 3 couples de chaines descriptives et de valeurs, le premier couple D est la valeur brute de la statistique (donc le maximum de l'écart entre les fonctions de distribution cumulées), le second couple vaut K=D*sqrt(n) ou K=D*sqrt(n1*n2/(n1+n2)) selon qu'il s'agit d'une adéquation à une loi ou entre 2 échantillons (à comparer à 1.36 pour un seuil de rejet de l'hypothèse d'adéquation au seuil de 0.05), le troisième couple est 1-kolmogorovd(K), plus cette valeur est proche de 1, plus l'adéquation est de bonne qualité.
  Voir Aide, Exemples, proba, kolmogorov.

---

Option B (calcul scientifique)

Remarques générales :

• Commencez par consulter les points relatifs au Chapitre 13
• si vos données sont exactes, Xcas utilisera des algorithmes de calcul formel et non numériques. Essayez par exemple A:=ranm(3,3); lu(A); lu(evalf(A)).
  Ceci n'est souvent pas judicieux pour faire du calcul scientifique, les calculs exacts étant beaucoup plus longs (par exemple pivot de Gauss) ou infaisables (par exemple réduction d'endomorphimes, calcul d'intégrale définie). Mais un calcul exact peut servir à montrer un problème de stabilité numérique, par exemple inverse d'une matrice de Hilbert de taille 20
  H:=hilbert(20); I:=inv(H); J:=inv(evalf(H)); COND(H);
  ou quadrature pour une intégrale convergente
  int(sqrt(x),x,0,1); romberg(sqrt(x),x,0,1)
  D'autre part, le calcul formel permet de programmer certains algorithmes nécessitant une dérivée comme la méthode de Newton.
  Il peut alors etre intéressant d'avoir une session configuréee en mode approché et une autre en mode exact.
• Le menu Aide, Exemples, analyse contient plusieurs sessions illustrant des notions au programme de l'option B. Le menu Aide, Manuels, Programmation contient aussi des exemples de programmes pertinents pour l'option B (pivot de Gauss, méthodes itératives, intégration...).
• Pour les experts: les fonctions d'algèbre linéaire numérique de Xcas utilisent la librarie LAPACK (implémentation ATLAS), mais seulement au-delà d'une taille seuil (par défaut 400) pour certaines commandes (pivot de Gauss, réduction d'endomorphismes). On peut modifier ce seuil par la commande export GIAC_LAPACK=valeur dans un terminal avant de lancer xcas &. En-deça de ce seuil c'est le code propre de giac qui est utilisé (car il est plus rapide). Pour le déterminant, c'est toujours le code propre de giac qui est exécuté, LAPACK ne fournissant pas de fonction à cet effet.
  Les méthodes de résolution numérique d'équations (en une ou plusieurs variables, et d'équation différentielle ordinaire) de Xcas utilisent aussi la GSL (Gnu Scientific Library).

Références:

• Analyse numérique et équations différentielles, J.P. Demailly
• Introduction à l'analyse numérique matricielle et à l'optimisation, P. Ciarlet.
• Polys d'analyse numérique d'Ernst Hairer disponibles gratuitement. En livre : Ernst Hairer, Syvert Paul Nørsett, Gerhard Wanner Solving Ordinary Differential Equations I. Nonstiff Problems.
• Matrix computations, G.H. Golub and C.F. Van Loan
• Une partie du programme de l'option B est couverte par le cours de méthodes numériques (niveau L3, en construction) et le cours de M. Eisermann (niveau L2+).

EDP

Notions élémentaires sur les équations aux dérivées partielles classiques en dimension un. Équation de transport (advection) linéaire : méthode des caractéristiques. Équations des ondes et de la chaleur : résolution par transformée de Fourier et séparation des variables. Aspects qualitatifs élémentaires. Équations elliptiques. Exemples de discrétisation de problèmes aux limites en dimension un par la méthode des différences finies : notions de consistance, stabilité, convergence, ordre
Un exemple d'illustration Xcas du texte du jury À la découverte de la dynamique des gaz

Optimisation et approximation

Extremums des fonctions réelles de n variables réelles
La fonction fMin (ou fMax) permet dans certains cas de localiser des extremas de fonctions de plusieurs variables sous contraintes, en utilisant l'algorithme Cobyla (Constrained Optimization BY Linear Approximation). La syntaxe est
fMin(func,[contraintes],[variables],[guess],[eps],[maxiter])
Les contraintes sont des expressions des variables qui doivent renvoyer une valeur positive, ainsi une condition x<1 sera traduite en 1-x, par exemple
fMax(x*y*z,[x,y,z,1-x-y-z],[x,y,z],[1/4,1/3,1/4])
va maximiser xyz sous les contraintes x>0, y>0, z>0, x+y+z<1 avec comme valeur initiale [1/4,1/3,1/4].

multiplicateurs de Lagrange
Si on optimise f(x) sous les contraintes g_i(x)=0, cela revient à optimiser L(x,lamba_i)=f(x)+sum(lambda_i*g_i(x)) par rapport à x et aux lambda_i. Un exemple de résolution exacte triangle d'aire maximale (inclus dans Aide, Exemples, analyse, mult_lagr)

Mise en œuvre de l’algorithme de gradient à pas constant.
Voir par exemple cette session Xcas, menu Aide, Exemples, analyse, grad_const

Méthode des moindres carrés et applications
Voir ici le cas sans contraintes.

---

Option C (algèbre et calcul formel)

Pour prendre en main Xcas, vous pouvez suivre ce TP agreg 1.
Voici, point par point du programme, quelques informations pour l'usage de Xcas relativement à chaque point du programme de l'option C. Quelques remarques préliminaires:

• Vous pouvez consulter sur le forum de Xcas un résumé des cours de la préparation option C de Grenoble ces 3 dernières annéees, ce qui devrait vous aider si vous ne bénéficiez pas de cours pour l'option C (par exemple si vous êtes certifiés ou inscrits à une préparation ne préparant pas l'option C). Vous pouvez aussi consulter les page de Frédéric Han, de Pascal Molin, qui contiennent des ressources pour préparer l'oral option C.
• Notez que vous pouvez utiliser PARI dans Xcas ce qui peut être utile en particulier pour accéder à des fonctions arithmétiques avancées. Pour cela tapez la commande pari(). Les commandes de PARI sont alors utilisables soit par leur nom PARI, soit en leur ajoutant le préfixe pari_ lorsque le nom existe déjà dans Xcas (par exemple weber(1+i) et pari_gcd(x^2-1,x^3-1)). Une aide succinte sur les commandes de pari est accessible par ?pari_nom_de_commande_pari. Le manuel plus complet de PARI se consulte depuis le menu Aide->Manuels->PARI-GP.
  On peut aussi utiliser les commandes de PARI sans les exporter, en tapant la commande pari( puis le nom de commande pari en chaine de caractères, puis les arguments de la commande pari, par exemple pari("weber",1+i).
• Le menu Aide, Exemples, sous-menus arit, crypto et geometrie contient des sessions illustrant des points au programme de l'option C. Le menu Aide, Manuel, algorithmes, contient des notes de cours de calcul formel dont l'intersection avec le programme de l'option C est importante. Le menu Aide, Manuel, programmation contient des programmes d'arithmétiques et d'algèbre.

C.a: représentations

Représentation et manipulation des entiers longs, flottants multiprécision, nombres complexes, polynomes, Z/nZ. Addition, multiplication, division. .

• Entiers
  Les entiers longs utilisent la librairie GMP 4, les algorithmes utilisés y sont documentés (cf. aussi la doc en ligne gmp*info en tapant info gmp en ligne de commande ou Ctrl-H I dans emacs puis chercher gmp, puis aller dans Algorithms). Par exemple, diverses méthodes de multiplication rapide sont implémentéees (Karatsuba, Toom3, FFT).
• Flottants
  La base de représentation des flottants utilisée par Xcas est 2 (et non 10 comme maple, c'est d'ailleurs pour cette raison que les calculs en flottants sont relativements lents en maple, sauf si on utilise evalhf qui force l'utilisation de l'arithmétique flottante du processeur). On peut le vérifier en calculant 0.5-5*0.1. Le programme suivant, tiré de V. Lefèvre et P.Zimmermann, permet de déterminer la base utilisée pour la représentation des flottants (fonctionne avec Xcas et maple)
  Base:=proc()
  local A,B;
  A:=1.0; B:=1.0;
  while evalf(evalf(A+1.0)-A)-1.0=0.0 do A:=2*A; od;
  while evalf(evalf(A+B)-A)-B<>0 do B:=B+1; od;
  B;
  end;
  Si Digits est plus petit ou egal à 14, les objets nouvellement créés utilisent l'arithmétique hardware "double" du standard IEEE en base 2, 52+1 bits de mantisse, 11 bits d'exposant, 1 bit de signe, mais pour le stockage les 5 bits de poids faible de la mantisse sont ramenés à 0, il n'y a donc que 48 bits de mantisse vraiment utilisables, Digits controle seulement l'affichage des flottants.
  Sinon, ce sont des flottants multiprécision utilisant la librairie MPFR. Digits qui est un nombre de chiffres significatifs en base 10 est alors arrondi en un nombre de bits en base 2. Certains calculs numériques par exemple l'algèbre linéaire numérique, convertissent les flottants longs en flottants hardware (avec évidemment des pertes de précision).
  Référence pour les erreurs : par exemple le livre Analyse numérique et équations différentielles de Demailly
  Les versions à jour de Xcas permettent aussi de faire de l'arithmétique d'intervalles, c'est-à-dire de certifier des bornes pour des calculs en flottants. Par exemple a:=1.023?; a^10 ou a:=[1.1111..1.1112]; a^10
• Polynomes
  Voir aussi polynomes 1-d et polynomes n-d.
  • On peut manipuler les polynomes sous forme symbolique (comme dans maple, cf ici), mais aussi directement en représentation dense à une variable ou creuse à plusieurs variables.
  • Polynomes à 1 variable
    • la représentation est une liste des coefficients donnés par ordre décroissant, avec le préfixe poly1[ par exemple poly1[1,0,3] représente le polynome x^2+3 (on peut omettre poly1[ s'il n'y a pas de risque de confusion). Les instructions arithmétiques de base s'appliquent sur les listes représentant des polynomes, par exemple rem([1,3,4,2],[1,1,1]) ou poly1[1,2,3]*poly1[1,1].
    • On passe de la représentation symbolique à la représentation liste et inversement avec les fonctions symb2poly et poly2symb en mettant comme second argument la variable.
    • La multiplication des polynomes en une variable est implémentée par Karatsuba lorsque les arguments sont de degré supérieur à 17. Exemples: multiplication par Karatsuba et par FFT sur C ou par FFT sur Z/nZ (menu Aide, Exemples, arit)
  • Polynome en plusieurs variables
    • On peut utiliser une représentation récursive à partir des polynomes denses en une variable ci-dessus, mais ce type est mal adapté s'il y a beaucoup de coefficients nuls. Xcas utilise une représentation creuse, une liste de monomes (classés par ordre lexicographique) dont on stocke le coefficient et un vecteur d'indices entiers (correspondant aux puissances des variables de ce monome).
    • Les fonctions de conversion sont symb2poly et poly2symb avec comme second argument la liste de variables.
    • Le produit de polynomes n-d est implementé en utilisant des tables de hachage pour regrouper dans la somme les termes de meme degré et lorsque cela est possible le vecteur d'indices entiers est compressé en un unique entier hardware (long ou long long, cf. les fichiers header /usr/share/giac/poly.h et monomial.h pour les programmeurs C++ intéressés). Cf. R. Fateman pour une discussion sur les produits de polynomes à plusieurs variables.
• Z/nZ
  
  • Xcas utilise les entiers modulo un "petit" nombre premier dans de très nombreux algorithmes (par exemple le PGCD de polynomes par méthode modulaire, déterminant de matrice à coefficients entiers, factorisation de polynomes ...).
  • En mode Xcas, on utilise le signe % (comme en C) pour indiquer un nombre de Z/nZ, par exemple 3 % 5. Pour retrouver un entier x à partir de son représentant modulo n y := x % n, en mode Xcas, on tape y % 0.
    En mode maple, on utilise la même syntaxe qu'en maple (forme inerte de l'instruction suivie de mod).
  • Xcas utilise la représentation symétrique des entiers modulo un nombre premier (on renvoie x % n avec x compris entre -n/2 et n/2), qui est la plus utile lorsqu'on veut reconstruire un entier dont on connait une majoration en valeur absolue à partir de son représentant modulo n (pour n assez grand).
• Vecteurs, listes et matrices
  Xcas ne fait pas de différence entre listes et vecteurs, les matrices sont des listes de listes de même taille. L'affectation dans une liste, vecteur ou matrice se fait par création d'une copie de l'objet si on utilise := pour l'affectation, ou par référence si on utilise =< (à utiliser si vous travaillez sur de grosses matrices modifiables en place).

C.b: algorithmes

Algorithmes algébriques élémentaires. Exponentiation (n -> a^n, pour n entier), algorithme d'Euclide étendu. Coût de ces algorithmes. Test de primalité de Fermat. Application au chiffrement RSA

• Puissance modulaire rapide
  Dans tous les modes, on peut utiliser powmod(a,b,n). En mode maple, on peut utiliser la syntaxe maple a &^ b mod n.
  Le manuel de programmation donne des versions de l'algorithme de puissance rapide comparé avec l'algorithme naif.
• Algorithme d'Euclide étendu
  (dit aussi algorithme de Bézout). La version pour les entiers est iegcd ou iabcuv, pour les polynomes egcd et abcuv.
  Le demi algorithme d'Euclide étendu (permettant par exemple de reconstruire une fraction par son représentant modulo un entier), est codé dans la fonction fracmod (synonyme de iratrecon). La version polynomiale du demi algorithme d'Euclide est utilisée pour les approximants de Padé (fonction pade).
  Le manuel de programmation donne des versions itératives et récursives de l'algorithme d'Eculide étendu.
• Nombres premiers
  Le manuel de programmation donne des exemples de code de tests de pseudo-primalité (Rabin et Miller-Rabin).
  Les fonctions isprime et is_prime de Xcas effectuent, par l'intermédiaire de GP-PARI, un test de primalité et non un test de pseudo-primalité (instruction is_pseudoprime) mais Xcas ne renvoie pas de certificat de primalité (contrairement à ce qui est indiqué dans la documentation), pour en obtenir un, vous pouvez utiliser la fonction pari("isprime",entier,0 ou 1 ou 2) avec en 2ème argument l'entier à tester et en 3ème argument optionnel 0, 1 ou 2 (voir la documentation de PARI). Par exemple
  p:=nextprime(3*10^14)
  calcule le premier pseudo-premier supérieur à 3.10^14, puis
  pari("isprime",p,1)
  calcule un certificat de primalité de Selfridge-Pocklington-Lehmer (Cohen chapitre 8.3 ou Knuth section 4.5), voir aussi cette session. Si on remplace 1 par 2, on effectue le test APRCL (Adleman-Pomerance-Rumely-Cohen-Lenstra). Voici aussi un exemple de programme montrant la méthode de Pollard.
• Factorisation d'entiers
  La factorisation des entiers est faite dans Xcas en utilisant la méthode de Pollard-rho, puis le crible quadratique (multi-polynomial quadratic sieve), par exemple pour ifactor(2^128+1).
  Vous pouvez aussi faire appel à GP/PARI (par exemple pour utiliser les courbes elliptiques pour factoriser), par la commande pari(); pari_factor(entier);. (Voir le manuel de PARI/GP depuis le menu Aide->Manuels->PARI-GP pour des détails sur les algorithmes utilisés par PARI, ainsi que Cohen ou Knuth).
  Cette session illustre la méthode des fractions continues (qui n'est plus guère utilisée, le crible quadratique étant plus efficace).
• RSA
  Les fonctions asc et char permettent de convertir une chaine de caractères en une liste de nombres (le code ASCII des caractères) et réciproquement (comme convert avec l'option bytes en maple). Par ailleurs, le menu Aide, Exemples->crypto->rsa.xws donne un exemple de programme de codage RSA et le manuel de programmation fournit de la documentation sur RSA. On peut illustrer graphiquement le choix des valeurs de clefs dans cette session.
  Quelques autres exemples (par Robert Rolland) échange de clefs de Diffie-Hellman, signature ombrée

C.c: Corps finis non premiers.

Représentation des éléments d’un corps fini. Calcul effectif : addition, multiplication, inversion. Coût de ces opérations.

• Pour représenter les corps finis non premiers, Xcas utilise la représentation polynomiale (additive) modulo un polynome irréductible, primitif (s'il est choisi par la machine)
• Pour créer un corps fini non premier de cardinal p^n, on tape la commande GF(p,n) ou GF(p^n) (ou GF(p,n,'g') si on veut specifier le nom du générateur qui doit etre une variable non assignée, ici g). Xcas cherche alors des noms de variables libres pour y stocker le corps (par défaut K) et un générateur du corps (par défaut g), il détermine un polynome primitif irréductible pour représenter le corps fini, les éléments du corps sont les restes de division euclidienne de polynomes (à coefficients dans Z/pZ) par le polynome irréductible (représentation additive).
  On peut alors créer un élément quelconque du corps en donnant un polynome à coefficients entiers en fonction du générateur, la valeur renvoyée est normalisée par division par le polynome irréductible (primitif) qui définit la représentation du corps.
  Par exemple GF(2,8) crée le corps à 256 éléments, on peut ensuite appliquer toutes les opérations arithmétiques sur le générateur g, par exemple calculer g^255 pour vérifier qu'il vaut 1, ou g^(255/3), g^(255/5) et g^(255/17) qui ne valent pas 1 (on vérifie ainsi que les puissances de g engendrent bien tout le corps).
  Les opérations arithmétiques sur un corps fini se font comme si les coefficients étaient rationnels (+ - * / sqrt inv, gcd, factor, egcd, ...).
  On peut créer des polynomes à coefficients alétoires [respectivement des matrices] avec randpoly(degre,variable,generateur) [resp. ranm(lignes,colonnes,generateur)].
• Pour vérifier qu'un polynome est irréductible modulo un premier, on peut utiliser en mode Xcas factor((x^8+x^6+x^5+x^4+1) % 2). ou en mode maple, Factor((x^8+x^6+x^5+x^4+1)) mod 2, Cette session Xcas explique comment construire un polynome irréductible primitif (menu Exemple, arit, makegf).
• Pour travailler avec des polynomes à coefficients dans un corps fini, vous pouvez utiliser la représentation symbolique habituelle ou la représentation dense expliquée ci-dessus. Par exemple rem(g*x^3+g^5*x^2+g*x,g*x+g^2) ou rem([g,g^5,g,0],[g,g^2]) calcule le reste d'un polynome de degré 3 par un polynome de degre 1 à coefficients dans le corps K (coefficients donnés par ordre décroissant dans le 2ème cas).

C.d: Matrices sur un corps.

Méthode du pivot de Gauss, décomposition LU. Calcul effectif du rang, du déterminant. Coût de ces calculs.
Les algorithmes de Gauss, de calcul du noyau, etc. sont explicités dans le manuel de programmation.

• Pivot de Gauss
  Xcas utilise par défaut l'algorithme de Gauss-Bareiss (dans rref, det, etc.). Les éléments de matrice sont transformés en fractions rationnelles polynomiales par rapport aux variables (étendues), les relations algébriques entre variables étendues sont ignorées (par exemple entre le cosinus et le sinus d'un angle, vous pouvez utiliser les fonctions de réécriture, en particulier tsimplify, pour écrire une matrice en fonctions de variables étendues algébriquement indépendantes). Le ppcm des dénominateurs est ensuite retiré ligne par ligne, puis la réduction a lieu (réduction de Gauss habituelle mais avec division par le pivot utilisé pour la réduction de la colonne précédent la colonne actuelle).
  L'option keep_pivot de rref n'effectue pas l'opération finale de division de la matrice réduite par le premier coefficient non nul de chaque ligne.
• Déterminant
  Par defaut, l'algorithme est p-adique/modulaire et probabiliste si les coefficients sont entiers (cf. infra), et Bareiss pour des coefficients polynomiaux.
  • L'option rational_det impose l'utilisation de l'algorithme de Gauss (et non Gauss-Bareiss) et n'effectue pas la transformation en fractions rationnelles (ce qui peut créer des problèmes de non reconnaissance de 0 si des variables interviennent).
  • L'option lagrange impose le calcul par interpolation.
  • L'option minor_det impose le calcul du déterminant par l'algorithme de développement selon les mineurs, par exemple det(A,minor_det) donnera des résultats bien plus rapides si A est une matrice creuse avec beaucoup de variables symboliques.

C.e: Codes correcteurs linéaires

Distance de Hamming, distance minimale d’un code linéaire Exemples de codes correcteurs linéaires: codes de répétition, codes de Hamming binaire.
La session codelin.xws (Aide, Exemples, crypto, codelin) illustre quelques aspects des codes linéaires. Le menu Aide, Exemples->crypto->reed_s.xws donne une session de calcul xcas illustrant les codes correcteurs de Reed-Solomon (rédigé pour le master 2 crypto de Grenoble). Pour les explications, cf. PDF (TeX). Cf. par exemple Demazure pour une introduction plus complète aux codes correcteurs.

C.f Polynomes 1-d

Évaluation (schéma de Horner), interpolation (Lagrange, différences finies). Coût de ces opérations. Localisation des racines dans R ou C: majoration en fonction des coefficients

• Évaluation
  La fonction horner de Xcas permet d'évaluer un polynome (symbolique ou liste par ordre décroissant des coefficients) par la méthode de Horner. Voir aussi la session horner.xws de Aide, Exemples->poly et le manuel de programmation.
• Interpolation
  La fonction lagrange (ou interp) calcule par la méthode des différences divisées le polynome d'interpolation de Lagrange (O(n^2) opérations sur un corps fini). Une session Xcas illustrant l'erreur d'interpolation pour des points equirepartis sur -10..10 (menu Aide, Exemples, analyse, lagrange_err). En calcul formel, l'interpolation est utilisée pour reconstruire des polynomes dont on connait le degré (donc pas d'erreur d'interpolation), par exemple polynome caracteristique d'une matrice, pgcd de polynomes à plusieurs variables, ... (voir un exemple dans le texte du jury sur le partage de secret).
  Références: la doc en ligne de Xcas (Manuel->Algorithmes de calcul formel), le livre de Demailly, sur le web, le chapitre 2 du cours d'Analyse numérique de Ernst Hairer
• Localisation de racines
  Les fonctions sturm et sturmab permettent de compter le nombre de racines réelles dans un intervalle ou complexes dans un rectangle de C. La fonction sturm commence par effectuer une factorisation sans racines multiples (sqrfree), puis calcule la suite des restes d'Euclide en utilisant l'algorithme du sous-résultant avec multiplication à chaque étape par un facteur pour tenir compte des signes.
  La fonction realroot(p) isole les racines réelles d'un polynome p à coefficients rationnels en renvoyant des intervalles ne contenant qu'une racine, par l'algorithme de Vincent-Akritas-Strzebonski. La méthode de base est la règle des signes de Descartes qui donne nombre de racines positives ≤ nombre de changements de signes des coefficients du polynome (et existence d'une racine au moins si ce nombre est impair). exemple avec Descartes.
  La fonction proot (et solve dans certains cas) permet de calculer numériquement les racines d'un polynome. Les racines sont calculées numériquement à partir des valeurs propres de la matrice companion du polynome (décomposition de Schur par l'algorithme de Francis) en précision double, puis si on est en multi-précision, elles sont affinées par la méthode de Newton.

C.g Polynomes n-d

Tout polynôme symétrique s’exprime en fonction des polynômes symétriques élémentaires. Résultants, élimination. pplications : résolution de systèmes polynomiaux, calcul de l’intersection de courbes algébriques planes, passage d’une paramétrisation à une équation implicite. Calcul effectif du résultant, coût de ce calcul.

• Polynômes symétriques
Comment verifier qu'un polynome est symetrique. Programme de calcul (manuel algorithme de Xcas) Applications(?): Identités de Newton, polynome caracteristique Recherche d'une extension algébrique contenant toutes les racines d'un polynome irreductible par resolution de systeme.
• Résultant
  La fonction resultant permet de calculer le résultant de 2 polynomes par rapport à une variable, en utilisant l'algorithme du sous-résultant. On peut aussi utiliser la fonction sylvester pour construire la matrice et en calculer le déterminant (ou passer sylvester en dernier argument de la fonction resultant pour forcer le calcul du résultant par calcul du déterminant de sa matrice de Sylvester).
  Les résultants trouvent vite leurs limites si on veut résoudre des systèmes polynomiaux par exemple de plus de 3 variables. La commande solve de Xcas utilise la représentation rationnelle univariée, dont l'outil de calcul principal est la recheche de bases d'ideaux polynomiaux dites bases de Groebner (hors programme), commande gbasis, ainsi que greduce qui joue un role équivalent à la division euclidienne en dimension 1.
• Intersection de courbes algébriques planes
  L'instruction implicitplot de Xcas permet de représenter une courbe ou une surface donnée par son équation cartésienne.
  Une session illustrant des cas où le nombre de points d' intersections de deux courbes algébriques est plus petit que le produit des degrés (menu Aide, Exemples, geometrie, intercourbe).

C.C Couts

Aucune formalisation d'un modèle de calcul n'est exigée.

• De nombreux algorithmes sont expliqués en détails dans le manuel de programmation de Xcas (menu Aide->Manuels->Programmation) et illustrés en langage xcas. La fonction time permet de calculer le temps d'exécution d'une fonction de Xcas, pour obtenir plus de précision, elle exécute plusieurs fois la même fonction lorsque le temps d'exécution est trop rapide et affiche alors le temps moyen d'exécution. Certains algorithmes de Xcas peuvent être exécutés en affichant des détails (mais qui peuvent être difficiles à interpréter), pour cela il faut aller dans la configuration du cas, et changer la valeur du champ debug. (Ceci correspond en maple à la commande infolevel[all]:=5; (ou 2, 3, 4) cf. aussi interface(verboseproc=2); suivi de eval(nom_de_procedure)).
• L'instruction time de Xcas permet de savoir le temps nécessaire à l'exécution d'une commande, il n'y a pas d'équivalent pour connaitre l'espace mémoire nécessaire à une instruction (on peut toutefois regarder l'espace mémoire utilisé par Xcas dans la zone d'état en haut de la session ou utiliser top depuis un terminal). Sous linux, time renvoie 2 valeurs, le temps processeur (CPU) et le temps réel (comme si on chronométrait), le temps réel est supérieur ou égal au temps CPU (sauf sur des machines multi-processeurs lorsque Xcas utilise des algorithmes utilisant le parallélisme).
  On peut illustrer graphiquement une complexité polynomiale en O(n^k) en prenant quelques valeurs de n, les logs des n et des temps correspondants et en effectuant une régression linéaire (instructions scatterplot, linear_regression_plot, ou directement avec n et les temps correspondants avec power_regression_plot). Par exemple pour le déterminant, l:=seq([log(evalf(n)),log(time(det(ranm(n,n)))[1])],n,200,500,30); scatterplot(l);linear_regression_plot(l)
• Pour générer des exemples aléatoires, on peut utiliser les fonctions dont le nom commencent par rand, taper rand puis la touche de tabulation. Pour générer des points aléatoires utiliser les commandes point2d et point3d avec en argument les noms des points aléatoires à créer.

Textes de modélisation option C

J'ai regroupé dans ce message quelques commentaires sur la majorité des textes de l'option C rendus public par le jury. A ne lire qu'après avoir cherché soi-meme (de toutes facons ces commentaires sont souvent incompréhensibles sinon, il ne s'agit absolument pas d'exemples d'exposés de modélisation). On trouvera en complément quelques textes proposés à la préparation à l'agrégation de Grenoble (option C) en 2006. D'autres textes pour vous exercer sont disponibles sur le serveur de l'agrégation (ici), et dans d'autres préparations, par exemple Bordeaux et Rennes, suivre ce lien. Au fur et à mesure, je pense ajouter des exemples de sessions Xcas illustrant certain de ces textes.

• Représentation des objets mathématiques et algorithmes: latex, pdf
• Algèbre linéaire sur les entiers: latex, pdf
• Cryptographie: latex, pdf
  Référence pour ce texte Gilles Zemor, Cours de Cryptographie
• PGCD: latex, pdf
• Approximation des fonctions: latex, pdf
• Résultant et applications: latex, pdf
• Localisation de racines d'un polynome: latex, pdf
• Session Xcas illustrant le texte sur les carrés magiques.
• Session Xcas calcul des polynomes du texte Construction explicite de surfaces algébriques dont la projection est imposée. Quelques exemples de surfaces algébriques du texte se projetant sur un carré, un triangle et un anneau.
• Session Xcas illustrant le texte sur les molecules a 6 atomes
• Session Xcas justifiant la formule arithmético-géométrique pour les intégrales elliptiques
• Session Xcas illustrant l'intersection de 2 courbes algébriques de degré 2 et 3.
• Correction du problème d'algèbre 2007, par R. De Graeve et B. Parisse, pdf, session Xcas, latex, figure 1, figure 2,

TP option C

Vous trouverez aussi des énoncés de TP ainsi que des corrections pour vous exercer à la manipulation de Xcas pour l'option C sur le site de Jussieu (F. Han), de Marseille (D. Kohel).

Liste des session Xcas

• Polynomes (texte 590) , surfaces (texte 590)
• Problème Algèbre 2007
• Fraction continues
• Codes linéaires
• Cyclohexane
• Codes de Reed-Solomon
• Carrés magiques
• Multiplication par FFT
• Multiplication polynomes
• Approximant de Padé
• Methode de Pollard
• Primalité
• Différences diviséees
• Erreur d'interpolation pour Lagrange
• systeme de Watt, alternative
• Intégrales elliptiques (moyenne arithmético-géométrique)
• partage de secret par interpolation (texte du jury 2009)
• modélisation wifi (texte jury 2015)
• Calcul du n-ieme nombre de Fibonacci méthode itérative en O(n^2) et méthode plus rapide avec les flottants multiprécision, pour réviser la puissance rapide les complexités.
• Générateur congruentiel de nombres pseudo-aléatoires.
• Exercice sur GF(7,5) : Trouver un polynome irreductible P de degre 5 sur Z/7Z. 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 donne x^7)
• Condition pour que 4 point soient cocyliques (exercice Géométrie et résultant du manuel Algorithmes de Xcas).

Quelques références option C

• A Computational Introduction to Number Theory and Algebra par Victor Shoup: existe en livre (payant) ou en téléchargement gratuit
• A Course in Computational Algebraic Number Theory, de Henri Cohen
• Modern Computer Algebra, par J. Von zur Gathen et J. Gerhard (site avec ajouts et errata)
• Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, version 0.5.1, March 2010
• The Art of Computer Programming, par D. Knuth, en particulier le volume semi-numerical algorithms et le volume searching and sorting
• Cours d'algèbre, Demazure
• Cours de calcul formel (2 tomes), Saux Picart et Rannou.
• Calcul formel: Systèmes et algorithmes de manipulations algébriques, par Davenport, Siret, Tournier,
• Algorithmes efficaces en calcul formel par A. Bostan, F. Chyzak, M. Giusti, R. Lebreton, G. Lecerf, B. Salvy, E. Schost
• Analyse numérique et équations différentielles, J.P. Demailly
• Calcul formel : mode d'emploi. Exemples en Maple, Philippe Dumas, Claude Gomez, Bruno Salvy, Paul Zimmermann.
• Le Frido
• Les manuels de l'aide en ligne, ainsi que les sources de Giac/Xcas dans les répertoires /usr/share/giac/src et /usr/include/giac

---

Si vous avez des suggestions d'ajout, vous pouvez les poster sur le forum ou me les envoyer à l'adresse bernard point parisse at univ tiret grenoble tiret alpes point fr.

(c) B. Parisse, 2007, 2022.
Si vous utilisez des données originales de cette page, je vous remercie de faire pointer un lien hypertexte vers cette page, afin que d'autres puissent la trouver plus facilement en utilisant un moteur de recherche.
Conditions d'utilisation:
La diffusion et l'utilisation des données de cette page est autorisée dans un but non commercial et vaut acceptation de ces conditions d'utilisation. Ces données sont fournies sans garantie aucune, le détenteur du copyright ne pourra en aucun cas être poursuivi pour quelque dommage que ce soit suite à l'utilisation des données ci-dessus, y compris s'il en a été averti.