Метод Бройдена

метод Бройдена - є квазіньютоновим методом для знаходження коренів у k змінних. Вперше він був описаний Ч. Г. Бройденом у 1965 році

Метод Ньютона для вирішення f(x) = 0 використовує обчислення якобіана матриці J, на кожній ітерації. Однак обчислення якобіана є важкою та дорогою операцією. Ідея методу Бройдена в тому, щоб обчислювати весь якобіан лише на першій ітерації та використовувати розв'язок рівняння хорди на інших ітераціях.

У 1979 році Девід М. Гей довів, що коли метод Бройдена застосовується до лінійної системи розміром n × n, він завершується за 2 n кроки, хоча, як і всі квазіньютоновські методи, він може не сходитися для нелінійних систем.

Опис методу

Розв’язування рівняння з однією змінною

У методі хорд ми замінюємо першу похідну f′ на x_n кінцево-різницевим наближенням:

$f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}},$

і діяємо подібно до методу Ньютона :

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f^{\prime }(x_{n})}}$

де n індекс ітерації.

Розв’язування системи нелінійних рівнянь

Розглянемо систему з k нелінійних рівнянь

$\mathbf {f} (\mathbf {x} )=\mathbf {0} ,$

де f — вектор-функція вектора x :

$\mathbf {x} =(x_{1},x_{2},x_{3},\dotsc ,x_{k}),$

$\mathbf {f} (\mathbf {x} )={\big (}f_{1}(x_{1},x_{2},\dotsc ,x_{k}),f_{2}(x_{1},x_{2},\dotsc ,x_{k}),\dotsc ,f_{k}(x_{1},x_{2},\dotsc ,x_{k}){\big )}.$

Для таких задач Бройден дає узагальнення одновимірного методу Ньютона, замінюючи похідну якобіаном J . Матриця Якобі визначається ітеративно на основі рівняння хорди в кінцево-різницевому наближенні:

$\mathbf {J} _{n}(\mathbf {x} _{n}-\mathbf {x} _{n-1})\simeq \mathbf {f} (\mathbf {x} _{n})-\mathbf {f} (\mathbf {x} _{n-1}),$

де n індекс ітерації. Для наочності визначимо:

$\mathbf {f} _{n}=\mathbf {f} (\mathbf {x} _{n}),$

$\Delta \mathbf {x} _{n}=\mathbf {x} _{n}-\mathbf {x} _{n-1},$

$\Delta \mathbf {f} _{n}=\mathbf {f} _{n}-\mathbf {f} _{n-1},$

тому вищезазначене можна переписати як

$\mathbf {J} _{n}\Delta \mathbf {x} _{n}\simeq \Delta \mathbf {f} _{n}.$

Наведене вище рівняння є недовизначеним, якщо k більше одиниці. Бройден пропонує використати поточну оцінку матриці Якобі J_n−1 і вдосконалити її, взявши розв'язок рівняння хорди, яке є мінімальною модифікацією J_n−1 :

$\mathbf {J} _{n}=\mathbf {J} _{n-1}+{\frac {\Delta \mathbf {f} _{n}-\mathbf {J} _{n-1}\Delta \mathbf {x} _{n}}{\|\Delta \mathbf {x} _{n}\|^{2}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }.$

Це мінімізує наступну норму Фробеніуса :

$\|\mathbf {J} _{n}-\mathbf {J} _{n-1}\|_{\rm {F}}.$

і ми можемо рухатися подібно до метода Ньютона:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\mathbf {J} _{n}^{-1}\mathbf {f} (\mathbf {x} _{n}).$

Бройден також запропонував використовувати формулу Шермана-Моррісона для знаходження якобіана зворотної матриці Якобі:

$\mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}}\Delta \mathbf {x} _{n}^{\mathrm {T} }\mathbf {J} _{n-1}^{-1}.$

Цей метод широко відомий як «хороший метод Бройдена».

Подібний результат можна отримати, використовуючи трохи іншу модифікацію J_n−1 . Це дає другий метод, так званий «поганий метод Бройдена» (але див. ):

$\mathbf {J} _{n}^{-1}=\mathbf {J} _{n-1}^{-1}+{\frac {\Delta \mathbf {x} _{n}-\mathbf {J} _{n-1}^{-1}\Delta \mathbf {f} _{n}}{\|\Delta \mathbf {f} _{n}\|^{2}}}\Delta \mathbf {f} _{n}^{\mathrm {T} }.$

Це мінімізує іншу норму Фробеніуса:

$\|\mathbf {J} _{n}^{-1}-\mathbf {J} _{n-1}^{-1}\|_{\rm {F}}.$

Багато інших квазіньютонівських схем було запропоновано в оптимізації, де шукають максимум або мінімум, знаходячи корінь першої похідної ( градієнт у багатьох вимірах). Якобіан градієнта називається Гессіаном і є симетричним, що додає додаткові обмеження для його оновлення.

Клас методів Бройдена

На додаток до двох методів, описаних вище, Бройден визначив цілий клас споріднених методів. ^:578Загалом, методи в класі Бройдена задаються у формі ^:150

$$\mathbf {J} _{k+1}=\mathbf {J} _{k}-{\frac {\mathbf {J} _{k}s_{k}s_{k}^{T}\mathbf {J} _{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}s_{k}}}+\phi _{k}\left(s_{k}^{T}\mathbf {J} _{k}s_{k}\right)v_{k}v_{k}^{T},$$

де $y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),$$s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},$ та

$$v_{k}=\left[{\frac {y_{k}}{y_{k}^{T}s_{k}}}-{\frac {\mathbf {J} _{k}s_{k}}{s_{k}^{T}\mathbf {J} _{k}s_{k}}}\right],$$

і $\phi _{k}\in \mathbb {R}$ для кожного $k=1,2,...$ . Вибір $\phi _{k}$ визначає метод.

</br> Інші методи в класі Бройдена були представлені іншими авторами.

• Метод Девідона–Флетчера–Пауелла (DFP) є єдиним членом цього класу, опублікованим до двох методів, визначених Бройденом. ^:582Для методу DFP, $\phi _{k}=1$ . ^:150
• Алгоритм Шуберта або розріджений Бройдена – модифікація для розріджених матриць Якобі.
• Klement (2014) – використовує менше ітерацій для вирішення багатьох систем рівнянь.

Дивись також

• Метод січної
• Метод Ньютона
• Метод квазіньютона
• Метод Ньютона в оптимізації
• Формула Девідона-Флетчера-Пауелла
• Метод Бройдена–Флетчера–Голдфарба–Шенно (BFGS).

Література

• Dennis, J. E.; Schnabel, Robert B. (1983). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Englewood Cliffs: Prentice Hall. с. 168—193. ISBN 0-13-627216-9.
• Fletcher, R. (1987). Practical Methods of Optimization (вид. Second). New York: John Wiley & Sons. с. 44–79. ISBN 0-471-91547-5.

Зовнішні посилання

• Просте базове пояснення: історія про сліпого стрільця