„Gauss-elimináció” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: idézőjelek javítása |
→Az eljárás célja és előnyei: link jav, kis korr |
||
24. sor:
Azt is megtehetjük, hogy az '''''A,b → A',b'''''' transzformáció helyett '''''A,x → A',x'''''' típusú alakítást végzünk:<br />
:<math>(AQ_1)(Q_1^{-1}x)=b\ldots\,</math>
Szemben az előbbi esettel, itt szükséges számontartanunk a végzett transzformációkat, mivel a megoldást nem a végső '''''x'''''', hanem az eredeti '''''x = Q<sub>1</sub> · Q<sub>2</sub> · ... Q<sub>m</sub> · x' ''''' [[vektor]]ra akarjuk meghatározni. A gyakorlatban a '''''T<sub>i</sub>''''' és '''''Q<sub>i</sub>''''' gyöktartó transzformációkat
Célunk az '''''A''''' mátrix bizonyos elemeinek a kinullázása a lehető legkisebb kerekítési hiba mellett. A következő egyszerű műveleteket használjuk:
* Felcserélve '''''A''''' bármely két sorát és a megfelelő sorokat '''''b'''''-ben , nem módosul az '''''x''''' megoldásvektor. Ez nyilvánvalóvá válik, ha észrevesszük, hogy a művelet az eredeti egyenletrendszer két egyenletének triviális felcserélését jelenti.
* Hasonlóképpen, ha bármelyik sort '''''A'''''-ban helyettesítjük önmaga és bármely másik sor [[lineáris kombináció]]jával, nem módosul a megoldás, ha azonos műveletet végzünk el '''''b''''' vektoron is. Az egyenletrendszer szintjén ez
* Két oszlop cseréje az '''''A'''''-ban a megfelelő együtthatók felcserélését teszik szükségessé az '''''x''''' megoldásvektorban. Az egyes egyenletek szintjén ez az összeadás [[kommutativitás]]ának kihasználását jelenti.
A mátrix-[[szorzás]]ok n<sup>3</sup>-bel arányos számítási költségének elkerülése érdekében kihasználjuk azt a tényt, hogy a fenti műveleteknek megfelelő transzformációs mátrixokban csak ''n'' elem különbözik nullától. Ezért a sorok és oszlopok módosítását közvetlenül elvégezhetjük ''n''-nel arányos [[művelet]]tel.
46. sor:
<math>a_{m1}x_{1}+a_{m2}x_{2}+\dots+a_{mn}x_{n}=b_{m}</math>
Ekkor tegyük fel, hogy <math>a_{11}\neq0</math>. (Ez az állapot az egyenletek sorrendjének felcserélésével elérhető.) Ekkor vonjuk ki az i. egyenletből (ahol <math>i\geq2</math>) az első egyenlet <math>\frac{a_{i1}}{a_{11}}</math> – szeresét. Az <math>a_{11}</math>
A következő egyenletrendszert kapjuk:
112. sor:
az (1), (2)... (n) felső indexek az egyes lépéseket jelölik.
A
'''''function''''' <math>Gauss</math> '''''inout:''''' <math>(a_{ij}),(b_i) i,j=1..n</math> (az '''''A''''' mátrixot és a '''''b''''' vektort „helyben” módosítjuk)<br />
154. sor:
A [[ritka mátrix]]ok Gauss-eliminációja során fellépő jelenséget, hogy olyan helyeken keletkezik nemzérus elem, ahol eredetileg nulla állt, feltöltődésnek nevezik. Mivel a ritka mátrixokban a nulla elemeket általában helytakarékosan tárolják, ezért a feltöltődésre ügyelni kell: helyet kell szerezni az újonnan keletkezett elemeknek. Ha külön nem foglalkoznak vele, a feltöltődés nagymértékű is lehet; egy eliminációs lépés alatt akár az egész mátrix feltöltődhet.<ref>[http://www.tankonyvtar.hu/hu/tartalom/tkt/numerikus-modszerek-1/ch02s03.html Stoyan Gisbert-Takó Galina: ''Numerikus módszerek I.]</ref>
A [[minimális feltöltődés]] ''(minimum fill-in)'' elérése kívánatos cél, a szükséges számítási bonyolultságról még kevés tanulmány született;<ref>[https://arxiv.org/abs/1606.08141 Yixin Cao, R. B. Sandeep: Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds]</ref>
== Hivatkozások ==
| |||