Previous Up Next

Chapter 2  Il metodo di Wassing

In questo capitolo verrà presentato il metodo di Wassing [] [], che consente la risoluzione di un sistema lineare con un utilizzo di memoria quattro volte inferiore rispetto all’eliminazione di Gauss. Questo è possibile grazie al fatto di non richiedere che la matrice dei coefficienti sia disponibile interamente in memoria, ma che sia possibile ottenerne gli elementi solo quando necessario.

2.1  Basi teoriche del metodo di Wassing

Il nostro problema è quello di risolvere un sistema lineare

Ax=b

con A matrice n × n non singolare e densa.

Un classico modo per risolvere questo problema, consiste nel fattorizzare LU la matrice A:

A=LU,

con L matrice triangolare inferiore a diagonale unitaria, U matrice triangolare superiore e risolvere, quindi, i sistemi triangolari

Ly=b,    Ux=y.

Questo ha un costo di n2 locazioni di memoria e circa 2/3 n3 flops1. Di questo metodo, esiste la nota variante con pivoting parziale, largamente utilizzata nella pratica computazionale, ed implementata in numerose librerie di software matematico.

Per il metodo di Wassing, si costruisce, a partire dal sistema lineare Ax=b, una nuova matrice (n+1) × n, chiamata Z, nel seguente modo:

Z=


AT 
bT



.

Se, dunque, si fattorizza la matrice Z come LU, si ottiene

Z=


AT 
bT



=

L
lT1


·




U 
0
T





≡ LÛ

dove L,U ∈ ℝn × n e 0,l ∈ ℝn.

Da questo, eseguendo formalmente il prodotto tra le due matrici, risulta che




AT 
bT



=


LU 
lTU



,

ovvero

bT=lTU    e    AT=LU.

Pertanto,

b=−UTl    e    A=UTLT.

Ricordando che il problema di partenza era Ax=b, si vede come sia possibile ricondurlo a questa forma: UTLTx=−UTl e cioè

LTx=−l    ⇒    xT=−lTL−1.

Si analizzi ora più in dettaglio la matrice L: essa ha forma

L = 

L
lT1


.

Considerandone l’inversa,

L−1 = 

L−1
lTL−11


,

si osserva che i primi n elementi dell’ultima riga coincidono con il vettore soluzione xT.

Pertanto, si richiede di dover calcolare soltanto L (e non anche U) per ottenere la soluzione al sistema lineare di partenza.

2.2  Descrizione dell’algoritmo

Sia Z=(zij)∈ ℝ n+1 × n, allora i passi dell’algoritmo di Wassing sono i seguenti:

  1. i=2, 3, …, n, n+1

    zi1=−zi1/z11

  2. k=2, 3, …, n,
    1. i=k, k+1, …, n, n+1

      zik=zik + ∑j=1k−1 zijzjk

    2. i=k+1, k+2, …, n, n+1

      zik=−zik/zkk

    3. j=1, 2, …, k−1 e ∀ i=k+1, k+2, …, n, n+1

      zij=zij + zikzkj

  3. Il vettore soluzione, sarà

    xj=zn+1,jj=1, 2, …, n

2.3  Ottenere un’occupazione di memoria di (n+1)2/4 elementi

Come detto in precedenza, per la risoluzione del sistema lineare si ha bisogno soltanto della matrice L: dal momento che questa è una matrice triangolare inferiore a diagonale unitaria, se si memorizzasse interamente si avrebbe un’occupazione di memoria di approssimativamente n2/2 elementi.

È possibile, tuttavia, ottenere un’occupazione ancora minore di memoria, eliminando gli elementi che, nei passi successivi, non verranno più utilizzati. Infatti, dalla descrizione fatta in precedenza, si può notare che, alla fine del passo 1, si ha bisogno di memorizzare n elementi (quelli sottodiagonali della prima colonna: [z21zn+1,1]); in seguito, al termine del secondo passo, si devono memorizzare 2(n−1) elementi (gli elementi sottodiagonali della seconda colonna, [z32zn+1,2], e quelli sulle stesse righe della prima colonna, [z31zn+1,1]). In generale, alla fine del passo i-esimo solo gli elementi sulle righe i+1,…, n+1 delle prime i colonne saranno necessari per il passo successivo. Pertanto, si ottiene la seguente relazione per l’occupazione di memoria ai vari dei passi:

f(i)=i(ni+1),    i=1,…,n.

Si vede facilmente che f(i) raggiunge il valore massimo in corrispondenza di i=n+1/2 (assumendo, per semplicità, che tale quantità sia intera): pertanto, la massima occupazione di memoria richiesta sarà:

f


n+1
2



=
(n+1)2
4
.

È dunque possibile ottenere un notevole risparmio di occupazione di memoria, a patto però di non utilizzare esplicitamente una matrice per contenere gli elementi intermedi della risoluzione (altrimenti verrebbero usati circa (n+1)2 elementi) ma un vettore, in cui l’accesso sia svolto in maniera opportuna.


1
Il termine flop è l’acronimo di floating-point operation.

Previous Up Next