авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

Динамические системы, вып. 22 (2007), 3–10

ДИНАМИЧЕСКИЕ СИСТЕМЫ

Межведомственный

научный сборник

УДК 539.3

О построении конформного отображения

крестообразной области методом

последовательных приближений

А. А. Кушнарёв, В. Н. Чехов

Таврический национальный университет им. В.И. Вернадского,

Симферополь 95007. E-mail: mak@mak.crimea.ua, chekhov@crimea.edu

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

Как известно задача о кручении сводится к решению уравнения Пуассона. Ме тод, используемый при решении данного дифференциального уравнения, – метод конформных отображений. Использование данного подхода упрощает решение за дачи о кручении. Решение выражается через конформное отображение, которое преобразует круг единичного радиуса ( || 1 ) в заданную область (в данном случае крестообразную). Но нахождение такого конформного преобразования са мо по себе является не простой задачей.

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

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

Изложение основных положений этих методов можно найти в обзорных ста тьях: М. К. Говурин и Л. В. Канторович [2], а также в монографиях Л. В. Канторо вича и В. И. Крылова [3], В. Коппенфельса и Ф. Штальмана [4], А. Г. Угодчикова, М. И. Длугача, А. Е. Степанова [5], П. Ф. Фильчакова [7] и др.

Рассмотрим призматический изотропный стержень призматическое тело, ограниченное цилиндрической (боковой) поверхностью и двумя основаниями кре стообразной формы с заданными размерами a и b (см. Рис. 1), перпендикулярными c А.А. КУШНАРЁВ, В.Н. ЧЕХОВ 4 А.А. КУШНАРЁВ, В.Н. ЧЕХОВ к образующей;

длина l (расстояние между основаниями) значительно больше раз меров оснований. Отнесем стержень к правой системе координат xOyz1, совместив плоскость xOy с одним из оснований, а ось z1 направим по оси стержня.

Рис. 1.

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

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

Представление приближенного выражения отображающей функции z = () в виде полинома m Ck k z = () = (1) k= существенно облегчает в большинстве случаев решение краевых задач. В рабо те А. Г. Угодчикова [5] был разработан метод построения интерполяционных по линомов для односвязных и двухсвязных областей с помощью интерполяционных полиномов Лагранжа и дана методика построения последовательных приближе ний с введением промежуточных узлов интерполяции.

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

Отметим, что в угловых точках конформность нарушается и добиться точного воспроизведения угловых точек, когда отображающая функция интерполируется полиномом (1) конечной степени, естественно, нельзя. Поэтому кусочно-гладкую ISSN 0203–3755 Динамические системы, вып. 22 (2007) О ПОСТРОЕНИИ КОНФОРМНОГО ОТОБРАЖЕНИЯ кривую – границу области S, следует преобразовать в кривую L, которая име ет непрерывно изменяющуюся касательную. В большинстве случаев углы можно скруглить с помощью дуг постоянного радиуса, как это и имеет место в деталях машин и элементах конструкций. Для крестообразной области углы интерполи руются четвертями окружностей. Зависимость напряжения в угловых точках от радиуса интерполирующих окружностей нами так же исследована.

Полином по положительным степеням (1) является функцией, регулярной в круге || 1. Поэтому, необходимо найти такие значения коэффициентов Ck = k +ik (k = 1,..., m), при которых кривая L, имеющая параметрическое уравнение z = (ei ), во-первых, не имела бы двойных точек и точек возврата, во-вторых, имела бы с заданной кривой ряд общих точек и, в-третьих, отклонения кривой L от заданной границы L области S лежали бы в допустимых пределах. Кривая L кусочно-гладкая кривая, у которой углы области интерполируются дугами.

При решении конкретных задач часто приходится встречаться с областями, которые имеют одну или несколько q осей симметрии. Если выбрать начало координат в точке пересечения осей симметрии, а ось направить по одной из этих осей, то интерполяционный полином, совпадающий в интервале 0 /q со значением отображающей функции в m1 узлах интерполяции = j = eij, где j = qm1 j (j = 0... m1 ), будет иметь вид 2m1 dqk1 +1 qk1 + z = m1 () = (2) k1 = Здесь коэффициенты dk = dqk1 +1 являются действительными и вычисляются со гласно выражениям:

m1 1 1 k dk = |z0 | + (1) q |zm1 | + xj cos kj + yj sin kj (3) m1 2 qm1 qm j= где zj = xj +iyj – координаты точек Mj границы L области S, в которые переходят при конформном отображении точки j (j = 0... m1 ) границы единичного круга значения отображающей функции в узлах интерполяции.

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

mk B = rCr C r+k (k = 0... m 1) k (4) r= B = kD + B (k = 1... m 1) k k k Тогда касательное напряжение может быть представлено формулой:

m µ B k k = B0 + 2Re (5) | ()| k= ISSN 0203–3755 Динамические системы, вып. 22 (2007) 6 А.А. КУШНАРЁВ, В.Н. ЧЕХОВ Есть одна особенность, описанная в [6] – это выбор способа сноса точек. Для кре стообразного профиля, в котором углы заменяются четвертями окружностей, снос производится перпендикулярно касательной.

Единственная трудность, с которой может столкнуться программист при ре ализации данного алгоритма на компьютере – выбор начальных значений для (0) алгоритма последовательных приближений (Mj ).

В работе Угодчикова [5] был предложен метод выбора начального приближе ния с помощью прибора ЭГДА (электрогидродинамических аналогий). Имея такой прибор можно выбрать наилучшее начальное приближение.

Но применение данного прибора составляет некоторые трудности. Нами же при реализации алгоритма были опробованы различные способы задания начальных (0) значений Mj без применения ЭГДА и иных приборов. В частности, было рас (0) смотрено равномерное распределение точек Mj на окружности для различных радиусов, но данный подход не дал хорошей сходимости алгоритма. Был предло (0) жен вариант задания начальных точек Mj равномерное распределение (рав ноотстоящие точки) на сторонах четверти профиля для промежутка 0 q (в случае крестообразного профиля, число осей симметрии q = 4). Именно этот подход и дал хорошие результаты.

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

Ниже, на рисунке 2 приведена работа алгоритма последовательных приближе ний. Видно, как с каждым шагом кривая, описываемая полиномом, приближается к заданному крестообразному профилю. Так же можно увидеть как меняется кри визна K во внутреннем углу. В данном случае углы были заменены четвертями окружностей с радиусом r = 103.

Построены графики (Рис. 3) зависимости напряжений во внутренних углах об ласти от радиуса закругления четвертей окружностей, с помощью которых сгла живались углы. На данном рисунке можно увидеть такую зависимость для про филя с размерами (согласно рис. 1) d = 2a и отношением a = 4.

b ISSN 0203–3755 Динамические системы, вып. 22 (2007) О ПОСТРОЕНИИ КОНФОРМНОГО ОТОБРАЖЕНИЯ Таблица 1.

k m = 61 m = 101 m = 1 0.78028922 0.82116796 0. 5 0.20028495 0.20394083 0. 9 0.08703809 0.06124697 0. 13 0.04376615 0.01305433 0. 17 0.01795330 -0.01342030 -0. 21 0.00644890 -0.01969286 -0. 25 -0.00046611 -0.01488543 -0. 29 -0.00045355 -0.00674391 -0. 33 -0.00007269 0.00165330 0. 37 0.00092887 0.00649329 0. 41 0.00366730 0.00782729 0. 45 0.00309507 0.00605093 0. 49 0.00374463 0.00319787 0. 53 0.00308319 0.00062175 -0. 57 0.00130216 -0.00095103 -0. 61 0.00000000 -0.00107050 -0. 65 -0.00066082 -0. 69 0.00000344 0. 73 0.00061410 0. 77 0.00062466 0. 81 0.00087378 0. 85 0.00084109 0. 89 0.00084264 0. 93 0.00099720 0. 97 0.00050527 0. 101 0.00000000 0. 105 0. 109 0. 113 -0. 117 -0. 121 -0. 125 0. 129 0. 133 0. 137 0. 141 0. ISSN 0203–3755 Динамические системы, вып. 22 (2007) 8 А.А. КУШНАРЁВ, В.Н. ЧЕХОВ (a) 1, K = 8.4194 (b) 7, K = 29. (c) 14, K = 936. Рис. 2. Номер шага, кривизна во внутреннем углу ISSN 0203–3755 Динамические системы, вып. 22 (2007) О ПОСТРОЕНИИ КОНФОРМНОГО ОТОБРАЖЕНИЯ Рис. 3.

Решение, полученное с помощью данного численного метода конформных отоб ражений, можно сравнить с решением, полученным с помощью метода Арутюняна Абрамяна [1]. Далее приведены значения жесткости крестообразного стержня на кручении, полученные методом конформных отображений и методом Арутюняна Абрамяна (таблица 2).

Жесткость на кручении определяется как C = 2G ud (6) () где G – модуль сдвига. Для удобства будем сравнивать величину C/Ga4 :

Таблица 2.

b 1.5 2.0 2.5 3.0 4. a Метод Арутюняна-Абрамяна 0.580 1.050 1.467 1.844 2. Метод конформных отображений 0.586 1.050 1.470 1.842 2. ISSN 0203–3755 Динамические системы, вып. 22 (2007) 10 А.А. КУШНАРЁВ, В.Н. ЧЕХОВ В заключение отметим, что представленный метод имеет много преимуществ, одним из которых является несложная программная реализация. Одно из удобств в его программировании состоит в том, что модули (библиотеки с набором функ ций), написанные для конкретной области, легко расширяются и адаптируются для других более сложных областей. Для таких областей нахождение конформно го отображения в аналитической форме, удобной для практического применения, невозможно, но приближенно посчитать с помощью этого метода не составляет труда.

Список цитируемых источников 1. Арутюнян Н. X., Абрамян Б. Л. Кручение упругих тел. М. : Физматгиз, 1963.

2. Говурин М.К., Кантарович Л.В. Приближенные и численные методы. //Математика в СССР за сорок лет М.: Физматгиз, 1959, стр. 846- 3. Канторович Л.В., Крылов В.И. Приближенные методы высшего анализа. М.-Л.:

Физматгиз, 1962.

4. Коппенфельс В., Штальман Ф. Практика конформных отображений. М.: ИЛ, 1963.

5. Угодчиков А.Г., Длугач М.И., Степанов А.Е. Решение краевых задач плоской теории упругости на цифровых и аналоговых машинах. Учеб. пособие для вузов. М. :

Высш. школа 1970.

6. Угодчиков А.Г., Швецов А.В., Ботов В.А. О новой методике сноса внеконтурных точек при конформном отображении // Прикладая механика. 1973. Т. 9, № 11.

С. 81–84.

7. Фильчаков П.Ф. Приложенные методы конформных отображений. Киев.: УССР, 1964.

Получена 18.02. ISSN 0203–3755 Динамические системы, вып. 22 (2007) Динамические системы, вып. 22 (2007), 11– ДИНАМИЧЕСКИЕ СИСТЕМЫ Межведомственный научный сборник УДК 519.642+517. О минимизации объема дискретной информации при решении некорректных задач Е. А. Лукьянова, Е. А. Волынец Таврический национальный университет им. В.И. Вернадского, Симферополь 95007. E-mail: lukyanovaea@mail.ru Верховная Рада АРК, Симферополь, 95003. E-mail: gentoo@list.ru Аннотация. Построен новый класс проекционных методов решения некорректных задач в смысле Адамара. Установлено, что методы из этого класса достигают оптимальный порядок точности восстановления нормального решения при минимально возможных затратах галеркин ской информации.

1. Введение Пусть X - гильбертово пространство со скалярным произведением (·, ·) и по рождаемой им нормой x = (x, x).

В пространстве X рассмотрим линейное операторное уравнение I рода Ax = f, (1.1) где свободный член f принадлежит множеству Range(A) := {f : f = Ag, gX}.

Будем считать, что вместо функции f задано некоторое её возмущение f X, такое что f f, 0.

В настоящей работе исследуется задача приближенного восстановления реше ния (1.1) с минимальной нормой в X, которое принято называть нормальным решением и обозначать x†. В отношении x† примем стандартное предположение гладкости x† M, (A) = {x : x = |A| u, u }. (1.2) Здесь |A| = (A A)1/2, A - сопряженный к A оператор, 0 известный пара метр, а об неизвестном параметре, характеризующем степень гладкости реше ния, известно лишь, что он принадлежит интервалу [1, 1 ], 1 1.

Хорошо известно (см., например, [1, с.43]), что Range(|A| ) = Range(A ) при любом 0 и элементы множества M, (A) образуют всюду плотное множество c Е. А. ЛУКЬЯНОВА, Е. А. ВОЛЫНЕЦ 12 Е. А. ЛУКЬЯНОВА, Е. А. ВОЛЫНЕЦ в подпространстве Ker(A), которому принадлежит x†, то есть любое нормальное решение уравнения (1.1) может быть сколь угодно близко приближено элементом из M, (A).

Выберем в X некоторый ортонормированный базис E = {ek }. Под Pm, k= как обычно, будем понимать ортопроектор на линейную оболочку элементов e1, e2,..., em, то есть Pm f = m (f, ek )ek. Пусть r, s N. Обозначим через H r,s k= класс линейных компактных операторов A, A, действующих в X и удовле творяющих условиям (I Pm )A r mr, A(I Pm ) s ms (1.3) при любых m = 1, 2,... и некоторых фиксированных r s и константах r, s 0.

r,s Будем считать, что H не является пустым множеством.

В случае X = L2 (0, 1) содержательным примером уравнения (1.1) с оператором r,s AH может служить интегральное уравнение Фредгольма первого рода Ax(t) k(t, )x( )d = f (t), t [0, 1], с ядром k(t, ), которое имеет r ограниченных в метрике L2 (0, 1) производных по внешней переменной и s производных – по внутренней. Тогда в качестве базиса E, удовлетворяющего (1.3), могут быть использованы: подпространство тригоно метрических многочленов (в случае периодических коэффициентов k(t, ), f (t)) и ортонормированная система полиномов Лежандра, рассматриваемая на отрезке [0, 1] (в общем случае).

2. Постановка задачи r,s Класс уравнений (1.1) с A H и f, заполняющими весь шар в пространстве X радиуса с центром в f, где f AM, (A) = {f : f = Av, vM, (A)}, а пробегает весь интервал [1, 1 ], обозначим через r,s.

, Известно (см., например, [1, с.14]), что если x† M, (A), то гарантирован ная точность восстановления такого решения не может быть меньше величины 1/(+1) /(+1).

Под дискретной информацией об уравнении (1.1) будем понимать набор зна чений скалярных произведений следующего вида (Aej, ei ), (f, ei ), (2.1) где элементы {ei } составляют базис, фигурирующий в определении класса опе i= r,s раторов H. Дискретную информацию вида (2.1) принято называть галеркинской информацией, а методы, использующие для своей реализации галеркинскую ин формацию – проекционными.

Целью настоящей работы является построение проекционных методов решения (1.1), достигающих на всем классе r,s оптимальный порядок точности O( /(+1) ), с минимально возможными затратами галеркинской информации (2.1).

ISSN 0203–3755 Динамические системы, вып. 22 (2007) О МИНИМИЗАЦИИ ОБЪЕМА ИНФОРМАЦИИ В случае r = s эта задача была решена ранее в [2]. Очевидно, что при фик сированном s рассматриваемый класс уравнений r,s, где r s, уже класса s,s,, с изотропной гладкостью, который был рассмотрен в [2]. Ниже будет показано, что в нашем случае за счет сужения класса уравнений удается сократить объ ем используемой галеркинской информации на логарифмический множитель по сравнению с результатом, полученным в [2].

3. Один класс регуляризирующих методов Поскольку в уравнении (1.1) оператор A – компактный, то такая задача явля ется некорректной в смысле Адамара. В силу этого факта построение устойчивого приближения к x† требует применения специальных регуляризирующих методов (см. [3]), осуществляющих переход от некорректной задачи к регуляризованному уравнению, процесс приближенного решения которого устойчив.

В рамках настоящей статьи ограничимся одним классом регуляризирующих методов, который впервые был введен в рассмотрение в [4]. Итак, под методом ре гуляризации будем понимать оператор R = R (A) : XX, такой, что в качестве приближенного решения берется элемент x = R (A)f, где 0 называют па раметром регуляризации и R (A) = g (A A)A. Здесь g () измерима по Борелю на отрезке [0, ] и удовлетворяет условиям sup |1 g ()|, (3.1) sup 1/2 |g ()| 1/2, (3.2) где 0, 1 2 1, (3.3) (0 = 1), - положительные не зависящие от константы и квалифика ция метода R. Условиям (3.1)-(3.3) удовлетворяют такие хорошо известные ме тоды регуляризации, как, например, метод Тихонова с g () = ( + )1 и = 1, метод Ландвебера с g () = 1 [1 (1 µ)1/ ] и =, 0 µ 2, а так же метод асимптотической регуляризации (или метод установления) с g () = 1 (1 exp(/)) и =.

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

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

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 14 Е. А. ЛУКЬЯНОВА, Е. А. ВОЛЫНЕЦ В настоящей статье для построения конечномерного приближения предлагает ся модифицированная проекционная схема дискретизации, суть которой состоит в замене оператора A и элемента f их конечномерными аналогами следующего вида 2n n An = (P2k P2k1 )AP2bnak + P1 AP2bn, P2n f = (f, ek )ek, (4.1) k=1 k= где задействован базис E = {ek }, фигурирующий в определении H. r,s k= В рамках предлагаемой проекционной схемы (4.1) используется гиперболиче ский крест, под которым понимается множество координатной плоскости i0j сле дующего вида a,b = n Qk, Q0 = {1} {2bn }, n k= (4.2) k1 k bnak Qk = (2, 2 ] [1, 2 ], k = 1, 2,..., n, где a и b - произвольные вещественные числа, такие что b a 0. Фигура a,b n состоит из прямоугольников Qk, k = 0, 1,..., n, левые нижние углы которых име ют координаты (2k1, 1), а правые верхние (2k, 2bnak ). Координаты (i, j) пра вых верхних углов прямоугольников Qk лежат на гиперболе ia j = 2bn, а само множество a,b лежит внутри области, имеющей границы {i = 2n, 1j2(ba)n } и n {ia j = 2bn, 2(ba)n j2bn }. В случае a = 0 фигура a,b трансформируется в пря n моугольник [2n, 2bn ], т.е. получаем стандартную проекционную схему Галеркина.

Ниже будет показано, что минимальные информационные затраты в рамках ис следуемой задачи достигаются при a 1. Этот факт свидетельствует о том, что модифицированная проекционная схема является более экономичной по сравне нию со стандартным методом Галеркина. Следует тут же отметить, что модифи цированная проекционная схема (4.1) при b = 2 и a = 1 была впервые использована в [5] для решения уравнений (1.1) в случае известного параметра = 2, а в общем виде была приведена в [6].

При вычислении оптимальных значений параметров модифицированной про екционной схемы следует выбирать параметры a и b в зависимости от "дифферен циальных" характеристик оператора уравнения (1.1) и от гладкостных свойств искомого решения, а параметр n – в зависимости от уровня возмущения правой части решаемого уравнения (1.1).

Таким образом, предлагаемая проекционная схема состоит в выборе скалярных произведений (2.1) с номерами из гиперболического креста a,b (4.2), задейство n ванных при построении конечномерных элементов вида (4.1).

Общее количество скалярных произведений (2.1), используемых при дискрети зации операторного уравнения (1.1) в рамках модифицированной проекционной схемы (4.1), обозначим card(a,b ). Известно [7, §1.2], что для величины card(a,b ) n n справедливы следующие (порядковые по n) оценки (ba+1)n 2, a card(a,b ) 2bn n, a=1. (4.3) n bn 2, a ISSN 0203–3755 Динамические системы, вып. 22 (2007) О МИНИМИЗАЦИИ ОБЪЕМА ИНФОРМАЦИИ Величину card(a,b ) будем рассматривать в качестве целевой функции, завися n щей от трех параметров: a, b и n. При этом из (4.3) следует, что для отыскания минимума целевой функции (то есть для обеспечения минимальной площади a,b )n требуется вычислить наименьшие значения параметров b и n, а также наибольшее значение параметра a среди допустимых.

5. Регуляризирующие проекционные методы При построении конечномерного приближения к x† будем определять прибли женное решение x по правилу x = R (An )P2n f.

(5.1) При этом регуляризирующий метод R выбирается из описанного выше (см.

§3) класса регуляризаторов, т.е. удовлетворяет условиям (3.1)–(3.3), оператор An представлен в виде (4.1), а в качестве значения параметра дискретизации целесо образно взять (см. [6]) наименьшее целое n 0, такое что 22rn = O(). (5.2) Соответствующая вычислительная процедура останавливается согласно принципу невязки [8], т.е. сразу как только параметр удовлетворит следующему условию b1 P2n f An x b2 (5.3) при некоторых фиксированных константах 2 b1 b2.

Любой регуляризирующий проекционный метод вида (4.1), (5.1)–(5.3) будем обозначать (R, An, b1, b2 ).

6. Минимизация объема галеркинской информации В работе [6] было показано, что для достижения оптимального порядка точно сти на классе s,s в рамках модифицированной проекционной схемы необходимо,, чтобы выполнялись условия An x† P2n f = O(), (6.1) |A| |An | = O( /(+1) ). (6.2) Таким образом, ближайшая наша цель состоит в подборе таких значений пара метров a и b, которые, с одной стороны, способны гарантировать справедливость оценок (6.1), (6.2), а с другой - обеспечивают минимальные затраты галеркинской информации в смысле величины card(a,b ) (4.3).

n Для изложения дальнейших рассуждений нам потребуются 2 вспомогательных соотношения (см. леммы 3.2 и 3.1 [7] соответственно) (An P2n A)|A| u c1 2vn, (6.3) ISSN 0203–3755 Динамические системы, вып. 22 (2007) 16 Е. А. ЛУКЬЯНОВА, Е. А. ВОЛЫНЕЦ A A A An r 22rn + c2 2yn, (6.4) n где c1, c2 - константы, не зависящие от, vn = 2sn(b a), yn = bsn (as r)+ n.

Здесь, как обычно, 0,g log2 n, g = 0.

g+ n = gn,g Далее, запишем очевидное соотношение An x† P2n f An x† P2n f + P2n (f f ) An x† P2n f +. (6.5) В силу (6.3), (6.5) и соотношения An x† P2n f = (An P2n A)|A| u (6.6) имеем An x† P2n f c1 22sn(ba) +. (6.7) Заметим, что согласно (6.1) и (6.7) параметры a, b следует выбирать так, чтобы величина 22sn(ba) не превосходила по порядку.

Чтобы обеспечить (6.2), воспользуемся известной оценкой (см. [9]) min{,1} |A| |An | z() A A A An, n где функция z() ограничена на (0, ).

Откуда с помощью (6.4) получаем |A| |An | c3 [22rn + 2bsn+(asr)+ n ]min{ 2,1}. (6.8) Напомним, что в силу (6.2) величина [22rn + 2bsn+(asr)+ n ]min{ 2,1} не должна пре восходить по порядку /(+1).

Очевидно, что наиболее экономичный выбор области a,b возможен в ситуации, n когда оба слагаемых в правой части (6.8) имеют одинаковый порядок, т.е. при условии 2rn = bsn (as r)+ n. (6.9) В силу (5.2) из (6.9) следует 2bsn+(asr)+ n = O() и значит, c4 2bsn+(asr)+ n.

Аналогично, из соотношения (6.7) получим c5 22bsn+2asn.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) О МИНИМИЗАЦИИ ОБЪЕМА ИНФОРМАЦИИ Далее, рассматривая возможные случаи: а) as r 0, б) as r 0, в) as r = 0 с учетом (5.2), получим три варианта. Непосредственными вычислениями убеждаемся, что случай б), приводящий к значениям b = 2r/s и 1 a r/s при n, выбираемом из условия (5.2), даёт наиболее экономичный крест с точки зрения количества используемой галеркинской информации, причем card(a,b ) = 22nr/s.

n Тем самым нами доказано следующее утверждение.

Лемма. Пусть A H, x† M, (A), [1, 1 ], где 1 1. Если параметр r,s дискретизации n выбран согласно (5.2), b = 2r/s и 1 a r/s, то имеют место соотношения (6.1), (6.2) и card(a,b ) = 22nr/s = O( 1/s ).

n 7. Оптимальная точность проекционных методов При доказательстве основного утверждения нам потребуется следующий факт (см. Лемму 3.2 [9]): для произвольной величины 1 0 и фиксированной функции g, удовлетворяющей условиям (3.1)-(3.3), найдется константа c 0, такая что для всех 0 и (1 g ())2 c (1 g1 ())2 + 1 ((1 g ()))2.

(7.1) Теорема. Пусть в (4.1) b = 2r/s, 1 a r/s, а параметр дискретиза ции n выбран согласно (5.2). Тогда оптимальная по порядку оценка погреш ности O( /(+1) ) достигается в рамках любого проекционного метода вида (R, An, b1, b2 ) на классе уравнений r,s.

, Доказательство. Доказательство проведем с использованием схемы рассужде ний, приведенной ранее при доказательстве теорем 3.3 [9] и 4.1 [10]. Величину погрешности метода (R, An, b1, b2 ) запишем в виде x† x = R,n (An x† P2n f ) + S,n x†, где R,n = g (A An )A, S,n = I g (A An )A An. Тогда с учетом (3.2) и (3.1) n n n n получаем соответственно x† x = S,n x† + 2 1/2, (7.2) I An R,n = I g (An A )An A sup |1 g ()|1.

n n Используя представление An S,n x† = (An An R,n An )x† = = (P2n f An x ) + (I An R,n )(An x† P2n f ) ISSN 0203–3755 Динамические системы, вып. 22 (2007) 18 Е. А. ЛУКЬЯНОВА, Е. А. ВОЛЫНЕЦ и лемму 1, аналогично теореме 4.1 [10] можно показать, что b1 2 An S,n x†, 1/2 1/2 (b1 2)1 An S,n x†. (7.3) Используя полярное разложение оператора An = U (A An )1/2, U = 1, отношение n (3.1) и лемму 1, оценим норму элемента An S,n x† следующим образом 1/2 An S,n x† = 1/2 An S,n |A| u 1/2 An S,n |An | + An S,n (|A| |An | ) 1/2 U S,n |An | + U S,n |An | |A| |An | (+1)/2 /2 + 1/2 c3 z() /(+1). (7.4) Аналогично получим S,n x† = S,n |A| v S,n |An | + S,n |A| |An | /2 /2 + z()c3 /(+1). (7.5) Подстановка (7.4) в (7.3) даёт отношение 1/2 (b1 2)1 ((+1)/2 /2 + 1/2 c3 z() / (+1 ).

Далее, используя (7.2) и полученные выше оценки для 1/2 и S,n x†, находим x† x (/2 /2 + z()c3 /(+1) + +2(b1 2)1 ((+1)/2 /2 + 1/2 c3 z() /(+1) )) = c4 /2 + c5 /(+1), где c4 = (/2 + 2 (+1)/2 (b1 2)1 ), c5 = z()c3 (2 1/2 (b1 2)1 + 1). И окончательно, если 2/+1, имеем следующее соотношение x† x (c4 + c5 ) /+1.

Таким образом, утверждение теоремы доказано для 2/(+1).

Пусть теперь 2/(+1). Далее, с учётом (7.1) получим 2 + 1 An S,n x† 2 ).

S,n x† c ( S1,n x† (7.6) Положим 1 = 2/(+1). С помощью леммы 1 легко установить, что 1 An S,n x† (b2 + 2)2 2/(+1) (7.7) Из (7.5) получим соотношение S1,n x† 2/(+1) (/2 + z()c3 )2. (7.8) ISSN 0203–3755 Динамические системы, вып. 22 (2007) О МИНИМИЗАЦИИ ОБЪЕМА ИНФОРМАЦИИ Подставляя (7.7) и (7.8) в (7.6), находим S,n x† c ((/2 + z()c3 )2 + (b2 + 2)2 ) 2/(+1). (7.9) С учётом отношения 1 = 2/(+1) имеем 1/ 1/2 1 = /(+1). (7.10) Подставляя (7.9) и (7.10) в (7.2), получим x† x c6 /(+1), где c6 = (c (/2 + z()c3 )2 + (b2 + 2)2 )1/2 + 2.

Таким образом, отношение x† x /(+1) max{c6, c4 + c5 } выполняется для любых 0. Теорема доказана.

8. Выводы 1. В работе введен в рассмотрение новый класс регуляризирующих проекци онных методов вида (R, An, b1, b2 ), использующих идею гиперболического креста.

2. В рамках указанных методов построены устойчивые приближения с наилуч шей возможной точностью O( /(+1) ) к нормальным решениям уравнений из класса r,s (r s).

, 3. За счет сокращения класса исследуемых уравнений по сравнению с s,s из, [2], удалось добиться уменьшения объема информационных затрат на лога рифмический множитель.

Список цитируемых источников 1. Вайникко Г. М., Веретенников А. Ю. Итерационные процедуры в некорректных задачах. М.: Наука, 1986. 182 с.

2. Solodky S.G., Lebedeva E. Bounds of information expenses in constructing projection methods for solving ill-posed problems// CMAM 2006. 6, № 1. p. 87– 3. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1979. 285 с.

4. Бакушинский А.Б. Оптимальные и квазиоптимальные методы решения линейных задач, порожденные регуляризующими алгоритмами // Изв.вузов.Математика.

1978. № 11. С. 6–10.

5. Pereverzev S.V. Optimization of Projection Methods for solving Ill-Posed Problems // Computing. 1995. 55. P. 113–124.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 20 Е. А. ЛУКЬЯНОВА, Е. А. ВОЛЫНЕЦ 6. Solodky S.G., A Generalized projection scheme for solving ill-posed problems, J. Inverse Ill Posed Probl. 1999. 7. P. 185–200.

7. Солодкий С.Г. Оптимальные схемы дискретизации операторных уравнений - Диссер тация на соискание ученой степени доктора физ.-мат.наук.-Киев: Ин-т математики НАНУ. 2003. 300 с.

8. Морозов В.А. О выборе параметра при решении функциональных уравнений мето дом регуляризации// ДАН СССР. 1967. 175, № 6. C. 1225–1228.

9. Plato R., Vainikko G. On the Regularization of Projection Methods for solving Ill-posed Problems// Numer.Math. 1990. 57. P. 63–79.

10. Pereverzev S.V., Solodky S.G. An ecient discretization for solving Ill-posed problems//Lec Appl. Math. 1996. 32. P. 643–649.

Получена 01.06. ISSN 0203–3755 Динамические системы, вып. 22 (2007) Динамические системы, вып. 22 (2007), 21– ДИНАМИЧЕСКИЕ СИСТЕМЫ Межведомственный научный сборник УДК 519. Методологические аспекты динамического программирования О.А. Щербина University of Vienna, Vienna 1090, Austria. E-mail: oleg.shcherbina@univie.ac.at Аннотация. Рассмотрены методологические аспекты динамического программирования, в том числе анализируются основные графовые интерпретации динамического программирования, та кие, как блочные диаграммы, выделение бесконтурных орграфов, лежащих в основе вычисли тельной процедуры динамического программирования, а также представление структуры задачи динамического программирования с помощью графа взаимосвязей. Описана классификация за дач динамического программирования на основе анализа бесконтурных орграфов процедуры динамического программирования на сериальные и несериальные задачи, на монадические и полиадические задачи. Приведены примеры классификации задач динамического программиро вания.

1. Введение Динамическое программирование (ДП) является чрезвычайно мощной алго ритмической парадигмой оптимизации последовательных процессов принятия ре шений, имеющей декомпозиционную природу. ДП, более чем другие оптимизаци онные подходы, обеспечивает общую схему анализа многих типов задач. Алгорит мическая схема ДП состоит в погружении решаемой сложной задачи в парамет ризованное семейство задач (иногда называемых подзадачами) и последующем решении этих подзадач, используя принцип оптимальности Беллмана и вытека ющее из него рекуррентное уравнение Беллмана. Принципом оптимальности называется следующая интуитивная идея, предложенная R. Bellman [5]:

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

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

При решении оптимизационных подзадач, порожденных в процессе решения всей c О.А. ЩЕРБИНА 22 О.А. ЩЕРБИНА задачи с помощью ДП, могут быть использованы известные методы оптимизации, такие как линейное, нелинейное и дискретное программирование.

О происхождении самого названия ”динамическое программирование (dynamic programming)” Dasgupta, Papadimitriou, Vazirani пишут [7]:

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

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

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

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

В современных учебниках по исследованию операций описываются только ставшие классическими сериальные задачи ДП, более сложные несериальные ди намические системы, обладающие разветвлениями и контурами, не рассматрива ются. В то же время несериальные динамические системы имеют интересные при ложения в задачах оптимизации водных систем и газопроводов [9]. Более того, со здается впечатление, что сериальное ДП и несериальное ДП (НСДП) используют различные подходы: если сериальное ДП состоит в погружении решаемой задачи в параметризованное семейство подзадач (что требует известного "инсайта") и по следующем решении этих задач, используя рекуррентное уравнение Беллмана, то несериальное ДП использует граф взаимосвязей задачи дискретной оптимизации и последовательно элиминирует переменные. Графовая интерпретация задачи ди намического программирования описывается обычно в виде поиска кратчайшего пути в сети. Многие аспекты ДП остаются и сейчас не до конца ясными, в том числе возможности несериального ДП (НСДП), разница между сериальными и несериальными задачами, классификация задач ДП.

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

ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 2. Графовые структуры в динамическом программировании 2.1. Блочные диаграммы в процедуре динамического программирования Использование блочных функциональных диаграмм является одной из гра фовых интерпретаций и является одним из стандартных способов анализа и оп тимизации дискретных динамических систем. Представление задачи ДП в виде блочных диаграмм часто используется для визуализации структуры задачи. n шаговый последовательный процесс принятия решений состоит из трех компонен тов: множества шагов (или этапов) i = 1,..., N, множества состояний и множе ства решений. Описание многошагового процесса принятия решения с помощью диаграмм показано на рис. 1. В диаграммах шаги представлены схематически с помощью пронумерованных прямоугольников, стрелки показывают входы и вы ходы шагов. i-му шагу соответствуют переменная состояния si, решающая переменная di, выход ri = fi (di, si ), называемый обобщенным доходом шага i. Преобразование si+1 = ti (di, si ) называется функцией перехода.

Сериальная оптимизационная задача для дискретной динамической системы может быть записана в виде N max fi (di, si ) + fN (sN ) (2.1) {s1,...,sN ;

d1,...,dN 1 } i= при ограничениях si+1 = ti (di, si ), i = 1,..., N 1. (2.2) di Di, i = 1,..., N. (2.3) Блочная диаграмма и граф взаимосвязей этой задачи показаны на рис. 1 и рис. соответственно. Эта модель представляет собой дискретный аналог задачи опти d1 d2 dN- s1 s2 sN- s3 sN t 1 d1, s1 t 2 d2, s2 t N-1 d N-1, s N- f1(d1, s1) f2(d2, s2) fN-1(dN-1, sN-1)+ fN(sN) ) Рис. 1. Блочно-диаграммное представление задачи динамического программирования.

мального управления следующего вида:

t max F (t, X, U )dt (2.4) U (t) t ISSN 0203–3755 Динамические системы, вып. 22 (2007) 24 О.А. ЩЕРБИНА при ограничениях Xt = g(t, X, U ), t1 t t2, (2.5) X(t1 ) = X1. (2.6) 2.2. Бесконтурные орграфы в процедуре динамического программирования ДП рассматривает исходную задачу в виде семейства взаимозависимых задач, которые решаются и результаты их решения используются при решении больших задач, пока исходная задача не будет решена. Решение любой подзадачи из се мейства зависит от решений одной или нескольких подзадач на предшествующих уровнях. Зависимости между задачами в процедуре ДП может быть представле на в виде бесконтурного орграфа (directed acyclic graph (DAG)), который в дальнейшем называть просто орграфом. Зачастую этот орграф задан неявно. Его вершинами являются подзадачи, выделенные процедурой ДП, а ребрами – (ин формационные) зависимости между подзадачами: если подзадача B требует для своего решения информацию о решении подзадачи A, это может быть графиче ски изображено с помощью ребра от A к B (рис. 2). Отсюда видно, как можно B A Рис. 2. Предшествование подзадач A и B.

выделить орграф, лежащий в основе алгоритмической схемы ДП, ставя в соответ ствие подзадачам, которые необходимо решить, вершины орграфа, а отношениям предшествования подзадач – ребра орграфа. Если имеются вершины u1,..., uk, от которых стрелки указывают на v, то это означает: подзадача v может быть решена лишь после нахождения решений для подзадач u1,..., uk (рис. 3). Для иллюстрации преимуществ использования орграфов в виде основы вычислитель ной схемы ДП рассмотрим последовательность чисел Фибоначчи, определенную следующим образом:

F0 = 1, F1 = 1, FN = FN 1 + FN 2, N 2.

Нетрудно заметить, что вычисление F3 = F1 + F2 и F4 = F2 + F3 включает вычисление F2. В связи с тем, что для вычисления F5 необходимо знать F3 и F4, наивный подход к вычислению F5 мог бы дважды использовать вычисление F2, попусту теряя время на повторное вычисление решений подзадач, которые уже были решены.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ v u2 uk u Рис. 3. Орграф подзадач схемы динамического программирования.

F F F F1 F2 F2 F F0 F1 F0 F1 F1 F F0 F Рис. 4. Дерево обращений к задачам при вычислении пятого числа Фибоначчи. Это дерево имеет экспоненциальное число вершин.

F F F2 F F0 F Рис. 5. Орграф процесса вычисления пятого числа Фибоначчи с линейным числом вершин.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 26 О.А. ЩЕРБИНА На рис. 4 показано дерево обращений к подзадачам при вычислении F5. Сле дует отметить, что одни и те же задачи решаются неоднократно. Чтобы избегнуть повторных вычислений, имеет смысл сохранять найденные решения. В этом слу чае, если возникает необходимость повторного решения задачи позже, можно про сто найти и использовать ранее вычисленное и сохраненное решение. Этот подход называется мемоизацией. На рис. 5 показан орграф вычислительного процесса пятого числа Фибоначчи.

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

2.3. Графовая интерпретация Бертеле–Бриоши процедуры динамического программирования В работах Mitten, Nemhauser, Aris и Wilde ([3], [4], [13], [15]) классическое сериальное ДП было обобщено для несериальных динамических систем, содержа щих контуры и разветвления, причем в этих работах использовано графическое представление динамической системы в виде блочных диаграмм.

Более общий и перспективный теоретико-графовый подход к решению несери альных оптимизационных задач был предложен в работах Bertele & Brioschi [6].

Рассмотрим несериальную задачу дискретной оптимизации (ДО) с ограниче ниями следующего вида:

fk (Y k ) max F (x1, x2,..., xn ) = (2.7) kK при ограничениях gi (X i ) Ri 0, i M = {1, 2,..., m}, (2.8) xj Dj, j {1,..., n}, (2.9) где Y k {x1, x2,..., xn }, k K = {1, 2,..., t} ;

(2.10) X i {x1, x2,..., xn }, Ri {, =, }, i M = {1, 2,..., m}. (2.11) Определение 1. Две переменные x X и y Y взаимосвязаны в несериальной задаче ДО с ограничениями, если они появляются вместе в одном компоненте целевой функции (ЦФ) или в одном и том же ограничении (другими словами, если переменные входят одновременно во множество X i или во множество Y k ).

Введем графовую интерпретацию несериальной задачи ДО в виде графа вза имосвязей ([6], [2]), естественным образом представляющего структуру оптимиза ционной задачи.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Определение 2. [6]. Графом взаимосвязей несериальной задачи ДО (без огра ничений или с ограничениями) называется неориентированный граф G = (V, X), для которого 1. множество вершин X графа соответствует множеству переменных задачи ДО;

2. две вершины графа смежны тогда и только тогда, когда соответствующие им переменные взаимосвязаны.

Определение 3. Множество переменных, взаимосвязанных с переменной x X, обозначается N b(x) и называется окрестностью переменной x.

Рассмотрим задачу ДО с ограничениями и предположим без потери общно сти, что порядок элиминации переменных следующий: x1,..., xn. Опишем про цедуру элиминации для переменной x1. Переменная x1 входит в подмножество K1 компонентов ЦФ: K1 = k | x1 Y k и во подмножество ограничений U1 :

U1 = {i | x1 X i }.

Одновременно с x1 в компоненты ЦФ Y k, k K1 и в ограничения U1 входят переменные из окрестности N b(x1 ).

Переменной x1 соответствует следующая подзадача P1 исходной задачи ДО:

fk (Y k ) | gi (X i ) Ri 0, i U1, xj Dj, xj N b(x1 ).

h1 (N b(x1 )) = max x kK Исходная задача ДО может быть преобразована следующим образом:

fk (Y k ) | gi (X i ) Ri 0, i M, xj Dj, j N max = x1,...,xn fk (Y k ) + h1 (N b(x1 )) | gi (X i ) Ri 0, i M U1, = max x1,...,xn kKK xj Dj, j X {x1 }.

В новой задаче n 1 переменная;

по сравнению с исходной задачей в ней исключе ны ограничения с индексами из U1 и компоненты ЦФ kK1 fk (Y k ), но появился новый компонент ЦФ h1 (N b(x1 )).

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

На шаге n описанного процесса элиминируется переменная xn и находится оп тимальное значение ЦФ. Затем нужно выполнить обратную часть процедуры ДП для нахождения оптимального решения.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 28 О.А. ЩЕРБИНА s1 d1 s2 d2 s3 sN dN sN 1 Рис. 6. Эквивалентное графовое представление многошагового процесса принятия решений.

Решение задачи ДО с помощью НСДП подробно описано в [1], [2]. Процесс пре образования графа взаимосвязей, соответствующий процедуре НСДП, известен как элиминационный процесс [6]. Описанная выше задача (2.1)–(2.3) имеет граф взаимосвязей (рис. 6) и может быть решена с помощью элиминации переменных [2] в очередности = (sN, dN 1, sN 1..., d1, s1 ).

3. Классификация задач динамического программирования Li & Wah [11], [14] предложили классификацию задач ДП на основе характера зависимостей между подзадачами и функцией композиции. Если решение задачи использует решение единственной задачи предыдущих уровней, то формулировка задачи ДП является монадической, иначе она называется полиадической. В орграфе без контуров вершины могут быть разбиты на уровни, так что задачи на данном уровне зависят только от подзадач предыдущих уровней. В зависимости от связей задач на разных уровнях, формулировка задачи ДП может быть отнесе на либо к сериальным, либо к несериальным задачам. Если задачи семейства на всех уровнях зависят только от результатов решения задач, находящихся на непосредственно предшествующем уровне, то такая задача ДП будет называться сериальной задачей ДП, иначе она называется несериальной задачей ДП. Ис пользуя эти два критерия классификации, можно относить задачи ДП к одному из следующих видов:

• сериально-монадическая, • сериально-полиадическая, • несериально-монадическая, • несериально-полиадическая.

3.1. Монадическая и полиадическая формулировки Формулировка задачи ДП называется монадической, если ее рекуррентное уравнение содержит лишь один рекурсивный член, иначе она называется полиа дической. Это отличие показано на примере поиска кратчайшего пути в сети.

Обозначим cij длина ребра (i, j). Длина пути от источника s до пункта назна чения (стока) t равна сумме длин ребер пути. Пусть f1 (i) минимальная длина ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ пути из i до t. Тогда длина пути из i до t через соседнюю вершину j составляет cij + f1 (j). Для нахождения f1 (i) необходимо сравнить пути, проходящие через все возможные промежуточные вершины. Таким образом, f1 (i) = minj [cij + f1 (j)]. (3.1) Рекуррентное уравнение (3.1) является монадическим, так как включает лишь один рекуррентный член f1 (i).

Рассмотрим более общую задачу поиска оптимального пути из любой вершины i до любой другой вершины j. Можно свести эту задачу к поиску такой проме жуточной вершины k, чтобы кратчайшие пути из i до k и из k до j составляли кратчайший путь из i до j. Рекуррентное уравнение имеет вид:

f3 (i, j) = mink [f3 (i, k) + f3 (k, j)], (3.2) где функция f3 (i, j) минимальная длина пути из i до j. Эта функция полиа дическая, так как она содержит более, чем один рекуррентный член. Для полиа дических формулировок принцип оптимальности Беллмана может быть обобщен добавлением фразы о том, что ”все подпоследовательности оптимальной страте гии также оптимальны” [10]. Например, согласно уравнению (3.2), если известно, что кратчайший путь из i до j проходит через k, то подпуть из i до k этого опти мального пути должен быть оптимальным по отношению ко всем подпутям из i до k;

то же справедливо для подпути из k до j.

3.2. Сериальные и несериальные формулировки Разница между сериальной и несериальной формулировками задач ДП основа на как на виде их целевых функций, так так и на типе рекурсии. По виду целевой функции, задача оптимизации называется сериальной, если каждый компонент целевой функции имеет одну общую переменную с предыдущим компонентом (за исключением первого компонента) и другую общую переменную с последующим компонентом (за исключением последнего компонента), иначе задача называет ся несериальной. Сериальная задача ДО имеет граф взаимосвязей с сериальной структурой (рис. 7). Рассмотрим задачу ДП со следующей целевой фунцией x1 x2 xn xn Рис. 7. Граф взаимосвязей сериальной задачи.

N max gi (xi, xi+1 ), (3.3) X i= ISSN 0203–3755 Динамические системы, вып. 22 (2007) 30 О.А. ЩЕРБИНА где X множество дискретных переменных {xi,..., xN }. В уравнении (3.3) каж дый компонент целевой функции содержит две переменные, связанные лишь с переменными в двух других компонентах, причем взаимосвязи являются сери альными. Так, компонент gi (xi, xi+1 ) связан только с компонентами gi (xi1, xi ) посредством переменной xi и gi+1 (xi+1, xi+2 ) посредством переменной xi+1. В ре зультате, уравнение (3.3) является сериальной задачей оптимизации.

ЦФ несериальной задачи ДО имеет следующий вид:

f (X) = k gl (X l ), (3.4) l= множество дискретных переменных, X l X, где X = {x1,..., xN } моно тонная функция, объединяющая функции gl вместе (например, сумма или произ ведение).

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

4.1. Задача о кратчайшем пути Нахождение кратчайшего пути в сети является известной задачей комбина торной оптимизации [8], [12]. ДП и задача о кратчайшем пути очень схожи. Как показано выше, рекуррентные соотношения ДП могут быть представлены как за дачи поиска оптимального пути в орграфе подзадач ДП. Решение оптимизацион ной задачи – последовательность состояний и решений, определяющих путь в сети (рис. 6), начинающийся в начальном состоянии s1 и оканчивающийся в конечном состоянии sN.

Рассмотрим бесконтурный орграф G = (V, E), состоящий из непустого конеч ного множества вершин V и множества дуг E {(u, v)|u, v V, u = v}. Се тью N = (G, l) называется орграф G с заданной на нем вещественной функцией l : E R. Действительное число l(u, v) называется длиной дуги (u, v) E. Путь из u до v в G это конечная последовательность quv = [u = v1, v2,..., vk = v] вершин G, для которой (vi, vi+1 ) E при i = 1, 2,..., k 1. Длина пути quv равна:

k L(quv ) = l(vi, vi+1 ).

i= Кратчайшим путем из u в v в сети N является путь quv, для которого длина L(quv ) минимальна среди длин всех путей из u до v.

Рассмотрим задачу нахождения кратчайшего пути между вершинами s и t в орграфе (рис. 8). В данно случае орграф вычислительного процесса задан;

он совпадает с данным орграфом G. Обозначим через h(v) длину кратчайшего пути от s до v, где v произвольная вершина сети. Начальные значения 0, если v = s;

h(v) =, в противном случае.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Рекуррентное уравнение Беллмана связывает вычисление различных функций 0 1 2 h(a) h(c) a c 1 2 h(t) s t h(s) 2 b d h(b) h(d) Рис. 8. Кратчайший путь в орграфе.

h(v):

h(v) = min {h(u) + l(u, v)}, (4.1) u:(u,v)E где l(u, v) – расстояние между вершинами u и v. Обозначим через pr(v) вершину, предшествующую вершине v в оптимальном пути: pr(v) = u : h(u ) + l(u, v) = minu (h(u) + l(u, v)). Решим подзадачи из семейства задач {h(v), v V }, начиная с h(s) (рис. 8).


h(b) = h(s) + l(s, b) = 0 + 2 = 2;

pr(b) = s;

h(a) = min (h(s) + l(s, a), h(b) + l(b, a)) = min (0 + 1, 2 + 4) = 1;

pr(a) = s;

h(c) = min (h(a) + l(a, c), h(b) + l(b, c)) = min (1 + 3, 2 + 5) = 4;

pr(c) = a;

h(d) = min (h(b) + l(b, d), h(c) + l(c, d)) = min (2 + 6, 4 + 2) = 6;

pr(d) = c;

h(t) = min (h(c) + l(c, t), h(d) + l(d, t)) = min (4 + 3, 6 + 2) = 7;

pr(t) = c;

Таким образом, длина кратчайшего пути равна 7. Обратная часть процедуры ДП позволяет найти кратчайший путь: t, pr(t) = c, pr(c) = a, pr(a) = s. Кратчайший путь: [s, a, c, t].

Анализируя орграф рис. 8, можно сделать вывод, что задача о кратчайшем пути в орграфе является сериальной полиадической задачей ДП, так как задачи из каждого уровня связаны лишь с задачами из предыдущего уровня (уровни на рисунке показаны пунктиром).

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 32 О.А. ЩЕРБИНА 4.2. Задача о ранце Рассмотрим бинарную задачу о ранце n n max{ cj xj | wj xj W, xj {0, 1}, j = 1,..., n.} j=1 j= Задача о ранце может быть решена с помощью погружения исходной задачи в параметризованное семейство подзадач:

k k h(k, w) = max{ cj xj | wj xj w, xj {0, 1}, j = 1,..., k, } j=1 j= где h(0, 0) = 0, k = 0,..., n;

w = 0,..., W.

Задачи этого семейства {h(k, w)} связаны с помощью рекуррентного соотно шения h(k + 1, w) = max{h(k, w), h(k, w wj ) + ck+1 }, k = 0,..., n 1, (4.2) где h(0, 0) = 0.

Вычисление функции hk (k, w) – это подзадача вычислительного процесса ДП.

Чтобы выявить орграф, лежащий в основе процедуры ДП, представим подзадачи в виде графа, в котором вершинами будут (k, w). Рекуррентное уравнение Беллмана 4.2 имеет графовое представление (рис. 9). Ребро из (k, w) до (k+1, w) соответству h(k, w) h(k+1, w) h(k, w-wk+1) Рис. 9. Подзадачи рекуррентного уравнения задачи о ранце.

ет переменной xk+1, принимающей значение 0, а ребро из (k, w) до (k + 1, w wk+1 ) переменной xk+1, принимающей значение 1. На рис. 10 показан орграф вычис лительного процесса ДП для задачи о ранце с ограничением 2x1 + 3x2 + x3 4.

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

ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ w= w= w= w= w= k=0 k=1 k=2 k= Рис. 10. Орграф подзадач задачи о ранце.

4.3. Задача умножения матриц Предположим, что нам нужно перемножить 4 матрицы A1 A2 A3 A4, размерности которых 50 20, 20 1, 1 10, и 10 100, соответственно. Возникает проблема оптимальной организации процесса вычислений, перемножая за один раз две матрицы. Умножение матриц ассоциативно: A1 (A2 A3 ) = (A1 A2 )A3.

Можно вычислить произведение четырех матриц разными способами, в зависи мости от порядка расстановки скобок. Умножение матрицы m n на матрицу n p требует m · n · p умножений. Используя эту оценку, можно сравнить по трудоемкости различные способы вычисления A1 A2 A3 A4 (табл.1 [7]):

Таблица 1. Трудоемкость вычисления произведения матриц различными способа ми Способ расстановки скобок Расчет трудоемкости вычисления Трудоемкость A1 ((A2 A3 ) A4 ) 20 · 1 · 10 + 20 · 10 · 100 + 50 · 20 · 100 (A1 (A2 A3 )) A4 ) 20 · 1 · 10 + 50 · 20 · 10 + 50 · 10 · 100 (A1 A2 ) (A3 A4 ) 50 · 20 · 1 + 1 · 10 · 100 + 50 · 1 · 100 Для задачи умножения n матриц A1, A2,..., An, где матрица Ai имеет размер ность pi, рассмотрим структуру оптимального решения. Оптимальная расстановка скобок в произведении (A1 · A2 ·... · An ) разбивает произведение между Ak и Ak+ для некоторого целого k, 1 k n: (A1 · A2 ·... · Ak ) · (Ak+1 ·... · An ). Предпосыл кой применения ДП к задаче умножения матриц является следующее наблюдение:

подцепь (A1 · A2 ·... · Ak ) внутри оптимальной расстановки скобок в произведении (A1 · A2 ·... · An ) должна быть оптимальной расстановка скобок в A1 · A2 ·... · Ak (подобное свойство справедливо и для второй подцепи).

Введем m[i, j] – минимальное число скалярных умножений, требуемых для вы ISSN 0203–3755 Динамические системы, вып. 22 (2007) 34 О.А. ЩЕРБИНА числения матричного произведения (Ai ·...·Aj ). Выведем рекуррентное уравнение Беллмана:

0, если i = j;

m[i, j] = minikj {m[i, k] + m[k + 1, j] + pi1 pj pk }, если i j Анализ орграфа на рис. 11 позволяет сделать вывод, что задача умножения мат A1A2A3A A1A2A3 A2A3A A1A2 A2A3 A3A Рис. 11. Орграф вычислительного процесса для задачи о произведении матриц.

риц является полиадической несериальной задачей ДП.

4.4. Несериальная задача оптимизации Примером несериальной задачи оптимизации может служить следующая за дача:

max{g1 (x1, x2, x4 ) + g2 (x3, x4 ) + g3 (x2, x5 )}, X где X = {x1,..., x5 }.

Граф взаимосвязей задачи показан на рис. 12а.

h x4 x h1(x4) h4(x4) x3 x2 x3 x x5 x x1 x h3(x2, x4) h2(x2) ISSN 0203–3755 Динамические системы, вып. 22 (2007) МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Рис. 12. Граф взаимосвязей (a) и орграф вычислительного процесса (б) для несе риальной задачи оптимизации.

Для порядка элиминации = {x3, x5, x1, x2, x4 } вычисления выполняются следующим образом (рис. 12а):

h1 (x4 ) = max[g2 (x3, x4 )];

x h2 (x2 ) = max[g3 (x2, x5 )];

x h3 (x2, x4 ) = max[g1 (x1, x2, x4 )];

x h4 (x4 ) = max[h2 (x2 ) + h3 (x2, x4 )];

x h5 = max[h4 (x4 ) + h1 (x4 )].

x Орграф вычислительного процесса является ориентированным стягивающим де ревом графа взаимосвязей (рис. 12б).Согласно приведенной выше классификации, данная задача является несериальной и полиадической.

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

Список цитируемых источников 1. Щербина О.А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы. 2005. Вып.19.

С.179 190.

2. Щербина О.А. Элиминационные алгоритмы декомпозиции задач дискретной оптими зации // Таврический вестник информатики и математики. 2006. №2. С. 28–41.

3. Aris R. The optimal design of chemical reactors. – New York: Academic Press, 1961.

4. Aris R., Nemhauser G.L., Wilde D. Optimization of multistage cyclic and branching system serial procedures // Journal of American Institute of Chemical Engineering. – 1964. – V. 10, N6. – P. 913–919.

5. Bellman R., Dreyfus S. Applied Dynamic Programming. - Princeton: Princeton University Press, 1962.

6. Bertele U., Brioschi F. Nonserial Dynamic Programming. New York: Academic Press, 1972. 235 p.

7. Dasgupta S., Papadimitriou C.H., Vazirani U.V. Algorithms. McGraw Hill, 2006.

336 p.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 36 О.А. ЩЕРБИНА 8. Dreyfus S.E. An appraisal of some shortest-path algorithms // Operations Research. – 1969. – 17. – P. 395– 9. Esogbue A.O., Marks B. Non-serial dynamic programming – A survey // Operational Research Quarterly. – l974. – 25. – P.253–265.

10. Ibaraki T. Solvable classes of discrete dynamic programming // J. Math. Anal. Appl. 1973. - 43. - P. 642-693.

11. Li G.-J., Wah B.W. Parallel processing of serial dynamic programming problems // Proceedings of COMPSAC 85. - 1985. P. 81–89.

12. Lawler E.L. Combinatorial Optimization Networks and Matroids. – New York: Holt, Rinehart, and Winston, 1976.

13. Mitten L.G., Nemhauser G.L. Multistage optimization // Chemical Engineering Progress.

– 1963. – 54. – P. 52–60.

14. Wah B.W., Li G.-J. Systolic processing for dynamic programming problems // Circuits Systems Signal Process. – 1988. – 7. – P.119–149.

15. Wilde D. Strategies for optimization macrosystems. Chemical Engineering Progress. – 1965. – V.61, N3. – P. 86–93.

Получена 29.03. ISSN 0203–3755 Динамические системы, вып. 22 (2007) Динамические системы, вып. 22 (2007), 37– ДИНАМИЧЕСКИЕ СИСТЕМЫ Межведомственный научный сборник УДК 517.977, 531. Оптимальное управление в задаче о колебаниях упругой системы А.Л. Зуев Институт прикладной математики и механики НАН Украины, Донецк 83114. E-mail: al zv@mail.ru Аннотация. Рассмотрена математическая модель вращающейся механической системы с упру гой балкой, которая была введена в предыдущей работе автора. Решена задача минимизации квадрата нормы управления при фиксированных начальном и конечном положениях систе мы. При этом использована каноническая форма Бруновского и сведение задачи оптимального управления к задаче Лагранжа.

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

Следует подчеркнуть, что метод Беллмана позволяет эффективно свести задачу оптимального управления для линейной системы с квадратичным функционалом качества к решению матричного уравнения Риккати для случая, если граничное условие в конечный момент времени не задано (см. [8, Chap. 8.2]). В предлагаемой статье использован иной подход к решению задачи оптимального управления с граничными условиями на обоих концах отрезка времени. Такой подход опирает ся на сведение задачи оптимального управления к вариационной задаче Лагран жа относительно вспомогательной функции y(t). В работе использован результат предыдущей статьи автора [1] о приведении управляемой системы к канонической форме Бруновского.


Работа поддержана за счет бюджетных средств МОН Украины, предоставленных как грант Президента Украины №GP/F13/0173.

c А.Л. ЗУЕВ 38 А.Л. ЗУЕВ 2. Постановка задачи Рассмотрим систему дифференциальных уравнений:

0 = 0, 0 = v, (2.1) j = j j, j = j j + bj v, (j = 1, N ), где x = (0, 0, 1, 1,..., N, N )T R2N +2 – фазовый вектор, v R – управление.

Система (2.1) введена в работе [1] для описания плоского вращения твердого тела с упругими балками в конечномерной постановке под действием управляющего момента.2 Здесь число N 1 характеризует количество обобщенных (модальных) координат, используемых для описания колебаний балки;

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

Задача 1. Для заданных T T t0 t1, x0 = 0, 0,..., N, N 00 0 R2N +2, x1 = 0, 0,..., N, N 11 1 R2N + требуется найти функцию управления v = v(t), t [t0, t1 ], для которой систе ма (2.1) имеет решение x(t), удовлетворяющее граничным условиям x(t0 ) = x0, x(t1 ) = x1.

В качестве допустимых управлений v(t) в статье [1] рассматривались непре рывные функции. Возможно также использовать более широкие классы допусти мых управлений L [t0, t1 ], L2 [t0, t1 ] и определять решения системы (2.1) с помо щью формулы Коши (формулы вариации произвольных постоянных) (см. напр. [2, гл. 2], [6, Chap. 14]). Известно, что задача 1 в общем случае имеет бесконечно много решений, и реализация некоторых решений может приводить к слишком большим значениям нормы управления. Поэтому рассмотрим задачу оптимального управ ления следующего вида.

Задача 2. Для заданных t0 t1 и x0, x1 R2N +2 требуется найти функцию управления v L2 [t0, t1 ], которая минимизирует значения функционала t |v(t)|2 dt J(v) = (2.2) t в классе всех управлений v L2 [t0, t1 ], решающих задачу 1.

Поскольку система (2.1) автономна, то без ограничения общности в дальней шем будем считать, что t0 = 0, t1 = 0. Сформулируем основной результат о разрешимости задачи 2.

Процедура вывода нелинейных бесконечномерных уравнений движения системы с упругими балками приведена в статье [9] ISSN 0203–3755 Динамические системы, вып. 22 (2007) ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ Теорема 1. Пусть bj = 0, j = 0, и все числа j различны для j = 1, N. Тогда для 0 1 2N + любых x, x R, 0 существует единственное оптимальное управление v (t), t [0, ], решающее задачу 2. Указанное оптимальное управление является гладким и задается формулой N v (t) = k0 + k1 t + (Uj cos(j t) + Vj sin(j t)), t [0, ] j= где коэффициенты k0, k1, Uj, Vj удовлетворяют системе линейных алгебраиче ских уравнений:

N 2 3 1 cos(j ) j sin(j ) 1 0 k0 + k1 + Uj + Vj = 0 0 0 ;

2 2 6 j j j= N 2 sin(j ) 1 cos(j ) 1 k0 + k1 + Uj + Vj = 0 0 ;

2 j j j= sin2 (j ) cos(j ) 1 j cos(j ) sin(j ) sin(2j ) 2j k0 + k1 Uj + Vj + j j 2j 4j 1 cos(i + j ) cos(j i ) 2j + + +2 Ui + 2 i + j j i i j i=j 1 1 j cos(j ) j sin(j ) j 1 sin(i + j ) sin(i j ) + + Vi = ;

2 i + j j i bj i=j sin2 (j ) sin(j ) j sin(j ) + cos(j ) 1 2j + sin(2j ) k0 + k1 + Uj + Vj + j j 4j 2j 1 cos(i j ) cos(i + j ) 2i + +2 Vi + 2 j i i + j i j i=j 1 1 j sin(j ) + j cos(j ) j 1 sin(i + j ) sin(i j ) + + Ui =, j = 1, N.

2 i + j i j bj i=j (2.3) Доказательство этой теоремы будет проведено в разделе 4.

3. Вспомогательные построения Если выполнены условия теоремы 1, то каждое непрерывное управление v(t), решающее задачу 1, можно представить в таком виде [1, теорема 2]:

N d2N +2 d2p v(t) = + p y(t), t [t0, t1 ], (3.1) dt2N +2 dt2p p= ISSN 0203–3755 Динамические системы, вып. 22 (2007) 40 А.Л. ЗУЕВ где N i 2N = c0 j, (3.2) 2 j i j=1 1iN i=j N 2N (j1 j2 · · · jN p )2, (3.3) p = k l k k=1 1lN 1 j1 j2... jN p N l=k j1, j2,..., jN p = k а функция y C 2N +2 [t0, t1 ] удовлетворяет граничным условиям:

N N i i i y(ti ) = cj j, y(ti ) = c0 0 + cj j j, j=0 j= d2 d 2i 3i y y c1 1 1 c1 1 dt2 dt d4 d 2i 3i c2 2 2 c2 2 y y dt4 dt = W, = W, i = 0, 1.

..

..

..

..

..

..

2i 3i d2N d2N + cN N N cN N N y y dt2N dt2N + t=ti t=ti (3.4) Здесь c0 – произвольная ненулевая константа, 1 1... 2 2 1 2... N c0 i 4 4 1 2... N cj =, W =.

2 2 j bj i j...

...

...

...

1iN i=j 2 N 1 2 N (N )N (1 ) (2 )...

(3.5) В случае p = N сумма в формуле (3.3) полагается равной единице;

все произведе ния с пустым множеством индексов также считаются равными единице. Приведем более удобную форму записи управления (3.1).

Лемма 1. Формула (3.1) эквивалентна следующей:

d2 d2 d2 d2 y(t) 1 2 2 v(t) = + 1 + 2... + N, t [t0, t1 ].

22 2 2 2 2 dt c0 1 2... N dt dt dt (3.6) Доказательство. Раскрывая скобки в формуле (3.6) и приравнивая коэффициен ты при соответствующих производных от y(t) в (3.1) и (3.6), получим:

22 2 22 = c0 1 2... N, p = j1 j2... jN p+1. (3.7) 1j1 j2...jN p+1 N ISSN 0203–3755 Динамические системы, вып. 22 (2007) ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ Для доказательства леммы достаточно установить равенства (3.7), где и p опре деляются выражениями (3.2) и (3.3). С этой целью вычислим определитель мат рицы, образованной строками W из (3.5):

1 1... 2 2 1 2... N N (1 ) (2 ) (N )... 2(N m) (1)k+m k = k, (3.8)...

...

...

... k= (1 )N 2 (2 )N 2...

2 (N )N 2 N m 2 N m 2 N m (1 ) (2 )... (N ) где 1 m N, k – минор, полученный вычеркиванием последней строки и k-го столбца матрицы W. Формула (3.8) получена разложением определителя по эле ментам нижней строки. Из известной формулы для определителя Вандермонда [4, с. 32] следует, что (i l2 ), k = (i l2 ).

|W | = il il i, l = k Подстановка этих выражений в формулу (3.8) при m = 1 дает такое тождество:

N 2(N 1) l2 ) (1)k+1 k (i l2 ).

|W | = (i = (3.9) il k=1 il i, l = k Заметим также, что для произвольного фиксированного индекса j, 1 j N, выполняется равенство:

(i l2 ) = 2 2 2 2 (i l2 ).

|W | = (i j ) (j i ) (3.10) ij ij il il i, l = j Учитывая, что строки матрицы в (3.8) линейно зависимы при 1 m N, получим N 2(N m) (1)k k (i l2 ) = 0, (1 m N ). (3.11) k=1 il i, l = k Перепишем формулу (3.2) для следующим образом:

2(N 1) 2(N 1) N N (1)j1 j j 2 2 2 = c0 1... N = c0 1... N.

2 (j i ) 2 2 2 ij (i j ) ij (j i ) i=j j=1 j= ISSN 0203–3755 Динамические системы, вып. 22 (2007) 42 А.Л. ЗУЕВ После приведения дроби под знаком суммы к общему знаменателю |W | и приме нения формулы (3.10), получим N 2 c0 1... N 2(N 1) (1)j1 j (i l2 ).

= |W | j=1 il i, l = j 22 Отсюда с учетом разложения (3.9) следует, что = c0 1 2... N. Итак, остается доказать равенство (3.7) для p. Приводя выражение (3.3) к общему знаменателю |W | с помощью представления (3.10), будем иметь N (1)k1 k 2N (i l2 ) (j1 j2 · · · jN p )2.

p = |W | k=1 il 1 j1... jN p N i, l = k j1,..., jN p = k (3.12) Рассуждая по индукции, получим 2(N 1) 2N (j1 · · · jN p )2 = k (j1 · · · jN p+1 ) k j1...jN p+ j1... jN p j1,..., jN p = k 2(N 1) (j1 · · · jN p+1 )2 = k j1... jN p+ j1,..., jN p+1 = k p 2(N m) (1)m1 k (j1 · · · jN p+m )2.

= (3.13) m=1 j1...jN p+m Подставим (3.13) в (3.12) и воспользуемся свойством (3.11) для значений индекса m 1. В результате останутся только слагаемые, соответствующие m = 1:

N 1 2(N 1) (1)k1 k (i l2 ) (j1 · · · jN p+1 )2 = p = |W | j1...jN p+ k=1 il i, l = k (j1 · · · jN p+1 )2.

= j1...jN p+ Здесь использовано представление (3.9). Итак, равенства (3.7) доказаны.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ 4. Доказательство теоремы Рассмотрим сначала задачу 2 в классе непрерывных функций управления v(t) на отрезке t [0, ]. Из представления (3.1) и леммы 1 следует, что задача эквивалентна задаче Лагранжа о минимизации функционала J(y):

F y, y, y,..., y (2N +2) dt min, J(y) = (4.1) d2 d2 d2 d2 y(t) (2N +2) 2 2 F y, y, y,..., y = + 1 + 2... + N, dt2 dt2 dt2 dt в классе функций y C 2N +2 [0, ], удовлетворяющих граничным условиям (3.4).

Пусть y = y (t) – решение задачи (4.1), (3.4), тогда соответствующее ему по форму ле (3.6) управление v (t) будет оптимальным для задачи 2 (в классе непрерывных управлений). Если y C 4N +4, то y (t) удовлетворяет уравнению Эйлера-Пуассона для функционала J [5, с. 310]:

2N + dk F F (1)k + = 0, t [0, ], (4.2) dtk y (k) y k=1 y=(t) y а также граничным условиям (3.4). Введем линейный дифференциальный опера тор D : C 2N [0, ] C[0, ], d2 d2 d 2 2 y(t) Dy(t) = + 1 + 2... + N y(t).

2 2 dt dt dt Тогда, как нетрудно видеть, уравнение (4.2) можно представить в следующем виде:

d4 D y (t) = 0, t [0, ]. (4.3) dt Поскольку решение y (t) уравнения (4.3) связано с оптимальным управлением v (t) d соотношением (3.6), то v (t) = c0 21 2 dt2 D(t) удовлетворяет дифференциальному y 1...N уравнению:

d D(t) = 0, t [0, ].

v (4.4) dt Запишем характеристическое уравнение для (4.4):

2 (2 + 1 )(2 + 2 )... (2 + N ) = 0.

2 2 Отсюда следует, что всякое решение дифференциального уравнения (4.4) предста вимо в виде N v (t) = k0 + k1 t + (Uj cos(j t) + Vj sin(j t)), t [0, ]. (4.5) j= ISSN 0203–3755 Динамические системы, вып. 22 (2007) 44 А.Л. ЗУЕВ Согласно теореме 2 из [1], граничные условия (3.4) на y = y (t) означают, что соот ветствующее решение x(t) системы (2.1) с управлением v = v (t) обладает свойства 0 ми x(0) = x и x( ) = x. Вместо интегрирования уравнения (4.3) c громоздкими граничными условиями (3.4), определим константы k0, k1, Uj, Vj с помошью под становки управления (4.5) непосредственно в граничную задачу (2.1), x(0) = x0, x( ) = x1. Применение формулы Коши для линейной неоднородной системы (2.1) с v = v (t) и начальными условиями x(0) = x0 дает:

t j j (t) tAj e(ts)Aj =e + ds, j = 0, N, (b0 = 1), (4.6) j (t) j bj v (s) где 01 1t, etA0 = A0 =, 00 0 j cos j t sin j t, etAj = Aj =, j = 1, N.

j 0 sin j t cos j t Интегрируя первые два уравнения системы (2.1) с управлением v = v (t), получим t t 0 0 (t) = 0 + v (s) ds, 0 (t) = 0 + 0 (s) ds.

0 Затем умножим обе части формулы (4.6) на etAj (1 j N ) и запишем гра ничное условие x( ) = x1 по компонентам 0, 0,..., N, N. В результате получим систему (2.3) из 2N + 2 линейных неоднородных алгебраических уравнений отно сительно 2N + 2 неизвестных k0, k1, Uj, Vj. Остается показать, что эта система имеет единственное решение при любых 0 и x0, x1 R2N +2, а также, что соответствующее управление (4.5) является оптимальным для задачи 2.

Для всякого ненулевого управления v L2 [0, ] функционал (2.2), очевидно, удовлетворяет неравенству J(v) 0. Поэтому задача 2 имеет решение v L2 [0, ] при любых 0 и x0, x1 R2N +2 на основании [6, Proposition 14.1], [7]. Кро ме того, любое оптимальное управление v (t) является гладким, поскольку макси мальное значение гамильтониана в принципе максимума Понтрягина достигается для управления в виде линейной функции от сопряженных переменных (см. [6, Chap. 14.3]). Следовательно, ввиду представления (3.1), (3.4), решение y = y (t) задачи Лагранжа (4.1) существует и является гладкой функцией, и формула (4.5) определяет оптимальное управление при некоторых значениях коэффициентов, определяемых условиями (2.3). Если предположить, что решение системы (2.3) неединственно при некоторых 0 и x0, x1 R2N +2, то возможно выбрать другие векторы граничных условий x0, x1 в правой части (2.3) таким образом, что система окажется несовместной. Сделанное предположение противоречит существованию оптимального управления для системы (2.1) с граничными условиями x(0) = x0, x( ) = x.

ISSN 0203–3755 Динамические системы, вып. 22 (2007) ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ 5. Заключение Доказанная теорема конструктивно определяет управление с наименьшей “энергией” (в смысле функционала (2.2)), переводящее систему из любого началь ного состояния в наперед заданное при произвольном количестве обобщенных ко ординат N. Ключевой момент в построении оптимального управления связан с ис пользованием соотношения (3.1), которое параметризует управления через вспо могательную функцию y(t) (выход Бруновского). В данной работе рассмотрена линейная система, и представляет дальнейший интерес изучение свойств решений задач оптимального управления для классов управляемых систем при наличии нелинейного аналога соотношения (3.1).

Список цитируемых источников 1. Зуев А.Л. Управление упругими колебаниями с использованием канонической фор мы // Динамические системы. 2006. Вып. 20. С. 27–34.

2. Ли Э.Б., Маркус Л. Основы теории оптимального управления М.: Наука, 1972.

576 с.

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

4. Проскуряков И.В. Сборник задач по линейной алгебре. 3-е изд. М.: Наука, 1967.

382 с.

5. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М.:

Наука, 1969. 424 с.

6. Agrachev A.A., Sachkov Yu.L. Lectures on Geometric Control Theory. Trieste: SISSA, 2001. 208 p.

7. Agrachev A.A., Sachkov Yu.L. Control Theory from the Geometric Viewpoint. Berlin:

Springer, 2004. 412 p.

8. Sontag E.D. Mathematical Control Theory, Deterministic Finite Dimensional Systems, Second Edition. New York: Springer-Verlag, 1998. 531 p.

9. Zuyev A. Partial asymptotic stabilization of nonlinear distributed parameter systems // Automatica. 2005. Vol. 41, № 1. P. 1–10.

Получена 30.03. ISSN 0203–3755 Динамические системы, вып. 22 (2007) Динамические системы, вып. 22 (2007), 46– ДИНАМИЧЕСКИЕ СИСТЕМЫ Межведомственный научный сборник УДК 517.9: 534. Динамический хаос в системе "бак с жидкостью – электродвигатель" А.Ю. Швец НТУУ "Киевский политехнический институт", Киев 03057. E-mail: alex.shvets@bigmir.net Аннотация. Рассмотрены колебания свободной поверхности жидкости в баке, возбуждаемые электродвигателем ограниченной мощности. В случае параметрического резонанса системы до казано существование в ней нескольких типов хаотических аттракторов. Построены и деталь но проанализированы фазовые портреты, сечения и отображения Пуанкаре, а также Фурье– спектры аттракторов системы. Описаны сценарии перехода от регулярных движений к хаотиче ским.

1. Введение Исследованию колебаний свободной поверхности жидкости в жестких баках посвящено значительное количество работ, как теоретических, так и эксперимен тальных, среди которых можно отметить работы: [1, 2, 3, 4, 5]. В некоторых из вышеприведенных работ имеется детальная библиография по колебаниям баков с жидкостью. Такое внимание к этим задачам обусловлено, помимо исследова тельского интереса, большим приложением получаемых результатов во многих областях современной техники. Громадное количество современных машин и ме ханизмов в качестве неотъемлемого элемента конструкций содержит различные баки с жидкостями.

Подавляющее большинство работ по изучению колебаний бака с жидкостью посвящено исследованию регулярной динамики поверхностных волн жидкости и рассматривается в постановке, так называемого, идеального возбуждения. При такой постановке задачи предполагается, что источник возбуждения колебаний имеет неограниченную мощность. Поэтому обратным влиянием колебательной си стемы, в данном случае бака с жидкостью, на источник возбуждения колебаний пренебрегают. Однако, на практике, чаще всего встречается ситуация, при ко торой мощность потребляемая колебательной нагрузкой сравнима, по величине, с мощностью возбудителя колебаний. В таких случаях применение "идеальных" математических моделей может привести к грубым ошибкам в описании динами ки, как колебательной нагрузки, так и источника возбуждения колебаний. Так c А.Ю. ШВЕЦ ДИНАМИЧЕСКИЙ ХАОС может быть полностью утеряна информация о реально существующем в систе ме детерминированном хаосе [6, 7]. Заметим, что одним из путей возникновения детерминированного хаоса как раз и является нелинейное взаимодействие между колебательной системой (баком с жидкостью) и устройством возбуждения коле баний (электродвигателем).

Настоящая работа посвящена исследованию взаимодействия бака с жидкостью с возбуждающим его колебания электродвигателем ограниченной мощности. Осо бое внимание будет уделено поиску динамического хаоса в такой системе.

2. Математическая модель системы "бак с жидкостью – электродвигатель" Рассмотрим случай вертикального возбуждения электродвигателем ограничен ной мощности платформы цилиндрического бака, частично заполненного жидко стью. Схематически такая механическая система представлена на рис. 1а. Вал электродвигателя через кривошипно-шатунный механизм соединен с платформой, на которой закреплен жесткий цилиндрический бак радиуса R, частично запол ненный жидкостью. Когда кривошип a поворачивается на угол, платформа по лучает перемещение вида v(t) = a cos (t). Для описания колебаний свободной по верхности жидкости введем цилиндрическую систему координат Oxr с началом на оси бака, на невозмущенной поверхности жидкости. Тогда уравнение рельефа свободной поверхности жидкости запишем в виде x = (r,, t). Предположим, что жидкость невязкая и несжимаемая с плотностью и заполняет цилиндрический бак сечения S до глубины x = d.

Отыскивать функцию рельефа поверхности жидкости будем в виде разложе ния по собственным модам [1]:

c s (r,, t) = [qij (t)kij (r) cos i + qij (t)kij (r) sin i], (2.1) i,j c s где qij, qij – неизвестные амплитуды нормальных мод;

kij (r) cos i и kij (r) sin i – собственные моды в линейной аппроксимации задачи о колебаниях идеальной жидкости в цилиндрической оболочке. Тогда, как показано в работах [8, 9], для (t) можно получить следующее уравнение Лагранжа:

I = 2m0 a2 2 sin cos m0 a2 sin2 + aS(2 sin (2.2) c,s c,s c,s c,s cos ) qij qij 2aS cos qij qij + () H().

i,j i,j Здесь m0 – масса бака с жидкостью;

() – движущий момент электродвигателя;

H() – момент внутренних сил сопротивления вращению вала электродвигателя [1, 8, 9].

ISSN 0203–3755 Динамические системы, вып. 22 (2007) 48 А.Ю. ШВЕЦ 0. 0. 0. 0. 0. 0. -2 -1.5 -1 -0.5 N а б Рис. 1. Схема системы (а);

зависимость максимального ляпуновского показателя 1 от параметра N1 (б).

Предположим, что реализуются условия основного параметрического резонан са, когда скорость вращения вала (t) в установившихся режимах двигателя близ ка к 21, где 1 – собственная частота основного тона колебаний свободной поверх c s ности жидкости, которая соответствует модам q11 (t)k11 (r) cos и q11 (t)k11 (r) sin.

Обозначим через g ускорение силы тяжести и введем в рассмотрение малый по ложительный параметр a = 1. (2.3) g Также предположим, что 21 = 2 1. (2.4) Колебания свободной поверхности жидкости аппроксимируем колебаниями по ос новным и вторичным модам, амплитуды которых определяем в виде [8, 9, 10]:

c q11 (t) = p1 ( ) cos + q1 ( ) sin ;

2 s q11 (t) = p2 ( ) cos + q2 ( ) sin ;

2 (2.5) q01 (t) = A01 ( ) cos + B01 ( ) sin + C01 ( ) ;

q21 (t) = 2 Ac,s ( ) cos + B21 ( ) sin + C21 ( ).

c,s c,s c,s ISSN 0203–3755 Динамические системы, вып. 22 (2007) ДИНАМИЧЕСКИЙ ХАОС 12 R 1. Здесь – медленное время, =, = th( d). Исполь 4 1.8412 R зуя метод Майлса [3, 8, 9, 10], можно выразить безразмерные амплитуды Ac,s ( ), Bij ( ), Cij ( ) вторичных мод через амплитуды p1 ( ), q1 ( ), p2 ( ), q2 ( ). Да c,s c,s ij лее, как показано в [8, 9], после применения процедуры усреднения по, явно входя щему, быстрому времени (t) для определения амплитуд основных мод получим следующую систему уравнений:

dp1 A = p1 + (p2 + q1 + p2 + q2 ) 2 q1 + B(p1 q2 p2 q1 )p2 + 2q1 ;



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

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