Доказательство

Доказательство Доказательство Доказательство В матричном виде это эквивалентно следующему выражению: \begin{equation*} \Omega(\boldsymbol{x^*}) \boldsymbol{J}(\boldsymbol{x^*}) = \boldsymbol{E} \end{equation*} где матрица $\boldsymbol{J}$ является матрицей Якоби: \begin{equation*} \boldsymbol{J}(\boldsymbol{x}) = \begin{bmatrix} \frac{\partial f_1(\boldsymbol{x})}{\partial x_1} & \dots & \frac{\partial f_1(\boldsymbol{x})}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial f_n(\boldsymbol{x})}{\partial x_1} & \dots & \frac{\partial f_n(\boldsymbol{x})}{\partial x_n} \end{bmatrix}. \end{equation*} Для квадратичной сходимости в качестве $\Omega(\boldsymbol{x})$ мы можем выбрать: \begin{equation*} \Omega(\boldsymbol{x}) = \boldsymbol{J}^{-1}(\boldsymbol{x}), \end{equation*} что дает метод Ньютона для систем нелинейных алгебраических уравнений: \begin{equation*} \boldsymbol{x}^{(k)} = \boldsymbol{g}(\boldsymbol{x}^{(k)}) = \boldsymbol{x}^{(k-1)} - \boldsymbol{J}^{-1}(\boldsymbol{x}^{(k-1)}) \boldsymbol{f}(\boldsymbol{x}^{(k-1)}). \end{equation*} Заметим, что:

• требуется вычисление $\boldsymbol{J}^{-1}(\boldsymbol{x}^{(k-1)})$ на каждом шаге
• необходим альтернативный подход.

На практике используется двухшаговая процедура: \begin{align*} \boldsymbol{J}(\boldsymbol{x}^{(k-1)}) \boldsymbol{y}^{(k-1)} = \boldsymbol{f}(\boldsymbol{x}^{(k-1)}), \\ \boldsymbol{x}^{(k)} = \boldsymbol{x}^{(k-1)} - \boldsymbol{y}^{(k-1)}, \end{align*} где $\boldsymbol{y}^{(k-1)}$ находится через решение первого уравнения. Обобщение на многомерный случай имеет вид: \begin{equation*} \begin{split} &f'(x^{(1)}) \left( x^{(1)} - x^{(0)} \right) \approx f(x^{(1)}) - f(x^{(0)}) \\ \Longrightarrow \quad &\boldsymbol{J}(\boldsymbol{x}^{(1)}) \left( \boldsymbol{x}^{(1)} - \boldsymbol{x}^{(0)} \right) \approx \boldsymbol{f}(\boldsymbol{x}^{(1)}) - \boldsymbol{f}(\boldsymbol{x}^{(0)}). \end{split} \end{equation*} Введем обозначение для аппроксимации матрицы Якоби: \begin{equation*} \boldsymbol{A}_1 \approx \boldsymbol{J}(\boldsymbol{x}^{(1)}) \end{equation*} Тогда мы получаем следующее равенство: \begin{equation*} \boldsymbol{A}_1 \left( \boldsymbol{x}^{(1)} - \boldsymbol{x}^{(0)} \right) = \boldsymbol{f}(\boldsymbol{x}^{(1)}) - \boldsymbol{f}(\boldsymbol{x}^{(0)}). \end{equation*} Заметим, что в $n$-мерном пространстве:

• поведение $\boldsymbol{A}_1$ определено только в направлении $\boldsymbol{x}^{(1)} - \boldsymbol{x}^{(0)}$;
• логично предположить, что для всех ортогональных направлений: \begin{equation*} \boldsymbol{A}_1 \boldsymbol{z} = \boldsymbol{J}(\boldsymbol{x}^{(0)}) \boldsymbol{z}, \quad \langle \boldsymbol{x}^{(1)} - \boldsymbol{x}^{(0)}, \boldsymbol{z} \rangle = 0. \end{equation*}

Найдем выражение для $\boldsymbol{A}_k^{-1}$, используя формулу Шермана–Моррисона: Метод Бройдена \begin{align*} \boldsymbol{A}_k^{-1} &= \boldsymbol{A}_{k-1}^{-1} - \frac{\left( \boldsymbol{A}_{k-1}^{-1} \boldsymbol{y}_k - \boldsymbol{s}_k \right) \boldsymbol{s}_k^T \boldsymbol{A}_{k-1}^{-1}}{\boldsymbol{s}_k^T \boldsymbol{A}_{k-1}^{-1} \boldsymbol{y}_k}, \\ \boldsymbol{x}^{(k+1)} &= \boldsymbol{x}^{(k)} - \boldsymbol{A}_k^{-1} \boldsymbol{f}(\boldsymbol{x}^{(k)}). \end{align*} Особенности

• $\boldsymbol{A}_k^{-1}$ рассчитывается, используя $\boldsymbol{A}_{k-1}^{-1}$ и перемножения "матрица-вектор";
• это требует только $O(n^2)$ операций.