matriz de banda

Matriz con elementos distintos de cero solo en una banda diagonal

En matemáticas , particularmente en teoría de matrices , una matriz de bandas o matriz de bandas es una matriz dispersa cuyas entradas distintas de cero están confinadas a una banda diagonal , que comprende la diagonal principal y cero o más diagonales a cada lado.

matriz de banda

Banda ancha

Formalmente, considere una matriz 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 ₁ y k ₂ :

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

entonces las cantidades k ₁ y k ₂ se llamanmenor ancho de banda yancho de banda superior , respectivamente.^[1]Elel ancho de banda de la matriz es el máximo dek₁yk₂; es decir, es el númeroktal quesi.^[2] ${\displaystyle a_{i,j}=0}$ ${\displaystyle |i-j|>k}$

Ejemplos

• Una matriz de bandas con k ₁ = k ₂ = 0 es una matriz diagonal
• Una matriz de bandas con k ₁ = k ₂ = 1 es una matriz tridiagonal
• Para k ₁ = k ₂ = 2 se tiene una matriz pentadiagonal y así sucesivamente.
• Matrices triangulares
  • Para k ₁ = 0, k ₂ = n −1, se obtiene la definición de una matriz triangular superior
  • de manera similar, para k ₁ = n −1, k ₂ = 0 se obtiene una matriz triangular inferior.
• Matrices de Hessenberg superior e inferior.
• Matrices de Toeplitz cuando el ancho de banda es limitado.
• Matrices diagonales de bloques
• 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 banda
• 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 problemas de elementos finitos o diferencias finitas suelen tener bandas. 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. Estas matrices se pueden dividir aún más; por ejemplo, existen matrices con bandas donde cada elemento de la banda es distinto de cero. Estos surgen a menudo al discretizar problemas unidimensionales. ^{[ cita necesaria ]}

Los problemas en dimensiones superiores también conducen a matrices con 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, aplicar 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 banda

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 un ancho de banda 1. La matriz de 6 por 6

${\displaystyle {\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}}}$

se almacena como la matriz de 6 por 3

${\displaystyle {\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}}.}$

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:

${\displaystyle {\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}}.}$

Esta matriz se almacena como matriz de 6 por 3:

${\displaystyle {\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}}.}$

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 realizar operaciones como la multiplicación se reduce significativamente, lo que a menudo genera enormes ahorros en términos de tiempo y complejidad de cálculo .

Como 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 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 ancho de banda mínimo mediante permutaciones de filas y columnas es NP-difícil . ^[4]

Ver también

• Matriz diagonal
• Ancho de banda del gráfico

Notas

1. Préstamo Golub & Van 1996, §1.2.1.
2. Atkinson 1989, pág. 527.
3. Davis 2006, §7.7.
4. 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ática Industrial y Aplicada, ISBN 978-0-898716-13-9.
• Feige, Uriel (2000), "Hacer frente a la dureza NP del problema del ancho de banda del gráfico", Teoría de algoritmos - SWAT 2000 , Apuntes de conferencias sobre informática, vol. 1851, págs. 129-145, doi :10.1007/3-540-44985-X_2.
• Golub, Gene H .; Van Loan, Charles F. (1996), Computaciones matriciales (3.ª ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
• Prensa, 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 con bandas y otros formatos de matrices dispersas