Непрерывные и дискретные методы минимизации высокого порядка тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

МОСКОВСКИ ГОСУДАРСТВЕННЫЕ! УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

Р Г Б ОД

- ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТМАТИКИ И КИБЕРНЕТИКИ

На правах рукописи УДК 519.6:517.938.68:519.853.6

НЕДИЧ АЩКЕЛИЯ

НЕПРЕРЫВНЫЕ И ДИСКРЕТНЫЕ МЕТОДЫ МИНИМИЗАЦИЙ ВЫСОКОГО ПОРЯДКА

01.01.07 - вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

М О С К В А - 1 994

Работа выполнена на кафедрз математической физики факультета вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова. '. ;

Научный руководитель: доктор физико-математических наук, профессор ВАСИЛЬЕВ Ф. П.

.Официальные, оппоненты:

доктор физико-математических наук, старший научный сотрудник АНТИПИН А. С.

доктор физико-математических наук, старший научный сотрудник АФАНАСЬЕВ А. П.

Ведущая организация: Вычислительный Центр РАН.

Защита диссертации состоится 1994 г. в

часов на заседаний специализированного совета Д.053.05.37 по математика при МГУ по адресу: 119899, Москва ГСП, Воробьевы горы, МГУ, факультет вычислительной математики и кибернетики, зуд. 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ,

Автореферат разослан » АЬ » ШШЩЫ 1994 г.

Ученый секретарь специализированного совета,

профессор Б. й. МОИСЕЕВ

СИЗАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность теш. Разработка методов решения экстремальных задач является одним из интенсивно развивающихся направлений вычислительной математики. Важным классом методов минимизации является класс непрерывных методов, в которых процесс минимизации описывается .дифференциальными уравнениями.

Интерес к непрерывным методам стимулируется, с одной стороны тем, что при исследовании сходимости траекторий непрерывных процессов к точке равновесия можно широко использовать развитый в теории дифференциальных уравнений аппарат, с другой стороны тем, что эти методы оставляют свободу при выборе методов численного интегрирования получающихся дифференциальных уравнений и определяют таким образом' целый класс дискретных методов, которые нельзя обнаружить, оставаясь в рамках привычных представлений, навязанных итеративной оптимизацией. До сих пор в литературе много внимания уделялось непрерывным методам первого порядка. Здесь можно /помянуть работы В.М.Венеца, М.В.Рыбашова, Ю.Г.Евтушенко, в.Г.Ка-дана, Б.Т.Поляка, М.Ковач, А.С.Антипина и других. Методы второго и более высокого порядка изучены недостаточно.

На основе непрерывных методов высокого порядка могут быть сконструированы многошаговые методы, представляющие собой дискретные аналоги непрерывных методов. Многошаговые методы имеют ряд достоинств, выгодно отличающих их от одношаговых методов. К их числу следует отнести более высокую скорость сходимости (по крайней мере для квадратичных функций), антиовражный характер, способность "проскакивать" отдельные локальные экстремумы в мно-гоэкстрамальных задачах, возможность "распараллеливания" на ЭВМ. Именно этим качествам многошаговые методы обязаны своей популярности.

Цель работа; разработка непрерывных и дискретных методов проекции градиента л линеаризации высокого порядка для задач минимизации, исследование их сходимости, получение оценки их скорости сходимости, конструирование регуляризованных вариантов предложенных непрерывных и дискретных методов и построение регул-

яризуодего оператора.

Методы исследований. В работе используются теория и метода выпуклого программирования, дифференциальных уравнений, теория разностных схем, методы функционального анализа, теория некорректных задач.

Научная новизна работа. В диссертации предлагаются новые непрерывные и дискретные методы проекции градиента и линеаризации высокого порядка для решения выпуклых задач математического программирования, исследуется их сходимость, дается оценка их скорости сходимости. Исследованы регуляризованные методы минимизации, основанные на предложенных непрерывных и дискретных методах.

Практическая значимость. Метода, предложенные в работе могут быть использованы при решении задач минимизации овражннх, многоэкстремальных функций, неустойчивых к погрешностям задания исходных данных оптимизационных задач.

Апробация работы. Результата диссертации докладывались и обсуадались на:

- научном семинаре кафедры оптимального управления факультета ВМиК МГУ под руководством проф. Васильева Ф.П.;

- научно-исследовательском семинаре кафедры математической физики факультета БМиК МГУ под руководством проф. Денисова A.M.;

- научно-исследовательском семинаре в Вычислительном центре РАН под руководством член-кор. РАН Евтушенко й.Г.;

- Международном конгрессе женщин - математиков в Пущино (30 мая - 3 июня 1994 г.).

Публикации. По материалам диссертации опубликовано пять статей И 3-f5], перечисленных в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы, включающего lj5 наименования. Объем работы составляет страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

В диссертации рассматривается задача минимизации

Ди> -»- I я f, и £ U, (Г;

где U - заданное выпуклое замкнутое множество из евклидова прос-

транства Еп; функция J(u) выпукла и дифференцируема на f Предполагается, что

J = I п t J(и) > U = { и € U: J(и) = J } * 0. (2)

' (If в * *

В начале работы предложен и исследован непрерывный метод

проекции градиента, описываемый следующим дифференциальным уравнением второго порядка

ß(t)u"(t) + u'(t) + u(t) =ФГГ tu(t) - a(W (u(î))l, t>0,

u (3)

u(0) = uQ, u'l0) = u1f где u0, ut - какие-либо фиксированные точки из (En; *?y(z) - проекция точки z на множество U; a(t) > О, ß(i) > 0, î > 0 - параметры метода. Дифференциальную систему (3) исследовал Антипин A.C. ( "Непрерывные и итеративные процессы с операторами проектирования и типа проектирования." Вопр. кибернетики, Вычисл. вопросы анализа больших систем, М. : Научный совет по комплексной проблеме <<Кибернетика>> АН СССР, С.5-43. 1989) в случае постоянных а, ß.

Достаточные условия сходимости метода (3) дает следующая теорема

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

1) Ü выпуклое замкнутое множество из Еп; функция J(и) выпукла, дифференцируема на !ЕП и ее градиент удовлетворяет условию Липшица

I J'(и) - J'(V) 1 « L J и - V I, и, V € £n, L = const < +»; выполнены условия (2);

2) функции a(t) ? £[0,+<о), ß(t) е J^fO.+o») такие, что

О < aQ ^ a(t) $ а,, ß*(t) $ 0, ßn(t) z 0, i j О,

lim ß(i) = ßM € (0.1). 1 - ßM - а1£ >

Тогда для любых начальных точек uQ, u, € Œn существует точка их е

€ V такая, что

Ilm С |u"(t)| + ju'(î)j + ju(t) - u I } = О, t*00 00

fl |ии(а)[г + iu'(a)|a + ß"(3) JU(3) - ujz } da < +«,.

Техника, которая использована при доказательстве этой и других теорем сходимости, является развитием техники Антипина A.C. из упомянутой выше статьи.

Если функция J(u) сильно Еыпукла и функции a(i). ß(t) удовлетворяют более жестким требованиям, чем в теореме 1 то можно

дать оценку скорости сходимости процесса (3). Напомним, что функция J{u) называется сильно выпуклой, если существует постоянная |х > 0 такая, что

J(au + (1-a)v> « cuT(u) + (1 -a)J(v) - а(1--а) -|r- I« - u|2, при всех u, » e En, 0 < a < 1. Тогда верна Теорема 2. Пусть

1) выполнены условия 1) теоремы 1; пусть J(и) силкао выпукла с постоянной сильной выпуклости ц > 0;

2) функции a(t) € C1tO,+»), ß(t) € е^О.+оо) такие, что

a(î) > 0, a'(t) $ О, ß(t) > 0, p'(t) « 0, ß*(t> а о,, t > о.

Um a(t) = a >0, Jim ß(t) = ß > Q, ct<0> < -rf- ,

txo t*M ^ ^

1 > 8 ц a(0) ß(0), 1 - 4 n аю (2 - ц aj > 0,

1 + [1 - 4 a(0) ß(0)],/s - 4 ß(0) >Û,' '

ß"(t) + 2 ß'(t) ö(t) + ß(t) ö'(t) ? 0, t ?0.

Тогда

|u(t) - UJ2 ^ c0 iwt)]-1 + 0, tff(tjî_t |u0 - u,fa» где a(t) - (ia(t) (2-ца(Я), ö(t) * [2 рШГ^ i ~ И --4a(t)ß(i>31/2}, S(i)*=iß(t>r1H -ß(tmt)), ft(t)=ôip{ .f&iajda],

t'(t) = eip [ /в(3)(За ], î г О.

Аналогичные оценки имеются и для |u'(t)!. |U"(i H- Насколько нам известно, оценки для метода (3) до сих пор не била получены.

На основе непрерывного метода (3) можно построить различные его дискретные аналоги» В работе исследован -ода из возможных дискретных вариантов &того метода:

Vt8pa4- h <Vr V - V^V й > 1* {4?

где u0, u, € U - заданные точки; ia^, <ßk3 -- параметры метода (4). Если Sj„ « 0 тогда метод (4) превращается в хорошо известный одношаговый метод проекции градиента. Двухшаговый метод проекция градиента (4) предлоадл и исследовал Антипин A.C. (см. упомянутую выше статью 19Ç9 г.) при о^ a = const, ß^ ■ ß = const. Теорэиа 3. Пусть выполнены условия

1) U замкнутое выпуклое множество из Еп; функции Ли) выпукла, дифференцируема на У и ее градиент удовлетворяет условию Липшица

J J'{u) - J"* (ü) { S 1 l U - V I, v, v tU, L = const < +00; выполнены условия (2):

2) последовательности iaR> и таковы, что О <aidkiä, ßkf1 » ßk, k » О.

Ilm ß, = 0 > G, 1 - 3 ß - 4- а I > 0.

. rk rOQ * £

«-wo

Тогда для любых uQf e !/ существует точка uw e Ut такая, что lim - u | = 0.

k -» то

При дополнительных условиях на последовательности ic^.}, {ßk> и сильной выпуклости функции J(u) получена оценка'скорости сходимости метода (4).

Теорема 4. Пусть выполнены условия 1) теоремы 3 и пусть

1) функция J(u) сильно выпукла с постоянной сильной выпуклости ц;

2) последовательности i<\}. ißk> удовлетворяют условиям

О < а i \ « ä, ßk+1 > ßk, k i О,

Ilm ß. - > 0, 1 - 6 - 2 а (А - ßOT ä |i - й L > О.

ä < ТГПГ' ^ 4~ сй ^ + (ä2 p.2 + 8 а \1)иг].

Тогда

• " »2 < Co J« V k *

где ut решение задачи (1), Ь± = (1 - a± ц)2 - a± |л, { ^ 1, Gq не зависит от к.

Как известно, задача (1) неустойчива к возмущениям исходных данных J{u), U и для ее решения нужно применять методы регуляризации. Следуя работам А.Н.Тихонова, Ф.П.Васильева, А.Б.Бакунинского , А.В.Гончарского и других, в работе проведена регуляризация вышеизложенных методов. Методы регуляризации в работе рассмотрены для задачи

J(u) — in/, и z U,

. (5)

ü = Си € UQ: gt(u) $ 0, t = T7m; g^u) = 0. С = m+T7S>, где lf - заданное выпуклое замкнутое множество из некоторого гильбертова пространства Ш, функции J(u), g^u) определены и дифференцируемы по Фреше на всем пространстве И.

В работе исследуется метод регуляризации, основанный на методе (3) в сочетании с методом штрафных функций. Для учета

ограничений типа равенств и неравенств из (5) будем пользоваться простейшей штрафной функцией

P(u) = f [ gUu) 3Р, и € И, Р > 1, (6)

1=1 1

где = max С gA; О ), t = = jgj, ( = m + 1.....s.

При сделанных предположениях функция P(u) из (6) дифференцируема по $реше на fH. Предположим, что вместо точных значений градиентов J'{u), Р' (и) нам известны их приближения J'(u,t), P'iu.t), зависящие от параметра ! ^ 0. Пусть u(i), t $ 0 - решение дифференциального уравнения

Pit) u"(t) + u'(t) + u(l) =.

~ iPrr t -uU) mt).,t) t»o. (?)

о

u(0) = u0, ■ tt'{0) где u0, - заданные точки из ¡H; T'(u,t) = J4u,t)+ <i(t)P'(u,t)+ + a(t) и, и t. Ш, l % u - приближение градиента функции Тихонова Qiu,t) в J(u) + i(t) P(u) + ait) i u l2, u ( И, t j 0; ¿(t). a(t), §if), j(t), t 5s о - параметры метода. Теорема б. Пусть выполнены условия.:

VQ - выпуклое замкнуто® множество "из гильбертова пространства

Ш, ФУНКЦИИ «Г<и), g,<U).....g^U). igs<")| ВЫПУКЛЫ

на И, функции J (и), Р(и) из (б) дифференцируемы по Фреше на IH и их градиенты удовлетворяют условию Липшица

Й a $ с |«7' (U) - еГЧу)!; IP'(U) - P' (U)| } « I |u - vj,

при всех u, v e fH; функция Лагранжа Ци,к) = J(u) + ) Я. g,(u),

i=i

u e I/0, U i0 = U f E6: ^ 0. £ = Тл > имеет седловую точку (ut,v*) € ио « h0, то есть

liu.t,K) < < Ь(иД*), u e К e A0;

2) приближения J4u,t), F' (u,t) градиентов J' (u), P' (u) непрерыв-еы по'ц при всех- .t г. Q, ■ измеримы no t.irpii всех u е Ш и

шаг i iJ'iu.t) - J'iu)(; |Р' (u,i) - P'<u)| } <

(8)

$ fi(i) (1 + I u J), U e IH, t^o;

3) параметры a(t),p(t),r((ty,0(t),A(t) метода (7) таковы, что

a(i), p(i). T(i) e S^CCM-®), SCi) с C£0,+»),

€ £1[0,+<o), ¿(t) - вогнутая функция,

a<t) > о, ,p(î> > о, ?(t) > ot ô(t) * о. Ait) > o, .fl'(i) iO. P'(t) ÎO. Y(t)iO, A-lt) } 0, a"(t) î 0, з 0, i"(t) JO, tjO,

Ш f<x(t) + T (t) + 0(t)+ A(t)~1+ f(t)A(t) + -5Î1MÎ1L] = o, t+m • ar(t)y(t)J

Ш p£i) « p € (O.D.

t*v>

Ш [a-1 (t) A(tr1/l»~" + t ] = 0.

t [a5(t)TJ(i )]1/г a(t)T2(t)J

Тогда

. VI « [ |u(t) - u | t ju'(t)l + |u"(t)| i = 0.

где u с fu l « lut | u | - нормальное решенное задачи (5), и ç. v л

причем сходимость здесь равномерная относительно выбора J'(u,t), Р' (uft) из (8).

В теореме 5 предполагалось, что значение градиентов J'(u), Рг (И) в любой фиксированной точке а t M может быть вычислено с -..любой наперед зздзнкой точностью S (t) в смысле неравенства (8). Однако s практических задачах исходные данные чаще всего задаются с погрешностью, остающейся больяе некоторого фиксированного положительного одела. В рассматриваемой задаче (5) более реальным, •чем (8),. представляется следующее условие: при каждом фиксированном и ç И вместо точного значения J' (u), Р'(и) могут быть вычислена их црййяихвная Pg(u) такие, что

тх - J'(U) I. |Р£(ц) - Р' (и) s ) 5 б (1 + nui), (8А)

при всех u € И, где б > о - известное число. Тогда процесс (7) нуздо заменить следующим процессом Ç(t) z"(t) + z'(t> z(t) = ""Pff 1 z(t) - j(t) (J£(z(t)) + Â(t) Pq(z{î)) + (7A)

+ ait) z{t)) ], î^û; z(0) = u0, z' (0) = u1f где параметр a(î), p(t), 7(i), S(i), 4(i) зафиксированы, не завися? от Ô > 0 из (8A), причем при каждом фиксированном уровне погрешности О, О < б < 0(0), процесс (7А) нужно продолжать до момента t - i(С >, определяемого из условия

t(ô) = зир £ t: д(з) > ô, 0 $ з £ t У. (3)

Обоснованием сформулированного правила останова (9) процесса (7а > служит

Теорема 6. Пусть выполнены все условия теоремы 5, кроме условия (8), приближения Jg(u), P¿(u), градиентов J'(u), P'(u) удовлетворяют условию (ЗА). Пусть z(t), 0$í$t(6) - траектории процесса (7А), где момент f(5) определен согласно правилу (3). Тогда

iim ä z(í (б)) - u i - О.

6 *- +о *

Из этой теоремы следует, чтс оператор который каждому набору úr¿(u),P¿(u),6) из (8А) ставит в соответствие точку и(б) = = z(f(б)), определяемую методом (7А), (9), является регуляризую-сдол оператором.

Аналогично для двушагового метода (4> рассмотрен его регул-яризовакный вариант

1 «к - Рк'Ч-, - V - \"< -W + 0 (10)

+ 4 P¿(Ufe) + о^ ) ], Ä > 1, где «7¿(u), P¿(u) приближения градиентов J'(u), Р'(и); функция Píu) из f6>. Доказана теорема согласованности параметров метода (1С), сформулировано правило останова и построен регуляризущий олерэтор.

Наряду с методами минимизации, основанными на методе проекции градиента, в работе рассматриваются модификации этого метода, связанные с 'идеей линеаризации, для задач выпуклого программирования

J(u) inj", и € U = { и е UQ: gt(u) $ О, £ = Т7Ш }, (11) где UQ - заданное выпуклое замкнутое множество из евклидова пространства Ек; функции J (и), gt(u) выпуклы и дифференцируемы на Еп. Непрерывный метод линеаризации второго порядка для задачи (11) имеет вид

ß(t) u-(í) + u'(t) + u(t) =

"^гдиш) с 'ut} ~ a(t) J'(u(í)) ]* t ? (,2)

u(0) = u0, и'(0) = u,,

ü(u) = { z € gt(u) + <g[(u), z - u> $ 0, í = T7m >. (13) где u0, uf заданные точки из En; a(í), ß(f) - параметры метода. Подчеркнем, что в отличие от непрерывного метода проекции градиента (3), в котором проектирование проводится на постоянное мно-

жество U, в методе (12) множество, на которое проектируется точка u(t) - a(í) J' (u(í)}, зависит от времени. Если UQ многогранное множество (например, UQ » it" или UQ = IE" = fu = (и1 ,...,ип) с Еп: и1 ) О,,.. / ? О } ), то задача проектирования превращается з стандартную задачу квадратичного программирования. Теорема 7. Пусть выполнены условия

1) У0 выпуклое замкнутое множество из Ъ"п; функции J (и), g±'u) выпуклы, дифференцируемы на Еп и их градиенты удовлетворяют условию Липшица

юг Í |«Г'(и) - «T<jj>!; max Ig'Au) - g'(ü)| } * L - v|.

1

при всех и, v € E ; выполнены условия (2) условие Слейтера

3 % î U0. g1(uo) < 0, t = î,,..,m; (14)

2) Функции a(í) е CtO.+oo), p(t) t C2[0,+to) такие, что

О < ct0 $ a(î> $ a,, p'(t) $ O, p"(í) í 0, ti О,

Um p(í) = р^ é (0,1 ), 1 - - сц! [4- + J.:vi)

где X*,..-.д* множители Лагранжа задачи (11). Тогда для любых начальных условий uQ, u ç Еп существует точка ит € такая, что Ига { iu"(í)J + \и* (í)| + |u(í) - и I } = О?

fl |и"(з)52 + |u*(а)|2 + (3"(s) |u(3) - uj2 } ds < +«.

Когда функция J (и) сильно выпукла, опираясь на теорему 7, можно получить оценку скорости сходимости метода (12), (13), которая по порядка совпадает со скоростью сходимости метода проекции градиента из теоремы 2.

Исследован следующий дискретный аналог метода (12), (13) для задачи (11);

\ а {г е CÍ0: gjUy + < g^V- z ~ V * °* { = ^^ (16)

где uQ, e í/Q заданные точки; í{3k> - параметры метода.

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

1) UQ замкнутое выпуклое множество из Еп; функции J(и), вы-

пуклы, дифференцируемы на VQ и их градиенты удовлетворяют условию Липшица

mar { |J'(u) - Jr{v)|; max Ig'tu) - gj (v)l > $ L \u~ вь

UKm 1 ^

при всех u, u ç UQ; выполнены условия (2) й (14); 2) последовательности Ca^J и ißk) таковы, что

0 < a ^ aK < ä, ßkf1 * ßk, & > 0, lim ßu ~ ßx > О,

k-кю 00

1 - 3 - â L ( -4r- + | Ä.* ) > 0,

где Я*,...Д* множители Дагранжа задачи (11). Тогда при любых uQ, и, б UQ существует точка ит ç такая, что

I 1 m | и. - и 1=0.

к - оо *

Для сильно выпуклых функций <7(и) получена оценка скорости сходимости метода (15), (16), которая по порядку совпадает с'оце-' нкой скорости сходимости двухшагового метода проекции градиента, данной в теореме 4.

Пусть вместо точных значений функции ¿^(и) и градиентов J'(u), g^u) нам известны их приближения gi(u,t), J'(u,t), g[(u,t), и t И, зависящие от параметра t > О. Тогда для решения задачи (11) можно использовать следующий рвгуляризованный вариант метода (12), (13):

ß(t) u"(t) + u'(t) + u(t) =

= TU(u(t)) [ u(i) _ T(i) 2"(u(t),t) J, t > 0, (17)

u(0) = u0, u'(0) = u,,

U(Ii) = { 2 € иn: gAu.t) + < gl(u,t), 2 - u > i

01 1 9 (-16) i 8(t) (1 + 1 и I ), i = TTffi >. где uQ, u, заданные точки из M; T'(u,t) = J'(u,t) + a (t) u приближение градиента функции Тихонова Q(u,t) = J(u) + -Jp a(t) |u|2, t j 0, u ( И; a(i), ß(t), 7(t), 0(i) - параметры метода.

Исследовано поведение решения задачи Коши (17), (18) при t -* +» и показано, что метод (17)-(18) обладает регуляризувдими свойствами, построен регуляризукхций оператор. Аналогичные результаты получены и для регуляризованного метода, основанного на дискретном двухшаговом методе линеаризации:

= xi "к - <vi- v - \ w ]> k *

= f 2 С u0: gik<V + < ei^tUfc). 2 - > i

< ек (1 + | |2), ( = 1.....Я1 }, где {¿(и) = «/¿.(и) + о^ и, и е и0 - приближение градиента функции Тихонова гуи) = /(и) + о^ |и|2. и е 1/0, Й » 1.

По той ае схеме, как для методов проекции градиента и линеаризации второго порядка, предложены и исследованы непрерывные и дискретные варианты 3-го, а также и 4-го порядка. Приведем описание методов третьего порядка. Для задачи (1) непрерывный метод проекции градиента третьего порядка имеет вид:

рза)ин,Ш + рг(г)иии) + и'Ш + иЦ) =

= [ иЦ) - а«?) <Г'(и(0) ], { (19)

и(0) = и0, и'(0) = и,, и" (О) = и2, где и0, , и2 - какие-либо фиксированные точки из Еп. Трехшаго-вый дискретный аналог метода (19):

^ *и ^ -Г - Ч-г~ VI > " (20)

- с^ J•(«k) ], * * г.

где и0, и,, и.г£ и - заданные точки. Регуляризованные методы (19), (20) для задачи (5) с неточными исходными данными имеют вид:

Рз^ц-Ш + р2(т"(*> + и'(Г) + иЦ) =

= [ иЦ) - уцу Г(иа),г) ], 1 ^ о, о

и(0) = и0. и'(0) = и,, и"(0) = иг, и0, и,, и2 е Еп.

= \ 1 «к " Рк (ик-Г "к) " Ч-г- VI > ~

- Тк Ч1ик> к 5 2' ио- «V "г «

Для задачи (11) исследован непрерывный метод линеаризации третьего порядка

в3(г>и"* сг) + рг(т"<п + и'(г) + и(г) = = Р!/(и(г)) [ иа) - а(г) .гшг)) ], г » о, (21)

и(0) = и0, и'(0) = и,, и"(О) = и2, и0, и,, иг е Еп, где и (и) задано соотношением (13), и его дискретный аналог

VI = V ^ - «VI- V - \ <\-2~ VI > - (22)

-а^оу К ь>2. и0, и,. иг €У0, где множество Ук определено в- (16). Для решения задачи (11) при

14

I ч

наличии погрешностей в исходных данных предложены и исследованы регуляризованные методы, основанные на методах (21) и (22): + + и'ш + и(п =

= 9ишг)) 1 и(П • Ь- 15 0,

и(0) = и0, и'<0) - и,, и"(0) = ц,, и0, и,, е 1ЕП, Щи) = { г е и0: + < г - и > $

* 8(4) (1 + |-и |г), « - 1,... ,т };

"ки = "к - <«к-Г V - °к.-(«к-г" «к-,) ' - 7к г^Пу ), к >2. и0, и,, и£ е Е70.

ук = { 2 С и0-, 81*1%) < в^)' Й - «к- > <

* ек (1 + 1 ^к ,г)" * = 1.....п К

Аналогично выписываются методы четвертого порядка. При исследовании непрерывных методов 3-го и 4-го порядков и их многошаговых аналогов тфимеиана несколько модифицированная техника,развитая и ранее использованная при доказательстве теорем 1-8.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1) для задач минимизации функций предложены непрерывные методы проекции градиента и линеаризации 2-го, 3-го и 4-го порядка, исследована их сходимость, получены оценки их скорости сходимости;

2) предложены и исследованы многошаговые дискретные метода проекции градиента и линеаризации, получены оценки их скорости сходимости;

3) проведена регуляризация всех предложенных методов и на их основе построены регуляризущие операторы.

По теме диссертации опубликовано 5 работ:

1. Недич А. Регуляризовэнкый непрерывный метод проекции градиента для задач минимизации с неточными исходными данными. Вестн. Моск. ун-та.: Сер. 15. Вычисл. матем. икиберн., 19Э4. Но. 1, С. 3-10.

2. Васильев Ф.П., Недич А. Регуляризованный непрерывный метод проекции градиента второго порядка. Вестн. Моск. ун-та. Сер. 15.

Вычисл. матем. и киберн., 1994, Ко. 2, С. 3-11.

3. Васильев Ф.П., Недич А. О трехшаговом регуляризованном. методе проекции градиента для решения задач минимизации, с неточными исходными данными. Известия* вузоЪ, Математика, Казань, 1993, Мо. 12, С. 379-387.

4. Недич А. Трехшаговый метод проекции градиента для Задач минимизации. Известия вузов, Математика, Казань, 1993, Но. 10, С.

5. Васильев Ф.П., Недич А. Об одном варианте регуляризованного метода проекции градиента. Ж. вычисл.- матем. и матем. физ., 1994, Том 34, N0. 4, С. 511-519.