Metody Newtona-Cotesa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

W analizie numerycznej wzory Newtona-Cotesa są zbiorem metod numerycznych całkowania, zwanego również kwadraturą. Nazwa pochodzi od Isaaca Newtona i Rogera Cotesa.

Przyjmujemy, że wartość funkcji f jest znana w równo oddalonych punktach xi, dla i = 0, ..., n. Dla punktów oddalonych od siebie o inne odległości ma zastosowanie inna klasa wzorów, kwadratura gaussowska.

Jeżeli a=x_0<x_1<x_2,\cdots <x_{n-1}<x_n=brówno odległymi węzłami interpolacji funkcji f(x) (tj. x_i są elementami dziedziny f, dla których znana jest wartość f(x_{i })=y_i), to całkę:

\int\limits_a^b f(x) dx

można aproksymować całką:

\int\limits_a^b L_{n }(x) dx

gdzie L_{n }(x) dx jest wielomianem interpolacyjnym Lagrange'a stopnia co najwyżej n, przybliżającym funkcję f(x) w węzłach interpolacji, tj.:

L_{n }(x_{0 })=y(x_{0 }),L_{n }(x_{1 })=y(x_{1 }),\cdots ,L_{n }(x_{n })=y(x_{n })

Niech h_n = \frac {b-a}{n} oznacza długość kroku dzielącą dwa węzły interpolacji.

Wprowadzając zmienną t taką, że x=a+th można zapisać:

L_{i }(x)=L_{n }(a+th)=\prod_{j = 0 \and j\ne i}^n \frac {t-j}{i-j}=g(t)

Wtedy:

\int\limits_a^b L_{n }(x) dx=\int\limits_a^b \sum_{i = 0}^n f(x_i)\cdot L_{i }(x) dx=
\sum_{i = 0}^n f(x_i)\cdot \int\limits_a^b L_{i }(x) dx


x=a+t\cdot h,
f(x_i)=f(a+i\cdot h)


x_i=a+i\cdot h
dla a=x_0 t=0
dla x_1 t=1
\cdots
dla b=x_n t=n
dx=(x)'=1
dt=(a+t\cdot h)dt=(a+t\cdot h)'=h=dt

Zmieniając zmienną, oraz granice całkowania otrzymuje się:

\int\limits_a^b L_{i }(x)dx = h\cdot \int\limits_0^n g(t) dt

Ostatecznie, wzór Newtona-Cotesa dla n+1 równo odległych węzłów przyjmuje postać:

\int\limits_a^b f(x) dx = \int\limits_a^b L_{n }(x) dx = \sum_{i=0}^n f(x_{i }) \cdot \int\limits_a^b L_{i }(x=a+t\cdot h) dx = \sum_{i=0}^n f(x_{i }) \cdot h\cdot \int\limits_0^n \prod_{j=0 \and j\ne i}^n \frac {t-j}{i-j} dt

Przyjmując za A_i = h\cdot \int\limits_0^n \prod_{j=0 \and j\ne i}^n \frac {t-j}{i-j} dt (nazywane współczynnikami kwadratury Newtona-Cotesa), otrzymuje się:

\int\limits_a^b f(x) \approx \sum_{i=0}^n f(x_i)\cdot A_i
  • A_i = A_{n-i}
Dowód:
A_i = h\cdot \int\limits_0^n \prod_{j=0 \and j\ne i}^n \frac {t-j}{i-j} dt
Niech v=n-t.
Wtedy:
dt=-dv
A_i= - h\cdot \int\limits_n^0 \prod_{j=0 \and j\ne i}^n \frac {n-v-j}{i-j} dv =
Odwrócenie granic całkowania:
 = h\cdot \int\limits_0^n \prod_{j=0 \and j\ne i}^n \frac {n-j-v}{(n-j)-(n-i)} dv =
Niech (n-j)=v'.
 = h\cdot \int\limits_0^n \prod_{v'=0 \and v'\ne (n-i)}^n \frac {v'-v}{v'-(n-i)} dv =
Po wyciągnięciu (-1) przed iloczyn i mianownik:
 = h\cdot \int\limits_0^n \prod_{v'=0 \and v'\ne (n-i)}^n \frac {v-v'}{(n-i)-v'} dv = A_{n-i}

Definiuje się dwa typy wzorów Newtona-Cotesa:

  • otwarte, które nie wykorzystują wartości funkcji w skrajnych punktach, oraz
  • zamknięte, wykorzystujące wszystkie wartości funkcji.

Zamknięty wzór Newtona-Cotesa rzędu n:

\int\limits_a^b f(x) \,dx \approx \sum_{i=0}^n w_i\, f(x_i)

gdzie xi = h i + x0, z h (nazywanym rozmiarem kroku) równym (xn - x0)/n oraz w_iwagami. Wagi można wyprowadzić z wielomianów bazowych Lagrange'a. To oznacza, że zależą tylko od xi a nie od funkcji f. L(x) wielomianem interpolacji w postaci Lagrange'a dla punktów (x0, f(x0) ),..,(xn, f(xn) )

\int\limits_a^b f(x) \,dx \approx \int\limits_a^b L(x)\,dx = \int\limits_a^b \sum_{i=0}^n f(x_i)\, 

l_i(x)\, dx
=\sum_{i=0}^n \int\limits_{x_{i-1}}^{x_i} f(x_i)\, l_i(x)\, dx = 
\sum_{i=0}^n f(x_i) \underbrace{\int\limits_{x_{i-1}}^{x_i} l_i(x)\, dx}_{w_i}

Otwarty wzór Newtona-Cotesa rzędu n:

\int\limits_a^b f(x)\, dx \approx \sum_{i=1}^{n-1} w_i\, f(x_i)

wagi znajdujemy w sposób analogiczny do powyższego.

  • Możemy skonstruować wzór Newtona-Cotesa dowolnego rzędu.
  • Niektóre wzory niskich rzędów mają swoje tradycyjne nazwy.
  • W poniższej tabeli znajdują się wzory Newtona-Cotesa typu zamkniętego.
  • Notacja f_i oznacza f(x_i).
Rząd Tradycyjna nazwa Wzór Błąd
1 wzór trapezów  \frac{h}{2} (f_0 + f_1) -\frac{h^3}{12}\,f^{(2)}(\xi)
2 wzór Simpsona  \frac{h}{3} (f_0 + 4 f_1 + f_2) -\frac{h^5}{90}\,f^{(4)}(\xi)
3 reguła 3/8  \frac{3\, h}{8} (f_0 + 3 f_1 + 3 f_2 + f_3) -\frac{3\, h^5}{80}\,f^{(4)}(\xi)
4 wzór Boole'a czasem błędnie[1] nazywany wzorem Bode'a  \frac{2\, h}{45} (7 f_0 + 32 f_1 + 12 f_2 + 32 f_3 + 7 f_4) -\frac{8\, h^7}{945}\,f^{(6)}(\xi)

Wykładnik o kroku h w wyrazie błędu pokazuje szybkość zmniejszania się błędu przybliżenia. Pochodna f w wyrazie błędu pokazuje który wielomian może być scałkowany dokładnie (tzn. z błędem równym 0). Zauważ, że pochodna f w wyrazie błędu wzrasta o 2 dla każdego innego wzoru. Liczba \xi zwiera się pomiędzy a i b.

W poniższej tabeli znajdują się wzory Newtona-Cotesa typu otwartego.

Rząd Tradycyjna nazwa Wzór Błąd
0 wzór prostokątów \ 2 h f_1 \frac{h^3}{24}\,f^{(2)}(\xi)
1  \frac{3\, h}{2} (f_1 + f_2)  \frac{h^3}{4}\,f^{(2)}(\xi)
2  \frac{4 \,h}{3} (2 f_1 - f_2 + 2 f_3)  \frac{28\, h^5}{90}\,f^{(4)}(\xi)
3  \frac{5 \,h}{24} (11 f_1 + f_2 + f_3 + 11 f_4)  \frac{95\, h^5}{144}\,f^{(4)}(\xi)

Zwróć uwagę, że aby wzór dawał dobre przybliżenie, krok h musi być mały, co oznacza, że przedział całkowania [a, b] również musi być mały, co zazwyczaj nie jest spełnione. Z tego powodu dzielimy przedział na mniejsze podprzedziały i stosujemy metodę Newtona-Cotesa na każdym z tych podprzedziałów a następnie dodając wyniki. Jest to metoda złożona.

Literatura[edytuj | edytuj kod]

  • J.i M. Jankowscy, Przegląd metod i algorytmów numerycznych. Warszawa, 1981. (See Section 4.5)
  • M. Abramowitz and I. A. Stegun, eds. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. New York: Dover, 1972. (See Section 25.4.)
  • George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Section 5.1.)
  • William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, 1988. (See Section 4.1.)
  • Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Section 3.1.)

Przypisy

Zobacz też[edytuj | edytuj kod]