Java – Gaussova Eliminační Metoda
Comments(5)
Funkční applet: ZDE.
EDIT: Problém s lineárně závislými řádky :-).
Následující kód, který jsem dnes uvařil:-), převádí pomocí GEM matice libovolného typu do horního trojúhelníkového tvaru. Je optimalizovaný i pro mrchy matice, které v sobě skrývají n lineárně závislých řádků nebo dokonce sloupců. Je částečně optimalizovaný i paměťově… během výpočtu efektivně krátí nově vzniklé řádky matice (to je možno vypnout pomocí opt_through).
po předvedení kódu (kde záměrně chybí ona krátící metoda) ho vysvětlím a potom ukážu pár příkladů (přímo ze skript pana Olšáka).
public void GEM(boolean opt_through) { int i, j, l; double c, d, gc; boolean cad = false; int m_var_r = 0; int m_var_s = -1; if(opt_through) { optimize(); } for(m_var_r = 0; m_var_r < _m - 1; m_var_r++) { m_var_s++; cad = false; for(l = m_var_r; l < _m; l++) { if((_matrix[m_var_r][m_var_s] != 0)) { break; } if(l == _m - 1) { swapRows(m_var_r, _m - 1); cad = true; } swapRows(m_var_r, _m - l); } if(cad) { m_var_r--; continue; } c = _matrix[m_var_r][m_var_s]; for(i = m_var_r; i < _m - 1; i++) { d = _matrix[i + 1][m_var_s]; for(j = m_var_r; j < _n; j++) { _matrix[i + 1][j] = (c * _ _matrix[i + 1][j]) - (_matrix[m_var_r][j] * d); } if(opt_through) { gc = gcdv(_matrix[i + 1], _ m_var_r, _n - 1); for(j = m_var_r; j < _n && _ gc != 0; j++) { _matrix[i + 1][j] = _ _matrix[i + 1][j] / Math.abs(gc); } } } } }
Znáte původní objektovou konvenci Microsoftu? Jestli ano, určitě jste poznali, že je kód vytržený z nějaké třídy, protože soukromé vnitřní proměnné bylo kdysi dohodnuto označovat underscorem v prvním znaku identifikátoru – „private: int _example=0;“
_matrix je tedy ona matice samotná
_m je počet řádků
_n je počet sloupců
m_var_r a m_var_s jsou proměnné, které identifikují aktuální levý horní roh matice
Na začátku se zkrátí řádky (užitečné pro matici náhodných čísel typu 10 10, kterou někdo z legrace vynásobil číslem 678). Nabíhá hlavní loop, který posouvá horní roh, následován několika smyčkami a podmínkami, které kontrolují, zda-li se vyskytuje na aktuální pozici našeho primárního řádku (ten, který se „opisuje“) nula. Pakliže ano, prohodí s posledním a zknotroluje. Takto postupuje vystřídaje všechny řádky a pokud nenalezne žádné nenulové číslo, dekrementuje řádkový čítač (protože se ve foru bežně inkementuje a my chceme zůstat na stejné řádce, abychom se mohli posunout doprava) a pokračuje zpět na hlavičku prvního řádkového foru, potom se inkrementuje sloupcový čítač a opět se kontrolují nuly ve sloupci.
Pokud nalezne nenulové číslo, program přejde do druhé části, kde se aktuální sloupec nuluje (klasicky alfa bé mínus beta á), přičemž každý nově vzniklý řádek zkouší zkrátit (pokud to má zadáno oním boolem v parametrech). No a to je v podstatě všechno. Kód spadne pouze pro pro matice typu (m, 1) nebo (1, n), neboť ty se nedají eliminovat.
Teď koukám, na co jsem zapomněl… zapomněl jsem na proměnnou cad. Cad protože column already done a slouží jako dablbrejk :-).
Je pravděpodobné, že jsou tam zbytečné nebo dále optimalizovatelné kroky, ale vem to čert. Funguje to, a celkem rychle. Matici 100 na 100 s čísly od 0 do 10 zeliminatí za pár vteřin… akorát to zarovnání je potom takové… no… zřete :-)…
/ 7.0 8.0 10.0 2.0 6.0 3.0 9.0 3.0 9.0 1.0 | 5.0 5.0 1.0 10.0 9.0 9.0 5.0 6.0 7.0 0.0 | 9.0 10.0 1.0 6.0 10.0 3.0 9.0 5.0 2.0 8.0 | 5.0 1.0 3.0 2.0 1.0 6.0 1.0 3.0 2.0 3.0 | 5.0 10.0 2.0 9.0 10.0 1.0 3.0 5.0 5.0 2.0 | 8.0 8.0 3.0 8.0 2.0 10.0 1.0 10.0 4.0 9.0 | 9.0 8.0 4.0 8.0 9.0 2.0 0.0 5.0 3.0 3.0 | 9.0 4.0 3.0 3.0 6.0 9.0 2.0 5.0 1.0 3.0 | 1.0 2.0 8.0 10.0 0.0 5.0 6.0 7.0 2.0 5.0 \ 0.0 0.0 1.0 6.0 5.0 7.0 4.0 2.0 8.0 10.0 / 7.0 8.0 10.0 2.0 6.0 3.0 9.0 3.0 9.0 1.0 | 0.0 -5.0 -43.0 60.0 33.0 48.0 -10.0 27.0 4.0 -5.0 | 0.0 0.0 47.0 0.0 -2.0 18.0 10.0 2.0 49.0 -35.0 | 0.0 0.0 0.0 2632.0 1544.0 2601.0 176.0 1229.0 2169.0 ... | 0.0 0.0 0.0 0.0 6312.0 5843.0 18448.0 -625.0 7459.0 ... | 0.0 0.0 0.0 0.0 0.0 -15857.0 -24598.0 -5237.0 -10999... | 0.0 0.0 0.0 0.0 0.0 0.0 22017.0 4380.0 9081.0 -15604... | 0.0 0.0 0.0 0.0 0.0 0.0 0.0 26961.0 8682.0 -98101.0 | 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -10579.0 11283.0 \ 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -1.0
Nyní ještě slíbené příklady. Oba dva lze najít ve skriptech pana Olšáka. Zde jsou ale rozepsané podrobně tak, jak je můj program počítal:
/ 2.0 -2.0 1.0 0.0 3.0 4.0 | -4.0 4.0 -1.0 1.0 -7.0 -11.0 | 4.0 -4.0 5.0 1.0 7.0 -3.0 \ -6.0 6.0 -4.0 1.0 -12.0 -7.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 2.0 2.0 -2.0 -6.0 | 4.0 -4.0 5.0 1.0 7.0 -3.0 \ -6.0 6.0 -4.0 1.0 -12.0 -7.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 1.0 1.0 -1.0 -3.0 | 0.0 0.0 6.0 2.0 2.0 -22.0 \ -6.0 6.0 -4.0 1.0 -12.0 -7.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 1.0 1.0 -1.0 -3.0 | 0.0 0.0 3.0 1.0 1.0 -11.0 \ 0.0 0.0 -2.0 2.0 -6.0 10.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 1.0 1.0 -1.0 -3.0 | 0.0 0.0 0.0 2.0 -4.0 2.0 \ 0.0 0.0 3.0 1.0 1.0 -11.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 1.0 1.0 -1.0 -3.0 | 0.0 0.0 0.0 1.0 -2.0 1.0 \ 0.0 0.0 0.0 -2.0 4.0 -2.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 1.0 1.0 -1.0 -3.0 | 0.0 0.0 0.0 1.0 -2.0 1.0 \ 0.0 0.0 0.0 0.0 0.0 0.0 / 2.0 -2.0 1.0 0.0 3.0 4.0 | 0.0 0.0 1.0 1.0 -1.0 -3.0 | 0.0 0.0 0.0 1.0 -2.0 1.0 \ 0.0 0.0 0.0 0.0 0.0 0.0
A ještě jeden.
/ 1.0 2.0 3.0 1.0 1.0 | 2.0 4.0 7.0 7.0 4.0 | 1.0 0.0 2.0 0.0 -2.0 \ 3.0 7.0 10.0 6.0 7.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 0.0 1.0 5.0 2.0 | 1.0 0.0 2.0 0.0 -2.0 \ 3.0 7.0 10.0 6.0 7.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 0.0 1.0 5.0 2.0 | 0.0 -2.0 -1.0 -1.0 -3.0 \ 3.0 7.0 10.0 6.0 7.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 0.0 1.0 5.0 2.0 | 0.0 -2.0 -1.0 -1.0 -3.0 \ 0.0 1.0 1.0 3.0 4.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 1.0 1.0 3.0 4.0 | 0.0 0.0 1.0 5.0 5.0 \ 0.0 0.0 1.0 5.0 2.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 1.0 1.0 3.0 4.0 | 0.0 0.0 1.0 5.0 5.0 \ 0.0 0.0 1.0 5.0 2.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 1.0 1.0 3.0 4.0 | 0.0 0.0 1.0 5.0 5.0 \ 0.0 0.0 0.0 0.0 -3.0 / 1.0 2.0 3.0 1.0 1.0 | 0.0 1.0 1.0 3.0 4.0 | 0.0 0.0 1.0 5.0 5.0 \ 0.0 0.0 0.0 0.0 -1.0
gratuluju, to je výzva, pustím se do toho taky :-)
„následován několika smyčkami a podmínkami, které kontrolují, zda-li se vyskytuje na aktuální pozici našeho primárního řádku (ten, který se „opisuje“) nula. Pakliže ano, prohodí s posledním a zknotroluje. Takto postupuje vystřídaje všechny řádky a pokud nenalezne žádné nenulové číslo“
Nestudoval jsem kód, ale tohle jsem dělal taky. Mělo to ale nějaký mouchy – aspoň v tom mým případě – tak jsem to dělal tak, že pokud tam byla 0, tak jsem nezačal prohozením, ale prohazoval jsem až když bylo co prohazovat. Tzn. v cyklu jsem procházel ty řádky a hledal nenulu. Pokud jsem jí nenašel, sloupec je již vynulovaný, není třeba nulovat a vycontinuoval jsem tu jednu smyčku. Pokud našel, tak samo swap.
A ještě: Nepomůže se zarovnáním odsazovat tabulátorem? Zeliminuje, ne zeliminatí. Jestli to byl vtip, tak pardon, vtipy v algebře se dost těžko rozpoznávaji. :o)) Jo a ta tvoje notace je fakt hnusná, vypadá prehistoricky. :o)
Tabulátor standardně odsazuje osm znaků, což se v javě nedá změnit. Ano, v javě se toho nedá spoustu a každou vteřinu někdo na světě objeví věc, která se v javě nedá :).
Eliminatit říká někdo z přednášejících… nejsem si jistý, jestli doktor Olšák nebo někdo jiný.
Zdá se ti hnusná, ale hnusná není. Ti, kdo ji používali pro to měli dobrý důvod. I kdyby ten důvod už neexistoval, existuje něco jako tradice… to je třeba proč se v čechách slaví Vánoce, i když jsou češi většinou bezvěrci. Protože to někdo dělal kdysi a bylo to dobré, není důvod s tím přestávat, protože si nějaký idiot vymyslel Santu a jeho teplou dílnu.
Stejně tak, protože nějaký homosexuální inženýr ze Sun microsystems vymyslel javu, nepřestanu používat to, co se kdysi používalo v céčku. Nějaká komunistická normalizace, kterou Sun praktikuje se mě netýká. Kód má být dílo, ve kterém poznáš autora stejně, jako ho poznáš v obrazech, nikoli unifikovaný kus vypadající, jako kdyby vypadl z linky.
A co se týče přehlednosti, rychlosti a jednoduchosti – hodnot dnešní společnosti, promítajích se i sem -, ty mě nezajímají o nic víc než Agáta Hanychová.
Když hodnoty společnosti upadají společně s těmi, kdo je posuzují, nezbýva, než se držet hodnot minulých let a roli v tom hraje i zdánlivě nepodstatná věc, jako je podtržítko.
Bohužel to bude pokračovat, dokud se na planetě zemi budou vyskytovat lidé, kteří při pohledu zpátky užívají slovo nemoderní, a to bez kapky respektu. Lidé hrdí na svůj v číně vyrobený mp3 přehrávač při pohledu na gramofon.
A takových je většina. He he he, děrnej štítek. He he he, suchej záchod.
Ale co, populace stoupá, tak budeme vyhlížet to, co logicky musí přijít, protože populace nemůže stoupat do nekonečna. Musí přijít regulace a taková, kterou podnítí příroda… nenormalizovaná
Nenormalizovaná. Taková, která nepíše závorku tam, kam by ji psát měla.
Tím samozřejmě nenám na mysli tebe, aby nedošlo k nedorozumění :-).