Illustrations informatiques et algorithmes pour l’agrégation interne

Bernard.Parisse@ujf-grenoble.fr

2010, 2024

Avertissement, Ce document a été écrit d’une part à une période où l’algorithmique occupait une place nettement plus importante dans la liste des leçons/exercices, et d’autre part où Xcas n’avait pas été supprimé arbitrairement et sans préavis de la liste des logiciels utilisables à l’oral. Je l’ai un peu mis à jour, mais pas complètement.

Le rapport du jury 2022 indique que Xcas ne fait plus partie des logiciels installés pour les oraux. J’ai découvert cela avec consternation. J’ai essayé d’obtenir des explications, on m’a dit que les personnes en charge du parc informatique de l’oral trouvent l’installation de Xcas trop difficile (ça parait assez étonnant sachant que Giac/Xcas est un package standard des distributions Linux majeures) par rapport au nombre de candidats qui l’utilisent. J’ai bien sur proposé mon aide technique à l’installation, mais je n’ai pas reçu de réponse. J’ai même modifié la version en ligne de commande giac pour qu’on puisse lancer l’interface xcas en tapant giac puis xcas depuis Sagemaths, mais ce n’est pas cette version qui est disponible sur agregos.

Il reste possible de faire du calcul formel sans apprendre un logiciel dédié grâce à la fenêtre CAS de Geogebra (qui en interne utilise Giac/Xcas) mais il y a beaucoup moins de commandes, et la documentation online ne semble pas accesible pendant l’oral. Il est même possible d’utiliser une commande Xcas en la précédant de @ (cela peut servir en particulier pour l’arithmétique), par exemple @iegcd(15,25) pour calculer les coefficients de l’identité de Bézout pour 15 et 25. Le résultat est affiché dans la fenêtre graphique et est stocké dans la variable casOutput, visible dans la fenêtre Algèbre et utilisable pour effectuer d’autres calculs, par exemple on peut vérifier l’identité de Bézout en tapant casOutput[1]*15+casOutput[2]*25. Voici une petite liste de commandes (d’après mes connaissances imparfaites de Geogebra...), cf. le manuel:

J’ai contacté mes collègues de l’équipe de développement de Geogebra qui ont ajouté le 10 mai 2023 certaines commandes manquantes ci-dessus dans Geogebra :
ExtendedGCD( <Integer>,<Integer> ), ExtendedGCD( <Polynomial>, <Polynomial> ), ModularExponent( <Number>, <Number>, <Number>), CharacteristicPolynomial( <Matrix> ), MinimalPolynomial( <Matrix> ), LUDecomposition( <Matrix> ), QRDecomposition( <Matrix> )
mais il n’y a pour le moment pas eu de mise à jour de Geogebra dans agregos.

Il y a aussi pour les gens qui connaissent bien Xcas la possibilité d’utiliser giac, la version en ligne de commande de Xcas. Cette possibilité n’est pas garantie vu l’attitude du jury, mais elle fonctionne sur agregos 2023. Pour cela on ouvre Jupyter, puis Nouveau, puis Terminal, puis on tape la commande giac (ou icas). Si cela ne fonctionne pas, vous pouvez lancer sage puis la commande !giac. L’aide en ligne courte de Xcas est disponible en tapant ?nom_de_commande (si on connait approximativement le nom de commande, des noms de commandes proches sont proposés). Pour sauvegarder l’ensemble des commandes de la session en cours, vous pouvez utiliser la commande write, par exemple write("test"). Vous pouvez éditer le fichier (test dans l’exemple) en-dehors de giac avec un éditeur de texte (atom ou l’éditeur de pyzo). Vous pouvez ensuite exécuter la session avec la commande read("test") ou faire du copier-coller depuis l’éditeur.

Si vous pensiez utiliser Xcas à l’oral 2023 ou après, merci de m’envoyer un email à l’adresse parisse at univ-grenoble-alpes point fr. Si suffisamment de monde est concerné, peut-être que la position du jury évoluera. Il n’est pas normal que l’on prétexte des difficultés d’installation de Xcas à l’oral de l’agrégation, ce qui oblige à utiliser Geogebra pour accéder aux commandes de calcul formel de Xcas, sans pouvoir disposer de l’aide (indispensable pour utiliser un logiciel de calcul formel), sans pouvoir stocker des résultats intermédiaires dans des variables ni les enchainer en écrivant un petit algorithme.

Table des matières

N.B.: ce texte est disponible en ligne (interactif) ou en PDF (mort). La version HTML vous permet de tester avec ou sans modifications certains calculs ou algorithmes.

1  Introduction

L’outil informatique peut servir de diverses manières en mathématiques :

  1. On peut vérifier un calcul, par exemple

  2. On peut effectuer une représentation graphique
  3. On peut faire des simulations (aléatoires)
  4. On peut écrire un algorithme qui donne la construction d’un objet et peut servir de preuve d’un théorème. Par exemple l’algorithme d’Euclide étendu est une manière de prouver l’identité de Bézout.
  5. Une fois que l’on sait faire des calculs dans des situations simples, on peut utiliser la machine pour faire des calculs fastidieux ou techniques. Par exemple, on apprend à inverser une matrice 2x2 ou 3x3 simple à la main, puis on considère que la machine est bien mieux à même de faire des calculs d’inverses de matrices qu’un être humain, qui guide le calcul.
  6. La machine peut servir à faire des conjectures en testant beaucoup d’exemples, conjecture que l’on prouve ensuite. Par exemple, pour quelles valeurs de l’entier nn a-t-on n 4+4n^4+4 premier ou étant donné nn réels strictement positifs, quel est le minimum du produit de leur somme par la somme de leurs inverses ?

Ces aspects peuvent servir à faire une illustration informatique à chacun des oraux de l’agrégation interne, il n’est pas indispensable de savoir programmer pour utiliser l’outil informatique, quelques lignes de commandes pertinentes peuvent très bien faire l’affaire. Je donne quelques pistes dans la section qui suit. Le reste du document est consacré à l’algorithmique.

2  Algorithmique

Dans cette section, on passe en revue les notions de bases en algorithmique au programme (B.2), en commencant par travailler en ligne de commande (notion de variable, affectation), puis en complexifiant au fur et à mesure la ligne de commande (test, boucle) et on termine par l’écriture de fonctions. Les commandes des sections qui suivent peuvent être saisies et exécutées dans une ligne de commande de Xcas, pour des programmes qui dépassent une ou deux lignes, il est conseillé d’utiliser le menu Prg, et les assistants Test et Boucle (voir la section 2.3.2).

On pourra trouver d’autres tutoriels introduisant l’algorithmique, par exemple Algorithmique et programmation ay lycée La syntaxe sera donnée en Xcas (très proche du langage algorithmique en français) ou Python, avec les éléments de syntaxe permettant d’adapter à d’autres languages utilisables à l’oral (Python, Scilab, Maxima) . Quelques remarques sur ces logiciels et langages :

2.1  Données, variables, affectation

Pour stocker une donnée en mémoire, on utilise une variable. Une variable possède un nom, qui est composé d’au moins un caractère alphabétique (de A à Z ou de a à z) suivi ou non d’autres caractères alphanumériques, par exemple a, var, b12. Xcas est sensible à la différence entre majuscules et minuscules (c’est aussi le cas de Python, Maxima, Scilab). Une variable peut contenir n’importe quel type de donnée.

Pour donner une valeur à une variable

Pour utiliser la valeur d’une variable

Xcas peut manipuler différents types de données dont :

Maxima et Python peuvent manipuler des entiers, flottants, chaines de caractères, et listes, avec les mêmes délimiteurs que Xcas. Pour adresser un élément d’une liste, on utilise le nom de variable suivi de l’indice entre [], les indices commencent à 0 en Xcas, Scilab, Python et à 1 en Maxima. Attention, Scilab ne propose pas de type entier (on peut représenter un entier par un flottant sans erreur de représentation s’il est inférieur en valeur absolue à 2 532^{53}).

Il faut être bien conscient du type de données que l’on manipule, par exemple en Xcas

renvoie un rationnel, en Python2 7/2 renvoie 3 le quotient euclidien des deux entiers, alors que 7./2. renvoie 3.5 (le quotient des deux flottants). Attention, en Python3, 7/2 renvoie 3.5, le quotient en flottant, donc 4/2 est un flottant et pas un entier (il faut utiliser // pour obtenir le quotient euclidien sur les versions 2 et 3 de Python).

Exercices (Xcas) :

2.2  Instructions

2.2.1  Syntaxe

Une instruction valide dans Xcas doit suivre une syntaxe précise qui ressemble à l’écriture d’une expression en mathématique. Les différents éléments d’une instruction simple peuvent être des nombres (entiers, réels, flottants), des noms de variables, des opérateurs (par exemple +), des appels à des fonctions (l’argument ou les arguments se trouvant entre les parenthèses séparés par une virgule s’il y a plusieurs arguments) : par exemple

pour désigner la racine carrée de 3 ou
pour désigner le reste de la division euclidienne de 26 par 3).

Il faut prendre garde à la priorité entre les différentes opérations. Par exemple dans
l’opération * est effectué avant + comme en mathématiques. On peut utiliser des parenthèses pour forcer l’ordre des opérations, par exemple
.

Exercice : Calculer (vous pouvez utiliser la console en bas de page si vous consultez la version HTML de cette page)
5/2/3, 5/(2/3), 5/2*3, 5/(2*3), 5^2*3, 5^(2*3),5*2^3, (5*2)^3
Conclure sur les priorités relatives de la multiplication, de la division et de la puissance.

Attention, la multiplication doit (presque) toujours être indiquée explicitement contrairement aux mathématiques. Ainsi l’écriture ab ne désigne pas le produit de 2 variables a et b mais une variable dont le nom est ab.

Lorsqu’on veut exécuter plusieurs instructions à la suite, on termine chaque instruction par le caractère ; (ou par les caractères :; si on ne souhaite pas afficher le résultat de l’instruction). En Python il suffit de passer à la ligne, en Scilab, Maxima, on utilise ; (en syntaxe TI on utilise :).

2.2.2  Instructions graphiques

Pour réaliser des graphes de fonction, on dispose d’assistants. dans le Menu Graphiques de Xcas PC.

La suite de cette section est spécifique à Xcas PC (non disponible dans Xcas pour Firefox), les autres systèmes n’ayant en général pas d’instruction géométrique interagissant comme du calcul numérique.

Toutes les instructions du menu Geo ont un résultat graphique (à l’exception des instructions du menu Mesure), par exemple :

Lorsqu’une ligne de commande contient une instruction graphique, le résultat est affiché dans un repère 2-d ou 3-d selon la nature de l’objet généré. On peut controler le repère avec les boutons situés à droite du graphique, par exemple orthonormaliser avec le bouton \perp. Si une ligne de commande contient des instructions graphiques et non graphiques, c’est la nature de la dernière instruction qui décide du type d’affichage. On peut donner des attributs graphiques aux objets graphiques en ajoutant à la fin de l’instruction graphique l’argument affichage=..., argument dont la saisie est facilitée par le menu Graphic->Attributs.

L’instruction A:=point(click()) permet de définir une variable contenant un point du plan que l’on clique avec la souris (click() renvoie le nombre complexe correspondant). C’est un peu l’analogue géométrique de l’instruction saisir.

Lorsqu’on veut voir sur un même graphique le résultat de plusieurs lignes de commandes, on crée une figure avec le menu Geo->Nouvelle figure->graph geo2d, la figure correspond alors aux lignes de commande situées à gauche. Dans ce mode, on peut créer les objets graphiques en ligne de commande ou pour certains directement à la souris en sélectionnant un Mode et en cliquant. On peut aussi déplacer un point en mode Pointeur et observer les modifications des objets géométriques qui en dépendent.

Exemples :

Exercices (cf. le menu Geo pour les commandes de géométrie de Xcas) :

2.2.3  Tests

On peut tester l’égalité de 2 expressions en utilisant l’instruction ==, alors que != teste si 2 expressions ne sont pas égales. On peut aussi tester l’ordre entre 2 expressions avec <, <=, >, >=, il s’agit de l’ordre habituel sur les réels pour des données numériques ou de l’ordre lexicographique pour les chaines de caractères. En Python et Scilab, les tests sont identiques, avec Maxima on utilise = pour l’égalité.

Un test renvoie 1 ou true s’il est vrai, 0 ou false s’il est faux. On peut combiner le résultat de deux tests au moyen des opérateurs logiques && (ou et ou and), || (ou ou ou or), et on peut calculer la négation logique d’un résultat de test avec ! (ou not). En Python, on utilise les symboles &&, || ou !. Avec Maxima, Scilab, and, or et not.

On utilise ensuite souvent la valeur du test pour exécuter une instruction conditionnelle comme l’instruction si :
si condition alors bloc_vrai sinon bloc_faux fsi;
Un test peut être exécuté directement en ligne de commande, avec la syntaxe indiquée ci-dessous ou avec l’instruction when (Xcas syntaxe TI). La plupart du temps, on utilise un test dans une fonction ou un programme. Un test peut aussi servir pour arrêter une boucle en cours d’exécution ou renvoyer la valeur calculée par une fonction.

Par exemple, on pourrait stocker la valeur absolue d’un réel xx dans yy par :
(on peut bien sur utiliser directement y:=abs(x)). En syntaxe Python

#
if x>0:
  y=x
else:
  y=-x


Exercices :

2.2.4  Boucles

On peut exécuter des instructions plusieurs fois de suite en utilisant une boucle définie (le nombre d’exécutions est fixé au début) ou indéfinie (le nombre d’exécutions n’est pas connu). On utilise en général une variable de controle (indice de boucle ou variable de terminaison).

Remarques :

Exercices :

2.3  Fonctions

Pour réaliser des taches un peu plus complexes, il devient intéressant de les subdiviser en plusieurs entités indépendantes appelées fonctions, qui permettent d’étendre les possibilités des instructions du logiciel. Une fonction peut avoir 0, 1 ou plusieurs arguments (comme la fonction racine carrée sqrt() en a un). Elle calcule une valeur, appelée valeur de retour. Cette valeur de retour peut être utilisée dans une autre fonction ou expression algébrique, exactement comme le résultat de la fonction racine carrée.

La définition de fonctions peut parfois se faire directement avec une formule (fonction définie algébriquement) mais nécessite parfois un algorithme plus complexe. Elle peut calculer des résultats intermédiaires et les stocker dans des variables locales (afin de ne pas interférer avec les variables que l’utilisateur pourrait avoir défini en-dehors de la fonction). Par exemple pour calculer les racines d’un polynôme du second degré, on aura intérêt à calculer le discriminant et le stocker dans une variable locale.

Remarque :
De nombreuses calculatrices (TI non formelles, Casio, HP38/40) ne permettent pas de définir des fonctions, ainsi de nombreux algorithmes des programmes du secondaire ne sont pas rédigés comme des fonctions, mais comme des programmes ne prenant pas d’arguments et saisissant leurs arguments par des instructions saisir ou équivalent et affichent le résultat au lieu de le renvoyer. Il est alors difficile d’utiliser la valeur calculée (il faut la stocker dans une variable globale convenue á l’avance...) et l’exécution plusieurs fois d’un même programme pour le mettre au point devient vite pénible (il faut saisir encore et encore les mêmes valeurs). Au niveau du concours de l’agrégation interne, on préférera l’écriture d’algorithmes sous forme de fonctions, conformément à l’esprit des nouveaux programmes du lycée.

2.3.1  Fonctions simples

Il s’agit de fonctions définies par une formule algébrique.
Exemples :

Exercices :

Attention
Il faut faire la différence entre fonction et expression. Par exemple
définit une expression alors que
définit une fonction. On peut donc écrire
qui renverra 3 mais l’analogue avec aa serait
. On peut composer des fonctions, par exemple la fonction c=bbc=b \circ b est


, composer une fonction nn fois avec elle-même (c:=b@@n), et construire une fonction à partir d’une expression avec l’instruction unapply par exemple la fonction b dépendant de la variable x et définie par l’expression a est

2.3.2  Fonctions plus complexes

La plupart des fonctions ne peuvent pas être définies simplement par une formule algébrique. On doit souvent calculer des données intermédiaires, faire des tests et des boucles. On peut observer que c’est déjà ce qui se passe pour des fonctions système comme sum() ou seq qui effectuent une boucle implicite (avec une variable d’index intermédiaire “muette”). Il faut alors définir la fonction par une suite d’instructions, délimitées en Xcas par { ... } ou compris entre fonction nom(parametres) et ffonction.

La valeur calculée par la fonction est alors implicitement la valeur calculée par la dernière instruction exécutée (qui n’est pas forcément la dernière instruction du programme) ou peut être explicitée en utilisant le mot-clef return suivi de la valeur à renvoyer. Attention, dès que le mot-clef return est rencontré la valeur qui suit return est évaluée et la fonction se termine. Si on veut renvoyer 2 valeurs aa et bb, il ne sert à rien d’écrire return a; return b;, on les renverra plutot dans une liste ou une séquence (return [a,b];).

Notez que l’exécution de return met un terme à la fonction, même à l’intérieur d’un test ou d’une boucle, ce qui permet souvent d’améliorer la lisibilité :

Pour éviter que les données intermédiaires n’interfèrent avec les variables de la session principale, on utilise un type spécial de variables, les variables locales, dont la valeur ne peut être modifiée ou accédée qu’à l’intérieur de la fonction. On utilise à cet effet le mot-clef local suivi par les noms des variables locales séparés par des virgules (attention, en Python, toute variable intermédiaire d’une fonction est considérée comme locale, sauf indication contraire avec global ceci peut être source d’erreur si vous faites une faute de frappe dans un nom de variable).

Comme le texte définissant une telle fonction ne tient en général pas sur une ou deux lignes, il est commode d’utiliser un éditeur de programmes pour définir une fonction, soit l’éditeur fourni par le logiciel, soit un éditeur généraliste (comme ultraedit, atom, emacs, vi, ...). Dans Xcas, il est conseillé d’utiliser le menu Prg->Nouveau programme. Les assistants Fonction, Boucle et Test ou le menu Prg->Ajouter facilitent la saisie des principales structures et commandes de programmation. Les commandes de Xcas sont affichées en brun, les mots clef du langage en bleu.

Exemple : encore le PGCD mais sous forme de fonction

fonction pgcd(a,b)
  local r;
  tantque b!=0 faire
    r:=irem(a,b);
    a:=b;
    b:=r;
  ftantque;
  return a;
ffonction:;

onload
En syntaxe Python :

def pgcd(a,b):
    # local r
    while b!=0:
        r=a % b
        a=b
        b=r
    return a


On clique ensuite sur le bouton OK, si tout va bien, le programme pgcd est défini et on peut le tester dans une ligne de commande par exemple par

On peut exécuter en mode pas à pas un programme et visualiser l’évolution de la valeur des variables avec l’instruction debug(), ce qui peut servir à comprendre le déroulement d’un algorithme, mais aussi à corriger un programme erroné (un analogue existe en Scilab et Python, selon l’environnement de programmation). Par exemple, enlevez le // de commentaire et exécutez

Exercice :

2.3.3  Récursivité

On peut au cours du déroulement d’une fonction faire appel à cette même fonction avec un ou des arguments “plus simples”, de sorte qu’après un nombre fini d’appels récursifs, l’argument ou les arguments sont devenus triviaux, et on peut alors renvoyer le résultat. Par exemple, l’algorithme d’Euclide peut s’énoncer sous la forme

Le PGCD de aa et bb est aa si bb est nul et est le PGCD de bb et du reste de la division euclidienne de aa par bb sinon.

On peut le traduire en Xcas par


En syntaxe Python

def pgcdr(a,b):
  if b==0:
     return a
  return pgcdr(b,a%b)

Dans certains cas, la récursivité permet de simplifier grandement la conception d’un algorithme, par exemple pour le calcul du reste de a na^n par un entier fixé mm, en distinguant nn pair et nn impair et en utilisant pour n>0n&gt;0 pair : a n(modm)=(a n/2(modm)) 2(modm) a^n \pmod m = (a^{n/2} \pmod m)^2 \pmod m et pour n>1n&gt;1 impair : a n(modm)=(a×(a (n1)/2(modm)) 2)(modm) a^n \pmod m = (a \times (a^{(n-1)/2} \pmod m)^2) \pmod m

Exercice : implémenter le calcul de a n(modm)a^n \pmod m de cette manière.

Attention à bien s’assurer que le programme récursif se termine. En particulier quand on teste un programme récursif, il est conseillé de commencer par tester le cas où la récursion doit se terminer. Notez aussi que Xcas limite le nombre de récursions (réglage modifiable dans la configuration du cas).

Attention aussi, un algorithme récursif peut être très inefficace, par exemple si on calcule les termes de la suite de Fibonacci par la formule


alors le calcul de F 5F_5
nécessite le calcul de F 4F_4 et F 3F_3 mais le calcul de F 4F_4 demande lui-même le calcul de F 3F_3 et F 2F_2, on calcule donc deux fois F 3F_3, trois fois F 2F_2, cinq fois F 1F_1, comme on peut le voir en affichant la valeur de nn pour laquelle FF est calculée :
(exercice : le nombre total de calcul est lui-même une suite de Fibonacci!). Il est plus efficace dans ce cas d’écrire une boucle (exercice : le faire!).

3  Arithmétique

Pour cette section, on pourra se référer au manuel de programmation de Xcas. Pour les instructions prédéfinies, utiliser le menu CAS, Arithmétique ou le menu Cmds, Entier et Cmds, Polynômes.

Exposés : 105, 107 Exercices : 305, 306, 307

3.1  Arithmétique des entiers

3.1.1  Division euclidienne

Application :écriture d’un entier en base bb. Instructions : iquorem, iquo, irem.

3.1.2  Euclide, Bézout

Commandes de Xcas : gcd, iegcd et iabcuv.

Exercice : Écrire un algorithme de PGCD itératif ou/et récursif. Même question pour Bézout.

Solution : Algorithme itératif pour aa et bb :

Exemple : exécutez la commande ci-dessous qui calcule l’identité de Bézout pour 125 et 45 en affichant les étapes de l’algorithme dans la partie basse de la page HTML

Explication : A chaque itération, l’élément l[2] d’indice 2 de la liste l 1l_1 (ou l 2l_2) prend comme valeur l’un des restes successifs de l’algorithme d’Euclide, et on a un invariant de boucle a*l[0]+b*l[1]=l[2] qui donne l’identité de Bézout lorsque l[2] est le dernier reste non nul. Cet invariant se prouve facilement par récurrence.

On peut aussi voir cet algorithme comme une version arithmétique de l’algorithme du pivot de Gauss pour créer un zéro dans la dernière colonne de la matrice (L 1 1 0 a L 2 0 1 b) \left(\begin{array}{rccc} L_1 & 1 & 0 & a \\ L_2 & 0 & 1 & b \end{array}\right) . Mais seules les manipulations de lignes du type L n+2=L nqL n+1L_{n+2}=L_n-qL_{n+1} avec qq entier sont admises, il faut donc plusieurs manipulations de lignes avant d’avoir un 0, la ligne précédente donnant le PGCD (dernier reste non nul) et les coefficients de Bézout. (L 1 1 0 125 L 2 0 1 45 L 3=L 12L 2 1 2 35 L 4=L 2L 3 1 3 10 L 5=L 34L 4 4 11 5 L 6=L 42L 5 9 25 0 )\left(\begin{array}{rccc} L_1 & 1 & 0 & 125 \\ L_2 & 0 & 1 & 45 \\ L_3=L_1-2L_2 & 1 & -2 & 35\\ L_4=L_2-L_3 & -1 & 3 & 10 \\ L_5=L_3-4L_4 & 4 & -11 & 5 \\ L_6=L_4-2L_5 & -9 & 25 & 0 \\ \end{array}\right)

Algorithme de Bézout itératif en syntaxe Xcas (disponible depuis Doc/Exemples lycée dans Xcas pour Firefox le jour de l’oral ou depuis Xcas dans la session du sous-menu Exemples/arit/bezout.xws)

fonction bezout(a,b)
  local l1,l2,q;
  l1:=[1,0,a];
  l2:=[0,1,b];
  tantque l2[2]!=0 faire
    q:=iquo(l1[2],l2[2]);
    l1,l2:=l2,l1-q*l2;
  ftantque;
  return l1;
ffonction:;

onload
On a utilisé l’affectation simultanée pour simplifier le décalage des indices.

Le même algorithme en Python. Attention, la combinaison linéaire de ligne doit se faire élément par élément.

def bezoutpy(a,b):
    # local l1,l2,q
    l1=[1,0,a]
    l2=[0,1,b]
    while l2[2]!=0:
        q=l1[2]//l2[2]
        l1,l2=l2,[l1[0]-q*l2[0],l1[1]-q*l2[1],l1[2]-q*l2[2]]
    return l1

onload

On peut adapter pour calculer l’inverse d’un entier modulo un autre entier en diminuer la longueur des listes de 1 (on n’a besoin que d’un seul des coefficients de Bézout).

Applications/exercices possibles :

3.1.3  Nombres premiers

Test de primalité par division. Recherche des nombres premiers inférieurs à un entier donné (crible).

fonction crible(n)
  local tab,prem,p;
  tab:=seq(j,j,0,n); // liste des entiers <= n 
  tab[0]:=0; tab[1]:=0; // on remplace par 0 un entier non premier
  p:=2;
  tantque p*p<=n faire
    // afficher(tab," on barre les multiples de "+p);
    // p est premier, on barre les multiples de p
    pour j de p*p jusque n pas p faire
      tab[j]:=0;
    fpour;
    // on cherche le prochain nombre non barre qui est premier
    p:=p+1;
    tantque p*p<=n et tab[p]==0 faire
      p:=p+1;
    ftantque;
  ftantque;
  // on cree la liste des nombres non barres
  prem:=[];
  pour j de 2 jusque n faire
    si tab[j]!=0 alors prem.append(j); fsi;
  fpour;
  return prem;
ffonction:;

onload

Pour obtenir la traduction en Python de ce programme, on peut utiliser la commande python(crible) dans Xcas, après nettoyage :

def criblepy(n):
    # local tab,prem,p
    tab=list(range(n+1))
    tab[0]=0
    tab[1]=0
    p=2
    while p*p<=n :        
        j=p*p
        while j<=n :
            tab[j]=0
            j=j+p
        p=p+1
        while p*p<=n and tab[p]==0 :
            p=p+1
    prem=[]
    for j in range(2,n+1):
        if tab[j]!=0 :
            prem.append(j)
    return(prem)

onload

Test de primalité probabiliste de Miller-Rabin :
Ce test utilise le fait que si pp est premier, /p\mathbb{Z}/p\mathbb{Z} est un corps et pour a0a\neq 0, a p1=1(modp)a^{p-1}=1 \pmod p. On écrit pp premier différent de 2 sous la forme 2 ts2^t s avec ss impair. Comme l’équation x 2=1x^2=1 n’admet que 1 et -1 comme racines modulo pp, pour aa fixé on peut avoir soit a t=1(modp)a^t=1 \pmod p, sinon en prenant tt fois le carré modulo pp on doit prendre la valeur -1. Si le test échoue, pp n’est pas premier. Si le test réussit, pp n’est pas forcément premier, mais on peut montrer qu’il y a au plus 1 entier sur 4 pour lequel il réussit. On reprend donc le test pour quelques autres valeurs de aa jusqu‘à être raisonnablement sur que pp est premier (il existe aussi des certifications de primalité).

fonction millerrabin(p,a)
  local t,s,j;
  si irem(p,2)==0 alors return "p doit etre impair"; fsi;
  // on ecrit p-1 sous la forme 2^t*s
  s:=p-1;
  t:=0;
  tantque irem(s,2)=0 faire 
    s:=s/2;
    t++;
  ftantque;
  // on calcule a^s, si c'est 1 le test passe, 
  // sinon on doit avoir un -1 dans la chaine des carres
  a:=powmod(a,s,p);
  si a==1 alors return "p est peut-etre premier"; fsi; 
  pour j de 1 jusque s faire
    si a==p-1 alors return "p est peut-etre premier"; fsi;
    a:=irem(a*a,p);
  fpour;
  return "p n'est pas premier";
ffonction:;

onload

En Python

def millerrabinpy(p,a):
    # local t,s,j
    if p % 2==0 :
        return "p doit etre impair"
    s=p-1
    t=0
    while s % 2==0 :        
        s=s//2
        t+=1
    a=pow(a,s,p)
    if a==1 :
        return "p est peut-etre premier"
    for j in range(s):
        if a==p-1 :
            return "p est peut-etre premier"
        a=a*a % p
    return "p n'est pas premier"

onload

On peut aussi aborder l’algorithme de Pollard-rho basé sur le théorème des anniversaires, voir le manuel Algorithmes dans l’aide de Xcas.

3.1.4  Restes chinois

Recherche de a(modp i)a \pmod{ \prod p_i} connaissant a(modp i)a \pmod {p_i}. On peut commencer par 2 nombres premiers (et utiliser Bézout). En effet si a=a 1(modp) 1a=a_1 \pmod p_1 et a=a 2(modp) 2a=a_2 \pmod p_2 alors il existe des entiers uu et vv tels que a=a 1+up 1=a 2+vp 2a=a_1+up_1=a_2+vp_2, on peut calculer uu et vv en appliquant Bézout à a 1a 2=up 1+vp 2a_1-a_2=-up_1+vp_2.

La commande de Xcas correspondante est ichinrem.

3.1.5  RSA and co

On choisit n=pqn=pq produit de deux nombres premiers assez grands gardés secrets, de sorte que la factorisation de nn soit trop longue pour pouvoir déterminer pp et qq connaissant nn. L’application de codage dans /n\mathbb{Z}/n\mathbb{Z} consiste à calculer xx d(modn) x \rightarrow x^d \pmod n Elle est inversible si dd admet un inverse ee modulo ϕ(n)\phi(n)ϕ(n)=(p1)(q1)\phi(n)=(p-1)(q-1) est l’indicatrice d’Euler de nn, son inverse est identique à l’application de codage en remplacant dd par ee.

Exercice : écrire des fonctions de chiffrement/déchiffrement par RSA. Instruction Xcas utiles : powmod, inv(d % n). Pour convertir une chaine de caractères en liste d’entiers (codes ASCII) on peut utiliser asc et char. Pour grouper plusieurs entiers, on peut utiliser convert(.,base,.)

Voir la section 4.2.2 ci-dessous.

3.2  Arithmétique des polynômes

3.2.1  Division euclidienne

Calcul du quotient et du reste de la division de 2 polynômes dont les coefficients sont donnés dans une liste. Instructions : quorem, quo, rem. Exemple d’application : élimination de racines (pour trouver toutes les racines d’un polynôme)

3.2.2  Évaluation d’un polynôme en un point

Application : inverse de l’écriture en base bb. Programmation de la méthode de Horner (fonction horner de Xcas)
Il s’agit d’évaluer efficacement un polynôme P(X)=a nX n+...+a 0 P(X) = a_n X^n + ... + a_0 en un point. On pose b 0=P(α)b_0=P(\alpha ) et on écrit : P(X)b 0=(Xα)Q(X) P(X)-b_0=(X-\alpha )Q(X) où : Q(X)=b nX n1+...+b 2X+b 1 Q(X) = b_n X^{n-1} + ... +b_2 X + b_1 On calcule alors par ordre décroissant b nb_n, b n1b_{n-1}, ..., b 0b_0.

  1. Donner b nb_n en fonction de a na_n puis pour in1i\leq n-1, b ib_i en fonction de a ia_i et b i+1b_{i+1}. Indiquez le détail des calculs pour P(X)=X 32X+5P(X)=X^3-2X+5 et une valeur de α\alpha entière non nulle.
  2. Écrire un fonction horn effectuant ce calcul: on donnera en arguments le polynôme sous forme de la liste de ces coefficients (dans l’exemple [1,2,0,-1,5]) et la valeur de α\alpha et le programme renverra P(α)P(\alpha ). (On pourra aussi renvoyer les coefficients de QQ).
  3. Quel est le nombre d’opérations effectuées (comparer à ce que donne le calcul en appliquant la forme développée du polynôme) ?
  4. En utilisant cette fonction, écrire une fonction qui calcule le développement de Taylor complet d’un polynôme en un point.

Solution : menu Aide de Xcas, Exemples, poly, horner.

def Horner(p,a):
  # p liste des coefficients par ordre décroissant
  # renvoie p évalué en a
  # local c,r
  r=0
  for c in p:
    r=r*a+c
  return r

onload
Test et vérification avec la commande interne horner de Xcas

3.2.3  Euclide, Bézout

Commandes de Xcas : gcd, egcd et abcuv. Se programme comme pour les entiers en utilisant la division euclidienne des polynômes (quo, rem). Applications :

3.2.4  Racines rationnelles

Écrire une fonction qui détermine les racines rationnelles d’un polynôme PP à coefficients entiers, en observant qu’elles sont de la forme p/qp/qqq divise le coefficient dominant de PP et ±p\pm p divise son coefficient de plus bas degré. Tester avec le polynôme P=12x 5+10x 46x 3+11x 2x6P=12x^5+10x^4-6x^3+11x^2-x-6.

N.B.: ce n’est pas un algorithme efficace, cf. le manuel Algorithmes de calcul formel. Les commandes Xcas correspondantes sont rationalroot, crationalroot.

Solution :

fonction racrat(P)
  local Lp, Lq, rac, p, q, r;
  // determiner les fractions possibles p/q  
  // p est dans la liste des diviseurs du coefficient constant de P
  Lp:=idivis(abs(tcoeff(P)));
  // q est dans la liste des diviseurs du coefficient dominant de P
  Lq:=idivis(abs(lcoeff(P)));
  rac:=[]; // liste des racines rationnelles, initialement vide
  pour p in Lp faire 
    pour q in Lq faire 
      si gcd(p,q)==1 alors
        r:=p/q;
        // test si P(r)=0 ou P(-r)=0, si oui ajout a la liste des racines
        si P(x=r)==0 alors rac:=append(rac, r); fsi;
        si P(x=-r)==0 alors rac:=append(rac, -r); fsi;
      fsi;
    fpour;
  fpour;
  return rac;
ffonction:;

onload


3.2.5  Racines réelles et complexes

proot permet d’avoir les racines approchées d’un polynôme à 1 variable. solve, csolve calculent les racines racines exactes si le calcul a un intérêt, au sens où le résultat peut être raisonnablement manipulé par le calcul formel. pcoeff donne les coefficients du polynôme unitaire dont on passe en arguments la liste des racines.

3.2.6  Autres

Interpolation de Lagrange, fonction lagrange de Xcas. Référence : documentation de Xcas et le livre de Demailly.

Transformée de Fourier rapide fft, ifft, application que l’on peut citer pour la lecon 167.

4  Codage et cryptographie

(Leçon disparue, peut encore servir dans d’autres leçons pour les candidats qui le souhaitent).

4.1  Codes

On désigne sous ce nom la numérisation de données, mais aussi diverses applications de l’algèbre et de l’arithmétique pour tester qu’une donnée a été transmise correctement en ajoutant une information supplémentaire. Pour certains codes (codes correcteurs), cette information supplémentaire permet de corriger un petit nombre d’erreurs de transmission.

4.1.1  Numérisation de texte

On peut citer le code ASCII, qui permet d’associer à tous les caractères américains un entier compris entre 0 et 127 (7 bits). Ainsi A correspond à 65, B à 66, etc. On peut tester la transmission en ajoutant un 8ème bit de parité (bit de poids fort mis à 0 ou à 1 pour que l’entier transmis soit pair). La prise en compte des accents et alphabets non latins à conduit à utiliser d’autres codes, les isolatin par exemple ou les pages de code windows. Ces codes n’étaient pas compatibles entre eux, récemment, ils ont été remplacés par l’unicode, dont deux variantes sont très populaires: UTF8 (compatible avec ASCII) et UTF16.

Xcas utilise l’UTF8 pour coder des chaines de caractères. Les commandes asc et char permettent de convertir une chaine de caractères en une liste et réciproquement.
Par exemple

On peut travailler sur la liste d’entiers obtenus, par exemple en considérant qu’il s’agit d’un seul entier écrit en base 256 (instruction convert), par exemple



si cet entier est trop grand, on peut le décomposer à nouveau, par exemple selon une base une puissance de 256 (ce qui revient à regrouper les caractères du message initial par bloc)


4.1.2  Représentation des nombres approchés

Pour représenter un nombre à virgule flottante, les microprocesseurs utilisent le format “double” composé d’un bit de signe, 11 bit pour l’exposant et 52 bits pour la mantisse. Voir le manuel Algorithmes de Xcas.

4.1.3  Vérification

Les codes de vérification les plus simples appelés clés, consistent à calculer le reste de la division de l’entier codant la donnée par un entier donné et à ajouter cette information supplémentaire (la clé). Le bit de parité est l’exemple le plus simple (parité du nombre de 1 dans l’écriture en base 2 d’un nombre). Autre exemple la clé RIB est le complément à 97 du reste de la division par 97 de l’information. Comme pour la preuve par 9, si le test de divisibilité est incorrect, on est sur que l’information est incorrecte, mais si le test est correct on n’est pas sur que l’information est bonne.

4.1.4  Codes polynomiaux

Définition : On travaille sur un corps fini (par exemple /p\mathbb{Z}/p\mathbb{Z} pour pp premier). On représente le message de longueur kk à coder par un polynôme PP de degré k1k-1 dont les coefficients contiennent l’information (par exemple message). On se donne un polynôme g(x)g(x) de degré m=nkm=n-k (avec n>kn&gt;k). On multiplie PP par x nkx^{n-k}, on calcule le reste RR de la division euclidienne de Px nkP x^{n-k} par gg. On émet alors Px nkRP x^{n-k}-R qui est un polynôme de degré n1\leq n-1 divisible par gg.

Un des intérêts des codes polynomiaux est que la vérification de bonne transmission de l’information est très simple : il suffit de tester la divisibilité par gg (et on extrait l’information pertinente en ne gardant que les kk premiers coefficients).

En Xcas, on peut travailler avec des polynômes à coefficients dans /p\mathbb{Z}/p\mathbb{Z} comme avec les mêmes instructions que pour des polynômes à coefficients dans Q\Q en ajoutant mod p. Par exemple
. On peut aussi travailler avec un corps fini de cardinal non premier (instruction GF, par exemple


permet de travailler sur le corps fini à 256 éléments, cf. le manuel Algorithmes de Xcas) mais ceci est un peu au-dessus du niveau de l’agrégation interne.

Exercice : écrire de cette facon le codage du bit de parité (divisibilité par x+1x+1 modulo 2 ou évaluation nulle en 1). Puis une procédure Xcas de codage utilisant g=X 7+X 3+1g=X^7+X^3+1 sur le corps /2\mathbb{Z}/2\mathbb{Z} (ce polynôme était utilisé par le Minitel).

Remarque : les codes polynomiaux sont un cas particulier de codes linéaires mais les espaces vectoriels à coefficients dans un corps finis ne sont pas au programme de l’agrégation interne, on n’en parlera donc pas.

4.1.5  Codes polynomiaux correcteurs

Avertissement : les notions abordées ici vont parfois bien au-delà de ce qu’on peut attendre d’un candidat à l’agrégation interne. Il s’agit plutot de montrer que des notions assez abstraites comme les polynômes à coefficients dans un corps fini ont des applications.

Si le polynôme gg est de degré pas trop petit, on peut espérer que l’information complémentaire contenue dans le reste peut permettre de corriger une ou 2 erreurs de transmission.

Définition: On appelle distance (de Hamming) entre 2 polynômes le nombre de coefficients distincts de ces 2 polynômes (On vérifie qu’il s’agit bien d’une distance).

Définition On appelle distance du code polynomial défini par l’entier kk et le polynôme gg de degré m=nkm=n-k le minimum de la distance de Hamming entre 2 multiples distincts de gg de degré <n&lt;n (ou ce qui revient au même d’un multiple non nul de gg de degré <n&lt;n).

Si une information reçue est codée par un polynôme PP qui n’est pas multiple de gg, il y a erreur de transmission, on peut chercher à corriger les coefficients mal transmis en remplaçant PP par un multiple de gg de degré <n&lt;n proche de PP au sens de la distance de Hamming. Cela fait sens si on peut assurer l’unicité du multiple de gg le plus proche (ceci n’assure pas l’existence d’un tel multiple de gg, même si c’est vrai pour certains codes). Si le nombre de coefficients à corriger est au plus tt et si 2t+12t+1 est inférieur ou égal à la distance du code, alors il y aura unicité (sinon il y aurait deux multiples distincts de gg à distance t\leq t de PP donc dont la distance mutuelle serait 2t\leq 2t, impossible car cette distance serait strictement inférieure à la distance du code).

On a donc tout intérêt à ce que la distance du code soit la plus grande possible. On observe que la distance du code est inférieure ou égale au nombre de coefficients non nuls de gg puisque gg est un multiple non nul de lui-même, donc à m+1m+1. Dans les cas favorables (choix judicieux de gg), la distance du code vaut exactement m+1m+1 et on pourra alors espérer corriger au plus m/2m/2 erreurs.

Proposition Soit KK corps fini de générateur aa, on considère un code polynomial tel que n<n &lt; cardinal(K)(K) et g(x)= j=1 m(xa j) g(x)=\prod_{j=1}^m (x-a^j) Alors la distance du code correspondant est m+1m+1.

Preuve : soit PP un multiple de gg de degré <n&lt;n ayant au plus mm coefficients non nuls, alors on peut écrire P(x)= j=1 mp k jx k j,k j<n P(x)=\sum_{j=1}^m p_{k_j} x^{k_j}, \quad k_j &lt; n Comme PP est un multiple de gg, il s’annule en a,a 2,..,a l,..,a ka, a^2,..,a^l, .., a^k, on a donc le système j=1 mp k j(a k j) l=0,l=1..m \sum_{j=1}^m p_{k_j} (a^{k_j})^l = 0, \quad l=1..m Mais ce système en les p k jp_{k_j} est un système de Cramer m,mm,m, car son déterminant est un déterminant de Vandermonde engendré par des éléments du corps fini, les a k j,j=1..ma^{k_j}, j=1..m, qui sont distincts 2 à 2 puisque aa est un générateur du corps.

Exercice : générer un code polynomial sur /97Z\mathbb{Z}/97Z pouvant corriger jusqu’à 2 erreurs. Programmer la correction au plus proche (on commencera par tester la divisibilité en changeant un coefficient, puis 2).

Exercice : lien avec la loi binomiale. On suppose que la probabilité d’erreur de transmission d’un coefficient est ε\varepsilon (par exemple ε=0.001=1e3\varepsilon=0.001=1e-3, et que les erreurs de transmission coefficient par coefficient sont indépendantes. On transmet nn caractères, quelle est la probabilité d’avoir au plus tt erreurs de transmission (et donc de pouvoir corriger avec le code précédent) ?

4.2  Cryptographie

4.2.1  Jules César, Vigenère, affine, Hill.

Le principe consiste à utiliser une bijection de /p\mathbb{Z}/p\mathbb{Z} dans lui-même pour crypter le message. Le codage de Jules César peut être vu comme l’addition d’une constante dans /26\mathbb{Z}/26\mathbb{Z}, Vigenère est l’addition des lettres du message à crypter avec les lettres d’un texte fixé. On peut enrichir l’alphabet cryptable de 26 à 37 en ajoutant les chiffres de 0 à 9 (codés par eux-même, les lettres de A à Z par les entiers de 10 à 35 et l’espace par 36), ce qui permet de travailler dans le corps /37\mathbb{Z}/37\mathbb{Z}.

Le codage affine utilise une application affine xax+b x \rightarrow ax+b avec aa inversible modulo pp (le calcul de l’inverse fait intervenir l’identité de Bézout). Aucune de ces méthodes n’est résistante à une analyse statistique du message crypté (dans le cas de Vigenére, l’attaque est plus complexe à mettre en oeuvre). Le codage affine n’est pas résistant à une attaque par force brute (on essaie toutes les clés possibles).

Le chiffrement de Hill groupe les lettres du message à crypter par paquets de nn (nn fixé) pour éviter l’attaque par analyse statistique (on peut améliorer la sécurité du cryptage en décidant d’ajouter une partie de caractères aléatoires dans un paquet, par exemple la moitié), on a donc un vecteur v(/p) nv \in (\mathbb{Z}/p\mathbb{Z})^n dont on calcule l’image par un chiffrement affine vAv+b v \rightarrow Av+b AA est une matrice inversible sur /p\mathbb{Z}/p\mathbb{Z} Ce codage est un peu à la limite du programme sauf dans des cas comme n=2n=2 où on peut exprimer l’inverse explicitement de manière simple, malheureusement dans ce cas nn n’est pas suffisamment grand pour que ce code soit résistant à une analyse statistique ou/et une attaque par force brute.

De plus toutes ces méthodes supposent que les clés de chiffrement et de déchiffrement sont secretes (en effet si on connait l’une des clefs on en déduit l’autre), alors que RSA par exemple permet de publier une des deux clefs.

Exercices : écrire des fonctions de chiffrement/déchiffrement par ces méthodes. Instruction en Xcas : asc, char, %, inv.

Soit p=37p=37 et la matrice à coefficients dans Z/pZ\Z/p\Z A=(1 5 7 8)[37]A= \begin{pmatrix} 1 & 5 \\ 7 & 8 \end{pmatrix} \ [37]

  1. Montrer que AA est inversible et calculer son inverse.
  2. On groupe les caractères par paires, chaque paire de caractères est considérée comme un vecteur vv de (Z/37Z) 2(\Z/37\Z)^2. On code un vecteur vv en envoyant AvAv. Comment décode-t-on un message codé ?
  3. Coder le message composé des 4 chiffres 2020
  4. Décoder le message suivant
    [20,10],[27,12],[9,16],[14,32],[19,14],[9,16],[2,14],[2,14]
  5. Ce codage est-il plus résistant à une attaque que celui de la section précédente ? Comment pourrait-on le rendre plus résistant ?
  6. Donner un algorithme permettant de coder un message, prenant en argument une matrice A (sous forme d’une liste de 2 listes ayant 2 éléments) et un message m sous forme d’une liste d’entiers compris entre 0 et 36 et renvoyant un message codé sous forme d’une liste d’entiers compris entre 0 et 36. Indiquer comment adapter cet algorithme pour votre codage plus résistant de la question (5).

4.2.2  Cryptographie RSA

Rappel du principe de codage RSA :


Exercice 1: Générer une paire de clefs
Génèrez deux nombres premiers pp et q>256q&gt;256 au hasard, en utilisant par exemple les fonctions nextprime et rand. Calculez n=p×qn=p \times q puis φ(n)=(p1)(q1)\varphi(n)=(p-1)(q-1) puis choisissez une clef secrète ss inversible modulo φ(n)\varphi(n) et calculez son inverse cc. Vérifiez sur quelques entiers la propriété (1), on utilisera la fonction powmod(a,c,n) pour calculer a c(modn)a^c \pmod n.


Exercice 2: Codage et décodage d’un message
On transforme une chaine de caractère en une liste d’entiers et réciproquement avec asc et char. Pour l’appliquer à une liste l, on peut utiliser map(l,powmod,c,n). En utilisant la paire de clefs de l’exercice 1, codez un message puis décodez ce message pour vérifier. Décodez le message authentifié situé sur ce lien


Exercice 3: Puissance modulaire rapide
Pour pouvoir crypter des messages de cette manière, il est nécessaire d’avoir une fonction calculant a c(modn)a^c \pmod n rapidement. Comparer le temps de calcul de a^c mod n et powmod(a,c,n) pour quelques valeurs de a,c,na, c, n (on pourra utiliser time(instruction) pour connaitre le temps d’exécution d’une instruction. Pour comprendre cela, programmez une fonction puimod calculant a c(modn)a^c \pmod n en utilisant et en justifiant un des algorithmes


Exercice 4: Attaque simple
L’utilisation de 256 valeurs possibles pour aa se prête à une attaque très simple : la personne souhaitant décoder un message codé avec une clef publique sans en connaitre la clef secrète calcule simplement la liste des a c(modn)a^c \pmod n pour les 256 valeurs possibles de aa et compare au message. Décodez de cette manière le message situé ici.


Exercice 5: Groupement de lettres
Pour parer à cette attaque, on va augmenter le nombre de valeurs possibles de aa pour que le calcul de la liste de toutes les puissances des aa possibles soit trop long. Pour cela, on groupe par paquets de xx caractères et on associe à un groupe de caractères l’entier correspondant en base 256. Par exemple, si on prend des groupes de x=3x=3 caractères, "ABC" devient 65*256^2+66*256+67 car le code ASCII de A, B, C est respectivement 65, 66, 67. Donner une condition reliant nn et xx pour que le décodage redonne le message original. Choisissez une paire de clefs vérifiant cette condition pour x=8x=8. Ecrire un programme de codage et de décodage avec groupement (on commencera par compléter le message original par des espaces pour qu’il soit un multiple de 8 caractères, l’instruction size permet de connaitre la taille d’une chaine de caractères, on pourra utiliser la fonction d’écriture en base de la feuille d’exercices 2).


Exercice 6: Sécurité du codage 1
Montrer que la connaissance de φ(n)\varphi(n) et de nn permet de calculer pp et qq par résolution d’une équation de degré 2. La sécurité du codage repose donc sur la difficulté de factoriser nn. Tester sur des entiers de taille croissante le temps nécessaire au logiciel pour factoriser pp et qq. Une valeur de nn de taille 128 bits, 512 bits, 1024 bits parait-elle suffisante?


Exercice 7: Sécurité du codage 2
Le choix de cc et de ss est aussi important. Pour le comprendre, prenons p=11p=11 et q=13q=13. Représentez pour différentes valeurs de cc les points (a,a c(modn))(a,a^c \pmod n), plus le dessin obtenu est aléatoire, plus il sera difficile à une personne mal intentionnée de déchiffrer un message sans connaitre la clef. On pourra utiliser les instructions seq pour générer une suite de terme général exprimé en fonction d’une variable formelle, et scatterplot(l) qui représente le nuage de points donné par une liste l de couples de coordonnées. Observez en particulier les cas où cc n’est pas premier avec φ(n)\varphi(n) et c=3c=3. Conclusions ?


Exercice 8: Primalité
Pour créer une paire de clefs, il faut générer des nombres premiers et donc être capable de déterminer si un nombre est premier ou non. Un test simple consiste à appliquer la contrapposée du petit théorème de Fermat: si a pa(modp)a^p \neq a \pmod p, alors pp n’est pas premier. Ecrire une fonction prenant en argument aa et pp et renvoyant 0 si pp n’est pas premier et 1 si a p=a(modp)a^p =a \pmod p, puis une fonction prenant en argument pp et effectuant le test pour toutes les valeurs de a[2,p1]a\in[2,p-1] jusqu’à ce que le test échoue. Si tous le tests réussissent, pp est peut-être premier mais ce n’est pas certain: existe-t-il un nombre non premier pour lequel tous les tests réussissent ?

4.2.3  Secret commun

On utilise le même fait que RSA, le calcul de la puissance modulo un entier donné est une opération efficace. On se donne deux entiers gg et pp avec pp premier et g<pg&lt;p un générateur de /p\mathbb{Z}/p\mathbb{Z} (si possible, sinon il faut que l’ordre de gg soit du même ordre de grandeur que pp). Pour créer un secret commun, Alice et Bob choisissent chacun un entier secret, respectivement a<p1a&lt;p-1 et b<p1b&lt;p-1. Ils calculent g a(modp)g^a \pmod p et g b(modp)g^b \pmod p et se les envoient. Le secret commun est g ab(modp)g^{ab} \pmod p. Alice et Bob peuvent efficacement calculer le secret commun, mais un espion ne peut pas déterminer efficacement aa ou bb à partir de gg, g ag^a et g bg^b.

4.2.4  Partage de secret entre plusieurs personnes

On représente un secret par un entier ss. On souhaite transmettre ce secret à nn personnes. Une première méthode consiste à découper ss en plusieurs parties, par exemple en écrivant ss dans une base convenable, ou bien en donnant la valeur de ss modulo plusieurs nombres premiers (reconstruction par le lemme chinois). Cette méthode est peu résistante, d’une part parce que la connaissance d’une partie des morceaux peut permettre la reconstruction de ss en testant toutes les valeurs possibles des morceaux manquants, d’autre part parce qu’on ne peut pas se prémunir contre des erreurs (ou un ou deux morceaux manquants).

Une deuxième méthode, plus résistante, consiste si sK=/ps\in K=\mathbb{Z}/p\mathbb{Z} avec pp premier (ou KK un corps fini non premier) à choisir aléatoirement n1n-1 éléments de KK, pour construire un polynôme PP de degré n1n-1 ayant ss comme coefficient constant. On calcule ensuite pour chacun des nn morceaux la valeur de t k=P(x k)t_k=P(x_k) en nn abscisses distinctes 2 à 2 fixées x kx_k, le morceau de secret est alors t kt_k. On peut alors reconstruire PP avec les t kt_k par interpolation de Lagrange et retrouver s=P(0)s=P(0). Si le polynôme PP est de degré plus petit, on peut reconstruire PP et donc ss avec un nombre plus faible de morceaux du secret (voire éliminer des morceaux de secrets invalides).

Instruction en Xcas : convert(.,base,.), ichinrem, horner, lagrange.

Pour en savoir plus sur toute cette section, cf. par exemple Demazure, Gilles Zémor, le manuel de programmation de Xcas.

5  Analyse

Référence: le livre de Demailly. 201, 204, 214, 219, 227, 402, 406, 416, 421, 430.

5.1  Dichotomie

Recherche de solutions de f(x)=0f(x)=0 sur [a,b][a,b] sachant que f(a)f(b)<0f(a)f(b)&lt;0.

Solution : cf. la section 8.5 ou dans Xcas pour Firefox dans Doc, Exemple lycée ou dans le manuel Algoseconde

5.2  Méthode du point fixe

Recherche de solutions de f(x)=xf(x)=x par étude de la suite u n+1=f(u n)u_{n+1}=f(u_n). Cf. la section 8.5 Exemple, résolution de l’équation du temps en mécanique céleste xesin(x)=y,e[0,1[x - e \sin(x) = y, \ e \in [0,1[.

Exercice 1
Écrire un programme iter prenant en argument la fonction ff, la valeur de u 0u_0, de NN et de ε\varepsilon, et qui s’arrête dès que l’une des conditions suivantes est satisfaite :

Dans le premier cas le programme renverra la valeur de u n+1u_{n+1}, dans le second cas une séquence composée de u Nu_N et de NN.
Tester votre programme avec f(x)=2+xf(x)=\sqrt{2+x} et f(x)=x 2f(x)=x^2.


On suppose que la fonction ff satisfait aux hypothèses du théorème du point fixe. On notera k<1k&lt;1 la constante de contractance. On peut alors trouver un encadrement de la limite ll de la suite (u n)(u_n) en fonction de u nu_n, u n1u_{n-1} et kk.


Exercice 2
Écrire un programme iter_k prenant en argument la fonction ff, la valeur de u 0u_0, la constante kk et l’écart toléré ε\varepsilon, et qui s’arrête dès que |u nl|ε| u_n - l | \le \varepsilon.

Vérifier les hypothèses du théorème du point fixe pour f(x)=3cos(x/4)f(x)=3\cos(x/4) sur [0,3][0,3] et expliciter une constante de contractance kk. Déterminer une valeur approchée de la limite de (u n)(u_{n}) à 10 310^{-3} près en utilisant la fonction iter_k.


La convergence de ces suites est en général linéaire, le nombre de décimales exactes augmente de la même valeur à chaque itération. Par contre lorsqu’on est prêt d’une racine, la méthode de Newton permet en gros de multiplier par deux le nombre de décimales à chaque itération.


Exercice 3

  1. Donner une suite itérative obtenue par la méthode de Newton convergeant vers 5\sqrt{5}.
  2. Montrer que la fonction f:R +R +f \colon \R_+ \to \R_+ définie par f(x)=5x+5x+5 f(x)=\frac{5x+5}{x+5} admet 5\sqrt{5} pour point fixe. Trouver un intervalle II contenant 5\sqrt{5} sur lequel les hypothèses du théorème du point fixe sont satisfaites et expliciter une constante de contractance kk.
  3. Comparer au tableur la vitesse de convergence des 10 premiers termes des deux suites (calculez les avec par exemple 100 chiffres significatifs et faites les différence entre 2 termes successifs).
  4. En utilisant la fonction iter, trouver un encadrement de 5\sqrt{5} à 10 610^{-6} près par les deux méthodes (on pourra prendre une valeur initiale approchée puis entière exacte pour avoir une valeur numérique approchée puis une fraction). Combien d’itérations sont nécessaires?


Dans certains cas, la fonction ff n’est pas contractante, mais on peut réécrire l’équation à résoudre sous une autre forme avec une fonction contractante, par exemple en utilisant une fonction réciproque.


Exercice 4
Donner un encadrement à 10 610^{-6} près d’une racine de l’équation tan(x)=x\tan(x)=x sur l’intervalle ]5π/2,7π/2[]5\pi/2,7\pi/2[ en utilisant une méthode de point fixe.

Solution (point fixe) :

fonction iter(f,u0,N,eps)
  local u,v,j;
  u:=evalf(u0); // pas de calcul exact
  pour j de 1 jusque N faire
    v:=f(u);
    si abs(u-v)<eps alors return v; fsi;
    u:=v;
  fpour;
  return "pas de convergence";
ffonction:;

onload


En Python :

def fixe(f,u0,N,eps):
  # local j,u1
  u0=u0*1.0 
  for j in range(N):
    u1=f(u0)
    if abs(u1-u0)<eps*abs(u0):
      return u1,j
    u0=u1
  return "Pas de convergence"

onload

5.3  Méthode de Newton

u n+1=u nf(u n)f(u n) u_{n+1}=u_n-\frac{f(u_n)}{f'(u_n)} Programmation de la méthode de Newton (voir Xcas en ligne, Exemples). Utilisation de la convexité pour prouver la convergence (voir le manuel Algorithmes de Xcas).

Exemple : racine carrée, recherche des racines d’un polynôme (illustration avec l’utilisation du calcul formel pour prouver la convexité), bassins d’attraction des racines.

Solution (Newton) :

fonction newt(f,u0,N,eps)
  local u,v,g,j;
  u:=evalf(u0); // pas de calcul exact
  g:=id-f/f'; // fonction a iterer
  pour j de 1 jusque N faire
    v:=g(u);
    si abs(u-v)<eps alors return v; fsi;
    u:=v;
  fpour;
  return "pas de convergence";
ffonction:;

onload

Python n’étant pas un langage formel on ne peut pas faire tourner l’équivalent (en tout cas sans addition de modules externe). On peut bien sur saisir un programme en syntaxe Python dans Xcas (par exemple en traduisant le programme ci-dessus avec la commande python(newt)).

5.4  Intégration numérique

Rectangles, trapèzes, Simpson. Programmation ou/et illustration. Majoration de l’erreur (illustration possible avec calcul formel pour calcul exact de l’intégrale). Exemple : la méthode des trapèzes

fonction trap(f,a,b,N)
  // trapezes pour la fonction f sur [a,b] N subdivisions
  local h,j,r;
  h:=evalf((b-a)/N);
  r:=1/2*(f(a)+f(b));
  pour j de 1 jusque N-1 faire
    r += f(a+j*h);
  fpour;
  return h*r;
ffonction:;

onload
On teste avec f(x)=expx 2f(x)=\exp{-x^2} sur [0,1][0,1] pour différentes valeurs de NN, par exemple 100 et 1000, observez que l’erreur est grosso-modo proportionnelle à 1/N 21/N^2 :

En Python :

def trap(f,a,b,N):
    # local h,j,r
    h=(b-a)/(1.0*N) # 1.0 permet la compatibilite Python 2 et 3
    r=1/2*(f(a)+f(b))
    for j in range(1,N):
        r+=f(a+j*h)
    return h*r

onload

Exercice 1 : Calculer une valeur approchée de 0 1dx1+x \int_0^1 \frac{dx}{1+x} par la méthode des rectangles, du point milieu et des trapèzes en utilisant un pas de 1/101/10 et de 1/1001/100 (vous pouvez la fonction plotarea ou utiliser le tableur ou écrire un programme effectuant ce calcul avec comme arguments la fonction, la borne inférieure, la borne supérieure et le nombre de subdivision). Observez numériquement la différence entre les valeurs obtenues et la valeur exacte de l’intégrale.

Exercice 2
Calculer le polynôme interpolateur PP de Lagrange de f(x)=11+x 2f(x)=\frac{1}{1+x^2} aux points d’abscisse j4\frac{j}{4} pour jj variant de 0 à 4. Donner un majorant de la différence entre PP et ff en un point x[0,1]x \in [0,1]. Représenter graphiquement ce majorant. Calculer une majoration de l’erreur entre l’intégrale de ff et l’intégrale de PP sur [0,1][0,1]. En déduire un encadrement de π/4\pi/4.

Exercice 3
On reprend le calcul de 0 1dx1+x\int_0^1 \frac{dx}{1+x} mais en utilisant un polynôme interpolateur de degré 4 sur NN subdivisions de [0,1][0,1] (de pas h=1/Nh=1/N). Déterminer une valeur de NN telle que la valeur approchée de l’intégrale ainsi calculée soit proche à 10 810^{-8} près de ln(2)\ln(2). En déduire une valeur approchée à 10 810^{-8} de ln(2)\ln(2).
Même question pour 0 1dx1+x 2\int_0^1 \frac{dx}{1+x^2} et π/4\pi/4 (pour majorer la dérivée nn-ième de 11+x 2\frac{1}{1+x^2}, on pourra utiliser une décomposition en éléments simples sur C\C).

5.5  Équations différentielles

Résolution numérique : méthode d’Euler explicite (ou implicite) illustration avec interactive_odeplot ou/et programmation.

fonction Euler(f,t0,t1,N,y0)
  // y'=f(t,y) avec f(t0)=y0, calcul de f(t1)
  local h,y,j;
  h:=(t1-t0)/N; // pas
  y:=evalf(y0);
  pour j de 0 jusque N-1 faire
    y += h*f(t0+j*h,y); // y(t+h)=y(t)+h*y'
  fpour;
  return y;
ffonction:;



En Python

def Eulerpy(f,t0,t1,N,y0):
  # local j,h,t,y
  h=(t1-t0)/(N*1.0)
  y=y0
  for j in range(N): 
    t = t0+j*h
    y += f(t,y)*h
  return y

onload

Voir la section 14 du manuel Algorithmes qui contient aussi des méthodes de résolution exacte d’équations différentielles, et des exemples venant de la physique.

Exemple : allure des solutions d’un système différentiel linéaire à coefficients constants :




L’étude qualitative près d’un point d’équilibre d’un système autonome se fait en linéarisant en ce point.

5.6  Propriétés métriques des courbes

Voir la section 10 du manuel Algorithmes de Xcas.

5.7  Séries entières

Exercice 1.

  1. Rappeler le développement de Taylor T 2n(x)T_{2n}(x) au voisinage de x=0x=0 de f(x)=cos(x)f(x)=\cos(x) à l’ordre 2n2n.
  2. Tracer sur un même graphique les graphes des fonctions ff et T 2,T 4,T 6,T 8T_2, T_4, T_6, T_8
  3. Graphiquement on voit que T 8(x)T_8(x) approche cos(x)\cos(x) : sur quel intervalle cette approximation vous paraît-elle acceptable ?
  4. Donner une majoration du reste R 2n(x)R_{2n}(x) du développement de Taylor de ff à l’ordre 2n2n, où f(x)=T 2n(x)+R 2n(x)f(x)=T_{2n}(x)+R_{2n}(x).
  5. On prend T 8(x)T_8(x) comme valeur approchée de cos(x)\cos(x) pour x[1,1]x \in [-1,1].

    Donner une majoration indépendante de xx de l’erreur commise.

    (A titre d’illustration, tracer la différence T 8(x)cos(x)T_8(x)-\cos(x).)

  6. En déduire un encadrement de cos(1)\cos(1).


Exercice 2. On veut approcher sin(x)\sin(x) à 1e-6 près en utilisant des développements en séries entières.

  1. Déterminer le plus petit kk tel que: T 2k+1(x)= j=0 k(1) jx 2j+1(2j+1)! T_{2k+1}(x)=\sum_{j=0}^k (-1)^{j}\frac{x^{2j+1}}{(2j+1)!} réalise cette approximation sur [0,π/4][0,\pi/4].
  2. Écrire une fonction qui calcule une valeur approchée à 1e-6 de sin(x)\sin(x) sur [100,100][-100,100] en justifiant et en effectuant les étapes suivantes:
    • on retire un multiple entier de π\pi (obtenu par arrondi de x/πx/\pi) pour se ramener à l’intervalle [π/2,π/2][-\pi/2,\pi/2] (on discutera sur l’erreur commise)
    • si xx est négatif, on remplace xx par x-x (que devient sin(x)\sin(x)?)
    • lorsque x[0,π/4]x \in [0,\pi/4], on utilise le développement en séries ci-dessus.
    • lorsque x[π/4,π/2]x \in [\pi/4,\pi/2], on se ramène au développement de l’exercice précédent en appliquant la formule sin(x)=cos(π/2x)\sin(x)=\cos(\pi/2-x).
  3. Afin de tester votre fonction ff et d’attraper d’éventuelles erreurs grossières, faites afficher le graphe de ff, disons sur l’intervalle [10,10][-10,10], puis le graphe de la différence fsinf-\sinsin\sin est la fonction déjà implémentée dans Xcas.


Exercice 3

  1. Pour x>0x&gt;0 exprimer arctan(x)\arctan(-x) en fonction de arctan(x)\arctan(x). Calculer la dérivée de arctan(x)+arctan(1/x)\arctan(x)+\arctan(1/x), en déduire arctan(1/x)\arctan(1/x) en fonction de arctan(x)\arctan(x) pour x>0x&gt;0. Montrer que le calcul de arctan(x)\arctan(x) sur R\R peut se ramener au calcul de arctan(x)\arctan(x) sur [0,1][0,1].
  2. Rappeler le développement en séries entières de arctan(x)\arctan(x) en x=0x=0, et son rayon de convergence. Soit α[0,1]\alpha \in [0,1], montrer que αα 33+α 55α 77arctan(α)αα 33+α 55 \alpha-\frac{\alpha^3}{3}+\frac{\alpha^5}{5} - \frac{\alpha^7}{7} \leq \arctan(\alpha) \leq \alpha-\frac{\alpha^3}{3}+\frac{\alpha^5}{5} en déduire que la méthode de Newton appliquée à l’équation tan(x)α=0\tan(x)-\alpha=0 avec comme valeur initiale αα 33+α 55\alpha-\frac{\alpha^3}{3}+\frac{\alpha^5}{5} est une suite décroissante qui converge vers arctan(α)\arctan(\alpha).
  3. Déterminez par cette méthode une valeur approchée à 1e-8 près de π/4=arctan(1)\pi/4= \arctan(1).
  4. On pourrait calculer π/4\pi/4 avec la même précision en utilisant le développement en séries de la formule de Machin π4=4arctan(15)arctan(1239) \frac{\pi}{4} = 4 \arctan(\frac{1}{5}) - \arctan(\frac{1}{239}) Combien de termes faudrait-il calculer dans le développement des deux arctangentes?

Exercice 4

  1. Écrire le développement en séries entières au voisinage de x=0x=0 de: g(x)=e x1x g(x)=\frac{e^{-x}-1}{x}
  2. On veut calculer une valeur approchée de I= 0 1g(x)dx I=\int_0^1 g(x) \ dx En utilisant le développement de gg, écrire II sous la forme d’une série j=0 v j\sum_{j=0}^\infty v_j.
  3. Soit R n= j=n+1 v jR_n=\sum_{j=n+1}^\infty v_j le reste de cette série. Donner une majoration de |R n||R_n|.
  4. En déduire un encadrement de II faisant intervenir j=0 nv j\sum_{j=0}^n v_j. Calculer explicitement cet encadrement lorsque n=10n=10.

5.8  Accélération de convergence

Méthode de Richardson lorsqu’on connait le développement asymptotique d’une suite convergeant vers la limite. Par exemple pour la constante d’Euler, cf. le manuel de programmation de Xcas.

Cas particulier : convergence de la méthode de trapèzes : méthode de Romberg pour approcher numériquement une intégrale.

Autres : méthode du Δ 2\Delta^2 d’Aitken, séries alternées (théorie voir le texte 585 de l’option C de l’agrégation externe, cf. la session du menu Exemples, analyse de Xcas).

6  Algèbre linéaire

Référence: dans Xcas, menu Aide, puis manuel, puis Programmation (pour le pivot de Gauss) ou Algorithmes de calcul formel section 20.

Exposés : 113, 114, 115 Exercices : 309, 314, 315

6.1  Pivot de Gauss et applications

6.2  Programmation

On rappelle qu’en mode Xcas, les indices commencent à 0 (en mode maple les indices commencent à 1). Etant donné une matrice MM ayant LL lignes et CC colonnes, on demande de programmer l’algorithme du pivot de Gauss que l’on rappelle :

  1. Initialiser la ligne courante ll et la colonne courante cc à 0
  2. Tant que l<Ll&lt;L et c<Cc&lt;C faire
  3. Chercher dans la colonne cc à partir de la ligne ll un coefficient non nul (appelé pivot)
  4. S’il n’y en a pas, incrémenter cc et revenir à l’étape 2
  5. S’il y en a un, échanger la ligne ll avec la ligne du pivot (rowSwap(matrice,l1,l2))
  6. Pour les lignes jj variant de l+1l+1 à L1L-1 ou de 0 à L1L-1 à l’exclusion de la ligne ll (selon que l’on effectue une réduction sous-diagonale ou complète), remplacer la ligne L jL_j par L jαL lL_j-\alpha L_lα\alpha est calculé pour annuler le coefficient de la colonne cc de L jL_j (mRowAdd(coeff,matrice,l1,l2))
  7. Incrémenter ll et cc et revenir à l’étape 2.
  8. Normaliser à 1 le premier coefficient non nul de chaque ligne (en divisant la ligne par ce coefficient)

Voir le manuel de programmation de Xcas pour une solution.

6.3  Inverse d’une matrice

Pour calculer l’inverse d’une matrice MM carrée de taille nn, on peut résoudre simultanément nn systèmes linéaires du type Mx k=y kMx_k=y_ky ky_k représente (en colonne) les coordonnées du kk-ième vecteur de la base canonique pour kk variant de 1 à nn. On écrit donc la matrice MM puis les colonnes des coordonnées de ces nn vecteurs, donc la matrice identité de taille nn. On réduit complètement la matrice par l’algorithme du pivot de Gauss. Si MM est inversible, les nn premières colonnes après réduction doivent être la matrice identité de taille nn, alors que les nn colonnes qui suivent sont les coordonnées des x kx_k donc ces nn colonnes constituent M 1M^{-1}. On peut aussi utiliser la factorisation LULU de la matrice AA et résoudre les nn systèmes avec cette factorisation.
Écrire un programme de calcul d’inverse de matrice par cet algorithme.

6.4  Noyau d’une application linéaire

On présente ici deux méthodes, la première se généralise au cas des systèmes à coefficients entiers, la deuxième utilise un peu moins de mémoire (elle travaille sur une matrice 2 fois plus petite).

Première méthode Soir MM la matrice dont on cherche le noyau. On ajoute à droite de la matrice transposée de MM une matrice identité ayant le même nombre de lignes que M tM^t. On effectue une réduction sous-diagonale qui nous amène à une matrice composée de deux blocs (M tI n)(UL˜) ( M^t I_n ) \ \rightarrow \ ( U \tilde{L} ) Attention, L˜\tilde{L} n’est pas la matrice LL de la décomposition LULU de M tM^t, on a en fait L˜M t=U \tilde{L} M^t = U donc ML˜ t=U t M \tilde{L}^t = U^t Les colonnes de L˜ t\tilde{L}^t correspondant aux colonnes nulles de U tU^t (ou si on préfère les lignes de L˜\tilde{L} correspondant aux lignes nulles de UU) sont donc dans le noyau de MM et réciproquement si Mv=0Mv=0 alors U t(L˜ t) 1v=0 U^t (\tilde{L}^t)^{-1} v =0 donc, comme UU est réduite, (L˜ t) 1v(\tilde{L}^t)^{-1} v est une combinaison linéaire des vecteurs de base d’indice les lignes nulles de UU. Finalement, les lignes de L˜\tilde{L} correspondant aux lignes nulles de UU forment une base du noyau de MM.

On peut faire le raisonnement ci-dessus à l’identique si MM est une matrice à coefficients entiers, en effectuant des manipulations élémentaires réversibles dans \mathbb{Z}, grâce à l’idendité de Bézout. Si aa est le pivot en ligne ii, bb le coefficient en ligne jj à annuler, et u,v,du, v, d les coefficients de l’identité de Bézout au+bv=da u + b v =d on fait les changements : L iuL i+vL j,L jbdL i+adL j L_i \leftarrow uL_i +v L_j, \quad L_j \leftarrow -\frac{b}{d} L_i + \frac{a}{d} L_j qui est réversible dans \mathbb{Z} car le déterminant de la sous-matrice élémentaire correspondante est |u v bd ad|=1 \left| \begin{array}{cc} u & v \\ -\frac{b}{d} & \frac{a}{d} \end{array} \right| = 1 Cette réduction (dite de Hermite) permet de trouver une base du noyau à coefficients entiers et telle que tout élément du noyau à coefficient entier s’écrit comme combinaison linéaire à coefficients entiers des éléments de la base.

Deuxième méthode On commence bien sûr par réduire la matrice (réduction complète en-dehors de la diagonale), et on divise chaque ligne par son premier coefficient non nul (appelé pivot). On insère alors des lignes de 0 pour que les pivots (non nuls) se trouvent sur la diagonale. Puis en fin de matrice, on ajoute ou on supprime des lignes de 0 pour avoir une matrice carrée de dimension le nombre de colonnes de la matrice de départ. On parcourt alors la matrice en diagonale. Si le ii-ième coefficient est non nul, on passe au suivant. S’il est nul, alors tous les coefficients d’indice supérieur ou égal à ii du ii-ième vecteur colonne v iv_i sont nuls (mais pas forcément pour les indices inférieurs à ii). Si on remplace le ii-ième coefficient de v iv_i par -1, il est facile de se convaincre que c’est un vecteur du noyau, on le rajoute donc à la base du noyau. On voit facilement que tous les vecteurs de ce type forment une famille libre de la bonne taille, c’est donc bien une base du noyau.

6.5  Factorisation PA=LUPA=LU

Voir l’explication de la factorisation LULU section 20.4 du manuel Algorithmes de Xcas.
La commande lu de Xcas renvoie P,L,UP code la permutation PP (on donne la liste des images des entiers de 00 à n1n-1). La commande linsolve(P,L,U,b) permet de résoudre le système linéaire Ax=bAx=b en utilisant la décomposition LULU de AA donc en effectuant O(n 2)O(n^2) opérations (résolution de deux systèmes triangulaires Ly=PbLy=Pb et Ux=yUx=y).

6.6  Algorithme de Gauss-Bareiss (hors programme)

Lorsque les coefficients de la matrice M=(m j,k) 0j<L,0k<CM=(m_{j,k})_{0 \leq j &lt;L, 0 \leq k &lt; C} sont entiers, on peut souhaiter éviter de faire des calculs dans les rationnels, et préférer utiliser une combinaison linéaire de lignes ne faisant intervenir que des coefficients entiers. On peut par exemple effectuer l’opération (où l,cl,c désignent la ligne et colonne du pivot) L jm l,cL jm j,cL l L_j \leftarrow m_{l,c} L_j - m_{j,c} L_l Tester la taille des coefficients obtenus pour une matrice carrée aléatoire de taille 5 puis 10. L’idée est-elle bonne ?

On peut montrer qu’on peut toujours diviser par le pivot utilisé pour réduire la colonne précédente (initialisé à 1 lors de la réduction de la première colonne) L j1p \small prec(m l,cL jm j,cL l) L_j \leftarrow \frac{1}{p_{\mbox{\small prec}}}(m_{l,c} L_j - m_{j,c} L_l) Tester à nouveau sur des matrices carrées de taille 5, 10, vérifier que les calculs sont bien effectués dans \mathbb{Z}. Comparer le dernier coefficient en bas à droite avec le déterminant de la matrice (si vous avez vu les propriétés des déterminants, démontrez ce résultat. Plus difficile: en déduire qu’on peut bien diviser par le pivot de la colonne précédente en considérant des déterminants de matrices extraites)

6.7  Exercices

Exercice 1
Calcul de la somme de deux sous-espaces vectoriels.
On donne deux sous-espaces vectoriels E 1E_1 et E 2E_2 de R n\R^n par deux familles géneratrices (c’est-à-dire une liste de vecteurs), il s’agit d’écrire un algorithme permettant

On pourra utiliser les fonctions rref ou/et ker de Xcas. Tester avec deux sous-espaces de dimension 2 de R 5\R^5. N’oubliez pas de rédiger une justification mathématique de la méthode mise en oeuvre.

Exercice 2
Calcul de l’intersection de deux sous-espaces vectoriels.
On donne deux sous-espaces vectoriels E 1E_1 et E 2E_2 de R n\R^n par deux familles géneratrices (c’est-à-dire une liste de vecteurs), il s’agit d’écrire un algorithme permettant de trouver une base de E 1E 2E_1 \cap E_2. On pourra utiliser les fonctions rref ou/et ker de Xcas. Tester avec 2 sous-espace de dimension 3 de R 4\R^4. N’oubliez pas de rédiger une justification mathématique de la méthode mise en oeuvre.

Exercice 3
Mise en oeuvre du théorème de la base incomplète. On donne une famille de vecteurs de R n\R^n (liste de vecteurs), il s’agit d’écrire un algorithme permettant d’extraire une base du sous-espace engendré, puis de compléter par des vecteurs afin de former une base de R n\R^n tout entier, et enfin d’écrire un vecteur de R n\R^n comme combinaison linéaire des vecteurs de la base complétée. On pourra utiliser les fonctions rref ou/et ker de Xcas. Tester avec une famille de 3 vecteurs de R 5\R^5. N’oubliez pas de rédiger une justification mathématique de la méthode mise en oeuvre.

6.8  Déterminants

Calcul par réduction. Autres algorithmes (à la limite du programme) : développement intelligent (2 n2^n opérations), modulaire (si les coefficients sont dans \mathbb{Z}).

6.9  Polynome minimal, caractéristique

On propose ici quelques algorithmes de calcul du polynôme minimal MM et/ou caractéristique PP d’une matrice carrée AA de taille nn. On peut bien sur calculer le polynôme caractéristique en calculant directement le déterminant (par exemple avec l’algorithme de Gauss-Bareiss pour éviter les fractions de polynômes), mais c’est souvent plus couteux que d’utiliser un des deux algorithmes ci-dessous.

6.9.1  Interpolation de Lagrange

On sait que le degré de PP est nn, il suffit donc de connaitre la valeur de PP en n+1n+1 points distincts pour connaitre PP. Par exemple, on calcule P(k)P(k) pour k=0,...,nk=0,...,n, et en utilisant l’instruction lagrange de Xcas, on en déduit le polynôme caractéristique. Programmer cet algorithme et testez votre programme en comparant le résultat de votre programme et de l’instruction charpoly de Xcas sur quelques matrices.

6.9.2  Algorithme probabiliste.

Cet algorithme permet de calculer le polynôme caractéristique CC dans presque tous les cas, en recherchant le polynôme minimal MM de AA (on note mm le degré de MM).

On sait que M(A)=0M(A)=0, donc pour tout vecteur vv, M(A)v=0M(A)v=0. Si M(x)= k=0 mM kx kM(x)=\sum_{k=0}^{m} M_k x^k, alors 0=M(A)v= k=0 mM kA kv 0 = M(A)v=\sum_{k=0}^{m} M_k A^k v On va donc rechercher les relations linéaires qui existent entre les n+1n+1 vecteurs v,...,A nvv, ..., A^nv. Cela revient à déterminer le noyau KK de l’application linéaire dont la matrice a pour colonnes v,...,A nvv,...,A^nv. On sait que le vecteur (M 0,...,M m,0,...,0)R n+1(M_0,...,M_m,0,...,0) \in \R^{n+1} des coefficients de MM (complété par des 0 si m<nm&lt;n) appartient à ce noyau KK. Si le noyau KK est de dimension 1, alors m=nm=n, et les coefficients de MM sont proportionnels aux coefficients du vecteur de la base du noyau calculé. On en déduit alors le polynôme minimal MM et comme m=nm=n, et aussi le polynôme caractéristique C=MC=M.

Programmer cet algorithme en prenant un vecteur vv aléatoire. Attention, pour calculer A kvA^kv on formera la suite récurrente v k=Av k1v_k=Av_{k-1}, pourquoi?

Si on n’a pas de chances dans le choix de vv, on trouvera un noyau de dimension plus grande que 1 bien que le polynome minimal soit de degré nn. On peut alors recommencer avec un autre vecteur. On peut aussi chercher la relation de degré minimal pour un vv donné (elle apparait automatiquement comme premier vecteur de la base dans l’algorithme de calcul du noyau donné au TP2), prendre le PPCM PP des polynomes pour 2 ou 3 vecteurs aléatoires et conclure s’il est de degré nn. Programmer cette variante.

Si le polynome minimal est de degré m<nm&lt;n, on peut tester si le PPCM PP est le polynome minimal en calculant P(A)P(A) mais ce calcul est couteux. On peut aussi faire confiance au hasard, supposer que le polynome minimal est bien M=PM=P et essayer de déterminer C/MC/M par d’autres moyens, par exemple la trace si n=m+1n=m+1. On dispose alors d’un moyen de vérification en calculant l’espace caractéristique correspondant à la valeur propre double. Programmer cette variante.

Algorithme de Fadeev (hors programme, référence, manuel algorithmes de calcul formel).

6.10  Méthode de la puissance

Si la matrice MM possède une seule valeur propre de module maximal, alors la suite v n+1=Mv nv_{n+1}=Mv_n se rapproche de l’espace propre correspondant. En pratique, on normalise v nv_n pour éviter les débordements numériques. Écrire un programme mettant en oeuvre la méthode de la puissance dans le cas réel (penser à normaliser v nv_n pour éviter les overflow). Utilisez ce programme pour trouver une valeur approchée de la valeur propre de norme maximale par la méthode de la puissance de B tBB \ ^t BBB est une matrice aléatoire. Trouver la plus grande racine en module d’un polynôme en appliquant à la matrice companion.

Solution :

fonction pui(A,eps,N) 
  // A la matrice, eps la precision, N nombre maximum d'iterations
  local j,n,v,w,l;
  n:=size(A); // taille de la matrice
  v:=ranv(n,uniformd,-1,1); // vecteur aleatoire
  v:=normalize(v); // de norme 1
  pour j de 1 jusque N faire
    w:=A*v;
    l:=dot(w,v); // valeur propre si v vecteur propre normalise
    si l2norm(w-l*v)<eps alors return l,v,j; fsi;
    v:=normalize(w);
  fpour;
  return "pas de convergence";
ffonction:;

onload


6.11  Factorisation QRQR

La factorisation QRQR d’une matrice (écriture comme produit d’une matrice orthogonale/unitaire et d’une matrice triangulaire supérieure) sert à calculer simultanément toutes les valeurs propres (approchées) d’une matrice, commande Xcas qr. L’idée est de poser A=QRA=QR puis A 1=RQA_1=RQ et de recommencer, on peut montrer qu’il y a convergence vers une matrice (presque) diagonale. Pour optimiser les itérations, on utilise la méthode QRQR implicite ou algorithme de Francis sur la forme de Hessenberg de la matrice, c’est la commande schur qui fait ce calcul dans Xcas, P,H:=schur(A) renvoie dans P une matrice orthogonale (ou unitaire) et dans H une matrice (presque) diagonale telles que A=PHP 1=PHP *A=PHP^{-1}=PHP^*. Cet algorithme peut servir pour la lecon 150, et aussi pour la lecon 168 pour la matrice companion d’un polynome.

7  Autres idées d’algorithmes.

7.1  Permutations

Représentation par la liste des images ou par une liste de cycles, chaque cycle étant la liste des éléments du cycle. Composition, inverse, décomposition en cycles.

7.2  Méthode de Monte-Carlo

Il s’agit d’un algorithme probabiliste pour déterminer la valeur approchée d’une intégrale a bf(t)dt\int_a^b f(t) \ dt. Le principe : on tire au hasard selon la loi uniforme sur [a,b][a,b] N réels x 1,...,x Nx_1,...,x_N, et on fait la moyenne des f(x i)f(x_i). On a convergence pour N+N \rightarrow +\infty vers 1/(ba) a bf(t)dt1/(b-a)\int_a^b f(t) \ dt. La convergence est lente en 1/N1/\sqrt{N} donc cette méthode est peu utile en dimension 1, par contre en dimension grande, elle est beaucoup plus efficace que des quadratures classiques. Illustration avec 0 2e t 2dt\int_0^2 e^{-t^2} \ dt




On fait une expérience avec N=400N=400





On fait une série d’expériences (500 ici) et on trace l’histogramme des valeurs approchées, que l’on compare avec le graphe de la loi normale de moyenne μ\mu et d’écart-type





En pratique, on estime ss par stddevp(w)/sqrt(N)

7.3  Calcul de π\pi par polygones

Encadrement de π\pi par un polygone régulier inscrit et par un polygone extérieur.

7.4  Calcul probabiliste de π\pi

En prenant un couple de nombres aléatoires entre -1 et 1, on regarde si le couple est dans le disque de rayon 1, et on calcule la proportion.

7.5  Fluctuations

7.5.1  Loi discrète

Expérience : on tire nn fois au hasard une boule dans une urne avec remise, la proportion de boules noires dans l’urne étant pp (proche de 0.5), on compte le nombre de boules noires. On effectue NN fois l’expérience. On compte le nombre de fois où la proportion de boules noires observée est dans un intervalle centré en pp de taille proportionnelle à 1/n1/\sqrt{n} (par exemple [p1/n,p+1/n][p-1/\sqrt{n},p+1/\sqrt{n}]). On peut aussi représenter graphiquement par des segments horizontaux les intervalles proportion de boules observées ±1/n\pm 1/\sqrt{n} et tracer verticalement la droite d’abscisse pp.

7.5.2  Loi continue

Expérience : on ajoute nn réels tirés au hasard pris entre 0 et 1 (loi uniforme, ou autre loi), par exemple pour n=30n=30. On effectue NN fois l’expérience (par exemple N=1000N=1000), et on trace un histogramme des résultats, et sur le même graphique on représente la loi normale de moyenne l’espérance de la loi et d’écart-type l’écart-type de la loi divisé par n\sqrt{n}.

7.6  Tracé de courbes

Par discrétisation.

8  Exemples d’exercices pour l’oral 2.

Remarques :

8.1  Écriture en base 22 et puissance rapide modulaire.

Ne convient plus.

Énoncé : : le but de l’exercice est de calculer rapidement a na^n modulo ppa,n,pa,n,p sont 3 entiers avec 0a<p0 \leq a &lt; p.

  1. Soit nn un entier et n= j=0 kn j2 j,n j{0,1} n= \sum_{j=0}^k n_j 2^j, \quad n_j \in \{ 0,1 \} sa décomposition en base 2. Écrire un algorithme qui renvoie la liste des n jn_j.
  2. On calcule a j=a 2 ja_j=a^{2^j} modulo pp successivement pour j=2..kj=2..k par a j=a 2 j(modp)=(a 2 j1(modp)) 2(modp) a_j=a^{2^j} \pmod p = (a^{2^{j-1}} \pmod p)^2 \pmod p Calculer a n(modp)a^n \pmod p en fonction des a ja_j et n jn_j. Quel est le nombre d’opérations à effectuer ? Comparer avec le nombre d’opérations à effectuer en faisant a×a×...×a(modp)a \times a \times ... \times a \pmod p.
  3. Écrire un algorithme permettant de calculer a na^n modulo pp par cet algorithme.

Solution :
1. On observe que n 0n_0 est le reste de la division euclidienne de nn par 2, n 1n_1 s’obtient à partir du quotient euclidien de nn par 2 de la même façon que n 0n_0 à partir de nn et donc si on remplace nn par le quotient euclidien de nn par 2, n 1n_1 est alors le reste de la division euclidienne de nn par 2 ... D’où le programme Xcas/Python :

def base2(n):
    # local l
    l=[]
    while n>0 :        
        l.append(n % 2)
        n = n // 2
    return l[::-1] # liste l a l'envers


Exemple et vérification :

L’instruction intégrée Xcas permettant de faire la conversion est convert(n,base,2), elle renvoie la liste des bits à l’envers.
2. On a a n(modp) = a j=0 kn j2 j(modp) = j=0 ka j n j(modp) = 0jk,n j=1a j(modp) \begin{matrix} a^n \pmod p &= &a^{ \sum_{j=0}^k n_j 2^j} \pmod p \\ &= &\prod_{j=0}^k a_j^{n_j} \pmod p \\ &=& \prod_{0\leq j \leq k, n_j =1} a_j \pmod p \end{matrix} Il faut effectuer k1k-1 opérations d’élévation au carré suivi de réduction modulo pp pour calculer les a ja_j, puis effectuer le produit de a ja_j pour les n j=1n_j=1. Au maximum on fait 2k12k-1 produits suivi de réduction modulo pp, où kk est la partie entière du log en base 2 de nn. Ce qui nécessite beaucoup moins d’opérations que de calculer n1n-1 produits suivi de réduction modulo pp.
Il est essentiel d’effectuer les réductions modulo pp après chaque produit et non pas seulement à la fin, sinon la taille des entiers à multiplier augmenterait considérablement, et donc le temps nécessaire pour effectuer une multiplication. Ici, toutes les multiplications se font avec des nombres plus petits que pp, en temps constant donc.
3. On pourrait utiliser la fonction base2 précédente, on peut aussi calculer simultanément les n jn_j et a n(modp)a^n \pmod p. En syntaxe Xcas/Python:

def puimod(a,n,p):
    # local aj,an_modp
    aj=a % p
    an_modp=1
    while n>0 :        
        if n % 2==1 :
            an_modp=an_modp*aj % p
        n=n // 2
        aj=aj*aj % p
    return an_modp



Commentaires

8.2  Primalité et petit théorème de Fermat

306

Énoncé :

  1. Soit pp un nombre premier. En utilisant la formule du binôme de Newton, montrer par récurrence que a pa^p est congru à aa modulo pp.
  2. Écrire un algorithme qui teste pour quelques valeurs de aa si a pa^p est congru à aa modulo pp, on renverra aa si pp n’est pas premier, et 0 sinon. Que signifie la valeur 0?
  3. Écrire un algorithme qui détermine le premier entier pp non premier tel que pour tout aa premier avec pp, a pa^p est congru à aa modulo pp (nombre de Carmichael). On pourra utiliser la fonction isprime pour tester si un entier est premier.

Solution :
1. On fait une démonstration par récurrence. On a 0 p=00^p=0 est bien congru à 0 modulo pp. La formule du binôme donne : (a+1) P= j=0 p(pj)a j=1+a p+ j=1 p1(pj) (a+1)^P = \sum_{j=0}^p \left( ^p_j \right) a^j = 1+a^p + \sum_{j=1}^{p-1} \left( ^p_j \right) Dans la somme, les coefficients binomiaux valent k=0 j1(pk)j! \frac{\prod_{k=0}^{j-1} (p-k) }{j!} et sont donc divisibles par pp puisque le numérateur l’est, le dénominateur ne l’est pas et pp est premier. Donc (a+1) P (a+1)^P est congru à a p+1a^p+1 modulo pp donc à a+1a+1 modulo pp par hypothèse de récurrence. 2. Le programme utilisable avec Xcas ou Python

def test(p,nmax):
    # local a
    if nmax>=p-1:
        nmax=p-1
    for a in range(2,nmax+1):
        if pow(a,p,p)!=a :
            return(a)
    return 0


On utilise ici la fonction pow avec 3 arguments (puissance modulaire rapide, synonyme de powmod ici). Le paramètre nmax sert à limiter le nombre d’essais, ici on essaie les entiers de 2 à nmax, mais on pourrait aussi tirer nmax entiers au hasard. La boucle sur aa se poursuit jusqu’à ce que le test de Fermat échoue, return provoque en effet l’arrêt prématuré de la fonction (donc de la boucle) ou va à son terme (test réussi, valeur de retour 0). Exemple

Lorsque la réponse du programme est non nulle, on est assuré que le nombre n’est pas premier, la valeur renvoyée est un certificat de non-primalité (un entier tel que a pa(modp)a^p \neq a \pmod p). Par contre, si la valeur renvoyée est 0, on ne peut pas en déduire que pp est premier (il y a seulement des présomptions).
3. Pour trouver un nombre de Carmichael, on doit tester que a p=a(modp)a^p = a \pmod p pour tous les entiers compris entre 2 et p1p-1 premiers avec pp et on doit de plus tester que pp n’est pas premier. Avec Xcas :

def carmi(nmax):
    # local a,p
    for p in range(3,nmax+1):
        for a in range(2,p):
            if gcd(a,p)==1 and pow(a,p,p)!=a :
                break # si le test de Fermat echoue on arrete la boucle sur a
        if a==p and not(isprime(p)) :
            return(a)
    return "non trouve"


On exécute par exemple

qui renvoie "non trouvé” (il n’y a pas de nombre de Carmichael inférieur à 100) alors que carmi(1000) renvoie après quelques instants 561, le premier nombre de Carmichael. Pour exécuter ce programme en Python, il faut définir au préalable une commande gcd de calcul de PGCD de 2 entiers et une commande isprime qui teste la primalité d’un entier, et il faut faire varier a in range(2,p+1) (en effet si la boucle s’exécute sans interruption, la valeur de sortie de aa varie de 1 entre Xcas et Python).

Commentaires :

8.3  PGCD, PPCM

305

Énoncé : Soient aa et bb 2 entiers. On pose r 0=ar_0=a,r 1=br_1=b, et pour n0n\geq 0 tel que r n+10r_{n+1} \neq 0, on note q n+2q_{n+2} et r n+2r_{n+2} le quotient et le reste de la division euclidienne de r nr_n par r n+1r_{n+1}. On rappelle qu’il existe un (premier) entier NN tel que r N=0r_N= 0, et que pgcd(a,b)=r N1(a,b)=r_{N-1} (dernier reste non nul).

  1. On définit pour n[0,N]n \in [0,N], les suites u nu_n et v nv_n par récurrence u 0=1,u 1=0,u n+2=u nq n+2u n+1,v 0=1,v 1=0,v n+2=v nq n+2v n+1 u_0=1, u_1=0, u_{n+2}=u_n-q_{n+2} u_{n+1}, \quad v_0=1, v_1=0, v_{n+2}=v_n-q_{n+2} v_{n+1} Montrer que au n+bv n=r n au_n+bv_n=r_n
  2. En déduire un algorithme permettant de déterminer des coefficients de l’identité de Bézout au+bv=au N1+bv N1=pgcd(a,b) au+bv=au_{N-1}+bv_{N-1}=\mbox{pgcd}(a,b)
  3. Adapter l’algorithme ci-dessus pour calculer l’inverse de aa modulo bb lorsque aa et bb sont premiers entre eux.
  4. Déterminer en fonction de nn la valeur de u nr n+1u n+1r n u_n r_{n+1}- u_{n+1} r_n En déduire que |au N|=|bv N|=ppcm(a,b)|a u_{N}|=|bv_N|=\mbox{ppcm}(a,b).

Solution

  1. Par récurrence, au rang n=0n=0 et n=1n=1 c’est une conséquence de la définition de r 0,r 1,u 0,u 1,v 0,v 1r_0, r_1, u_0, u_1, v_0, v_1. Pour n2n\geq 2, au n+bv n = a(u n2q nu n1)+b(v n2q nv n1) = au n2+bv n2q n(au n1+bv n1) = r n2q nr n1 = r n \begin{matrix} au_n+bv_n&=&a(u_{n-2}-q_n u_{n-1})+b(v_{n-2}-q_n v_{n-1})\\ &=& au_{n-2}+bv_{n-2}-q_n (au_{n-1}+b v_{n-1})\\ &=&r_{n-2}-q_nr_{n-1} \\ &=& r_n \end{matrix}
  2. On remarque que la relation de récurrence définissant r nr_n, u nu_n et v nv_n est identique, on utilisera une liste pour contenir ces 3 valeurs. On exécute une boucle (avec test d’arrêt sur la valeur de r n+1r_{n+1}), au cours de la boucle La liste l0 contiendra les valeurs de r n,u n,v nr_n,u_n,v_n, l1 les valeurs de r n+1,u n+1,v n+1r_{n+1},u_{n+1},v_{n+1} et l2 les valeurs de r n+2,u n+2,v n+2r_{n+2},u_{n+2},v_{n+2}, en fin de boucle l’incrémentation de nn se traduit par la recopie de l1 dans l0 et de l2 dans l1. Voir les programmes à la section 3.1.2.
  3. L’inverse de aa modulo bb est uu, le coefficient de Bézout de aa dans au+bv=1 au+bv=1 On remarque que la valeur des u nu_n se calcule indépendamment de la valeur des v nv_n, on peut donc écrire un algorithme de calcul d’inverse modulaire un peu plus rapide que l’algorithme de Bézout en ne calculant pas les v nv_n. (N.B.: c’est un des avantages de l’algorithme itératif présenté ici par rapport à l’algorithme récursif présenté par exemple dans le manuel de programmation de Xcas).
  4. On a u n+1r n+2u n+2r n+1 = u n+1(r nq nr n+1)(u nq nu n+1)r n+1 = u n+1r nu nr n+1 = (u nr n+1u n+1r n) \begin{matrix} u_{n+1} r_{n+2}-u_{n+2}r_{n+1} &=& u_{n+1} (r_{n}-q_nr_{n+1})-(u_{n}-q_n u_{n+1})r_{n+1} \\ &=& u_{n+1} r_{n} - u_{n}r_{n+1}\\ &=& -( u_{n}r_{n+1} -u_{n+1} r_{n} ) \end{matrix} Donc u nr n+1u n+1r n=(1) n(u 0r 1u 1r 0)=(1) nb u_{n}r_{n+1} -u_{n+1} r_{n} = (-1)^n (u_{0}r_{1} -u_{1} r_{0} ) =(-1)^n b Au rang n=N1n=N-1, on a donc u Npgcd(a,b)=(1) Nbu_N \mbox{pgcd}(a,b)=(-1)^N b. En multipliant par aa, on a alors u Na=(1) Nabpgcd(a,b)=(1) Nppcm(a,b) u_N a =(-1)^N \frac{ab}{\mbox{pgcd}(a,b)} = (-1)^N \mbox{ppcm}(a,b) On peut faire de même avec v Nv_N ou tout simplement utiliser au N+bv N=0 au_N+bv_N=0 Bien entendu, on ne calculera les cofacteurs du PPCM de cette manière que si on doit calculer les coefficients de Bézout.

Commentaires

8.4  Calcul efficace du polynôme caractéristique

309

Énoncé : Soit AA une matrice carrée d’ordre nn à coefficients complexes. On se propose de déterminer le polynôme caractéristique de AA en recherchant des relations linéaires entre un vecteur v 0v_0, et ses images successives par AA: v k+1=Av kv_{k+1}=Av_k

  1. Montrer que {v 0,...,v n}\{ v_0,...,v_n\} est une famille liée (on pourra donner une combinaison linéaire faisant intervenir les coefficients du polynôme minimal de AA). Déterminer une matrice dont le noyau est le sous-espace vectoriel des coefficients réalisant une combinaison linéaire nulle entre ces vecteurs.
  2. On suppose qu’il existe, à multiplication près, une unique relation linéaire entre ces vecteurs {v 0,...,v n}\{ v_0,...,v_n\}, en déduire le polynôme minimal et caractéristique de AA. Programmer cet algorithme avec un choix au hasard de v 0v_0.
  3. On suppose que la matrice AA a un polynôme minimal de degré nn. Expliquer quelles stratégies permettraient d’améliorer le programme pour tenir compte de choix malchanceux de v 0v_0.

Solution
1. Comme la famille {v 0,...,v n}\{ v_0,...,v_n\} contient n+1n+1 vecteurs dans C n\C^n elle est forcément liée. On peut d’ailleurs donner explicitement une combinaison linéaire nulle, si P(x)= j=0 np jx jP(x)=\sum_{j=0}^n p_j x^j est le polynôme caractéristique de AA, le théorème de Cayley-Hamilton donne P(A)=0P(A)=0, d’où l’on déduit P(A)v=0P(A)v=0 soit j=0 np jv j=0 \sum_{j=0}^n p_j v_j=0 Plus générallement, avoir une combinaison linéaire nulle de coefficients Λ=(λ n,...,λ 0)\Lambda=(\lambda_n,...,\lambda_0) revient à dire que Λ\Lambda est dans le noyau de la matrice BB dont les colonnes sont v n,...,v 0v_n,...,v_0.
2. On a le même type de relation avec le polynôme minimal de AA, donc s’il existe une seule combinaison linéaire à multiplication près, elle est multiple des coefficients du polynôme minimal et de tout polynôme annulateur de AA non nul. Il s’en suit que le degré du polynôme minimal est nn, qu’il est donc égal au polynôme caractéristique et que l’on peut déduire les 2 du calcul du noyau de BB (en multipliant de sorte que le coefficient de v nv_n soit 1 ou (1) n(-1)^n selon la définition adoptée pour le polynôme caractéristique).
L’algorithme va donc choisir un vecteur aléatoire v 0v_0, calculer les v kv_k (attention pour l’efficacité, il faut utiliser la récurrence et surtout ne pas calculer les A kA^k), les mettre en ligne dans une matrice que l’on transpose pour obtenir BB, puis appeler l’instruction ker de calcul du noyau.

fonction polmin(A)
  local k,n,vk,B,noyau;
  n:=size(A); // nombre de lignes
  vk:=ranm(n); // initialise v0 aleatoire (reel)
  B:=[vk]; // initialise B (tranposee)
  pour k de 1 jusque n faire
    vk:=A*vk;
    B[k]:=vk;
  fpour;
  B:=tran(revlist(B)); // vn ... v0
  noyau:=ker(B);
  si size(noyau)>1 alors 
    return "echec de l'algorithme"; 
  fsi;
  return noyau[0];
ffonction:;


On peut le tester avec une matrice aléatoire, par exemple


Le même algorithme nécessite la maitrise de librairies d’algèbre linéaire en Python. Mais on peut bien entendu saisir le programme en syntaxe Python dans Xcas

def polmin(A):
    # local k,n,vk,B,noyau
    n=size(A)
    vk=ranm(n)
    B=[vk]
    for k in range(1,n+1):
        vk=A*vk
        B[k]=vk
    B=tran(revlist(B))
    noyau=ker(B)
    if size(noyau)>1 :
        return "echec de l'algorithme"
    return noyau[0]


3. L’algorithme peut échouer parce que v 0v_0 se trouve dans un sous-espace strict de C n\C^n formé par une somme de sous-espaces caractéristiques, le polynôme minimal relatif à v 0v_0 (obtenu comme premier élément du noyau de BB) est alors un diviseur strict du polynôme minimal. On peut y remédier en ajoutant une boucle extérieure qui effectue un nombre fini d’essais de choix de v 0v_0 (par exemple 3). On peut même améliorer en prenant le PPCM des polynômes minimaux relatifs aux vecteurs v 0v_0 testés.
Néanmoins l’algorithme échouera si le polynôme minimal n’est pas égal au polynôme caractéristique. L’algorithme de Danilevsky ne présente pas cet inconvénient (il est aussi en O(n 3)O(n^3), voir le manuel algorithme de Xcas).

Commentaires

8.5  Exemples de méthodes et d’algorithmes de résolution approchée d’équations F(X)=0F(X)=0.

219, 430

Énoncé :
Soit e[0,1[e\in[0,1[ et t[π,π]t\in[-\pi,\pi] On se propose de résoudre l’équation x=t+esin(x) x=t + e \sin(x) par dichotomie et par la méthode du point fixe et comparer ces deux méthodes. (N.B. ee ne désigne pas la base des logarithmes ici, mais l’excentricité d’une ellipse dont on cherche à résoudre l’équation du temps).

  1. Par dichotomie. Soit f(x)=xtesin(x)f(x)=x-t-e\sin(x). Déterminer le signe de f(πe)f(-\pi-e) et de f(π+e)f(\pi+e), ainsi que le sens de variations de ff, en déduire qu’il existe une unique solution de l’équation. Proposer un algorithme permettant de trouver une valeur approchée de la solution à 1e-8 près. Combien d’étapes sont-elles nécessaires ?
  2. Par le point fixe. Soit g(x)=t+esin(x)g(x)=t+e\sin(x). Montrer que gg est contractante sur [πe,π+e][-\pi-e,\pi+e]. En déduire une suite récurrente convergeant vers l’unique solution de l’équation sur [πe,π+e][-\pi-e,\pi+e]. Proposer un algorithme permettant de trouver une valeur approchée de la solution à 1e-8 près. Combien d’étapes sont-elles nécessaires ?
  3. Comparer la vitesse de ces deux méthodes en fonction de ee.

Solution
1. ff est une fois continument dérivable sur R\R et sa dérivée est f(x)=1ecos(x)>1e>0f'(x)=1-e\cos(x)&gt;1-e&gt;0 donc ff est strictement croissante. De plus f(πe)πet+e0f(-\pi-e) \leq -\pi-e-t+e \leq 0, f(π+e)π+ete0f(\pi +e ) \geq \pi+e-t-e \geq 0 donc ff s’annule une fois et une seule sur l’intervalle [πe,π+e][-\pi-e,\pi+e].

def dicho(f,a,b,eps):
    # local c,niter;
    if f(a)*f(b)>=0: 
        return "erreur: f(a)*f(b)>=0"
    while b-a>eps:
        c=(a+b)/2.0
        if f(a)*f(c)>0:
            a=c
        else:
            b=c
    return [a,b]


Puis on essaie par exemple pour t=1t=1 et e=0.1e=0.1.

Le nombre d’étapes est le plus petit entier nn tel que 2(π+e)2 nε \frac{2(\pi+e)}{2^n} \leq \varepsilon soit : nln(2(π+e)/ε)ln(2) n \geq \frac{\ln(2(\pi+e)/\varepsilon)}{\ln(2)} 2. On a clairement g([πe,π+e])g([-\pi-e,\pi+e]) inclus dans [πe,π+e][-\pi-e,\pi+e]. De plus la dérivée de gg est de valeur absolue au plus ee, indépendant de xx et strictement inférieur à 1. Donc gg est contractante de rapport ee. Le théorème du point fixe assure que la suite récurrente définie par u 0[πe,π+e]u_0\in [-\pi-e,\pi+e] et u n+1=g(u n)u_{n+1}=g(u_n) converge vers l’unique solution de g(x)=xg(x)=x dans [πe,π+e][-\pi-e,\pi+e]. Si ll désigne la solution de l’équation, on a de plus l’estimation à priori : |u nl|2(π+e)e n |u_n-l| \leq 2(\pi+e) e^n Plus générallement, si kk est la constante de contractance, on a l’estimation à postériori : |u nl||u n+1u n|1k |u_n-l| \leq \frac{|u_{n+1}-u_n|}{1-k} qui permet de fournir un test dans l’algorithme pourvu que kk soit passé en paramètre

def fixe(f,u0,k,eps):
    # local u1
    u0=u0*1.0
    u1=f(u0)
    eps=eps*(1-k)
    while (abs(u1-u0))>eps :        
        u0=u1
        u1=f(u0)
    return(u0)


On teste ensuite avec par exemple u 0=0.0u_0=0.0 :

Le nombre d’étapes se majore avec l’estimation à priori nln(2(π+e)/ε)ln(e) n \geq \frac{\ln(2(\pi+e)/\varepsilon)}{-\ln(e)} En réalité, le nombre d’étapes peut être (très) inférieur, car la majoration de la constante de contractance peut être beaucoup trop large lorsqu’on se rapproche du point fixe (par exemple si la dérivée de gg est nulle au point fixe, ce qui serait le cas si on appliquait une méthode de Newton), d’où l’intérêt de l’estimation à postériori utilisée dans l’algorithme.
3. Le nombre d’étapes aboutit à la même formule que pour la dichotomie, à l’exception de ln(2)\ln(2) remplacé par ln(e)-\ln(e). On a donc intérêt à utiliser la dichotomie si la constante e>0.5e&gt;0.5 et le point fixe sinon (avec les mêmes réserves que précédemment si la majoration de |g||g'| par ee au point fixe est beaucoup trop large).

Commentaires

9  Références

Dans la documentation de Xcas (donc disponible le jour de l’oral 2), aller dans le menu Aide, sous-menu Manuels, puis Programmation. Vous y trouverez une grande partie des algorithmes ci-dessus. Le manuel Exercices et le manuel Amusement peuvent aussi contenir des exercices à vocation algorithmique ou illustrable par Xcas. Enfin, le manuel tableur, statistiques peut servir pour une illustration d’exercices de proba-stats. Vous pouvez aussi lancer une recherche avec un mot clef (menu Aide, Rechercher un mot, par exemple Bezout).

En livres :

Sur le web :

10  Aide-mémoire

Instructions Xcas en français
puissance^ ** powmod
quotient, reste euclidieniquo irem
affectationa:=2;
entrée expressionsaisir("a=",a);
entrée chainesaisir_chaine("a=",a);
sortieafficher("a=",a);
valeur retournéeretourne(a);
arrêt dans bouclebreak;
déclaration fonctionf(parametres):={ ... }
alternativesi <condition> alors <inst> fsi;
 si <condition> alors <inst1> sinon <inst2> fsi;
boucle pourpour j de a jusque b faire <inst> fpour;
 pour j de a jusque b pas p faire <inst> fpour;
boucle répéterrepeter <inst> jusqua <condition>;
boucle tantquetantque <condition> faire <inst> ftantque;

Les indices de tableau commencent à 0 avec la notation [] ou à 1 avec la notation [[]], par exemple l:=[1,2]; l[0]; l[[1]]

Instructions Python (utilisables dans Xcas)
puissance** pow(a,n,m)
quotient, reste euclidien// %
affectationa=2
entrée expressiona=input("a=")
sortieprint "a=",a
déclaration fonctiondef f(parametres):
     instructions
valeur retournéereturn a;
arrêt dans bouclebreak;
alternativeif <condition>:
     instructions1
 else:
     instructions2
boucle pourfor j in range(debut,fin,pas):
     instructions
boucle tant quewhile condition:
     instructions

Les indices de tableau commencent à 0, par exemple l=[1,2]; l[0];. Attention, le test d’égalité se fait avec == et non = (affectation).

Instructions Xcas "C-like"
puissance^ ** powmod
quotient, reste euclidieniquo irem
affectationa:=2;
entrée expressioninput("a=",a);
entrée chainetextinput("a=",a);
sortieprint("a=",a);
valeur retournéereturn(a);
arrêt dans bouclebreak;
déclaration fonctionf(parametres):={ ... }
alternativeif (<condition>) {<inst>};
 if (<condition>) {<inst1>} else {<inst2>};
boucle pourfor (j:= a;j<=b;j++) {<inst>}
 for (j:= a;j<=b;j:=j+p) {<inst>}
boucle répéterrepeat <inst> until <condition>;
boucle tantquewhile (<condition>) {<inst>};

Les indices de tableau commencent à 0 avec la notation [] ou à 1 avec la notation [[]], par exemple l:=[1,2]; l[0]; l[[1]]

Instructions Maxima
puissance^ ** power_mod
division euclidienne, restedivide mod
affectationa:2;
sortieprint("a=",a)
valeur retournéereturn(a)
déclaration fonctionf(parametres):=( ... )
alternativeif (<condition>) then <inst>
 if (<condition>) then <inst1> else <inst2>
boucle pourfor j:1 thru 26 do (inst1,inst2)
 for j:2 thru 20 step 2 do (inst,...,inst)
boucle tantquefor i:1 while <condition> do (inst,...,inst)

Les indices de tableau commencent à 1, par exemple l:[1,2]; l[1];

Instructions Xcas en mode Maple
puissance^ ** a&^n mod m
quotient, reste euclidieniquo irem
affectationa:=2;
sortieprint("a=",a);
valeur retournéeRETURN(a);
arrêt dans bouclebreak;
déclaration fonctionf:=proc(parametre) ... end;
alternativeif <condition> then <inst> fi;
 if <condition> then <inst1> else <inst2> fi;
boucle pourfor j from a to b do <inst> od;
 for j from a to b step p do <inst> od;
boucle tantquewhile <condition> do <inst> od;

Les indices de tableau commencent à 1 (Xcas syntaxe mode Maple), par exemple l:=[1,2]; l[1];

Instructions Scilab
affectationa=2
entrée expressiona=input("a=")
sortiedisp("a=",a)
déclaration fonctionfunction nom_var=f(parametres) ... endfunction
valeur retournéenom_var=...;
arrêt dans bouclebreak;
alternativeif <condition> then <inst> end;
 if <condition> then <inst1> else <inst2> end;
boucle pourfor j=debut:fin do <inst> end;
boucle tantquewhile <condition> do <inst> end;

Les indices de tableau commencent à 1, par exemple l=[1,2]; l(1);.