Kezdőlap


Cím:	Számítástechnika 12. rész
Szerző(k):	Ada-Winter Péter
Füzet:	1978/január, 24 - 27. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Az előző részben kitűzött feladatok megoldása

1. Feladat:
Blokkdiagram készítendő a $10$ ismeretlenes lineáris egyenletrendszer elimációs program‐részletéhez.
Megoldás az alábbi ábrán látható:

2. Feladat:
Az elkészült blokkdiagram alapján ELIM azonosítójú SUBROUTINE készítendő.
Megoldás lehet pl. az alábbi programrész:

\begin{matrix} SUBROUTINE ELIM(A) \\ DIMENSION A(10,11) \\ DO 3K=1,9 \\ L= K+1 \\ DO 2I= L,10 \\ B =A(I,K)/A(K,K) \\ DO1J=K,11 \\ 1 & A(I,J)=B*A(K,J)‐A(I,J) \\ 2 & CONTINUE \\ 3 & CONTINUE \\ RETURN \\ END \end{matrix}

Megjegyezzük, hogy az elimináció végrehajtására ez a szubrutin még nem teljesen megfelelő, a továbbiakban módosítani fogjuk.

6.2 Főelem keresés

Már többször szó esett arról, hogy az elimináció során folyamatosan átalakuló együttható‐mátrixban nem válhatnak zérussá ‐ pontosabban valamilyen alkalmasan választott

ε

számmal egyenlővé ill. annál kisebbé ‐ azon elemek abszolút értékei, melyek a további számítás során osztók lesznek. Az eljárásból látható, hogy ezek az együtthatók az

n \times (n + 1)

méretű mátrix utolsó oszlopának elhagyásával kapható négyzetes mátrix főátlójában helyezkednek el. (Négyzetes mátrixban a sorok és oszlopok száma megegyezik; a főátló a négyzetes mátrix bal felső sarkától a jobb alsó sarkához húzott egyenes.) Azaz

a_{i, i} (i = 1, 2, ..., n - 1)

aktuális értékeivel osztunk, éspedig első menetben

a_{1,1}

-gyel, a másodikban

a_{2,2}

-vel, stb, az utolsó,

(n - 1)

-dik menetben

a_{n - 1, n - 1}

-gyel. A továbbiakban ezeket a felhasználás időpontjában felvett főátlóbeli értékeket nevezzük főelemeknek. Mit tehetünk, ha egy főelem

ε

-nal egyenlővé, vagy annál kisebbé (röviden: ,,közel zérussá'') válik? Az egyenletrendszer számítási eljárásának megzavarása nélkül megcserélhetjük az oszlopokat, amivel a rossz főelem helyére egy jó helyezhető. Ennek bemutatására módosítsuk a 6.1 fejezet elején hozott numerikus példánkat az alábbira:

E_{0,1} : 3 x_{1} + 4 x_{2} + 3 x_{3} = 1

E_{0,2} : 2 x_{1} + \frac{8}{3} x_{2} - x_{3} = 6

E_{0,3} : x_{1} + 3 x_{2} + 2 x_{3} = - 1

Az első menet után az egyenletrendszer alakja:

E_{1,1} : 3 x_{1} + 4 x_{2} + 3 x_{3} = 1

E_{1,2} : 0 + 0 + 3 x_{3} = - \frac{16}{3}

E_{1,3} : 0 - \frac{5}{3} x_{2} - x_{3} = \frac{4}{3}

Most felcseréljük a második és harmadik oszlopot, hogy a főelem ne legyen zérus:

E_{1,1} : 3 x_{1} + 3 x_{3} + 4 x_{2} = 1

E_{1,2} : 0 + 3 x_{3} + 0 = - \frac{16}{3}

E_{1,3} : 0 - x_{3} - \frac{5}{3} x_{2} = \frac{4}{3}

Ezek után a második menet végrehajtható, eredménye:

E_{2,1} : 3 x_{1} + 3 x_{3} + 4 x_{2} = 1

E_{2,2} : 0 + 3 x_{3} + 0 = - \frac{16}{3}

E_{2,3} : 0 + 0 + \frac{5}{3} x_{2} = \frac{4}{9}

Ezzel az eliminációs rész befejeződött. A visszahelyettesítésnél a legalsó egyenletből

x_{2}

-t fejezzük ki, ezt a fölötte levő egyenletbe behelyettesítve, onnan

x_{3}

-at kapjuk meg, végül az első egyenletbe

x_{2}

és

x_{3}

behelyettesítésével kapjuk

x_{1}

-et. A gyökök rendre:

x_{2} = \frac{4}{15}

x_{3} = - \frac{16}{9}

x_{1} = \frac{79}{45}

abban a sorrendben, ahogy megkaptuk. Ez a körülmény újabb feladatot ró ránk: visszahelyettesítés után helyre kell raknunk a gyököket, abba a sorrendbe, amilyenben az adott egyenletrendszerben voltak.
Elvileg minden menetben előfordulhat, hogy új főelemet kell keresni. Ez egy

k

-dik menetben úgy történik, hogy megvizsgáljuk a

k

-dik sor

k

-dik elemét. Ha annak értéke nem közel zérus, akkor a menet megindítható, ha viszont

a_{k, k} \leq ε

, akkor megvizsgáljuk

a_{k, k + 1}

-et. Ha ennek értéke nem közel zérus, akkor a

k

-adik oszlopot kicseréljük a

(k + 1)

-edikkel, ha igen, akkor megvizsgáljuk az

a_{k, k + 2}

értékét, stb. Minden sorban csak az

n

-dik elemig szabad a vizsgálatot folytatni, mivel az

(n + 1)

-edik elem nem együttható. Ha a

k

-adik sorban

a_{k, k}

-tól

a_{k, n}

-ig bezárólag mindegyik elem közel zérus, akkor az egyik egyenlet egy másikból konstanssal való szorzással előállítható, azaz kevesebb az egymástól független egyenletek száma az ismeretlenek számánál. Ilyenkor az egyenletrendszer határozatlan. Ilyen esetekben megfelelő szöveg kiíratása után megállíthatjuk a programvégrehajtást.
A mondottakból következik, hogy eliminációs szubrutinunkat módosítanunk kell. Mielőtt a főelemmel az osztást elvégeznénk, megvizsgáljuk, hogy közel zérus-e. Ha nem, indulhat a soron következő menet, de ha igen, akkor egy főelem kereső szubrutin hívása következik.

Feladatok:
1. Blokkdiagram készítendő a

10

ismeretlenes egyenletrendszer eliminációs eljárása során alkalmazandó főelem keresésére. Ez egy szubrutin, melyet az elimináló szubrutin hív abban az esetben, ha az eredeti főelem közel zérus. A főelem kereső szubrutin átveszi az aktuális menet sorszámát, az aktuális együttható mátrixot, epszilon értékét, valamint egy egész típusú,

10

elemű vektort, amely a számítandó gyökök indexeit az oszlopcseréknek megfelelő sorrendben tárolja. (Ennek komponensei a program megindításakor rendre az

1

-től

10

-ig terjedő egész számok.) A szubrutin megkeresi a szóban forgó sorban balról jobbfelé haladva az első nem zérusnak számító együtthatót, és ennek megfelelően végrehajtja az oszlopcserét. Ezzel egyidejűleg az egész típusú vektorban is felcseréli a megfelelő komponenseket. Ha a sorban megfelelő főelem nem található, akkor kinyomtatja, hogy ,,az egyenletrendszer határozatlan'', majd STOP-ra megy.

2. Program készítendő egy

5 \times 5

-ös méretű bűvös négyzet betöltésére és kinyomtatására. (Bűvös négyzeten itt az olyan páratlan számú sort ill. oszlopot tartalmazó négyzetes mátrixot értjük, melynek valamennyi sorösszege és oszlopösszege ugyanaz a szám. Pl. ilyen a

\begin{matrix} \begin{matrix} 8 & 1 & 6 \\ 4 & 9 & 2 \\ 3 & 5 & 7 \end{matrix} \end{matrix}

mátrix is. A bűvös négyzet rendjén sorainak ill. oszlopainak számát értjük.)

Bűvös négyzetek egy kitöltési szabálya:

a) A mátrix bármilyen számtani sor egymást követő elemeivel betölthető. Ha

a_{0}

az első betöltött elem és

d

a növekmény, akkor a

(k + 1)

-edik elem:

a_{0} + k \cdot d

.
b) Mindazon esetekben, amikor

k + 1

nem osztható a bűvös négyzet rendjével, a mátrix elemeinek kitöltésénél a haladás iránya ,,ferdén le'', azaz az alatta levő sorban a balfelé következő elem.
c) Mindazon esetekben, amikor a bal szélső oszlopból kell továbblépni, ciklikusan a jobb szélső oszlopra térünk át; amikor pedig a legalsó sorból kell továbblépni, akkor ciklikusan a legfölső sorba térünk át.
d) Azon esetekben, amikor

k + 1

osztható a mátrix rendjével, a kitöltés iránya ,,egyenesen felfelé'', azaz ugyanezen oszlopban az egy sorral feljebb álló elem. A ciklikusság itt is érvényesül.
A program kártyáról olvassa be

a_{0}

és

d

értékét. Kinyomtatja a mátrixot és valamivel lejjebb a közös sor- ill. oszlopösszeget.