Градиенты это: Градиент — Википедия – Несколько слов о градиентах / Habr

градиент — это… Что такое градиент?

Градиентный — это… Что такое Градиентный?

Градиентные методы — Википедия

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

Задача решения системы уравнений:

{f1(x1,x2,…,xn)=0…fn(x1,x2,…,xn)=0{\displaystyle \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{\displaystyle n} x1,x2,…,xn{\displaystyle x_{1},x_{2},\ldots ,x_{n}} эквивалентна задаче минимизации функции

F(x1,x2,…,xn)≡∑i=1n|fi(x1,x2,…,xn)|2{\displaystyle F(x_{1},x_{2},\ldots ,x_{n})\equiv \sum _{i=1}^{n}|f_{i}(x_{1},x_{2},…,x_{n})|^{2}} (2)

или какой-либо другой возрастающей функции от абсолютных величин |fi|{\displaystyle |f_{i}|} невязок (ошибок) fi=fi(x1,x2,…,xn){\displaystyle f_{i}=f_{i}(x_{1},x_{2},\ldots ,x_{n})}, i=1,2,…,n{\displaystyle i=1,2,\ldots ,n}. Задача отыскания минимума (или максимума) функции n{\displaystyle n} переменных и сама по себе имеет большое практическое значение.

Для решения этой задачи итерационными методами начинают с произвольных значений xi[0](i=1,2,…,n){\displaystyle x_{i}^{[0]}(i=1,2,…,n)} и строят последовательные приближения:

x→[j+1]=x→[j]+λ[j]v→[j]{\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}+\lambda ^{[j]}{\vec {v}}^{[j]}}

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

xi[j+1]=xi[j]+λ[j]vi[j],i=1,2,…,n,j=0,1,2,…{\displaystyle 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)

которые сходятся к некоторому решению x→[k]{\displaystyle {\vec {x}}^{[k]}} при j→∞{\displaystyle {j\to \infty }}.

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

v1[j]:v2[j]:…:vn[j]{\displaystyle v_{1}^{[j]}:v_{2}^{[j]}:\ldots :v_{n}^{[j]}}.

Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра λ[j]{\displaystyle \lambda ^{[j]}}, минимизирующим величину F(x1[j+1],x2[j+1],…,xn[j+1]){\displaystyle F(x_{1}^{[j+1]},x_{2}^{[j+1]},\ldots ,x_{n}^{[j+1]})} как функцию от λ[j]{\displaystyle \lambda ^{[j]}}. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям λ[j]{\displaystyle \lambda ^{[j]}}. Последний метод применим для отыскания max и min таблично заданной функции F(x1,x2,…,xn){\displaystyle F(x_{1},x_{2},…,x_{n})}.

Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом −∇F{\displaystyle -\nabla F}:

x→[j+1]=x→[j]−λ[j]∇F(x→[j]){\displaystyle {\overrightarrow {x}}^{[j+1]}={\overrightarrow {x}}^{[j]}-\lambda ^{[j]}\nabla F({\overrightarrow {x}}^{[j]})}

где λ[j]{\displaystyle \lambda ^{[j]}} выбирается:

• постоянной, в этом случае метод может расходиться;
• дробным шагом, то есть длина шага в процессе спуска делится на некое число;
• наискорейшим спуском: λ[j]=argminλF(x→[j]−λ[j]∇F(x→[j])){\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F({\vec {x}}^{[j]}))}

Метод наискорейшего спуска (метод градиента)[править | править код]

Выбирают vi[j]=−∂F∂xi{\displaystyle v_{i}^{[j]}=-{\frac {\partial F}{\partial x_{i}}}}, где все производные вычисляются при xi=xi[j]{\displaystyle x_{i}=x_{i}^{[j]}}, и уменьшают длину шага λ[j]{\displaystyle \lambda ^{[j]}} по мере приближения к минимуму функции F{\displaystyle F}.

Для аналитических функций F{\displaystyle F} и малых значений fi{\displaystyle f_{i}} тейлоровское разложение F(λ[j]){\displaystyle F(\lambda ^{[j]})} позволяет выбрать оптимальную величину шага

λ[j]=∑k=1n(∂F∂xk)2∑k=1n∑h=1n∂2F∂xkdxh∂F∂xk∂F∂xh{\displaystyle \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)

где все производные вычисляются при xi=xi[j]{\displaystyle x_{i}=x_{i}^{[j]}}. Параболическая интерполяция функции F(λ[j]){\displaystyle F(\lambda ^{[j]})} может оказаться более удобной.

Алгоритм[править | править код]

1. Задаются начальное приближение и точность расчёта x→0,ϵ{\displaystyle {\vec {x}}^{0}\!,\,\epsilon }
2. Рассчитывают x→[j+1]=x→[j]−λ[j]∇F(x→[j]){\displaystyle {\vec {x}}^{[j+1]}={\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)}, где λ[j]=argminλF(x→[j]−λ[j]∇F(x→[j])){\displaystyle \lambda ^{[j]}=\mathrm {argmin} _{\lambda }\,F\left({\vec {x}}^{[j]}-\lambda ^{[j]}\nabla F\left({\vec {x}}^{[j]}\right)\right)}
3. Проверяют условие останова:
   • Если |x→[j+1]−x→[j]|>ϵ{\displaystyle \left|{\vec {x}}^{[j+1]}-{\vec {x}}^{[j]}\right|>\epsilon }, то j=j+1{\displaystyle j=j+1} и переход к шагу 2.
   • Иначе x→=x→[j+1]{\displaystyle {\vec {x}}={\vec {x}}^{[j+1]}} и останов.

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

Этот метод назван по аналогии с методом Гаусса — Зейделя для решения системы линейных уравнений. Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые λn{\displaystyle \lambda \quad n} раз за один шаг.

Алгоритм[править | править код]

1. Задаются начальное приближение и точность расчёта x→00,ε{\displaystyle {\vec {x}}_{0}^{0},\quad \varepsilon }
2. Рассчитывают {x→1[j]=x→0[j]−λ1[j]∂F(x→0[j])∂x1e→1…x→n[j]=x→n−1[j]−λn[j]∂F(x→n−1[j])∂xne→n{\displaystyle \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.}, где λi[j]=argminλF(x→i−1[j]−λ[j]∂F(x→i−1[j])∂xie→i){\displaystyle \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)}
3. Проверяют условие остановки:
   • Если |x→n[j]−x→0[j]|>ε{\displaystyle |{\vec {x}}_{n}^{[j]}-{\vec {x}}_{0}^{[j]}|>\varepsilon }, то x→0[j+1]=x→n[j],j=j+1{\displaystyle {\vec {x}}_{0}^{[j+1]}={\vec {x}}_{n}^{[j]},\quad j=j+1} и переход к шагу 2.
   • Иначе x→=x→n[j]{\displaystyle {\vec {x}}={\vec {x}}_{n}^{[j]}} и останов.

Метод сопряжённых градиентов[править | править код]

Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.

Применение метода к квадратичным функциям в Rn{\displaystyle \mathbb {R} ^{n}} определяет минимум за n{\displaystyle n} шагов.

Алгоритм[править | править код]

1. Задаются начальным приближением и погрешностью: x→0,ε,k=0{\displaystyle {\vec {x}}_{0},\quad \varepsilon ,\quad k=0}
2. Рассчитывают начальное направление: j=0,S→kj=−∇f(x→k),x→kj=x→k{\displaystyle j=0,\quad {\vec {S}}_{k}^{j}=-\nabla f({\vec {x}}_{k}),\quad {\vec {x}}_{k}^{j}={\vec {x}}_{k}}
3. x→kj+1=x→kj+λS→kj,λ=arg⁡minλf(x→kj+λS→kj),S→kj+1=−∇f(x→kj+1)+ωS→kj,ω=||∇f(x→kj+1)||2||∇f(x→kj)||2{\displaystyle {\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}}}}

• Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
• Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
• Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
• Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

Градиентность — это… Что такое Градиентность?

{{gradient|#начальный цвет|#конечный цвет|направление}}

{{градиент|#начальный цвет|#конечный цвет|направление}}

<div>Lorem ipsum...*...est laborum.</div>

<div>Lorem ipsum...*...est laborum.</div>

<div>Lorem ipsum...*...est laborum.</div>