Metody numeryczne: listopada 2013

Metoda równego podziału (metoda połowienia, metoda bisekcji, metoda połowienia przedziału) – jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na twierdzeniu Bolzano-Cauchy’ego:

Jeżeli funkcja ciągła $f(x)$ ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania $f(x)=0.$

Aby można było zastosować metodę równego podziału, muszą być spełnione założenia:

funkcja $f(x)$ jest ciągła w przedziale domkniętym $[a;b]$
funkcja przyjmuje różne znaki na końcach przedziału: $f(a)f(b)<0$

Przebieg algorytmu:

Sprawdzić, czy pierwiastkiem równania jest punkt $x_1=\frac{a+b}{2},$ czyli czy $f(x_1)=0.$
Jeżeli tak jest, algorytm kończy się, a punkt jest miejscem zerowym. W przeciwnym razie $x_1$ dzieli przedział $[a,b]$ na dwa mniejsze przedziały $[a, x_1]$ i $[x_1, b].$
Wybierany jest ten przedział, dla którego spełnione jest drugie założenie, tzn. albo $f(x_1)f(a) < 0$ albo $f(x_1)f(b) < 0.$ Cały proces powtarzany jest dla wybranego przedziału.

Działanie algorytmu kończy się w punkcie 2 albo po osiągnięciu żądanej dokładności przybliżenia pierwiastka.

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'astopnia 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.

Ogólna metoda

Przykład interpolacji wielomianowej.

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[edytuj | edytuj kod]

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

Metody numeryczne

czwartek, 28 listopada 2013

niedziela, 3 listopada 2013

Ogólna metoda

Znajdowanie odpowiedniego wielomianu[edytuj | edytuj kod]

Dowód istnienia wielomianu interpolującego