2.2 Kombinatoryka

Często mamy do czynienia ze zbiorami. Gdy elementy zbioru są wypisane, to łatwo możemy znaleĽć ich liczbę. Czasami jednak zbiór jest podany w formie bardziej skomplikowanej i nie jest oczywiste, ile ma ewlementów. Z pomocą przychodzi kombinatoryka - dział matematyki zajmujący się zbiorami skończonymi oraz odwzorowaniami między nimi.
Kombinatoryka zajmuje się wyznaczaniem liczby elementów zbiorów skończonych utworzonych zgodnie z określonymi zasadami. Najważniejszym jej zadaniem jest konstruowanie spełniających pewne określone warunki odwzorowań jednego zbioru skończonego w drugi oraz znajdowanie wzorów na liczbę tych odwzorowań.
Podstawowe pojęcia, którymi posługuje się kominatoryka
Zbiór {x₁ , x₂, ..., x_n} oznacza zbiór o elementach x₁ , x₂, ..., x_n. Każdy zbiór nie zawiera dwóch identycznych elementów, to znaczy każdy element traktujemy tak, jakby występował tylko jeden raz, a kolejność elementów zbioru nie odgrywa roli.

Multizbiór - to zbiór, który może zawierać elementy identyczne, a więc każdy z różnych elementów multizbioru może występować więcej niż jeden raz.
Ciąg (a₁ , a₂, ..., a_n) oznacza ciąg o wyrazach a₁ , a₂, ..., a_n. Kolejność ustawienia wyrazów w ciągu jest bardzo ważna. Zmieniając kolejność wyrazów w ciągu otrzymujemy inny ciąg. Ciąg może zawierać wyrazy identyczne lub nie.
Silnia n! oznacza iloczyn kolejnych liczb naturalnych od 1 do n.
n! = 1 · 2 · 3 · ... · n
0! = 1
Symbol Newtona $\left(\begin{array}{c}n\\ k\end{array}\right)$ dla n, k∈N i 0 ≤ k ≤ n oznacza liczbę określoną wzorem
$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}$

Kombinatoryka odpowiada na pytanie, ile da się zbudować odwzorowań określonego rodzaju z dostępnych elementów. Wyróżniamy trzy rodzaje takich odwzorowań: permutacje, wariacje i kombinacje.
Wzajemnie jednoznaczne przekształcenie pewnego zbioru skończonego na siebie nazywamy permutacją. Permutacja zatem to ilość możliwych przestawień pewnego zbioru w różne ciągi. Ciąg k-elementowy powstały ze zbioru n-elementowego to wariacja, w której ważna jest kolejność elementów. Jedna z możliwości wyboru kilku elementów z pewnego zbioru to kombinacja, przy czym kolejność wyboru elementów nie ma znaczenia. Należy pamiętać, że w wariacji liczy się kolejność ustawienia wyrazów, a kombinacja to tylko zbiór elementów. Elementarną metodą kombinatoryki, często stosowaną intuicyjnie jest również tzw. reguła mnożenia i dodawania.
Mocą zbioru skończonego A nazywamy liczbę jego elementów. Oznaczamy ${\displaystyle \stackrel{=}{A}}$

1.7 Aproksymacja

Funkcja aproksymowana f(x) określona może być w różny sposób. W naszych rozważaniach będzie zadana w postaci zbioru dyskretnych wartości f₀=f(x₀), f₁=f(x₁), f₂=f(x₂),..., f_m=f(x_m), wyznaczonych odpowiednio w punktach x₀, x₁, x₂,..., x_m, zwanych węzłami aproksymacji. Dla ustalenia uwagi oznaczmy przez f^*(x) funkcję aproksymującą, która przybliża f(x), natomiast przez E(f)=f(x)-f^*(x) błąd takiego przybliżenia. W klasycznym przypadku zatem przez aproksymację rozumieć będziemy poszukiwanie, dla danej funkcji f(x), takiej funkcji f^*(x), aby przyjęta norma błędu ||E(f)|| była najmniejsza.

Do najczęściej stosowanych norm należą

norma średniokwadratowa

oraz norma maksymalna

Jak już wspomnieliśmy funkcję f^*(x) zapisujemy w postaci liniowej kombinacji n funkcji, które będziemy nazywać funkcjami bazowymi.

Zatem:

f^*(x)=c₀f₀(x)+c₁f₁(x)+ c₂f₂(x)+ ... +c_nf_n(x),                                                    (1)

gdzie f₀(x),f₁(x),f₂(x),...,f_n(x) są ustalonymi funkcjami bazowymi, c_0,c_1,c_2,...,c_n są poszukiwanymi współczynnikami.

Wielomian (1) nazywać będziemy wielomianem aproksymującym.

Jeżeli np. funkcje bazowe są w postaci jednomianów, tj. f_k(x)=x^k dla k=0,1,2,...,n, wtedy

f^*(x)=c₀+c₁x+c₂x²+...+c_nxⁿ.

W takim przypadku mówimy o aproksymacji za pomocą jednomianów. Natomiast jeśli wybrane funkcje bazowe należą do klasy funkcji trygonometrycznych postaci {sinkx, coskx} lub wykładniczych {e^kx}, k=0,1,...,n, to taką aproksymację nazywać będziemy odpowiednio  trygonometryczną lub wykładniczą. Zgodnie z powyższym, zagadnienie aproksymacji funkcji f(x) polega na zastąpieniu jej wielomianem aproksymującym f^*(x), rozumiane w sensie przyjętej normy ||E(f)||, było jak najmniejsze. Można to osiągnąć, jak się przekonamy, przez odpowiedni dobór w wyrażeniu (1)współczynników c_0,c_1,c_2,...,c_n..

Załóżmy, że chcemy określić wartości tych współczynników tak, aby spełniony był warunek

f^*(x_k)=f(x_k),                  dla k=0,1,2,...,m.                                                            (2)

Tzn. aby funkcje aproksymujące i aproksymowana miały te same wartości we wszystkich węzłach aproksymacji. Prowadzi to do układu m+1 równań liniowych z n+1 niewiadomymi
                               (3)

Zauważmy, że w tym przypadku nie nakładamy żadnych warunków na zachowanie się funkcji f^*(x) poza punktami x₀, x₁, x₂,..., x_m. W innym podejściu do rozwiązania zadania aproksymacji możemy zrezygnować z warunku (2), a w zamian za to żądać, aby funkcja f^*(x) w całym interesującym nas przedziale przebiegała jak "najbliżej" funkcji f(x). Takie sformułowania zadania przybliżenia funkcji prowadzą do różnych ( w zasadzie trzech) ich typów.

 

1. Przybliżenie interpolacyjne.


Jeżeli n=m, to układ (3) ma dokładnie jedno rozwiązanie, a współczynniki c₀, c₁, c₂,..., c_n mają takie wartości, aby w punktach x₀, x₁, x₂,..., x_m funkcja f(x) była zgodna z funkcją przybliżającą f^*(x), tzn. f(x_k)=f^*(x_k), k-0,1,2,...m. Przybliżenie takie nazywamy interpolacją natomiast punkty x₀, x₁, x₂,..., x_m  węzłami interpolacji. Jeśli m > n, to w ogólności nie jest spełniona równość (2), wtedy układ (3) ma więcej równań niż niewiadomych, o takim układzie mówimy, że jest nieokreślony. W tym przypadku trzeba zadowolić się rozwiązaniem przybliżonym.


2. Przybliżenie średniokwadratowe (aproksymacja średniokwadratowa).
   
   Wyrażeniem, którego minimum szukamy jest całka z kwadratu różnicy liczonej między f(x) i jej przybliżeniem f^*(x) w zadanym przedziale [a,b] lub sumą kwadratów takich różnic wyznaczoną w dyskretnych punktach x₀, x₁, x₂,..., x_m.
   
   
3. Przybliżenie jednostajne (aproksymacja jednostajna)
   
   Poszukujemy minimum wyrażenia będącego maksymalną różnicą między f(x) a f^*(x) w przedziale [a,b] lub w dyskretnych punktach x₀, x₁, x₂,..., x_m.

Poniższy rysunek jest ilustracją idei zadania aproksymacji.

Zauważmy, że postawienie i rozwiązanie powyższych zagadnień ma na celu uzyskanie pewnej informacji o funkcji, np. wyznaczenie jej wartości w danym punkcie xąx_k, k=0,1,2,...m.

Weźmy pod uwagę przybliżenie (1.) . Jeżeli punkt x leży wewnątrz zadanego przedziału [a,b], to mówimy o interpolacji. Jeżeli natomiast punkt leży na zewnątrz tego przedziału, to mamy do czynienia z ekstrapolacją. Zwykle błąd interpolacji jest mniejszy niż błąd ekstrapolacji.

Poniższy rysunek przedstawia zakres formułowania tych zadań.

1.6.4 Wzór interpolacyjny Newtona dla równoodległych wartości argumentu

W niżej przedstawionej metodzie, po raz pierwszy założymy, że węzły tworzą ciąg arytmetyczny (o różnicy h), co znacznie uprości wzory interpolacyjne: Podobnie jak przy poprzedniej metodzie, i tym razem należy wprowadzić dodatkowe oznaczenia: Mając dane wartości funkcji w punktach , , ... , różnicą progresywną rzędu pierwszego nazywamy wyrażenie:





Ogólnie różnice progresywne definiujemy jako:
,

Analogicznie definiujemy różnice wsteczne:
dla

Uogólniając:

Warto zauważyć, że ,

Korzystając z powyższych oznaczeń, możemy skorzystać z następujących wzorów:
Wzór


nazywamy pierwszym wzorem interpolacyjnym Newtona. Można go znacznie uprościć,

wprowadzając zmienną dzięki której otrzymujemy:


Wzór ten nazywamy często wzorem interpolacyjnym Newtona na interpolację w przód. Stosujemy go, gdy używamy początkowej części tablicy. Dla danych znajdujących się na końcu, istnieje inny wzór w którym wykorzystuje się różnice wsteczne:


Jest to drugi wzór interpolacyjny Newtona. Podobnie jak poprzednio przyjmując , oraz przekształcając ten wzór otrzymujemy wzór interpolacyjny Newtona na interpolację wstecz:


Błędy dla wcześniej przedstawionych wzorów obliczamy za pomocą następujących wzorów: Dla pierwszego wzoru Newtona:

oraz dla drugiego wzoru Newtona:

Zalety:	Wady:
-   W przypadku węzłów równoodległych, powyższe wzory są wygodne podczas obliczeń ręcznych    -   Łatwo dodać kolejne składniki do wzorów	-   Nie posiada istotnych wad

1.6.1 Metoda interpolacyjna Lagrange’a

Jedną z najpopularniejszych i najprostszych metod interpolacyjnych jest metoda Lagrange'a. Jest to metoda, która zawsze pozwala nam na znalezienie jednoznacznie określonej funkcji interpolującej będącej wielomianem.
Mając dane n+1 węzłów wraz z ich wartościami, szukamy wielomianu W_n(x) stopnia co najwyżej n, który przyjmuje zadane wartości dla zadanych węzłów.
Oznaczając przez

Wzór interpolacyjny Langrange'a możemy zapisać jako:

Obie zapisane powyżej postacie wzoru Lagrange'a są równoważne, stosujemy je jednak w różnych przypadkach.

Przykład: Mając dane węzły 0, 1, 3, 8 wraz z wartościami 2, 6, -1, 8 obliczamy wielomian interpolacyjny: Błąd metody Lagrange'a obliczamy za pomocą wzorów: gdzie .

Zalety:	Wady:
-   Przydatna w obliczeniach ręcznych	-   Nie posiada istotnych wad

1.4 Iteracja

Interpretacje geometryczną pokazano poniżej

Pierwiastek równania (1) jest odciętą (i rzędną) punktu przecięcia krzywej y=F(x) i prostej y=x . Startując z punktu (x₀,f(x₀)) i używając iteracji, otrzymujemy x₁=F(x₀); punkt x₁ na osi x dostajemy, rysując linie poziomą z punktu (x₀,F(x₀))=(x₀,x₁) do przecięcia z prostą y=x w punkcie (x₁,x₁). Stąd prowadzimy linię pionową do (x₁,F(x₁))=(x₁,x₂) itd. Z powyższego rysunku jest oczywiste, że ciąg {x_n} jest zbieżny monotonicznie do a.

Na rysunku poniżej pokazano przypadek, gdy F jest funkcją malejącą

Tym razem zbieżność jest monotoniczna: kolejne przybliżenia x_n leżą na przemian po lewej i po prawej stronie pierwiastka a.

Istnieją też jednak pzrypadki rozbieżności, pokazane na przykładach poniżej

Z rysunków tych widać, że wielkością określającą prędkość zbieżności (lub rozbieżności) jest nachylenie krzywej y=F(x) w otoczeniu pierwiastka. Rzeczywiście, z twierdzenia o wartości średniej mamy



gdzie x_n leży między x_n-1 i x_n. Wobec tego zbieżność jest tym szybsza, im mniejsze jest |f '(x)| w otoczeniu pierwiastka. Zbieżność jest pewna, jeśli |f '(x)|<1 dla każdego x z otoczenia pierwiastka, które zawiera x₀ i x₁. Jeśli jednak |f '(a)|>1, to x_n dąży do a tylko w bardzo szczególnych przypadkach, niezależnie od tego, jak blisko a wybierze się do x₀ (różne do a).
Przykład

Szybka metoda obliczania pierwiastków kwadratowych.

Równanie x²=c można napisać w postaci x=F(x), gdzie

             c>0

Pierwiastkiem jest a=c^1/2, jest też f '(a)=0. Przyjmujemy więc



Dla c=2, x₀=1.5 otrzymujemy x₁=1/2(1.5+2/1.5)=1.4167, x₂=1.414216; porównajmy z tym wartość


Dobrą wartość dla x₀ możemy otrzymać za pomocą suwaka logarytmicznego, ale jak możemy sprawdzić - wystarczy znacznie grubsze przybliżenie. Istotnie, dowodzi się, że jeśli x_n ma t cyfr dokładnych, to x_n+1 ma takich cyfr co najmniej 2t-1. Powyższą metodę iteracyjną obliczania pierwiastków kwadratowych stosuje się powszechnie i w kalkulatorach kieszonkowych, i w komputerach.

1.3.4 Metoda Monte Carlo

Metoda Monte Carlo I

Załóżmy, że chcemy obliczyć całkę z funkcji f(x) w przedziale <x_p; x_k>. Definicja całki oznaczonej Riemana, mówi nam, że wartość całki równa jest polu obszaru pod wykresem krzywej w zadanym przedziale całkowania.
Załóżmy na początek, iż wiemy z całą pewnością, że wartości funkcji w obszarze całkowania mieszczą się w przedziale <y_p; y_k>. Pole prostokąta wyznaczonego przez przedział całkowania: <x_p; x_k> oraz zakres wartości funkcji w tym przedziale: <y_p; y_k> jest prosty do wyznaczenia i wynosi:

Metoda Monte Carlo polega na wylosowaniu n punktów znajdujących się w obrębie wspomnianego prostokąta i na tej podstawie obliczenia stosunku pola powierzchni pod krzywą czyli wartości całki do pola wyznaczonego prostokąta. W tym celu wprowadzimy zmienną pomocniczą c, którą modyfikować będziemy następująco:

• jeżeli wylosowany punkt (x_i, y_i) leży nad osią OY i jednocześnie pod wykresem funkcji całkowanej, czyli spełnia nierówność: 0 < y_i ≤ f(x_i), wówczas zwiększamy zmienną c o jeden,
• jeżeli wylosowany punkt (x_i, y_i) leży pod osią OY i jednocześnie nad wykresem funkcji całkowanej, czyli spełnia nierówność: 0 > y_i ≥ f(x_i), wówczas zmniejszamy zmienną c o jeden,
• jeżeli wylosowany punkt (x_i, y_i) nie spełnia żadnego z powyższych warunków, wówczas pozostawiamy zmienną c bez zmian.

Na poniższym schemacie, punkty spełniające warunek pierwszy oznaczono kolorem niebieskim. Punkty spełniające warunek drugi oznaczono kolorem czerwonym, pozostałe - spełniające warunek trzeci oznaczono kolorem czarnym.

Jak już wspominaliśmy na podstawie wylosowanych punktów i przyporządkowania ich do odpowiedniej kategorii możemy wyznaczyć odpowiednie proporcje:

zatem po przekształceniach wartość szukanej całki możemy wyrazić wzorem:

Wraz ze zwiększaniem się liczby punktów pomiarowych n, rozkładają się one coraz bardziej równomiernie w obrębie wyznaczonego prostokąta dając coraz dokładniejszy wynik. Podstawowym problemem w tej metodzie jest wyznaczenie zakresu wartości funkcji w przedziale całkowania. Dlatego też opracowano również inny algorytm całkowania oparty o Metodę Monte-Carlo, nie wymagający tej informacji.

Przykład:

Obliczymy wartości całki, dla funkcji przedstawionej na schemacie powyżej zakładając, że:
x_p = 3
x_k = 7
y_p = -2
y_k = 5
Liczba wszystkich punktów pomiarowych n wynosi 36.
Liczba punktów niebieskich zwiększających zmienną c wynosi 8.
Liczba punktów czerwonych zmniejszających zmienną c wynosi 3.
Zatem ostateczna wartość zmiennej c wynosi 8 - 3 = 5.
Podstawiając wszystkie dane pod wyznaczony wzór otrzymujemy: |x_k - x_p| * |y_k - y_p| * (c/n) = |7 - 3| * |5 - -2| * (5/36) = 4 * 7 * 0.1388889 = 3.8888892
Zatem przybliżona wartość całki wynosi: 3.8888892

Metoda Monte Carlo II

 Załóżmy, że chcemy obliczyć całkę z funkcji f(x) w przedziale <x_p; x_k>. Definicja całki oznaczonej Riemana, mówi nam, że wartość całki równa jest polu obszaru pod wykresem krzywej w zadanym przedziale całkowania. Przedstawiona tutaj metoda Monte Carlo polega na wylosowaniu n punktów znajdujących się w obrębie przedziału całkowania i na tej podstawie obliczeniu średniej wartości funkcji w tym przedziale.

Zatem jeżeli losowane punkty oznaczymy jako: x₁, x₂, ... x_n, to wartość średnią obliczymy następująco:

A przybliżoną wartość całki mnożąc uzyskaną wartość średnią przez długość całkowanego przedziału:

Wraz ze zwiększaniem się liczby punktów pomiarowych n, rozkładają się one coraz bardziej równomiernie w obrębie wyznaczonego przedziału dając coraz dokładniejszy wynik. Z drugiej zaś strony uważać należy by przy dużych ilościach punktów pomiarowych nie przekroczyć zakresu używanych zmiennych podczas dodawania przy obliczaniu wartości średniej. Zabezpieczyć się można przed takim przypadkiem obliczając wartość średnią następująco:

ale z kolei mamy tutaj problem nakładania się na siebie zaokrągleń z dzielenia przez n.

Przykład:

Załóżmy, iż na wykresie powyżej zakres całkowania to: x_p = 2, x_k = 10
Wartości kolejnych wylosowanych punktów to: x₁ = 2.4, x₂ = 3.1, x₃ = 6, x₄ = 9, x₅ = 9.5, a wartości funkcji całkowanej w tych punktach to: f(x₁) = 3, f(x₂) = 3.5, f(x₃) = 5, f(x₄) = 5.1, f(x₅) = 4.4
Najpierw obliczymy wartość średnią: (3 + 3.5 + 5 + 5.1 + 4.4) / 5 = 21 / 5 = 4.2
A następnie pomnożymy tą wartość przez długość przedziału całkowania otrzymując przybliżoną wartość całki: (10 - 2) * 4.2 = 8 * 4.2 = 33.6

1.3.3 Metoda Simpsona

Załóżmy, że chcemy obliczyć całkę z funkcji f(x) w przedziale <x_p; x_k>. Definicja całki oznaczonej Riemana, mówi nam, że wartość całki równa jest sumie pól obszarów pod wykresem krzywej w zadanym przedziale całkowania. Sumę taką możemy obliczyć w przybliżeniu dzieląc obszar całkowania na n równych części. W metodach prostokątów i trapezów zakładaliśmy, że przybliżenie funkcji w przedziale jest funkcją liniową (przybliżenie odwzorowywało funkcję na odcinek w obrębie przedziału). W metodzie Simpsona w każdym takim przedziale będziemy przybliżać funkcję dla, której obliczamy całkę przy pomocy paraboli.



Jak już wspomnieliśmy przedział całkowania <x_p; x_k> podzielimy na n równych części. Szerokość każdej z nich wynosić będzie zatem:

 Na końcach każdego przedziału funkcja będzie przyjmowała wartości f( x_i-1 ) oraz f( x_i ) dla i = 1, 2, ..., n, gdzie x_i = x_p + i*dx.
W każdym przedziale <x_i-1; x_i> funkcję f(x) będziemy przybliżać przy pomocy paraboli g(x) = a_ix² + b_ix + c_i
By jednoznacznie określić parabolę, potrzebujemy danych trzech punktów, przez które ma ona przechodzić. Dla każdego przedziału mamy dane już dwa (na końcu i początku przedziału), brakuje nam zatem jeszcze jednego. Dlatego teżdla każdego takiego przedziału wprowadzimy punkt środkowy t_i = (x_i-1 + x_i) / 2

Pole pod parabolą obliczmy z definicji całki Newtona-Leibniza, która mówi, że całka oznaczona z funkcji w przedziale zamkniętym określona jest jako różnica wartości funkcji pierwotnej na końcu tego przedziału i wartości funkcji pierwotnej na początku tego przedziału. Funkcja pierwotna dla funkcji f(x), to taka funkcja F(x), że jej pochodna równa jest funkcji f(x), czyli F'(x) = f(x). Zatem Stosując podane twierdzenie do naszego przybliżenia g(x) otrzymamy: