Метод Бройденса - Broydens method

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

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

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

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

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

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

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

куда п - индекс итерации.

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

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

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

куда ж является векторной функцией вектора Икс:

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

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

${\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_п−1 и улучшив его, взяв решение секущего уравнения, которое является минимальной модификацией J_п−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_п−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}}.}$

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

Другие члены класса Бройдена

Бройден определил не только два метода, но и целый класс методов. Остальные члены этого класса были добавлены другими авторами.

• В Последние новости Дэвидона – Флетчера – Пауэлла является единственным членом этого класса, который публикуется до двух членов, определенных Бройденом.^[4]
• Алгоритм Шуберта или разреженный алгоритм Бройдена - модификация разреженных якобиевых матриц.^[5]
• Клемент (2014) - использует меньше итераций для решения многих систем уравнений.^[6][7]

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

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

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

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

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

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

внешняя ссылка

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