Em matemática, particularmente na teoria matricial, uma matriz banda é uma matriz esparsa cujas entradas diferentes de zero estão confinadas a uma banda diagonal, compreendendo a diagonal principal e zero ou mais diagonais em cada lado.
Formalmente, considere uma matriz , . Se todos os elementos da matriz forem zero fora de uma banda com borda diagonal, cujo intervalo é determinado pelas constantes e :
então as quantidades e são chamadas de largura de banda inferior e largura de banda superior, respectivamente[1] A largura de banda da matriz é o máximo de e ; em outras palavras, é o número tal que se .[2]
Uma matriz é chamada de matriz banda ou matriz de banda se sua largura de banda for razoavelmente pequena.[necessário esclarecer]
Na análise numérica, matrizes de problemas de elementos finitos ou diferenças finitas são frequentemente agrupadas. Essas matrizes podem ser vistas como descrições do acoplamento entre as variáveis do problema; a propriedade com bandas corresponde ao fato de que as variáveis não são acopladas em distâncias arbitrariamente grandes. Essas matrizes podem ser divididas posteriormente – por exemplo, matrizes banda existem onde cada elemento na banda é diferente de zero. Muitas vezes surgem ao discriminar problemas unidimensionais.[carece de fontes]
Problemas em dimensões superiores também levam a matrizes banda, caso em que a própria banda tende a ser esparsa. Por exemplo, uma equação diferencial parcial em um domínio quadrado (usando diferenças centrais) produzirá uma matriz com largura de banda igual à raiz quadrada da dimensão da matriz, mas dentro da banda apenas 5 diagonais são diferentes de zero. Infelizmente, a aplicação de eliminação Gaussiana (ou equivalentemente uma decomposição LU) a tal matriz resulta na banda sendo preenchida por muitos elementos diferentes de zero.
Matrizes banda são geralmente armazenadas armazenando as diagonais na banda; o resto é implicitamente zero.
Por exemplo, uma matriz tridiagonal tem largura de banda 1. A matriz 6 por 6
é armazenada como a matriz 6 por 3
Uma economia adicional é possível quando a matriz é simétrica. Por exemplo, considere uma matriz simétrica 6 por 6 com uma largura de banda superior de 2:
Esta matriz é armazenada como a matriz 6 por 3:
Do ponto de vista computacional, trabalhar com matrizes banda é sempre preferencial a trabalhar com matrizes quadradas de dimensões semelhantes. Uma matriz banda pode ser comparada em complexidade a uma matriz retangular cuja dimensão da linha é igual à largura de banda da matriz de banda. Assim, o trabalho envolvido na execução de operações como a multiplicação cai significativamente, muitas vezes levando a uma enorme economia em termos de tempo de cálculo e complexidade.
Como matrizes esparsas se prestam a cálculos mais eficientes do que matrizes densas, bem como na utilização mais eficiente de armazenamento de computador, tem havido muitas pesquisas focadas em encontrar maneiras de minimizar a largura de banda (ou minimizar diretamente o preenchimento) aplicando permutações para a matriz, ou outras transformações de equivalência ou similaridade.[3]
O algoritmo Cuthill–McKee pode ser usado para reduzir a largura de banda de uma matriz simétrica esparsa. Existem, no entanto, matrizes para as quais o algoritmo reverso de Cuthill–McKee tem melhor desempenho. Existem muitos outros métodos em uso.
O problema de encontrar uma representação de uma matriz com largura de banda mínima por meio de permutações de linhas e colunas é NP-difícil.[4]
Classes de matriz | |
---|---|
Elementos explicitamente restritos |
|
Constante |
|
Condições sobre autovalores e autovetores |
|
Satisfazendo condições sobre produtos ou inversas |
|
Com aplicações específicas |
|
Usada em estatística |
|
Usada em teoria dos grafos |
|
Usada em ciência e engenharia |
|
Termos relacionados | |