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=(a_i,j ) è una matrice a banda se tutti gli elementi dalla matrice 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 \ge 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 inferiore; similmente, con k₁ = n−1, k₂ = 0 si ottiene una matrice triangolare superiore.

[modifica] 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.^{[citazione necessaria]}

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 eliminazinoe 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. ^{[citazione necessaria]}

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.

[modifica] 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 3 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}$

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

[modifica] Note

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

[modifica] Collegamenti esterni

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Matrice a banda

Da Wikipedia, l'enciclopedia libera.

Indice

[modifica] Applicazioni

[modifica] Memorizzazione della banda

[modifica] Esempi e casi degeneri

[modifica] Note

[modifica] Collegamenti esterni

Views

Navigazione

comunità

Ricerca

Altre lingue