Matrice a banda

Da Wikipedia, l'enciclopedia libera.

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=(ai,j ) è una matrice a banda se tutti gli elementi dalla matrice all'esterno di una striscia diagonale la cui ampiezza è determinata dalle costanti k1 e k2:

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 \ge 0.

Le quantità k1 e k2 sono le semiampiezze di banda rispettivamente sinistra e destra. La banda della matrice è k1 + k2 + 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 k1 = k2 = 0 è una matrice diagonale: una con k1 = k2 = 1 è una matrice tridiagonale; Se k1 = k2 = 2 si ha una matrice pentadiagonale, e così via. Se si impone che k1 = 0, k2 = n−1, si ottiene la definizione di una matrice triangolare inferiore; similmente, con k1 = n−1, k2 = 0 si ottiene una matrice triangolare superiore.

Applicazioni[modifica | modifica sorgente]

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.[senza fonte]

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. [senza fonte]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

I seguenti sono casi degeneri di una matrice a banda:

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

Note[modifica | modifica sorgente]

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

Collegamenti esterni[modifica | modifica sorgente]