Modélisation et résolutions numérique et symbolique de problèmes via les logiciels Maple et MATLAB

66Construction d’une suite de SturmModélisation et résolutions numérique et symboliquede problèmes via les logiciels Maple et MATLAB0(MODEL) il suffit d’appliquer l’algorithme d’Euclide au couple (f;f )Entrée : Deux polynômes A et B dansK[X ] (oùK est un corps) avecoCours n 5 : Résolution de systèmes bivariés – Algorithme deg(A) deg(B).Sortie : La suite des restes euclidiens.d’Euclide et Algèbre linéaireEuclide1 A = A et A = B0 1Stef Graillat & Mohab Safey El Din 2 Tant que A = 0iA =A remAi+1 i 1 iUniversité Pierre et Marie Curie (Paris 6) i + +3 Retourner les A .i2Complexité : O(D ) où D est le degré de f.S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 1 / 19 S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 2 / 19Propriétés Relation de BézoutEuclideEtendu1 A = A et A = B et U = 1 et V = 00 1 0 0Le dernier élément non nul de la suite renvoyée par Euclide(A;B) est2 Tant que A = 0ile PGCD de A et B.Q =A divAi i 1 iImplantation : Prendre garde à ne pas calculer 0 dans les divisions A =A A Qi+1 i 1 i ieuclidiennes. U =U Q U et U =U Q Ui+1 i 1 i i i+1 i 1 i ii + +Forte croissance des coefficients (à tester en TME).3 Retourner les A .Idée : Faire du calcul modulaire et utiliser le Théorème des restes ichinois (chrem)Proposition 1Pour tout i, On a A U +A V = A .0 i 1 i iS. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 3 / 19 S. Graillat & M. Safey (Univ. Paris 6) MODEL (cours nr5) 4 / 19Rappel : Motivation initiale Objectif3 ...