Метод Бройденса - Википедия - 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 {е} ( 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)

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

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

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

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

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