Programmation et calcul polynomial

DEA algorithmique

Attention
Pour visualiser convenablement les formules mathématiques sous netscape, il faut ajouter la ligne suivante à votre fichier .Xdefaults:

Netscape*documentFonts.charset*adobe-fontspecific: iso-8859-1

et redémarrer netscape.

1 Évaluation

Taper la session Maple suivante :

    x:=y;
    x;
    y:=3;
    x;

Pour comprendre comment limiter l'évaluation des expressions Maple, consulter l'aide sur quotes et evaln.

    unassign(x): unassign(y):

Regarder l'aide de eval et taper les instructions ci-dessous :

    a:=v:
    b:=a:
    v:=5:
    a;b;eval(b,1);eval(b,2);
    v:=b+1:
    a;b;v;eval(b,1);eval(b,2);
    v:='b';

Que devrait donner l'évaluation de a ? Utiliser la fonction eval avec deux paramètres pour visualiser le processus d'évaluation.

2 Sous-termes et types

Consulter l'aide sur op, subsop, type, type[structure] et whattype. Soit le polynôme P(X)=(X-Y+1)², quel est le troisième terme de l'expression expansée Q de P? Remplacer l'expression en y finale par z+1. Combien Q a-t-il de termes? Quel est le type de Q, de factor(Q)?

3 Structures de données

3.1 Séquences, listes et ensembles

Maple dispose de structures complexes : les séquences, les listes et les ensembles.

Consulter l'aide sur ce sujet ainsi que sur l'opérateur $. Afficher le cube des entiers entre 10 et 15; afficher tous les produits de nombres compris entre 2 et 5 pour l'un, 3 et 7 pour l'autre; afficher les pgcd de 12 et tous les nombres compris entre 1 et 30. Construire la liste et l'ensemble associés.
Créer la liste [x1,x2,...,x30] de la façon la plus concise possible.
Consulter l'aide de l'itérateur map. Montrer que tout calcul réalisable avec map l'est aussi avec seq.
Soit L = [a₁, ..., a_n] une liste de nombres. Calculer la liste M = [a₁ a₂, a₂ a₃, ..., a_n₁ a_n]. En déduire qu'il existe des calculs réalisables avec seq qui ne le sont pas avec map.

3.2 Tableaux

Consultez l'aide de array et matrix. Créer un tableau vide de nom a ayant dix termes numérotés de 1 à 10. Afficher a. Affecter des valeurs polynomiales en x à a. Créer le tableau b des dérivées en x des termes de a. Rendre les 5 premières valeurs de a inaffectées.

4 Structures de contrôle

Lisez l'aide en ligne disponible pour statement for, if et proc. Consulter ensuite l'aide pour option et local.

Écrire une boucle for pour créer la liste [x1,x2,...,x30]. Quelle est la valeur de votre variable de boucle?
Écrire dans un fichier une procédure qui calcule la suite de Fibonacci (F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-1 pour n ³ 2). Que pouvez-vous faire pour rendre cette fonction efficace sans la dérécursiver? Écrivez une version matricielle du calcul de cette suite. Pensez à utiliser la commande time pour comparer les temps d'exécution. Chercher le premier nombre entier k>1 tel que F_k = k².
Écrire un crible d'Ératosthène.

5 Calcul polynomial

5.1 Remarque sur les opérateurs syntaxiques sur les polynômes

Attention en Maple, le degré degree, la valuation ldegree (pour least degree), les coefficients coeff et coeffs, de tête lcoeff (pour leading coefficient), de queue tcoeff (pour trailing coefficient) sont des informations syntaxiques, comme vous pouvez le constater par :

    degree((x-1)*x-x^2,x);
    ldegree((x+2)*x^2-2*x^2,x);
    degree((exp(a)*exp(-a)-1)*x+2,x);
    lcoeff((exp(a)*exp(-a)-1)*x+2,x);
    tcoeff(x+(exp(a)*exp(-a)-1),x);

Les deux premiers cas se traitent facilement en appliquant collect avant d'appliquer la fonction. Les trois derniers sont plus problématique car il s'agit de deux expressions transcendantes (exp(a) et exp(-a)) mais algébriquement dépendantes qui sont simultanément présentes dans la même expression. combine arrange souvent bien les choses, mais ce n'est pas une solution miracle.

5.2 Petites manipulations

Choisir deux polynômes, consulter l'aide en ligne sur les polynômes, essayer les différentes fonctions sur ces polynômes.

5.3 Exercices

Calculer le résultant des polynômes :
x⁴-3x⁴-2x³+3x²+7x+6
et
x⁴+x²+1.
Sans calculer de pgcd en déduire si ces polynômes ont un facteur commun sur Q[x].
Par quel calcul peut-on déterminer si le polynôme
6x⁴-23x³+32x²-19x+4
a une racine multiple sur C?
Si P et Q sont deux polynômes de degré m et n en x, que vaut Res_x(P,Q)/Res_x(Q,P)?
Soit P(X) un polynôme. Comment peut-on calculer un polynôme de même degré dont les racines complexes sont les carrés des racines de P?

Indication : séparer les parties paire et impaire de P.
Soit P:=(x²+y²)³-4 x² y² et Q =(1+x)y²-(1-x)³. Calculer le résultant de P et Q en x et en y. On veut trouver les points d'intersection des courbes représentatives de P et Q. Utiliser fsolve pour calculer une approximation de ces points.
Écrire une procédure coef qui prend un polynôme en plusieurs variables et une liste [x₁^n₁,x₂^n₂,...] (avec x_i ¹ x_j pour i¹ j) et retourne le coefficient de p en x₁^n₁ x₂^n₂ .... Par exemple, si
p= 3x² y³-7 z x y⁴+9 z² y³-4 x² y
alors coef(p,[x,y⁴]) retourne -7 z.
Écrire une procédure reste(A, B, x) qui calcule le reste de la division euclidienne d'un polynôme A de Q[x] par un polynôme B et mette la valeur du quotient dans la variable éventuellement passée en quatrième argument.

Valérie Ménissier-Morain et Philippe Aubry
Friday 22 October 1999
This document was translated from L^AT_EX by H^EV^EA.