Rombergsova metoda - Rombergs method - Wikipedia

v numerická analýza, Rombergova metoda (Romberg 1955 ) se používá k odhadu určitý integrál

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

aplikováním Richardsonova extrapolace (Richardson 1911 ) opakovaně na lichoběžníkové pravidlo nebo pravidlo obdélníku (pravidlo středu). Odhady generují a trojúhelníkové pole. Rombergova metoda je a Newton – Cotesův vzorec - vyhodnocuje integrand v rovnoměrně rozmístěných bodech. Integrand musí mít spojité derivace, i když celkem dobrých výsledků lze dosáhnout, pokud existuje jen několik derivací. Pokud je možné hodnotit integrand v nerovnoměrně rozmístěných bodech, pak lze použít i jiné metody Gaussova kvadratura a Clenshaw – Curtisova kvadratura jsou obecně přesnější.

Metoda je pojmenována po Werner Romberg (1909–2003), který metodu publikoval v roce 1955.

Metoda

Použitím

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

způsob lze induktivně definovat pomocí

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

${ displaystyle R (n, 0) = { tfrac {1} {2}} R (n-1,0) + h_ {n} součet _ {k = 1} ^ {2 ^ {n-1} } f (a + (2k-1) h_ {n})}$

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

nebo

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

kde ${ displaystyle n geq m ,}$ a ${ displaystyle m geq 1 ,}$. v velká O notace, chyba pro R(n, m) je (Mysovskikh 2002 ):

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

Nulová extrapolace, R(n, 0), je ekvivalentní s lichoběžníkové pravidlo s 2ⁿ + 1 bod; první extrapolace, R(n, 1), je ekvivalentní s Simpsonovo pravidlo s 2ⁿ + 1 bod. Druhá extrapolace, R(n, 2), je ekvivalentní s Booleovo pravidlo s 2ⁿ + 1 bod. Další extrapolace se liší od vzorců Newton Cotes. Zejména další Rombergovy extrapolace velmi mírným způsobem expandují na Booleovu vládu a upravují váhy na poměry podobné jako v Booleově pravidle. Naproti tomu další metody Newton Cotes produkují stále se lišící váhy, což nakonec vede k velkým kladným a záporným váhám. To svědčí o tom, jak velké míry interpolační polynomické metody Newton Cotes nedokážou konvergovat pro mnoho integrálů, zatímco Rombergova integrace je stabilnější.

Když jsou vyhodnocení funkcí nákladná, může být výhodné nahradit polynomiální interpolaci Richardsona racionální interpolací navrženou Bulirsch & Stoer (1967).

Geometrický příklad

Pro odhad plochy pod křivkou se lichoběžníkové pravidlo použije nejprve na jeden kus, poté na dva, potom na čtyři atd.

Jeden kus. Protože tato aproximace začíná a končí na nule, poskytuje nulovou plochu.

Dva kusy

Čtyřdílný

Osm kusů

Po získání odhadů lichoběžníkového pravidla Richardsonova extrapolace je použito.

• Pro první iteraci se ve vzorci použijí odhady dvou a jednoho kusu (4 × (přesnější) - (méně přesné)) / 3 Stejný vzorec se poté použije k porovnání čtyřdílného a dvoudílného odhadu a podobně pro vyšší odhady
• Pro druhou iteraci se ve vzorci použijí hodnoty první iterace (16 (přesnější) - méně přesné)) / 15
• Třetí iterace využívá další sílu 4: (64 (přesnější) - méně přesné)) / 63 na hodnotách odvozených druhou iterací.
• Vzor pokračuje, dokud neexistuje jeden odhad.

• MA znamená přesnější, LA znamená méně přesný

Příklad

Jako příklad lze uvést Gaussova funkce je integrován od 0 do 1, tj chybová funkce erf (1) ≈ 0,842700792949715. Trojúhelníkové pole se počítá řádek po řádku a výpočet je ukončen, pokud se dvě poslední položky v posledním řádku liší méně než 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

Výsledek v pravém dolním rohu trojúhelníkového pole je přesný k uvedeným číslicím. Je pozoruhodné, že tento výsledek je odvozen od méně přesné aproximace získané pravidlem lichoběžníku v prvním sloupci trojúhelníkového pole.

Implementace

Zde je příklad počítačové implementace Rombergovy metody (v Programovací jazyk C. ).

#zahrnout <stdio.h>#zahrnout <math.h>prázdnotadump_row(size_t i, dvojnásobek *R) {   printf("R [% 2zu] =", i);   pro (size_t j = 0; j <= i; ++j){      printf("% f", R[j]);   }   printf(" n");}dvojnásobekRomberg(dvojnásobek (*F/ * funkce pro integraci * /)(dvojnásobek), dvojnásobek /*spodní limit*/ A, dvojnásobek /*horní limit*/ b, size_t max_steps, dvojnásobek / * požadovaná přesnost * / dle) {   dvojnásobek R1[max_steps], R2[max_steps]; // Nárazníky   dvojnásobek *Rp = &R1[0], *Rc = &R2[0]; // Rp je předchozí řádek, Rc je aktuální řádek   dvojnásobek h = (b-A); // velikost kroku   Rp[0] = (F(A) + F(b))*h*.5; // první lichoběžníkový krok   dump_row(0, Rp);   pro (size_t i = 1; i < max_steps; ++i) {      h /= 2.;      dvojnásobek C = 0;      size_t ep = 1 << (i-1); // 2 ^ (n-1)      pro (size_t j = 1; j <= ep; ++j) {         C += F(A+(2*j-1)*h);      }      Rc[0] = h*C + .5*Rp[0]; // R (i, 0)      pro (size_t j = 1; j <= i; ++j) {         dvojnásobek n_k = prášek(4, j);         Rc[j] = (n_k*Rc[j-1] - Rp[j-1])/(n_k-1); // výpočet R (i, j)      }      // Dump i-tý sloupec R, R [i, i] je zatím nejlepší odhad      dump_row(i, Rc);      -li (i > 1 && báječné(Rp[i-1]-Rc[i]) < dle) {         vrátit se Rc[i-1];      }      // vyměníme Rn a Rc, protože potřebujeme pouze poslední řádek      dvojnásobek *rt = Rp;      Rp = Rc;      Rc = rt;   }   vrátit se Rp[max_steps-1]; // vrátit náš nejlepší odhad}

Reference

• Richardson, L. F. (1911), „Přibližné aritmetické řešení konečných rozdílů fyzikálních problémů zahrnujících diferenciální rovnice s aplikací na namáhání ve zdivu“, Filozofické transakce královské společnosti A, 210 (459–470): 307–357, doi:10.1098 / rsta.1911.0009, JSTOR  90994
• Romberg, W. (1955), „Vereinfachte numerische Integration“, Det Kongelige Norske Videnskabers Selskab Forhandlinger, Trondheim, 28 (7): 30–36
• Thacher Jr., Henry C. (červenec 1964), „Poznámka k algoritmu 60: Rombergova integrace“, Komunikace ACM, 7 (7): 420–421, doi:10.1145/364520.364542
• Bauer, F.L .; Rutishauser, H .; Stiefel, E. (1963), Metropolis, N. C .; et al. (eds.), "Nové aspekty v numerické kvadratuře", Experimentální aritmetika, vysokorychlostní výpočty a matematika, Sborník sympozií z aplikované matematiky, AMS (15): 199–218
• Bulirsch, Roland; Stoer, Josef (1967), „Příručka Numerická integrace. Numerická kvadratura extrapolací“, Numerische Mathematik, 9: 271–278, doi:10.1007 / bf02162420
• Mysovskikh, I.P. (2002), „Rombergova metoda“, Hazewinkel, Michiel (ed.), Encyklopedie matematiky, Springer-Verlag, ISBN  1-4020-0609-8
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 4.3. Rombergova integrace“, Numerické recepty: Umění vědecké práce na počítači (3. vyd.), New York: Cambridge University Press, ISBN  978-0-521-88068-8

externí odkazy

• ROMBINT - kód pro MATLAB (autor: Martin Kacenak)
• Bezplatný online integrační nástroj využívající Romberg, Fox – Romberg, Gauss – Legendre a další numerické metody
• SciPy implementace Rombergovy metody