Metoda Broydena

Zastosowanie

Procedura Broydena znajduje przybliżone wartości składowych rozwiązania układu n równań nieliniowych postaci

$f_{k}(x_{1},x_{2},\dots ,x_{n})=0,\quad k=1,2,\dots ,n.$

Opis metody

W algorytmie Broydena najpierw dla danego (z góry) początkowego przybliżenia rozwiązania $x^{(0)}=(x_{1}^{(0)},x_{2}^{(0)},\dots ,x_{n}^{(0)})^{T}$ wyznacza się macierz

$A_{0}^{-1}=[Df(x^{(0)})]^{-1},$

gdzie Df jest macierzą Jacobiego w postaci

$Df(x)={\begin{bmatrix}{\frac {\partial f_{1}(x)}{\partial x_{1}}}&{\frac {\partial f_{1}(x)}{\partial x_{2}}}&\cdots &{\frac {\partial f_{1}(x)}{\partial x_{n}}}\\{\frac {\partial f_{2}(x)}{\partial x_{1}}}&{\frac {\partial f_{2}(x)}{\partial x_{2}}}&\cdots &{\frac {\partial f_{2}(x)}{\partial x_{n}}}\\\vdots &\vdots &\cdots &\vdots \\{\frac {\partial f_{n}(x)}{\partial x_{1}}}&{\frac {\partial f_{n}(x)}{\partial x_{2}}}&\cdots &{\frac {\partial f_{n}(x)}{\partial x_{n}}}\end{bmatrix}}.$

Następnie wyznacza się przybliżenie $x^{(1)}=(x_{1}^{(1)},x_{2}^{(1)},\dots ,x_{n}^{(1)})^{T}$ na podstawie wzoru

$x^{(1)}=x^{(0)}-A_{0}^{-1}f(x^{(0)}),$

gdzie $f(x)=(f_{1}(x),f_{2}(x),\dots ,f_{n}(x))^{T}.$

Kolejne przybliżenia rozwiązania zadanego układu równań oblicza się z zależności

$x^{(i+1)}=x^{(i)}-A_{i}^{-1}f(x^{(i)}),$

przy czym macierz $A_{i}^{-1}$ wyznacza się na podstawie znajomości macierzy $A_{i-1}^{-1}$ i dwóch poprzednich przybliżeń rozwiązania

$A_{i}^{-1}=A_{i-1}^{-1}+{\frac {(s_{i}-A_{i-1}^{-1}y_{i})s_{i}^{T}A_{i-1}^{-1}}{s_{i}^{T}A_{i-1}^{-1}y_{i}}},$

gdzie:

$y_{i}=f(x^{(i)})-f(x^{(i-1)}),$ $s_{i}=x^{(i)}-x^{(i-1)}.$

Algorytm kończy się, gdy

$\|A_{i}^{-1}f(x^{(i)})\|<t,$

gdzie $\|\|$ oznacza normę euklidesową, a $t$ – zadaną tolerancję błędu, lub gdy zostanie przekroczona maksymalna dozwolona liczba iteracji.

Metoda alternatywna

Można również skorzystać ze wzoru wykorzystującego iloczyn Kroneckera i iloczyn skalarny ($\otimes$ i $\cdot$).

wybieramy wektor startowy $x_{(0)}$

$A_{0}=Df(x^{(0)})$ – macierz Jacobiego

$s^{(0)}=-A_{0}^{-1}f(x^{(0)})$

$x^{(1)}=x^{(0)}+s^{(0)}$

$i=0$

powtarzaj 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}$

$i=i+1$

$s^{(i)}=A_{i}^{-1}f(x^{(i)})$

$x^{(i+1)}=x^{(i)}+s^{(i)}$