EGYSZERŰSÍTETT ALGORITMUS AZ ELEMI BÁZISCSERE ELVÉGZÉSÉRE


1 Lipécz György* EGYSZERŰSÍTETT ALGORITMUS AZ ELEMI BÁZISCSERE ELVÉGZÉSÉRE AVAGY A SZÁMÍT...

0 downloads 2 Views 300KB Size

Recommend Documents


Az ellipszoid algoritmus
1 Az ellipszoid algoritmus Csizmadia Zsolt Eötvös Loránd Tudományegyetem2 Bevezető Az ellipszoid módszert a nemline&aac...

Az ismert elemi részecskék legtünékenyebb
1 PATKÓS ANDRÁS Túl a részecskefizikai Standard Modellen Az ismert elemi részecskék legtünékenye...

Problémák, kérdések az algoritmus vizualizációval kapcsolatban
1 Problémák, kérdések az algoritmus vizualizációval kapcsolatban Bende Imre ELTE IK Absztrakt. Az algoritmus...

Nem-extenzív effektusok az elemi kvantumstatisztikában?
1 Nm-xtzív tuso az lm vatumstatsztába? Bró Tamás Sádor MTA Wgr FK RMI Boltzma-Gbbs-Plac-Réy-Tsalls 2. Frm &a...

Elemi költségvetés Elemi költségvetés
1 A megye megnevezése, székhelye: Irányító szerv: számjel PIR-törzsszám Szektor Megye PÜK S...

Beiger Anna: Hitelemzések az első elemi osztály számára
1 PPEK 1005 Beiger Anna: Hitelemzések az első elemi osztály számára Beiger Anna Hitelemzések az első elemi oszt&aac...

Az elfogadó iskola koncepcionális kereteinek kidolgozása Elemi projekt száma:
1 Az elfogadó iskola koncepcionális kereteinek kidolgozása Elemi projekt száma: Az adaptív iskola koncepciój...

Matematika A1H - oktatási segédanyag. 1. Az euklideszi algoritmus az egész számokra
1 Budapesti Műszaki és Gazdaságtudományi Egyetem Gépészmérnöki Kar Energetika, Mechatronika és T...

Algoritmus odesílání pacienta
1 Algoritmus odesílání pacienta s exacerbací CHOPN k hospitalizaci Ondřej Kudela Plicní klinika FNHK a LFHK UK2 AE ...

EM-ALGORITMUS HIÁNYOS ADATRENDSZEREKRE
1 Süvítenek napjank, a forró sortüzek valamt mnden nap elmulasztunk. Robotolunk lélekszakadva, jóttevőn, s valam...



Lipécz György* EGYSZERŰSÍTETT ALGORITMUS AZ ELEMI BÁZISCSERE ELVÉGZÉSÉRE AVAGY A SZÁMÍTÓGÉP-HASZNÁLAT LEHETŐSÉGE A LINEÁRIS ALGEBRA ÉS AZ OPERÁCIÓKUTATÁS ALAPJAINAK OKTATÁSÁBAN "

„Simplicitassigillum veri"

A lineáris algebra és az operációkutatás egyik, mind gyakorlati, mind elméleti szempontból alapvető eljárása a szimplex algoritmus és ezen belül az elemi bázistranszformáció. A szimplex módszert kifeje­ zetten a programozhatóság céljából fejlesztették ki, s bár a tankönyvek szokásos tárgyalásmódja jól ki­ emeli az eljárás matematikai lényegét, mégis, a jól megjegyezhető mechanikusan elvégezhető eljárás könnyen eltereli a figyelmet a matematikai lényegről. A módszer azonban meglehetősen számolásigényes. Egy n x rc-es mátrix invertálása n * vektorkompo­ nens kiszámítását jelenti, (egy 4x4-es mátrix esetében, pl. ez 64 komponens), és - ha a mátrix egyáltalán invertálható - ez több mint kétszerannyi elemi művelet elvégzését igényli. Az illusztratív számpéldákban persze egyjegyű számokkal lehet dolgozni, köztük több O-val, így az invertáláshoz szükséges szimplex táblák viszonylag gyorsan, számológép használata nélkül előállíthatók. De a legkedvezőbb esetben is mechanikus, unalmas és könnyen eltéveszthető számítássorozatról van szó. Az elemi báziscsere alábbi módosított és végső soron egyszerűsített kifejtése az algoritmust nem bont­ ja elemeire, hanem mátrixműveletek használatával teszi lehetővé, hogy a gondolatmenet egyszerűbb és átláthatóbb legyen, a báziscsere matematikai lényegét még szemléletesebbé is teszi. Minimális számítógé­ pes jártassággal a sok számolás a gépre hárítható. Egyetlenegy műveletről: az elemi báziscseréről van csak szó. Mivel azonban ez számtalan lineáris algebrai és lineáris programozási probléma megoldásában játszik központi szerepet, ezért a bemutatan­ dó módszer az oktatás lehetőségeit a matematikai lényeg változatlansága mellett jelentősen bővíti. 1

1.Az elemi báziscsere mátrixának meghatározása az invertálásra való utalás nélkül Gondolatmenetünket az egyszerűség kedvéért 3 dimenziós esetre szűkítjük, az általánosítás azonban formálisan és kézenfekvő módon elvégezhető.

* Lipécz György főiskolai tanár, tanszékvezető, Általános Vállalkozási Főiskola Köszönettel tartozom Horváth József közgazdász-matematikusnak, a BKÁE oktatójának és Kovács Edithnek, az ÁVF oktatójának, mivel tanulmányom gondolatmenete azon beszélgetések során formálódott ki, amelyeket velük folytattam a lineáris algebra és az operációkutatás oktatásáról.

—130

— =

Legyen adva az e e , e bázisban egy a és egy b vektor, 1?

e

a = ö,e, + # 2

+ í 7

2

2

e

3 3

b = b e +b e + & e l

l

2

2

3

3

3

A feladatunk egy elemi báziscsere végrehajtása: •

vonjuk be az a vektort a bázisba, pl. az e helyére, (feltesszük, a nem egyenlő 0-val)



és írjuk föl az új bázisban a b vektort.

2

2

Mielőtt belekezdünk, felhívjuk a figyelmet, hogy nem szükséges úgy tekinteni, mintha ez a báziscsere első lépése volna. Az E egységmátrix által megadott bázis egy báziscsere-sorozat akárhányadik lépéseként előállított aktuális bázisnak is tekinthető, ahol persze a bázis vektorai a bázisban egységvektorokként jelennek meg. Az aktuális bázis vektorait nyugodtan elkeresztelhetjük kinthetjük „kanonikus bázisnak" is. Az alább leírt eljárás tehát általánosan vonatkozóan

e, e 2

3

vektoroknak, és te­

érvényes bármely

bázisra

egy elemi báziscsere lefolytatására.

Gondolatmenetünk a tankönyvekével megegyezően kezdődik: fejezzük ki az e vektort az a fenteb­ 2

bi felírásából:

1 2

1

1

—e, + — a - a , — e

e =-a

}

a

a

2

3

a

2

2

va

Ez tehát az e felírva az új [e a, e ] bázisban. Jelöljük ezt e " ^2

-a

x

1?

3

2

1 " — a 2

J_

a

2

1 a

2

( a)

A b vektor új koordinátáit úgy kapjuk, hogy e helyébe az e 2

b

(a)

=b e +b e? l

l

2

+b,e

3

2

-t írjuk.

Ezzel meg is érkeztünk, mivel a jobboldal felírható egy mátrix-szorzatként:

'b, (a,

b =[e, e f

e,] b

3

Az [ej

C ] mátrixot jelöljük C-vel és nevezzük az elemi báziscsere 3

A b és a

b

(a)

mátrixának.

vektor között a C mátrix teremt kapcsolatot:

b< = C b a)

Az C = [ej e

( a) 2

e ] mátrix elemei: 3

0 a

1

c = 0



0

0

1

Elvégébe a műveletet:

•ÍZ,

0 a,

b


=l 0

0

0

1

Természetesen ugyanazt kaptuk, mint a hagyományos generáló elemes algoritmussal, ahol a generáló elem az a , csak egyszerűbb, áttekinthetőbb, számítógéppel elvégezhető algoritmus segítségével. 2

Ífl2

=E===I^=======

— ===g=====i =

Továbbá, a kézi számolás lehetősége is ugyanúgy fennáll, és a munka ugyanannyi, de - a báziscsere alapelveinek ismertetése után - elegendő a mátrix-szorzás ismert műveletére hivatkozni. Összefoglalva: Ha az aktuális bázis &-adik vektorát akarjuk kicserélni az a vektorral, (a ^ 0) és ebben a bázisban k

meg akarjuk határozni egy b vektor új koordinátáit, akkor •

veszünk egy egységmátrixot,



és a k-adik oszlopát kicseréljük az e^ -val.

a)

Ezzel megkaptuk az elemi báziscsere C mátrixát. •

Ennek segítségével bármely - az előbbi bázisban felírt - vektornak az új koordinátáit a C-vel való szorzással kapjuk meg.

Egy szimplex táblázatban szereplő valamennyi vektornak az új koordinátáit tehát egyetlen mátrix­ szorzással elő lehet állítani, ami egy táblázatkezelő program birtokában nagyon egyszerű művelet. Jelöl­ jük az egész szimplex táblázatot S-sel, akkor az új táblázat: s

(a)

=c s

2. Elemi báziscsere invertálással Ugyanerre az eredményre egy másik úton is eljuthatunk, igénybe véve az inverz mátrix fogalmát. A báziscsere eljárása többek között mátrixok invertálására használható, ezért úgy tűnhet, a gondolatmenet önmagába fordul. De nem így van, mert számunkra az inverz mátrixnak a fogalma is elegendő, és az alkalmazandó gondolatmenetben olyan speciális mátrix szerepel, amelynek az inverze - ha létezik elemi úton is egyszerűen előállítható.

~1 0 0" A kiinduló bázisunk (az aktuális bázis) most is az [e,

e

2

3

A bázisba bevonandó vektor is az a (a ^ 0). Az új bázis pedig: [e, k

azaz:

1

a,

0

0

a

0

0

a

2

E, = 3

1

Az E mátrix a báziscsere tényét szemléletesen és egyszerűen mutatja. 2

0 1 0 0 0 1

e ], azaz:

a

e ], jelöljük E -vel, 3

2

(a)

A b vektor az új bázisban: b . A b vektor az új bázis vektorainak lineáris kombinációjaként állítható elő, tehát

E b

(a)

2

= b

Amennyiben a b

b

(a)

(a)

vektort akarjuk előállítani, akkor A inverzével kell szorozni:

1

= E" b

Az E

! 2

mátrixot az elemi báziscsere mátrixának

nevezhetjük. Ezt jelöltük az előbb C-vel.

Határozzuk meg az inverz mátrixot. Egyszerű a feladat, mert, mint látni fogjuk, az inverz az eredetitől ( a)

csak a 2. oszlopban fog különbözni, és ez éppen az e

2

vektor lesz. Az előző gondolatmenettől függet­

lenül haladva, írjuk föl az inverz definíciójának megfelelően, hogy:

[e,

a

ejc^i

[e

a

e ] c = e

[e,

a

e ]c,

2

=e

3

2

3

Ebből rögtön látható, hogy a c, = e, és c, = e_ Tehát, hogy csak az v

[e,

a

ejc =e 2

2

egyenletet kell megoldani.

"0"

C

\2

0

a

0

a

2

3

0

1

c

22

-

1

0

Ez az alábbi három egyszerű egyenletet jelenti:

C

C

\2

C

A

22 \

ü

22 l

=

C

+ 32 =

0

0

A megoldásra kijön a korábbi eredmény. (Egy ilyen C a = 1 típusú egyenlet egyébként a dimenzió­ ii

i

számtól függetlenül mindig adódik az egyenletrendszerben, és a többi egyenlet baloldala mindig kétta­ gú összeg lesz, ez biztosítja, hogy az inverz elemi úton is gyorsan előállítható.)

-a,

C = 2

'22

'32

Az elemi báziscsere mátrixa így (e c e ), azaz: {

2

3

0 1 a Az elemi báziscsere mátrixa tehát:

C = 0

0

a

x

0

2

0

0

a, 1

0

a.

a, 1 0

1

Összefoglalva: Ha az aktuális bázis &-adik vektorát akarjuk kicserélni az a vektorral (a

k

^ 0), és ebben a bázisban

meg akarjuk határozni egy b vektor új koordinátáit, akkor eljárhatunk a következőképpen is: Vegyünk egy egységmátrixot, A k-adik oszlopát cseréljük ki az a-val, a módosított mátrixot jelöljük E -val. K

Határozzuk meg az E inverzét, amivel megkapjuk az elemi báziscsere C mátrixát. K

^

^

^

^

^

=I=ZZ==ZIZEEEEEEEE^B5

3. Az elemi báziscsere mátrixának értelmezéséről Az elemi báziscsere C mátrixa nem más, mint a korábbi bázis egységvektorainak az új bázisbeli alakja. Más szóval, az új bázis vektoraiból álló mátrix inverze. Ezt fentebb a 2. pontban formálisan levezettük, de megfogalmazhattuk volna már akkor, amikor az e vektort az [e,

a

2

(a) e

1

1

= -a, — e

2

x

bázisban

1

H

a - a

Cl 2

e,]

— e

3

Cl 2

3

Cl 2

alakban felírtuk, és beillesztettük az e és e vektorok közé. Az ej és e komponensei az új bázisban változatlanok maradnak, mivel maguk is tagjai az új bázisnak. l

íly módon a C = [e, e új bázisbeli felírása.

( a)

e]

2

3

3

3

mátrix mindhárom vektora úgy tekinthető, mint a régi bázisvektorok

Általánosan is: ha nemcsak egy új vektort vontunk be az eredeti E bázisba, hanem az A összes vekto­ ()

rát, tehát már az A mátrix oszlopvektorai alkotják az új bázist, akkor a b meghatározható úgy, hogy továbbra is az eredeti bázisvektorok

(A)

vektornak az új bázisbeli alakja

lineáris kombinációjaként írjuk föl, vi­

szont az eredeti bázisvektorokat már az új bázisvektorok lineáris kombinációjaként fejezzük ki. Azaz:

b

(A)

=b e

( A )

]

l

(A)

(A)

+ be 2

*(A)

2

Mindezek alapján magának az inverz mátrixnak a fogalmát is építhetnénk a báziscsere fogalmára, írjuk föl az aktuális bázis vektorait - ha ez lehetséges - az A négyzetes mátrix vektorai által alkotott bázisban, és az így kapott vektorok mátrixát nevezzük el inverz mátrixnak. Ha pedig már elfogadtuk, hogy az E bázisról az A bázisra történő áttérés megoldható úgy, hogy az E ()

0

bázis vektorait felírjuk az A bázisban, akkor ebből már következik, hogy

AA

1

=E (A)

Hiszen a bázisban.

A

- 1 =

C

Az A e|

A)

mátrix

c vektora nem más, mint e)

, azaz, egy E -beli egységvektor az A 0

szorzat tehát az E bázis i-edik egységvektorát adja meg. Az eredményül kapott 0

mátrix tehát az egységmátrix. A tényezőket fölcserélve szintén az egységmátrixot kapjuk: 1

A" A = E Ez szorzat ugyanis az a.-nek az A bázisbeli alakját adja, ami egységvektor. A fenti gondolatmenetben ugyanannak az E egységmátrixnak eltérő lesz az interpretációja aszerint, hogy az A vektort az inverzével milyen sorrendben szorozzuk össze. Az egységvektorokat jelenti az E bázisban, míg a A 0

amik szintén egységvektorok.

- 1

szorzat az E bázisbeli 0

A szorzat az A bázis bázisvektorait adja az A bázisban,

T06 Az elemi báziscsere mátrixszorzatként való előállítása tehát egyrészt lehetővé teszi az oktatásban ül. a tanulásban a számítógép felhasználását, másrészt a figyelmet a mechanikus eljárásoktól a vektorterek alapvető tulajdonságai felé tereli. Az elemi báziscserét az általános bázistranszformáció egyszerű esete­ ként lehet bemutatni, és a lineáris egyenletrendszerek elméletét a vektorterek szintjén következetesen, néhány egyszerű alapelv és tétel segítségével mélyebben, mégis egyszerűbben lehet tárgyalni.

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 TIXPDF.COM - All rights reserved.