Métodos Diretos para Sistemas Lineares

Métodos diretos resolvem um sistema linear Ax = b em um número finito de etapas aritméticas, tipicamente fatorando a matriz e então resolvendo sistemas triangulares por substituição.

Definition

Um método direto é um algoritmo que calcula a solução exata de um sistema linear — até o erro de arredondamento — em um número finito e predeterminado de operações, em oposição a um método iterativo que produz uma sequência de aproximações.

Scope

Este tópico abrange a eliminação gaussiana, sua expressão como uma fatoração LU, o papel do pivoteamento no controle do crescimento de erros, substituição progressiva e retroativa para sistemas triangulares, e as contagens de operações que tornam os resolvedores diretos práticos para matrizes densas e em banda.

Core questions

• Como a eliminação gaussiana reduz um sistema à forma triangular, e por que isso é equivalente a uma fatoração LU?
• Por que o pivoteamento é necessário, e como o pivoteamento parcial e completo controlam o crescimento do erro de arredondamento?
• Qual é o custo computacional de uma resolução direta, e como a exploração da estrutura (simetria, bandedness, esparsidade) o reduz?
• Sob quais condições a eliminação gaussiana com pivoteamento parcial é numericamente estável na prática?

Key theories

Fatoração LU com pivoteamento parcial

A eliminação gaussiana com intercâmbio de linhas fatora uma matriz como PA = LU, com L unitária triangular inferior e U triangular superior; o pivoteamento parcial limita os multiplicadores e torna o método confiável para quase todas as matrizes encontradas na prática.

Fator de crescimento e estabilidade numérica

O erro inverso da eliminação gaussiana é governado pelo fator de crescimento das entradas durante a eliminação; embora o crescimento exponencial seja possível em casos artificiais, o pivoteamento parcial mantém o crescimento pequeno o suficiente para que o método seja numericamente estável para praticamente todos os problemas reais.

Mechanisms

A eliminação gaussiana procede coluna por coluna: a cada passo, um pivô é selecionado (o pivoteamento parcial escolhe o candidato de maior magnitude na coluna atual), múltiplos da linha do pivô são subtraídos das linhas abaixo para introduzir zeros, e os multiplicadores são armazenados para formar L. O U triangular superior resultante é resolvido por substituição retroativa e o lado direito é processado por substituição progressiva. Para uma matriz densa n por n, a fatoração custa cerca de dois terços de n ao cubo de operações, enquanto cada resolução triangular custa da ordem de n ao quadrado.

Clinical relevance

Resolvedores diretos são a ferramenta padrão sempre que um sistema denso ou em banda de tamanho moderado deve ser resolvido com precisão total — na montagem de elementos finitos, simulação de circuitos, controle, e como a resolução interna dentro de esquemas numéricos maiores — e uma única fatoração pode ser reutilizada para resolver muitos lados direitos de forma econômica.

History

Os métodos de eliminação remontam a Gauss e a períodos anteriores, mas seu comportamento na aritmética de precisão finita foi esclarecido pela análise de erro inverso de Wilkinson na década de 1960, que mostrou que o pivoteamento parcial controla o crescimento do erro e explicou a confiabilidade empírica do método que há muito era observada em computadores antigos.

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

Quando um método direto deve ser preferido em relação a um iterativo?

Métodos diretos são preferidos quando a matriz é densa ou de tamanho moderado, quando muitos lados direitos compartilham uma matriz (de modo que uma única fatoração é reutilizada), ou quando uma solução garantida de precisão total e finita é necessária. Sistemas esparsos muito grandes geralmente favorecem métodos iterativos.

O pivoteamento sempre garante um erro pequeno?

O pivoteamento parcial garante estabilidade numérica na prática para quase todas as matrizes, mas não supera o mau condicionamento: se a própria matriz é quase singular, mesmo uma resolução numericamente estável pode retornar uma solução com grande erro direto.