Оптимизационный подход к решению вариационных неравенств тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Намм, Роберт Викторович

  • Намм, Роберт Викторович
  • кандидат физико-математических науккандидат физико-математических наук
  • 1984, Новосибирск
  • Специальность ВАК РФ01.01.07
  • Количество страниц 102
Намм, Роберт Викторович. Оптимизационный подход к решению вариационных неравенств: дис. кандидат физико-математических наук: 01.01.07 - Вычислительная математика. Новосибирск. 1984. 102 с.

Оглавление диссертации кандидат физико-математических наук Намм, Роберт Викторович

ВВЕДЕНИЕ.

ГЛАВА I. О РЕШЕНИИ ЭЛЛИПТИЧЕСКИХ ВАШАЩСЗННЫХ

НЕРАВЕНСТВ В УСЛОВИЯХ СЛАБОЙ КОЭРЩШВНОСТИ

§ I. Характеристика минимизирующих последовательностей в задаче Синьорини.

§ 2. Построение минимизирующей последовательности

§ 3. Устойчивость вспомогательных задач.

ГЛАВА 2. О ЧИСЛЕННОМ РЕШЕНИИ ЭЛЛИПТИЧЕСКИХ

ВАШАЩОННЫХ НЕРАВЕНСТВ.

§ I. Необходимые сведения о внешних аппроксимациях

§ 2. Метод поточечной релаксации.

§ 3. О скорости сходимости метода поточечной релаксации в задаче упругопластического кручения цилиндрического стержня.

ГЛАВА 3. МОДШЩРОВАННЫЙ МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

§ I. Некоторые сведения о методе возможных направлений

§ 2. Метод возможных направлений с отбрасыванием ограничений.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЩОННОЙ РАБОТЫ.

Рекомендованный список диссертаций по специальности «Вычислительная математика», 01.01.07 шифр ВАК

Введение диссертации (часть автореферата) на тему «Оптимизационный подход к решению вариационных неравенств»

Приближенное решение глногих линейных задач математической физики может быть получено в результате безусловной минимизации конечномерного (квадратичного и выпуклого) функционала или решения соответствующей системы линейных алгебраических уравнений. В последнее время объектом повышенного интереса являются нелинейные краевые задачи, такие, как задача об упругопластическом кручении цилиндрического стермня, задача о препятствии и другие [з] , [s] , [iQ] . Эти задачи (как и линейные) допускают естественную вариационную постановку и, в результате соответствующей аппроксимации, могут быть сведены к выпуклым конечномерным экстремальным задачам с ограничениями. Целью диссертационной работы является развитие численных методов решения такого рода вариационных задач с использованием аппарата вариационно-разностных аппроксимаций и математического программирования.

Пусть - открытая область с кусочно-гладкой гранигильбертово пространство, билинейная форма непрерывна на

УхУ . Требуется найти минимум квадратичного функционала

SL на некотором замкнутом выпуклом множестве }C<Z?\fРешение вариационной задачи существует, если функционал ^ выпуклый и удовлетворяет условию нестрогой (слабой) коэрцитивности

2J: p(U)-нос при Ilully-UeX ,

Методы решения таких задач в последнее время интенсивно развиваются, причем особый вклад внесен математиками школы ЖгЛ.Лион-са. Решение LL экстремальной задачи р(и)-пгщ ! иеХ. характеризуется условием

•4-<t>(U*+*(U-U*l) >0 для любого иеТС Я* oL-0 т.е. задача (0.1) эквивалентна решению вариационного неравенства

0.1) для любого UeJC где Uu)=ifUzfSL. ) л

В предположении, что квадратичная форма CC(U,U) строго коэрцитивна, т.е. при некотором jf > О для всех U€~\T справедливо неравенство , вариационная задача (0.1) имеет единственное решение и любая минимизирующая последовательность {ИП} сходится в норме пространства V к этому решению fz] . При более слабых предположениях эти вопросы требуют дополнительных исследований.

В первой главе диссертации рассматривается задача об установившемся движении жидкости в области, ограниченной полупроницаемой мембраной: JW=k\m\x-ljU.)t(lL-min! (0.2)

SL ueK={ir<i\Ni(SL): rr>f п.б. на Г}

Здесь - ограниченная область с достаточно регулярной границей Г ^ f€Lz(SL) » LZ(D - заданные функции, f U. - след функции Щ € на Г

При естественном предположении, что Jfi^SL < 0 решение

SL задачи (0.2) существует и единственно, причем

Т(и)-> + при ll^ll -»и tJC.

Однако функционал в (0.2) не является строго коэрцитивным на множестве . По этой причине утверждение о сильной сходимости в V\£L(Sl) минимизирующей последовательности (lC"J к решению Ц* требует обоснования. Известные результаты

Ш . /29] сводятся к установлению слабой сходимости [UH] % к искомому решению U и легко проверяемого соотношения im l!iru"-vu*lll .

L2(SL)

В § I, б предположении, что на области SI Для функций иещй) справедливо неравенство Пуанкаре

Л SL л А>0 и В>0 - постоянные, не зависящие от U. ), доказывается два утверждения.

ТЕОРЕМА I.I. Для любой минимизирующей последовательности имеет место

Ьт IIU"-U*IL=0 . схо Щ (SI)

Приведенная характеристика минимизирующих последовательностей установлена совместно с научным руководителем А.А.Капланом.

ТЕОРЕМА 1.2. Для последовательности [2И] > определяемой условиями а^щтм (КФф-г"-^ } (^>о-соМ{) г

IIК -л«бое); Z £ * ~ справедливо

•йт II2*-и*II =0 .

Щ(SL)

Как нетрудно заметить, регуляризирующая добавка оL \{Ur^h Mit(SL) обеспечивает строгую коэрцитивность в Wi^Q) функционалов в экстремальных задачах, рассматриваемых в теореме 1.2. Далее предполагается, что Sl^K .

Для построения последовательности {г**} предлагается использовать метод конечных элементов на последовательности нерегулярных сеток с условием iim^-O ( - шаг сетки)

Обозначим

- фиксированное разбиение области Q на треугольники Т (с использованием криволинейных элементов у границы области), . удовлетворяющие стандартным условиям триангуляций ( [ю] , стр, 115);

Ni - шожество узлов ^ /;

Vj> - линейная оболочка соответствующих кусочно-аффинных базисных функций; Ре/%}

Последовательность fU^ } (т.е. ) определяется из условий tft =г агапгт {Т(иЫЦи-й£ Цг ]

-к iic -i£\\ <L где ^ - произвольный элемент из К. , £uz0 , t(m Ёи — О . Можно проверить, что в предлагаемом методе обеспечивается хорошая обусловленность гессианов минимизируемых функционалов в соответствующих конечномерных экстремальных задачах. В § 2 показано, что если (2 - многоугольник, - выпукла на каждой из сторон L и последовательность триангуляций [^j удовлетворяет условиям ъО

UT-fl, М тс <х=> при всех h. , то

Щ Vt > lm\\L-u.*\\ =<9 .

В обосновании построенного метода существенную роль играет теорема 1.2. в которой рассматриваются вспомогательные задачи г

В § 3 исследована устойчивость этих задач по отношению к малым возмущениям J- и У . Пусть / и такие, что f/Ш, IIKII,^, nun, lf-т п.в. на Г.

Доказано, что решение iC(fi) возмущенной задачи

Мг-2^и*ф-Г1П ИI-torn на Г} при -0 сходится в (теорема 1.4). иск. 1

При конечноэлементной или разностной аппроксимации некоторых вариационных неравенств возникают экстремальные задачи специальной структуры. В § I главы 2 на примере задачи об упругопластическом кручении цилиндрического стержня [z] , [8] = л Л

-.} (ГСг/)

- расстояние от точки 2 ДО границы области J2. »

1 С R ) рассматривается конечномерная аппроксимация, приводящая к задаче квадратичного программирования следующего вида:

Г(х)=т<Ах>+<р>*>-! хеК

А/ ^ где , /Ы , </U,X>>0 для ХФО,

А Л/

ТС=ПК. /=1,Л/ могут быть неограниченными).

Заметим, что аппроксимация и некоторых других вариационных неравенств (например, задача о препятствии) приводит к (0.3). Это объясняется тем, что конструкция множества в ряде важных вариационных неравенств является относительно несложной.

Минимизируемые функционалы в (0.3) подобны соответствующим функционалам, получаемым при аппроксимации линейных краевых задач математической физики. Зто обстоятельство делает привлекательным использование для решения задачи (0.3) итерационных методов, учитывающих специальную структуру матрицы /\ . В главе 2 изучается метод поточечной релаксации для решения задачи квадратичного программирования (0.3).

Алгоритм поточечной релаксации выглядит следующим образом

И =

1) задаемся начальным вектором X \

2) определяем X; как решение неравенства

ТАЛ* Vй ^М ✓ TV Mtt л*"- л

3) полагаем Р ((1-Ш)Х*+со х"*'Л) , где Р (•)

Jv| "Ту- ■^•J

- оператор проектирования на Д. , а СО - параметр релаксации.

Известно /"2J , что при 0<tO ^Z алгоритм сходится к элементу X*€jV > минимизирующему функционал X на А

Х^ • В § 2 устанавливаются оценки скорости сходимости в предположении, что /4 - симметрическая, положительно определенная матрица общего вида.

Пусть Е ~ множество индексов, соответствующих нулевым компонентам вектора и Хр вектора, полученные в результате исключения из X компонент, индексы которых принадлежат соответственно множествам Р и Е . Имеет место[27]

ЛЕММА 2.1. Пусть Q< СО < Z . Тогда существует номер ХА , начиная с которого в методе поточечной релаксации V1 * < • - — Хр .

Из леммы 2.1, в частности, следует, что в задаче об упругопластическом кручении стержня за конечное число шагов будут найдены компоненты решения, соответствующие области пластичности.

Для матрицы {\ через обозначим подматрицу Д соответствующую множеству

Е , т.е. Ae~(4ij), Ue£ .

Очевидно, что R , где $) - диагональная матрица, L - левая треугольная, L . Аналогично + Re . При естественном предположении о том, что /7JC • » нетрудно установить, что, начиная с

Е ieE lr Т • г некоторого номера / ^ / , для всех I € Ь выполняются соотношения хър^а-ш^+юхгь^а-^хг+шх*-* .

Полагая в дальнейшем Ц Iz , рассмотрим функционал

Алгоритм поточечной релаксации при /I Zможно рассматривать как обычный метод релаксации (см. /~19] ) для решения системы Ае • Матрица перехода в методе релаксации имеет вид

TfaHQ+vLif [(*■-*)(o<cv<z).

A.M.Островским для случая СО—1 была получена оценка спектрального радиуса М (TW) матрицы ~J~(l) (см. [3l/) i F 171 £ - наименьшее собственное число матрицы /\ , # При СО < Z аналогичным путем уста /6 jb. навливается

7, "tTf £

I ll(i-&)wt

В § 2 доказано, что в действительности имеет место строгое неравенство

1 (ти < ^ из которого, используя свойства спектрального радиуса, следует соотношение ( /14J , стр. 15)

Однако на указанном пути не удается получить эффективную оценку постоянной С . Вместе с тем, анализ релаксационного процесса, проведенный в § 2, позволяет установить оценку

В § 3 отдельно рассматривается вопрос о скорости сходимости метода поточечной релаксации в задаче об упругопласти-ческом стержне.

Пусть О < СО < 4- • Тогда, используя специфику задачи, легко доказать следующее утверждение: для того, чтобы процесс

0 4 Z. релаксации был неубывающим, т.е. Х^Х , достаточно, о i. чтобы X йХ . Утверждение справедливо, например, если х°~о.

При условии, что процесс поточечной релаксации является неубывающим, доказывается

ТЕОРЕМА 2.1. Имеет место где • • • > c-ff®. r-it ц, . Cm

1((1-&Ш1Г

X^aiftnLn J(X) ? M - наименьшее собственное число матрицы /\

В главе 3 диссертации предлагается модификация одного из распространенных вариантов метода возможных направлений для решения задачи выпуклого программирования

-f(x) -шк ! xeSL=£:фт > со.4) где f- ^ ~ выпуклые дифференцируемые на функции.

В процессе реализации различных схем метода возможных направлений на каждом шаге в соответствующей точке допустимой области определяется направление убывания минимизируемой функции, по которому возможен сдвиг, не выводящий из допустимой области.На выбранном направлении находится новая допустимая точка с меньшим значением целевой функции, являющаяся исходной для следующего шага. Из многочисленных работ, посвященных методу возможных направлений, следует особо выделить исследования Г.Зойтендейка [i\] , который рассмотрел указанный метод в достаточно общем виде и предложил различные подходы его реализации, а также [ъ] , /хзJ , [l5] .

Такое направление назовем возможным.

В § I приведены необходимые сведения о методе возможных направлений. В § 2 рассматривается модификация указанного метода, связанная с уменьшением числа ограничений во вспомогательной задаче поиска подходящего направления сдвига. Предполагается, что множество решений задачи (0.4) ограничено и выполнено условие Слейтера: существует точка X » такая, что ^(х

Пусть к началу итерационного процесса имеется некоторая точка Х°€ „(2 и число JO> J • Алгоритм состоит в следующем. Полагая известными последовательности чисел ft € JO, 1J , где litfif^O и Д.- > 0 с iftV^tfij—O на ( K+l )-OM шаге решаем следующую задачу

J-*oo

Vf(X%S>£-6 t,-ivax!

Здесь s*- означает скалярное произведение векторов;

T(x")=(j ■?(х*)=0] ■ шиит) ■ $ - аффинная функция } ;

Т,ФШ)\Шит :<v/(xl WxfrXl-u,)|lv/Mltllv?WII хотя бы для одного (€

Принцип выбора И^ следующий: в начале процесса полагаем (о =<9. Далее к если 7^=0 или или fflct/x. llVf'wil

K+l J +1 в противном случае;

Определяем x'ttfeQ. если ; ' если

Для рассмотренной модификации метода возможных направлений доказана теорема 3.1, в условиях которой гарантирована сходимость метода, т.е. iim, f(xK)-=wn f(x)=fM(Vl . к->с>о хба

Множество » соответствующее отбрасываемым ограничениям, можно конструировать и другими способами, что отражено в § 2. Если вместо описанной выше процедуры построения положить "Л — ф К- t.Z, - -• , данный алгоритм превращается в

С ) один из основных вариантов метода возможных направлений (естественно, что при такой замене нет нужды в использовании управляющих последовательностей {fi}7 J )•

Приведенный метод наиболее целесообразно использовать в тех задачах выпуклого программирования, в которых число ограничений существенно превосходит размерность пространства переменных. Важный класс таких задач составляют задачи выпуклой полубесконечной оптимизации5^ [2з] , [29] j-(x)-min ! = [2ОС ОUM где ограничение £ зависит от непрерывного параметра t , принадлежащего некоторому компактному множеству (замечание 1.4). х) Точнее их дискретизированные аналоги.

Похожие диссертационные работы по специальности «Вычислительная математика», 01.01.07 шифр ВАК

Заключение диссертации по теме «Вычислительная математика», Намм, Роберт Викторович

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Намм, Роберт Викторович, 1984 год

1. Аннин Б.Д., Черепанов Г.П. Упругопластическая задача.-Новосибирск: Наука, 1983.- 240 с.

2. Гловински Р., Лионе Ж.-Л., Тремольер Р. Численное исследование вариационных неравенств/ перев. с франц.- М.: Мир, 1979.574 с.

3. Дюво Г., Лионе Ж.-Л. Неравенства в механике и физике/ перев. с франц.- М.: Наука, 1980.- 384 с.

4. Зойтендейк Г. Методы возможных направлений/ перев. с англ.-М.: ИЛ, 1963.- 176 с.

5. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование.- М.: Наука, 1964.- 348 с.

6. Каплан А.А. К вопросу о реализации метода возможных направлений.- Оптимизация, 1972, вып. 5, с. 41-46.

7. Каплан А.А. Алгоритмы выпуклого программирования, использующие сглаживание точных функций штрафа.- Сиб. мат. журн., 1982, т. 23, № 4, с. 1322-1350.

8. Лионе l.-Л. Некоторые методы решения нелинейных краевых задач/ перев. с франц.- М.: Мир, 1972.- 587 с.

9. Мазья В.Г. 0 задаче Неймана в областях с нерегулярными границами.- Сиб. мат. журн., 1968, т. 9, № 6, с. 1322-1350.

10. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы.- М.: Наука, 1981.- 416 е.

11. Михлин С.Г. Линейные уравнения в частных производных.-М.: Высш. школа, 1977.- 431 с.

12. Оганесян Л.А., Руховец Л.А. Вариационно-разностные методы решения эллиптических уравнений.- Ереван: Изд-во АН Армянской ССР, 1979.- 334 с.

13. Полак Э. Численные методы оптимизации. Единый подход/ перев. с англ.- М.: Мир, 1974.- 376 с.

14. Приближенное решение операторных уравнений/ Красносельский М.А., Вайникко Г.М., Забрейко П.П., Рутицкий Я.Б., Сте-ценко В.Я.- М.: Наука, 1969.- 455 с.

15. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экстремальных задачах.- М.: Наука, 1975.- 319 с.

16. Рокафеллар Р. Выпуклый анализ/ перев. с англ.- М.: Мир, 1973.- 471 с.

17. Стренг Г., Фикс Дж. Теория метода конечных элементов/ перев. с англ.- М.: Мир, 1977.- 349 с.

18. Сьярле §. Метод конечных элементов для эллиптических систем/ перев. с англ.- М.: Мир, 1980.- 512 с.

19. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры.- М.: Физматгиз, I960.- 656 с.

20. Каплан А.А., Намм Р.В. К характеристике минимизирующих последовательностей для задачи Синьорини.- Докл. АН СССР, 1983, т. 273, № 4, с.797-800.

21. Намм Р.В. Метод возможных направлений с отбрасыванием ограничений.- Оптимизация, 1978, вып. 22, с. 94-97.

22. Намм Р.В. Метод поточечной релаксации в задаче упругоплас-тического кручения цилиндрического стрежня.- Оптимизация, 1983, вып. 32, с. 140-152.

23. Borweih Т. /1 Direct theorems \п semi-infiniie convex t>ro3rzmmin<jf.—p\${h, Proyrtm., m±} V.2i, AA°3, PAot-zn .

24. В regis H. ProUemes цтЫегаих. -J Je ftaih . Pares ei Afrfifuees, mz, V. ЗГ1, №1,2, Р.1-Ш •

25. Cditereli I, A, Friedman A. The free houndiry ±or tUstic-phsh'c torsion problems. ~Trdft. Awer. ML Soc., f№, V.2S2, A tS-9? .

26. СШггеО I. A., Friedman A., Pozzi Q. Reflection methods ш He eUstiC-pkstic torsion problem-Indim tilth. X, mo, V.23J P.zos-zz$ .

27. Cryer C.W. The Solution of a fuadrdlc /эгоугамм/и? problem using systematic over-relaxdtio/i. Si AM T OH Control, 1SH, Л 34S-Z32 .

28. Glowhski R., Lions J.-LTremolteres R. bfumtricd шlysis of vtriztionrf /ле futilities.-kmsierdim d. 0. : North-Holland, mi, Нбр.

29. Н(шМ I. Convergence of dud finite element approximations for и ft it den I boundary value problems.-Apliket Mdkmiiky, 'Щ

30. Kirvey &F A duality theorem for se/ni-Ufinite Convex programs tnd their iinite subprograms.-ML Projrtmmi) v.Zf, A ?s-gL .

31. Tinj T.W. FUstiC-pUstiL torsion Of Simply connected cylindrical krs-Itldim V/iiv. MtU. Т.,1. Ш, Hiu9 p.mt-wc.

32. Xoiuntj J). M. Ikrd-fivc solution of (гг?е (ine&r5Vskms.-Mew York} London: Aazte/m'C Press, im3 5tfp.

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.