Quais são algumas aplicações que requerem aritmética de intervalo?

Eu tenho uma noção muito básica sobre aritmética intervalar (IA), mas parece ser um ramo muito interessante da ciência computacional, tanto teórica quanto praticamente. É claro que os aplicativos óbvios são computação verificada e problemas incorretos, mas isso é abstrato demais. Como existem muitas pessoas envolvidas em cálculos aplicados aqui, estou curioso sobre problemas do mundo real que são difíceis ou impossíveis de resolver sem a IA .

Essa resposta responde parcialmente ao comentário de JackPoulson (porque é longo) e responde parcialmente à pergunta.

A aritmética de intervalos é um procedimento computacional para fornecer limites rigorosos em quantidades calculadas, apenas no sentido de que a extensão do intervalo de uma função com valor real em um intervalo encerra a imagem dessa função no mesmo intervalo. Sem calcular nada, a aritmética de intervalo não pode fornecer informações sobre quais fatores influenciam o erro numérico em um cálculo, enquanto os teoremas do livro de Higham e outros fornecem informações sobre os fatores que influenciam o erro numérico, ao custo de limites potencialmente fracos. É verdade que os limites obtidos pela aritmética de intervalo também podem ser fracos, devido ao chamado problema de dependência , mas às vezes são muito mais fortes. Por exemplo, os limites de intervalo obtidos usando o pacote de integração COZY Infinitysão muito mais rigorosos do que os tipos de limites de erro que você obteria na integração numérica a partir dos resultados de Dahlquist (consulte Hairer, Wanner e Nørsett para obter detalhes); Esses resultados (refiro-me particularmente aos Teoremas 10.2 e 10.6 na Parte I) fornecem mais informações sobre as fontes de erro, mas os limites são fracos, enquanto os que usam o COZY podem ser rígidos. (Eles usam vários truques para atenuar os problemas de dependência.)

Hesito em usar a palavra "prova" ao descrever o que a aritmética de intervalo faz. Existem provas envolvendo aritmética de intervalo, mas calcular resultados usando aritmética de intervalo com arredondamento externo é realmente apenas um meio de contabilidade para limitar de forma conservadora o intervalo de uma função. Os cálculos aritméticos de intervalo não são provas; eles são uma maneira de propagar a incerteza.

No que diz respeito às aplicações, além do trabalho da Stadtherr em engenharia química, a aritmética intervalar também foi usada para calcular limites para experimentos com feixes de partículas (veja o trabalho de Makino e Berz, vinculado ao site do COSY Infinity). usado em otimização global e aplicativos de design de engenharia química (entre outros) por Barton (o link é para uma lista de publicações), design de espaçonaves e otimização global (entre outros) de Neumaier (novamente, o link é para uma lista de publicações ), otimização global e solucionadores de equações não lineares de Kearfott (outra lista de publicações) e quantificação de incertezas (várias fontes; Barton é uma delas).

Finalmente, um aviso: Barton é um dos meus conselheiros de tese.

A aritmética de intervalos fornece uma prova com rigor matemático.

Bons exemplos de aplicações reais são o trabalho de Mark Stadtherr e seu grupo de pesquisa. Em particular, os cálculos de equilíbrio e estabilidade de fase são resolvidos com sucesso com métodos de intervalos.

Uma boa coleção de benchmarks, com referência à sua base física, está no site da ALIAS .

Outra característica da aritmética de intervalo e suas generalizações é que ela permite a exploração adaptativa do domínio de uma função. Assim, pode ser usado para modelagem geométrica adaptativa, processamento e renderização, apenas para obter exemplos de gráficos de computador.

Os métodos de intervalo foram apresentados em algumas provas recentes de teoremas matemáticos difíceis, como a existência de caos no atrator de Lorenz e na Conjectura de Kepler. Consulte http://www.cs.utep.edu/interval-comp/kearfottPopular.pdf para essas e outras aplicações.

A aritmética de intervalos é muito útil para algoritmos geométricos. Tais algoritmos geométricos tomam como entrada um conjunto de objetos geométricos (por exemplo, um conjunto de pontos) e constroem uma estrutura combinatória de dados (por exemplo, uma triangulação) com base nas relações espaciais entre os pontos. Esses algoritmos dependem de um pequeno número de funções, chamadas 'predicados', que recebem como entrada um número fixo de objetos geométricos e retornam um valor discreto (geralmente um de 'acima, alinhado, abaixo'). Tais predicados normalmente correspondem ao sinal de um determinante das coordenadas do ponto.

O uso de números de ponto flutuante padrão não é suficiente, pois pode falhar na computação precisa do sinal do determinante e, pior ainda, retornar resultados incoerentes (ou seja, dizer que A está acima de B AND B está acima de A, fazendo com que o algoritmo crie um bagunça em vez de uma malha!). Usar sistematicamente a precisão múltipla (como na biblioteca Gnu Multi-Precision e sua extensão MPFR para números de ponto flutuante de precisão múltipla) funciona, mas causa uma penalidade significativa no desempenho. Quando o predicado geométrico é o sinal de alguma coisa (como na maioria dos casos), o uso da aritmética de intervalos permite fazer uma computação mais rápida e, em seguida, iniciar apenas a computação de multi-precisão mais expansiva se zero estiver no intervalo.

Essa abordagem é usada em vários códigos grandes de geometria computacional (por exemplo, CGAL).