En matemáticas , en particular en la teoría de matrices , una matriz de bandas o matriz de bandas es una matriz dispersa cuyas entradas distintas de cero se limitan a una banda diagonal , que comprende la diagonal principal y cero o más diagonales a cada lado.
Matriz de bandas
Banda ancha
Formalmente, considere una matriz de n × n A = ( a i, j ). Si todos los elementos de la matriz son cero fuera de una banda bordeada diagonalmente cuyo rango está determinado por las constantes k 1 y k 2 :
entonces las cantidades k 1 y k 2 se denominanmenor ancho de banda yancho de banda superior, respectivamente. [1] Elbanda anchade la matriz es el máximo de k 1 y k 2 ; en otras palabras, es el número k tal que Si . [2]
Ejemplos de
- Una matriz de bandas con k 1 = k 2 = 0 es una matriz diagonal
- Una matriz de bandas con k 1 = k 2 = 1 es una matriz tridiagonal
- Para k 1 = k 2 = 2 uno tiene una matriz pentadiagonal y así sucesivamente.
- Matrices triangulares
- Para k 1 = 0, k 2 = n −1, se obtiene la definición de una matriz triangular superior
- de manera similar, para k 1 = n −1, k 2 = 0 se obtiene una matriz triangular inferior.
- Matrices de Hessenberg superior e inferior
- Matrices Toeplitz cuando el ancho de banda es limitado.
- Bloquear matrices diagonales
- Matrices de desplazamiento y matrices de corte
- Matrices en forma normal de Jordan
- Una matriz de horizonte , también llamada "matriz de banda variable": una generalización de la matriz de bandas
- Las inversas de las matrices de Lehmer son matrices tridiagonales constantes y, por tanto, son matrices de bandas.
Aplicaciones
En el análisis numérico , las matrices de los problemas de elementos finitos o diferencias finitas a menudo se agrupan. Estas matrices pueden verse como descripciones del acoplamiento entre las variables del problema; la propiedad de bandas corresponde al hecho de que las variables no están acopladas en distancias arbitrariamente grandes. Dichas matrices se pueden dividir aún más; por ejemplo, existen matrices en bandas donde cada elemento de la banda es distinto de cero. A menudo surgen cuando se discretizan problemas unidimensionales. [ cita requerida ]
Los problemas en dimensiones más altas también conducen a matrices en bandas, en cuyo caso la banda en sí también tiende a ser escasa. Por ejemplo, una ecuación diferencial parcial en un dominio cuadrado (usando diferencias centrales) producirá una matriz con un ancho de banda igual a la raíz cuadrada de la dimensión de la matriz, pero dentro de la banda solo 5 diagonales son distintas de cero. Desafortunadamente, la aplicación de la eliminación gaussiana (o equivalentemente una descomposición LU ) a dicha matriz da como resultado que la banda se complete con muchos elementos distintos de cero.
Almacenamiento de bandas
Las matrices de bandas generalmente se almacenan almacenando las diagonales en la banda; el resto es implícitamente cero.
Por ejemplo, una matriz tridiagonal tiene ancho de banda 1. La matriz de 6 por 6
se almacena como la matriz de 6 por 3
Es posible un ahorro adicional cuando la matriz es simétrica. Por ejemplo, considere una matriz simétrica de 6 por 6 con un ancho de banda superior de 2:
Esta matriz se almacena como la matriz de 6 por 3:
Forma de banda de matrices dispersas
Desde un punto de vista computacional, trabajar con matrices de bandas siempre es preferible a trabajar con matrices cuadradas de dimensiones similares . Una matriz de bandas puede compararse en complejidad a una matriz rectangular cuya dimensión de fila es igual al ancho de banda de la matriz de bandas. Por lo tanto, el trabajo involucrado en la realización de operaciones como la multiplicación se reduce significativamente, lo que a menudo conduce a grandes ahorros en términos de tiempo y complejidad de cálculo .
Dado que las matrices dispersas se prestan a un cálculo más eficiente que las matrices densas, así como a una utilización más eficiente del almacenamiento informático, se han realizado muchas investigaciones centradas en encontrar formas de minimizar el ancho de banda (o minimizar directamente el relleno) aplicando permutaciones a la matriz, u otras transformaciones similares de equivalencia o similitud. [3]
El algoritmo de Cuthill-McKee se puede utilizar para reducir el ancho de banda de una matriz simétrica dispersa . Sin embargo, existen matrices para las que el algoritmo inverso de Cuthill-McKee funciona mejor. Hay muchos otros métodos en uso.
El problema de encontrar una representación de una matriz con un ancho de banda mínimo mediante permutaciones de filas y columnas es NP-difícil . [4]
Ver también
Notas
- ^ Golub y Van Loan 1996 , §1.2.1.
- ^ Atkinson 1989 , p. 527.
- ^ Davis , 2006 , §7.7.
- ^ Feige 2000 .
Referencias
- Atkinson, Kendall E. (1989), Introducción al análisis numérico , John Wiley & Sons, ISBN 0-471-62489-6.
- Davis, Timothy A. (2006), Métodos directos para sistemas lineales dispersos , Sociedad de Matemáticas Industriales y Aplicadas, ISBN 978-0-898716-13-9.
- Feige, Uriel (2000), "Afrontar la dureza NP del problema del ancho de banda del gráfico", Teoría de algoritmos - SWAT 2000 , Lecture Notes in Computer Science, 1851 , págs. 129-145, doi : 10.1007 / 3-540-44985 -X_2.
- Golub, Gene H .; Van Loan, Charles F. (1996), Computaciones matriciales (3.a ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.4" , Recetas numéricas: El arte de la informática científica (3ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8.
enlaces externos
- Información relativa a LAPACK y matrices de bandas
- Un tutorial sobre matrices en bandas y otros formatos de matriz dispersa