3. Метод наискорейшего спуска

Нелинейное уравнение и его вариационная формулировка.

Пусть F — потенциальный оператор, действующий из банахова пространства Е в сопряженное пространство Е*. Это означает, что существует такой функционал / є ?*, что F = grad/.

Поставим задачу отыскания решений нелинейного уравнения

F(u)= 0.

Как следует из теоремы 10, эта задача сводится к нахождению критических точек функционала /. Поставим вопрос о безусловном минимуме функционала /, а именно: найти мо Є ? такое, что

/(ио) = inf f(u). (5)

иЄ?

Формулировка задачи в таком виде называется вариационной.

Если оператор / не является потенциальным, то вместо (5) рассматривают следующую задачу о минимизации функционала ||F(M)||: найти ио Є ? такое, что

||F(«0)||=inf||F(«)||. (6)

и€Е

Вариационные формулировки в виде (5), (6) часто используются для исследования и численного решения исходной нелинейной задачи (4). Ниже для этой цели применяется метод наискорейшего спуска, который позволяет находить приближенные решения вариационных постановок.

Основная идея метода наискорейшего спуска. Пусть в вещественном гильбертовом пространстве Н задан дифференцируемый по Гато вещественный и ограниченный снизу нелинейный функционал /. Положим d = inf„gtf / и F = grad /. Возьмем произвольный вектор и і Є Я и допустим, что F(u\) ф 0. Разумеется, если / — строго выпуклый функционал, то он может иметь лишь единственную точку минимума и принимает в ней значение, равное d\ поэтому требование F(uі) ф 0 означает, что и\ не есть точка минимума /. Выберем вектор Л Є Я так, чтобы его длина ||/I|| = ||F(KI)||, И выясним, как можно выбрать направление Л, чтобы производная

jtf(Ui+th) = (F(Ui+th),h)

имела наименьшее значение при / = 0, т. е. чтобы h было направлением наибольшего убывания /(и) в точке и\. С этой целью сначала выберем направление h так, чтобы (F(ui),h) имело наибольшее значение, а затем изменим знак вектора Л, так что (F(MІ), —h) будет иметь наймень-? 10858728

291

J.

шее значение. Так как {F(u\), h) < = ||F(mi)||2, то (F(u\), h)

примет наибольшее значение лишь при h = F(u\) и наименьшее при h = —F(ui), т.е когда направление h совпадает с направлением антиградиента /. Положим hi = -F(ui) и рассмотрим вещественную функцию ф(г) = /(мі +ffti), t > 0. По построению функция ф(г) убывает в некоторой правой полуокрестности точки t = 0. Пусть существует шіпф(г) и rj — наименьшее положительное значение t, для которого ф(?і) = шіпф(г). Положим U2 = Ml +t\h\ = Ml —/]F(MI). По построению f (u2) = /(мі +/lftl) < < /(«І). Считая F(m2) ф 0, можно повторить предыдущие рассуждения. Таким образом, если для каждого к выполнено F(m*) Ф 0, то приходим к следующему процессу:

u„+i = u„-tnF(un) (п - 1,2,3,...), (7)

который называется процессом наискорейшего спуска, или процессом градиентного спуска. Хотя последовательность (7) и такова, что

/(м,1+і) она может и не быть минимизирующей.

Определение 15. Всякая последовательность {м„}, для которой выполняется неравенство (8), называется релаксационной, а числа t„, входящие в (7), называются релаксационными множителями.

Отметим, что даже в случае гильбертова пространства возникают трудности при определении релаксационных множителей. Лишь в простейших случаях удается эффективно их вычислить. Ввиду этого числа tn заменяются положительными числами є„, которые либо задаются априорно, либо для них указываются границы, в которых они могут изменяться произвольно. В том случае, когда tn заменяются на є„, процесс (7) называется процесссм типа спуска (градиентного типа).

Рассмотрим теперь более общий случай, когда дифференцируемый по Гато вещественный и ограниченный снизу функционал / задан в рефлексивном вещественном банаховом пространстве Е. Пусть F = grad f киї — произвольный вектор из Е такой, что F(m) Ф 0. Выберем вектор hi € Е так, что hi = -UF(m), где U — оператор, действующий из Е* в Е и удовлетворяющий условиям ||?/v|| = ||v||, {v,Uv) = ||v||2.

«н+1 - u„-tnUF{un) (п- 1,2,3,...),

где /„ — наименьшее положительное значение t, для которого ф(г„) = = шіпф(/) при ф(/) =f{un + th„).

Обычно tn не вычисляют, а рассматривают процесс

м„+1 = ип - є,,UF(u„). (9)

Причем на выбор е„ накладываются такие ограничения, чтобы процесс типа наискорейшего спуска сходился.

3.3. Сходимость метода. Справедливо следующее утверждение.

Лемма 1. Пусть вещественный функционал /, заданный в рефлексивном вещественном банаховом пространстве Е, дифференцируем по

Гато и его градиент F удовлетворяет условию

(F(u + h)-F(u),h)(10)

где М — М(г) — произвольная положительная возрастающая функция на полуоси г > 0 и норма Е* пространства дифференцируема по Гато.

Тогда если гпМп < 1/2, где Мп = MAX[L, M(Rn)}, Rn = ||И„|| + ||F(M„)||, то процесс (9) будет релаксационным.

Отметим, что для выполнения неравенства (10) достаточно, чтобы оператор F удовлетворял условию Липшица

||F(m + A)-F(M)|| <Л*(г)||А||, (11)

причем константа Липшица может быть и возрастающей функцией от

г= ІИІ-

Лемма 2. Пусть выполнены условия:

Е — рефлексивное вещественное банахово пространство, причем норма в Е* дифференцируема по Гато;

дифференцируемый по Гато вещественный функционал f на Е ограничен снизу и является возрастающим (или множество Е\ ограничено), а его градиент удовлетворяет условию Липшица (11);

релаксационные множители єп удовлетворяют неравенствам 1/4 < Е„Мп < 1/2.

Тогда итерационный процесс (9) будет релаксационным и

lim F(un) = 0.

Заметим, что если в дополнение к условиям леммы 2 потребовать, чтобы /(и) - d < ||F(K)||a (a > 0), где d = inff(u), то последовательность un будет минимизирующей.

Теорема 20. Пусть выполнены условия:

Е — рефлексивное вещественное банахово пространство, причем норма в Е* дифференцируема по Гато;

вещественный функционал /, заданный на Е, дифференцируем по Гато, и его градиент F обладает тем свойством, что (F(tu),u) — интегрируемая по t Є [0, 1] функция, удовлетворяющая неравенствам

||F(« + /0-F(«)||(F(u + h) — F(u),h) > ||А||у(||А||),

где M(r) — непрерывная возрастающая неотрицательная функция, заданная для г > 0, и у(0> ' > 0, — возрастающая непрерывная функция такая, что у(0) = 0, причем функция

R

c(R) = y{w) dw о

возрастает и при некотором R справедливо неравенство c(R) > ||F(0)||;

3) 1/4 < ЕпМп < 1/2, Мп = тах[1,Л/(Л„)], Rn = ||«„|| + |Ии„)||.

Тогда последовательность к„+і = un—E„UF(u„) оказывается релаксационной, минимизирующей и сходящейся к точке абсолютного минимума функционала /.

В условиях теоремы 20 метод наискорейшего спуска (9) можно использовать для отыскания приближенного решения задачи (4).