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

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

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

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

$\{\begin{array}{ccc}{f}_1(x_1,x_2,\dots ,x_n)& =& 0\\ \dots & & \\ f_n(x_1,x_2,\dots ,x_n)& =& 0\end{array}$(1)

з $n$ $x_1,x_2,\dots ,x_n$ еквівалентна задачі мінімізації функції

$F(x_1,x_2,\dots ,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,\dots ,x_n)$, $i=1,2,\dots ,n$. Завдання знаходження мінімуму (або максимуму) функції $n$ змінних і сама по собі має велике практичне значення.

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

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

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

$x_i^{[j+1]}=x_i^{[j]}+{\lambda }^{[j]}{v}_i^{[j]},i=1,2,\dots ,n,j=0,1,2,\dots$ (3)

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

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

$v_1^{[j]}:v_2^{[j]}:\dots :v_n^{[j]}$.

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

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

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

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

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

• сталою, в цьому випадку метод може розходитися;
• дробовим кроком, тобто довжина кроку в процесі спуску ділиться на деяке число;
• якнайскорішим спуском: ${\lambda }^{[j]}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\lambda }F({\overrightarrow{x}}^{[j]}-{\lambda }^{[j]}\mathrm{\nabla }F({\overrightarrow{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}d{x}_h}\frac{\partial F}{\partial x_k}\frac{\partial F}{\partial x_h}}$(5)

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

Алгоритм

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

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

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

Алгоритм

1. Задаються початкове наближення і точність розрахунку ${\overrightarrow{x}}_0^0,\epsilon$
2. Розраховують$\{\begin{array}{ccc}{\overrightarrow{x}}_1^{[j]}& =& {\overrightarrow{x}}_0^{[j]}-{\lambda }_1^{[j]}\frac{\partial F({\overrightarrow{x}}_0^{[j]})}{\partial x_1}{\overrightarrow{e}}_1\\ \dots & & \\ {\overrightarrow{x}}_n^{[j]}& =& {\overrightarrow{x}}_{n-1}^{[j]}-{\lambda }_n^{[j]}\frac{\partial F({\overrightarrow{x}}_{n-1}^{[j]})}{\partial x_n}{\overrightarrow{e}}_n\end{array}$, де ${\lambda }_i^{[j]}={\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}_{\lambda }F({\overrightarrow{x}}_{i-1}^{[j]}-{\lambda }^{[j]}\frac{\partial F({\overrightarrow{x}}_{i-1}^{[j]})}{\partial x_i}{\overrightarrow{e}}_i)$
3. Перевірють умову зупинки:
   • Якщо $|{\overrightarrow{x}}_n^{[j]}-{\overrightarrow{x}}_0^{[j]}|>\epsilon$, то ${\overrightarrow{x}}_0^{[j+1]}={\overrightarrow{x}}_n^{[j]},j=j+1$ і перехід до кроку 2.
   • Інакше $\overrightarrow{x}={\overrightarrow{x}}_n^{[j]}$ і зупинка.

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

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

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

Алгоритм

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

Див. також

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

Література

• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Книга-ру
• Шаблон:Книга-ру