Доказательный вычислительный эксперимент в исследовании вариационных задач для квадратичных функционалов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Шишкин, Владимир Андреевич

• Шишкин, Владимир Андреевич
• кандидат физико-математических наук
• 2009

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

Используемые обозначения

Введение

1 Предварительные сведения

1.1 Примеры вариационных задач для квадратичных функционалов

1.2 Минимизация квадратичного функционала.

1.3 Доказательные вычисления.

2 Абстрактная вариационная задача для квадратичного функционала

2.1 Постановка задачи.

2.2 Условия существования решения

2.3 Проекционный метод исследования.

3 Доказательный вычислительный эксперимент

3.1 Алгоритм доказательного вычислительного эксперимента

3.2 Приближённое интегральное уравнение.

3.3 Обобщение на случай функций многих переменных.

4 Программная реализация

4.1 Структура программы

4.2 Вспомогательные процедуры.

4.3 Постановка и решение задачи.

5 Примеры

5.1 Простейшая задача Лагранжа.

5.2 Задача с сосредоточенным отклонением аргумента.

Введение диссертации (часть автореферата) на тему «Доказательный вычислительный эксперимент в исследовании вариационных задач для квадратичных функционалов»

Актуальность исследования. При изучении динамических систем в естественных, технических и экономических науках часто будущее состояние исследуемой системы зависит не только от её настоящего, но также и от предыстории развития [34]. При построении достаточно точных и адекватных моделей сложных систем в большинстве случаев приходится учитывать запаздывание, возникающее вследствие конечных скоростей при распространении информации и перемещении материальных объектов. В некоторых задачах требуется учитывать также и будущее состояние системы [46,49]. Всё это приводит к тому, что при исследовании и оптимизации деятельности таких систем приходится иметь дело с функционалами, содержащими не только локальные, но и с нелокальные операторы [15].

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

Классический подход к управлению линейными системами с квадратичным функционалом описан, например, в [8]. В [1,2] рассматривается решение задачи минимизации квадратичного функционала на основе идей и результатов теории абстрактного функционально-дифференциального уравнения, развитых в работах Пермского семинара. Редукция исходной задачи к задаче минимизации в гильбертовом пространстве описана в [12,13].

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

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

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

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

Задачи:

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

2. теоретически доказать применимость предлагаемого метода к решению вариационных задач с уравнением Эйлера в виде интегрального уравнения Фредгольма второго рода;

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

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

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

6. определить теоретические и практические границы применимости предлагаемого доказательного вычислительного эксперимента.

Объект исследования. В диссертационной работе исследуется задача минимизации вида N

Хх = T2ix)н + (F0, х)х -> min, (0.1а) г=1 р(х) = 0, q{x) ^ 0. (0.1b)

Решение ищется в банаховом пространстве X, изоморфном прямому произведению вещественного сепарабельного гильбертова пространства Н и пространства ш-мерных вещественнх векторов Rrn (X ~Нх Rm). Предполагается, что Тц,Т2г, г = 1,., iV, — линейные ограниченные операторы, действующие из X в Н; Fo Е X*; р и q — аффинные вектор-функционалы.

В квадратичном функционале (0.1а) могут находиться, кроме самой функции а; и её производных любого порядка, интегральные операторы, а также операторы с сосредоточенным или/и распределённым запаздыванием (интегральные операторы Стилтьеса).

Исследуемая задача (O.la)-(O.lb) сводится к задаче минимизации в подходящем гильбертовом пространстве 1 g Z)H ~ + ^о min, (0.2а) g(z) = 0, h(z) ^ 0, (0.2b) где Q — ограниченный самосопряжённый оператор. В работе рассматриваются только те задачи, в которых оператор Q можно записать в виде разности I — К, где I — тождественный оператор, К — вполне непрерывный и самосопряжённый оператор. В этом случае исследование необходимых и достаточных условий существования решения сводится к исследованию обратимости и положительной определённости оператора I — К интегрального уравнения Фредгольма второго рода z-Kz = f. (0.3)

Методологическая и теоретическая основа исследования. В ходе проверки необходимых и достаточных существования решения задачи (0.2а)-(0.2Ь), исследуемое уравнение Фредгольма г — Kz = / заменяется близким уравнением г — Kz = / с конечномерным оператором К. Для этого строятся проекции К и / в конечномерные подпространства исходных пространств (Н) и Н соответственно.

Если оператор I — К обратим и положительно определён, то для проверки обратимости и положительной определённости исходного оператора I — К используются теорема о взаимной обратимости близких по норме операторов и теорема о спектре вполне непрерывного самосопряжённого оператора с вполне непрерывным самосопряжённым возмущением.

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

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

Структура диссертации. Работа состоит из пяти глав.

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

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

Для проверки необходимых и достаточных условий существования решения предлагается заменить исходный объект (0.3) более простым — уравнением Фредгольма второго рода с конечномерным ядром г — Кпг = уп. Обосновывается выбор метода аппроксимации К и / на основе проекции в подпространства, натянутые на подмножества .фТ1} заданной'полной системы функций {Фг}™-, ортогональных с единичным весом.

Если уравнение г — Кпг =■ уп имеет решение, то проверка разрешимости исходного уравнения осуществляется на основе теоремы об обратном операторе с помощью сравнения значений \\К — Кп||^(нп) и \\(1 — Кп)~гИ^Нп)■ Для проверки достаточного условия существования решения исходной вариационной задачи оценивается нижняя граница спектра оператора /• — К, для чего используется теорема о спектре возмущённого ограниченного самосопряжённого компактного1 оператора.

Если необходимые и достаточные условия существования решения выполнены, строится решение приближённого уравнения 5 и оценивается, норма разности между построенным решением 2 и истинным решением исходной задачи

В третьей главе описывается конструктивная реализация предлагаемого подхода для пространства Н = Ь2[а, 6].

Даётся обоснование выбора в качестве базиса аппроксимации ортогональных многочленов Лежандра или системы ортогональных функций Радемахера-Уолша.

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

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

В конце главы рассматривается случай Н = Ь2 ([а^ 61] х • • • х [а^, 6^]).

Четвёртая глава посвящена описанию особенностей программной реализации.

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

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

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

Приложение содержит тексты программ с краткими комментариями.

Научная новизна исследования.

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

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

• Определены границы применимости предлагаемого подхода.

Апробация результатов исследования. Результаты диссертационного исследования были опубликованы в работах автора [28-33, 47] и в работах [21,41], написанных в соавторстве. Из результатов совместных работ в диссертацию вошли только результаты, полученные автором лично.

Основные результаты диссертации докладывались и обсуждались на Пермском городском семинаре по функционально-дифференциальным уравнениям (1995-2006 гг., руководитель проф. Азбелев Н. В.), Ижевском семинаре по дифференциальным уравнениям и задачам управления (1999 г., руководитель проф. Тонков Е. Л.), семинаре Лаборатории конструктивных методов исследования динамических моделей (в 2005 и 2008 гг., руководитель проф. Максимов В. П.), Пермском городском теоретическом семинаре "Фундаментальные и прикладные модели управления экономикой" (2006 г., руководители проф. Аверин В. И. и проф. Пер-ский Ю. К.), Междуродной конференции "Информационные технологии в инновационных проектах" (Ижевск, 1999 г.), III Всероссийском семинаре "Теория сеточных методов для нелинейных краевых задач" (Казань, 2000 г.), региональной конференции "Экономика и управление: актуальные проблемы и поиск путей решения" (Пермь, 2004 г.), IV Международном конгрессе по математическому моделированию (Нижний Новгород, 2004 г.), конференции "Современные проблемы прикладной математики и математического моделирования" (Воронеж, 2005 г.).

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Шишкин, Владимир Андреевич

Заключение

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

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

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

• оператор <3 в (2.4а) не может быть представлен в виде разности I — К, где I — тождественный оператор, К — самосопряжённый вполне непрерывный оператор;

• оператор I — К не является регулярным;

• спектр оператора I — К не содержит нулевых собственных чисел, однако в ходе вычислительного эксперимента не удаётся построить такой приближённый конечномерный оператор КТ1, чтобы было выполнено условие (2.13);

• система линейных алгебраических уравнений (3.7) имеет настолько большую размерность, что с помощью имеющейся в наличии вычислительной техники не удаётся получить её решение, построить характеристический многочлен матрицы коэффициентов, построить систему Штурма или оценить норму резольвентного оператора за приемлемое время.

Список литературы диссертационного исследования кандидат физико-математических наук Шишкин, Владимир Андреевич, 2009 год

1. Азбелев, Н. В. Функционально—дифференциальные уравнения и вариационные задачи / Н. В. Азбелев, Ю. Култышев, В. 3. Цалюк.— Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика», 2006. — 122 с.

2. Азбелев, И. В. Элементы современной теории функционально- дифференциальных уравнений. Методы и приложения / Н. В. Азбелев, В. П. Максимов, Л. Ф. Рахматуллина. — М.: Институт компьютерных исследований, 2002. — 384 с.

3. Алексеев, В. М. Оптимальное управление / В. М. Алексеев, В. М. Тихомиров, В. Фомин.— М.: Наука. Гл. ред. физ.-мат. лит., 1979. — 432 с.

4. Алефельд, Г. Введение в интервальные вычисления / Г. Алефельд, Ю. Херцбергер.— М.: Мир, 1987. — 360 с.

5. Алтунин, А. Е. Модели и алгоритмы принятия решений в нечетких условиях / А. Е. Алтунин, М. В. Семухин.— Тюмень: Изд-во Тюменского государственного ун-та, 2000. — 352 с. www.plink.ru/tnni.

6. Арнольд, В. И. Математические принципы классической механики / В. И. Арнольд. — М.: Эдиториал УРСС, 2000. — 408 с.

7. Арнольд, В. И. Математические принципы классической и небесной механики / В. И. Арнольд, В. В. Козлов, А. И. Нейштадт.— 2-е, перераб. и доп. изд. — М.: Эдиториал УРСС, 2002. — 416 с.

8. Афанасьев, В. Н. Математическая теория конструирования систем управления / В. Н. Афанасьев, В. Б. Колмановский, В. Р. Носов. — 2-е, доп изд. — М.: Высш. шк., 1998. — 574 с.

9. Бабенко, К. И. Основы численного анализа / К. И. Бабенко. — Москва- Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. — 848 с.

10. Гарантированная точность решения систем линейных уравнений в евклидовых пространствах / К. Годунов, А. Г. Антонов, О. П. Кирилюк, В. И. Костин. — Новосибирск: Наука, Сиб. отделение, 1988. — 465 с.

11. Голуб, Д. X. Матричные вычисления / Д. X. Голуб, Ч. Ф. Ван Лоун. — М.: Мир, 1999.—548 с.

12. Груздев, А. А. О редукции экстремальных задач к линейным уравнениям в гильбертовом пространстве / А. А. Груздев // Изв. ВУЗов. Математика. — 1993. — № 5 (372). — 36-42.

13. Гусаренко, А. Оптимальное управление: экстремальные и вариационные задачи / А. Гусаренко. — Пермь: Перм. ун-т, Перм. техн. ун-т, 2001. — 86 с.

14. Данфорд, Н. Линейные операторы. Общая теория / И. Данфорд, Д. Шварц. — М.: Издательство иностранной литературы, 1962. — 896 с.

15. Каменский, Г. А. Экстремумы функционалов с отклоняющимися аргументами / Г. А. Каменский, А. Л. Скубачевский.— М.: МАИ, 1979.— 54 с.

16. Канторович, Л. В. Функциональный анализ / Л. В. Канторович, Г. П. Акилов.— М.: Наука. Гл. ред. физ.-мат. лит., 1977. — 744 с.

17. Кнут, Д. Э. Искусство программирования / Д. Э. Кнут.— 3-е изд.— М.: Издательский дом «Вильяме», 2000. — Т. 1. Основные алгоритмы. — 720 с.

18. Кнут, Д. Э. Искусство программирования / Д. Э. Кнут.— 3-е изд.— М.: Издательский дом «Вильяме», 2000. — Т. 2. Получисленные алгоритмы. — 832 с.

19. Колмогоров, А. Н. Элементы теории функций и функционального анализа / А. Н. Колмогоров, В. Фомин. — 4-е, перераб изд.— М.: Наука. Гл. ред. физ.-мат. лит., 1976.— 545 с.

20. Ландау, Л. Теоретическая физика: учебное пособие в 10 т. / Л. Ландау, Е. М. Лифшиц.— 4-е, исир. изд.— М.: Наука. Гл. ред. физ.-мат. лит., 1988. — Т. I. Механика. — 216 с.

21. Максимов, В. П. Вычислительный эксперимент при оптимизации процессов с сегрегацией / В. П. Максимов, А. Н. Румянцев, В. А. Шишкин // Журнал физической химии. — 1997. — Т. 71, № 10. — 1913-1916.

22. Прасолов, В. В. Многочлены / В. В. Прасолов. — 2-е, стереотипное изд. — М.: МЦНМО, 2001. - 336 с.

23. Пу, Т. Нелинейная экономическая динамика / Т. Пу. — Ижевск: Издательский дом «Удмуртский университет», 2000. — 200 с.

24. Рисе, Ф. Лекции по функциональному анализу / Ф. Рисе, Б. Сёкефальви- Надь. — М.: Мир, 1979. — 569 с.

25. Треногий, В. А. Функциональный анализ / В. А. Треногий.— М.: ФИЗ- МАТЛИТ, 2002. — 488 с.

26. Фаддеев, Д. Вычислительные методы линейной алгебры / Д. Фаддеев, В. Фаддеева. - СПб.: Лань, 2002. — 736 с.

27. Шарый, П. Интервальные алгебраические задачи и их численное решение: Дисс... докт. физ.-мат. наук: 01.01.07. — Новосибирск, 2000. — 327 с.

28. Шишкин, В. А. Конструктивный подход к исследованию вариационных задач для квадратичных функционалов / В. А. Шишкин // Экономическая кибернетика: методы и средства эффективного управления. — Пермь, 2000. - 90-94.

29. Шишкин, В. А. Конструктивный подход к исследованию вариационных задач для квадратичных функционалов / В. А. Шишкин // Материалы Всероссийского семинара "Теория сеточных методов для нелинейных краевых задач". — Казань: 2000. — 135-137.

30. Шишкин, В. А. Вариационные задачи для квадратичных функционалов, доказательный вычислительный эксперимент / В. А. Шишкин // Вестник Тамбовского университета. Серия Естественные и технические науки. — 2006. - Т. 11, № 3. - 268-269.

31. Chukwu, Е. N. Stability and time—optimal cointrol of hereditary systems / Б. N. Chukwu. — USA: Academic Press, Inc, 1992. — 509 pp.

32. Higham, N. J. Accuracy and stability of numerical algorithms / N. J. High- am. — USA, Philadelphia: SIAM, 1996. — 688 pp.

33. Kaucher, E. Computer arithmetic, scientic computation and mathematical modelling / E. Kaucher, S. M. Markov, G. Mayer // IMACS Annals on Computing and Appl. Math. — 1992. — no. 12.

34. Kearfott, R. B. INTLIB: A Portable FORTRAN 77 Interval Standard Function 1.ibrary / R. B. Kearfott. — USA, University of Southwestern Louisiana, 1995.

35. Kearfott, R. B. INTERVAL ARITHMETIC: A Fortran 90 Module for an Interval Data Type / R. B. Kearfott. — USA, University of Southwestern Louisiana, 1996.

36. Kulisch, U. Computer Arithmetic in Theory and Practice / U. Kulisch, W. L. Miranker. — New York: Academic Press, 1981.

37. Kushner, B. A. The constructive mathematics of A. A. Markov / B. A. Kushn- er // The Mathematical Association of America. Monthly. — Vol. 113, no. 6. — Pp. 559-566.

38. Maksimov, V. P. On constructing solutions of functional differential systems with a guaranteed precision / V. P. Maksimov, A. N. Rumyantsev, V. A. Shishkin // Functional Differential Equations. — 1995. — Vol. 3, no. 1-2. - Pp. 135-144.

39. Moore, R. E. Interval arithmetic and automatic analysis in digital computing / R. E. Moore / Stanford Univercity. — Stanford: 1962. — 134 pp.

40. Moore, R. E. The automatic analysis and control of error in digital computation based on the use of interval numbers / R. E. Moore // Error in Digital Computation. — Vol. 1. — New York: John Wiley & Sons, Inc., 1965. — P p . 61— 130.

41. Moore, R. E. Interval Analysis / R. E. Moore, T . Yang. — Sunnyvale, California: Lockheed Aircraft Corporation, Missiles and Space Division, 1959. — Vol. 1 . - 4 6 pp.

42. Neumaier, A. Interval Methods for Systems of Equations / A. Neumaier.— Cambridge: Cambridge Univercity Press, 1990.

43. Schulman, L. S. Some differential-difference equations containing both ad vance and retardation / L. S. Schulman / / J. Math. Phys. — 1974. — Vol. 15, no. 3. — Pp. 295-298.

44. Shishkin, V. A. Computer-assisted study of variational problems with quadrat ic functionals / V. A. Shishkin / / Book of Abstracts. VI International Congress of Mathematical Modeling. — University of Nizhny Novgorod, 2004. — P. 123.

45. Wheeler, J. A. Classical electrodinamics in terms of direct interparticle ac tion / J. A. Wheeler, R. P. Feynman / / Reviews of Modern Physics. — 1945. — Vol. 21, no. 3. - Pp. 425-433.

46. Wheeler, J. A. Interaction with the absorber as the mechanism of radiation / J. A. Wheeler, R. P. Feynman / / Reviews of Modern Physics. — 1945. — Vol. 17, no. 2 and 3. — Pp. 157-179.