Thème 2 : Algèbre matricielle avec Sagemath, systèmes d’équations linéaires

Sujet de devoir : Application à la théorie des jeux : Ecrire un algorithme prenant en entrée une matrice M (la matrice de paiement du premier joueur J1 d’un jeu fini à somme nulle), rendant les sommets (au sens de la convexité) de l’ensemble des stratégies mixtes prudentes de J1. Dessiner le découpage des stratégies mixtes prudentes de J1, le paiement minimal sur chacun des morceaux, les stratégies mixtes prudentes. Commencer par le cas où J1 a deux stratégies pures (la matrice M a deux lignes).

Document de cours sur la recherche des équilibre de l’extension mixte d’un jeu (fini à deux joueur à somme nulle), exemple de recherche algorithmique des solutions ; voir la page web du cours.

Autre sujet de devoir (difficile) : Application aux Chaînes de Markov : Ecrire un algorithme prenant en entrée la matrice M des probabilités de transition d’une chaîne de Markov (homogène, à temps discret, ayant un ensemble fini d’états), rendant la ou les formes limites de Mⁿ pour n grand. Simuler la chaîne de Markov de matrice M pour un état initial donné ; estimer les probabilités de présence en un état après un temps long, les temps d’atteinte d’un état donné.

Documents de cours sur cette page.

TP2 : Expérimenter l’algèbre matricielle avec Sagemath

Tutoriel sur l’algèbre matricielle avec sagemath

D’autres ressources sur internet (google “sagemath matrices”)

Soit $M$ la matrice

(\begin{array}{rr} \frac{1}{3} & \frac{1}{2} \\ \frac{2}{3} & \frac{1}{2} \end{array})

$\left(\begin{array}{rr} \frac{1}{3} & \frac{1}{2} \\ \frac{2}{3} & \frac{1}{2} \end{array}\right)$ et

I

$I$ la matrice unité. Exhiber avec Sagemath une base du noyau de

M - I

$M-I$ (l’espace propre de

M

$M$ pour la valeur propre

1

$1$ ). Quelles sont les méthodes disponibles ? Comment utiliser la méthode (M_I).kernel() ?

Quel est le système d’équations linéaires correspondant ? (Appliquer la méthode solve() ). Illustration graphique.

Calculer $M^k$ pour k=2,16,128. Calculer une valeur numérique approchée de $M^k$ avec la méthode (M^k).n()

Mêmes questions avec la matrice

N = (\begin{array}{rrr} \frac{1}{2} & 0 & 0 \\ \frac{1}{4} & 0 & 1 \\ \frac{1}{4} & 1 & 0 \end{array})

$N=\left(\begin{array}{rrr} \frac{1}{2} & 0 & 0 \\ \frac{1}{4} & 0 & 1 \\ \frac{1}{4} & 1 & 0 \end{array}\right)$

Au passage listes, vecteurs, matrices dans Python, listes imbriquées, génération de listes

File: /projects/sage/sage-7.5/src/sage/matrix/matrix2.pyx Signature : M.eigenvectors_right(self, extend=True) Docstring : Compute the right eigenvectors of a matrix. For each distinct eigenvalue, returns a list of the form (e,V,n) where e is the eigenvalue, V is a list of eigenvectors forming a basis for the corresponding right eigenspace, and n is the algebraic multiplicity of the eigenvalue. If "extend = True" (the default), this will return eigenspaces over the algebraic closure of the base field where this is implemented; otherwise it will restrict to eigenvalues in the base field. EXAMPLES: We compute the right eigenvectors of a 3 x 3 rational matrix. sage: A = matrix(QQ,3,3,range(9)); A [0 1 2] [3 4 5] [6 7 8] sage: es = A.eigenvectors_right(); es [(0, [ (1, -2, 1) ], 1), (-1.348469228349535?, [(1, 0.1303061543300932?, -0.7393876913398137?)], 1), (13.34846922834954?, [(1, 3.069693845669907?, 5.139387691339814?)], 1)] sage: A.eigenvectors_right(extend=False) [(0, [ (1, -2, 1) ], 1)] sage: eval, [evec], mult = es[0] sage: delta = eval*evec - A*evec sage: abs(abs(delta)) < 1e-10 True

#le paramètre r* est créé par Sage et change à chaque exécution. Peut on lui assigner une valeur ?#solution après visualisation du résultatS[0][1].rhs() #rhs pour "right hand side"vector([x,y]).subs(S).subs(S[0][1].rhs()==1) #[x,y].subs(S).subs(S[0][1].rhs()==1) donne une erreur

#Liste des paramètres dans la réponse de solve :#maxima_calculus("%rnum_list") cf https://ask.sagemath.org/question/26205/questions-about-the-parameters-in-the-output-of-solve/var('y');solve([1/3*x+1/2*y==x,2/3*x+1/2*y==y],[x,y])a=maxima_calculus("%rnum_list")print a, a[0].str()[1:]

#application :var('x y');S=solve([1/3*x+1/2*y==x,2/3*x+1/2*y==y],[x,y]);Sparam=[i.str()[1:] for i in maxima_calculus("%rnum_list")]t=[var('t'+str(i)) for i in range(len(param))];tr=[var(i) for i in param];rv=vector([x,y])v=v.subs(S).subs(r[0]==t[0])print "v=", v

(\begin{array}{rr} \frac{429856276558674694292684291539547551359685980829479881352399816713084541777734705200945845241605559}{1002997978636907620016263346925610953172600621935453056488932905663863930814714312135540305563746304} & \frac{573141702078232925723579055386063401812914641105973175136533088950779389036979606934594460322140745}{1337330638182543493355017795900814604230134162580604075318577207551818574419619082847387074084995072} \\ \frac{573141702078232925723579055386063401812914641105973175136533088950779389036979606934594460322140745}{1002997978636907620016263346925610953172600621935453056488932905663863930814714312135540305563746304} & \frac{764188936104310567631438740514751202417219521474630900182044118601039185382639475912792613762854327}{1337330638182543493355017795900814604230134162580604075318577207551818574419619082847387074084995072} \end{array})

$\displaystyle \left(\begin{array}{rr} \frac{429856276558674694292684291539547551359685980829479881352399816713084541777734705200945845241605559}{1002997978636907620016263346925610953172600621935453056488932905663863930814714312135540305563746304} & \frac{573141702078232925723579055386063401812914641105973175136533088950779389036979606934594460322140745}{1337330638182543493355017795900814604230134162580604075318577207551818574419619082847387074084995072} \\ \frac{573141702078232925723579055386063401812914641105973175136533088950779389036979606934594460322140745}{1002997978636907620016263346925610953172600621935453056488932905663863930814714312135540305563746304} & \frac{764188936104310567631438740514751202417219521474630900182044118601039185382639475912792613762854327}{1337330638182543493355017795900814604230134162580604075318577207551818574419619082847387074084995072} \end{array}\right)$

#points fixes de la matrice (ou espace propre pour la valeur propre 1)var('x,y,z')show(implicit_plot3d(1/2*x==x,(x,-1,1),(y,-1,1),(z,-1,1))+implicit_plot3d(1/4*x+z==y,(x,-1,1),(y,-1,1),(z,-1,1),color='darkkhaki')+implicit_plot3d(1/4*x+y==z,(x,-1,1),(y,-1,1),(z,-1,1),color='aquamarine')) #,1/4*x+z==y,1/4*x+y==z]

n=3x=var(['x'+str(i) for i in range(n)]);x # fait une erreur si n n'a pas de valeur ou si n=1 !x=[var('x'+str(i)) for i in range(n)] # ok si n=1A=matrix(3,range(9));Afor k in range(n):show(A[k]*vector(x)==0)#cf http://stackoverflow.com/questions/3394835/args-and-kwargs pour l'expansion des arguments *argsum(implicit_plot3d(*([A[k]*vector(x)==0]+[(x[i],-1,1) for i in range(n)])) for k in range(n))#for k in range(n-1):# for l in [k+1..n-1]:# eqs=eqs+[A[k]*vector(x)==A[l]*vector(x)]#eqs#show(sum(implicit_plot3d(*([eq]+[(x[i],-1,1) for i in range(n)])) for eq in eqs))

Thème 2 : Algèbre matricielle avec Sagemath, systèmes d’équations linéaires

Thème 2 : Algèbre matricielle avec Sagemath, systèmes d’équations linéaires

TP2 : Expérimenter l’algèbre matricielle avec Sagemath

Corrigé du TP

Complément : Système d’équations avec un nombre n d’inconnues, où n est un paramètre