Como identificar cálculos de ponto flutuante instável?

15

Em numerics, é muito importante ser capaz de identificar instável regimes e melhorar a sua estabilidade. Como identificar instável cálculos de ponto flutuante?

Eu estou trabalhando em uma simulação muito complexa, onde muitos esquemas numéricos trabalham juntos e eu estou procurando um método para identificar suas partes fracas. Eu estou trabalhando em um modelo físico envolvendo equações diferenciais. Uma visão geral do processo geral é:

  1. (Etapa preliminar) Reúna observações físicas P .

  2. Determine os parâmetros iniciais da simulação. Isso usa um algoritmo de otimização, onde andamos em um espaço de parâmetros e procuramos parâmetros C de forma que alguma função de erro E (F (C), P) seja minimizada, onde F é alguma quantidade derivada dos parâmetros.

  3. Conecte C no mecanismo de simulação. Este é um esquema de Euler do EDP, de modo que a cada passo de tempo, calculamos os termos que impulsionam a dinâmica (cada um deles é uma função complexa, potencialmente sujeita a instabilidade) e alimentamos o esquema de Euler com esses termos dinâmicos para computar o próximo Estado. Isso continua por milhares de pontos no tempo.

  4. No final da simulação, calculamos alguma função Prova (S) do estado final S e comparamos com algumas quantidades Exigir ( P) deduzido das quantidades observadas. Esta não é uma prova formal do resultado, mais uma verificação de plausibilidade.

Além disso, vejo uma torre de operações complexas (computação de termos dinâmicos, dentro do esquema de Euler, dentro da Prova ). E gostaria de reconhecer "partes ruins" e consertá-las.

Eu especulo que usando uma implementação de software de ponto flutuante números com precisão reduzida aumentariam a instabilidade do esquemas numéricos, facilitando assim a comparação entre diferentes implementações. Esta é uma técnica comum para investigar isso questão? É possível usar uma máquina virtual, como Bochs, para conseguir isso sem alterar o programa?

Para lidar adequadamente com a questão da estabilidade, às vezes é aceitável para direcionar a entrada típica do procedimento numérico, que pode ser ajustado para fazer bem nessa entrada e talvez menos bem outra entrada válida, ainda que improvável. Dada uma amostra de entradas típicas, é possível bisbilhotar alguns resultados intermediários e preparar um perfil estatístico para eles. Mais uma vez, isso é uma técnica comum para estudar questões de estabilidade? Uma máquina virtual é útil para isso?

    
por user40989 11.12.2013 / 10:50
fonte

4 respostas

6

O estudo da estabilidade da computação de ponto flutuante faz parte da análise numérica e, se você realmente quer um resultado sonoro, você realmente quer que alguém com conhecimento nesse domínio faça a análise dos algoritmos usados.

Existem algumas coisas que podem ajudar a identificar experimentalmente algoritmos instáveis. Correndo com o conjunto de arredondamentos para diferentes modos (up / down / random) ou com precisão diferente e verificando se o resultado não varia muito. Responder é demais? não é nada simples e mesmo quando a resposta é não isso não significa que o algoritmo é estável, só que não foi detectado instável no conjunto de dados que você usou.

A aritmética do intervalo foi proposta nos comentários. Quando eu olhei para ele, até mesmo o defensor mais raivoso da aritmética de intervalos admitiu que funcionava bem com algoritmos projetados para a aritmética de intervalo, mas que mudar para ele sem analisar o algoritmo e garantir que não tivesse padrões conhecidos de não funcionar bem não ser útil (os oponentes pareciam ser da opinião de que as condições prévias para a aritmética intervalar seriam úteis quando demasiado restritivas para serem de interesse prático)

    
por 13.12.2013 / 15:41
fonte
3

Projetar algoritmos estáveis de ponto flutuante é altamente não trivial. Aqueles que são mais matematicamente qualificados do que eu, sugerem usar bibliotecas bem conceituadas sempre que possível, em vez de tentar criar as suas próprias. A referência padrão na área parece ser:

N. J. Higham Precisão e Estabilidade de Algoritmos Numéricos. Society for Industrial and Applied Mathematics, Filadélfia, PA, EUA, segunda edição, 2002. ISBN 0-89871-521-0

Não saber mais sobre os tipos de cálculos, idiomas, etc. torna difícil dar uma resposta muito concreta. Há uma boa palestra aqui: link isso pode ser um pouco básico, mas é uma boa introdução se você for usando java.

    
por 17.12.2013 / 19:25
fonte
1

How to identify unstable floating point computations? Is this a common technique to investigate this question?

Acho que, a menos que você precise mostrar algumas estatísticas sobre erro, não é necessário coletar amostras. O que você precisa é Análise Numérica , que também se enquadra nas disciplinas de Métodos Numéricos, Álgebra Linear Numérica, etc. re parte da ciência da computação, então você pode obter algumas respostas também em cs.stackexchange.

De qualquer forma, na programação geral, a maioria dos problemas é fácil de detectar, dado algum entendimento básico sobre como o ponto flutuante funciona e métodos numéricos básicos. Mas problemas ainda mais complexos são "mais fáceis" de resolver hoje com a disponibilidade de flutuadores de 128 bits, menos ainda para produzir amostras de erro. Aqui estão alguns exemplos de problemas para mostrar o meu ponto:

  1. usando ponto flutuante para calcular valores monetários.
  2. usando ponto flutuante para grandes números.
  3. não faz divisões antes de outras operações quando é possível fazer isso. (para tornar o valor mais próximo de 0).
  4. cálculo longo sem tratamento especial para propagação de erros.

Há também um exemplo de algoritmo ingênuo e algoritmo de erro compensado aqui algoritmo para calcular a variância . No exemplo, olhando para a versão ingênua, você meio que pode cheirar que fazer cálculos em loops carregará alguns erros e não está sendo compensado.

    
por 11.12.2013 / 22:08
fonte
0

Você pode evitar erros numéricos usando tipos de dados apropriados (como, por exemplo, frações contínuas). Se você precisar ou quiser usar a aritmética de ponto flutuante, precisará aplicar o conhecimento numérico para saber os erros.

    
por 12.12.2013 / 12:17
fonte