Метод Бройдена — є квазіньютоновим методом для знаходження коренів системи рівнянь для змінних. Вперше він був описаний у 1965 році.
Метод Ньютона для розв'язання системи рівнянь , де , використовує обчислення якобіана матриці J на кожній ітерації. Однак обчислення якобіана є важкою та дорогою операцією. Ідея методу Бройдена в тому, щоб обчислювати весь якобіан лише на першій ітерації та використовувати розв'язок методом хорд на наступних ітераціях.
У 1979 році Девід М. Гей довів, що коли метод Бройдена застосовати до лінійної системи розміру , то він завершується за кроків, хоча, як і всі квазіньютоновські методи, він може не сходитися у випадку нелінійних систем.
Опис методу
Розв'язування рівняння з однією змінною У методі хорд ми замінюємо першу похідну у точці наближенням скінченною різницею:
і діємо подібно до методу Ньютона:
де — індекс ітерації.
Розв'язування системи нелінійних рівнянь Розглянемо систему з нелінійних рівнянь
де — вектор-функція вектора :
Для таких задач Бройден дає узагальнення одновимірного методу Ньютона, замінюючи похідну якобіаном . Матриця Якобі визначається ітеративно на основі рівняння хорди при наближенні скінченною різницею:
де — індекс ітерації. Для наочності визначимо:
тому вищезазначене можна переписати як
Наведене вище рівняння є , якщо більше одиниці. Бройден пропонує використати поточну оцінку матриці Якобі і вдосконалити її, взявши розв'язок рівняння хорди, яке є мінімальною модифікацією :
Це мінімізує наступну норму Фробеніуса:
і ми можемо рухатися подібно до метода Ньютона:
Бройден також запропонував використовувати для знаходження якобіана зворотної матриці Якобі:
Цей метод широко відомий як «хороший метод Бройдена».
Подібний результат можна отримати, використовуючи трохи іншу модифікацію . Це дає інший метод, так званий «поганий метод Бройдена» (див.):
Це мінімізує іншу норму Фробеніуса:
Багато квазі-ньютонових методів було запропоновано для задач оптимізації, коли при пошуку максимуму або мінімуму, знаходять корінь першої похідної (багатовимірний градієнт). Якобіан градієнта називається Гессіаном і є симетричним, що накладає додаткові обмеження для його оновлення.
Клас методів Бройдена На додаток до двох методів, описаних вище, Бройден визначив цілий клас споріднених методів. Загалом, методи в класі Бройдена задаються у формі де таі для кожного . Вибір визначає метод.
Інші методи в класі Бройдена були представлені іншими авторами є єдиним членом цього класу, опублікованим до двох методів, визначених Бройденом. Для методу DFP, . Алгоритм Шуберта або розріджений Бройдена — модифікація для розріджених матриць Якобі. Klement (2014) — використовує менше ітерацій для вирішення багатьох систем рівнянь.
Див. також
Метод хорд Метод Ньютона Квазі-ньютонів метод Метод Ньютона в оптимізації
Метод Бройдена–Флетчера–Голдфарба–Шенно (BFGS)
Примітки
Література
Посилання Просте базове пояснення: історія про сліпого стрільця