Java – Gaussova Eliminační Metoda 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
