Novák Ágnes - lineáris egyenletrendszerek

Országok listájaHungaryMiskolci EgyetemGépészmérnöki és Informatikai KarProgramtervező informatikusDiszkrét MatematikaJegyzetekNovák Ágnes - lineáris egyenletrendszerek

PPKE ITK

Algebra és diszkrét matematika

Lineáris egyenletrendszerek
lineáris= elsfokú, az ismeretlenek (xi-k) elsfokon szerepelnek. a11x1+a12x2+...a1nxn=b1 a21x1+a22x2+...a2nxn=b2
...

am1x1+am2x2+...amnxn=b3
a 11 a 21 ... a m1 a 12 a 22 ... a m2 a 1 n x 1 b1 ... a 2 n x 2 b 2 = ... ... ... ... ... a mn x n b m ...

(m×n)(n×1)=m×1 Ax=b A: együttható mátrix Megoldás: milyen értékeket vehetnek fel az ismeretlenek? ­ elre meg kel mondnai, mely testben keressük a megoldást. A továbbiakban megoldást R-ben keressük. 1. Speciális eset: HA n=m, és az egyenletek függetlenek egymástól (egyiket sem lehet a többibl algebrai átalakításokkal levezetni-ezt nehéz látni,de a következ feltétel biztosítja) det(A)0 akkor a.) inverz mátrix b.) Cramer szabály segítségével megkaphatjuk meg az egyetlen megoldást 2. Általános eset: Gauss elimináció 1. a.) Egyenletrendszer megoldása inverz mátrix segítségével

Ax = b
A -1

A x = A b
-1 -1

-1

Ex = A b x=A b

©Bércesné Novák Ágnes

1

PPKE ITK

Algebra és diszkrét matematika

Példa:

x+2y=3 4x+5y=6
1 2 x 3 4 5 y = 6
1 2 A= 4 5 det(A)=1·5-4·2=-3 + - - +
2 - 3 1 3

5 1 1 5 - 2 3 A -1 = adj( A ) = - = det( A ) 3 - 4 1 - 4 3 1 2 x 3 -1 4 5 y = 6 / A , balról szorozva

5 2 1 0 x - 3 3 3 0 1 y = 4 1 - 6 3 3 2 5 x - 3 3 3 6 y = 4 3 - 1 6 3 3 x=-1 y=2

©Bércesné Novák Ágnes

2

PPKE ITK

Algebra és diszkrét matematika

b.) Tétel (Cramer-szabály): Ha ATn×n és D=det(A) 0, akkor az Ax=b egyenletrendszernek pontosan egy megoldása van. A megoldásban xj=D j/D, ahol D j determinánst úgy kapjuk,hogy D-ben a j-edik oszlop helyére a jobb oldali konstansokat (azaz a b vektor komponenseit) írjuk. a11x1+a12x2+...a1nxn=b1 a21x1+a22x2+...a2nxn=b2
...

am1x1+am2x2+...amnxn=b3
a 11 a 21 ... a m1 a 12 a 22 ... a m2 ... a 1n x 1 b1 ... a 2 n x 2 b 2 = ... ... ... ... ... a mn x n b m Pl: a 11 a 21 ... x2 = b1 b2 ... ... a 1n ... a 2 n ... ...

a n1 b n ... a nn a 11 a 12 ... a 1n a 21 ... a n1 a 22 ... a n2 ... a 2 n ... ... ... a nn

©Bércesné Novák Ágnes

3

PPKE ITK

Algebra és diszkrét matematika

Bizonyítás:
Tfh. xi-t szeretnénk kiszámítani. A módszer lényege, hogy az összes egyenletbl kiküszöböljük egyszerre az ismeretleneket, kivéve xi-t. a11x1+a12x2+...+a1ixi...+ a1nxn =b1 /D1i a21x1+a22x2+...+ a2ixi ...+ anxn =b2 /D2i
...

an1x1+am2x2+...+ anixi ...+ annxn =bn/Dni ahol Dik az A együtthatómátrixban az aik elemhez tartozó eljeles aldetermináns. Összeadva az összes egyenletet és kiemelve az ismeretleneket a következ adódik: BALOLDAL: x1(a11 D1i+a21D2i+...an1Dni)+ / (1. oszlop) * (i. oszlophoz tartozó aldeterminánsok) + x2(a12 D1i+a22D2i+...an2Dni)+ / (2. oszlop) * (i. oszlophoz tartozó aldeterminánsok) + x3(a13 D1i+a23D2i+...an3Dni)+ / (3. oszlop) * (i. oszlophoz tartozó aldeterminánsok) ... +xi(a1i D1i+a2iD2i+...an1Dni)+ / (i. oszlop) * (i. oszlophoz tartozó aldeterminánsok) ... + xn(a1n Dni+a2nD2i+...annDni)= / (n. oszlop) * (i. oszlophoz tartozó aldeterminánsok) =xi det(A), a kifejtési tétel, illetve a ferde kifejtés miatt JOBBOLDAL: a 11 ... b1D1i+b2D2i+b3D3i+...biDii+...+bnDni= b1 ... a 1n ... a 2 n ... ... ... a nn

a 21 ... b 2 ... ... a n1 ... b n

BALOLDAL=JOBBOLDAL a 11 ... xi det(A) = b1 ... a 1n ... a 2 n ... ... ... a nn

a 21 ... b 2 ... ... a n1 ... b n

©Bércesné Novák Ágnes

4

PPKE ITK

Algebra és diszkrét matematika

2. Általános eset, n egyenlet, m ismeretlen

Gauss elimináció (kiküszöbölés) n x n-es független egyenletekbl álló lineáris egyenletrendszerre:
Elve: Alsó (vagy fels) háromszög mátrixban 0 elemek létrehozása (lépcss alak) után az ismeretlenek fokozatos közelítéssel (szukcesszív approximáció) kaphatók: Az egyenletrendszeren megengedett mveletek: 1.R, 0 ­val szorozni az egyenletet. 2. Valamely egyenlethez egy másik egyenlet számszorosát hozzáadni. 3. Egyenleteket felcserélni. 4. Az olyan egyenletet, amelyben minden együttható és jobboldali konstans 0, elhagyni (ez független egyenletekbl álló rendszer esetén nem fordul el). 1-4. ún. elemi ekvivalens átalakítások. Az egyenletekbl csak az együtthatókat és a jobboldali konstansokat írjuk sorrendhelyesen egy mátrixba, amelynek soraira ugyanezek a ,,mveletek" alkalmazhatók. Ezt a mátrixot kibvített mátrixnak nevezzük.

Példa:
x-2y+3z=1 2x+y+z=-3 -x+2y-2z=0

Rövidített jelölés - kibvített mátrix:
Els sor ­2-szeresét hozzáadjuk a második sorhoz, els sort hozzáadjuk a harmadik sorhoz:
1 2 -1 -2 1 2 3 1 1 -2 5 0 0 3 1 1 1 1 -3 0 -2 0 -5 -5

A fátló alatti elemek nullák, létrejött az alsó 0 háromszömátrix. Ebbl már az ismeretlenek könnyen kaphatók: 1z=1, z=1 5y+-5z=-5, z-t behelyettesítve, y=0 x + 0 +3=1, (y-t és z-t már behelyettesítettük), x=-2

©Bércesné Novák Ágnes

5

PPKE ITK

Algebra és diszkrét matematika

Gauss elimináció ,,algoritmusa":
A k. lépésben akk segítségével ,,nullázzuk" az akk alatti elemeket, k:=1,...,m (m az ismeretlenek száma). Ha akk nulla, akkor felcseréljük egy alkalmas, alk helyén nem nulla elemet tartalmazó sorra. Kérdés: Mi a helyzet, ha nem találunk alk helyén nemnulla elemet?

Gauss-Jordan elimináció n x n-es, független egyenletekbl álló lineáris egyenletrendszerre:
Az elzhöz hasonló módszerrel a fátló feletti elemek is kinullázhatók. Az utolsó sor 5szörösét hozzáadjuk a második sorhoz, az utolsó sor kétszeresét hozzáadjuk az els sorhoz, igy nullázzuk a 3. oszlop fels elemeit:
1 2 -1 -2 1 2 3 1 1 -2 0 -2 1 -2 0 -2 1 -3 0 5 0 0 0 5 0 0 -2 0 0 0 1 1 0 0 1 1

A második sort osztjuk 5-tel, hogy a fátlóban 1 legyen, majd a második sor kéteszresét hozzáadjuk az els sorhoz :
1 -2 0 -2 1 0 0 -2 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 1

Igy a fátló fölött is csupa nulla áll, az ismeretlenek értékei rögtön kiolvashatók: 1x=-2 , 1y=0, 1z=1

©Bércesné Novák Ágnes

6

PPKE ITK

Algebra és diszkrét matematika

Gauss-Jordan elimináció ,,algoritmusa":
1. Gauss elimináció 2. Mivel a fátló alatti elemek nullák, az együttható mátrix utolsó sorának csak az utolsó eleme nem nulla, így osztással könnyen egyest hozhatunk létre. Ezután ezzel az egyessel nullázzuk a felette lev számokat. A következ lépésben az eltte lev oszlop fátlóbeli elemét redukáljuk 1-re, majd ennek sgítségével nullázzuk a felette lev elemeket, és így tovább. Röviden: A k. lépésben an-k,n-k-t osztjuk önmagával, így 1-t kapunk, és ennek segítségével ,,nullázzuk" az akk feletti elemeket, az utolsó sorból indulva. K:=0,1...,m (m az ismeretlenek száma) Az így kapott lépcss alakot, amikor a fátló felett is nullák állnak, redukált lépcss alaknak nevezzük. A fenti leírás szerint létrhozott lépcss alakban szerpl egyeseket, amlyek tehát különböz sorokban és oszlopokban, a föátlóban helyezkednek el, vezéregyeseknek nevezzük. Független rendszer esetén nincsenek csupa nullából álló sorok. De ún. tilos sorok elfordulhatnak, amennyiben az egyenletrendszer ellentmondó egyneleteket tartalmazekkor nincsen megoldás. Tilos sor : az adott sorban az együttható mátrix elemei mind nullák, de a kibvített mátrixban a b-nek megfelel elem nem.

Példa: tilos sor a 3.:
1 0 0 -2 0 1 0 0 0 0 0 3

, mert 0x+0y+0z3!!!!

Tétel:
I. Az egyenletrendszer akkor és csak akkor oldható meg, ha nincs a lépcss alakban tilos sor. II. Egyértelm a megoldás, ha nincs tilos sor, és a vezéregyesek száma egyenl az ismeretlenek számával.

©Bércesné Novák Ágnes

7

PPKE ITK

Algebra és diszkrét matematika

Homogén lineáris egyenletrendszer
Ax = 0

Triviális megoldás: Homogén lineáris egyenletrendszernek mindig van ún. triviális megoldása: x1= x2=...= xn=0. Ha det(A)=0, ahol A ­ együtthatókból képezett mátrix. akkor van triviálistól különböz megoldás, amit Gauss eliminációval találhatunk meg. DE ha det(A)0, akkor csak a triviális megoldás van. Tétel:
Ha az egyenletrendszernek egyértelm a megoldása, akkor az ismeretlenek száma(n) <= egyenletek száma (k). Biz.: egyértelm n db ,,vezéregyes", n= ismeretlenek száma mivel ezek különböz sorokban vannak, n<=k, hiszen felesleges sor lehetséges, ez ,,nem rontja el" az egyenletrendszer egyértelm megoldását.

Tétel: Ha a homogén lineáris egyenletrendszerben kn.

©Bércesné Novák Ágnes

8

PPKE ITK

Algebra és diszkrét matematika

Megjegyzések:
1. A megoldásokszáma NEM függ az egyenletek számának és az ismeretlenek számának viszonyától. 2. Több (végtelen elemszámú test esetén végtelen) megoldás esetében nem tetszleges az ismeretlenek választása. Azok az ismeretlenek választhatók szabadon, amelyekkel, és csak azokkal a több ismeretlen kifejezhet. Ez a lépcss alakból könnyen következtethet: azok az ismeretlenek választhatók szabadon, amelyeknek oszlopában nincsen vezéregyes.

1 3 0 0 - 2 - 4 Példa: 0 0 1 0 - 1 - 2 3 0 0 0 1 1 Mivel a 2. és 5. oszlopban nincsen vezéregyes, ezért ezen helyeken álló ismeretlenek szabadon választhatók: x1=-3x2+2x5 x1+3x2+0+0-2x5=-4 x3=-2+x5 x3-x5=-2 x4+x5=3 x4=3-x5 Ennek az egyenletrendszernek tehát a valós számok körében végtelen sok megoldása van; ha x2, és x5 értékét rögzítjük, akkor minden olyan számötös, amelyeket úgy kapunk, hogy a rögzített x2, x5 értékekkel kiszámítjuk a velük kifejezett x1, x3, x4 ismeretleneket, az egyenletrendszer egy megoldását kapjuk.

TANULJUK MEG AZ ALÁBBI PROGRAMOK SEGTÍSÉGÉVEL!

http://wims.unice.fr/wims/wims.cgi
A search for ablakba írja be: Gauss elimination ­ az új lapon klikkeljen a Visual Gauss linkre. Itt interaktív gyakorlatokat talál a Gauss eliminációra és sok más lineáris algebrai feladatra. Jó szórakozást! (merthogy a jó munka is az :) Másik elemi sormveleteket elvégz kalkulátor: http://www.math.ncsu.edu/ma114/tools/row_ops.html

©Bércesné Novák Ágnes

9



Hasonló témájú dokumentumok

Diszkrét Matematika I. - Bacsó Sándor

- 2008-01-24 08:55:34

Novák Ágnes - Lineáris leképzések

- 2008-01-24 09:05:25

Pótzh 2007-12-13 Bcsop.

- 2008-01-24 09:15:26

Novák Ágnes - Komplex számok

- 2008-01-24 09:04:35

Elóadás jegyzet (Radeleczki féle)

- 2008-01-24 00:43:39

Vizsgazh 2007-01-08

- 2008-01-24 00:37:39

Novák Ágnes - Vektorterek

- 2008-01-24 09:06:25

A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.

Hozzászólások

Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni

Egy tipp az oldalhoz! - Naptári bejegyzéseket vehettek fel egy tantárggyal kapcsolatban, vagy az egész szakotok számára. Például:

• Zh időpontok
• Gólyabál időpontja
• Házi leadási határidő
• Tanítási szünetek
• stb ...

Kattints a Naptárra, majd a jobb felső részen levő Új naptári bejegyzés felvétele linkre.

1. félév 18. század 1eloadas 3. óra 5. agresszió alapfogalmak ásvány- és kőzettan corbu dolgozat éghajlat elm elte energia etika fehérje fejlődéslélektan feladatok fogyasztóvédelem házi dolgozat kaffka kafka kereskedelem keringés kiadott anyag kivitel környezet kulturális antropológia makroökonómia marás matek 1 miskolc móricz munkássága neveléslélektan oecd oprendszerek példák regterv reklámelmélet rezgéstan szte tanári jegyzet település tóth ttk valós érték vergilius vetőmag vízlágyítás