|
|
| (Nie pokazano 8 pośrednich wersji utworzonych przez tego samego użytkownika) |
| Linia 1: |
Linia 1: |
| ==Definicja przestrzeni wektorowej==
| | <quiz> |
| | Język rekurencyjny to |
| | <wrongoption>język akceptowany przez pewną maszynę Turinga</wrongoption> |
| | <rightoption>język akceptowany przez pewną maszynę Turinga z własnością stopu</rightoption> |
| | <wrongoption>zbiór słów nad pewnym alfabetem</wrongoption> |
| | <wrongoption>skończony zbiór słów nad pewnym alfabetem</wrongoption> |
| | <wrongoption>zbiór słów, który można wylistować uruchamiając pewną maszynę Turinga</wrongoption> |
| | </quiz> |
|
| |
|
| Na początku tego wykładu wprowadzimy pojęcie przestrzeni wektorowej - najważniejszej struktury, którą zajmuje się algebra liniowa.
| | <quiz> |
| | W maszynie Turinga funkcja przejścia |
| | <wrongoption>może mieć nieskończenie wiele wartości</wrongoption> |
| | <wrongoption>określona jest dla przeliczalnej liczby argumentów</wrongoption> |
| | <rightoption>może być funkcją częściową</rightoption> |
| | <wrongoption>określona jest na konfiguracjach maszyny</wrongoption> |
| | <wrongoption>dla każdej pary <math>(stan, znak)</math> posiada inną wartość</wrongoption> |
| | </quiz> |
|
| |
|
| {{definicja|1.1 [Przestrzeń wektorowa]|def 1.1|
| | <quiz> |
| Niech <math>\displaystyle\V</math> będzie zbiorem niepustym wyposażonym w działanie wewnętrzne - dodawanie. Dane jest także ciało <math>\displaystyle\\mathbb K</math> oraz działanie zewnętrzne, tak zwane mnożenie zewnętrzne z lewej strony, będące odwzorowaniem zbioru <math>\displaystyle\\mathbb K \times V</math> w zbiór <math>\displaystyle\V</math>. Wartość tego odwzorowania na parze <math>\displaystyle\(\lambda ,v)\in \mathbb K\times V</math> oznaczamy przez <math>\displaystyle\\lambda\cdot v</math>. Występującą tu kropkę najczęściej pomijamy.
| | W <math>k</math>-taśmowej maszynie Turinga funkcja przejścia |
| | określona jest dla całych konfiguracji |
| | <rightoption>przekształca <math>(k+1)</math>-krotki w <math>(2k+1)</math>-krotki</rightoption> |
| | <wrongoption>zależy od numerów klatek czytanych przez <math>k</math> głowic</wrongoption> |
| | <wrongoption>przekształca <math>(k+1)</math>-krotki w <math>(k+2)</math>-krotki</wrongoption> |
| | <wrongoption>nie może być funkcją częściową</wrongoption> |
| | </quiz> |
|
| |
|
| Mówimy, że struktura składająca się ze zbioru <math>\displaystyle\V</math>, ciała <math>\displaystyle\\mathbb K</math> oraz dwóch powyższych działań jest ''przestrzenią wektorową'', jeśli spełnionych jest pięć poniższych warunków, zwanych aksjomatami przestrzeni wektorowej:
| | <quiz> |
| | Symulacja maszyny <math>k</math>-taśmowej na maszynie z jedną taśmą |
| | <wrongoption>wymaga kwadratowego zwiększenia pamięci roboczej</wrongoption> |
| | <rightoption>jest wykonalna przy kwadratowym zwiększeniu czasu</rightoption> |
| | <wrongoption>może być przeprowadzona w tym samym czasie</wrongoption> |
| | <rightoption>może być przeprowadzona w tej samej pamięci</rightoption> |
| | </quiz> |
|
| |
|
| V1) Zbiór <math>\displaystyle\V</math> z dodawaniem jest grupą przemienną,
| | <quiz> |
| | Jeśli maszyna niedeterministyczna <math>M</math> o złożoności <math>O(n^2)</math> na wejściu ma słowo <math>x\in L(M)</math>, to |
| | <wrongoption>stopnie wierzchołków drzewa obliczeń nie są ograniczone przez stałą i są ograniczone przez <math>O(n^2)</math></wrongoption> |
| | <rightoption>długości wszystkich ścieżek są ograniczone przez <math>O(n^2)</math></rightoption> |
| | <rightoption>niektóre wierzchołki w drzewie mogą być identyczne</rightoption> |
| | <rightoption>możliwe jest, że wszystkie ścieżki mają długość <math>O(n)</math></rightoption> |
| | </quiz> |
|
| |
|
| V2) Dla każdych <math>\displaystyle\\lambda\, \mu \in \mathbb K</math> i dla każdego <math>\displaystyle\v\in V</math> zachodzi równość <math>\displaystyle\\lambda(\mu v)=(\lambda\mu )v</math>.
| | <quiz> |
| | Maszyna niedterministyczna dla danego słowa wejściowego <math>x</math> na <math>3/4</math> możliwych ścieżek obliczeń zatrzymuje się po <math>O(n)</math> krokach, na pozostałych nie zatrzymuje się. Maszyna ta |
| | <wrongoption>ma własność stopu</wrongoption> |
| | <rightoption>nie ma własności stopu</rightoption> |
| | <wrongoption>ma złożoność czasową <math>O(n)</math></wrongoption> |
| | <rightoption>akceptuje <math>x</math></rightoption> |
| | <wrongoption>nie akceptuje <math>x</math></wrongoption> |
| | </quiz> |
|
| |
|
| V3) Dla każdych <math>\displaystyle\\lambda\, \mu \in \mathbb K</math> i dla każdego <math>\displaystyle\v\in V</math> zachodzi równość <math>\displaystyle\(\lambda +\mu )v=\lambda v +\mu v</math>.
| | <quiz> |
| | | Symulacja maszyny niedeterministycznej przez deterministyczną |
| V4) Dla każdego <math>\displaystyle\\lambda \in \mathbb K</math> i każdych <math>\displaystyle\v,w\in V</math> zachodzi równość <math>\displaystyle\\lambda (v+w)= \alpha v +\alpha w</math>.
| | <wrongoption>wymaga kwadratowego zwiększenia czasu</wrongoption> |
| | | <rightoption>wymaga wykładniczego zwiększenia czasu</rightoption> |
| V5) Dla każdego <math>\displaystyle\v\in V</math> zachodzi równość <math>\displaystyle\1\cdot v= v</math>.
| | <wrongoption>nie wymaga zwiększenia rzędu złożoności czasowej</wrongoption> |
| | | <wrongoption>nie jest możliwa na maszynie jednotaśmowej</wrongoption> |
| }}
| | <wrongoption>nie jest możliwa na maszynie dwutaśmowej</wrongoption> |
| | | </quiz> |
| W pierwszym aksjomacie najczęściej żąda się, tak jak to zrobiliśmy, aby grupa była przemienna, choć przemienność tej grupy jest konsekwencją pozostałych warunków. Proponujemy, aby czytelnik sam sprawdził ten fakt. Aksjomaty V2)- V5) są w definicji niezbędne. Proponujemy, aby czytelnik sprawdził to, znajdując przykład struktury, dla której spełnione są wszystkie warunki oprócz <math>\displaystyle\V2)</math>, następnie przykład struktury, dla której spełnione są wszystkie warunki
| |
| oprócz warunku V3), etc. Własność V3) nazywa się łącznością mieszaną, własność V4) - rozdzielnością mnożenia zewnętrznego względem dodawania w ciele i wreszczcie własność V4) - rozdzielnością mnożenia zewnętrznego względem dodawania wewnętrznego.
| |
| | |
| Jeśli spełnione są wszystkie powyższe aksjomaty, to mówimy także, że <math>\displaystyle\V</math> jest przestrzenią wektorową nad ciałem <math>\displaystyle\\mathbb K</math>. Elementy przestrzeni <math>\displaystyle\V</math> nazywamy wektorami, zaś elementy ciała <math>\displaystyle\\mathbb K</math> nazywamy skalarami.
| |
| | |
| Zauważmy najpierw pewne elementarne własności przestrzeni wektorowych.
| |
| | |
| {{twierdzenie|1.2 |tw 1.2|
| |
| Niech <math>\displaystyle\V</math> będzie przestrzenią wektorową nad ciałem <math>\displaystyle\\mathbb K</math>. Wtedy dla każdego <math>\displaystyle\v\in V</math> i każdego <math>\displaystyle\\lambda \in \mathbb K</math> zachodzą równości:
| |
| | |
| | |
| <center><math>\displaystyle\0\cdot v=0,</math></center>
| |
| | |
| | |
| <center><math>\displaystyle\\lambda \cdot 0=0,</math></center>
| |
|
| |
| | |
| <center><math>\displaystyle\(-1)v=-v,</math></center>
| |
| | |
| | |
| <center><math>\displaystyle\\lambda \cdot v= 0 \Longrightarrow \lambda =0 \{\rm lub}\ v=0.</math></center>
| |
| | |
| }}
| |
| | |
| {{uwaga|1.3 |uw 1.3|
| |
| W pierwszej z powyższych równości <math>\displaystyle\0</math> z lewej strony jest zerem w ciele, zaś <math>\displaystyle\0</math> z prawej strony jest zerem w przestrzeni wektorowej. W drugiej równości oba <math>\displaystyle\0</math> są zerami w przestrzeni wektorowej.
| |
| | |
| }}
| |
| | |
| {{dowod|||
| |
| Dowód trzech pierwszych z powyższych własności jest analogiczny do odpowiednich części dowodu Twierdzenia 2.2. z Wykładu 1. Dla dowodu czwartej własności załóżmy, że <math>\displaystyle\\lambda \ne 0</math> i <math>\displaystyle\\lambda v=0</math>. Pomnóżmy obie strony przez <math>\displaystyle\\lambda ^{-1}</math>. Otrzymujemy stąd równość <math>\displaystyle\v=0</math>.
| |
| }}
| |
| | |
| Podamy teraz kilka przykładów przestrzeni wektorowych.
| |
| | |
| {{przyklad|1.4 |przy 1.4|
| |
| Dowolny zbiór jednoelementowy jest przestrzenią wektorową nad dowolnym ciałem. Jedyny element takiego zbioru jest zerem w tej przestrzeni. Taką przestrzeń nazywamy przestrzenią zerową.
| |
| }}
| |
| | |
| {{przyklad|1.5 |przy 1.5|
| |
| Każde ciało jest przestrzenią wektorową nad samym sobą.
| |
| | |
| Ogólniej, jeśli <math>\displaystyle\\mathbb K</math> jest ciałem, to iloczyn kartezjański <math>\displaystyle\\mathbb K ^n</math>, <math>\displaystyle\n\in \mathbb N</math>, ma naturalną strukturę przestrzeni wektorowej nad ciałem <math>\displaystyle\\mathbb K</math>. Dodawanie w <math>\displaystyle\\mathbb K ^n</math> definiujemy następująco
| |
| | |
| | |
| <center><math>\displaystyle\(a_1,...,a_n) +(b_1,...,b_n) =(a_1+b_1,..., a_n +b_n),</math></center> | |
| | |
| | |
| zaś mnożenie zewnętrzne dane jest formułą
| |
| | |
| | |
| <center><math>\displaystyle\\lambda (a_1,...,a_n)=(\lambda a_1,...,\lambda a_n).</math></center> | |
| | |
| | |
| Bezpośrednim i łatwym rachunkiem można sprawdzić, że tak zdefiniowana struktura na <math>\displaystyle\\mathbb K ^n</math> jest przestrzenią wektorową nad ciałem <math>\displaystyle\\mathbb K</math>.
| |
| }}
| |
| | |
| W kolejnym przykładzie zdefiniujemy strukturę przestrzeni wektorowej na iloczynie kartezjańskim dowolnych przestrzeni wektorowych.
| |
| | |
| {{przyklad|1.6 |przy 1.6|
| |
| Niech <math>\displaystyle\V</math>, <math>\displaystyle\W</math> będą przestrzeniami wektorowymi nad ciałem <math>\displaystyle\\mathbb K</math>. Wtedy iloczyn kartezjański <math>\displaystyle\V\times W</math> ma naturalną strukturę przestrzeni wektorowej nad ciałem <math>\displaystyle\\mathbb K</math>. Istotnie, jeśli zdefiniujemy dodawanie formułą
| |
| | |
| | |
| <center><math>\displaystyle\(v_1,w_1)+(v_2,w_2)=(v_1+v_2, w_1+w_2),</math></center>
| |
| | |
| | |
| dla <math>\displaystyle\v_1, v_2\in V</math> i <math>\displaystyle\w_1, w_2\in W</math>, a mnożenie zewnętrzne formułą
| |
| | |
| | |
| <center><math>\displaystyle\\lambda (v,w)=(\lambda v, \lambda w)</math></center>
| |
| | |
| | |
| dla <math>\displaystyle\\lambda \in\mathbb K</math> i <math>\displaystyle\v\in V</math>, <math>\displaystyle\w\in W</math>, to otrzymujemy strukturę przestrzeni wektorowej (nad ciałem <math>\displaystyle\\mathbb K</math>) na <math>\displaystyle\V\times W</math>.
| |
| }}
| |
| | |
| {{przyklad|1.7 |przy 1.7|
| |
| Załóżmy, że dana jest przestrzeń wektorowa <math>\displaystyle\V</math> nad ciałem <math>\displaystyle\\mathbb K</math> i <math>\displaystyle\X</math> jest dowolnym zbiorem niepustym. Weźmy zbiór wszystkich odwzorowań <math>\displaystyle\f:X\longrightarrow V</math>. Oznaczmy ten zbiór przez <math>\displaystyle\V^X</math>. W zbiorze <math>\displaystyle\V ^X</math> wprowadzamy dodawanie
| |
| | |
| | |
| <center><math>\displaystyle\(f+g)(x)=f(x)+g(x)</math></center>
| |
| | |
| | |
| dla każdych <math>\displaystyle\f,g\in V^X</math> i dla każdego <math>\displaystyle\x\in X</math>. Mnożenie
| |
| zewnętrzne definiujemy formułą
| |
| | |
| | |
| <center><math>\displaystyle\(\lambda f)(x)=\lambda (f(x))</math></center>
| |
| | |
| | |
| dla <math>\displaystyle\\lambda \in\mathbb K</math>, <math>\displaystyle\f\in V</math> i <math>\displaystyle\x\in X</math>.
| |
| | |
| Tak określone działania definiują , co łatwo sprawdzić, strukturę przestrzeni wektorowej na <math>\displaystyle\V^X</math> nad <math>\displaystyle\\mathbb K</math>.
| |
| | |
| Jako szczególny przypadek możemy wziąć zbiór wszystkich ciągów nieskończonych o wartościach w dowolnej przestrzeni wektorowej <math>\displaystyle\V</math>. Zbiorem <math>\displaystyle\X</math> jest tutaj zbiór liczb naturalnych <math>\displaystyle\\mathbb N</math>.
| |
| | |
| Jeśli za <math>\displaystyle\X</math> weźmiemy zbiór <math>\displaystyle\\{1,...,n\}</math>, a <math>\displaystyle\V</math> jest dowolną przestrzenią wektorową, to otrzymamy przestrzeń ciągów o długości <math>\displaystyle\n</math> i wyrazach w <math>\displaystyle\V</math>.
| |
| | |
| Jeśli za <math>\displaystyle\X</math> przyjmiemy pewien przedział w zbiorze liczb rzeczywistych, to zbiór wszystkich funkcji określonych na tym przedziale i o wartościach w zbiorze liczb rzeczywistych jest przestrzenią wektorową.
| |
| | |
| }}
| |
| | |
| {{przyklad|1.8 |przy 1.8|
| |
| W szkole wprowadza się pojęcie wektora swobodnego na płaszczyźnie. Zbiór wszystkich takich wektorów ze znanymi ze szkoły dodawaniem (przez zastosowanie reguły równoległoboku) i mnożeniem wektorów przez liczby rzeczywiste stanowi przykład przestrzeni wektorowej nad ciałem <math>\displaystyle\\mathbb R</math>. Podobnie ma się rzecz ze zbiorem wektorów swobodnych w trójwymiarowej przestrzeni fizycznej.
| |
| | |
| Można też rozumować tak (pomijając pojęcie wektora swobodnego). Rozważmy płaszczyznę (lub trójwymiarową przestrzeń) z ustalonym punktem (np. początkiem pewnego układu współrzędnych). Bierzemy zbiór wszystkich wektorów zaczepionych w tym punkcie. Wprowadzamy dodawanie wektorów i mnożenie przez liczbę rzeczywistą tak, jak się to robi w szkole. Tak otrzymana struktura jest przestrzenią wektorową nad <math>\displaystyle\\mathbb R</math>.
| |
| | |
| Jeśli płaszczyzna (lub trójwymiarowa przestrzeń fizyczna) jest wyposażona w układ współrzędnych, to tak otrzymaną przestrzeń wektorów można utożsamiać z <math>\displaystyle\\mathbb R ^2</math> (w przypadku płaszczyzny) lub z <math>\displaystyle\\mathbb R ^3</math> (w przypadku trójwymiarowej przestrzeni fizycznej).
| |
| }}
| |
| | |
| Przestrzeń wektorową <math>\displaystyle\V</math> nad ciałem liczb zespolonych nazywamy przestrzenią wektorową zespoloną. Przestrzeń wektorową nad ciałem liczb rzeczywistych nazywamy przestrzenią wektorową rzeczywistą. Każda przestrzeń wektorowa zespolona jest automatycznie przestrzenią wektorową rzeczywistą (z mnożeniem zewnętrznym będącym zawężeniem do <math>\displaystyle\\mathbb R\times V</math> mnożenia zewnętrznego przez liczby zespolone).
| |
