Calcolo del precondizionatore

Una delle chiavi del successo del GCM nella soluzione efficiente di sistemi lineari sparsi, simmetrici e definiti positivi sta nella possibilità di ottenere formidabili accelerazioni della convergenza mediante l'uso di opportune matrici di precondizionamento. La scelta di $K^{-1}$ deve soddisfare alle seguenti caratteristiche:

• deve essere tale che il prodotto $A K^{-1}$ abbia lo spettro, cioè l'insieme degli autovalori, raggruppato attorno all'unità e comunque un numero di condizionamento spettrale inferiore a quello di $A$;
• il calcolo deve essere semplice e poco costoso per non appesantire lo schema;
• l'occupazione di memoria deve essere inferiore o al più paragonabile a quella della matrice del sistema allo scopo di non vanificare lo sforzo computazionale effettuato per la memorizzazione compatta.

Spesso le suddette caratteristiche confliggono fra loro e necessariamente la scelta di $K^{-1}$ diventa il risultato di un compromesso. Per paradosso, la matrice che soddisfa completamente la prima richiesta è ovviamente $A^{-1}$, il cui costo ed occupazione di memoria (si ricordi che l'inversa di una matrice sparsa è generalmente una matrice piena) tuttavia rendono del tutto incalcolabile.

Una discreta accelerazione del metodo del GC è ottenuta scegliendo:

$$K^{-1} = D^{-1}$$ (20)

dove $D$ è la matrice diagonale contenente gli elementi diagonali di $A$. In questo caso, il calcolo della matrice di precondizionamento e la sua applicazione nello schema del GCM risultano banali e vengono lasciati per esercizio al lettore. Il raggruppamento degli autovalori attorno all'unità di $A D^{-1}$, tuttavia, può essere limitato, specialmente se $A$ presenta coefficienti extra-diagonali grandi rispetto agli elementi diagonali.

Risultati assai più significativi sono invece ottenuti assumendo:

$$K^{-1} = \left( \tilde{L} \tilde{L}^T \right)^{-1}$$ (21)

dove $\tilde{L}$, matrice triangolare bassa, è calcolata mediante la fattorizzazione incompleta di $A$, cioè la decomposta di Cholesky a cui viene assegnato il medesimo schema di sparsità di $A$. L'uso di questa matrice di precondizionamento, proposto negli anni '70 da Kershaw, si rivela generalmente un ottimo compromesso fra le contrapposte esigenze precedentemente discusse. Il calcolo di $K^{-1}$ secondo la (21) e la sua applicazione nell'algoritmo del GCM verranno esaminati nei due paragrafi seguenti.