Metody Newtona-Cotesa

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 x_i, 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=b$ są ró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 j\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 j\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 x_i = h i + x₀, z h (nazywanym rozmiarem kroku) równym (x_n - x₀)/n oraz $w_i$ są wagami. Wagi można wyprowadzić z wielomianów bazowych Lagrange'a. To oznacza, że zależą tylko od x_i a nie od funkcji f. L(x) wielomianem interpolacji w postaci Lagrange'a dla punktów (x₀, f(x₀) ),..,(x_n, f(x_n) )

$\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 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

• 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.)

Zobacz też

• Analiza numeryczna
• Metoda numeryczna
• Wzory Newtona-Cotesa