Matrice a banda

In matematica, ed in particolare nella teoria delle matrici, una matrice a banda è una matrice sparsa i cui elementi diversi da zero sono tutti posti in una banda diagonale che comprende la diagonale principale e, opzionalmente, una o più diagonali alla sua destra od alla sua sinistra.

Formalmente una matrice n×n A=(a_i,j ) è una matrice a banda se sono nulli tutti gli elementi all'esterno di una striscia diagonale, la cui ampiezza è determinata dalle costanti k₁ e k₂:

$a_{i,j}=0\quad {\mbox{se}}\quad j<i-k_{1}\quad {\mbox{ o }}\quad j>i+k_{2};\quad k_{1},k_{2}\geq 0.$

Le quantità k₁ e k₂ sono le semiampiezze di banda rispettivamente sinistra e destra. La banda della matrice è k₁ + k₂ + 1 (in altre parole, il più piccolo numero di diagonali adiacenti in cui sono raggruppati gli elementi diversi da zero).

Una matrice a banda con k₁ = k₂ = 0 è una matrice diagonale: una con k₁ = k₂ = 1 è una matrice tridiagonale; Se k₁ = k₂ = 2 si ha una matrice pentadiagonale, e così via. Se si impone che k₁ = 0, k₂ = n−1, si ottiene la definizione di una matrice triangolare superiore; similmente, con k₁ = n−1, k₂ = 0 si ottiene una matrice triangolare inferiore.

Applicazioni

Nell'analisi numerica, le matrici utilizzate nei problemi risolvibili tramite il metodo degli elementi finiti od il metodo delle differenze finite sono spesso a banda. Queste matrici possono essere viste come la descrizione dell'accoppiamento tra le variabili del problema; la presenza di una banda corrisponde al fatto che le variabili non sono accoppiate su distanze grandi a piacere. Queste matrici non possono essere ulteriormente divise - ad esempio, le matrici a banda esistono quando ogni elemento della banda è diverso da zero. Esse sono spesso generate quando si trattano nel discreto problemi monodimensionali.

I problemi in più dimensioni possono portare anch'essi a matrici a banda, ed in questo caso anche la banda in sé tende ad essere sparsa. Ad esempio, un'equazione differenziale alle derivate parziali su un dominio quadrato (usando le differenze centrali) restituirà un matrice con una semibanda uguale alla radice quadra della dimensione della matrice, ma all'interno della banda solo 5 diagonali sono diverse da zero. Sfortunatamente, l'applicazione del metodo di eliminazione di Gauss (o, in maniera equivalente, della decomposizione LU) a una matrice siffatta comporta il riempimento della banda di molti elementi diversi da zero. Dal momento che le matrici sparse tendono ad essere più efficienti, dal punto di vista computazionale, delle matrici dense, sono state svolte molte ricerche con l'obiettivo di trovare il modo di minimizzare la banda (o, direttamente, di minimizzare il fill-in applicando delle permutazioni alla matrice, oppure altre trasformazioni per equivalenza o similitudine.

Da un punto di vista computazionale, lavorare con matrici a banda è sempre preferibile a farlo con matrici quadrate dense di pari dimensioni. Una matrice a banda può essere assimilata, quanto a complessità, a una matrice rettangolare in cui la dimensione delle righe è pari alla banda della matrice di partenza. Per questo motivo, l'impiego di risorse per svolgere operazioni quali le moltiplicazioni si riduce significativamente, e si arriva spesso a grandi risparmi in termini di tempo e di complessità di calcolo.

Memorizzazione della banda

Le matrici a banda sono spesso memorizzate tenendo conto solo della diagonale della banda; il resto della matrice viene implicitamente considerato pari a zero.

Per esempio, si consideri una matrice tridiagonale con banda pari a 3. La matrice 6 per 6

${\begin{bmatrix}B_{11}&B_{12}&0&\cdots &\cdots &0\\B_{21}&B_{22}&B_{23}&\ddots &\ddots &\vdots \\0&B_{32}&B_{33}&B_{34}&\ddots &\vdots \\\vdots &\ddots &B_{43}&B_{44}&B_{45}&0\\\vdots &\ddots &\ddots &B_{54}&B_{55}&B_{56}\\0&\cdots &\cdots &0&B_{65}&B_{66}\end{bmatrix}}$

può essere memorizzata come una matrice 6 per 3

${\begin{bmatrix}0&B_{11}&B_{12}\\B_{21}&B_{22}&B_{23}\\B_{32}&B_{33}&B_{34}\\B_{43}&B_{44}&B_{45}\\B_{54}&B_{55}&B_{56}\\B_{65}&B_{66}&0\end{bmatrix}}$

Un risparmio ancora maggiore è possibile quando la matrice è simmetrica. Ad esempio, si consideri una matrice simmetrica 6 per 6 con banda destra pari a 2:

${\begin{bmatrix}A_{11}&A_{12}&A_{13}&0&\cdots &0\\&A_{22}&A_{23}&A_{24}&\ddots &\vdots \\&&A_{33}&A_{34}&A_{35}&0\\&&&A_{44}&A_{45}&A_{46}\\&sym&&&A_{55}&A_{56}\\&&&&&A_{66}\end{bmatrix}}$

Questa matrice può essere memorizzata come una matrice 6 per 3:

${\begin{bmatrix}A_{11}&A_{12}&A_{13}\\A_{22}&A_{23}&A_{24}\\A_{33}&A_{34}&A_{35}\\A_{44}&A_{45}&A_{46}\\A_{55}&A_{56}&0\\A_{66}&0&0\end{bmatrix}}$

Esempi e casi degeneri

I seguenti sono casi degeneri di una matrice a banda:

• Matrice diagonale
• Matrice tridiagonale
• Matrice pentadiagonale
• Matrice triangolare superiore ed inferiore.
• Matrice di Hessenberg superiore ed inferiore.
• Matrice a blocchi.
• Matrice shift e Matrice shear.
• Matrici in forma canonica di Jordan.
• Una matrice grattacielo è una maniera più compatta di memorizzare una matrice a banda.

Le inverse delle matrici di Lehmer sono matrici tridiagonali costanti, e sono quindi matrici a banda.

Note

La rappresentazione delle matrici a banda nel pacchetto LAPACK per il linguaggio Fortran non è congruente a quella del pacchetto EISPACK.

Collegamenti esterni

• (EN) Informazioni relative a LAPACK e alle matrici a banda, su netlib.org.
• (EN) Tutoriali sulle matrici a banda e su altri tipi di matrici sparse, su netlib.org.
• (EN) Introduzione alla rappresentazione matriciale, su intel.com. URL consultato il 23 aprile 2008 (archiviato dall'url originale il 9 aprile 2008).
• (EN) Introduzione alla rappresentazioni della banda, su cs.ut.ee. URL consultato il 23 aprile 2008 (archiviato dall'url originale il 28 dicembre 2007).

Controllo di autorità	GND (DE) 4134366-9