1 TP: Prise en main (2H) *=*=*=*=*=*=*=*=*=*=*=*=* L'objectif de ce TP est de reprendre des exercices précédemment faits en TD, afin de découvrir ce qu'un système de calcul formel est capable, ou pas, de faire. Exercice 1 [Arithmétique] 1. Calculer 1+1, 2*2, 2^30, 10!, 5/9. Que constate-t'on? 2. Calculer (2)^1/2, puis ((2)^1/2)^2 (indication: consulter l'aide avec ?sqrt). En calculer des approximations numériques (cf. ?float). Faire varier la précision en jouant avec DIGITS := 200. Puis réinitialiser à 10 chiffres de précision. 3. Calculer sin(3.14), sin(pi), sin(pi/3) (cf. ?sin, ?PI). Que constate-t'on? Exercice 2 [Polynômes] 1. Essayer la commande: (f+g) ( x + y ). Comparer avec (f+g) * (x+y). Conclusion? 2. Développer (x+3)(x-2) (cf. ? expand), et stocker le résultat dans une variable p (cf. ?:=). 3. Refactoriser le résultat (cf. ? factor). 4. Utiliser solve pour retrouver les racines de p. 5. Factoriser x^2-2 et chercher ses racines. 6. Factoriser p := x^7-3x^2+x+1 et chercher ses racines. Interpréter. 7. Évaluer p en x=0, x=2, x=pi, x=y^2 (cf. ? |). 8. Tracer le graphe de la fonction x|-> p(x) de R dans R (cf. ? plot::Function2d). En utilisant ce graphe et la fonctionnalité de zoom, donner le nombre de racines de p. 9. Calculer numériquement les racines de p (cf. ? solve, ? float). Exercice 3 [Analyse] 1. Calculer arccos(1), arccos(-1), arccos((2)^1/2/2), arccos(-x). 2. Calculer la dérivée de arccos, puis en tracer le graphe (cf. ? diff, ? plot::Function2d) 3. Calculer la dérivée par rapport à x des expressions suivantes: 1. 3sin(x)+x^5 - 1/(1+x^2+3x^5) 2. f(x) + g(x) 3. f(x) g(x) 4. f(x)/g(x) 5. (f^o g) (x) (cf. ?@) 4. Calculer symboliquement puis numériquement les intégrales suivantes (cf. ? int): 1. int_x=0^pi/2 cos(x)/1+sin(x) dx. 2. int_x=0^1 dx/e^x^2 + 1. Que constate-t'on? 5. Calculer les primitives des expressions suivantes, puis les redériver pour vérifier le résultat: 1. x^2. 2. 1/4 e^x + e^-x + 4. 3. 1/e^x^2 + 1. Que constate-t'on? Exercice 4 [Algèbre linéaire] Résoudre en fonction de m le système d'équations: { -mx -3y -z = m { (m+1)y + (m+1)z =0 { 3y + (m+1)z = 0 . { 6y + 2z + mt = m+1 2 TP Algèbre linéaire 2 (1H30) *=*=*=*=*=*=*=*=*=*=*=*=*=*=*=* L'objectif de ce TP est de voir quelques applications de la diagonalisation de matrices, en particulier pour l'étude des suites récurrentes. Comme d'habitude, c'est à vous de déterminer, au cas par cas, quels calculs il vaut mieux faire à la machine ou à la main. Les exercices sont de difficulté croissante. Exercice 5 La première application concerne la modélisation de la dynamique des populations, telle qu'étudiée en écologie. Le cas d'école que nous allons considérer n'est pas nouveau, puisqu'il a été proposé en 1202 par Leonardo Pisano comme problème récréatif dans un de ses ouvrages, le Liber Abaci. Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? Nous allons considérer un modèle très simple, dans lequel on notera f_n le nombre nombre de paires de lapins en fin de n-ième mois, dans une population idéale telle que: - le premier mois, il y a juste une paire de lapereaux, - les lapereaux ne sont pubères qu'à partir du deuxième mois, - chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapereaux, - les lapins ne meurent jamais. 1. Donner la relation de récurrence satisfaite par la suite f_n. 2. Donner le surnom de Leonardo Pisano. 3. Nous souhaitons maintenant calculer f_n pour n relativement grand. Pour cela, nous allons mettre le problème sous forme matricielle en notant pour n>=2, F_n:=( f n f n-1 ). 1. Donner F_2, et déterminer une matrice M telle que F_n+1=M F_n pour n>= 2. 2. À l'aide d'une boucle for, calculer f_1026 et f_65636. 3. Calculer F_1026=M^1024 F_2 et F_65638=M^65636 F_2. À votre avis, comment s'y prend la machine? 4. Pouvez-vous l'égaler en utilisant uniquement des produits de matrices? 5. Évaluer le nombre d'opérations arithmétiques (+, * sur les coefficients des matrices) nécessaires pour calculer M^2^n. 6. Utiliser la commande time pour comparer le temps de calcul de M^2^20 et de float(M)^2^20. Interpréter. 7. Calculer numériquement f_2^20, f_2^23, f_2^24. Interpréter. 4. Nous cherchons maintenant donner une formule exacte pour f_n. Pour cela, on va diagonaliser la matrice M. 1. Vérifier que M^2-M-I_2=0. Comparer avec le résultat de linalg::minimalPolynomial(M,z). 2. Soit v un vecteur non nul et lambda un réel tels que Mv=lambda v. Montrer que lambda^2-lambda-1=0. En déduire les deux valeurs lambda_10 do if nombre mod 2 = 1 then resultat := append(resultat,1); nombre := nombre-1 else resultat := append(resultat,0) end_if; nombre := nombre div 2; end_while; resultat; end_proc: >> sera décrit par le graphe suivant: [height=7cm]diagrammeFlot Une trace d'exécution est alors une suite de sommets consécutifs allant du sommet a au sommet h dans ce diagramme. Par exemple, en appliquant ce programme au nombre 5, on obtient la trace (a,b,c,d,e,g,b,c,f,g,b,c,d,e,g,b,h). Vous pouvez le vérifier à la main, ou en utilisant la commande debug(decompositionBinaire(5)). La longueur d'une trace est le nombre de sommets parcourus, soit 17 dans l'exemple précédent. Le principe de cette méthode de test est d'étudier les traces d'exécutions possibles, et de déterminer si elles sont correctes. Ici, notre objectif est simplement de compter le nombre h_k de traces d'exécutions de longueur n, afin de déterminer jusqu'à quelle longueur on peut envisager de faire du test exhaustif. En particulier, on ne se préoccupera pas ici des valeurs des variables du programme. Formellement, le problème est de compter les chemins dans un graphe orienté. 1. Lister toutes les traces d'exécutions de longueur inférieure à 17. 2. On considère le vecteur ( a ) ( ) ( n ) ( b ) ( ) ( n ) ( c ) ( ) ( n ) ( d ) ( ) V ( n ) :=( e ) (1) n ( ) ( n ) ( f ) ( ) ( n ) ( g ) ( ) ( n ) ( h ) ( ) ( n ) où c_n compte le nombre de traces d'exécutions du sommet a au sommet c de longueur n, et similairement pour a_n,...,h_n 1. Calculer les vecteurs V_0, V_1, V_2, V_3, V_4. 2. Donner une formule de récurrence permettant d'exprimer g_n en fonction de a_n-1,...,h_n-1. Exprimer de même les autres coordonnées de V_n. 3. Déterminer une matrice M telle que V_n=MV_n-1. 4. Calculer le nombre de traces d'exécutions de longueur 1024. Évaluer très grossièrement le temps nécessaire pour tester toutes ces traces, sur un ordinateur à 2GHz (on admettra que le traitement de chaque sommet prend environ 100 cycles d'horloge). 3. Pour donner une formule approximative pour h_n, on va procéder comme dans l'exercice précédent en diagonalisant la matrice M. 1. Calculer les valeurs propres de M à l'aide de la commande linalg::eigenvalues(M). Interprétation? Calculer le polynôme minimal de M avec linalg::minimalPolynomial 2. Pour simplifier, nous nous contenterons de faire un calcul numérique approché, en considérant la matrice de flottants float(M). 3. Calculer numériquement les vecteurs propres de M. 4. En déduire une base B' de R^n dans laquelle M est diagonale. 5. Calculer les matrices de changement de base. 6. Calculer la matrice M' correspondant à M dans cette nouvelle base. 7. Calculer M'^n, puis M^n, puis V_n puis h_n. 8. Donner une approximation de h_n sous la forme a^n. 9. Jusqu'à quelle valeur de n peut-on raisonnablement faire du test exhaustif? - Analyse de données Plot de nuage de points Objectif: constater dans la pratique que les vecteurs propres de la matrice d'inertie d'un objet mécanique donnent ses axes principaux de rotation. À faire en 2D, puis en 3D, avec une centaine de points. Application à l'analyse de donnée: représenter un nuage de points par un patatoïde. => infos sur les corrélations. En principe, on se ramène à des variables réduites pour avoir une bonne métrique malgré les unités différentes. Exemple (pour lequel les unités sont homogènes; donc on peut prendre la métrique euclidienne). Voir TP d'Albane. 3 TP: Géométrie *=*=*=*=*=*=*=*= Le calcul matriciel est un outil fondamental en géométrie. En particulier, il donne des notations compactes et puissantes pour le graphisme 2D et 3D. Dans ce TP, nous allons explorer comment utiliser les matrices pour implanter des transformations géométriques naturelles comme les rotations, les symétries ou les projections. Tout au long de ce TP, nous visualiserons l'effet des transformations sur le polygone suivant, dont chaque sommet est décrit par un vecteur de R^2 (1): << points := [matrix(point) $ point in [[ 0, 1755], [1980, 180], [2070, 1260], [3150, 720], [2340, 3240], [4095, 1125], [3060, 3735], [4860, 1260], [4050, 900], [4590, 900], [7650, 2070], [6300, 1890], [5130, 1395], [3645, 4275], [3735, 4320], [5175, 1485], [5445, 1620], [4950, 3105], [5355, 3285], [6795, 2250], [7695, 2295], [4590, 4860], [4365, 4725], [4860, 3915], [4590, 3780], [3915, 4455], [2790, 3780], [3060, 2880], [2070, 3645], [1710, 2655], [2970, 990], [1440, 2295], [1845, 450], [1035, 2160]]]; >> Pour visualiser le polygône, utiliser: << plot(plot::Polygon2d(points)) >> Si vous avez des talents de graphistes, merci de nous proposer d'autres polygones esthétiques pour les TP de l'année prochaine! Exercice 7 Soit M une matrice M de dimension 2× 2, et phi l'application linéaire de R^2 dans R^2 correspondante. Notre objectif est d'interpréter géométriquement la transformation phi lorsque cela est possible. Considérons d'abord la matrice: << M := matrix ( [ [ 0,1], [ 1,0] ]): >> Étant donné un vecteur v de R^2, l'image phi(v) de v par phi peut être obtenue en calculant M*v. Calculer l'image des vecteurs de la base canonique de R^2. Pour visualiser l'image du polygone par phi, il suffit donc de faire: << plot(plot::Polygon2d([ M*v $ v in points])) >> 1. Quelle est la transformation géométrique effectuée par phi? 2. Même question pour les matrices suivantes: << M := matrix ( [ [-1, 0], [ 0,-1]]) >> << M := matrix ( [ [ 4, 0], [ 0, 1]]) >> << M := matrix ( [ [ 1, 0], [ 0, 1]]) >> << M := matrix ( [ [ 1, 0], [ 0,-1]]) >> 3. L'animation suivante permet de visualiser l'effet de la matrice << M := matrix ( [ [ 1, 0], [ 0, 1/2^n]]) >> lorsque n tend vers l'infini. << plot(plot::Polygon2d([ matrix([[1,0],[0,1/2^n]])*v $ v in points], n=1..10)) >> Quelle est la transformation géométrique pour la matrice limite << M := matrix ( [ [ 1, 0], [ 0, 0]]) >> 4. Chercher la matrice de l'application linéaire phi qui effectue une homothétie (zoom) de facteur 2, et plus généralement de facteur lambda. Vérifier le résultat en visualisant le polygone transformé. 5. En vous inspirant de l'exemple précédent, construire une animation où le polygone grossit progressivement. 6. Chercher la matrice de l'application linéaire phi qui effectue une rotation d'un quart de tour dans le sens trigonométrique. 7. Chercher la matrice de l'application linéaire phi qui effectue une rotation d'angle theta dans le sens trigonométrique (indication: chercher l'image par phi des vecteurs de la base canonique). 8. Construisez une animation où le polygone tourne autour du point de coordonnées (0,0). 9. Même chose, en faisant grossir progressivement le polygone au fur et à mesure qu'il tourne. 10. Chercher la matrice de l'application linéaire phi qui envoie le vecteur b_1:= 1 1 sur 2b_1, et b_2:= 1 -1 sur 1/2 b_2 (indication: donner la matrice de phi dans la base (b_1,b_2), puis appliquer les formules de changement de base pour obtenir sa matrice M dans la base canonique). 11. Exercice 8 [Transformations affines] Toutes les transformations que nous avons rencontrées pour l'instant sont linéaires; en particulier le vecteur 0 reste inchangé. 1. Quelle opération matricielle pourrait-on utiliser pour décaler le polygone de 1000 points vers la gauche? 2. Plus généralement pour effectuer une translation le long d'un vecteur de coordonnées (x,y)? 3. Construire une animation où le polygone part vers la droite de plus en plus vite. 4. Ce que nous venons de faire, c'est de nous placer dans une classe plus grande de transformations: les transformations affines. Celles si sont de la forme v |-> M v + u, où M est une matrice 2× 2, et u un vecteur de R^2. 5. Chercher la transformation affine correspondant à la rotation d'angle 45 degrés autour du centre du polygone. 6. Construire une animation où le polygone tourne, grossit et se déplace simultanément. Exercice 9 [3D] Nous voulons maintenant animer le polygone en 3D. Afin de comprendre la mécanique interne, nous n'utiliserons pas les possibilités natives de MuPAD. Pour simplifier, nous nous contenterons ici de perspective cavalière. 1. Pour plonger le polygone dans R^3, nous pouvons utiliser l'application linéaire de R^2 dans R^3 qui envoie les deux vecteurs de la base canonique de R^2 sur les deux premiers vecteurs de R^3. Donner la matrice de cette application linéaire. 2. Réciproquement, pour visualiser un objet en 3D sur l'écran (qui n'a que deux dimensions), il faut faire une projection de R^3 dans R^2. Nous supposerons que l'observateur regarde depuis le haut, de sorte que la projection se fera sur le plan des x et y. Donner la matrice de cette application linéaire. 3. Calculer le produit des deux matrices correspondant au plongement de R^2 dans R^3 suivi de la projection de R^3 dans R^2. Interprétation? 4. Afficher le polygone après plongement puis projection. 5. Donner la matrice de la rotation de R^3 d'angle theta autour de l'axe des x. Indication: faire un dessin, et chercher l'image des vecteurs de la base canonique. Afficher le polygone après plongement, rotation de 45 degrés puis projection. Animer le résultat pour theta variant de 0 à 359 degrés. Exercice 10 [Perspective cavalière] Probablement trop ambitieux. 4 TP: Polynômes 1 (1H30) *=*=*=*=*=*=*=*=*=*=*=*=* L'objectif de ce TP est d'explorer plusieurs façons d'approximer une fonction f de R dans R par une fonction plus simple. Exercice 11 [Approximation par une fonction affine] Soit f := x |-> sin(x). Tracer son graphe avec << f := sin: plot(plot::Function2d(f)) >> Notre objectif est de construire des fonctions simples qui approximent f aux alentours d'un point x_0. 1. Chercher une constante a_0 telle que la fonction constante g := a_0 approxime au mieux f aux environs de 0. Tracer son graphe par dessus celui de f avec << plot(plot::Function2d(g(x)), plot::Function2d(g(x))) >> Zoomer le graphique. 2. Chercher une fonction affine g := a_0 + a_1 x qui approxime au mieux f aux environs de x_0:=0. La comparer graphiquement avec f. 3. Chercher une fonction affine g := a_0 + a_1 (x-x_0) qui approxime au mieux f aux environs de x_0 := pi/4 (pi se note PI). 4. << xmin := -2*PI: xmax := 2*PI: plot(plot::Function2d(sin(x), x=xmin..xmax), plot::Function2d(f(x0) + f'(x0)*(x-x0), x=xmin..xmax, x0=xmin..xmax), ViewingBoxYRange=-2..2) >> Exercice 12 [Interpolation de Lagrange] - Approximation d'une fonction par un polynôme: interpolation / DL / Padé? Objectif: leur faire passer la notion de DL 5 TP: Polynômes 2 (1H30) *=*=*=*=*=*=*=*=*=*=*=*=* Exercice 13 Un vieux pirate est sur son lit de mort. Dans sa jeunesse il a enfoui un Fabuleux Trésor dans la lagune interminable de l'Ile de la Tortue, quelque part à l'est du Grand Cocotier. Il a réuni ses dix lieutenants préférés pour leur transmettre l'information secrète indispensable: la distance entre le Grand Cocotier et le Trésor. Connaissant bien ses lieutenants, et dans un étonnant dernier sursaut de justice, il ne voudrait pas qu'une conjuration de quelques uns d'entre eux assassines les autres pour empocher seuls le trésor. En tenant cependant compte de la mortalité habituelle du milieu, il souhaite donner une information secrète à chacun de ses lieutenants pour que sept survivants puissent toujours retrouver ensemble le trésor, mais pas moins. Comment peut-il s'y prendre? 1. « The art of doing mathematics consists in finding that special case which contains all the germs of generality » -- David Hilbert Autrement dit, la première chose à faire pour attaquer ce genre de problème est de le généraliser pour des paramètres quelconques, et de commencer par essayer de comprendre ce qu'il se passe pour de petites valeurs des paramètres. Ici, les paramètres naturels sont le nombre n de lieutenants, et le nombre k de survivants. Que peut on dire pour n<= 1? pour k<= 1? 2. Étudions maintenant le cas n=k=2. Soit b la distance secrète. Le pirate choisit au hasard un coefficient a qu'il garde secret, et considère la fonction f(x) = ax+b. Puis il choisit au hasard deux points d'évaluation x_1:=-3 et x_2:=7 qu'il annonce publiquement. Enfin, il dit en secret au premier pirate que f(x_1) = 5 et au deuxième pirate que f(x_2) = 7. Les deux pirates se mettent ensemble; retrouver la valeur de b. Est-ce que le premier pirate aurait pu la retrouver tout seul? 3. Généralisation pour n=10 et k=7: choisir une valeur secrète b. Tirer au hasard les coefficients d'un polynôme f(x) = a_6 x^6 +...+a_1 x + b de degré 6 et dont le terme constant est b. Tirer au hasard dix points d'évaluation x_1,...,x_10 distincts et non nuls, et calculer f(x_1),...,f(x_10). À l'aide de la commande interpolate, et en utilisant uniquement x_1,...,x_7 et f(x_1),...,f(x_7) retrouver la valeur de b. Pour se mettre en condition réelle, donner à chaque étudiant du TP un couple (x_i, f(x_i)), et laissez les retrouver ensemble la valeur secrète. ----------------------------------- (1) Rappel: matrix(1,2) permet de construire le vecteur de R^2 de coordonnées (1, 2); pour comprendre la notation $, essayer f(x) $ x in [a,b,c,d]. ----------------------------------------------------------------------- This document was translated from LaTeX by HeVeA (2).