Jacobiho metóda

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

Výhody

  1. V každej iterácii poznáme aproximáciu riešenia xk.
  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.

Maticové normy

Pri iteračných metódach meriame "veľkosť" matíc a vektorov. Norma matice je zovšeobecnením funkcie absolútnej hodnoty reálneho čísla.

Základné normy

  1. Riadková

    ||A||R = maxi=1..n(∑j=1m |aij|)

    Maximum súčtu absolútnych hodnôt v riadkoch.

  2. Stĺpcová

    ||A||S = maxj=1..m(∑i=1n |aij|)

    Maximum súčtu absolútnych hodnôt v stĺpcoch.

  3. Frobeniova

    ||A||F = √[ ∑i=1n (∑j=1m(aij)2) ]

    Druhá odmocnina zo súčtu všetkých prvkov matice umocnených na druhú.

    i - index riadkov
    j - index stĺpcov

Pr. Určte normy v matici

    1 2 3
A = 0 1 2
    -10 2 -3

 

||A||R = max(1+2+3; 0+1+2; 10+2+3) = 15
||A||S = max(1+0+10; 2+1+2; 3+2+3) = 11
||A||F = √(1+4+9+0+1+4+100+4+9) = √132 = 11,489

Algoritmus Jacobiho metódy

  1. Vstupy:
    1. matica: A = (aij)
    2. vektor pravej strany: b = (bi)
    3. počiatočná aproximácia - stĺpcová (transponovaná - T) matica: napr. x0 = (0,0,0)T
    4. požadovaná presnosť: ε; ε > 0
  2. Ak pre niektorú normu platí ||C||>=1, chyba - nie je zaručená konvergencia
    • C je iteračná matica
    • Ak máme napr. SLR:
      x1 = 15 - 10x1 - 2x2 - x3
      x2 = 16 - x1 - 9x2 - 2x3
      x3 = -1 + 2x1 + 3x2 - 7x3,

    • Potom:
          -10 -2 -1
      C = -1 -9 -2
          2 3 -7

    • Ak ||C|| < 1, metóda zaručene konverguje.
  3. Vyjadríme i-tu neznámu:
    • xik+1 = (1/aii).(bi - ∑j=1i-1(aijxjk) -∑j=i+1n(aij-xjk)),
    • pre k = 0,1,2,...,
    • pre i = 1,...,n,
    • opakuj 3., kým ||xk+1 - xk|| > ε.
  4. Výstup: xk+1 = (xik+1).

Implementácia

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

ε
platných miest

JavaScript kód

PHP kód

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

//maticove normy
function norma($matica, $typ_normy='ar') 
{
	$riadkov = count($matica);
	$stlpcov = count($matica[0]);
	for ($i = 0; $i < $riadkov; $i++)
	{
		$ar[] = array_sum(array_map('abs',$matica[$i])); //ulozi sucet riadka
		
		$tmp = 0;
		for ($j = 0; $j < $stlpcov; $j++)
		{
			$tmp += abs($matica[$j][$i]); //pripocita prvok v stlpci
			$af[] = pow($matica[$i][$j],2); //umocni kazdy prvok na druhu
		}
		
		$as[] = $tmp; //ulozi sucet stlpca
	}
	
	$ar = max($ar);
	$as = max($as);
	$af = sqrt(array_sum($af));
	
	if ($typ_normy == 'ar') $o = $ar;
	elseif ($typ_normy == 'as') $o = $as;
	elseif ($typ_normy == 'af') $o = $af;
	
	return round($o, 4);
}

//vstup z jquery
$slr = $_POST['vstup'];
//echo str_replace("\n","<br>",$slr);

$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]);

	//rydzo diagonalne dominantna matica
	$rd_matica[] = $hodnoty[1]; //je A rydzo diagonalne dominantna? Ak ano, metoda konverguje.
	
	//echo print_r($hodnoty[2])."<br />";
	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

/*
Jacobiho metóda konverguje, 
keď A je rýdzo diagonálne dominantná.
A je rýdzo diagonálne dominantná,
ak v každom riadku je
absolútna hodnota diagonálneho prvku 
väčšia ako
súčet absolútnych hodnôt
ostatných prvkov tohto riadku.

http://www.earthphysics.sk/mainpage/stud_mat/menm/prednaska4.pdf
*/
foreach($rd_matica as $i => $hodnoty)
{
	$d_prvok = abs($rd_matica[$i][$i]);
	array_splice($hodnoty, $i, 1); //odstrani d_prvok
	$zvysne = array_sum(array_map('abs', $hodnoty));
	if ($d_prvok <= $zvysne) 
	{
		echo "<p>Nie je zaručená konvergencia. Výpočet zastavený.</p>";
		die;
	}
}

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

for (;;)
{
	$k++;
	$tmp_matica = $matica;
	for ($i = 0; $i < $riadkov; $i++)
	{
		$x_tmp = $x;
		array_splice($x_tmp, $i, 1);	
		for ($j = 1; $j < $stlpcov; $j++) $tmp_matica[$i][$j] *= ($x_tmp[$j-1]);
		$tmp_matica[$i] = round(array_sum($tmp_matica[$i]), 4); //zaokruhlime na 4 miesta
	}
		
	echo "x<sup>$k</sup> = (".implode('; ', $tmp_matica).")<sup>T</sup><br />";
	
	//ukoncovacia podmienka
	$ar = array();
	foreach ($tmp_matica as $i => $val) $ar[] = $x[$i]-$tmp_matica[$i];
	$ar = max(array_map('abs', $ar));
	
	if ($ar <= $_POST['presnost']) break;	
	$x = $tmp_matica;
}
?>