chapitre 13 : calcul matriciel 1 Le codage des matrices : Python pur
Contents
1. chapitre 13 calcul matriciel D M pour le 11 Mai 2014 Mode d emploi il s agit d un cours D M Au fil du cours vous allez trouver des questions qui pour la plupart demandent d crire des fonctions python mettant en oeuvre les algorithmes pr sent s Merci de r diger ce DM int gralement sur un fichier py pour les questions complexit taper le texte simplement Merci de s parer les fonctions dans des cellules avec le num ro de la question 1 Le codage des matrices PYTHON pur vs NUMPY 1 1 En python pur on code une matrice par une liste de listes Par exemple A 1 2 3 4 repr sentera pour nous la matrice G J Les entr es de A sont obtenues via A i j Noter que l affichage d une matrice n est pas bien joli mais qu il est facile de programmer une petite fonction qui fasse un affichage joli Attention En python les indices commencent 0 donc pour les matrices A 0 0 1 2 Attention au pr formatage pour les matrices en python pur Une r gle bien connue pour les listes On ne peut pas d finir une liste ex nihilo en affectant des entr es par exemple on ne peut pas d finir la matrice du paragraphe pr c dent en posant A 0 0 1 A 0 1 2 etc On reverra pour les listes les diff rentes m thodes append concatenation ou pr formatage pour une liste par exemple on peut cr er une liste de z ros L 0 n puis modifier les entr es mais pour les listes de listes a2. Comme A est inversible on sait qu on va toujours en trouver car la premi re colonne ne peut pas tre nulle Une pr caution li e au calcul num rique pour le choix du pivot e Quand on manipule des flottants le test de l galit z ro n est pas adapt car parfois dans les calculs un nombre qui vaudrait th oriquement z ro sera remplac par un nombre tr s petit On pourrait remplacer le test d galit z ro par la comparaison avec le epsilon machine mais e pour des raisons de meilleure pr cision du calcul num rique Fe ne ns x N lil vaut mieux viter de diviser par des tr s petits nombres Corollaire du principe pr c dent ce que dit un math maticien num rique il vaut mieux choisir comme pivot dans la colonne 1 l entr e ayant la plus grande valeur absolue Le pivot l tape i A l tape i en suivant le principe pr c dent on choisit parmi les lignes L avec j gt i celle o l entr e A j i a la plus grande valeur absolue et on l change avec L Ensuite on se sert de cette nouvelle L pour nettoyer la colonne C en dessous de la diagonale Remarque du math maticien l encore on est s r qu une des entr es A j i avec j gt est non nulle Sinon comme ce stade les premi res colonnes C1 C 1 sont d j celles d une matrice T S on aurait C1 C li es 4 2 Estimation de la complexit de la m thode du pivot pr c dente Ecrite
3. crire une fonction qui ram ne un syst me Y AX un syst me triangulaire Pour cela il suffit de faire subir Y les m mes op rations que celles faites sur A Ceci se formalise aussi avec la notion de matrice augment e A Y b Deuxi me tape crire une fonction resout_systeme qui prend comme argument une matrice inversible A et une colonne Y et renvoie l unique X tel que Y AX 6 Cas des matrices coefficients entiers ou rationnels Question Comment utiliser les algorithmes pr c dents pour faire du calcul exact sur les rationnels R ponse Il suffit de d clarer des matrices A et Y coefficients rationnels On utilisera le module fractions comme suit gt gt gt from fractions import ce qui suit est un exemple de calcul gt gt gt Fraction 1 3 Fraction 1 2 Fraction 5 6 a V rifier que vos fonctions pr c dentes s appliquent bien des matrices dont les entr es sont des Fractions en renvoyant des Fractions b Par commodit pour la suite crire une fonction convert_ratio qui prend une matrice rectangulaire quelconque dont les coefficients sont suppos s entiers et renvoie une autre matrice o on a converti chaque entr e Ali j en la fraction Fraction Ali 3j1 1 Ecrire aussi convert_float qui fait l inverse et convertit les entr es en flottant 7 Calcul exact sur les rationnels vs calcul sur les flottants la matrice de Hilbert ri 3 1 jeon 1 Cette matrice qui interv
4. atrice triangulaire sup rieure inversible T TS K et une matrice Y M 1 K et qui renvoie l unique solution X M K du syst me Y TX Ici les nombres dans K seront des flottants 3 Les op rations simples sur les lignes d une matrice Les programmes suivants seront crits pour s appliquer m me une matrice rectangulaire a Ecrire une fonction echangeLI A i j qui change les lignes i et j de la matrice A b Ecrire une fonction transvectionLI A i j mu qui dans la matrice A fait l op ration L Li uLj On tient compte du fait que les array sont des objets mutables Les fonctions pr c dentes modifieront la matrice A pass e en argument Remarque Pourquoi ai je appel la constante mu et pas lambda Parce qu en PYTHON le nom lambda est r serv pour la d claration de fonction en une ligne 4 Pr sentation du pivot mise sous forme triangulaire On fixe une matrice M K inversible 4 1 La m thode du pivot avec une sp cificit pour les machines Le premier pivot Au d but de la m thode du pivot on veut lt nettoyer gt la premi re colonne en utilisant A 1 1 comme pivot via L lt Li u L pour i gt 2 o u A i 1 A 1 1 Mais le seul probl me est que A 1 1 peut tre nul Ce que dira t un math maticien On doit donc d abord rechercher la premi re entr e non nulle dans la colonne 1 et une fois cette entr e trouv e une ligne L changer L et L
5. de mani re plus formelle la description de l algorithme du pivot donn e au paragraphe pr c dent devient On num rote ici les lignes en Lo Ln 1 dans l esprit de PYTHON pour i de O n 2 trouver j gt i tel que A j i soit maximum changer L_i et L_j pour k de iti n L_k lt L_k mu_k L_i Pour chaque valeur de i 0 n 2 e la recherche de j co te n i comparaisons e l change ventuel de L et Lj co te 2n 2 affectations 2n pour les entr es des lignes et 2 pour i et j e pour chaque valeur de k entre 1 et n 1 la transvection co te n affectations et autant de divisions multiplications soustractions une par entr e de la ligne Propri t En ajoutant toutes ces contributions comme comptant 1 on obtient pour la m thode du pivot sur une matrice GL K un co t en O n 4 3 Mise en oeuvre de la m thode du pivot vous de jouer Travail faire e crire une fonction devient_triangle qui prend comme argument une matrice qui ne sera pas modifi e par la fonction et qui renvoie une matrice T triangulaire sup rieure obtenue par pivot sur les lignes partir de A Outils utiles e On pourra cr er d abord une petite fonction cherche_pivot auxiliaire qui recherche la plus grande entr e non nulle en dessous de la diagonale dans une colonne j 5 Application la r solution de syst mes de Cramer 5 1 Codage matriciel d un syst me quelconqu
6. e avec second membre Remarque Si on se donne un syst me lin aire quelconque S Y AX avec A My n K Y Mn1 K et X Mn K o et Y sont fix s et on cherche X si on transforme ce syst me S par des op rations l mentaires sur les lignes on arrive un syst me quivalent S Y A X o Y et A ont t modifi es par les m mes op rations op rations sur les lignes Ces syst mes quivalents ont bien s r m me ensemble de solution On en d duit la Propri t d finition de la matrice augment e associ e un syst me Toutes les op rations sur un syst me peuvent tre cod es sur ce qu on appelle la matrice aug ment e de ce syst me savoir la matrice A Y obtenue en rajoutant Y comme derni re colonne A Les op rations faites sur lignes du syst me sont faites sur les lignes de cette matrice On arrive une matrice A Y telle qu on ait toujours l quivalence AX Y s A X Y Exemple On consid re le syst me T y 7z 1 2 y 5z 5 xz 3y 9z 5 A ce syst me on associe la matrice augment e 1 2 fi 2 1 5 5 1 3 9 5 Comparons alors l effet d une op ration l mentaire sur le syst me et la matrice augment e Par exemple avec L lt L 2L e le syst me devient gz y 7z 1 3y 9z 3 gz 3y 9z 5 e la matrice augment e devient 1 1 7 i 0 3 9 3 1 3 9 5 Ceci illustre bien qu il suffit de conduire l
7. e un np array rempli de 0 1 3 Les tableaux NUMPY np array Dans toute la suite on consid re qu on import numpy via import numpy as np La syntaxe pour d clarer un tableau NUMPY codant la matrice donn e au d but du cours est tr s proche A np array 1 21 3 4 1 Cette fois on a un affichage en deux dimensions array 1 2 3 4 On acc de aux entr es de deux mani res A i j ou Ali j Pour initialiser une matrice 3 x 2 remplies de z ros A np zeros 3 2 noter les doubles parenth ses print A array 0 0 0 0 0 gt 0 11 Noter que par d faut ces z ros sont des flottants mais A np zeros 3 2 dtype int dtype pour data type fabriquera une matrice dont les entr es sont des entiers 2 R solution des syst mes triangulaires On consid re un syst me Y TX avec T TS K inversible et Y M K fix s et on cherche l unique solution X M 1 K de ce syst me Un tel syst me se r sout de bas en haut A la ligne Ln on va seulement faire un quotient pour trouver n Yn tnn Mais ensuite la ligne L on obtiendra x par la formule 1 Ti a Hi DAT di j gt i Questions r diger la maison sur fichier py a Donner en justifiant votre r ponse l ordre de grandeur de la complexit de cet algorithme de r solution O n O n O n b Ecrire une fonction PYTHON appel e resoutTS qui prend comme arguments une m
8. es op rations l mentaires sur la matrice augment e pour coder les diff rents syst mes quivalents obtenus par op rations l mentaires Ici en poursuivant le pivot avec la matrice augment e L3 L3 Li 1 1 7 1 0 3 9 3 0 2 2 6 Lo lt FL 1 1 7 1 0 1 3 1 0 2 2 6 Ls lt Ls 2L 1 1 7 1 0 1 3 1 0 0 4 4 Cette matrice augment e dont la premi re partie est une matrice TS 3 x 3 code le syst me triangulaire quivalent notre syst me initial T y 7z 1 y 3z 1 4z 4 5 2 Les deux tapes r solution d un syst me de Cramer par le pivot D finition Un syst me de Cramer est un syst me AX Y avec matrice carr e inversible donn e Y colonne donn e et d inconnue une colonne X On sait donc que ce syst me admet un unique solution La premi re tape de la r solution Transformer A en une matrice A triangulaire sup avec la m thode du pivot sur les lignes donn e au 4 1 Appliquer les m mes transformations sur les lignes Y ce qui donne une nouvelle colonne Y On peut utiliser la matrice augment e pour cela La deuxi me tape de la r solution R soudre le syst me triangulaire A X Y avec la m thode du 2 Question Quelle est la complexit totale de cet algorithme 5 3 Mise en oeuvre de cette m thode vous de jouer a Premi re tape l aide de ce qui pr c de en modifiant l g rement la fonction devient _triangle pr c dente
9. ient notamment dans certains probl mes d analyse est tr s connue notamment pour e tre inversible son inverse est m me coefficients entiers et on peut donner une formule explicite pour cet inverse avec des binomiaux e avoir un calcul d inverse tr s instable du point de vue du calcul num rique L exercice qui suit va illustrer ces affirmations On consid re la matrice dite de Hilbert H a Ecrire une fonction hilbert n qui fabrique la matrice de Hilbert H en PYTHON comme une matrice coefficients de type Fraction b Appliquer la fonction devient_triangle H pour n 20 entr e la plus petite de FH est 1 2n 1 Commentez la taille des d nominateurs obtenus pour T devient_triangle hilbert 20 c A l aide de convert_float T que peut on dire des entr es diagonales de la matrice T Que penser a priori des risques de l algorithme de r solution appliqu un syst me TX Y d On veut expliciter la premi re colonne de la matrice H71 Pour cela il suffit de r soudre le syst me H X E1 o E est la premi re colonne canonique R soudre ce syst me l aide de la fonction resout_systeme avec Hp cod e avec des Fractions e R soudre ce syst me l aide de la fonction resout_systeme avec H cod e avec des floats f Que dire des r sultats obtenus
10. ttention RER Danger Un mauvais gag du pr formage des listes doubles On pourrait avoir envie de pr formater une matrice 2 x 2 de z ros de la fa on suivante gt gt gt X 0 0 2 gt gt gt X C O 0 0 01 jusqu ici tout va bien gt gt gt X 0 0 1 gt gt gt X C 1 0 1 0 la 7 7 E7 SET 7 SE On ne voulait modifier qu une entr e et on a modifi deux D o vient ce ph nom ne R ponse l objet 0 0 qui est copi par l op rateur 2 est une liste La copie pointe donc vers la m me adresse m moire pointeur Toute modification de la liste X 0 modifie aussi sa copie x 1 Comment contourner ce mauvais gag a D abord en revoyant le chapitre sur les listes e les listes ont beaucoup d avantage Pour une matrice fabriqu e partir de listes de listes on peut modifier les entr es de la matrice c est bien les fonctions peuvent transformer la matrice qu elles ont en argument c est bien mais il faut prendre garde aussi aux probl mes des ventuelles copies d une matrice qui pointeraient vers la m me case m moire une modification de la copie modifiera aussi l original e On rappelle qu il existe un module appel copy avec une fonction deepcopy qui r sout ce probl me des copies b Pour nous par commodit on pourra se servir plut t des np array de numpy qui ont des fonctions d initialisations int gr es comme np zeros n n qui initialis
Download Pdf Manuals
Related Search