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

15

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 .

faleichik
fonte

Respostas:

11

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.

Geoff Oxberry
fonte
Obrigado! Alguma idéia de quão bem as feiras aritméticas de intervalo para computação EVD e / ou SVD? Ou algoritmos de Krylov?
Jack Poulson
11
Tanto quanto eu sei, você pode obter limites em autovalores ou valores singulares. Não tenho certeza do que autovetores de intervalo ou vetores singulares significariam. O artigo mais recente que conheço em uma revista respeitável é "Limites de autovalores reais e valores singulares de matrizes de intervalo", de Hladík, Daney e Tsigaridas em SIAM J. Matrix. Anal. Appl. (2010). Para resolver sistemas lineares, este livro é a melhor referência.
Geoff Oxberry
7

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 .

Todos
fonte
3
Pergunta honesta: em que sentido é mais rigoroso do que o tipo de limites decorrentes da análise clássica de erros, por exemplo, na precisão e na estabilidade de algoritmos numéricos de Higham ?
precisa saber é o seguinte
11
@ JackPoulson: Eu tentei responder seu comentário na minha resposta, além de fornecer algumas referências.
Geoff Oxberry
11
Veja também Provando conjecturas usando aritmética de intervalo por Andreas Frommer.
lhf 21/05
5

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.

lhf
fonte
11
Isso é verdade; a subdivisão de intervalos produz resultados mais precisos e essa propriedade ajuda a explorar adaptativamente o domínio de uma função.
Geoff Oxberry
@lhf Voto a favor! É uma pena que eu tenha esquecido as provas do teorema e o site do Prof. Kearfott. Obrigado pela referência!
Ali
2

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).

BrunoLevy
fonte