Metoda Broydena

Zastosowanie

Procedura Broydena służy do przybliżonego rozwiązania układów n równań nieliniowych postaci:

$f\_k(x\_1,x\_2,dots,x\_n)\; =\; 0,\; quad\; k\; =\; 1,2,\; dots,\; n.$

Opis metody

Algorytm Broydena zaczyna się od przyjęcia początkowego przybliżenia rozwiązania $x^\{(0)\}\; =\; (x\_1^\{(0)\},\; x\_2^\{(0)\},dots,\; x\_n^\{(0)\})^T$. Następnie wyznacza się macierz Jacobiego:

$A\_0^\{-1\}\; =\; [Df(x^\{(0)\})]^\{-1\},$

gdzie $Df(x)$ jest macierzą Jacobiego składającą się z pochodnych funkcji $f\_k$.

Kolejne kroki obliczania przybliżeń są następujące:

• Oblicz $x^\{(1)\}\; =\; x^\{(0)\}\; –\; A\_0^\{-1\}f(x^\{(0)\}).$
• Wyznaczaj kolejne przybliżenia z zależności $x^\{(i+1)\}\; =\; x^\{(i)\}\; –\; A\_i^\{-1\}f(x^\{(i)\}).$
• Macierz $A\_i^\{-1\}$ oblicza się z wzoru:

$A\_i^\{-1\}\; =\; A\_\{i-1\}^\{-1\}\; +\; frac\{(s\_i\; –\; A\_\{i-1\}^\{-1\}y\_i)s\_i^TA\_\{i-1\}^\{-1\}\}\{s\_i^TA\_\{i-1\}^\{-1\}y\_i\},$

• gdzie $y\_i\; =\; f(x^\{(i)\})\; –\; f(x^\{(i-1)\})$ oraz $s\_i\; =\; x^\{(i)\}\; –\; x^\{(i-1)\}.$

Algorytm kończy się, gdy spełniony jest warunek:

gdzie $t$ to zadana tolerancja błędu lub gdy osiągnięta zostanie maksymalna liczba iteracji.

Metoda alternatywna

Alternatywna wersja metody korzysta z iloczynu Kroneckera i iloczynu skalarnego:

• Wybierz wektor startowy $x\_\{(0)\}$.
• Oblicz macierz Jacobiego $A\_0\; =\; Df(x^\{(0)\})$.
• Wyznacz $s^\{(0)\}\; =\; -A\_0^\{-1\}\; f(x^\{(0)\})$.
• Oblicz pierwsze przybliżenie: $x^\{(1)\}\; =\; x^\{(0)\}\; +\; s^\{(0)\}.$

Powtarzaj kroki, aż $s^\{(i)\}$ będzie miało wystarczająco małą normę:

• $t^\{(i)\}\; =\; A\_i^\{-1\}\; f(x^\{(i+1)\})$.
• $q\_i\; =\; s^\{(i)\}\; cdot\; (s^\{(i)\}\; +\; t^\{(i)\})$.
• $A\_\{i+1\}^\{-1\}\; =\; A\_i^\{-1\}\; –\; frac\{1\}\{q\_i\}(t^\{(i)\}\; otimes\; s^\{(i)\})A\_i^\{-1\}$.
• Zwiększ $i$ o 1 i oblicz $s^\{(i)\}\; =\; A\_i^\{-1\}\; f(x^\{(i)\})$ oraz $x^\{(i+1)\}\; =\; x^\{(i)\}\; +\; s^\{(i)\}.$

Przypisy

Kategoria: Algebra liniowa