Como escolher um método para resolver equações lineares

31

Que eu saiba, existem 4 maneiras de resolver um sistema de equações lineares (corrija-me se houver mais):

  1. Se a matriz do sistema for uma matriz quadrada de classificação completa, você poderá usar a Regra de Cramer;
  2. Calcule o inverso ou o pseudo-inverso da matriz do sistema;
  3. Use métodos de decomposição matricial (a eliminação Gaussiana ou Gauss-Jordan é considerada como decomposição LU);
  4. Use métodos iterativos, como o método de gradiente conjugado.

De fato, você quase nunca deseja resolver as equações usando a regra de Cramer ou computando o inverso ou o pseudo-inverso, especialmente para matrizes de alta dimensão, portanto a primeira pergunta é quando usar métodos de decomposição e métodos iterativos, respectivamente. Eu acho que depende do tamanho e das propriedades da matriz do sistema.

A segunda pergunta é, que você saiba, que tipo de métodos de decomposição ou métodos iterativos são mais adequados para determinada matriz do sistema em termos de estabilidade e eficiência numéricas.

Por exemplo, o método gradiente conjugado é usado para resolver equações em que a matriz é simétrica e definida positiva, embora também possa ser aplicada a qualquer equação linear convertendo em . Também para a matriz definida positiva, você pode usar o método de decomposição de Cholesky para buscar a solução. Mas não sei quando escolher o método de CG e quando escolher a decomposição de Cholesky. Meu sentimento é que é melhor usarmos o método CG para matrizes grandes.A T A x = A T bUMAx=bATAx=ATb

Para matrizes retangulares, podemos usar a decomposição QR ou SVD, mas, novamente, não sei como escolher uma delas.

Para outras matrizes, agora não sei como escolher o solucionador apropriado, como matrizes hermitianas / simétricas, matrizes esparsas, matrizes de banda etc.

chaohuang
fonte
1
Olá @chaohuang, e bem-vindo ao SciComp! Você pode querer assistir a esta discussão: scicomp.stackexchange.com/questions/81/…
Paul
Oi @Paul, obrigado por seus comentários, esse tópico é apenas sobre matrizes esparsas ou qualquer matriz?
chaohuang
6
Sua pergunta tem um escopo enorme e pode ser um pouco ampla para o formato de perguntas e respostas que temos aqui na stackexchange ... existe uma classe específica de sistema de matriz em que você está interessado?
Paul
3
@chaohuang Existem inúmeros livros sobre esse assunto. Esta pergunta é como perguntar a um médico como eles escolhem os tratamentos "em geral". Se você quiser fazer uma pergunta que não é específica para uma determinada classe de problemas, faça o trabalho de familiarizar-se o suficiente com o campo para fazer algo preciso. Caso contrário, explique o problema específico com o qual você está preocupado.
Jed Brown
2
Do FAQ: Se você pode imaginar um livro inteiro que responda à sua pergunta, está pedindo demais. Existem diários inteiros e centenas de livros associados a esta pergunta.
David Ketcheson

Respostas:

45

Sua pergunta é como perguntar qual chave de fenda escolher, dependendo da unidade (slot, Phillips, Torx, ...): Além de haver muitas , a escolha também depende se você deseja apenas apertar um parafuso ou montar um conjunto inteiro de prateleiras da biblioteca. No entanto, em resposta parcial à sua pergunta, aqui estão alguns dos problemas que você deve ter em mente ao escolher um método para resolver o sistema linear . Também vou me restringir a matrizes invertíveis; os casos de sistemas super ou subdeterminados são uma questão diferente e devem realmente ser perguntas separadas.Ax=b

Como você observou corretamente, as opções 1 e 2 estão corretas: calcular e aplicar a matriz inversa é uma ideia tremendamente ruim, pois é muito mais cara e geralmente numericamente menos estável do que a aplicação de um dos outros algoritmos. Isso deixa você com a escolha entre métodos diretos e iterativos. A primeira coisa a considerar não é a matriz , mas o que você espera da solução numérica ˜ x :Ax~

  1. Quão preciso ele precisa ser? Does tem que resolver o sistema até precisão da máquina, ou você está satisfeito com ~ x satisfazendo (digamos) ~ x - x *< 10 - 3 , onde x * é a solução exata?x~x~x~x<103x
  2. Quão rápido você precisa? A única métrica relevante aqui é a hora do relógio na sua máquina - um método que escala perfeitamente em um cluster enorme pode não ser a melhor opção se você não tiver uma dessas, mas você tem uma daquelas novas e brilhantes placas de Tesla.

Como não existe almoço grátis, você geralmente precisa decidir sobre uma troca entre os dois. Depois disso, você começa a examinar a matriz (e seu hardware) para decidir sobre um bom método (ou melhor, o método para o qual você pode encontrar uma boa implementação). (Observe como evitei escrever "melhor" aqui ...) As propriedades mais relevantes aqui sãoA

  • A estrutura : é simétrica? É denso ou escasso? Unido?A
  • Os autovalores : todos eles são positivos (isto é, é positivo)? Eles estão agrupados? Alguns deles têm magnitude muito pequena ou muito grande?A

Com isso em mente, você deve vasculhar a (enorme) literatura e avaliar os diferentes métodos encontrados para o seu problema específico. Aqui estão algumas observações gerais:

  • Se você realmente precisa (quase) da precisão da máquina para sua solução, ou se sua matriz é pequena (por exemplo, até linhas), é difícil vencer métodos diretos, especialmente para sistemas densos (pois, neste caso, toda multiplicação de matrizes será O ( n 2 ) e, se você precisar de muitas iterações, isso pode não estar muito longe do O ( n 3 ) que um método direto precisa). Além disso, a decomposição da LU (com pivô) funciona para qualquer matriz invertível, em oposição à maioria dos métodos iterativos. (Obviamente, se A for simétrico e positivo, você usaria Cholesky.)1000O(n2)O(n3)A

    Isso também é válido para matrizes esparsas (grandes) se você não tiver problemas de memória: as matrizes esparsas em geral não têm uma decomposição de LU esparsa e, se os fatores não se encaixam na memória (rápida), esses métodos se tornam inutilizáveis.

    Além disso, os métodos directos têm sido em torno de um longo período de tempo, e existe software de muito alta qualidade (por exemplo, UMFPACK, papeira, SuperLU para matrizes esparsas) que automaticamente pode explorar a estrutura de banda de .A

  • Se você precisar de menos precisão ou não puder usar métodos diretos, escolha um método de Krylov (por exemplo, CG se for simétrico positivo definido, GMRES ou BiCGStab, se não) em vez de um método estacionário (como Jacobi ou Gauss-Seidel): estes geralmente funcionam muito melhor, pois sua convergência não é determinada pelo raio espectral de A, mas pela (raiz quadrada) do número da condição e não depende da estrutura da matriz. No entanto, para obter um desempenho realmente bom com um método de Krylov, você precisa escolher um bom pré-condicionador para sua matriz - e isso é mais um ofício do que uma ciência ...AA

  • Se você precisar repetidamente resolver sistemas lineares com a mesma matriz e diferentes lados do lado direito, os métodos diretos ainda poderão ser mais rápidos que os métodos iterativos, pois você só precisará calcular a decomposição uma vez. (Isso pressupõe uma solução seqüencial; se você tiver todos os lados do lado direito ao mesmo tempo, poderá usar os métodos de Krylov do bloco).

Obviamente, estas são apenas diretrizes muito aproximadas: Para qualquer uma das declarações acima, provavelmente existe uma matriz para a qual o inverso é verdadeiro ...

Como você solicitou referências nos comentários, aqui estão alguns livros e documentos de revisão para você começar. (Nenhum desses - nem o conjunto - é abrangente; essa questão é muito ampla e depende muito do seu problema específico.)

Christian Clason
fonte
2
Eu gosto da sua analogia da chave de fenda!
Paul
@chaohuang Se isso respondeu à sua pergunta, você deve aceitá-la. (Se isso não aconteceu, fique à vontade para apontar o que está faltando.)
Christian Clason
@ChristianClason aceitou. Eu estava esperando e esperando que alguém pudesse lançar alguma luz sobre a questão das matrizes retangulares. Uma vez que tem sido um longo tempo, eu acho que nunca haverá uma resposta tão :(
chaohuang
@chaohuang Obrigado. Se você ainda estiver interessado em matrizes retangulares, faça uma pergunta (vinculada) em "Como escolher um método para resolver sistemas sobredeterminados".
Christian Clason
Aqui, uma referência sobre o uso de métodos iterativos para resolver grandes sistemas esparsos de equações lineares.
chaohuang