Algebra liniowa/Przestrzenie metryczne
1/10
Przestrzenie metryczne
w tym: pojęcie funkcji, iloczynu kartezjańskiego
Niełatwa w odbiorze dla przeciętnego, normalnego, ciężko pracującego człeka definicja brzmi:
Jest to taka para P = (X, ρ), której funkcja ρ określona na zbiorze X spełnia jakieś tam założenia.
Już pewnego wyjaśnienia wymaga określenie „para”. Po prostu jest to zbiór, rodzaj pojemnika, w której pierwszym elementem jest dziedzina (mówiąc kolokwialnie – zbiór, z którego sobie zapieprzamy liczby) funkcji ρ, a drugim – właśnie ta funkcja.
A, jedna uwaga – samo „mięso”, czyli sposób rozwiązywania zadania, zaczyna się gdzieś w połowie piątej stronie. Przedtem – sporo teorii, którą wydaje mi się – każdy powinien w jakimś kawałku posiadać przed rozwiązywaniem zadań. Jednak, jeżeli zacznie was nudzić, pomyślicie „Co on pieprzy”, to przejdźcie już do przykładu rozwiązanego zadania.
Wyjaśnienie, co to jest „funkcja”. Człowiek normalny, czyli tuż po napisanej maturze, ale jeszcze przed studiami, jest przyzwyczajony do np. takiej postaci funkcji:
f(x) = 5 – x
(x należy do zbioru liczb rzeczywistych)
Za „iksa” coś tam podstawiamy; wrzucamy jakąś liczbę, ta funkcja coś z tą liczbą robi i coś tam wypluwa. Na przykład, w powyższym przykładzie „wrzucamy” w funkcję liczbę 2, funkcja coś tam z liczbą zrobi i wypluje 3. Czemu? Po prostu za „iksa” podstawiamy 2 i wykonujemy działanie: f(2) = 5 – 2 = 3
Czemu podkreśliłem dwójkę w obydwu przypadkach? Bo możemy sobie wrzucić jakąś liczbę a , która będzie liczba rzeczywistą, na miejsce tego podkreślenia. A co, nie zawsze musimy wstawiać konkretne liczby, bo nam się nie chce albo rzygamy na widok liczb; wynik będzie taki: f(a) = 5 – a
Pójdźmy dalej, możemy sobie zamiast „iksa” podstawić jakieś tam wyrażenie, załóżmy: Argument: c + h + u + j
f(c + h + u + j) = 5 – (c + h + u + j) = 5 – c – h – u – j
Jak widzimy, funkcję możemy sobie wyobrazić jako „czarną skrzynkę”, w którą coś wrzucamy, czekamy, aż skrzynka pomyśli, po czym funkcja „wypluwa” coś, będącym wynikiem.
Specjalnie pogrubiłem słowo „coś”, bo tak naprawdę, można funkcję określić na czymkolwiek, a w wyniku też dostać cokolwiek.
Na przykład, chcemy sobie policzyć pole prostokąta. Wzór, znany zapewne ze szkoły Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
2/10
podstawowej, wygląda tak:
P = a * b
A ponieważ, mówiąc idiotycznie prosto, jestem pojebany, postanowiłem zapisać to jako jakąś funkcję:
P(a, b) = a * b
Ba, poszedłem o krok dalej, bo powiedzmy wziąłem do serca wykład z Problemów
Społecznych Informatyki, skasowałem wszystkie brutalne gry, nielegalne oprogramowanie i nudziło mi się w domu. Postanowiłem sobie zapisać coś w tym stylu:
P: (a , b) jakaś tam liczba
Symbol przed dwukropkiem oznacza po prostu jakąś tam nazwę funkcji, potem mam napisane argumenty, a na końcu – wynik. Faktycznie, wrzucam dwie liczby i w wyniku otrzymuję jakąś tam liczbę.
No dobra, ale powyższy zapis jest do dupy. Nie wiemy przecież, skąd wzieliśmy liczby a i b.
Czy to są liczby naturalne? A może całkowite? Rzeczywiste? Zespolone? Niestety, będziemy się bawić w programowanie (niestety, bo jedyne, co próbowałem programować, to pralkę, a i tak pranie wyszło takie, że pożal się Boże), gdzie definiowanie funkcji wymaga konkretów.
By trochę uściślić, poprawię powyższy napis:
P: (liczba rzeczywista a, liczba rzeczywista b) liczba rzeczywista No dobra, wiemy, skąd zapieprzamy liczbę a, skąd liczbę b, są to jakieś tam dwie liczby rzeczywiste, które się wrzuca w funkcję i wychodzi liczba rzeczywista. Dobra, ale i to nie jest konkretne.
Bo przecież nie będziemy do końca życia ograniczać do jebanych literek a, b, x, y czy cholera wie, jakich jeszcze. Trzeba precyzyjnie napisać zbiór, z którego czerpiemy argumenty i zbiór, w którym znajdzie się nasz potencjalny wynik, czyli już poprawny zapis powinien wyglądać tak:
P: R x R R
(lub, równoważne)
P: R2 R
Jest to tzw. specyfikacja funkcji
I tutaj mogę sam siebie się zapytać, a nawet powinienem: „co to jest R x R? A R2 co do cholery oznacza”? Pojawia się pojęcie „iloczynu kartezjańskiego”.
Powiedzmy, że mamy zbiór, składający się z 10 facetów i 10 dziewczyn, które mają umysły wyjątkowo heteroseksualne. Możemy je połączyć (tak, te uśmieszki są kierowane w dobrą stronę) w dowolne pary. Poza tym, że będziemy mieć niesamowitą orgię, zbiór takich wszystkich możliwych „par” możemy nazwać „iloczynem kartezjańskim” zbiorów głupich chłopów i czasem Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
3/10
niegłupich bab (te przymiotniki to fakty, nie będziemy się nad nimi rozwodzić).
Jeżeli mamy dwa zbiory – zbiór A oraz zbiór B, to iloczyn kartezjański możemy krótko określić jako A x B.
Przykład:
Mamy zbiór A, składający się z cyfr: 2, 3, 4
I zbiór B, składający się z cyfr: 1, 5, 6.
Trzeba dodać, że odpowiednie „pary” zazwyczaj zapisuje się normalnie w nawiasach, ale gdzie kolejność jest kurewsko ważna, więc iloczyn kartezjański będzie się składać z następujących elementów:
(2,1),(2,5),(2,6),
//to, z czym można „połączyć” dwójkę ze zbioru A
(3,1),(3,5),(3,6),
//to, z czym można „połączyć” trójkę ze zbioru A
(4,1),(4,5),(4,6)
//to, z czym można „połączyć” czwórkę ze zbioru A.
Jeżeli więc mamy zapis R x R (równoważnie: R2, bo nikomu się nie chce pisać znaków mnożenia) przy specyfikacji funkcji, to po prostu oznacza to jakąś tam parę liczb, w której pierwszym elementem jest jakaś liczba rzeczywista, a drugim – również liczba rzeczywista.
Na przykład, zapis R3 pokazuje nam, że mamy do czynienia z trójką liczb rzeczywistych, zapisanych na przykład tak: (a, b, c), w której a jest jakąś liczbą rzeczywistą, b też, a i c nie wyrywa się z kanonów.
Przyszedł mi do głowy taki niebanalny przykład funkcji (uwaga, wymagana znajomość silni):
f(a, b) = a2 + b!
I ktoś bardzo złośliwy każe nam napisać specyfikację tej funkcji. I se tak głośno myślimy:
„Hmm... za a mogę wstawić cokolwiek, co mi się tylko podoba, bo do kwadratu mogę podnieść, co se tam zechcę. Ale b... nie wiem, czy dla jakiejkolwiek liczby mogę sobie znaleźć silnię. Dla 3 se znajdę, ale ile wynosi silnia z 5,312? Cholera wie”.
Nie „cholera wie”, tylko jak widzimy, liczba b w powyższej funkcji wymaga specjalnego traktowania. Nie możemy wstawić cokolwiek. A najbliższe prawdy będzie chyba stwierdzenie, że najlepiej będzie za b wstawiać tylko liczby naturalne.
Spójrzmy na argumenty, które mamy wstawić. Za a wstawiajmy, co chcemy, ale za b możemy wstawić tylko liczbę naturalną. Możemy więc wstawić tylko taką parę liczb, z których pierwsza (a) będzie rzeczywista, a druga (b) - tylko naturalna.
A, jeszcze wynik. Nie jest to specjalnie rzecz trudna, bo wynikiem może być też jakaś tam liczba rzeczywista (jak podniesiemy jakiegoś „potworka” - liczbę rzeczywistą do kwadratu, to wyjdzie również jakaś odrażająca liczba rzeczywista, a jak dodamy jakąś liczbę naturalną – wynik Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
4/10
silni – to nam to specjalnie nie pomoże).
Widzimy więc, że pary argumentów – (a, b) będą iloczynem kartezjańskim zbioru liczb rzeczywistych (bo pierwsza liczba to chuj wie, co, cokolwiek) i naturalnych (bo tylko takie możemy
„wrzucić” do silni), więc nasze argumenty będziemy czerpać ze zbioru R x N.
Dla przypomnienia – wymyśliłem se taką funkcję:
f(a, b) = a2 + b!
f: R x N R
Stąd zapieprzamy pierwszą liczbę
Stąd drugą liczbę
A funkcja zwraca nam liczbę z tego
zbioru
Trochę o funkcjach napisałem, czas wrócić do przestrzeni metrycznych, gdzie jednak trochę się nam pomiesza zapewne dziedzina.
Ogólnie sam zapis przestrzeni metrycznej jako pary wygląda następująco:
P = (_ , _)
W to miejsce „wsadzamy” dziedzinę;
A w to miejsce funkcję, która ma
iloczyn kartezjański, skąd będziemy brać pojedynczy argument
być metryką
Czyli na przykład zapis:
P = (R , ρ)
oznacza po prostu, że w funkcję ρ wrzucimy dwie liczby.
A taki:
P = (R2 , ρ)
oznacza, że w funkcję ρ wrzucimy dwie pary liczb.
Nie daj Boże, jeżeli zdarzy się kiedyś taki zapis:
P = (R3 , ρ)
oznaczający, że funkcja będzie potrzebować dwóch trójek liczb.
Dlaczego tak dziwnie i czemu, kurwa mać, dwa argumenty od razu?
W przestrzeni metrycznej najważniejsza jest funkcja. Nie jest to pierwsza z brzegu wzięta z dupy funkcja... To znaczy, najczęściej, by dręczyć studentów – właśnie taka jest, ale ma swoje zadanie: ma policzyć odległość pomiędzy dwoma argumentami. Co oznacza „odległość”?
Przykładam linijkę i zmierzyłem, po co się tak męczyć? No niestety, ktoś se jednak pomyślał, że Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
5/10
odległoś se będzie mierzył jakimś specjalnym wzorem, czy – zapewne już ktoś pomyślał „Jeszcze raz napisze to słowo, to rzygnę” - funkcją.
By uznać taką funkcję za godną siedzenia w przestrzeni metrycznej, musi spełniać trzy warunki (dokładne definicje – na pewno gdzieś w internecie):
1. Dla tych samych argumentów wartość musi być równa 0
ρ(x, x) = 0
2. Zmienienie kolejności argumentów ma chuja dać
ρ(x, y) = ρ(y,x)
3. Funkcja dla dowolnych, z dupy wziętych argumentów ma spełniać taką nierówność: ρ(x, z) <= ρ(x, y) + ρ(y, z)
(<= oznacza „większe bądź równe)
Dobra, więc finalnie – przykład:
1. Sprawdź, czy para (R2 , ρ), gdzie ρ = ((x1, y1), (x2, y2)) = | x1 – x2 | + | y1 – y2| jest metryką.
Brzmi złowrogo, ale – damy radę. Najpierw sprawdzimy, czy faktycznie jest metryką.
Jak widzimy (po zbiorze, z którego zapieprzamy argumenty), argumenty będą parą. Czyli wrzucamy jakąś pierwszą parę, wrzucamy drugą i sprawdzamy, czy mieszczą się w naszych surowych ramach.
Załóżmy, dla wygody zapisu, że w zapisie typu: ρ ( a, b)
a będzie oznaczać parę (x1, y1), a b – parę (x2, y2) (specjalnie zmieniłem zwyczajowe x, y na literki a i b, aby się nam nie pojebało od razu).
1) Po pierwsze, dla takich samych par - wynik musi się równać zero.
Czyli ρ (a, a) – większość ludzi na studiach od razu przyzna się do przynależenia do takich argumentów – ma nam dać 0.
Jak sobie zapisaliśmy, a oznacza (x1, y1). Patrzmy, co się stanie.
ρ (a, a) = ρ ((x1, y1), (x1, y1))
Dobra, już sobie „przywróciliśmy” zapis do zgodnego z treścią zadania, więc policzmy: ρ ((x1, y1), (x1, y1)) = |x1 – x1| + |y1 – y1|
Kreskami namalowałem „miejsca”, w które wsadzamy poszczególne liczby. To tak dla ułatwienia, co gdzie powinno pójść. Mam nadzieję, że wśród braci studenckiej nie muszę się gęsto usprawiedliwiać i znajdę wyjaśnienie dla tak krzywych kresek.
Nie ulega wątpliwościom, że w pierwszym „członie” (napisałbym normalnie, ale nie chcę zbytnio przeklinać) wyłazi ogromne zero, z drugiego – też.
Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
6/10
|x1 – x1| + |y1 – y1| = 0 + 0 = 0
Więc:
ρ (a, a) = 0
Okej, sprawdziliśmy pierwszą własność.
2) Przy sprawdzaniu drugiej własności najczęściej postępujemy tak – wychodzimy z jednej strony, majstrujemy tak, by wyszła nam druga strona równania.
Jak sobie zapisaliśmy, a = (x1, y1), a b = (x2, y2). Jedziemy:
ρ (a, b) = ρ ((x1, y1), (x2, y2))
Już sobie „znormalizowaliśmy” zadanie, rozpiszmy, jak to wygląda dalej:
ρ ((x1, y1), (x2, y2)) = |x1 – x2| + |y1 – y2|
Zajmijmy się pierwszym „członem” powyższej sumy:
| x1 – x2|
Możemy przed nawias wyłączyć liczbę (-1)
|(-1) (- x1 + x2)|
(bo zauważmy, że jak z powrotem pomnożymy -1 przez nawias, to wyjdzie nam pierwotne wyrażenie, więc nic złego nie robimy).
Z własności wartości bezwzględnej ( |a * b| = |a| * |b| ) i po zamianie kolejności w drugim nawiasie:
|-1| * |x2 – x1|
Wartość bezwzględna z wartości ujemnej to po prostu rozwalenie minusa:
1 * |x2 – x1|
co po prostu jest równe:
|x2 – x1|
Więc możemy z całą pewnością zapisać:
|x1 – x2| = |x2 – x1|
Więc w naszej sumie możemy się tak popisać:
Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
7/10
|x1 – x2| + |y1 – y2| = |x2 – x1| + |y1 – y2|
Zróbmy podobny numer w drugim „członie”:
|x2 – x1| + |y1 – y2| = |x2 – x1| + |y2 – y1|
Dobra, teraz pokusimy się o kontrowersyjne (lepiej nie piszcie tak na kolokwium, tylko gdzieś z boku, nieoficjalnie, bo nie jestem pewien całkowitej poprawności tego typu zapisu) rzeczy, czyli hmmm... liczby z równania będziemy wsadzać do funkcji. Zauważmy, korzystając z krzywych kresek z połowy poprzedniej kartki, że:
|x2 – x1| + |y2 – y1| = ρ ((_, _), (_, _))
Jest to po prostu takie bezczelne odwrócenie zapisu funkcji. Czyli:
|x2 – x1| + |y2 – y1| = ρ ((x2, y2), (x1, y1))
A to jest nic więcej, jak:
ρ ((x2, y2), (x1, y1)) = ρ (b, a)
A ponieważ szliśmy z jednej strony równania i doszliśmy do drugiej strony, więc zapisujemy: ρ (a, b) = ρ (b, a)
Zalecam jednak pisanie całego równania w jednym ciągu, głośno myśląc nad tym, co wypisałem powyżej. Więc dowód na to powinniśmy tak zapisać:
ρ (a, b) = ρ ((x1, y1), (x2, y2)) = |x1 – x2| + |y1 – y2| = |x2 – x1| + |y2 – y1| =
= ρ ((x2, y2), (x1, y1)) = ρ (b, a)
Koniec dowodu, ale teraz będzie najgorsze.
3) Musimy sprawdzić tzw. nierówność trójkąta. Czyli
ρ(x, z) <= ρ(x, y) + ρ(y, z)
By się nam zbytnio nie pomyliło, zapiszmy to sobie w postaci:
ρ(a, c) <= ρ(a, b) + ρ(b, c)
Załóżmy, że c to taka para: (x3, y3)
Ło Jezu, to wygląda okropnie... ale z dodatkową własnością, czyli znajomością takiej
„podstawowej” nierówności trójkąta w wart. bezwględnej:
|a + b| <= |a| + |b|
Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
8/10
damy radę!
Najgorzej jest zacząć, a więc – pobadajmy lewą stronę nierówności:
ρ(a, c)
To będzie równe, przy wiedzy, że a = (x1, y1), a c = (x3, y3):
ρ(a, c) = ρ((x1, y1), (x3, y3))
co, już bez rysowania kresek, wiemy, że jest równe:
ρ((x1, y1), (x3, y3)) = |x1 – x3| + |y1 – y3|
Przypatrzmy się pierwszemu członowi sumy.
Załóżmy, że idziemy obrobić kiosk, a pani z kiosku wyszła na papierosa 100 metrów dalej i nas na pewno nie złapie. Pomyślimy: „A, zwinę sobie gumki” (z czego zakładam, że pojęcie
„gumki” jest znane). No dobra, podchodzimy, nikt nie patrzy – i zapierdalamy tuż przy okienku paczkę wyżej wspomnianych gumek. Jednak po kilku sekundach sobie nagle uśmiadomimy: „Po cholerę mi te gumki, przecież nie mam nawet jak ich użyć”, albo „O Matko Przenajświętsza, cóż ja uczyniłem”, więc oddajemy gumki w miejscu, w który były, odchodzimy, a pani z kiosku się nie skapowała. Z fizycznego (i rachunkowego) punktu widzenia – nic się nie stało, gumki może i na chwilę zabraliśmy, ale po sekundach oddaliśmy. My zrobimy podobnie, tylko będziemy obracać się wokół bardziej przyzwoitych liczb.
Pierwszy człon jest równy:
|x1 – x3|
A ja tak brutalnie zapierdolę sobie, ni stąd, ni zowąd, jakąś liczbę o nazwie x2:
|x1 – x3 – x2 ...
... ale od razu mnie wezmą wyrzuty sumienia, więc oddam, co zabrałem. Bóg jest jednak mściwy i zapisuje występki:
|x1 – x3 – x2 + x2|
No dobra, zamieszajmy sobie trochę kolejnością:
|x1 – x2 + x2 – x3|
Możemy sobie postawić nawiasy przy różnicach (bo tak nam się podoba.. i tak nie zmienią wartości, bo nigdzie minus nie będzie czaić przed nawiasem):
| (x1 – x2) + (x2 – x3) |
I na razie zostawmy ten pierwszy człon.
Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
9/10
Podobnie postępując, zrobimy w drugim członie (poćwiczcie i sprawdźcie, czy się nie mylę):
| (y1 – y2) + (y2 – y3) |
Czyli całe to:
ρ((x1, y1), (x3, y3)) = | (x1 – x2) + (x2 – x3) | + | (y1 – y2) + (y2 – y3) | ***
Dobra, teraz wiemy na pewno, patrząc na pierwszy człon, że będzie coś takiego następować, z własności wartości bezwględnych:
| (x1 – x2) + (x2 – x3) | <= |(x1 – x2)| + |(x2 – x3)|
Olejmy nawiasy po prawej stronie (nic nie zmieniają) i zróbmy z tego przyzwoity zapis:
| (x1 – x2) + (x2 – x3) | <= |x1 – x2| + |x2 – x3|
Podobnie postąpimy z drugim członem:
| (y1 – y2) + (y2 – y3) | < = |y1 – y2|+ |y2 – y3|
Mamy takie coś, zwane układem dwóch nierówności:
| (x1 – x2) + (x2 – x3) | <= |x1 – x2| + |x2 – x3|
| (y1 – y2) + (y2 – y3) | < = |y1 – y2|+ |y2 – y3|
I teraz również kontrowersyjna rzecz... a, dodajmy te nierówności stronami, wszystko jest większe od zera, więc nie powinno być nic złego:
| (x1 – x2) + (x2 – x3) | + | (y1 – y2) + (y2 – y3) | <= |x1 – x2| + |x2 – x3| + |y1 – y2|+ |y2 – y3|
Spójrzmy na tę potworną lewą stronę równania. Ale, gdzieś tu na stronie postawiłem trzy gwiazdki przy którymś równaniu. Zauważmy, że przecież lewa strona to
ρ((x1, y1), (x3, y3)) , czyli ρ (a, c)
A prawa strona? Patrzmy:
|x1 – x2| + |x2 – x3| + |y1 – y2|+ |y2 – y3|
Zamieńmy se gdzieś tam kolejność i popatrzmy, co to jest:
|x1 – x2| + |y1 – y2| + |x2 – x3| + |y2 – y3|
ρ((x1, y1), (x2, y2)) = ρ(a, b)
ρ((x2, y3), (x2, y3)) = ρ(b, c)
Autor: vbx
WIMiI
Informatyka 2008
Algebra liniowa/Przestrzenie metryczne
10/10
Czyli:
ρ (a, c) <= ρ(a, b) + ρ(b, c)
Czyli to, co mieliśmy wykazać. Hura, otwieramy flaszkę i „najebujemy się”. W najbliższym czasie spróbuję napisać, jak rysuje się okrąg w takich przestrzeniach metrycznych. A osobiście mam nadzieję, że w czymś pomogłem, a swoją głupotą co najwyżej poprawiłem humor, a nie do końca zażenowałem.
pj
poap[at]interia.pl
Linki do innych pomocy (być może naukowych):
Autor: vbx
WIMiI
Informatyka 2008