KULT Underground

una della più "antiche" e-zine italiane – attiva dal 1994

Sistemi lineari (prima puntata)

4 min read

Metodi per la risoluzione

dei sistemi lineari

Prima puntata

Il sistema lineare è lo strumento matematico che permette di analizzare sia i fenomeni rappresentabili con modelli lineari sia i fenomeni i cui modelli, non lineari, possono essere linearizzati. Si tratta per tanto di affrontare un problema di tipo inverso che consiste nella ricerca delle componenti di un vettore x tale che sia
Ax=b, dove A è la matrice dei coefficienti e b è il vettore dei termini noti.
Apparentemente il metodo più semplice è quello di ridurre il problema così posto ad un problema diretto del tipo x=A-1b. In questo modo, tuttavia, occorre calcolare l’inverso della matrice A del sistema e ciò comporta sia un calcolo in molti casi oneroso, sia errori di arrotondamento. Si consideri ad esempio il sistema di dimensione unitaria

7x=21

Calcolando dapprima l’inversa si ha, in aritmetica a sei cifre:

x=(7)-1(21)=0.14285*21=2.99985

In questa modo si è ottenuta la soluzione con due operazioni.
Eliminando, invece, il coefficiente dell’incognita, cioè calcolando x=21/7 si ottiene il risultato con una sola operazione e con maggiore accuratezza.
Poichè questo esempio può essere generalizzato a sistemi di ordine n, da esso si può impiricamente dedurre che sia sconveniente la ricerca della soluzione mediante il calcolo dell’inversa; inoltre si può notare come uno stesso problema sia stato risolto con metodo diverso.
In realtà la bibliografia esistente mette a disposizione degli utenti un vasto numero di metodi applicabili in situazioni differenti ed aventi un diverso grado di difficoltà per l’implementazione; in particolare essi si possono distinguere in metodi diretti e metodi iterativi.
I primi sono per lo più basati sul metodo di eliminazione di Gauss e sono tali che, supponendo assenti gli errori di arrotondamento, forniscono la soluzione del sistema in un numero finito di passi. I metodi iterativi, invece, ottengono la soluzione come limite di una successione di soluzioni di sistemi lineari più semplici e sono in genere usati in alternativa ai metodi diretti per risolvere i sistemi con matrice A di ordine elevato o sparsa. Mettendoci nel caso di matrici quadrate, dense o di piccole dimensioni, è interessante analizzare il metodo di eliminazione di Gauss che, come si è detto, sta alla base dei metodi diretti. Esso consiste nell’eliminazione successiva delle incognite mediante la sostituzione delle equazioni del sistema con oppurtune combinazioni lineari delle equazioni stesse.
Questo procedimento permette di ottenere un nuovo sistema, equivalente al primo, che ha però il vantaggio di essere triangolare, pertanto risolubile mediante un semplice metodo di sostituzione all’indietro.
Supponiamo, come esempio, di avere un sistema di n equazioni in n incognite, con matrice A tale che det(A)=/0:

{a11x1+…+a1nxn=a1n+1
{a21x1+…+a2nxn=a2n+1
{………………….
{an1x1+…+annxn=ann+1

Se a11=/0, dalle equazioni successive alla prima si può eliminare x1 sottraendo alla riga i-esima, della matrice del sistema, la prima moltiplicata per mi1=ai1/a11.
In questo modo si ottiene:

{a(1)11×1+…+a(1)1nxn= a(1)1n+1
{0+a(1)22×2+…+a(1)2nxn= a(1)2n+1
{………………….
{0+a(1)n2x1+…+a(1)nnxn= a(1)nn+1

A questo punto se a(1)22=/0 si può ripetere il procedimento per eliminare x2 dalle equazioni 3,4,…,n; quindi si guarda a(2)33 e così via fino ad ottenere, al passo (n-1)-esimo, il seguente sistema triangolare

{a(1)11×1+a(1)12×2+… +a(1)1nxn= a(1)1n+1
{ a(2)22×2+… +a(2)2nxn= a(2)2n+1
{………………….
{a(n)nnxn= a(n)nn+1
dove a(i)ij = a(i-1)ij-mika(i-1)kj e

mik = a(i-1)ik/a(i-1)kk

Ora, utilizzando il metodo di sostituzione all’indietro si ha che:
xn=an,n+1/an,n
xn-1=(an-1,n+1-an-1,nxn)/an-1,n-1
xn-2=(an-2,n+1-an-2,n-1xn-1+

-an-2,nxn)/an-2,n-2

e in generale
xi=(ai,n+1-Sommatoria(n,j=i+1)aijxj)/ai,i
dove, per semplicità, si è posto a(k)ij=aij.
In questo modo si ottiene la soluzione del sistema; tuttavia non avendo posto alcun ipotesi sulla matrice iniziale, se non che sia a determinante=/0 è possibile che al generico passo i-esimo sia aii=0.
Questo implica una divisione per 0 nel calcolo di mik con il conseguente arresto del procedimento di eliminazione delle incognite.
Per ovviare a tale inconveniente viene utilizzata la strategia del pivoting. Essa consiste nello scambio di righe e colonne della sottomatrice quadrata B, che si ottiene all’i-esimo passo del procedimento di eliminazione, in modo da porre in aii l’elemento di B massimo in valore assoluto.
In questo modo è sempre aii=/0; inoltre è da specificare che si sceglie l’elemento massimo in quanto è quello che genera sulle soluzioni del sistema gli errori di arrotondamento più piccoli.
Viene allegata l’implementazione in C delle tecniche fin qui descritte supponendo, per semplicità, che il sistema possa avere dimensione al più 100.

Elena

Altri articoli correlati

Commenta