В численном анализе, метод Бройден в этом квазиньютоновский метод для нахождения корней в K переменных. Первоначально он был описан К.Г. Бройденом в 1965 году [1].
Метод Ньютона для решения ф ( х ) = 0 использует матрицу Якоби , J , на каждой итерации. Однако вычисление этого якобиана - сложная и дорогостоящая операция. Идея метода Бройдена состоит в том, чтобы вычислить весь якобиан только на первой итерации и выполнить обновления первого ранга на других итерациях.
В 1979 году Гей доказал, что когда метод Бройдена применяется к линейной системе размера n × n , он завершается за 2 n шагов [2], хотя, как и все квазиньютоновские методы, он может не сходиться для нелинейных систем.
Описание метода
Решение уравнения с одной переменной
В секущей методе мы заменить первую производную п ' при й п с конечно-разностной аппроксимацией:
и действуем аналогично методу Ньютона :
где n - индекс итерации.
Решение системы нелинейных уравнений
Рассмотрим систему k нелинейных уравнений
где f - вектор-функция вектора x :
Для таких задач, Бройдено дает обобщение метода одномерного Ньютон, заменив производную с якобиевой J . Матрица Якоби определяется итеративно на основе уравнения секущей в конечно-разностном приближении:
где n - индекс итерации. Для наглядности определим:
поэтому приведенное выше можно переписать как
Вышеупомянутое уравнение недоопределено, когда k больше единицы. Бройден предлагает использовать текущую оценку матрицы Якоби J n −1 и улучшить ее, взяв решение уравнения секущей, которое является минимальной модификацией J n −1 :
Это минимизирует следующую норму Фробениуса :
Затем мы можем продолжить движение в направлении Ньютона:
Бройден также предложил использовать формулу Шермана – Моррисона для непосредственного обновления обратной матрицы Якоби:
Этот первый метод широко известен как «метод хорошего Бройдена».
Аналогичный метод может быть получен путем использования немного другой модификации J n -1 . Это дает второй метод, так называемый «метод плохого Бройдена» (но см. [3] ):
Это минимизирует другую норму Фробениуса:
Многие другие квазиньютоновские схемы были предложены для оптимизации , когда ищут максимум или минимум, находя корень первой производной ( градиент в нескольких измерениях). Якобиан градиента называется гессианом и является симметричным, что добавляет дополнительные ограничения к его обновлению.
Другие члены класса Бройдена
Бройден определил не только два метода, но и целый класс методов. Другие члены этого класса были добавлены другими авторами.
- Обновление Давидона-Флетчера-Пауэлла является единственным членом этого класса публикуется до двух членов , определенных Бройдена. [4]
- Алгоритм Шуберта или разреженный алгоритм Бройдена - модификация разреженных якобиевых матриц. [5]
- Клемент (2014) - использует меньше итераций для решения многих систем уравнений. [6] [7]
Смотрите также
Рекомендации
- ^ Бройдена, CG (октябрь 1965). «Класс методов решения нелинейных одновременных уравнений» . Математика вычислений . Американское математическое общество. 19 (92): 577–593. DOI : 10.1090 / S0025-5718-1965-0198670-6 . JSTOR 2003941 .
- ^ Гей, DM (август 1979 г.). «Некоторые свойства сходимости метода Бройдена». Журнал СИАМ по численному анализу . СИАМ. 16 (4): 623–630. DOI : 10.1137 / 0716047 .
- ^ Кваален, Эрик (ноябрь 1991). «Более быстрый метод Бройдена». BIT Численная математика . СИАМ. 31 (2): 369–372. DOI : 10.1007 / BF01931297 .
- ^ Бройден, CG (октябрь 1965 г.). «Класс методов решения нелинейных одновременных уравнений» . Математика вычислений . Американское математическое общество. 19 (92): 577–593. DOI : 10.1090 / S0025-5718-1965-0198670-6 . JSTOR 2003941 .
- ^ Шуберт, LK (1970-01-01). «Модификация квазиньютоновского метода для нелинейных уравнений с разреженным якобианом» . Математика вычислений . 24 (109): 27–30. DOI : 10.1090 / S0025-5718-1970-0258276-9 . ISSN 0025-5718 .
- ^ Клемент, янв (23.11.2014). «Об использовании квазиньютоновских алгоритмов класса Бройдена для корреляции модели и теста» . Журнал аэрокосмических технологий и менеджмента . 6 (4): 407–414. DOI : 10,5028 / jatm.v6i4.373 . ISSN 2175-9146 .
- ^ «Методы класса Broyden - Обмен файлами - MATLAB Central» . www.mathworks.com . Проверено 4 февраля 2016 .
дальнейшее чтение
- Деннис, JE ; Шнабель, Роберт Б. (1983). Численные методы безусловной оптимизации и нелинейных уравнений . Энглвудские скалы: Прентис-холл. С. 168–193. ISBN 0-13-627216-9.
- Флетчер Р. (1987). Практические методы оптимизации (2-е изд.). Нью-Йорк: Джон Вили и сыновья. С. 44–79 . ISBN 0-471-91547-5.
Внешние ссылки
- Простое базовое объяснение: история слепого лучника