1
Első zárthelyi dolgozat megoldásai biomatematikából* „A” verzió Elméleti kérdések: E1. Mikor nevezünk egy gráfot gyengén és mikor erősen összefüggőnek? Adjon példát gyengén összefüggő, de erősen nem összefüggő gráfra. (25 pont) Egy gráf gyengén összefüggő, ha bármely két különböző csúcsa között vezet a gráf éleiből álló út. Egy gráf erősen összefüggő, ha bármely két különböző csúcsa között vezet a gráf éleiből álló éllánc. Példa: E2. Adja meg két oszlopvektor skaláris szorzatának definícióját. Adjon példát olyan oszlopvektorokra, melyeknek létezik és olyanokra is, melyeknek nem létezik skaláris szorzata. Indoklás is szükséges! Mi az R-ben a mátrixszorzás műveleti jele? (25 pont) ⎡ a1 ⎤ ⎡ b1 ⎤ ⎢a ⎥ ⎢b ⎥ ⎢ 2⎥ ⎢ 2⎥ ⎢.⎥ ⎢.⎥ Legyen a = ⎢ ⎥ és b = ⎢ ⎥ két ugyanannyi elemből álló oszlopvektor (azt is mondhatnánk, ⎢.⎥ ⎢.⎥ ⎢.⎥ ⎢.⎥ ⎢ ⎥ ⎢ ⎥ ⎣⎢a n ⎦⎥ ⎣⎢bn ⎦⎥
hogy ugyanannyi sorból állók). Ekkor skaláris szorzatukon az a1 ⋅ b1 + a 2 ⋅ b2 + ... + a n ⋅ bn T
számot (skalárt) értjük. Ez megegyezik az a b mátrixszorzattal, mert az 1x1-es mátrixokat ⎡1⎤ ⎡ 2⎤ azonosítjuk a skalárokkal. Például az ⎢ ⎥ és ⎢ ⎥ oszlopvektorok skaláris szorzata ⎣−1⎦ ⎣1 ⎦ 1 ⋅ 2 + (−1) ⋅ 1 = 1 . Ha az elemek száma nem egyenlő, akkor a vektorok skaláris szorzata nincs ⎡1 ⎤ ⎡1⎤ értelmezve, mint pl. az ⎢ ⎥ és ⎢⎢1 ⎥⎥ vektorok esetében. ⎣−1⎦ ⎢⎣2⎥⎦
A mátrixszorzás műveleti jele R ben %*%.
*
Zh ponthatárok: 50-62 2-es, 63-75 3-as, 76-88 4-es, 89- 5-ös. A minimum elméletből is, feladatokból is 25-25 pont.
2 Feladatok: F1. Az x és y ismeretlen mennyiségek eleget tesznek az alábbi egyenlőtlenségeknek: 2x 2y
≥
y
≥
x
x + 4 y ≤ 30
Írja át ezt mátrixalakú olyan egyenlőtlenségbe, ami a tanult módon R-ben már megoldható. Ábrázolja a feltételeknek eleget tevő pontok tartományát síkbeli koordinátarendszerben, majd találja meg azt a megoldást, melyre 2 x + y maximális. Mi a neve annak az R-beli csomagnak (azaz library-nek) és ezen belül annak az eljárásnak, amivel ilyen feladat megoldását ki lehet számoltatni? (25 pont) Először is átalakítjuk az egyenlőtlenségeket úgy, hogy mindegyik ≥ formájú legyen és az ismeretlenek mind a bal oldalra kerüljenek, a jobb oldalon csak konstansok maradjanak: 2x − y ≥ 0 − x + 2y ≥ 0 . − x − 4 y ≥ − 30 Vegyük észre, hogy ennek nagyon hasonlít a formája a lineáris egyenletrendszerekéhez. Ugyanúgy kell ezt is mátrixalakúvá átírni: ⎡ 2 − 1⎤ ⎡ 0 ⎤ ⎢− 1 2 ⎥ ⋅ ⎡ x ⎤ ≥ ⎢ 0 ⎥. ⎥ ⎢ y⎥ ⎢ ⎥ ⎢ ⎢⎣− 1 − 4⎥⎦ ⎣ ⎦ ⎢⎣− 30⎥⎦
Felrajzoljuk az egyenlőtlenségek határoló egyeneseit, és pl. próbálgatással, értékek behelyettesítésével eldöntjük, hogy az adott egyenlőtlenség melyik félsíkra vonatkozik. Végül ezeknek a félsíkoknak a metszetei adják a lehetséges megoldások halmazát. Az ábrán ez a téglamintázatú háromszög. Ennek a határa is beletartozik, ui. az egyenlőtlenségekben az egyenlőségek is megengedettek.
y = −2 x + 25 y = 2x y = 0,5 x 7,5 5
y = −0,25 x + 7,5
1
1
10
3 Az optimális megoldás keresésekor ábrázoljuk a 2 x + y = c egyenletű egyeneseket különböző c értékek mellett. Ha ezeket az egyeneseket felfelé mozgatjuk, akkor c nő, ha lefelé, akkor csökken (ez onnan látszik, hogy c éppen az egyenes és az y tengely metszéspontjában lévő szám. Ha ui. x=0, akkor y=c.) Az ábra szerinti vastag fekete egyenesnek felel meg a megoldási tartományon a legnagyobb c érték, itt van tehát 2 x + y maximuma. (Elég csak a tartomány csúcspontjain áthaladó 2 x + y = c egyenletű egyeneseket vizsgálni, mindig ezek valamelyikében van az optimum.) Az optimális megoldás tehát x = 10, y = 5. R-ben a szükséges csomag neve linprog, a függvényé pedig solveLP. ⎡2 1 ⎤ F2. Határozza meg az A = ⎢ ⎥ mátrix összes sajátértékét és adjon meg minden ⎣1 2 ⎦ sajátértékhez egy-egy sajátvektort. Igaz-e, hogy az A mátrix pozitív szemidefinit? Indokolja is meg a válaszát. Mi a neve annak az R-beli függvénynek, amellyel meghatározhatók egy négyzetes mátrix sajátértékei és sajátvektorai? (25 pont) A sajátvektorok egyenlete det( A − λ ⋅ I ) = 0 , ahol I a megfelelő rendű egységmátrix. Ennek 2−λ 1 alapján most az egyenlet = 0. A determinánst kifejtve a (2 − λ ) 2 = 1 másodfokú 1 2−λ egyenletet kapjuk, melynek megoldásai λ1 = 3 és λ2 = 1 . Ezek lesznek a mátrix keresett sajátértékei. ⎡u ⎤ Ha a mátrix sajátértéke λ és az ehhez tartozó sajátvektor u = ⎢ 1 ⎥ , akkor fennáll az ⎣u 2 ⎦ A ⋅ u = λ ⋅ u mátrixegyenlet. Számításokhoz jobban használható az ezzel ekvivalens ( A − λ ⋅ I ) ⋅ u = 0 alak (gondolják végig az ekvivalenciát). A λ1 = 3 sajátértékhez ez a
⎡− 1 1 ⎤ ⎡ u1 ⎤ ⎡0⎤ ⎢ 1 − 1⎥ ⋅ ⎢u ⎥ = ⎢0⎥ mátrixegyenletet jelenti (ezt is gondolják végig). Az ennek megfelelő ⎣ ⎦ ⎣ 2⎦ ⎣ ⎦ − u1 + u 2 = 0 homogén lineáris egyenletrendszer . A két egyenlet ugyanaz, elég ezért u1 − u 2 = 0 csak az elsővel foglalkozni. Azt kapjuk, hogy u1 = u 2 , ennek végtelen sok megoldása van, az egyik például u1 = 1, u 2 = 1. (Ilyenkor néhány ismeretlennek önkényesen beállítjuk az értékét, a többit pedig ezekből az egyenletek alapján kifejezzük.) A λ1 = 3 sajátértékhez tartozó egyik ⎡1⎤ sajátvektor tehát az ⎢ ⎥ vektor. ⎣1⎦
4 ⎡2⎤ ⎡3⎤ ⎡− 1⎤ (A többi ennek számszorosaként állítható elő, így a ⎢ ⎥, ⎢ ⎥, ⎢ ⎥ vektorok szintén a ⎣2⎦ ⎣3⎦ ⎣− 1⎦ λ1 = 3 sajátértékhez tartozó sajátvektorok.) A λ 2 = 1 sajátértékhez tartozó sajátvektor(ok) u1 + u 2 = 0 ⎡1 1⎤ ⎡ u1 ⎤ ⎡0⎤ homogén lineáris ⎢1 1⎥ ⋅ ⎢u ⎥ = ⎢0⎥ , ez a u + u = 0 ⎣ ⎦ ⎣ 2⎦ ⎣ ⎦ 1 2 egyenletrendszerré írható át. A második egyenlet ugyanaz, mint az első, azt kapjuk, hogy u1 = −u 2 , ennek megoldása például u1 = 1, u 2 = −1. A λ2 = 1 sajátértékhez tartozó egyik ⎡1⎤ sajátvektor tehát az ⎢ ⎥ vektor. ⎣−1⎦
mátrixegyenlete
Egy szimmetrikus mátrix akkor pozitív szemidefinit, ha sajátértékei nemnegatívak. Ez most teljesül, tehát a mátrix pozitív szemidefinit. (A sajátértékek most határozottan pozitívak, ezért mondható, hogy a mátrix pozitív definit is. Ez a megállapítás nem mond ellent annak, hogy a mátrix pozitív szemidefinit.) Most is nagyon ajánlott ellenőrzést végezni, ezért behelyettesítjük az eredményeket a sajátértékek-sajátvektorok kapcsolatát kifejező mátrixegyenletekbe: ⎡2 1 ⎤ ⎡1⎤ ⎡3⎤ ⎡1⎤ ⎢1 2⎥ ⋅ ⎢1⎥ = ⎢3⎥ = 3 ⋅ ⎢1⎥, illetve ⎣ ⎦ ⎣⎦ ⎣ ⎦ ⎣⎦ ⎡2 1 ⎤ ⎡ 1 ⎤ ⎡ 1 ⎤ ⎡1⎤ ⎢1 2⎥ ⋅ ⎢− 1⎥ = ⎢− 1⎥ = 1 ⋅ ⎢− 1⎥ , tehát az eredmények jók. ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ Az R függvény neve eigen.
5
„B” verzió Elméleti kérdések: E1. Mikor mondjuk, hogy egy halmaz végtelen? Mikor mondjuk, hogy megszámlálhatóan végtelen számosságú? Adjon példát megszámlálhatóan végtelen számosságú halmazra. Mit jelent az, hogy a valós számok R halmaza nem megszámlálható? (25 pont)
Egy halmaz végtelen, ha elemeinek száma végtelen. Egy másik, ezzel ekvivalens definíció: egy halmaz végtelen, ha ekvivalens egy valódi részhalmazával. Egy halmaz megszámlálhatóan végtelen számosságú, ha valamilyen szabály szerint elemei sorozatba rendezhetők, azaz ha a halmaz ekvivalens a természetes számok halmazával. Így például maga a természetes számok halmaza megszámlálható számosságú. Az, hogy a valós számok R halmaza nem megszámlálható, azt jelenti, hogy R nem ekvivalens a természetes számok halmazával. Másképp megfogalmazva, nem létezik olyan rendezési szabály, amellyel a valós számok sorozatba rendezhetők. E2. Adja meg a négyzetes mátrix inverzének definícióját. Adjon példát olyan négyzetes mátrixra, melynek létezik, és olyanra is, melynek nem létezik inverze. Indoklás is szükséges! Mi a neve annak az R-beli függvénynek, amivel kiszámítható egy mátrix inverze? (25 pont)
Az A négyzetes mátrix inverze egy olyan B mátrix, melyre A ⋅ B = I . Egy négyzetes mátrixnak pontosan akkor létezik inverze, ha a determinánsa nem nulla. Így például I -nek létezik inverze (ami maga az I ) , a csupa 0 elemből álló ún. nullmátrixnak pedig nem. R-ben a ginv függvénnyel számíthatjuk ki egy mátrix inverzét. Feladatok: F1. Írja át a
3x1 2 x1 x1
+ x2 + x2 − x2
+ x3 − 2 x3
= 5 = 2 = 3
egyenletrendszert mátrixegyenletté, majd oldja meg a Cramer-szabállyal. (Más módszert most nem fogadok el!) Mi a neve annak az R-beli függvénynek, amivel egy lineáris egyenletrendszer megoldható? (25 pont) 0 ⎤ ⎡ x1 ⎤ ⎡5⎤ ⎡3 1 A mátrixegyenlet: ⎢⎢2 1 1 ⎥⎥ ⋅ ⎢⎢ x2 ⎥⎥ = ⎢⎢2⎥⎥. ⎢⎣1 − 1 − 2⎥⎦ ⎢⎣ x3 ⎥⎦ ⎢⎣3⎥⎦
6 Megoldás a Cramer-szabállyal:
x1 =
5
1
0
3 5
0
3
1
5
2
1
1
2 2
1
2
1
2
3 −1 − 2 1 3 −2 1 −1 3 , x2 = , x3 = . 3 1 0 3 1 0 3 1 0 2
1
1
1 −1 − 2
2
1
1
2
1 −1 − 2 3
1
1
1
1 −1 − 2
0
1 1 2 1 A rendszer determinánsa 2 1 1 =3 − 1⋅ = 3 ⋅ (−1) − 1 ⋅ (−5) = 2. −1 − 2 1 −2 1 −1 − 2 5
Az x1 számlálójának determinánsa
1
0
5 1 0
5 1 2 1 1 = 2 1 1 = −1 ⋅ = −1 ⋅ −2 = 2 (a 3. 7 1 3 −1 − 2 7 1 0
sorhoz hozzáadtam a 2. sor kétszeresét, ez a determináns értékén nem változat, viszont könnyebbé teszi a 3. oszlop szerinti kifejtést) . Az 3 2 1
x 2 számlálójának determinánsa
5
0
3 5 0
3 5 2 1 = 2 2 1 = −1 ⋅ = −1 ⋅ −4 = 4 ( A 3. sorhoz hozzáadtam a 2. sor kétszeresét). 5 7 3 −2 5 7 0 3
1
5
1 0 3
1 3 Az x3 számlálójának determinánsa 2 1 2 = 2 1 2 = 1 ⋅ = 1 ⋅ −4 = −4 . (Az 1. 3 5 1 −1 3 3 0 5
sorból kivontam a 2. sort, a 3. sorhoz hozzáadtam a 2. sort.) Ez alapján x1 = 1, x2 = 2, x3 = −2. A számolás (és a módszerek alkalmazása) nagyon könnyen elrontható, érdemes ezért az eredményeket ellenőrizni. Helyettesítsünk vissza mondjuk a mátrixegyenletbe: ⎡1 ⎤ ⎢2⎥ ⎢ ⎥ ⎢⎣− 2⎥⎦ . Tehát az eredmények jók. 0 ⎤ ⎡5 ⎤ ⎡3 1 ⎢2 1 1 ⎥⎥ ⎢⎢2⎥⎥ ⎢ ⎢⎣1 − 1 − 2⎥⎦ ⎢⎣3⎥⎦ Az R-beli függvény neve solve.
7 F2. Egy 3x3-as szimmetrikus A mátrix sajátértékei 0, -2 és -3. Az alábbi állítások közül melyek igazak és melyek nem a mátrixra?
a) b) c) d) e) f)
Pozitív definit. Negatív definit. Pozitív szemidefinit. Negatív szemidefinit. Indefinit. Ha a a 0-hoz, b a -2-höz, c a -3-hoz tartozó sajátvektorok, akkor a , b és c páronként merőlegesek egymásra. g) Létezik a 3-dimenziós térnek az A mátrix sajátvektoraiból álló ortonormált bázisa. ⎡1⎤ T Legyen u = ⎢⎢0⎥⎥ . Milyen előjele lehet u ⋅ A ⋅ u -nak? Válaszai csak indoklással együtt ⎢⎣1⎥⎦
érvényesek! Mi a neve annak az R-beli függvénynek, amellyel meghatározhatók egy négyzetes mátrix sajátértékei és sajátvektorai? (25 pont) A sajátértékek negatívak vagy 0 az értékük, így a mátrix negatív szemidefinit, vagyis d igaz. Az a és b nem lehet igaz, mert a 0 sajátérték. A c nem igaz, mert van a mátrixnak negatív sajátértéke. Az e nem igaz, mert nincs a mátrixnak pozitív sajátértéke. Az f igaz, mert szimmetrikus mátrix különböző sajátértékeihez tartozó sajátvektorai ortogonálisak. A g igaz, ui. szimmetrikus mátrixhoz mindig létezik ortonormált sajátvektorokból álló bázis. T
A mátrix negatív szemidefinit, így u ⋅ A ⋅ u előjele negatív, vagy 0. (0 akkor lehet, ha u a mátrix 0-hoz tartozó egyik sajátvektora). Az R-beli függvény neve eigen.