Исследование метода инвариантного погружения в задачах оптимизации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ.

I, ПРИМЕНЕНИЕ МЕТОДА ИНВАРИАНТНОГО ПОГРУЖЕНИЯ ДЛЯ РЕШЕНИЯ МНОГОМЕРНЫХ ЛИНЕЙНЫХ ДВУХТОЧЕЧНЫХ ГРАНИЧНЫХ ЗАДАЧ.

1.1. Краткий обзор методов решения линейных граничных задач для систем обыкновенных дифференциальных уравнений.

1.2. О разрешимости линейных граничных задач для систем дифференциальных уравнений первого порядка.

1.3. Единая терминология метода инвариантного погружения.

1.4. Описание метода инвариантного погружения для многомерных линейных граничных задач

1.5. Доказательство эквивалентности

1.6. Алгоритм метода инвариантного погружения для решения линейной многомерной граничной задачи. Численный эксперимент.hi

1.7. О сходимости,устойчивости и погрешности метода инвариантного погружения для многомерных линейных граничных задач.

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

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

1.10. Сравнительный анализ метода инвариантного погружения с другими методами решения многомерных линейных граничных задач.Численные эксперименты

1.11. Выводы.

2. ПРИМЕНЕНИЕ МЕТОДА ИНВАРИАНТНОГО ПОГРУЖЕНИЯ ДЛЯ РЕШЕНИЯ МНОГОМЕРНЫХ НЕЛИНЕЙНЫХ ДВУХТОЧЕЧНЫХ ГРАНИЧНЫХ ЗАДАЧ.

2.1* Существующие методы решения граничных задач для систем нелинейных дифференциальных уравнений

2.2. О разрешимости нелинейных граничных задач

2.3. Описание метода инвариантного погружения для многомерных нелинейных граничных задач

2.4. Доказательство эквивалентности

2.5. Алгоритм решения нелинейной граничной задачи на основе метода инвариантного погружения

2.6. Оценка сложности алгоритма решения многомерных нелинейных граничных задач

2.7. О сходимости,устойчивости,погрешности метода инвариантного погружения для многомерных нелинейных граничных задач

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

2.9. Выводы.

3. ПРИМЕНЕНИЕ МЕТОДА ИНВАРИАНТНОГО ПОГРУЖЕНИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ В СОЧЕТАНИИ

- il

С ПРИНЦИПОМ МАКСИМУМА Л.С.ПОНТРЯГИНА . НО

3.1. Задачи оптимизации и их классификация . III

3.2. Сведение задач оптимального управления к задаче о минимизации конечного значения переменной состояния

3.3. Сведение задачи о минимизации конечного значения переменной состояния к нелинейной граничной задаче

3.4. Применение метода инвариантного погружения для решения задачи о минимизации конечного значения переменной состояния.

3.5. Выводы.

4. О РЕШЕНИИ НЕКОТОРЫХ КЛАССОВ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ С ПОМОЩЬЮ МЕТОДА ИНВАРИАНТНОГО ПОГРУЖЕНИЯ

4.1. Линейные задачи оптимального управления с квадратичным функционалом

4.2. Одна задача динамики космических аппаратов.

4.3. Задача Майера для систем линейных по фазовой переменной и по управлению

4.4. Задачи оптимального управления с фазовыми ограничениями в форме неравенств

4.5. Выводы.

Современный этап научно-технической революции характеризуется постоянно возрастающим вниманием к проблемам управления.Теория управления получила дальнейшее развитие благодаря появлению электронно-вычислительной техники,которая позволила создавать сложные алгоритмы управления.Развитие теории управления в последнее время определяла идея оптимизации.Задачи оптимизации по своему смыслу являются вариационными,но их усложняет необходимость учета при построении оптимальных процессов различного рода ограничений,задающих замкнутые области допус -тимых изменений переменных.Это и определяет особенности, которыми характеризуются направления развития теории оптимальных систем.Часть методов теории оптимальных систем базируется на аппарате классического вариационного исчисления и теории приближенных вычислений,другая часть -методы,специально созданные для теории оптимальных систем. Но в настоящее время в теории оптимизации существует разрыв между теоретическими исследованиями задач оптимизации и практикой их решения.Несмотря на то,что разработаны условия оптимальности в форме принципа максимума Л.С.Понт-рягина и принципа динамического программирования Р.Белл-мана,на практике используются в основном методы направленного перебора,разностные и градиентные метод и другие, непосредственно не связанные с условиями оптимальности.

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

Для численного решения граничных задач может быть применен метод инвариантного погружения,суть которого состоит в сведении граничных задач к задачам Коши,т.е. в том,чтобы сформулировать задачу Коши,решение которой единственным образом определяет решение граничной задачи и наоборот.Такое сведение становится возможным благодаря введению новых переменных состояния - параметров, погружению (включению) данной конкретной задачи в семейство подобных ей задач и рассмотрению взаимосвязи между близкими задачами семейства.Одним из главных достоинств метода является тот факт,что несмотря на то,что исходная граничная задача численно неустойчива,эквивалентные задачи Коши имеют численно устойчивое решение.

Впервые идеи метода инвариантного погружения были высказаны советским ученым В.А.Амбарцумяном в 1943 году и развиты Чандрасекхаром,который и ввел понятие "принцип инвариантности".Затем метод инвариантного погружения активно разрабатывался зарубежными учеными Беллманом, Калаба,Касти,Уингом,Прейзендорфом,Алспо,Кагивада и другими.В Советском Союзе до последнего времени (до появления работ П.И.Монастырного) метод инвариантного погружения не входил в арсенал численных методов решения граничных задач.За рубежом особенно интенсивно развивался прикладной аспект метода инвариантного погружения,который успешно применялся для решения задач теории нейтронной диффузии,переноса лучистой энергии,распространения волн и многих других физических задач.

Существуют различные вычислительные схемы метода инвариантного погружения:для случая системы из двух скалярных уравнений,для линейных и нелинейных граничных задач, для решения интегральных уравнений и т.д.Особенно сложны и интересны вопросы применения метода инвариантного погружения к многомерным граничным задачам,которые не позволяют непосредственно использовать технику метода инвариантного погружения.Вычислительные схемы для многомерных граничных задач были предложены Алспо,Каги-вадой,Бретеникером,Мейером.Однако все они имеют некоторые недостатки:одни - трудоемки, с помощью других нельзя получить достаточно точное решение задачи.

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

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

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

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

Все предложенные алгоритмы реализованы на алгоритмическом языке Ф0РТРАН-1У.Тексты программ даны в при-ложе нии I.

По теме диссертационной работы опубликовано три статьи,две статьи находятся в печати (депонирование).

Работа выполнена на кафедре автоматизации сложных систем факультета прикладной математики-процессов управления Ленинградского государственного университета им. А.А.Жданова,

Материалы диссертационной работы докладывались на семинарах кафедры автоматизации сложных систем и численного анализа ЛГУ им.А.А.Жданова,научной конференции факультета прикладной математики-процессов управления (1981 год),на ХУ1 конференции, "Управление динамическими системами" (Ленинград,1984 г.).

- 1и

I.ПРИМЕНЕНИЕ МЕТОДА ИНВАРИАНТНОГО ПОГРУЖЕНИЯ ДЛЯ РЕШЕНИЯ МНОГОМЕРНЫХ ЛИНЕЙНЫХ ДВУХТОЧЕЧНЫХ ГРАНИЧНЫХ ЗАДАЧ.

Основные результаты,полученные в работе,состоят в следующем.

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

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

3.Приведен расчет временной и емкостной сложности предложенных алгоритмов,подтверждающий возможность их использо- • вания для решения задач достаточно большой размерности. Приводятся результаты численных экспериментов,подтверждающие правильность работы предложенных вычислительных схем и показывающие,что метод инвариантного погружения дает возможность получить достаточно точное решение граничной задачи за небольшое время и при использовании небольшого объема памяти ЭВМ.Приводятся результаты сравнения работы предложенных схем и других методов численного решения подобных задач,показывающие преимущества метода инвариантного погружения.

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

5.Практическая ценность полученных результатов состоит в том,что разработан и отлажен комплекс алгоритмов и программ для решения многомерных линейных и нелинейных граничных многомерных задач на основе метода инвариантного погружения.Разработанный комплекс алгоритмов и программ используется в Ленинградском научно-исследовательском вычислительном центре Академии Наук СССР в прикладных программах пользователей.

ЗАКЛЮЧЕНИЕ.

1. Алексеев В.М.,Тихомиров В.М.,Фомин C.B. Оптимальное управление М.:Наука,1979

2. Амбарцумян В.А.Теоретическая астрофизика. М.:ГТТИ,1952

3. Ахо А.Допкрофт Дж.,Ульман Дж.Построение и анализ вычислительных алгоритмов. М.:Мир,1979

4. Бабушка И.,Витасек Э.,Прагер М.Численные процессы решения дифференциальных уравнений. М.:Мир,1969

5. Баринов Н.Г.Оптимизация процессов и систем управления в судовой автоматике. Ленинград:Судостроение,1976

6. Бахвалов Н.С.Численные методы,ч.1 М.:Наука,1973

7. Беллман Р.Введение в теорию матриц. М.:Наука,1976

8. Беллман Р.Динамическое программирование. М.:ИЛ,i960

9. Беллман Р.Теория устойчивости решений дифференциальных уравнений. М.:ИЛ,1954

10. Ю.Беллман Р.,Гликсберг И.,Гросс 0.Некоторые вопросы математической теории процессов управления.- М.:ИЛ,1962 И.Беллман Р.,Калаба Р.Квазилинеаризация и нелинейные краевые задачи. М.:Мир,1968

11. Беллман Р.,Калаба Р.Динамическое программирование и современная теория управления. М.: Наука,1969

12. Беллман Р.,Кук К.Дифференциально-разностные уравнения.-М.:Мир,1967

13. Березин И.С.,Жидков Н.П.Методы вычислений,т.I М.: Наука,1966

14. Березин И.С.,Жидков Н.П.Методы вычислений,т.2 М.: Физматгиз,1962

15. Болтянский В.Г.Математические методы оптимального управ-.ления. М.:Наука,1969

16. Бут Э.Д.Численные методы. М,:Физматгиз,1959

17. Васильев Н.И.,Клоков Ю.А.Основы теории краевых задач обыкновенных дифференциальных уравнений. Рига:3инантне, 1978

18. Гантмахер Ф.Р.Теория матриц. М.:Наука,1967

19. Гельфанд И.М.,Фомин С.В.Вариационное исчисление. -М.:Физматгиз,1961

20. Гудков В.В.,Клоков Ю.А. и др.Двухточечные краевые задачи для обыкновенных дифференциальных уравнений. РигагЗинант-не,1973

21. Демидович Б.П.Лекции по математической теории устойчивости. М.:Наука,1967

22. Зубов В.И.Теория оптимального управления. Ленинград: Судпромгиз,1966

23. Калиткин Н.Н.Численные методы. М.:Наука,1978

24. Касти Дж.,Калаба Р.Методы погружения в прикладной математике. М.:Мир,1976

25. Кирин Н.Е.Вычислительные методы теории оптимального управления. Ленинград:изд-во ЛГУ,1968

26. Коллатц Л.Численные методы решения дифференциальных уравнений. М.:ИЛ,1953

27. Крылов В.И.,Бобков В.В.,Монастырный П.И.Вычислительные методы,т.I М.:Наука,1976

28. Крылов В.И.,Бобков В.В.,Монастырный П.И.Вычислительные методы,т.2 М.:Наука,1977

29. Лаврушкина Н.С.Метод инвариантного погружения в задачах оптимизации с фазовыми ограничениями. В кн.применение вычислительных методов в научно-технических исследованиях:

30. Межвузовский сборник научных трудов Пенза,Пенз.политехи, ин-т,1981,вып.3,с.144-150

31. Лаврушкина Н.С.Метод инвариантного погружения в многомерных нелинейных двухточечных граничных задачах. Редкол. журн."Вестник Ленингр.ун-та,сер.:математика,механика,астрономия", Л.,1984 - 9 с./Рукопись деп. в ВИНИТИ №2404-84 от 17.04.84

32. Лаврушкина Н.С.Организация вычислительного процесса решения нелинейных краевых задач с помощью метода инвариантного погружения. В кн.:Вычислительные процессы и структуры: Межвузовский сборник,ЛИАП,1982,вып.154,с.109-113

33. Лаврушкина Н.С.Применение метода инвариантного погружения к многомерным линейным двухточечным граничным задачам. -Редкол.журн."Вестник Ленингр.ун-та,сер.:математика,механика, астрономия", Л., 1984 12 с. деп. в ВИНИТИ №2403-84 от17.04.84/

34. Методы оптимизации с приложениями к механике космичес -кого полета./Под ред.Лейтмана Дж. М,:Наука,1965

35. Милн В.Э.Численное решение дифференциальных уравнений, -М.:ИЛ,1955

36. Моисеев Н.Н.Элементы теории оптимальных систем. М.: Наука,1975

37. Монастырный П.И.К теории метода инвариантного погружения для граничных задач. Доклады АН БССР,т*22,№4,1978

38. На Ц.Вычислительные методы решения прикладных граничных задач. М.:Мир,1982

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

40. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. М.:Наука,1965

41. Понтрягин Л. С.,Болтянский В.Г.,Гамкрелидзе Р.В.,Мищенко Е.Ф. Математическая теория оптимальных процессов.-М.:Наука,1969

42. Рейнгольд Э.,Нивергельт Ю.,Део Н. Комбинаторные алгоритмы. Теория и практика. М.:Мир,1980

43. Хемминг Р.В, Численные методы. М.:Наука,1972

44. Холл Дж.,Уатт Дж. Современные численные методы решения обыкновенных дифференциальных уравнений. М.:Мир,1979

45. Шаманский В.Е. Методы численного решения краевых задач на ЭЦВМ,ч.Г Киев:изд-во АН УССР,1963

46. Шаманекий В.Е. Методы численного решения краевых задач на ЭЦВМ,ч.2 Киев: Наукова думка,1966

47. U. AZspaugk, H.H. Kanada, Д. Каеъёа1.aíion о4 fmrar/ané Ih?éeototíng to ¿/¡е. Ьискбсид of Columns Journal о/ С О fr? ры i. <? ííOH. phy<s¿có f Vo. f, р. (1970).

48. M9. Ba¿Cy ¿\n</ a. M¿£¿oH. IV¿^.

49. Soma Rece*? ¿ De i/e. ¿'oftmesits ¿h, ßwt-cärtt Irr» c/ot¿Ptg th. /Ifpp с a é¿o*i s— Jou

50. Maihetn*i¿ca£ physic*, Vo 6, a/o. 3, /96<г, p 4S2-4S4.

51. R. BaCe^an anoL Я.Кавъёа . A A/o¿e он Hon ¿¿near 3и torn 4 é¿£¿ ¿y Те c/in¿ep ¿/es Ih\sah¿4ht . — Cfout/о/ Maíheyy,aí¿ca£ Арр вес*-¿loms?1. Vo.6, P-46S-472 (f?63).

52. R. в e Cf/na/i <W R.KaeaSa. On 2f/e c.ip£e. o-f £nv<a r*¿ant Tm ¿e o/o/¿n<p хгпоС Ргорода-ííom Through Tn /wmogeяеous Mec/¿a. — Pro-ceeo/tyijs о/ ¿he /Va¿¿ona£ /4 cao/e ¿>/ Se¿en~ ees о/ &Sff} 16.42, p 629- 63¡>t /956.

53. Sfí, |ш, p. /64G-/649, ШО.

54. R. &eee™a» } R.Káe&£a, G>. M. l4/¿,ig , Oh ihe Pt~¿ne¿p£e. of Inva r¿<¡ni ZmSeoAdtng ano! Orte- oí¿me ns¿onéi£ A/e u ¿ros? Mue-6¿pe¿cai¿ony— Pro cee o/ünjs o/ A/a¿¿o/,a£ /1 c^elemif o<¿ ^c.i'e/7ces o/ ¿AS/J, p. 5Y7- 52 O f /3*7.

55. R. Se¿e^ai, R. K a G-.H fánj. IhrarCémi Iyn£eoAoA¿nj shoA A/eu ¿ron TranSport Theo/-L/ A// : A/eu ¿r-o/7 - /Ve u ¿ ro A?of?c£¿on. Procesases - /four*i¿\€ 0 W<3 AAieand Mechantes, te- f, -262, /fss.

56. F. Bre¿-¿enecAzf-. On ¿Ae <So/u¿¿'&/il/a fue Proáfesr?.s fy

57. Ex íen cAeo/ Im áeo/o/eng — Compesf t l/o.2&, p.333-343, 5£ A. HA. Pre¿ser oAor<fe >-. &e r?e z ecA ání Lm Se otoÍLfn^ Re £ a ¿con. —ceeoAcsr^s04 № ¿cotiaé /Icdc/emy Se ¿es? se $ o<¿

58. USfíf te. 4?, ¡>.№-5$*, Sféf.

59. R.li/- Pretsev a/orfer, fh\/2lr¿4h / I*n¿eM¿0f Replicón. joz. étt e Ph¿n cipfes o^ n'd/iee — PtoceeoA¿f7j 0 ¿f ihe AY$¿¿onct€ Ácade/ny Sc/e/?ees £AS¿ t /0. 44, a/».*, /0. 320-333,6A ÍV.T. A ¿r¿x J)¿ //ere*

60. A?c'ccd ú¿ Type — ¿4*ner¿ca/7

61. Jowrnᣠo<P MaA/iej-nziecs, ¡fo*6¿,Ab2, 246, mó.