Градієнтні методи

Градієнтні методи — чисельні методи рішення з допомогою градієнта задач, що зводяться до знаходження екстремумів функції.

Постановка задачі розв'язання системи рівнянь в термінах методів оптимізації

Завдання рішення системи рівнянь:

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_{n}(x_{1},x_{2},\ldots ,x_{n})&=&0\end{array}}\right.$ (1)

з $n$ $x_{1},x_{2},\ldots ,x_{n}$ еквівалентна задачі мінімізації функції

$F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2},...,x_{n})|^{2}$ (2)

або якій-небудь іншій зростаючій функції від абсолютних величин $|f_{i}|$ нев'язок (помилок) $f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})$ , $i=1,2,\ldots ,n$ . Завдання знаходження мінімуму (або максимуму) функції $n$ змінних і сама по собі має велике практичне значення.

Для вирішення цієї задачі ітераційними методами починають з довільних значень $x_{i}^{[0]}(i=1,2,...,n)$ і будують послідовні наближення:

${\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}$

або покоординатно:

$x_{i}^{[j+1]}=x_{i}^{[j]}+\lambda ^{[j]}v_{i}^{[j]},\quad i=1,2,\ldots ,n,\quad j=0,1,2,\ldots$ (3)

які зводяться до деякого рішенням ${\vec {x}}^{[k]}$ при ${j\to \infty }$ .

Різні методи відрізняються вибором «напрямку» для чергового кроку, тобто вибором відносин

$v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}$ .

Величина кроку (відстань, на яку треба піднятися в заданому напрямку в пошуках екстремуму) визначається значенням параметра $\lambda ^{[j]}$ , який мінімізує величину $F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})$ як функцію від $\lambda ^{[j]}$ . Цю функцію зазвичай апроксимують її розкладанням у ряд Тейлора або інтерполяційним многочленом з трьох-п'яти вибраних значень $\lambda ^{[j]}$ . Останній метод застосуємо для знаходження max і min таблично заданої функції $F(x_{1},x_{2},...,x_{n}).$

Градієнтні методи

Основна ідея методів полягає в тому, щоб йти в напрямку найшвидшого спуску, а це напрямок задається антиградієнтом $-\nabla F$ :

${\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})$

де $\lambda ^{[j]}$ вибирається:

сталою, в цьому випадку метод може розходитися;
дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
якнайскорішим спуском: $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))$

Метод найшвидшого спуску (метод градієнта)

Вибирають $v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}$ , де всі похідні обчислюються при $x_{i}=x_{i}^{[j]}$ , і зменшують довжину кроку $\lambda ^{[j]}$ по мірі наближення до мінімуму функції $F$ .

Для аналітичних функцій $F$ і малих значень $f_{i}$ тейлорівський розклад $F(\lambda ^{[j]})$ дозволяє вибрати оптимальну величину кроку

$\lambda ^{[j]}={\frac {\sum _{k=1}^{n}({\frac {\partial F}{\partial x_{k}}})^{2}}{\sum _{k=1}^{n}\sum _{h=1}^{n}{\frac {\partial ^{2}F}{\partial x_{k}dx_{h}}}{\frac {\partial F}{\partial x_{k}}}{\frac {\partial F}{\partial x_{h}}}}}$ (5)

де всі похідні обчислюються при $x_{i}=x_{i}^{[j]}$ . Параболічна інтерполяція функції $F(\lambda ^{[j]})$ може виявитися більш зручною.

Алгоритм

Задаються початкове наближення і точність розрахунку ${\vec {x}}^{0},\quad \epsilon$
Розраховують ${\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})$ , де $\lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))$
Перевіряють умову зупинки:
- Якщо $|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}|>\epsilon$ , то $j=j+1$ і перехід до кроку 2.
- Інакше ${\vec {x}}={\vec {x}}^{[j+1]}$ і зупинка.

Метод покоординатного спуску Гауса — Зейделя

Цей метод названий за аналогією з методом Гауса — Зейделя для розв'язання системи лінійних рівнянь. Покращує попередній метод за рахунок того, що на черговій ітерації спуск здійснюється поступово уздовж кожної з координат, однак тепер необхідно обчислювати нові $\lambda n$ раз за один крок.

Алгоритм

Задаються початкове наближення і точність розрахунку ${\vec {x}}_{0}^{0},\quad \varepsilon$
Розраховують $\left\{{\begin{array}{lcr}{\vec {x}}_{1}^{[j]}&=&{\vec {x}}_{0}^{[j]}-\lambda _{1}^{[j]}{\frac {\partial F({\vec {x}}_{0}^{[j]})}{\partial x_{1}}}{\vec {e}}_{1}\\\ldots &&\\{\vec {x}}_{n}^{[j]}&=&{\vec {x}}_{n-1}^{[j]}-\lambda _{n}^{[j]}{\frac {\partial F({\vec {x}}_{n-1}^{[j]})}{\partial x_{n}}}{\vec {e}}_{n}\end{array}}\right.$ , де $\lambda _{i}^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}_{i-1}^{[j]}-\lambda ^{[j]}{\frac {\partial F({\vec {x}}_{i-1}^{[j]})}{\partial x_{i}}}{\vec {e}}_{i}\right)$
Перевірють умову зупинки:
- Якщо $|{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon$ , то ${\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1$ і перехід до кроку 2.
- Інакше ${\vec {x}}={\vec {x}}_{n}^{[j]}$ і зупинка.

Метод спряжених градієнтів

Метод спряжених градієнтів ґрунтується на поняттях прямого методу багатовимірної оптимізації — методу спряжених напрямів.

Застосування методу до квадратичних функцій $\mathbb {R} ^{n}$ визначає мінімум за $n$ кроків.

Алгоритм

Задаються початковим наближенням і похибкою: ${\vec {x}}_{0},\quad \varepsilon ,\quad k=0$
Розраховують початковий напрямок: $j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}$
${\vec {x}}_{k}^{j+1}={\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j},\quad \lambda =\arg \min _{\lambda }f({\vec {x}}_{k}^{j}+\lambda {\vec {S}}_{k}^{j}),\quad {\vec {S}}_{k}^{j+1}=-\nabla f({\vec {x}}_{k}^{j+1})+\omega {\vec {S}}_{k}^{j},\quad \omega ={\frac {||\nabla f({\vec {x}}_{k}^{j+1})||^{2}}{||\nabla f({\vec {x}}_{k}^{j})||^{2}}}$ $\text{[math]}$
- Якщо $||{\vec {S}}_{k}^{j+1}||<\varepsilon$ або $||{\vec {x}}_{k}^{j+1}-{\vec {x}}_{k}^{j}||<\varepsilon$ , то ${\vec {x}}={\vec {x}}_{k}^{j+1}$ і зупинка.
- Інакше
  - якщо $(j+1)<n$ , то $j=j+1$ і перехід до 3;
  - ${\vec {x}}_{k+1}={\vec {x}}_{k}^{j+1},\quad k=k+1$ і перехід до 2.

Див. також

Інтерполяційні формули
Математичне програмування
- Метод градієнта
- Метод спряжених градієнтів
- Прямі методи
Формула Тейлора
Чисельні методи
- Чисельне рішення рівнянь
- Метод Нелдера — Міда

Література

Акулич И.Л. {{{Заголовок}}}.
Гилл Ф., Мюррей У., Райт М. {{{Заголовок}}}.
Коршунов Ю.М., Коршунов Ю.М. {{{Заголовок}}}.
Максимов Ю.А.,Филлиповская Е.А. {{{Заголовок}}}.
Максимов Ю.А. {{{Заголовок}}}.
Корн Г., Корн Т. {{{Заголовок}}}.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.