In un precedente articolo, abbiamo esaminato la risoluzione di un problema LP, cioè un sistema di equazioni lineari con vincoli di disuguaglianza. Se il nostro insieme di equazioni lineari ha vincoli deterministici, possiamo rappresentare il problema come matrici e applicare l’algebra matriciale. I metodi a matrice rappresentano più equazioni lineari in modo compatto mantenendo l’utilizzo delle funzioni della libreria di matrici esistenti.
Useremo NumPy (un buon tutorial qui) e SciPy (una guida di riferimento qui). Per l’installazione di questi moduli esistono centinaia di risorse nel web, ne indicherò solo una Installare lo stack SciPy.
Un esempio: sistema di equazioni lineari
Come nostra pratica, procederemo con un esempio, prima scrivendo il modello a matrice e poi usando Numpy per le soluzioni.
Ora possiamo formalizzare il problema con le matrici:
Quindi, le equazioni lineari possono essere scritte in questo modo:
per risolvere per il vettore x, dobbiamo prendere l’inversa della matrice A e l’equazione viene scritta come segue:
Utilizzo di numpy per risolvere il sistema
import numpy as np
# definiamo la matrice A usando Numpy
A = np.array([[2, 1, 1],
[1, 3, 2],
[1, 0, 0]])
#definiamo la matrice B
B = np.array([4, 5, 6])
# linalg.solve è la funzione di NumPy per risolvere un sistema di equazioni lineari
print "Soluzioni:\n",np.linalg.solve(A, B )
Soluzioni:
[ 6. 15. -23.]
Dunque le soluzioni del sistema di equazioni lineari sono: a=6, b=15, c=-23
Quando le matrici crescono
All’aumentare del numero di variabili, aumenta anche la dimensione della matrice A e diventa computazionalmente costoso ottenere l’inversa della matrice A. Tra i vari metodi, considereremo una tra le procedure più utilizzate per ottenere la matrice A fattorizzata in matrici più semplici: la decomposizione LU.
La decomposizione LU
La decomposizione LU, nota anche come fattorizzazione inferiore superiore, è uno dei metodi per risolvere sistemi quadrati di equazioni lineari. Come suggerisce il nome, la fattorizzazione LU scompone la matrice A nel prodotto di due matrici: una matrice triangolare inferiore L e una matrice triangolare superiore U. La decomposizione può essere rappresentata come segue:
La decomposizione LU con SciPy
#importo il pacchetto linalg di SciPy per la decomposizione LU
import scipy.linalg as linalg
#import NumPy
import numpy as np
#definisco A come prima
A = np.array([[2., 1., 1.],
[1., 3., 2.],
[1., 0., 0.]])
#definisco B
B = np.array([4., 5., 6.])
#invochiamo la funzione di fattorizzazione LU
LU = linalg.lu_factor(A)
#risolviamo date LU and B
x = linalg.lu_solve(LU, B)
print ("Soluzioni:\n",x)
#vediamo come è stata fattorizzata A, dove P è la cosiddetta matrice di permutazione
P, L, U = linalg.lu(A)
print("P=\n",P,"\n","U=\n",U,"\n","L=\n",L)
print (np.dot(L,U))
Si ottiene:
[evaluate linalg.py]
Soluzioni:
[ 6. 15. -23.]
P=
[[1. 0. 0.]
[0. 1. 0.]
[0. 0. 1.]]
U=
[[ 2. 1. 1. ]
[ 0. 2.5 1.5]
[ 0. 0. -0.2]]
L=
[[ 1. 0. 0. ]
[ 0.5 1. 0. ]
[ 0.5 -0.2 1. ]]
[[ 2.00000000e+00 1.00000000e+00 1.00000000e+00]
[ 1.00000000e+00 3.00000000e+00 2.00000000e+00]
[ 1.00000000e+00 -2.77555756e-17 2.77555756e-17]]
Date L e U, possiamo rappresentare la matrice fattorizata A come: