Quando é vantajoso iterar integrais numericamente?

Se houver uma integral -dimensional da forma $(n+1)$ normalmente alguém avaliaria isso usando uma biblioteca de integração multidimensional em todo o domínio, .

\int_{[0 0, 1]^{n + 1}} f (x, y) d^{n} x d y,

$\int_{[0,1]^{n+1}} f(x, y)\,\mathrm{d}^n x \,\mathrm{d}y,$

[0, 1]^{n + 1}

$[0,1]^{n+1}$

Mas há algumas condições em que pode fazer sentido executar a integral sobre separadamente, usando uma quadratura unidimensional e, em seguida, usar a biblioteca de integração multidimensional para avaliar o integrando sobre as outras coordenadas? $y$ $n$

\int_{[0 0, 1]^{n}} g (x) d^{n} x, g (x) = \int_{0 0}^{1} f (x, y) d y .

$\int_{[0,1]^n}g(x)\,\mathrm{d}^nx, \qquad g(x) = \int_0^1 f(x,y)\,\mathrm{d}y.$

Isso pode fazer sentido, por exemplo, se é especialmente suave em função de , mas não . Mas quão suave exatamente precisa ser nesse caso? Meu palpite era que quase nunca faz sentido, porque muitos dos pontos de avaliação em quadratura 1-d seriam "desperdiçados", mas não tenho tanta certeza de que isso sempre se aplique. Isso é garantido pelo design dos métodos de integração de alta dimensão? $f$ $y$ $x$

No meu caso, é uma caixa preta, mas suave em , e possui uma quantidade desconhecida de dobras e saltos em em locais desconhecidos, e é bastante alto ( ), portanto a integral sobre tem para ser feito com algo especificamente para muitas dimensões. A integral over pode ser feita com algo como regular . Neste exemplo, a função é suficientemente suave em que quase parece funcionar, mas a integração repetida acaba sendo 30 vezes mais lenta, por isso estou me perguntando se a abordagem está equivocada. $f$ $y$ $x$ $n$ $n\geq 4$ $x$ $y$ quadgk $y$

Se você souber onde isso já é discutido na literatura, isso também seria útil.

Exemplo. (de por que isso não é trivial) Considere um "fácil" integral, o que é muito bom, ao contrário do que eu estou realmente interessado em: Poderíamos fazerMonte Carloingênuo tridimensional no integrando, ou Monte Carlo ingênuo tridimensional no integrando integrado uma vez wrt , que é (onde ).

\int_{[0 0, 1]^{n}} e^{- x_{1} x_{2} \dots x_{n}} d^{n} x = F (\begin{matrix} {1, \dots, 1}_{n} \\ {2, \dots, 2}_{n} \end{matrix} | - 1) .

$\int_{[0,1]^n} e^{-x_1 x_2\cdots x_n}\,\mathrm{d}^n x = \mathrm{F}\left(\begin{array}{}\{1,\ldots,1\}_n\\\{2,\ldots,2\}_n\end{array}\middle| -1\right).$

n

$n$

(n - 1)

$(n-1)$

x_{1}

$x_1$

g (x_{2 : n}) = - (e^{- a} - 1) / a

$g(x_{2:n}) = -(e^{-a}-1)/a$

a = x_{2} \dots x_{n}

$a=x_2\cdots x_n$

Com alguns álgebra, I calcularam que a variância do -dimensional -ponto MC estimativa é , e é para o integrante -dimensional de , para uma redução de variância por um fator de . $(n=5)$ $N$ $0.00244N^{-1}$ $0.00167N^{-1}$ $4$ $g$ $1.5$

Essa é uma redução insignificante na variação: seria negada usando vezes mais pontos de amostra, e isso é compensado pelo fato de o integrando interno poder ser mais de vezes mais lento para avaliar. Se a função acima for mais de vezes mais lenta, isso representa uma perda líquida de precisão, mantendo o tempo de computação fixo. $1.5$ $1.5$ $g = (1-e^{-a})/a$ $1.5$

Presumivelmente, o mesmo tipo de troca se aplica ao considerar uma regra determinística para integrar sobre . O método de Monte Carlo torna essa análise muito mais fácil do que o caso geral, porque a integração sobre atua como uma técnica muito simples de redução de variância. Mas estou realmente muito mais interessado em métodos determinísticos, que não consegui analisar tão facilmente. $x$ $y$

numerical-analysis reference-request quadrature integration Kirill
fonte

Você pode usar apenas regras de quadratura diferentes em cada dimensão? Como

é suave em

, você pode usar a quadratura de ordem baixa lá e a quadratura de ordem superior ao longo das dimensões menos suaves. Os pontos e pesos da quadratura são construídos por produtos tensores das regras 1-D. Isso deve reduzir drasticamente o número total de avaliações de funções.

f

$f$

y

$y$

Tyler Olsen

@TylerOlsen Não, mas essa é a questão ... (Além disso, certamente regras de alta ordem para dimensões suaves, e não o contrário?) Se a função for suficientemente difícil, eu trato de muitas dimensões não suaves com QMC ou grades esparsas ou tensores produtos de regras com refinamento adaptativo, etc., não é a alta precisão de integrar sobre

desperdiçado pelos erros nas outras dimensões? Então, por que não usar apenas uma regra dimensional

sem desperdiçar as avaliações? Mas não tenho certeza de qual é o princípio geral certo, então estou perguntando se alguém sabe alguma coisa.

y

$y$

(n + 1)

$(n+1)$

Kirill

@TylerOlsen Em outras palavras, deve, de alguma forma, depender de quão fácil é integrar a função sobre

(muito fácil - use

d então

-d, mas muito difícil - use

-d). Mas o que é um bom guia ou um limite?

y

$y$

1

$1$

n

$n$

(n + 1)

$(n+1)$

21416 Kirill

Ah, desculpe por isso. Eu virei na minha cabeça. Não posso dizer que conheço uma boa regra de ouro aqui, então alguém terá que seguir essa.

Tyler Olsen

Esclarecimento: Minha resposta foi escrita especificamente para rotinas de integração adaptativa com controle determinístico de erros como este . Torna-se discutível para a grade esparsa e rotinas de integração baseadas em Monte Carlo, cujo controle de erros não é executado da maneira descrita abaixo.

Um custo significativo de rotinas de integração automáticas baseadas em produto de caixa-preta é o controle de erros, sob dois aspectos

Avaliações de função desperdiçada. Toda integração adaptativa funciona estimando o integrando e o erro usando uma regra de baixa ordem ou particionamento mais grosso e repetindo-o com regras de ordem superior progressivamente ou partições mais refinadas até que os requisitos de erro sejam atendidos. As regras de integração aninhada permitem que parte do trabalho realizado nas etapas anteriores seja reciclada, mas geralmente nem todas.
Em um esforço para conservar as avaliações de funções, regras altamente aninhadas, como Gauss-Kronrod ou Newton-Cotes, são frequentemente usadas em códigos de integração adaptativos. Regras de quadratura aninhadas são regras de quadratura abaixo do ideal, pois são consideravelmente menos precisas que as regras ideais (por exemplo, Gauss-Legendre e Clenshaw Curtis) para uma classe específica de funções em uma ordem de quadratura fixa. Em outras palavras, regras aninhadas fazem uso menos eficiente de avaliações de função.

$y$ $y$ $f(x,y)$ $y$ $r$

| \sum_{k = 1}^{r} W_{k} f (x, y_{k}) - \int_{[0 0, 1]} f (x, y) d y | \leq ϵ para todos x \in [0 0, 1]^{n},

$\left|\sum_{k=1}^r w_k f(x,y_k) - \int_{[0,1]}f(x,y)\,\mathrm{d}y\right| \le \epsilon\qquad \text{for all }x\in[0,1]^n,$

f (x, y)

$f(x,y)$

y

$y$

x

$x$

r

$r$

x

$x$

ϵ

$\epsilon$

$g(x)$ $n$ $g(x)$

$f(x,y)$

Para dar um exemplo de aplicação, esse problema exato surgiu para mim na avaliação de integrais singulares volume a volume neste artigo , e meu tratamento é semelhante ao proposto acima. Como regra geral, é sempre aconselhável remover o maior número possível de dimensões usando argumentos analíticos antes de alimentar o problema por meio de uma rotina de integração de caixa preta.

Richard Zhang
fonte

y

$y$

Meu argumento é simplesmente que, se você assumir um método adaptativo com controle determinístico de erros, a avaliação de algumas dimensões de forma fechada (ou semi-fechada) elimina etapas inevitáveis que, de outra forma, seriam realizadas numericamente. Mas seu exemplo (excelente) é aquele em que um método adaptativo determinístico nunca seria usado em primeiro lugar.

Richard Zhang

Suponha que você tenha usado um método adaptativo determinístico padrão, por exemplo, ab-initio.mit.edu/wiki/index.php/Cubature , então eu ficaria muito, muito surpreso se você não obtiver uma velocidade de fator inteira cortando uma das dimensões semi-analiticamente.

Richard Zhang

Usar o Cubature exatamente como você sugere (o que é uma sugestão perfeitamente razoável) é como eu obtive a figura "30 vezes mais lenta" na minha pergunta em primeiro lugar, então fiquei surpreso (daí a pergunta). Eu só quis dizer o exemplo de Monte Carlo como algo fácil de analisar; na verdade, estou mais interessado em métodos determinísticos.

Kirill

n + 1

$n+1$

(n + 1)

$(n+1)$

Quando é vantajoso iterar integrais numericamente?

Respostas: