Metody numeryczne - Paweł Wasiak : 2013

czwartek, 28 listopada 2013

Metoda Simpsona

Całkowanie metodą Simpsona – jedna z metod przybliżania wartości całki oznaczonej funkcji rzeczywistej.

Metoda ma zastosowanie do funkcji stablicowanych w nieparzystej liczbie równo odległych punktów (wliczając końce przedziału całkowania). Metoda opiera się na przybliżaniu funkcji całkowanej przez interpolację wielomianem drugiego stopnia.

Znając wartości $y_0,\ y_1,\ y_2$ funkcji $f(x)$ w 3 punktach $x_0,\ x_1,\ x_2$ (przy czym $x_2-x_1 = x_1-x_0 = h\;$ ), przybliża się funkcję wielomianem Lagrange'a i, całkując w przedziale $[x_0,x_2]$ , otrzymuje przybliżoną wartość całki:

$\int\limits_{x_0}^{x_2}f(x)dx\approx \frac h 3 (y_0+4y_1+y_2)$

Błąd, który przy tym popełniamy, jest równy: $R = \frac{1}{90} h^5 |f^{(4)}(c)|$ , gdzie:

$c \in [x_0; x_2]$ .

Nie znamy położenia punktu c, więc posługujemy się poniższym szacowaniem, mającym zastosowanie w obliczeniach numerycznych:

$R \leqslant \frac{1}{90} h^5 \max_{x \in [x_0; x_2]} |f^{(4)}(x)|$ .

Znając wartości funkcji w 2k+1 kolejnych, równo odległych punktach $x_0,\,x_1,\dots x_n$ (gdzie n=2k), możemy iterować powyższy wzór na kprzedziałów:

otrzymując:

$\int\limits_{x_0}^{x_n}f(x)dx=\sum_{i=1}^k \int\limits_{x_{2i-2}}^{x_{2i}}f(x)dx\approx \frac h 3 \left( y_0+4\sum_{i=1}^k y_{2i-1}+2\sum_{i=1}^{k-1} y_{2i}+y_{n} \right)$ .

Wartość błędu, jakim są obarczone wyliczenia, wyraża się wzorem:

$R \leqslant \frac{1}{180} (x_n - x_0) h^4 \max_{x \in [x_0; x_n]} |f^{(4)}(x)|$ .

By czytelnik mógł go odnieść do rysunku:

$x_n = b$ ; $f(x_n) = y_n$ ,

$x_0 = a$ ; $f(x_0) = y_0$ .

Geometrycznie metoda ta odpowiada zastąpieniu w każdym z kolejnych k przedziałów zmiennej x łuku wykresu funkcji y=f(x) łukiem paraboli przeprowadzonej przez trzy kolejne węzły interpolacji (punkty wykresu o znanych współrzędnych) odpowiadające początkowi, środkowi i końcowi kolejnego przedziału.

Aproksymacja

Aproksymacja – proces określania rozwiązań przybliżonych na podstawie rozwiązań znanych, które są bliskie rozwiązaniom dokładnym w ściśle sprecyzowanym sensie. Zazwyczaj aproksymuje się byty (np. funkcje) skomplikowane bytami prostszymi. Często stosowana w przypadku szukania rozwiązań dla danych uzyskanych metodami empirycznymi, które mogą być obarczone błędami

Zadanie najlepszej aproksymacji

Niech dana będzie przestrzeń liniową $X$ z normą $\|\cdot\|$ i niech $V \subset X$ będzie podprzestrzenią liniową $X$ skończonego wymiaru. Zadanie najlepszej aproksymacji polega na znalezieniu takiego $v^* \in V$ (elementu najlepszej aproksymacji dla danego $x \in X$ ), że zachodzi:

$\displaystyle{\forall{v \in V}}\quad\|x - v^*\| \leqslant \|x-v\|$

Należy przez to rozumieć, że element $v^*$ jest elementem "najbliższym" do aproksymowanego $x$ spośród wszystkich elementów $v \in V$ .

Zadanie najlepszej aproksymacji jest zawsze rozwiązywalne tzn. dla każdego $x \in X$ istnieje element najlepszej aproksymacji $v^*$ , ale niekoniecznie jest on jedyny. Należy zauważyć, że element najlepszej aproksymacji zależy od normy, jaka została przyjęta w przestrzeni $X$ .

Zadanie najlepszej aproksymacji w przestrzeniach unitarnych

Niech $X$ będzie przestrzenią z iloczynem skalarnym i niech norma w $X$ będzie generowana tym iloczynem: $\|x\|= \sqrt{\langle x, x \rangle}$ .

Wtedy element najlepszej aproksymacji jest jedyny i jest określony następującą tożsamością

$\forall{v \in V}\ \ \langle x-v^*, v \rangle = 0$

Aproksymacja funkcji

Aproksymacje można wykorzystać w sytuacji, gdy nie istnieje funkcja analityczna pozwalająca na wyznaczenie wartości dla dowolnego z jej argumentów, a jednocześnie wartości tej nieznanej funkcji są dla pewnego zbioru jej argumentów znane. Mogą to być na przykład wyniki badań aktywności biologicznej dla wielu konfiguracji leków. Do wyznaczenia aproksymowanej aktywności biologicznej nieznanego leku można wówczas zastosować jedną z wielu metod aproksymacyjnych.

Aproksymowanie funkcji może polegać na przybliżaniu jej za pomocą kombinacji liniowej tzw. funkcji bazowych Od funkcji aproksymującej, przybliżającej zadaną funkcję nie wymaga się, aby przechodziła ona przez jakieś konkretne punkty, tak jak to ma miejsce w interpolacji. Z matematycznego punktu widzenia aproksymacja funkcji $f$ w pewnej przestrzeni Hilberta $H$ jest zagadnieniem polegającym na odnalezieniu pewnej funkcji $g\in G,$ gdzie $G$ jest podprzestrzenią $H$ tj. $G\subset H$ takiej, by odległość (w sensie obowiązującej w $H$ normy) między $f$ a $g$ była jak najmniejsza. Funkcja aproksymująca może wygładzać daną funkcję (gdy funkcja jest gładka, jest też różniczkowalna).

Aproksymacja funkcji powoduje pojawienie się błędów, zwanych błędami aproksymacji. Dużą zaletą aproksymacji w stosunku do interpolacji jest to, że aby dobrze przybliżać, funkcja aproksymująca nie musi być wielomianem bardzo dużego stopnia (w ogóle nie musi być wielomianem). Przybliżenie w tym wypadku rozumiane jest jako minimalizacja pewnej funkcji błędu. Prawdopodobnie najpopularniejszą miarą tego błędu jest średni błąd kwadratowy, ale możliwe są również inne funkcje błędu, jak choćby błąd średni.

Istnieje wiele metod aproksymacyjnych. Jednymi z najbardziej popularnych są: aproksymacja średniokwadratową i aproksymacja jednostajna oraz aproksymacja liniowa, gdzie funkcją bazową jest funkcja liniowa.

wtorek, 29 października 2013

Schemat Hornera

Schemat Hornera powiązany z nazwiskiem Hornera - brytyjskiego matematyka żyjącego na przełowmie XVIII i XIX wieku. Schemat Hornera to sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń. Jest to również algorytm dzielenia wielomianu W(x) przez dwumian x - c.

Schemat Hornera pozwala na wyznaczenie ilorazu Q(x) z dzielenia wielomianu
W(x) = a_nxⁿ + a_n-1x^n-1 + ... + a₂x² + a₁x + a₀ przez dwumian x - c.

Podzielmy przez dwumian x - 5 wielomian W(x) = x³ + x² - 10x + 8

Wykonując dzielenie za pomocą schematu Hornera tworzymy tabelkę, gdzie w górnym wierszu schematu wypisujemy współczynniki dzielnej, tzn. wielomianu x³ + x² - 10x + 8.

	1	+1	-10	+8
+5	1	+6	+20	(+108)

W dolnym wierszu w pierwszej kolumnie zapisujemy liczbę odjętą od x w dzielniku. Pozostałe wartości to współczynniki ilorazu x² + 6x + 20 oraz reszta (+108).

Wiersz dolny otrzymujemy z górnego w następujący sposób:
- pierwszy współczynnik wiersza dolnego równy jest pierwszemu współczynnikowi wiersza górnego tzn. liczbie 1,

- drugi współczynnik wiersza dolnego otrzymujemy, mnożąc poprzedni współczynnik tego wiersza, tzn. 1 przez 5 i dodając do drugiego współczynnika wiersza górnego, tzn. do +1
1 · (+5) + (+1) = +6 ,

- trzeci współczynnik wiersza dolnego otrzymujemy, mnożąc poprzedni współczynnik tego wiersza, tzn. +6 przez +5 i dodając do trzeciego współczynnika wiersza górnego, tzn. -10
(+6) · (+5) + (-10) = +20 ,

- podobnie mamy (+20) · (+5) + (+8) = +108,

Ostatecznie możemy zapisać:
(x³ + x² - 10x + 8) : (x - 5) = x² + 6x + 20 reszta +108.

Film prezentujący zastosowanie schematu Hornera:

poniedziałek, 14 października 2013

Interpolacja wielomianowa

Interpolacja wielomianowa, nazywana też interpolacją Lagrange'a, od nazwiska pioniera badań nad interpolacją Josepha Lagrange'a, lub po prostu interpolacją jest metodą numeryczną przybliżania funkcji tzw. wielomianem Lagrange'a stopnia n, przyjmującym w n+1 punktach, zwanych węzłami interpolacji wartości takie same jak przybliżana funkcja.

Interpolacja jest często stosowana w naukach doświadczalnych, gdzie dysponuje się zazwyczaj skończoną liczbą danych do określenia zależności między wielkościami.

Zgodnie z twierdzeniem Weierstrassa dowolną funkcję y=f(x) ciągłą na przedziale domkniętym można dowolnie przybliżyć za pomocą wielomianu odpowiednio wysokiego stopnia.

Interpolacja liniowa

Jest przypadkiem interpolacji wielomianowej dla dwóch punktów pomiarowych $x_0$ i $x_1$ , dla których można utworzyć funkcję liniową, której wykres przechodzi przez punkty

$(x_0,f(x_0))$ i $(x_1,f(x_1))$ .

Ogólna metoda

Metoda interpolacji polega na:

wybraniu $n+1$ punktów $x_0,x_1,\cdots ,x_n$ należących do dziedziny $f$ , dla których znane są wartości $y_0=f(x_0),y_1=f(x_1),\cdots ,y_n=f(x_n)$

znalezieniu wielomianu $W(x)$ stopnia co najwyżej $n$ takiego, że $W(x_0)=y_0,W(x_1)=y_1,\cdots W(x_n)=y_n$ .

Interpretacja geometryczna – dla danych $n+1$ punktów na wykresie szuka się wielomianu stopnia co najwyżej $n$ , którego wykres przechodzi przez dane punkty.

Znajdowanie odpowiedniego wielomianu

Wielomian przyjmujący zadane wartości w konkretnych punktach można zbudować w ten sposób:

Dla pierwszego węzła o wartości $f(x_0)$ znajduje się wielomian, który w tym punkcie przyjmuje wartość $f(x_0)$ , a w pozostałych węzłach $x_1,x_2,\cdots ,x_n$ wartość zero.
Dla kolejnego węzła znajduje sie podobny wielomian, który w drugim węźle przyjmuje wartość $f(x_1)$ , a w pozostałych węzłach $x_0,x_2,\cdots ,x_n$ wartość zero.
Dodaje się wartość ostatnio obliczonego wielomianu do wartości poprzedniego
Dla każdego z pozostałych węzłów znajduje się podobny wielomian, za każdym razem dodając go do wielomianu wynikowego
Wielomian będący sumą wielomianów obliczonych dla poszczególnych węzłów jest wielomianem interpolującym

Dowód ostatniego punktu i dokładny sposób tworzenia poszczególnych wielomianów opisany jest poniżej w dowodzie istnienia wielomianu interpolującego będącego podstawą algorytmu odnajdowania tego wielomianu.

Dowód istnienia wielomianu interpolującego

Niech $x_0,x_1,\cdots ,x_n$ będą węzłami interpolacji funkcji $\! f$ takimi, że znane są wartości $\! f(x_0)=y_0,f(x_1)=y_1,\cdots ,f(x_n)=y_n$

Można zdefiniować funkcję:

$L_i(x)=\prod_{j = 0 \and j\ne i}^n \frac{x-x_j}{x_i-x_j}\ \ \ \ \$ , $i\in {0,1\cdots ,n}$

taką, że dla $x\notin \{x_0,x_1,\cdots ,x_n\}$ $L_i(x)$ jest wielomianem stopnia $n$ (mianownik jest liczbą, a licznik iloczynem $n$ wyrazów postaci $(x-x_{j\ })$ )

Gdy $x_k\in \{x_0,x_1,\cdots ,x_n\}$ i $k=i$ :

$L_i(x_k)=L_i(x_i)=\prod_{j = 0 \and j\ne i}^n (\frac{x_i-x_j}{x_i-x_j})=\prod_{j = 0 \and j\ne i}^n (1) = 1$

Gdy $x_k\in \{x_0,x_1,\cdots ,x_n\}$ i $k\not=i$ :

$L_i(x_k)=\prod_{j = 0 \and j\ne i}^n \frac{x_k-x_j}{x_i-x_j}\ =\frac{(x_k-x_0)\cdot (x_k-x_1)\cdot \cdots \cdot (x_k-x_{k })\cdot \cdots (x_k-x_n) }{(x_i-x_0)\cdot (x_i-x_1)\cdot \cdots \cdot (x_i-x_{i-1 })\cdot (x_i-x_{i+1 })\cdot \cdots (x_i-x_n) }\ =\ 0\ \$

(licznik = 0 ponieważ występuje element $(x_k-x_k)$ )

Niech $\! W(x)$ będzie wielomianem stopnia co najwyżej $n$ , określonym jako:

$\! W(x)=y_0\cdot L_0(x) + y_1\cdot L_1(x) + y_2\cdot L_2(x) + \cdots + y_n\cdot L_n(x)$

Dla $\! x_i \in \{x_0,x_1,\cdots ,x_n\}$

$W(x_i)= y_0\cdot L_0(x_i) + y_1\cdot L_1(x_i) + \cdots + y_i\cdot L_i(x_i) + \cdots + y_n\cdot L_n(x_i)$ .

Wszystkie składniki sumy o indeksach różnych od $i$ są równe zeru (ponieważ dla $j\not=i\ \ L_i(x_j)\ =\ 0)$ , składnik o indeksie $i$ jest równy:

$L_i(x_i)\cdot y_i\ =\ 1\cdot y_i\ =\ y_i$ .

A więc

$\! W(x_i)=y_i$

z czego wynika, że $\! W(x)$ jest wielomianem interpolującym funkcję $\! f(x)$ w punktach $x_0,x_1,\cdots ,x_n$ .

Jednoznaczność interpolacji wielomianowej

Dowód

Załóżmy, że istnieją dwa tożsamościowo różne wielomiany $W_1(x)$ i $W_2(x)$ stopnia $n$ , przyjmujące w węzłach $\! x_0,x_1,\cdots ,x_n$ takie same wartości.

Niech

$\! W_3(x) = W_1(x) - W_2(x)$

będzie wielomianem. Jest on stopnia co najwyżej $n$ (co wynika z własności odejmowania wielomianów).

Ponieważ $W_1(x)$ i $W_2(x)$ w węzłach $x_i : i \in 0,1,\cdots ,n$ interpolują tę samą funkcję, to $W_1(x_i)=W_2(x_i)$ , a więc $W_3(x_i)=0$ (węzły interpolacji są pierwiastkami $W_3(x)$ ).(*)

Ale każdy niezerowy wielomian stopnia $n$ ma co najwyżej $n$ pierwiastków rzeczywistych, a ponieważ z (*) wiadomo, że $\! W_3(x)$ ma $n+1$ pierwiastków, to $W_3(x)$ musi być wielomian tożsamościowo równy zeru. A ponieważ

$\! W_3(x)\ =\ W_1(x) - W_2(x)\ =\ 0$

$\! W_1(x)\ =\ W_2(x)$

co jest sprzeczne z założeniem, że $W_1(x)$ i $W_2(x)$ są różne.

Błąd interpolacji

Dość naturalne wydaje się przyjęcie, że zwiększenie liczby węzłów interpolacji (lub stopnia wielomianu interpolacyjnego) pociąga za sobą coraz lepsze przybliżenie funkcji f(x) wielomianem $L_n(x)$ . Idealna byłaby zależność:

$\! \lim_{n \to \infty}L_n(x) = f(x)$ ,

tj. dla coraz większej liczby węzłów wielomian interpolacyjny staje się "coraz bardziej podobny" do interpolowanej funkcji.

Dla węzłów równo odległych tak być nie musi → efekt Rungego.

Można dowieść, że dla każdego wielomianu interpolacyjnego stopnia $n$ , przybliżającego funkcję $f(x)$ w przedziale $[a,b]$ na podstawie $n+1$ węzłów, istnieje taka liczba $\! \xi$ zależna od $x$ , że dla reszty interpolacji $\! r(x)$

$\! \frac{f^{(n+1)}(\xi)}{(n+1)!}\cdot p_n(x)= r(x)$

gdzie $p_n(x)=(x-x_0)(x-x_1)\cdots (x-x_n)$ , a $\xi \in [a;b]$ jest liczbą zależną od x.

Do oszacowania z góry wartości $r(x)$ można posłużyć się wielomianami Czebyszewa stopnia $n+1$ do oszacowania wartości $p_n(x)$ dla $x\in [-1,1]$ . Dla przedziału $[a,b]$ wystarczy dokonać przeskalowania wielomianu $p_n(x)$ .

Wikipedia