Álgebra linear numérica - Numerical linear algebra

A álgebra linear numérica , às vezes chamada de álgebra linear aplicada , é o estudo de como as operações de matriz podem ser usadas para criar algoritmos de computador que fornecem respostas aproximadas de forma eficiente e precisa para questões em matemática contínua . É um subcampo da análise numérica e um tipo de álgebra linear . Os computadores usam aritmética de ponto flutuante e não podem representar exatamente dados irracionais , portanto, quando um algoritmo de computador é aplicado a uma matriz de dados, às vezes pode aumentar a diferença entre um número armazenado no computador e o número verdadeiro do qual é uma aproximação. A álgebra linear numérica usa propriedades de vetores e matrizes para desenvolver algoritmos de computador que minimizam o erro introduzido pelo computador, e também se preocupa em garantir que o algoritmo seja o mais eficiente possível.

A álgebra linear numérica visa resolver problemas de matemática contínua usando computadores de precisão finita, portanto, suas aplicações às ciências naturais e sociais são tão vastas quanto as aplicações da matemática contínua. Muitas vezes, é uma parte fundamental dos problemas de engenharia e ciência computacional , como processamento de imagem e sinal , telecomunicações , finanças computacionais , simulações de ciência de materiais , biologia estrutural , mineração de dados , bioinformática e dinâmica de fluidos . Métodos matriciais são particularmente usadas em métodos finitos diferença , os métodos de elementos finitos , e a modelação de equações diferenciais . Observando as amplas aplicações da álgebra linear numérica, Lloyd N. Trefethen e David Bau, III argumentam que é "tão fundamental para as ciências matemáticas quanto cálculo e equações diferenciais", embora seja um campo comparativamente pequeno. Como muitas propriedades de matrizes e vetores também se aplicam a funções e operadores, a álgebra linear numérica também pode ser vista como um tipo de análise funcional com ênfase particular em algoritmos práticos.

Problemas comuns em álgebra linear numérica incluem a obtenção de decomposições de matriz como a decomposição de valor singular , a fatoração QR , a fatoração LU ou a decomposição automática , que pode então ser usada para responder a problemas algébricos lineares comuns, como resolução de sistemas lineares de equações, localização de autovalores ou otimização de mínimos quadrados. A preocupação central da álgebra linear numérica com o desenvolvimento de algoritmos que não introduzem erros quando aplicados a dados reais em um computador de precisão finita é freqüentemente alcançada por métodos iterativos em vez de diretos.

História

A álgebra linear numérica foi desenvolvida por pioneiros da computação como John von Neumann , Alan Turing , James H. Wilkinson , Alston Scott Householder , George Forsythe e Heinz Rutishauser , a fim de aplicar os primeiros computadores a problemas em matemática contínua, como problemas de balística e as soluções para sistemas de equações diferenciais parciais . A primeira tentativa séria de minimizar o erro do computador na aplicação de algoritmos a dados reais é o trabalho de John von Neumann e Herman Goldstine em 1947. O campo tem crescido à medida que a tecnologia tem permitido cada vez mais pesquisadores resolver problemas complexos em matrizes extremamente grandes de alta precisão , e alguns algoritmos numéricos cresceram em proeminência à medida que tecnologias como a computação paralela os tornaram abordagens práticas para problemas científicos.

Decomposições de matriz

Matrizes particionadas

Para muitos problemas de álgebra linear aplicada, é útil adotar a perspectiva de uma matriz como sendo uma concatenação de vetores de colunas. Por exemplo, quando a solução do sistema linear , em vez de entendimento x como o produto de com b , é útil pensar em x como o vetor de coeficientes na expansão linear de b na base formada pelas colunas de A . Pensar em matrizes como uma concatenação de colunas também é uma abordagem prática para fins de algoritmos de matriz. Isto é porque os algoritmos de matriz cont frequentemente dois circuitos encaixados: um sobre as colunas de uma matriz de um , e outro ao longo das linhas de Uma . Por exemplo, para matrizes e vetores e , poderíamos usar a perspectiva de particionamento de coluna para calcular Ax + y como ${\ displaystyle x = A ^ {- 1} b}$${\ displaystyle A ^ {- 1}}$${\ displaystyle A ^ {m \ times n}}$${\ displaystyle x ^ {n \ vezes 1}}$${\ displaystyle y ^ {m \ times 1}}$

for j = 1:n
  for i = 1:m
    y(i) = A(i,j)x(j) + y(i)
  end
end

Decomposição de valor singular

A decomposição de valor singular de uma matriz é onde U e V são unitários e são diagonais . Os elementos da diagonal de são chamados os valores singulares de A . Como os valores singulares são as raízes quadradas dos autovalores de , há uma conexão estreita entre a decomposição de valor singular e as decomposições de autovalor. Isso significa que a maioria dos métodos para calcular a decomposição de valor singular são semelhantes aos métodos de valor próprio; talvez o método mais comum envolva procedimentos de Householder . ${\ displaystyle A ^ {m \ times n}}$${\ displaystyle A = U \ Sigma V ^ {\ ast}}$${\ displaystyle \ Sigma}$${\ displaystyle \ Sigma}$${\ displaystyle AA ^ {\ ast}}$

Fatoração QR

A fatoração QR de uma matriz é uma matriz e uma matriz de modo que A = QR , onde Q é ortogonal e R é triangular superior . Os dois algoritmos principais para calcular as fatorações QR são o processo de Gram-Schmidt e a transformação de Householder . A fatoração QR é freqüentemente usada para resolver problemas lineares de mínimos quadrados e problemas de autovalores (por meio do algoritmo QR iterativo ). ${\ displaystyle A ^ {m \ times n}}$${\ displaystyle Q ^ {m \ times m}}$${\ displaystyle R ^ {m \ vezes n}}$

Fatoração LU

Uma fatoração LU de uma matriz A consiste em uma matriz triangular inferior L e uma matriz triangular superior M de modo que A = LU . A matriz U é encontrada por um procedimento de triangularização superior que envolve a multiplicação à esquerda de A por uma série de matrizes para formar o produto , de forma equivalente . ${\ displaystyle M_ {1}, \ ldots, M_ {n-1}}$${\ displaystyle M_ {n-1} \ cdots M_ {1} A = U}$${\ displaystyle L = M_ {1} ^ {- 1} \ cdots M_ {n-1} ^ {- 1}}$

Decomposição de autovalor

A decomposição de valores próprios de uma matriz é , em que as colunas de X são os vectores próprios de um , e é uma matriz diagonal os elementos da diagonal dos quais são os valores próprios correspondentes de Uma . Não existe um método direto para encontrar a decomposição dos valores próprios de uma matriz arbitrária. Como não é possível escrever um programa que encontre as raízes exatas de um polinômio arbitrário em tempo finito, qualquer solucionador de autovalor geral deve ser necessariamente iterativo. ${\ displaystyle A ^ {m \ times m}}$${\ displaystyle A = X \ Lambda X ^ {- 1}}$${\ displaystyle \ Lambda}$

Algoritmos

Eliminação gaussiana

Da perspectiva da álgebra linear numérica, a eliminação gaussiana é um procedimento para fatorar uma matriz A em sua fatoração LU , que a eliminação gaussiana realiza multiplicando à esquerda A por uma sucessão de matrizes até que U seja triangular superior e L seja triangular inferior, onde . Programas ingênuos para eliminação gaussiana são notoriamente altamente instáveis ​​e produzem erros enormes quando aplicados a matrizes com muitos dígitos significativos. A solução mais simples é introduzir o pivotamento , que produz um algoritmo de eliminação gaussiana modificado que é estável. ${\ displaystyle L_ {m-1} \ cdots L_ {2} L_ {1} A = U}$${\ displaystyle L \ equiv L_ {1} ^ {- 1} L_ {2} ^ {- 1} \ cdots L_ {m-1} ^ {- 1}}$

Soluções de sistemas lineares

A álgebra linear numérica aborda caracteristicamente as matrizes como uma concatenação de vetores de colunas. Para resolver o sistema linear , a abordagem algébrica tradicional é entender x como o produto de com b . Numérica álgebra linear em vez interpreta x como o vector de coeficientes de expansão linear de b na base formada pelas colunas de Uma . ${\ displaystyle x = A ^ {- 1} b}$${\ displaystyle A ^ {- 1}}$

Muitas decomposições diferentes podem ser usados para resolver o problema linear, dependendo das características da matriz A e os vetores x e b , que pode fazer uma fatoração muito mais fácil de obter do que outros. Se A = QR é uma fatoração QR de A , então de forma equivalente . Isso é fácil de calcular como uma fatoração de matriz. Se é uma autocomposição A , e procuramos encontrar b de forma que b = Ax , com e , então temos . Isso está intimamente relacionado à solução para o sistema linear usando a decomposição de valores singulares, porque os valores singulares de uma matriz são as raízes quadradas de seus autovalores. E se A = LU é um LU fatoração de uma , em seguida, Ax = b pode ser resolvido usando o triangular matrizes Ly = b e Ux = y . ${\ displaystyle Rx = Q ^ {\ ast} b}$${\ displaystyle A = X \ Lambda X ^ {- 1}}$${\ displaystyle b ^ {\ prime} = X ^ {- 1} b}$${\ displaystyle x ^ {\ prime} = X ^ {- 1} x}$${\ displaystyle b ^ {\ prime} = \ Lambda x ^ {\ prime}}$

Otimização de mínimos quadrados

As decomposições matriciais sugerem uma série de maneiras de resolver o sistema linear r = b - Ax onde buscamos minimizar r , como no problema de regressão . O algoritmo QR resolve esse problema definindo primeiro y = Ax e, em seguida, calculando a fatoração QR reduzida de A e reorganizando para obter . Este sistema triangular superior pode então ser resolvido para b . O SVD também sugere um algoritmo para a obtenção de mínimos quadrados lineares. Ao calcular a decomposição SVD reduzida e, em seguida, calcular o vetor , reduzimos o problema dos mínimos quadrados a um sistema diagonal simples. O fato de soluções de mínimos quadrados poderem ser produzidas pelas fatorações QR e SVD significa que, além do método clássico de equações normais para resolver problemas de mínimos quadrados, esses problemas também podem ser resolvidos por métodos que incluem o algoritmo de Gram-Schmidt e métodos de Householder. . ${\ displaystyle {\ widehat {R}} x = {\ widehat {Q}} ^ {\ ast} b}$${\ displaystyle A = {\ widehat {U}} {\ widehat {\ Sigma}} V ^ {\ ast}}$${\ displaystyle {\ widehat {U}} ^ {\ ast} b}$

Condicionamento e estabilidade

Admita que um problema é uma função , onde X é um espaço vetorial normatizado de dados e Y é um espaço vetorial normado de soluções. Para alguns dados , o problema é considerado mal condicionado se uma pequena perturbação em x produzir uma grande mudança no valor de f (x) . Podemos quantificar isso definindo um número de condição que representa o quão bem condicionado um problema é, definido como ${\ displaystyle f: X \ a Y}$${\ displaystyle x \ in X}$

${\ displaystyle {\ widehat {\ kappa}} = \ lim _ {\ delta \ to 0} \ sup _ {\ | \ delta x \ | \ leq \ delta} {\ frac {\ | \ delta f \ |} {\ | \ delta x \ |}}.}$

A instabilidade é a tendência dos algoritmos de computador, que dependem da aritmética de ponto flutuante , para produzir resultados que diferem dramaticamente da solução matemática exata para um problema. Quando uma matriz contém dados reais com muitos dígitos significativos , muitos algoritmos para resolver problemas como sistemas lineares de equação ou otimização de mínimos quadrados podem produzir resultados altamente imprecisos. A criação de algoritmos estáveis ​​para problemas mal condicionados é uma preocupação central na álgebra linear numérica. Um exemplo é que a estabilidade da triangularização do agregado familiar torna um método de solução particularmente robusto para sistemas lineares, enquanto a instabilidade do método de equações normais para resolver problemas de mínimos quadrados é uma razão para favorecer métodos de decomposição de matriz como usar a decomposição de valor singular. Alguns métodos de decomposição de matrizes podem ser instáveis, mas possuem modificações diretas que os tornam estáveis; um exemplo é o Gram-Schmidt instável, que pode ser facilmente alterado para produzir o Gram-Schmidt modificado estável . Outro problema clássico em álgebra linear numérica é a descoberta de que a eliminação gaussiana é instável, mas se torna estável com a introdução do pivotamento.

Métodos iterativos

Existem dois motivos pelos quais os algoritmos iterativos são uma parte importante da álgebra linear numérica. Primeiro, muitos problemas numéricos importantes não têm solução direta; para encontrar os autovalores e autovetores de uma matriz arbitrária, podemos apenas adotar uma abordagem iterativa. Em segundo lugar, os algoritmos não literários para uma matriz arbitrária requerem tempo, o que é um piso surpreendentemente alto, dado que as matrizes contêm apenas números. As abordagens iterativas podem tirar proveito de vários recursos de algumas matrizes para reduzir esse tempo. Por exemplo, quando uma matriz é esparsa , um algoritmo iterativo pode pular muitas das etapas que uma abordagem direta necessariamente seguiria, mesmo se fossem etapas redundantes em uma matriz altamente estruturada. ${\ displaystyle m \ times m}$${\ displaystyle O (m ^ {3})}$${\ displaystyle m ^ {2}}$

O núcleo de muitos métodos iterativos em álgebra linear numérica é a projeção de uma matriz em um subespaço de Krylov de dimensão inferior , que permite que os recursos de uma matriz de alta dimensão sejam aproximados pela computação iterativa dos recursos equivalentes de matrizes semelhantes começando em um espaço de baixa dimensão e movendo-se para dimensões sucessivamente mais altas. Quando A é simétrico e queremos resolver o problema linear Ax = b , a abordagem iterativa clássica é o método do gradiente conjugado . Se A não for simétrico, exemplos de soluções iterativas para o problema linear são o método dos resíduos mínimos generalizados e o CGN . Se A for simétrico, então para resolver o problema dos autovalores e autovetores, podemos usar o algoritmo de Lanczos , e se A for não simétrico, podemos usar a iteração de Arnoldi .

Programas

Várias linguagens de programação usam técnicas de otimização de álgebra linear numérica e são projetadas para implementar algoritmos de álgebra linear numérica. Essas linguagens incluem MATLAB , Analytica , Maple e Mathematica . Outras linguagens de programação que não são explicitamente projetadas para álgebra linear numérica têm bibliotecas que fornecem rotinas e otimização de álgebra linear numérica; C e Fortran têm pacotes como Basic Linear Algebra Subprograms e LAPACK , python tem a biblioteca NumPy e Perl tem Perl Data Language . Muitos comandos de álgebra linear numérica em R contam com essas bibliotecas mais fundamentais como LAPACK . Mais bibliotecas podem ser encontradas na Lista de bibliotecas numéricas .

Referências

Leitura adicional

• Dongarra, Jack ; Hammarling, Sven (1990). "Evolução do software numérico para álgebra linear densa". Em Cox, MG; Hammarling, S. (eds.). Computação Numérica Confiável . Oxford: Clarendon Press. pp. 297–327. ISBN   0-19-853564-3 .

links externos

• Software para álgebra numérica disponível gratuitamente na web , composto por Jack Dongarra e Hatem Ltaief, University of Tennessee
• Biblioteca NAG de rotinas de álgebra linear numérica
• Grupo de álgebra linear numérica no Twitter (grupo de pesquisa no Reino Unido)
• siagla no Twitter (grupo de atividades sobre álgebra linear numérica na sociedade para matemática industrial e aplicada )
• Grupo de Atividades GAMM em Álgebra Linear Aplicada e Numérica