Método ODE ideal para número fixo de avaliações de RHS

Na prática, o tempo de execução de resolver numericamente um IVP é frequentemente dominada pela duração da avaliação do lado direito (RHS) . Vamos, portanto, assumir que todas as outras operações são instantâneas (ou seja, sem custo computacional). Se o tempo de execução geral para resolver o IVP for limitado, isso equivale a limitar o número de avaliações de para alguns .x ( t 0 ) = x 0 f f N ∈

Estamos interessados ​​apenas no valor final .$x(t_1)$

Estou procurando resultados teóricos e práticos que me ajudem a escolher o melhor método de EDO nesse cenário.

Se, por exemplo, , poderíamos resolver o IVP usando duas etapas explícitas de largura de Euler ou uma etapa de largura usando o método do ponto médio. Não está imediatamente claro para mim qual é o preferido. Para maior , é claro que também é possível pensar em métodos de várias etapas, esquemas de Runge-Kutta iterados, etc.( t 1 - t 0 ) / 2 t 1 - t 0$N = 2$$(t_1 - t_0)/2$$t_1 - t_0$$N$

O que estou procurando são resultados semelhantes aos que existem, por exemplo, para regras de quadratura: Podemos escolher pesos e pontos associados modo que a regra de quadratura é exato para todos os polinômios tais que .$n$$\{w_i\}$$\{x_i\}$$\sum_{i = 1}^n w_i g(x_i)$$g$$deg(g) \le 2n - 1$

Por isso, estou procurando limites superiores ou inferiores na precisão global dos métodos ODE, dado um número limitado de avaliações permitidas do RHS . Tudo bem se os limites se mantiverem apenas para algumas classes de RHS ou apresentarem restrições adicionais na solução (assim como o resultado da regra de quadratura que se aplica apenas a polinômios até um certo grau).$f$$x$

EDIT: Algumas informações básicas: são para aplicativos difíceis em tempo real, ou seja, o resultado deve estar disponível antes de um prazo conhecido. Daí o limite do número de avaliações de RHS como o fator de custo dominante. Normalmente, nossos problemas são rígidos e comparativamente pequenos.$x(t_1)$$N$

EDIT2: Infelizmente não tenho os requisitos de tempo precisos, mas é seguro supor que será um pouco pequeno (definitivamente <100, provavelmente mais próximo de 10). Dado o requisito em tempo real, precisamos encontrar uma compensação entre a precisão dos modelos (com melhores modelos levando a tempos de execução mais longos do RHS e, portanto, com um menor ) e a precisão do método ODE (com melhores métodos que exigem maior valores de ).$N$$N$$N$

Penso que uma referência fundamental para responder à sua pergunta é este artigo de Oséias e Shampine . Agora vou dar uma base.

Em geral, o tamanho da etapa que você pode usar ao integrar numericamente um IVP pode ser restringido pela estabilidade ou precisão. Se você quiser escolher o melhor solucionador em termos de estabilidade, precisará considerar a região de estabilidade absoluta . Para um método de uma etapa, é

Aqui é a função de estabilidade do método; veja, por exemplo, o texto de Hairer et. al. Uma condição necessária para a estabilidade é que λ h ∈ S onde λ varia sobre os valores próprios do jacobiano de f e h seja o tamanho do passo. Isso nem sempre é uma condição suficiente para problemas não lineares, mas geralmente é uma boa regra geral e é usado na prática.$P(z)$$\lambda h \in S$$\lambda$$f$$h$

Para um tratamento extensivo do problema de encontrar métodos (explícitos) que permitam grandes tamanhos de etapas estáveis, consulte este artigo sobre polinômios de estabilidade e este sobre otimização dos métodos de Runge-Kutta para simulações de fluidos compressíveis .

A estabilidade é a preocupação relevante se você achar que o maior tamanho estável da etapa já oferece precisão suficiente. Por outro lado, o tamanho da etapa pode ser restringido por seus requisitos de precisão. O que normalmente é feito é o controle de erros local. A solução é calculada usando dois métodos, e sua diferença é usada como estimativa do erro no menos preciso. O tamanho da etapa é escolhido de forma adaptativa para atingir o mais próximo possível a tolerância prescrita.

Duas medidas teóricas são fundamentais para prever a eficiência da precisão. A primeira é a ordem de precisão do método, que descreve a taxa na qual o erro se aproxima de zero quando o tamanho da etapa é diminuído. O segundo é o índice de eficiência de precisão (veja o artigo de Oséias e Shampine, vinculado na primeira frase acima), que leva em consideração as constantes que aparecem nos termos do erro e permite comparações entre métodos da mesma ordem.

A precisão e a eficiência da estabilidade de uma ampla gama de métodos podem ser calculadas de maneira simples e automatizada usando o NodePy (aviso: o NodePy é desenvolvido por mim).

Não há muitos resultados nessa direção porque é mais difícil do que apenas corrigir a precisão, pois as considerações de estabilidade geralmente exigem que você escolha etapas de tempo menores do que o necessário para a precisão desejada. Portanto, os resultados são divididos entre os casos rígido e não rígido. No primeiro caso, os prazos e os requisitos das avaliações de RHS geralmente não são regidos pela precisão, e no último caso são.

Vou me concentrar em métodos explícitos, já que o caso implícito é muito menos óbvio quantas avaliações de RHS você precisará usar ... isso depende inteiramente de como você decide resolver o sistema resultante.

Para sistemas não rígidos:

Existem limitações de estágio para métodos explícitos de Runge-Kutta, para os quais digamos quantos estágios (avaliações RHS) são necessários para atingir uma certa ordem de precisão. Após a quarta ordem, o número de estágios excede a ordem da precisão e a disparidade continua a aumentar. Grande livro ODE de açougueiro: http://books.google.com/books/about/Numerical_Methods_for_Ordinary_Different.html?id=opd2NkBmMxsC

faz um bom trabalho explicando algumas dessas provas de 'inexistência'.

Seu exemplo de regra de quadratura leva a um método do tipo de várias etapas, como Adams-bashforth, ou ao que agora são chamados métodos de correção espectral adiada. Para adams-bashforth, você precisa apenas de uma avaliação RHS por etapa, mas como as regiões de estabilidade são tão pequenas em geral para esses métodos, você geralmente acaba fazendo a mesma quantidade de trabalho em termos de avaliações RHS que um método Runge-Kutta com o mesmo método. ordem.

Aqui está um artigo sobre correção adiada espectral:

https://www.google.com/search?q=spectral+deferred+correction&aq=f&oq=spectral+deferred+correction&aqs=chrome.0.57j0l2j62.3336j0&sourceid=chrome&ie=UTF-8

Não tenho certeza de como esses métodos de integração se comportam contra métodos explícitos padrão, geralmente exigem muito mais memória para salvar estados de solução em nós de quadratura e, portanto, nunca os usei eu mesmo.

Para sistemas rígidos:

infelizmente existem indicadores de tempo "otimizados", mas resultados teóricos precisos sobre o quão bom eles podem obter estão infelizmente limitados a alguns casos simples (e mesmo aqueles que acabaram não sendo um trabalho trivial). Os três resultados padrão dizem que, para os métodos Runge-Kutta com estágios : O eixo real mais negativo que pode incluir em sua região de estabilidade é um intervalo de comprimento 2 S 2 , o eixo mais imaginário que ele pode conter é um intervalo de comprimento S - 1 , e o maior círculo tangente ao eixo imaginário que ele pode conter possui raio S (todos eles são mutuamente exclusivos).$S$$2S^2$$S-1$$S$

$10^{-14}$$f(x)$

É claro que há exceções (sistemas muito grandes, sistemas muito rígidos), mas um sentimento comum na comunidade é que a questão de projetar solucionadores de EDO para sistemas "padrão" é resolvida. Consequentemente, acho que a pergunta que você faz não é muito interessante - trata de um componente do design do solucionador de ODE que não é mais importante. Isso também pode explicar a falta de literatura sobre o assunto.

$O(\mathit{dim}^3)$$O(\mathit{dim}^2)$

Portanto, o primeiro ponto é garantir que o seu RHS seja realmente mais caro que a álgebra linear subjacente.

O segundo ponto: é sabido na literatura que os solucionadores baseados em métodos "caros" (ou seja, métodos RK explícitos) às vezes são mais rápidos que os "mais baratos" (métodos explícitos em várias etapas).

Resumindo, acho que você não deve considerar apenas a contagem de avaliações do RHS.