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,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)=\left[\begin{array}{cccc}\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}\\ ⋮& ⋮& \cdots & ⋮\\ \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{array}\right].$

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

$\Vert A_i^{-1}f(x^{(i)})\Vert <t,$

gdzie $\Vert \Vert$ 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)}$