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

Квазиньютоновский метод поиска корня для многомерного случая

В численном анализе метод Бройдена представляет собой квазиньютоновский метод поиска корней от k переменных. Первоначально он был описан К. Г. Бройденом в 1965 году. ^[1]

Метод Ньютона для решения f ( x ) = 0 использует матрицу Якоби J на ​​каждой итерации. Однако вычисление этого якобиана — сложная и дорогостоящая операция. Идея метода Бройдена состоит в том, чтобы вычислить весь якобиан максимум только на первой итерации и выполнить обновления первого ранга на других итерациях.

В 1979 году Гей доказал, что когда метод Бройдена применяется к линейной системе размера n × n , он завершается за 2 n шагов, ^[2] хотя, как и все квазиньютоновские методы, он может не сходиться для нелинейных систем.

Описание метода

Решение уравнения с одной переменной

В методе секущих мы заменяем первую производную f ′ в точке x _n конечно -разностным приближением:

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

и действуйте аналогично методу Ньютона :

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

где n — индекс итерации.

Решение системы нелинейных уравнений

Рассмотрим систему k нелинейных уравнений

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

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

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

${\displaystyle \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. Матрица Якоби определяется итеративно на основе уравнения секущего в конечно-разностном приближении:

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

где n — индекс итерации. Для ясности определим:

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

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

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

поэтому вышеизложенное можно переписать как

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

Приведенное выше уравнение является недоопределенным , когда k больше единицы. Бройден предлагает использовать текущую оценку матрицы Якоби J _{n −1} и улучшить ее, взяв решение уравнения секущего, которое является минимальной модификацией J _{n −1} :

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

Это минимизирует следующую норму Фробениуса :

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

Тогда мы можем продолжить в направлении Ньютона:

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

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

${\displaystyle \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} . Это дает второй метод, так называемый «метод плохого Бройдена» (см. ^[3] ):

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

Это минимизирует другую норму Фробениуса:

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

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

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

Помимо двух описанных выше методов, Бройден определил целый класс родственных методов. ^{[1] : 578} В общем случае методы класса Бройдена задаются в виде ^{[4] : 150}

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

${\displaystyle y_{k}:=\mathbf {f} (\mathbf {x} _{k+1})-\mathbf {f} (\mathbf {x} _{k}),}$ ${\displaystyle s_{k}:=\mathbf {x} _{k+1}-\mathbf {x} _{k},}$

$${\displaystyle 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],}$$

${\displaystyle \phi _{k}\in \mathbb {R} }$ ${\displaystyle k=1,2,...}$ ${\displaystyle \phi _{k}}$

Другие методы класса Бройдена были представлены другими авторами.

• Метод Дэвидона-Флетчера-Пауэлла (DFP) — единственный член этого класса, опубликованный до двух методов, определенных Бройденом. ^{[1] : 582} Для метода DFP . ^{[4] : 150} ${\displaystyle \phi _{k}=1}$
• Алгоритм Шуберта или разреженный Бройден - модификация разреженных матриц Якобиана. ^[5]
• Клемент (2014) – использует меньше итераций для решения многих систем уравнений. ^{[6] [7]}

Смотрите также

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

Рекомендации

1. Broyden, CG (октябрь 1965 г.). «Класс методов решения нелинейных одновременных уравнений». Математика вычислений . 19 (92). Американское математическое общество: 577–593. дои : 10.1090/S0025-5718-1965-0198670-6 . JSTOR  2003941.
2. Гей, DM (август 1979 г.). «Некоторые свойства сходимости метода Бройдена». SIAM Journal по численному анализу . 16 (4). СИАМ: 623–630. дои : 10.1137/0716047.
3. Кваален, Эрик (ноябрь 1991 г.). «Более быстрый метод Бройдена». БИТ Численная математика . 31 (2). СИАМ: 369–372. дои : 10.1007/BF01931297.
4. Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация. Серия Springer по исследованию операций и финансовой инженерии. Спрингер Нью-Йорк. дои : 10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.
5. Шуберт, Л.К. (1 января 1970 г.). «Модификация квазиньютоновского метода для нелинейных уравнений с разреженным якобианом». Математика вычислений . 24 (109): 27–30. дои : 10.1090/S0025-5718-1970-0258276-9 . ISSN  0025-5718.
6. Клемент, Ян (23 ноября 2014 г.). «Об использовании квазиньютоновских алгоритмов класса Бройдена для корреляции модели и теста». Журнал аэрокосмических технологий и менеджмента . 6 (4): 407–414. дои : 10.5028/jatm.v6i4.373 . ISSN  2175-9146.
7. «Методы класса Бройдена – Обмен файлами – MATLAB Central». www.mathworks.com . Проверено 4 февраля 2016 г.

дальнейшее чтение

• Деннис, JE ; Шнабель, Роберт Б. (1983). Численные методы неограниченной оптимизации и нелинейных уравнений . Энглвуд Клиффс: Прентис Холл. стр. 168–193. ISBN 0-13-627216-9.
• Флетчер, Р. (1987). Практические методы оптимизации (Второе изд.). Нью-Йорк: Джон Уайли и сыновья. стр. 44–79. ISBN 0-471-91547-5.

Внешние ссылки

• Простое базовое объяснение: история слепого лучника.