Matriz de bandas

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 en cada lado.

Matriz de bandas

Ancho de banda

Formalmente, considere una matriz n × n A = ( a _i,j ). Si todos los elementos de la matriz son cero fuera de una banda delimitada 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₂; en otras palabras, 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 , con ancho de banda 0.
• Una matriz de bandas con k ₁ = k ₂ = 1 es una matriz tridiagonal , con ancho de banda 1.
• 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 en bloques
• Matrices de desplazamiento y matrices de cizallamiento
• Matrices en forma normal de Jordan
• Una matriz de horizonte , también llamada "matriz de banda variable", es una generalización de la matriz de banda.
• Las inversas de las matrices de Lehmer son matrices tridiagonales constantes y, por lo tanto, son matrices de bandas.

Aplicaciones

En el análisis numérico , las matrices de los problemas de elementos finitos o de diferencias finitas suelen estar en bandas. Estas matrices pueden considerarse 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 pueden dividirse aún más; por ejemplo, existen matrices en bandas en las que cada elemento de la banda es distinto de cero.

Los problemas en dimensiones superiores también dan lugar a matrices con bandas, en cuyo caso la banda en sí también tiende a ser dispersa. Por ejemplo, una ecuación diferencial parcial en un dominio cuadrado (utilizando 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 una matriz de este tipo da como resultado que la banda se rellene 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 de 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}}.}$

Se puede lograr 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 la 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 es siempre preferible a trabajar con matrices cuadradas de dimensiones similares . Una matriz de bandas puede compararse en complejidad con 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 un gran ahorro en términos de tiempo de cálculo y complejidad .

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 de la computadora, ha habido mucha investigación enfocada en encontrar formas de minimizar el ancho de banda (o minimizar directamente el relleno) aplicando permutaciones a la matriz u otras transformaciones de equivalencia o similitud similares. ^[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 Cuthill–McKee inverso funciona mejor. Existen 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-hard . ^[4]

Véase también

• Matriz diagonal
• Ancho de banda del gráfico

Notas

1. Golub y Van Loan 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áticas Industriales y Aplicadas, ISBN 978-0-898716-13-9.
• Feige, Uriel (2000), "Cómo afrontar la NP-dureza del problema del ancho de banda del grafo", Algorithm Theory - SWAT 2000 , Lecture Notes in Computer Science, vol. 1851, págs. 129-145, doi :10.1007/3-540-44985-X_2.
• Golub, Gene H. ; Van Loan, Charles F. (1996), Cálculos matriciales (3.ª ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.4", Recetas numéricas: el arte de la computación 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 matrices dispersas