Matriz de banda

En matemáticas, particularmente en teoría de matrices, una matriz de bandas o una matriz de bandas es una matriz dispersa cuyas entradas distintas de cero se limitan a una banda, que comprende la diagonal principal y cero o más diagonales a 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 bordeada diagonalmente cuyo rango está determinado por las constantes k₁ y k₂ :

<math alttext="{displaystyle a_{i,j}=0quad {mbox{if}}quad ji+k_{2};quad k_{1},k_{2}geq 0.,}" xmlns="http://www.w3.org/1998/Math/MathML">ai,j=0sijc)i− − k1 o j■i+k2;k1,k2≥ ≥ 0.{displaystyle a_{i,j}=0quad {mbox{if}quad {fnMicrosoft Sans}fnK} j títuloi+k_{2};quad K_{1},k_{2}geq 0,}<img alt="{displaystyle a_{i,j}=0quad {mbox{if}}quad ji+k_{2};quad k_{1},k_{2}geq 0.,}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/400386f6da3230400608478a17b7f02ab6cb2e7b" style="vertical-align: -1.005ex; width:55.456ex; height:2.843ex;"/>

entonces las cantidades k₁ y k₂ son llamados inferior ancho de banda y ancho de banda superior, respectivamente. El ancho de banda de la matriz es el máximo k₁ y k₂; en otras palabras, es el número k tales que ai,j=0{displaystyle a_{i,j}=0} si k}" xmlns="http://www.w3.org/1998/Math/MathML">Silencioi− − jSilencio■k{displaystyle Silencio.k}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf649e164eaa3dc51af3cb39455302360c981d0a" style="vertical-align: -0.838ex; width:10.204ex; height:2.843ex;"/>.

Ejemplos

• Una matriz de banda con k₁ = k₂ = 0 es una matriz diagonal
• Una matriz de banda con k₁ = k₂ = 1 es una matriz tridiagonal
• Para k₁ = k₂ = 2 uno 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
  • similarmente, para k₁ = n−1, k₂ = 0 se obtiene una matriz triangular inferior.
• Matrices Hessenberg superiores e inferiores
• Toeplitz matrices cuando el ancho de banda es limitado.
• Bloquea matrices diagonales
• Matrices de robo y matrices de corte
• Matrices en Jordania
• Una matriz de skyline, también llamada " matriz de banda variable" – una generalización de matriz de banda
• Los inversos de las matrices Lehmer son matrices tridiagonales constantes, y son así matrices de banda.

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.

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 banda 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

[B11B120⋯ ⋯ ⋯ ⋯ 0B21B22B23⋱ ⋱ ⋱ ⋱ ⋮ ⋮ 0B32B33B34⋱ ⋱ ⋮ ⋮ ⋮ ⋮ ⋱ ⋱ B43B44B450⋮ ⋮ ⋱ ⋱ ⋱ ⋱ B54B55B560⋯ ⋯ ⋯ ⋯ 0B65B66]{BdotsBdotsBdotsBdots}BdotsBdotsB_{21}{B_{22} {BdotsBdotsBdotsBdotsBdotsBdotsBdots2}

se almacena como la matriz de 6 por 3

[0B11B12B21B22B23B32B33B34B43B44B45B54B55B56B65B660].{B_00}B_{4}B_}B_}B_}B_}B_}B_{22}B_{23}B_{32}B_{34}B_{34}B_{44}}}}B_{4}B_}}B_#{4}}}}} {B_}}}}}}}}}}}}}}}}}}}}}}B_######################################################################################################################################

Un ahorro adicional es posible 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:

[A11A12A130⋯ ⋯ 0A22A23A24⋱ ⋱ ⋮ ⋮ A33A34A350A44A45A46sSí.mA55A56A66].{displaystyle {begin{bmatrix}A_{11} limitA_{12} limitA_{13} limit0 limitcdots {0\cH00}cH00}cH009}cdotsvdots\\cH003} {33} limitA_{34} reducidaA_{35} {0\\cH009}cH00_{45}c4}cH00}cH00}cH00}cH0} {cH00}cH00}}}}cH00}}}}}cH00}}}cH00}}cH00}}}cH00}cH00}cH00}cH00}cH00}}}}}}}}}}}}}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}}}cH00}cH00}}}cH00}}cH00}}}cH00}}}}cH00}

Esta matriz se almacena como matriz de 6 por 3:

[A11A12A13A22A23A24A33A34A35A44A45A46A55A560A6600].{displaystyle {begin{bmatrix}A_{11} limitA_{12} limitA_{13}\A_{22} limitA_{23} {24}A_{24}A_{33} limitA_}{35}A_{40}} {0}{0}{0}{0}{0}{0}{0}{0}{0}{0}{0}}}}}{0}{0}{0}{0}}}}}{0}}{0}{0}}}}}}}}}}{0}}}}{0}}}}}}}}}}}}}}}}{0}}}}}}{0}}}}}}}}}}}}}}}}{0}{0}}{0}}}}{0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

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.

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) mediante aplicar permutaciones a la matriz u otras transformaciones de equivalencia o similitud similares.

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