Método de Romberg

Em Análise numérica, o Método de Romberg é usado para estimar a integral definida

${\displaystyle \int _{a}^{b}f(x)\,dx}$

pela aplicação da Extrapolação de Richardson repetidamente sobre a regra do trapézio ou a regra do retângulo (regra do ponto médio). As estimativas geram a ordenação triangular. O Método de Romberg é uma Fórmula de Newton-Cotes, ela avalia o integrante em pontos igualmente espaçados. O integrante deve ter derivadas contínuas apesar de que resultados razoavelmente bons podem ser obtidos se existem apenas algumas derivadas. Se for possível avaliar o integrante em pontos igualmente espaçados, então outros métodos, como Quadratura Gaussiana e Quadratura de Clenshaw-Curtis são, geralmente, mais precisas.

O método foi batizado em homenagem a Werner Romberg (1909-2003), que publicou o método em 1955.

Método

Usando

${\displaystyle h_{n}={\tfrac {1}{2^{n}}}(b-a)}$

O método pode ser definido da seguinte maneira:

${\displaystyle R(0,0)=h_{1}(f(a)+f(b))}$

${\displaystyle R(n,0)={\frac {1}{2}}R(n-1,0)+h_{n}\sum _{k=1}^{2^{n-1}}f(a+(2k-1)h_{n})}$

${\displaystyle R(n,m)=R(n,m-1)+{\frac {1}{4^{m}-1}}(R(n,m-1)-R(n-1,m-1))}$

ou

${\displaystyle R(n,m)={\frac {1}{4^{m}-1}}(4^{m}R(n,m-1)-R(n-1,m-1))}$

onde

${\displaystyle n\geq 1\,}$

${\displaystyle m\geq 1\,}$

${\displaystyle h_{n}={\frac {b-a}{2^{n}}}.}$

Em big o notation, o erro para R(n, m) é (Mysovskikh 2002):

${\displaystyle O\left(h_{n}^{2m+2}\right).\,}$

A extrapolação "zeroeth, R(n, 0), é equivalente a regra do trapézio, com 2ⁿ + 1 pontos; a primeira extrapolação R(n, 1), é equivalente a Regra de Simpson com 2ⁿ + 1 pontos. A segunda extrapolação, R(n, 2), é equivalente a Regra de Boole com 2ⁿ + 1 pontos. Demais extrapolações diferem das Fórmulas de Newton-Cotes. Em particular, demais Extrapolações de Romberg expandem na regra de Boole, de maneira suave, modificando pesos em taxas, de maneira similar à regra de Boole. De maneira oposta, demais métodos de Newton-Cotes produzem crescentes diferenças de pesos, levando, eventualmente, a grandes pesos positivos e negativos.Este é um indicativo de como Métodos de Newton-Cotes, para interpolações polinomiais de grande grau, falham em convergir para muitas integrais, enquanto a Integração de Romberg é mais estável.

Quando as avaliações da função são dispendiosas, pode ser preferível substituir a interpolação polinomial de Richardson pela interpolação racional proposta por Bulirsch & Stoer (1967).

Exemplo geométrico

Para estimar a área sob uma curva, a regra trapezoidal é aplicada em um intervalo, após em dois intervalos, em quatro intervalos e assim consecutivamente.

Um intervalo (Aumentar)

Dois intervalos

Quatro intervalos

Oito intervalos

Após obter as estimativas pela regra dos trapézios, aplica-se a extrapolação de Richardson:

• Para a primeira interação, as estimativas de dois intervalos e de um intervalo são usadas na fórmula (4 X (Mais precisa) - (Menos precisa))/3. A mesma fórmula é então utilizada para comparar as estimativas de quatro e de dois intervalos, e de maneira análoga, para estimativas de maiores intervalos.
• Para a segunda interação, os valores da primeira interação são usados na fórmula (16(Mais precisa)-Menos precisa)/15.
• A terceira interação utiliza a próxima potência de 4:(64 (Mais precisa) - Menos precisa)/63 dos valores derivados da segunda interação.
• Repete-se a operação até que se obtenha uma única estimativa.

Número de Intervalos	Estimativas trapezoidais	Primeira Interação	Segunda Interação	Terceira Interação
		(4MA-ME)/3*	(16MA-ME)/15	(64MA-ME)/63
1	0	(4*480-0)/3 = 640	(16*880-640)/15 =896	(64*1015.11-896)/63 = 1017.002
2	480	(4*780-480)/3 = 880	(16*1006.67-880)/15 = 1015.11..
4	780	(4*950-780)/3 =1006.666..
8	950

• MA: Mais precisa; ME: Menos precisa

Exemplo

Como exemplo, a Função Gaussiana é integrada de 0 a 1, erro da função erf(1) ≈ 0.842700792949715. A distribuição triangular é calculada célula a célula e o processo é terminado quando as duas últimas entradas diferem menos de 10⁻⁸.

 0.77174333
 0.82526296  0.84310283
 0.83836778  0.84273605  0.84271160
 0.84161922  0.84270304  0.84270083  0.84270066
 0.84243051  0.84270093  0.84270079  0.84270079  0.84270079

O resultado no canto inferior direito da distribuição triangular é preciso até os dígitos mostrados. Destaca-se que este resultado deriva de aproximações menos precisas, obtidas pela regra dos trapézios, na primeira coluna da distribuição triangular.

Implementação

Segue um exemplo de uma implementação computacional do Método de Romberg ( em linguagem C). São necessários um vetor e uma variável, bem como uma rotina de trapézios:

 #include <stdio.h>
 #include <stdlib.h>
 #include <math.h>
 #define MAX 6

int main()
{
    double s[MAX];
    int i,k;
    double var ;
    for (i = 1; i< MAX; i++)
        s[i] = 1;
 
    for (k=1; k< MAX; k++)
    {
        for (i=1; i <=k; i++)
        {
            if (i==1)
            {
                var = s[i];
                s[i] = Trap(0, 1, pow(2, k-1));     // Rotina de trapézios
            }                                       // Integração de 0 a 1
                                                    /* pow() é o número de sub-divisões*/
            else
            {
                s[k]= ( pow(4 , i-1)*s[i-1]-var )/(pow(4, i-1) - 1); 
                                                                 
                var = s[i];
                s[i]= s[k];  
            }
         }

        for (i=1; i <=k; i++)
            printf ("  %f  ", s[i]);

        printf ("\n");
    }

    return 0;
}

Referências

• Este artigo foi inicialmente traduzido, total ou parcialmente, do artigo da Wikipédia em inglês cujo título é «Romberg's method».

• Richardson, L. F. (1911), «The Approximate Arithmetical Solution by Finite Differences of Physical Problems Involving Differential Equations, with an Application to the Stresses in a Masonry Dam», Philosophical Transactions of the Royal Society of London. Series A, 210 (459-470): 307–357, JSTOR 90994, doi:10.1098/rsta.1911.0009
• Romberg, W. (1955), «Vereinfachte numerische Integration», Trondheim, Det Kongelige Norske Videnskabers Selskab Forhandlinger, 28 (7): 30–36
• Thacher, Jr., Henry C. (1964), «Remark on Algorithm 60: Romberg integration», Communications of the ACM, 7 (7): 420–421, doi:10.1145/364520.364542
• Bauer, F.L.; Rutishauser, H.; Stiefel, E. (1963), Metropolis, N. C.; et al., eds., «New aspects in numerical quadrature», AMS, Experimental Arithmetic, high-speed computing and mathematics, Proceedings of Symposia in Applied Mathematics (15): 199–218 !CS1 manut: Uso explícito de et al. (link)
• Bulirsch, Roland; Stoer, Josef (1967), «Handbook Series Numerical Integration. Numerical quadrature by extrapolation», Numerische Mathematik, 9: 271–278
• Mysovskikh, I.P. (2002), «Romberg method», in: Hazewinkel, Michiel, Encyclopaedia of Mathematics, ISBN 1-4020-0609-8, Springer-Verlag
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 4.3. Romberg Integration», Numerical Recipes: The Art of Scientific Computing, ISBN 978-0-521-88068-8 3rd ed. , New York: Cambridge University Press

Ligações externas

• ROMBINT – code for MATLAB (author: Martin Kacenak)
• Module for Romberg integration
• Free online integration tool using Romberg, Fox–Romberg, Gauss–Legendre and other numerical methods