Metoda Broydena

Ten artykuł należy dopracować: od 2016-07 → zweryfikować treść i dodać przypisy, → napisać/poprawić definicję. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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

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

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

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

gdzie Df jest macierzą Jacobiego w postaci

${\displaystyle 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 ${\displaystyle x^{(1)}=(x_{1}^{(1)},x_{2}^{(1)},\dots ,x_{n}^{(1)})^{T}}$ na podstawie wzoru

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

gdzie ${\displaystyle 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

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

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

${\displaystyle 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:

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

Algorytm kończy się, gdy

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

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

Można również skorzystać ze wzoru wykorzystującego iloczyn Kroneckera i iloczyn skalarny (${\displaystyle \otimes }$ i ${\displaystyle \cdot }$)^[1].

wybieramy wektor startowy ${\displaystyle x_{(0)}}$

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

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

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

${\displaystyle i=0}$

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

${\displaystyle t^{(i)}=A_{i}^{-1}f(x^{(i+1)})}$

${\displaystyle q_{i}=s^{(i)}\cdot (s^{(i)}+t^{(i)})}$

${\displaystyle A_{i+1}^{-1}=A_{i}^{-1}-{\frac {1}{q_{i}}}(t^{(i)}\otimes s^{(i)})A_{i}^{-1}}$

${\displaystyle i=i+1}$

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

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