1
Diszkrét matematika II., 4. el®adás Skalárszorzat, norma, szög, távolság
Dr. Takách Géza NyME FMK Informatikai Intézet
[email protected] http://inf.nyme.hu/takach/ 2005. március 1 A téma jelent®sége
Ha valamiféle geometriát szeretnénk értelmezni a vektorainkon vagy pontjainkon, akkor nem elég egy vektortér, kell valamilyen skalárszorzatot is rögzítenünk. Nem mindig a standard skalárszorzat felel meg a céljainknak. Néha nem is egy skalárszorzatból indulunk ki, csak valamilyen módon távolságot de niálunk. A távolságfogalomnak nagy szerepe van a hibajavító ill. hibajelz® kódolásoknál. Ott szokás két egyenl® hosszú bitsorozat távolságán az eltér® bitek számát érteni. Ekkor ha bármely két lehetséges elküldött üzenet távolsága legalább d, akkor a címzett észlel minden olyan hibát, amikor legfeljebb d 1 bit sérül meg. S®t, ki is tud javítani minden olyan hibát, ahol d=2-nél kevesebb bit sérül meg! Gyakorlati célok
Ezen el®adáson, és a hozzá kapcsolódó gyakorlaton való
aktív részvétellel Ön képes lesz
az n-komponens¶ valós vektorok körében kiszámolni egy vektor hosszát, két vektor szögét és két pont távolságát akár a standard, akár valamely szendvicsmátrixszal adott skalárszorzat esetén; ellen®rizni, hogy egy véges halmazon adott kétváltozós függvény vajon távolságfüggvénynek tekinthet®-e; úgy megadni egy függvényt egy véges halmazon, hogy az távolságfüggyvény legyen és el®re megadott értékeket vegyen fel;
Elméleti, fogalmi célok
Ezen el®adáson, és a hozzá kapcsolódó gyakorlaton való
megérti a skalárszorzatból származtatott norma és távolságfogalmat; megérti, hogy más skalárszorzathoz más norma ill. távolság tartozik; tudatára ébred, hogy nem egzotikus módon is megadható távolságfüggvény, és hogy ennek esetleg semmi köze nincs skalárszorzathoz.
Szükséges fogalmak és módszerek korábbról
aktív részvétellel Ön
vektortér, bázis; középiskolás skalárszorzat-fogalom; bilineáris függvény, szimmetria, de nitség; Gram-Schmidt ortoganalizáció;
2 Euklideszi terek
De níció.
A skalárszorzat szimmetrikus, pozitív de nit bilineáris függvény:
= (x + y ) z = (x) z = x= 6 0 ! x z
De níció.
x z + y z; (x z ); x x > 0: z x;
Euklideszi téren skalárszorzattal ellátott vektorteret értünk.
Norma Euklideszi terekben
De níció. Tétel. (N1) (N2) (N3)
Egy Euklideszi térben egy x vektor hosszán (normáján, abszolút értékén) az jjxjj =
px x számot értjük.
A hossz az alábbi tulajdonságokkal rendelkezik:
jjxjj 0 és jjxjj = 0 , x = 0; jjxjj = jj jjxjj; jjx + zjj jjxjj + jjzjj.
Bizonyítás.
(N1) (és egyben a de níció jósága) a skalárszorzat pozitív deinitségén múlik.
(N2) a skalárszorzat homogenitásán múlik.
}
(N3) kés®bb. Szögfogalom Euklideszi terekben
Láttuk, hogy ha van skalárszorzat, akkor van mer®legességfogalom. A norma segítségével szögfogalmat is de niálunk. A motiváció a skalárszorzat középiskolás de níciója:
jj jj jjzjj cos :
x z= x
De níció.
Egy Euklideszi tér x; z
6= 0 vektorai által közbezárt szögön azt a 0 szöget értjük, amelyre xz cos = jjxjj jjzjj :
A de nició helyessége következik a kés®bb következ® CSB-egyenl®tlenségb®l. Ortonormált bázis
De níció. Az e1 ; : : : ; en vektorok ortonormált rendszert alkotnak, ha ei ej = ij (Kronecker-delta). Azaz minden vektor hossza egy, és a vektorok páronként mer®legesek. Ha az ei vektorok egyben bázist is alkotnak, akkor ortonormált bázisról beszélünk. A Gram-Schmidt ortogonalizációval kaphatunk ortonormált bázist egy tetsz®leges bázisból kiindulva. Normált terek
Tegyük fel, hogy egy olyan vektortérben vagyunk, amely nem rendelkezik skalárszorzattal. Ekkor is adható értelmes hosszfogalom a hossz Euklideszi térbeli hossz tulajdonságai alapján.
De níció. Egy valós vektorteret normált térnek nevezünk, ha értelmezve van rajta egy rendelkezik az alábbi tulajdonságokkal:
jj jj : V ! R norma, amely
3 (N1) (N2) (N3)
jjxjj 0 és jjxjj = 0 , x = 0; jjxjj = jj jjxjj; jjx + zjj jjxjj + jjzjj.
Minden Euklideszi tér normált, de fordítva nem feltétlenül. Távolságfogalom normált terekben
Ahogyan a skalárszorzatból normát értelmeztünk, a normából megalkotjuk a távolságfogalmat. Így minden normált térben, speciálisan Euklideszi terekben is beszélhetünk távolságról.
De níció. Tétel.
Egy normált térben az x és z pont távolságán az r(x; z ) = jjx
z
jj számot értjük.
A távolság rendelkezik az alábbi tulajdonságokkal
(M1) r (x; z )
0 és és r(x; z) = 0 , x = z;
(M2) r (x; z ) = r (z; x); (M3) r (x; z )
Bizonyítás.
r(x; y) + r(y; z).
}
Mindegyik tulajdonság következik az azonos számú (N) tulajdonságból.
Metrikus terek
Tegyük fel, hogy egy olyan vektortérben vagyunk, amely nem rendelkezik normafogalommal. Ekkor is adható értelmes távolságfogalom a norma normált térbeli tulajdonságai alapján.
De níció.
Egy H halmazt metrikus térnek nevezünk, ha értelmezve van rajta egy H amely rendelkezik az alábbi tulajdonságokkal: (M1) r(x; z ) 0 és és r(x; z ) = 0
H ! R távolság (metrika),
, x = z;
(M2) r(x; z ) = r(z; x); (M3) r(x; z ) r(x; y ) + r(y; z ). Minden normált tér egyben metrikus tér is, de fordítva nem.
Tétel.
(Cauchy-Schwarz-Bunyakovszkij-egyenl®tlenség) Egy Euklideszi tér bármely x és z vektorára fenáll az
jx zj jjxjj jjzjj egyenl®tlenség. Egyenl®ség pontosan akkor teljesül, ha x és z lineárisan összefügg®ek.
Bizonyítás.
A két oldalt egy ortonormál bázis szerinti koordinátákkal felírva, és négyzetre emelve a következ® lesz: 2 (x1 z1 + : : : + x z )
n n
Átrendezve: 0
(x21 + : : : + x2n )(z12 + : : : + zn2 ):
X
ii<jn
i j
(x z
xj zi )2 :
Ez a négyzetösszeg nemnegatív, és pontosan akkor nulla, ha x és z koordinátái arányosak, azaz egymás konstansszorosai. }
4 Következmények
Az (N3) Háromszög-egyenl®tlenség igazolása.
Az jjx + z jj jjxjj + jjz jj összefüggést kell igazolni. Négyzetre emelve:
(x x + z z)2 jj jj jjxjj2 + 2jjxjj jjzjj + jjzjj2 x z jjxjj jjz jj
(x + z ) (x + z ) 2 x +2 x z+ z 2
jj jj
Ez pedig következik a CSB-egyenl®tlenségb®l.
}
A CSB-egyenl®tlenségb®l az is következik, hogy a szögfogalom jól értelmezett, hisz a jobb oldallal végigosztva kapjuk, hogy j cos j 1. Mivel a cos függvény bijektíven képezi le a [0; ] intervallumot a [ 1; 1] intervallumra, így a két vektor szöge egyértelm¶en de niált. Összefoglalás
Az el®adás elején de niáltuk a skalárszoratot ill. az Euklideszi tereket. A skalárszorzatból norma- és szögfogalmat származtattunk. Az Euklideszi terek normájának legfontosabb tulajdonságait axiómának tekintve értelmeztük a normált vektortér fogalmát, és csupán ezekb®l származtattuk a távolságfogalmat. Hasonlóan az el®z® elvhez, a normált terek távolságfüggvényének legfontosabb tulajdonságait axiómának tekintve értelmeztük a metrikus tér fogalmát. A metrikus terekben már nem követeltünk meg vektortérstruktúrát, csupán a tér pontnak nevezett elemeinek kell tudnunk a távolságát. A származtatáskor a kiindulási tér tulajdonságai implikálják a származtatott tér megfelel® tulajdonságait. Az egyetlen nehézséget a normára vonatkozó háromszög-egyenl®tlenség jelentette, amit a CSB-egyenl®tlenségb®l vezettünk le. Ellen®rz® kérdések
1. Mit értünk azon, hogy a skalárszorzat pozitív de nit? 2. Hogyan de niáljuk a normát illetve a szöget Euklideszi terekben? 3. Mit értünk ortonormált bázison és milyen vektorterekben van értelme err®l beszélni? 4. Mondja ki a távolságaxiómákat! 5. Hogyan szól a CSB-egyenl®tlenség, és hol használjuk?
5 M¶veletigény a lineáris algebrai számításokban
A lineáris algebrai tanulmányaink végén ismételjük át a legfontosabb feladatokat, és adjuk meg m¶veletigényüket. A m¶veletigény számításakor a szorzások számát gyeljük az input méretének függvényében, mert a szorzás végrehajtása számítógépen ugyanúgy nagyságrenddel nagyobb ideig tart, mintha papíron végeznénk el. 1. Egyenletrendszer megoldása Jordan-eliminációval. 2. Egyenletrendszer megoldása Gauss-eliminációval. 3. Determinánsszámítás de níció szerint. 4. Determinánsszámítás eliminációval. 5. Determinánsszámítás kifejtési tétellel. 6. Mátrixok szorzása. 7. Mátroxok invertálása el®jeles aldeterminánsokkal. 8. Mátrixok invertálása eliminációval. 9. Egyenletrendszer magoldása Cramer-szabállyal. 10. Függetlenség eldöntése. 11. Rang számítása. 12. Lineáris leképezés végrehajtása mátrixszorzással. 13. Mátrixok regularitásának eldöntése. 14. Sajátértékek kiszámítása. 15. Egy sajátértékhez tartozó sajátvektorok meghatározása. 16. Bilineáris függvények végrehajtása. 17. Egy bilineáris függvényre vonatkozóan ortogonális bázis keresése. 18. Kvadratikus alakba helyettesítés. 19. Kvadratikus alakde nitségének eldöntése ortogonalizációval. 20. Kvadratikus alakde nitségének eldöntése eliminációval. 21. Kvadratikus alak de nitségének eldöntése f®minorokkal.
