Eliminazione di Gauss: un metodo per risolvere sistemi di equazioni

L’eliminazione di Gauss è uno degli algoritmi più fondamentali dell’algebra lineare per risolvere sistemi di equazioni lineari. Prende il nome dal matematico tedesco Carl Friedrich Gauss e trasforma un sistema di equazioni in una forma equivalente e più semplice eseguendo una sequenza di operazioni sulla sua rappresentazione matriciale.

In questo articolo vedremo come funziona l’eliminazione di Gauss, come implementarla in Python e ne esamineremo le applicazioni nella data science e nel calcolo numerico. Capendo questo algoritmo, acquisiremo familiarità con una tecnica fondamentale alla base di molti metodi computazionali usati nell’analisi dei dati.

Che cos’è l’eliminazione di Gauss?

L’eliminazione di Gauss è un algoritmo per risolvere sistemi di equazioni lineari trasformando sistematicamente la matrice aumentata del sistema in forma a scalini per righe (REF). Questa trasformazione preserva l’insieme delle soluzioni e rende più semplice trovare i valori delle variabili.

Una matrice è in forma a scalini quando:

• Tutte le righe composte interamente da zeri si trovano in fondo alla matrice
• L’elemento guida (il primo elemento non nullo) di ogni riga non nulla è a destra dell’elemento guida della riga superiore
• Tutti gli elementi sotto un elemento guida sono zeri

Per ottenere la forma a scalini, usiamo tre tipi di operazioni elementari di riga:

• Scambio di righe: scambiare due righe
• Moltiplicazione di riga: moltiplicare tutti gli elementi di una riga per una costante non nulla
• Addizione di righe: sostituire una riga con la somma di sé stessa e un multiplo di un’altra riga

Inoltre, è importante distinguere tra eliminazione di Gauss ed eliminazione di Gauss–Jordan:

• Eliminazione di Gauss trasforma la matrice in forma a scalini, richiedendo poi la sostituzione all’indietro per trovare i valori delle variabili
• Eliminazione di Gauss–Jordan prosegue fino alla forma a scalini ridotta (RREF), in cui tutti gli elementi guida sono 1 e tutti gli altri elementi nelle rispettive colonne guida sono 0

Sebbene l’eliminazione di Gauss–Jordan fornisca una soluzione più diretta, l’eliminazione di Gauss è in genere più efficiente per sistemi di grandi dimensioni, soprattutto se combinata con la sostituzione all’indietro e tecniche come la decomposizione LU.

Scomposizione passo-passo dell’algoritmo di eliminazione di Gauss

Vediamo il processo di eliminazione di Gauss con un semplice esempio. Considera il seguente sistema di equazioni lineari:

Sistema di equazioni lineari. Immagine dell’autore.

Passo 1: crea la matrice aumentata

Per prima cosa rappresentiamo il sistema come una matrice aumentata, combinando la matrice dei coefficienti con i termini noti:

Matrice aumentata. Immagine dell’autore.

Passo 2: eliminazione in avanti

Ora eseguiremo operazioni elementari di riga per trasformare la matrice in forma a scalini.

Rendi il primo elemento della prima colonna un pivot ed elimina tutti gli elementi sotto di esso:

• Aggiungi 3/2 × Riga 1 a Riga 2:

Aggiungi 3/2 × Riga 1 a Riga 2. Immagine dell’autore.

• Aggiungi Riga 1 a Riga 3:

Aggiungi Riga 1 a Riga 3. Immagine dell’autore.

Passa alla seconda colonna ed elimina tutti gli elementi sotto il pivot:

• Moltiplica la Riga 2 per 2 per rendere il pivot uguale a 1:

Moltiplica la Riga 2 per 2. Immagine dell’autore.

• Sottrai 2 × Riga 2 da Riga 3:

Sottrai 2 × Riga 2. Immagine dell’autore.

Rendi positivo il pivot nella terza riga:

• Moltiplica la Riga 3 per -1:

Moltiplica la Riga 3 per -1. Immagine dell’autore.

La matrice è ora in forma a scalini.

Passo 3: sostituzione all’indietro

Ora possiamo trovare i valori delle variabili tramite sostituzione all’indietro:

Dalla Riga 3: 

          z = -1

Dalla Riga 2: 

          y + z = 2,

          quindi y + (-1) = 2,

          da cui y = 3

Dalla Riga 1: 

          2x + y - z = 8,

          quindi 2x + 3 - (-1) = 8,

          da cui 2x = 4,

          quindi x = 2

Pertanto, la soluzione è x = 2, y = 3, z = -1.

Sebbene applichiamo l’eliminazione di Gauss a questo esempio, i passaggi restano gli stessi per qualsiasi altro sistema lineare di equazioni.

Implementazione dell’eliminazione di Gauss in Python

Anche se possiamo scrivere l’algoritmo usando Python di base, le operazioni vettorializzate di NumPy rendono l’implementazione sia più pulita sia significativamente più veloce. 

Per finalità didattiche è utile comprendere l’algoritmo sottostante, ma in produzione è consigliabile sfruttare librerie ottimizzate. Avendo già compreso l’algoritmo nella sezione precedente, ora passeremo all’implementazione usando librerie ottimizzate in Python.

Implementazione basata su NumPy

NumPy fornisce la funzione numpy.linalg.solve(), che implementa una soluzione altamente ottimizzata per sistemi di equazioni lineari:

import numpy as np

# Define the coefficient matrix A and constant vector b
A = np.array([[2, 1, -1],
             [-3, -1, 2],
             [-2, 1, 2]], dtype=float)
b = np.array([8, -11, -3], dtype=float)

# Solve the system Ax = b
x = np.linalg.solve(A, b)

print("Solution:", x)Offerto da

Nel codice sopra, definiamo la matrice dei coefficienti A insieme al vettore dei termini noti b, che sono gli stessi della matrice aumentata creata nel passo 1 dell’esempio di eliminazione di Gauss riportato sopra. 

Usiamo la funzione numpy.linalg.solve() per ottenere la soluzione e stampiamo l’output come mostrato di seguito:

Soluzione usando l’implementazione in codice. Immagine dell’autore.

Questa implementazione utilizza LAPACK sotto il cofano, applicando la decomposizione LU (una variante dell’eliminazione di Gauss) ottimizzata per stabilità numerica e prestazioni.

Gestione dei casi particolari

Implementando l’eliminazione di Gauss, incontrerai diversi casi particolari che richiedono attenzione:

• Matrici singolari: se il determinante della matrice dei coefficienti è zero o molto vicino a zero, il sistema non ha soluzione o ne ha infinite. La funzione linalg.solve() di NumPy in questo caso genera un LinAlgError.

• Stabilità numerica: con l’aritmetica in virgola mobile, gli errori di arrotondamento possono accumularsi e portare a risultati imprecisi. Il pivoting parziale, in cui si sceglie come pivot l’elemento più grande della colonna, aiuta a mitigare il problema.

• Sistemi sovradeterminati o sottodeterminati: quando il numero di equazioni non coincide con il numero di variabili, puoi usare numpy.linalg.lstsq(), che trova la soluzione ai minimi quadrati.

Per sistemi di grandi dimensioni con molti zeri, i risolutori per matrici sparse di SciPy possono essere ordini di grandezza più veloci rispetto ai risolutori densi:

from scipy.sparse import csr_matrix
from scipy.sparse.linalg import spsolve

# For large sparse matrices
A_sparse = csr_matrix(A)
x = spsolve(A_sparse, b)Offerto da

Sebbene comprendere i meccanismi dell’algoritmo sia prezioso, in pratica sfruttare le implementazioni ottimizzate di NumPy e SciPy ti consente di risolvere sistemi lineari in modo efficiente e affidabile senza reinventare la ruota.

Dove si usa l’eliminazione di Gauss

L’eliminazione di Gauss va ben oltre la matematica teorica e trova numerose applicazioni pratiche in vari campi della scienza, dell’ingegneria e dell’analisi dei dati. 

Ecco alcune delle applicazioni reali più importanti di questo algoritmo fondamentale:

• Regressione lineare: nella data science, l’eliminazione di Gauss è usata per risolvere le equazioni normali che emergono quando si cercano i parametri di miglior adattamento nei modelli di regressione lineare. Questo permette di fare previsioni basate sui dati storici.
• Analisi di reti: gli ingegneri usano l’eliminazione di Gauss per trovare correnti o tensioni incognite nei circuiti elettrici applicando le leggi di Kirchhoff, che generano sistemi di equazioni lineari da risolvere simultaneamente.
• Inversione di matrici: l’eliminazione di Gauss è alla base del calcolo delle inverse di matrice, essenziali in trasformazioni, analisi statistiche e nella risoluzione di problemi matematici complessi negli algoritmi di machine learning.
• Integrazione numerica: nell’implementazione di metodi numerici avanzati come l’Eulero implicito o gli schemi di integrazione di Runge–Kutta, si usa l’eliminazione di Gauss per risolvere i sistemi di equazioni risultanti, garantendo stabilità nelle simulazioni di sistemi dinamici.

Capendo queste applicazioni, possiamo vedere come una singola tecnica matematica possa fare da spina dorsale a molti strumenti usati quotidianamente da data scientist, ingegneri e ricercatori.

Conclusione

In questo articolo abbiamo esaminato l’algoritmo fondamentale dell’eliminazione di Gauss per risolvere sistemi di equazioni lineari trasformando le matrici in forma a scalini. Abbiamo anche visto come implementare questa tecnica in Python usando le funzioni ottimizzate di NumPy e ne abbiamo compreso le applicazioni pratiche in regressione lineare, analisi di reti, inversione di matrici e metodi numerici. 

Per approfondire l’algebra lineare e le sue applicazioni nella data science, valuta l’iscrizione al nostro corso di Algebra lineare, dove esplorerai concetti più avanzati e implementazioni di queste tecniche fondamentali.