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

Метод Бройдена — є квазіньютоновим методом для знаходження коренів системи рівнянь для Шаблон:Math змінних. Вперше він був описаний Шаблон:Не перекладено у 1965 році.

Метод Ньютона для розв'язання системи рівнянь $f_i(x_1,x_2,\dots ,x_n)=0$, де $i=1,2,\dots ,n$, використовує обчислення якобіана матриці J на кожній ітерації. Однак обчислення якобіана є важкою та дорогою операцією. Ідея методу Бройдена в тому, щоб обчислювати весь якобіан лише на першій ітерації та використовувати розв'язок методом хорд на наступних ітераціях.

У 1979 році Девід М. Гей довів, що коли метод Бройдена застосовати до лінійної системи розміру $n\times n$, то він завершується за Шаблон:Math кроків, хоча, як і всі квазіньютоновські методи, він може не сходитися у випадку нелінійних систем.

Опис методу

Розв'язування рівняння з однією змінною

У методі хорд ми замінюємо першу похідну Шаблон:Math у точці Шаблон:Math наближенням скінченною різницею:

$f^{\prime }(x_n)\simeq \frac{f(x_n)-f(x_{n-1})}{x_n-x_{n-1}},$

і діємо подібно до методу Ньютона:

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

де Шаблон:Math — індекс ітерації.

Розв'язування системи нелінійних рівнянь

Розглянемо систему з Шаблон:Math нелінійних рівнянь

$𝐟(𝐱)=\mathrm{𝟎},$

де Шаблон:Math — вектор-функція вектора Шаблон:Math:

$𝐱=(x_1,x_2,x_3,\dots ,x_k),$

$𝐟(𝐱)=(f_1(x_1,x_2,\dots ,x_k),f_2(x_1,x_2,\dots ,x_k),\dots ,f_k(x_1,x_2,\dots ,x_k)).$

Для таких задач Бройден дає узагальнення одновимірного методу Ньютона, замінюючи похідну якобіаном Шаблон:Math. Матриця Якобі визначається ітеративно на основі рівняння хорди при наближенні скінченною різницею:

${𝐉}_n({𝐱}_n-{𝐱}_{n-1})\simeq 𝐟({𝐱}_n)-𝐟({𝐱}_{n-1}),$

де Шаблон:Math — індекс ітерації. Для наочності визначимо:

${𝐟}_n=𝐟({𝐱}_n),$

$\mathrm{\Delta }{𝐱}_n={𝐱}_n-{𝐱}_{n-1},$

$\mathrm{\Delta }{𝐟}_n={𝐟}_n-{𝐟}_{n-1},$

тому вищезазначене можна переписати як

${𝐉}_n\mathrm{\Delta }{𝐱}_n\simeq \mathrm{\Delta }{𝐟}_n.$

Наведене вище рівняння є Шаблон:Не перекладено, якщо Шаблон:Math більше одиниці. Бройден пропонує використати поточну оцінку матриці Якобі Шаблон:Math і вдосконалити її, взявши розв'язок рівняння хорди, яке є мінімальною модифікацією Шаблон:Math:

${𝐉}_n={𝐉}_{n-1}+\frac{\mathrm{\Delta }{𝐟}_n-{𝐉}_{n-1}\mathrm{\Delta }{𝐱}_n}{\Vert \mathrm{\Delta }{𝐱}_n{\Vert }^2}\mathrm{\Delta }{𝐱}_n^{\mathrm{T}}.$

Це мінімізує наступну норму Фробеніуса:

$\Vert {𝐉}_n-{𝐉}_{n-1}{\Vert }_{\mathrm{F}}.$

і ми можемо рухатися подібно до метода Ньютона:

${𝐱}_{n+1}={𝐱}_n-{𝐉}_n^{-1}𝐟({𝐱}_n).$

Бройден також запропонував використовувати Шаблон:Не перекладено для знаходження якобіана зворотної матриці Якобі:

${𝐉}_n^{-1}={𝐉}_{n-1}^{-1}+\frac{\mathrm{\Delta }{𝐱}_n-{𝐉}_{n-1}^{-1}\mathrm{\Delta }{𝐟}_n}{\mathrm{\Delta }{𝐱}_n^{\mathrm{T}}{𝐉}_{n-1}^{-1}\mathrm{\Delta }{𝐟}_n}\mathrm{\Delta }{𝐱}_n^{\mathrm{T}}{𝐉}_{n-1}^{-1}.$

Цей метод широко відомий як «хороший метод Бройдена».

Подібний результат можна отримати, використовуючи трохи іншу модифікацію Шаблон:Math. Це дає інший метод, так званий «поганий метод Бройдена» (див.):

${𝐉}_n^{-1}={𝐉}_{n-1}^{-1}+\frac{\mathrm{\Delta }{𝐱}_n-{𝐉}_{n-1}^{-1}\mathrm{\Delta }{𝐟}_n}{\Vert \mathrm{\Delta }{𝐟}_n{\Vert }^2}\mathrm{\Delta }{𝐟}_n^{\mathrm{T}}.$

Це мінімізує іншу норму Фробеніуса:

$\Vert {𝐉}_n^{-1}-{𝐉}_{n-1}^{-1}{\Vert }_{\mathrm{F}}.$

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

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

На додаток до двох методів, описаних вище, Бройден визначив цілий клас споріднених методів.Шаблон:Rp Загалом, методи в класі Бройдена задаються у форміШаблон:Rp $${𝐉}_{k+1}={𝐉}_k-\frac{{𝐉}_k{s}_k{s}_k^T{𝐉}_k}{s_k^T{𝐉}_k{s}_k}+\frac{y_k{y}_k^T}{y_k^T{s}_k}+{\varphi }_k\left(s_k^T{𝐉}_k{s}_k\right)v_k{v}_k^T,$$де $y_k:=𝐟({𝐱}_{k+1})-𝐟({𝐱}_k),$$s_k:={𝐱}_{k+1}-{𝐱}_k,$ та$$v_k=[\frac{y_k}{y_k^T{s}_k}-\frac{{𝐉}_k{s}_k}{s_k^T{𝐉}_k{s}_k}],$$і ${\varphi }_k\in ℝ$ для кожного $k=1,2,...$ . Вибір ${\varphi }_k$ визначає метод.

Інші методи в класі Бройдена були представлені іншими авторами

• Шаблон:Не перекладено є єдиним членом цього класу, опублікованим до двох методів, визначених Бройденом.Шаблон:Rp Для методу DFP, ${\varphi }_k=1$.Шаблон:Rp
• Алгоритм Шуберта або розріджений Бройдена — модифікація для розріджених матриць Якобі.
• Klement (2014) — використовує менше ітерацій для вирішення багатьох систем рівнянь.

Див. також

• Метод хорд
• Метод Ньютона
• Квазі-ньютонів метод
• Метод Ньютона в оптимізації
• Шаблон:Не перекладено
• Метод Бройдена–Флетчера–Голдфарба–Шенно (BFGS)

Література

• Шаблон:Cite book
• Шаблон:Cite book

Посилання

• Просте базове пояснення: історія про сліпого стрільця