Gauss-Seidelova metóda

Gauss-Seidelova metóda je iteračná metóda na výpočet sústavy lineárnych rovníc (SLR).

Vlastnosti

  1. Rýchlejšia ako Jacobiho metóda, ale môže divergovať, aj keď Jacobiho konverguje.
  2. V každej iterácii je najpracnejšou operáciou násobenie matice a vektora. Je podstatne jednoduchšia, ako Gaussova eliminačná metóda.
  3. Iteračné metódy sú menej citlivé na zaokrúhľovacie chyby, než priame metódy. Pokiaľ v ďalšom výpočte dôjde ku konvergencii, predošlé chyby výpočtu vymiznú.

Pre matice s rozmerom n > 10 000 sa odporúča použiť iteračné metódy, inak Gaussovú eliminačnú metódu.

Odlišnosť od Jacobiho metódy

Výpočet prebieha podobne ako u jacobiho metódy s tým rozdielom, že nasledujúcu zložku transponovaného vektora počítame priebežne dosadením predošlej zložky:

  1. 11x1 +  2x2 +   x3 = 15 // x1 dosadíme do 2.
  2.    x1 + 10x2 + 2x3 = 16 // x1 z 1. a x2 z 2. dosadíme do 3.
  3.  2x1 +   3x2 - 8x3 =   1

Algoritmus

  1. Vstupy - rovnaké ako u Jacobiho metóde, aii != 0
  2. Vyjadríme i-tu neznámu:
    • xik+1 = (1/aii).(bi - ∑j=1i-1(aijxjk+1) -∑j=i+1n(aijxjk)),
    • pre k = 0,1,2,...,
    • pre i = 1,...,n,
    • opakuj 2., kým ||xk+1 - xk|| > ε.
  3. Výstup: xk+1 = (xik+1).

Implementácia

SLR: (chýbajúce premenné v riadku zapíšte v tvare 0xindex)

ε
desatinných miest

JavaScript kód

$("#gauss").submit(function(e) {
 	$.post("php/ulohy/slr-gauss.php", $(this).serialize(), function(vystup) {
		$("#konzola").html(vystup)		
	});
});

PHP kód

<?php
function konvertuj($cislo)
{
	if (empty($cislo) || $cislo === '+') return 1;
	if ($cislo === '-') return -1;
	return intval($cislo);
}

//vstup z jquery
$slr = $_POST['vstup'];  
$miest =  intval($_POST['zaokruhlenie']);
if ($_POST['presnost'] < 0) die('ε > 0');

$slr = trim($slr);
$slr = str_replace(' ','',$slr);
$riadky = explode("\n", $slr);

foreach($riadky as $riadok)
{
	$riadok = explode("=", $riadok);
	$l[] = $riadok[0];
	$p[] = intval($riadok[1]); //prava strana rovnice
}

foreach($l as $i => $riadok)
{
	preg_match_all("/(.*?)x([0-9]+)/", $riadok, $hodnoty);	
	$hodnoty[1] = array_map('konvertuj', $hodnoty[1]);

	foreach ($hodnoty[2] as $j => $index) //index premennej
	{
		//prehod premennu na zaciatok riadku
		if ($index == $i+1) {
			$lava_strana = $hodnoty[1][$j]; //vytiahne x z vyrazu
			unset($hodnoty[1][$j]); //zmaze vybrate x z vyrazu
			//array_splice($hodnoty[1], $j, 1); //to iste ako unset + prepise indexy
		}
		//prehod znamienka ostatnych clenov
		else $hodnoty[1][$j] *= -1;
	}
	
	//vlozi pravu stranu rovnice na zaciatok lavej strany
	array_unshift($hodnoty[1], array_shift($p));	
	//vydeli vsetky prvky lavou stranou
	foreach($hodnoty[1] as $j => $val) $hodnoty[1][$j] /= $lava_strana;
	//resetujeme kluce, nech medzi nimi nie je medzera z vybrateho x
	$matica[] = array_values($hodnoty[1]);
}

//$p je vyprazdnene

//hlavny vypocet
$riadkov = count($matica);
$stlpcov = count($matica[0]);
$x = array_fill(0,$stlpcov,0); //pociatocna aproximacia
$k = 0;
$x_tmp = $x;
echo "x<sup>$k</sup> = (".implode('; ', $x).")<sup>T</sup><br />";

for (;;)
{
	$k++;
	$tmp_matica = $matica;
	for ($i = 0; $i < $riadkov; $i++)
	{
		$index = 0;
		for ($j = 1; $j < $stlpcov; $j++) {
			if ($index == $i) $index++;
			$tmp_matica[$i][$j] *= $x_tmp[$index]; //prenasobi riadok vektorom
			$index++;
		}
		//gauss-seidel
		$x_tmp[$i] = round(array_sum($tmp_matica[$i]), $miest); //i-ty prvok
	}
		
	echo "x<sup>$k</sup> = (".implode('; ', $x_tmp).")<sup>T</sup><br />";
	
	//ukoncovacia podmienka
	$ar = array();
	foreach ($x_tmp as $i => $val) $ar[] = $x[$i]-$x_tmp[$i];
	$ar = max(array_map('abs', $ar));
	
	if ($ar <= $_POST['presnost']) break;	
	$x = $x_tmp;
}
?>