Condicionamento e Estabilidade Numérica

O condicionamento mede a sensibilidade da solução de um problema a perturbações nos seus dados, enquanto a estabilidade mede o erro que um algoritmo particular adiciona na aritmética de precisão finita; juntos, eles determinam a precisão de um resultado computado.

Definition

Condicionamento é uma propriedade intrínseca de um problema que descreve como sua solução exata responde a perturbações da entrada, enquanto a estabilidade numérica é uma propriedade de um algoritmo que descreve quão fielmente ele resolve o problema apesar dos erros de arredondamento.

Scope

Este tópico abrange a aritmética de ponto flutuante e o arredondamento unitário, o número de condição de problemas como a resolução de sistemas lineares e a avaliação de funções, o erro direto e o erro inverso, a regra prática de que o erro direto é limitado pelo número de condição vezes o erro inverso, e as definições de estabilidade inversa e direta.

Core questions

• Como a aritmética de ponto flutuante é modelada e qual é o papel do arredondamento unitário?
• O que o número de condição de um problema quantifica e como ele é definido para sistemas lineares e para avaliação de funções?
• Como o erro direto, o erro inverso e o condicionamento estão relacionados?
• O que distingue um algoritmo estável inversamente de um estável diretamente, e por que a estabilidade inversa é o objetivo usual?

Key theories

Número de condição

O número de condição é o fator pelo qual as perturbações relativas nos dados podem ser amplificadas na solução; para um sistema linear, ele é igual à norma da matriz vezes a norma da inversa, e estabelece um limite para a precisão alcançável, independente do algoritmo.

Análise de erro inverso

Em vez de limitar o erro na resposta diretamente, mostra-se que o resultado computado é a resposta exata para um problema próximo; um algoritmo é estável inversamente quando este problema próximo difere do original por uma quantidade da ordem do arredondamento unitário.

Erro direto é igual ao número de condição vezes o erro inverso

A regra prática central da análise numérica afirma que o erro direto (da solução) é limitado aproximadamente pelo número de condição do problema multiplicado pelo erro inverso, separando claramente as contribuições do problema e do algoritmo.

Mechanisms

Números de ponto flutuante representam números reais com precisão finita, então cada operação elementar incorre em um erro relativo limitado pelo arredondamento unitário. A análise de erro inverso rastreia esses erros atribuindo-os a perturbações dos dados em vez do resultado, produzindo limites da forma: a resposta computada é igual à resposta exata de uma entrada perturbada. A combinação de um limite de erro inverso com o número de condição do problema produz uma estimativa de erro direto, o que explica por que um algoritmo estável ainda pode perder precisão em um problema mal-condicionado.

Clinical relevance

Compreender o condicionamento e a estabilidade é essencial sempre que os resultados computados devem ser confiáveis: explica por que algumas formulações de mínimos quadrados perdem precisão, orienta a escolha de algoritmos estáveis e formulações bem-postas em simulações e análises de dados, e alerta quando um modelo mal-condicionado não pode fornecer uma resposta confiável, independentemente do método utilizado.

History

A estrutura conceitual foi estabelecida por Wilkinson, cuja análise de erro inverso na década de 1960 explicou a confiabilidade prática da eliminação gaussiana, e foi posteriormente sistematizada e estendida por Higham em todo o campo; o padrão IEEE 754 de ponto flutuante subsequentemente estabeleceu o comportamento de arredondamento em uma base sólida e portátil.

Key figures

• James H. Wilkinson
• Nicholas J. Higham
• Lloyd N. Trefethen
• William Kahan

Seminal works

• trefethen1997
• higham2002

Frequently asked questions

Se um algoritmo é estável, ele sempre dará uma resposta precisa?

Não. Um algoritmo estável inversamente garante apenas que sua resposta é exata para um problema próximo; se o problema em si é mal-condicionado, esse problema próximo pode ter uma solução muito diferente, então o erro direto ainda pode ser grande.

O que é arredondamento unitário?

Arredondamento unitário é o erro relativo máximo incorrido quando um número real é arredondado para o número de ponto flutuante mais próximo; ele define a granularidade da aritmética de ponto flutuante e aparece em essencialmente todos os limites de estabilidade.