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

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

Метод Ньютона для розв'язання системи рівнянь $\displaystyle f_{i}(x_{1},x_{2},\ldots ,x_{n})=0$, де $i=1,2,\ldots ,n$, використовує обчислення якобіана матриці J на кожній ітерації. Однак обчислення якобіана є важкою та дорогою операцією. Ідея методу Бройдена в тому, щоб обчислювати весь якобіан лише на першій ітерації та використовувати розв'язок методом хорд на наступних ітераціях.

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

Опис методу

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

У методі хорд ми замінюємо першу похідну 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}$ визначає метод.

Інші методи в класі Бройдена були представлені іншими авторами:

• Метод Девідона–Флетчера–Пауелла (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.

Посилання

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