Metoda Broydena

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Zastosowanie[edytuj | edytuj kod]

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

f_k(x_1,x_2,\ldots,x_n) = 0,  k = 1,2, \ldots ,n

Opis metody[edytuj | edytuj kod]

W algorytmie Broydena najpierw dla danego (z góry) początkowego przybliżenia rozwiązania x^{(0)} = (x_1^{(0)},x_2^{(0)},\ldots,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} 
{{\partial f_1(x)} \over {\partial x_1}} & {{\partial f_1(x)} \over {\partial x_2}} & \cdots & {{\partial f_1(x)} \over {\partial x_n}} \\
{{\partial f_2(x)} \over {\partial x_1}} & {{\partial f_2(x)} \over {\partial x_2}} & \cdots & {{\partial f_2(x)} \over {\partial x_n}} \\
\cdots & \cdots & \cdots & \cdots \\
{{\partial f_n(x)} \over {\partial x_1}} & {{\partial f_n(x)} \over {\partial x_2}} & \cdots & {{\partial f_n(x)} \over {\partial x_n}} \\
\end{bmatrix}

Następnie wyznacza się przybliżenie x^{(1)} = (x_1^{(1)},x_2^{(1)},\ldots,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), \ldots , 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} + {{(s_i - A_{i-1}^{-1}y_i)s_i^TA_{i-1}^{-1}} \over {s_i^TA_{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

\left \Vert A_i^{-1}f(x^{(i)}) \right \| < t

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