close

Вход

Забыли?

вход по аккаунту

?

1243.Современные проблемы математики и информатики Вып 12

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Современные
проблемы
математики
и информатики
Выпуск 12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П. Г. Демидова
СОВРЕМЕННЫЕ ПРОБЛЕМЫ
МАТЕМАТИКИ И ИНФОРМАТИКИ
Сборник научных трудов
молодых ученых, аспирантов и студентов
ВЫПУСК 12
Ярославль 2011
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 517.9 + 512.54 + 519.6
ББК В1+Ч23
С 56
Рекомендовано
редакционно-издательским советом ЯрГУ
в качестве научного издания. План 2011 года
С 56
Современные проблемы математики и информатики:
сборник научных трудов молодых ученых, аспирантов и студентов / Яросл. гос. ун-т им. П. Г. Демидова. — Ярославль, 2011. —
Вып. 12. — 100 с.
В сборнике представлены работы молодых ученых, аспирантов и студентов.
В статьях рассматриваются различные проблемы математического анализа, динамических систем и информационных технологий.
Сборник подготовлен с использованием издательской системы
LATEX.
Редакционная коллегия:
канд. физ.-мат. наук П. Н. Нестеров (отв. редактор)
д-р физ.-мат. наук С. Д. Глызин
c
Ярославский
государственный
университет
им. П. Г. Демидова, 2011
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
Математический анализ . . . . . . . . . . . . . . . . . . . . .
5
Демьянков Н. А. Численное исследование вариационной
задачи с фазовыми ограничениями с помощью метода
локальных вариаций . . . . . . . . . . . . . . . . . . . . .
5
Динамические системы . . . . . . . . . . . . . . . . . . . . .
12
Агафончиков Е. Н. Построение асимптотики решений
системы двух дискретных осцилляторов с медленно
убывающей связью . . . . . . . . . . . . . . . . . . . . . .
Антонычев А. А., Короткин А. А. Игровая автоматная
модель локального управления в системе распределения
общего нерасходуемого ресурса . . . . . . . . . . . . . .
Ануфриенко С. Е., Прописнова В. А. Трехкратная волна
в кольце из модифицированных импульсных нейронов .
Быкова Н. Д. Критический случай наибольшего вырождения
в задаче с двумя запаздываниями . . . . . . . . . . . . .
Кащенко А. А. Исследование устойчивости решений вида
бегущих волн в уравнении Гинзбурга-Ландау
с малой диффузией . . . . . . . . . . . . . . . . . . . . .
Коновалов И. И. О существовании интегрируемых
с квадратом решений одномерного уравнения
Шредингера с параметром . . . . . . . . . . . . . . . . .
Информационные технологии . . . . . . . . . . . . . . . . .
Бойцов Е. А., Васильчиков В. В. Кроссплатформенная
библиотека параллельного выполнения rpC-программ . .
Колесов А. Ю. О классификации текстов в условиях
неполноты обучающего множества . . . . . . . . . . . . .
3
12
27
36
42
49
56
71
71
82
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4
СОДЕРЖАНИЕ
Кулаков С. С., Краснов М. В. Программный комплекс
для локализации области лица на фронтальном
фотоизображении . . . . . . . . . . . . . . . . . . . . . .
93
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
МАТЕМАТИЧЕСКИЙ АНАЛИЗ
УДК 519.6
Н. А. Демьянков
Численное исследование вариационной задачи
с фазовыми ограничениями
с помощью метода локальных вариаций
Приводится метод локальных вариаций для численного решения
вариационной задачи с фазовыми ограничениями. Производится численное исследование конкретной вариационной задачи при различных
краевых условиях.
1. Введение. Теория вариационных задач достаточно хорошо развита и была неоднократно рассмотрена как для конечномерного, так
и для бесконечномерного случая. Различные теоретические материалы по данной тематике можно найти в [1], [2] и [4]. Нам же было интересно провести численное исследование вариационной задачи
с фазовыми ограничениями при различных вариантах краевых условий, воспользоваться каким-нибудь численным методом для решения
определенной задачи. Для решения поставленной цели использовался метод локальных вариаций [3], который был реализован автором
программно в Maple 13. С помощью данного метода было выполнено
небольшое численное исследование одной вариационной задачи, которое приводится в третьей части данной статьи.
2. Метод локальных вариаций. Пусть требуется найти функцию
x(t), заданную на интервале [a, b] вещественной оси, удовлетворяющую ограничениям
x− (t) ≤ x(t) ≤ x+ (t), a ≤ t ≤ b
(1)
и доставляющую минимум функциналу
b
.
f (t, x, x) dt.
a
(2)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Н. А. Демьянков
6
.
Здесь x− , x+, f — заданные функции своих аргументов, через x обозначена производная dx
dt .
Разобъем интервал [a, b] на N равных частей точками:
ti = a + iΔt, Δt =
b−a
, i = 0, 1, . . . , N.
N
(3)
Введем обозначение
Δt x + x x − x Ii(x , x ) = f ti +
,
,
Δt
2
2
Δt
где x = x(ti), x = x(ti+1).
Обозначим xi = x(ti) при i = 0, 1, . . . , N . Функции x(t) будем аппроксимировать ломаными, соединяющими точки (ti , xi) в плоскости
(t, x), а функционал (3) приближенно заменим суммой
I=
N
−1
Ii(xi, xi+1).
(4)
i=0
Вместо решения исходной задачи о нахождении функции x(t), доставляющей минимум функционалу (2) при условиях (1), рассмотрим
задачу об определении таких чисел xi при i = 0, 1, . . . , N , которые
удовлетворяют ограничениям
x− (ti) ≤ xi ≤ x+ (ti), i = 0, 1, . . . , N
(5)
и доставляют минимум сумме (4).
Ограничения (5) вытекают из (2). Таким образом, вместо решения
непрерывной вариационной задачи (2), (1) будем решать дискретную
задачу (4), (5), в которой функция x(t) заменяется ломаной с вершинами в точках (ti, xi).
Решение задачи (4), (5) будет строиться путем последовательных
приближений. Номер приближения обозначим верхним индексом. В
качестве нулевого приближения x0i , i = 0, 1, . . . , N возьмем любой набор чисел, удовлетворяющий ограничениям (5).
Опишем рекуррентный процесс построения последовательных приближений. Пусть h — некоторое достаточно малое положительное число, которое будем называть шагом варьирования. Пусть n-е приближение уже построено, т. е. известны числа xni при i = 0, 1, . . . , N при
каком-то целом n ≥ 0. Пусть уже найдены первые i чисел n + 1n+1
n+1
го приближения, т. е. величины xn+1
0 , x1 , . . . , xi−1 при некотором
i, 1 ≤ i ≤ N . Предполагаем, что все величины xnj при j = 0, 1, . . . , N
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
7
и xn+1
при j = 0, 1, . . . , i − 1 удовлетворяют ограничениям (5). Для наj
поступим следующим образом. Рассмотрим в качестве
хождения xn+1
i
возможных значений xn+1
три величины:
i
xni , xni + h, xni − h.
(6)
Величина xni , по предположению, удовлетворяет ограничениям (5).
Проверим для остальных двух величин выполнение ограничений (5) и
подсчитаем суммы:
n n n
Φi = Ii−1 xn+1
,
x
i +Ii xi , xi+1 ,
i−1
n
n+1 n
n
=
I
,
x
+
h
+I
+
h,
x
(7)
x
x
Φ+
i−1
i
i
i
i+1 ,
i
i−1
n+1 n
n
n
Φ−
i = Ii−1 xi−1 , xi − h +Ii xi − h, xi+1 .
При i = 0 и i = N суммы (7) состоят лишь из одного слагаемого
(первого при i = N и второго при i = 0). Если xni + h не удовлетворяет
(5), то сумму Φ+
i подсчитывать не нужно, и принимаем ее равной +∞.
Аналогично, если xni − h не удовлетворяет (5), то сумму Φ−
i мы не
вычисляем и принимаем равной −∞.
равной тому из трех чисел
Теперь полагаем искомую величину xn+1
i
(6), которое, во-первых, удовлетворяет ограничениям (5) и, во-вторых,
которому отвечает наименьшая из сумм (7). Таким образом,
⎧
−
n
⎪
при Φi ≤ Φ+
⎨xi
i , Φi ≤ Φi ,
= xni + h при Φ+
xn+1
< Φi , Φ+
≤ Φ−
i
i
i
i ,
⎪
⎩xn − h при Φ− < Φ , Φ− < Φ+.
i
i
i
i
i
После определения xn+1
переходим к нахождению xn+1
i
i+1 , которое
осуществляется аналогично. Такой процесс продолжается до тех пор,
пока не будет найдено xn+1
N . После этого новое (n + 1)-е приближение
будет полностью построено. Итерации по описанной схеме продолжаем
до выполнения равенств
xn+1
= xni(i = 0, 1, . . . , N ), I n+1 = I n ,
i
где I — функционал из (4), верхний индекс соответствует номеру итерации.
После нахождения решения с заданными h и Δt можно уменьшить
шаг варьирования h и повторить итерационный процесс. Затем можно увеличивать число точек N разбиения отрезка. Процесс решения
заканчивается при полной сходимости итераций для некоторых достаточно малых Δt и h.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Н. А. Демьянков
8
3. Численное исследование вариационной задачи с фазовыми
ограничениями. Для рассмотрения была взята следующая вариационная задача
π
.2
x + x2 − 10x sin(t) dt → min
(8)
−π
с фазовым ограничением:
|x| 1.
(9)
Рассмотрим данную задачу с краевым условием
x(−π) = x(π) = 0,
(10)
x(−π) = x(π),
(11)
и вообще без краевых условий.
Решением задачи (8) без фазового ограничения (9) является
x(t) = C1 et + C2 e−t + 2, 5 sin(t).
При краевых условиях (10) и (11) оно обращается в
x(t) = 2, 5 sin(t).
Однако, поскольку в нашей задаче присутствует фазовое ограничение (9), данное решение нам уже не подходит. Для решения задачи
с фазовым ограничением воспользуемся численным методом локальных вариаций, который был описан выше. Для этого была написана
программа в Maple 13, которая реализовывала данный численный метод. Ниже приводятся графики решения задачи (8), (9) при различных
краевых условиях.
При условии (10) график решения задачи (8) будет следующим:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
9
N = 299, h = 0.001
При краевом условии (11) график решения совпадает с приведенным выше.
Искомая функция x(t) при краевых условиях (10) и (11) имеет вид:
⎧
⎪
при t∈[−π − arcsin( 25 ), − arcsin( 25 )],
⎨−1
x(t)= 1
при t∈[arcsin( 25 ), π − arcsin( 25 )],
⎪
⎩2, 5 sin(t) при t∈[−π−
/
arcsin( 25 ), − arcsin( 25 )]∪[arcsin( 25 ), π− arcsin( 25 )].
Однако если вообще убрать краевые условия и рассмотреть задачу
(8), (9) без них, то численный метод локальных вариаций дает следующий результат:
N = 299, h = 0.001
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Н. А. Демьянков
10
Если продолжить уменьшать шаг метода, то график меняется на
следующий:
N = 399, h = 0.0001
Как видно, с уменьшением шага метода и, следовательно, уменьшением погрешности график решения на интервале t ∈ [arcsin( 25 ), π]
немного «выпрямляется». Аналогично, и кусок на интервале
t ∈ [−π, − arcsin( 25 )].
Дальнейшее уменьшение шага и увеличение числа точек не приносит новых результатов, однако время вычисления сильно возрастает.
4. Заключение. В данной статье был приведен численный метод локальных вариаций, который можно использовать для решения вариационных задач с фазовыми ограничениями. Рассмотренная задача имеет достаточно частный вид, но в дальнейшем можно вполне перейти
и к более общим случаям. Также интересно попробовать оптимизировать метод локальных вариаций, поскольку при большом числе точек
и малом шаге вычисление идет достаточно долго.
Литература
1. Иоффе А. Д., Тихомиров В. М. Теория экстремальных задач. М.:
Наука, 1974.
2. Гирсанов И. В. Лекции по математической теории экстремальных
задач. М.: МГУ, 1970.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
11
3. Черноусько Ф. Л., Баничук Н. В. Вариационные задачи механики
и управления. М.: Наука, 1973.
4. Милютин А. А. Принцип максимума в общей задаче оптимального управления. М.: ФИЗМАТЛИТ, 2001.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ДИНАМИЧЕСКИЕ СИСТЕМЫ
УДК 517.929
Е. Н. Агафончиков
Построение асимптотики решений
системы двух дискретных осцилляторов
с медленно убывающей связью
Исследуется динамика одной разностной системы двух линейных
осцилляторов с медленно убывающей связью. Построена асимптотика
решений данной системы при различных значениях параметров.
1. Постановка задачи. В работе рассматривается задача построения
асимптотики при n → ∞ решений системы двух дискретных связанных осцилляторов следующего вида:
a sin ωn
x2(n) = 0,
nα
b sin ωn
x2(n + 2) − 2(cos ω2 )x2(n + 1) + x2(n) +
x1(n) = 0,
nβ
x1(n + 2) − 2(cos ω1 )x1(n + 1) + x1(n) +
(1)
где 0 < ω1, ω2 < π; α, β > 0; a, b ∈ R, a = 0, b = 0, 0 < ω < 2π и n ∈ N.
Для решения указанной задачи мы будем использовать усредняющие замены переменных, а также воспользуемся разностным вариантом известной асимптотической теоремы Н. Левинсона. В следующем
пункте мы подробно опишем используемую нами методику.
2. Вспомогательные сведения. Введем некоторые обозначения. Мы
будем писать, что f (t) ∈ 1, где f (t) : N → C, если
∞
|f (k)| < ∞.
k=1
Запись R(t) ∈ 1 , где R(t) — матрица произвольных размеров и t ∈ N,
означает, что f (t) = ||R(t)|| ∈ 1 , где ||·|| — некоторая матричная норма.
Далее, если f (t) — скалярная функция (или матрица), то положим
Δf (t) = f (t + 1) − f (t),
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
13
где Δ — конечно-разностный оператор.
Рассмотрим следующую систему линейных разностных уравнений:
x(t + 1) = Λ(t) + R(t) x(t),
(2)
где Λ(t) = diag λ1 (t), . . . , λm (t) и λ−1
i (t)R(t) ∈ 1 для всех i = 1, . . . , m.
Определение. Системы вида (2) будем называть -диагональными.
Имеет место следующий разностный аналог теоремы Левинсона,
известный как теорема Бензаида-Латса [1].
Теорема 1. Пусть
(1)
λi (t) = 0,
(2)
1 ≤ i ≤ m,
λ−1
i (t)R(t) ∈ 1 ,
t ≥ t0 ,
1 ≤ i ≤ m,
(3) выполнены следующие условия: найдутся положительные
константы μ > 0 и K > 0 такие, что для любой пары индексов
(i, j), i = j, имеет место или
t2 t λi (l) λi (l) λj (l) → ∞, t → ∞ и
λj (l) ≥ μ > 0, t0 ≤ t1 ≤ t2 , (3)
l=t0
или
l=t1
t2 λi (l) λj (l) ≤ K,
t0 ≤ t1 ≤ t2 .
(4)
l=t1
Тогда фундаментальная матрица X(t) системы (2) допускает следующее асимптотическое представление при t → ∞:
t−1
Λ(l).
X(t) = I + o(1)
(5)
l=t0
Замечание 1. Если |λi (t)| ≥ δ > 0 для всех i = 1, . . . , m, то условие
(2) теоремы 1 заведомо выполняется, когда R(t) ∈ 1 .
Замечание 2. Отметим следующие условия, достаточные для выполнения (3), (4). Пусть λi (t) → λi = 0, 1 ≤ i ≤ m и
a) |λi | = |λj | для i = j. Тогда если |λi | > |λj |, то имеет место (3), в
противном случае выполнено (4).
б) |λi | = |λj | для некоторой пары индексов (i, j), i = j. Положим
|λi (t)/λj (t)| = 1 + rij (t),
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
14
где rij (t) → 0, t → ∞. Тогда, как несложно показать, если rij (t) не
меняет своего знака при t ≥ t0, то условия (3), (4) также оказываются
выполненными.
Рассмотрим далее систему
x(t + 1) = (A0 + V (t) + R(t))x(t),
(6)
где матрица A0 не вырождена и все ее собственные числа различны,
V (t) → 0, t → ∞, ΔV (t) ∈ 1 , R(t) ∈ 1 . Имеет место следующее
утверждение.
Лемма 1. Существует не вырожденная при t ≥ t0 матрица C(t),
удовлетворяющая свойствам:
1. C(t) → Π при t → ∞, где матрица Π приводит матрицу A0 к
диагональному виду,
2. ΔC(t) ∈ 1,
такая, что замена x(t) = C(t)y(t) приводит систему (6) к -диагональной форме
y(t + 1) = (Λ(t) + R1 (t))y(t).
Здесь Λ(t) — диагональная матрица, составленная из собственных
чисел матрицы A0 + V (t) и R1 (t) ∈ 1 .
Определение. Будем говорить, что матрица A(t) принадлежит классу Σ, если ее элементами являются тригонометрические многочлены
p(t) =
n
cj eiωj t .
j=1
Кроме того, если эти тригонометрические многочлены имеют нулевое
среднее значение
t−1
1
M p(t) = lim
p(k) = 0,
t→∞ t
k=0
то будем писать, что матрица A(t) ∈ Σ0.
Рассмотрим следующую систему линейных разностных уравнений
с колебательно убывающими коэффициентами:
n
Ai (t)vi(t) +
x(t + 1) = A0 +
i=1
+
1≤i1 ≤...≤ik ≤n
1≤i1 ≤i2 ≤n
Ai1i2 (t)vi1 (t)vi2 (t) + . . . +
Ai1 ... ik (t)vi1 (t) · . . . · vik (t) + R(t) x(t). (7)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
15
Здесь A0 , Ai1 ... il (t), R(t) — квадратные матрицы, v1(t), . . . , vn (t) — скалярные функции, x(t) ∈ Cm и t ∈ N.
Пусть
1. A0 — постоянная невырожденная матрица с вещественными
собственными значениями. Кроме того, мы предположим, что спектры
матриц A0 и (−A0) не пересекаются.
2. v1(t) → 0, v2(t) → 0, . . . , vn(t) → 0 при t → ∞.
3. Δv1(t), Δv2(t), . . . , Δvn(t) ∈ 1.
4. Произведение vi1 (t)vi2 (t) . . . vik+1 (t) ∈ 1 для любого набора
1 ≤ i1 ≤ i2 ≤ . . . ≤ ik+1 ≤ n.
5. Матрицы Ai1 ... il (t) принадлежат классу Σ.
6. Матрица R(t) ∈ 1 .
При выполнении указанных выше условий 1 — 6 справедлива следующая теорема (см. [3]).
Теорема 2. Система (7) при достаточно больших t заменой
n
x(t) = I +
Yi (t)vi(t) +
i=1
1≤i1 ≤i2 ≤n
+
Yi1i2 (t)vi1 (t)vi2 (t) + . . . +
Yi1... ik (t)vi1 (t) · . . . · vik (t) y(t), (8)
1≤i1≤...≤ik ≤n
где I — единичная матрица, а матрицы Yi1 ... il (t) принадлежат классу Σ0, приводится к виду
y(t + 1) = A0 +
n
Ai vi(t) +
i=1
+
Ai1 i2 vi1 (t)vi2 (t) + . . . +
1≤i1 ≤i2 ≤n
Ai1... ik vi1 (t) · . . . · vik (t) + R1(t) y(t),
t ∈ N (9)
1≤i1 ≤...≤ik ≤n
с постоянными матрицами Ai1 ... il и матрицей R1 (t) ∈ 1.
Явные формулы для определения постоянных матриц Ai1... il могут
быть найдены в книге [3]. Нам в дальнейшем потребуется лишь вид
матриц первого «приближения»:
Ai = M[Ai(t)],
i = 1, . . . , n.
3. Построение асимптотики. Стандартным образом приводим систему (1) к виду
z(n + 1) = (A + B1(n)n−α + B2 (n)n−β )z(n),
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
16
где
⎞
x1
⎜ y1 ⎟
⎟
z(n) = ⎜
⎝ x2 ⎠ ,
y2
⎛
и
⎛
B1 (n) = ⎝
O
O
⎛
⎞
0
1
⎜ −1 2 cos ω1
A=⎜
⎝
O
⎞
0
0
−a sin ωn 0 ⎠ ,
O
O
⎟
⎟,
⎠
0
1
−1 2 cos ω2
⎛
O
0
0
B2(n) = ⎝
−b sin ωn 0
O
O
⎞
⎠.
Здесь O — (2 × 2)-нулевая матрица.
Вычислим собственные значения матрицы A:
λ1,2 = cos ω1 ± i sin ω1 ,
λ3,4 = cos ω2 ± i sin ω2 .
Дальнейшие расчеты удобнее будет проводить, если записать собственные значения матрицы A в показательной форме:
λ2 = e−iω1 ,
λ1 = eiω1 ,
λ4 = e−iω2 .
λ3 = eiω2 ,
Сделаем замену z(n) = DC nu(n), где
⎞
⎛ −iω iω
⎛ iω
0
e 1 e 1
e 1
O
−iω1
⎟
⎜ 1
⎜
1
⎟, C = ⎜ 0 e
D=⎜
−iω
iω
⎝
⎝
e 2 e 2 ⎠
O
O
1
1
⎞
O
0
eiω2
−iω2
0 e
⎟
⎟.
⎠
Отметим, что матрица D приводит матрицу A к диагональному виду.
Приходим к следующей системе:
u(n + 1) = [I + A1(n)n−α + A2 (n)n−β ]u(n)
с матрицами A1, A2 вида
ai O Ā1(n)
,
A1 (n) =
O
O
2
где
Ā1(n) = c1
ā11 ā12
ā21 ā22
bi
A2(n) =
2
, Ā2(n) = c2
(10)
O
O
Ā2(n) O
b̄11 b̄12
b̄21 b̄22
,
(10a)
,
(10b)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
ā11
ā12
ā21
ā22
b̄11
b̄12
b̄21
b̄22
=
=
=
=
=
=
=
=
−e−iω2 [ein(−ω1+ω2 +ω) − ein(−ω1+ω2 −ω)],
−eiω2 [ein(−ω1−ω2+ω) − ein(−ω1 −ω2−ω) ],
e−iω2 [ein(ω1 +ω2+ω) − ein(ω1 +ω2 −ω)],
eiω2 [ein(ω1−ω2 +ω) − ein(ω1−ω2 −ω) ],
−e−iω1 [ein(ω1 −ω2+ω) − ein(ω1 −ω2 −ω)],
−eiω1 [ein(−ω1−ω2+ω) − ein(−ω1 −ω2−ω) ],
e−iω1 [ein(ω1 +ω2+ω) − ein(ω1 +ω2 −ω)],
eiω1 [ein(−ω1+ω2+ω) − ein(−ω1 +ω2−ω) ],
и
c1 =
17
(e−iω1
1
,
− eiω1 )
c2 =
(e−iω2
1
.
− eiω2 )
Заметим, что в случае α > 1, β > 1 система (10) уже имеет диагональный вид. Воспользовавшись теоремой 1, мы можем получить
асимптотику решений системы (1) в этом случае:
x1(n) = C1 sin(ω1n + γ1) + o(1),
x2(n) = C2 sin(ω2n + γ2) + o(1),
(11)
где C1, C2, γ1, γ2 — произвольные действительные постоянные. Поэтому
в дальнейшем считаем, что
α ≤ 1 и (или) β ≤ 1.
Используя теорему 2, сделаем в системе (10) замену
u(n) = [I + Y1(n)n−α + Y2 (n)n−β ]v(n).
(12)
Получим усредненную систему вида
v(n + 1) = (I + A1n−α + A2 n−β + R(n))v(n).
(13)
Из представления (10a), (10b) матриц A1 (n) и A2(n) следует, что вид
матриц A1, A2 (как, впрочем, и вид матриц Y1 (n), Y2 (n) в замене (12))
будет различным в следующих случаях:
1. ω = ω1 − ω2, ω = ω2 − ω1, ω = ω1 + ω2 ,
2. ω = ω1 − ω2,
3. ω = ω2 − ω1,
4. ω = ω1 + ω2.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
18
Рассмотрим подробно первые два из этих случаев.
3.1. ω = ω1 − ω2 , ω = ω2 − ω1 , ω = ω1 + ω2 .
В этом случае A1 = A2 = 0, тогда система (13) имеет вид
v(n + 1) = (I + R(n))v(n),
и асимптотика решений исходной системы (1) будет определяться формулами (11).
3.2. Случай ω = ω1 − ω2 .
Матрицы A1 и A2 определяются следующим образом:
⎛
⎞
e−iω2 0
a ⎝O
0 eiω2 ⎠ ,
A1 = M[A1(n)] =
4 sin ω1
O
O
⎛
A2 = M[A2(n)] = −
O
O
b
⎝ e−iω1 0
4 sin ω2
0 eiω1
O
⎞
⎠.
Вычислим собственные числа матрицы (I + A1n−α + A2n−β ). Имеем:
λ1 = 1 − γ1n−
α+β
2
где
, λ2 = 1 + γ1n−
α+β
2
, λ3 = 1 − γ2n−
i
γ1 = γ̂e− 2 (ω1 +ω2) ,
и
γ̂ =
Обозначим:
√
√ i ab
,
4 sin√ω1 sin ω2
√ − −ab
,
4 sin ω1 sin ω2
α+β
2
, λ4 = 1 + γ2n−
α+β
2
,
i
γ2 = γ̂e 2 (ω1 +ω2) ,
если ab > 0,
если ab < 0.
Λ = diag(−γ1, γ1, −γ2, γ2).
(14)
Выпишем матрицу, составленную из собственных векторов матрицы I + A1n−α + A2n−β :
⎛ ⎞
γ1 β−α
γ1 β−α
2
2
− γ3 n
0
0
γ3 n
⎜
⎟
β−α ⎟
⎜
γ2 β−α
γ
2
2
0
0
− γ4 n 2
⎟.
F (n) = ⎜
γ4 n
⎜
⎟
⎝
⎠
1
1
0
0
0
0
1
1
Осуществим в системе (13) замену v(n) = F (n)v1(n). Учитывая равенство
F (n + 1) = F (n) + ΔF (n),
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
19
получим следующую систему:
[I + F −1(n)ΔF (n)]v1(n + 1) = [I + Λ(n) + F −1 (n)R(n)F (n)]v1(n). (15)
Матрица F −1 (n)ΔF (n) имеет следующий вид:
F −1(n)ΔF (n) = Bn−1 + O(n−2 ),
⎛
где
1 −1
⎜
β − α ⎜ −1 1
B=
4 ⎝
O
⎞
O
⎟
⎟.
1 −1 ⎠
−1 1
Поскольку матрица F −1 (n)ΔF (n) стремится к нулевой матрице при
n → ∞, то матрица (I + F −1 (n)ΔF (n)) обратима и
(I + F −1(n)ΔF (n))−1 = I − F −1(n)ΔF (n) + O(n−2 ).
Покажем теперь, что R1 (n) = F −1(n)R(n)F (n) ∈ 1. Матрица R(n)
имеет следующий вид:
O(n−α−β ) O(n−α−1)
.
R(n) =
O(n−β−1) O(n−α−β )
Кроме того, несложно показать, что
F (n) =
β−α
2
O(n
O(1)
β−α
2
) O(n
O(1)
)
, F −1(n) =
α−β
2
O(n ) O(1)
α−β
O(n 2 ) O(1)
.
Следовательно, R1 (n) = O(n−(α+β) ) и при условии α + β > 1 матрица
R1(n) принадлежит классу 1.
Таким образом, система (15) принимает вид:
v1(n + 1) = [I − Bn−1 + Λn−
α+β
2
+ R2 (n)]v1(n),
(16)
где R2 (n) ∈ 1.
Далее задача разбивается на несколько случаев.
3.2.1. Случай α + β > 2.
При выполнении условия α + β > 2 система (16) принимает вид:
v1(n + 1) = [I + Bn−1 + R3(n)]v1(n),
где R3 (n) = Λn−
α+β
2
+ R2(n) ∈ 1.
(17)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
20
В данной ситуации нам удобнее будет работать с системой (13).
Для определенности считаем, что 0 < α < 1 < β (случай α = 1 < β
рассмотрим отдельно). В рассматриваемом случае слагаемое A2n−β
войдет в суммируемый остаток. Приведем матрицу I + A1n−α к жордановой нормальной форме. Для этого сделаем замену v(n) = Jv1(n),
где
⎞
⎛
0
0
1
0
⎟
⎜1
0
0
0
⎟
⎜
J =⎜
2i(e−iω1 −eiω1 ) ⎟ .
0
0
⎠
⎝0
ae−iω2
2i(e−iω1 −eiω1 )
0
0
0
aeiω2
Система (13) приобретает вид:
ˆ −α + R̂(n)]v1(n),
v1(n + 1) = [I + Jn
⎛
где
0 1
⎜ 0 0
Jˆ = ⎜
⎝
O
(18)
⎞
O
⎟
⎟.
0 1 ⎠
0 0
Сделаем далее замену v1 = P (n)v2, где
⎛
n
n−1
O
⎜ 0 nα (1 − α)
P (n) = ⎜
⎝
n
n−1
O
α
0 n (1 − α)
⎞
⎟
⎟.
⎠
Имеем
(19)
v2(n + 1) = [V̂ (n) + R̂1 (n)]v2(n),
где
и
⎛
v̂1 o(n−1)
⎜ 0
v̂2
V̂ (n) = ⎜
⎝
O
⎞
O
⎟
⎟
v̂1 o(n−1) ⎠
0
v̂2
v̂1 = 1 − n−1 + o(n−1), v̂2 = 1 − αn−1 + o(n−1).
Так как замена v1 = P (n)v2 является заменой с неограниченными коэффициентами, то нам необходимо проверить суммируемость остатка R̂1 (n). Этот остаток можно разбить на два слагаемых:
P −1(n + 1)J −1A2 n−β JP (n) и P −1 (n + 1)J −1R(n)JP (n).
Слагаемое P −1 (n+1)J −1A2n−β JP (n) несложно найти в явном виде,
его порядок равен O(n1−β−α ), а P −1 (n + 1)J −1R(n)JP (n) будет иметь
порядок O(n−2). Отсюда следует, что R̂1 (n) ∈ 1 .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
21
Перепишем (19) в виде:
v2(n + 1) = [I + V n−1 + R1 (n)]v2(n),
где R1 (n) ∈ 1, а
(20)
V = diag(−1, −α, −1, −α).
Воспользовавшись теоремой 1, получаем асимптотику системы (20)
при n → ∞:
n−1
V2(n) = [I + o(1)]
I + V l−1 .
l=n0
Поскольку
n−1
l−1 = ln n + C + O(n−1),
l=n0
заключаем, что
n−1
(1 − l−1) = C1n−1[1 + O(n−1)],
l=n0
и
n−1
(1 − αl−1) = C2n−α [1 + O(n−1 )],
l=n0
где C1, C2 — некоторые постоянные. Возвращаясь к исходной системе
(1), получаем:
x1 = 4(1+α)a sin ω1 n−α+1(ei(ω1 +ω2) c1 e−inω1 + e−i(ω1 +ω2) c2 einω1 ) + o(n−α+1),
x2 = eiω2 c1 e−inω2 + e−iω2 c2 einω2 + o(1),
(21)
где c1 , c2 — произвольные постоянные.
Перейдем к случаю α = 1 < β. Система (18) примет вид:
ˆ −1 + R̂(n)]v(n),
v(n + 1) = [I + Jn
(22)
где R̂(n) ∈ 1 . Найдем фундаментальную матрицу системы
ˆ −1]v(n),
v(n + 1) = [I + Jn
которую мы получили
ем
⎛
1 n1
⎜0 1
V̄ (n + 1) = ⎜
⎝0 0
0 0
(23)
из (22), отбросив остаток R̂(n). Из (23) получа⎞⎛
1
0 0
⎜
0 0⎟
⎟⎜ 0
1 ⎠⎝
1 n
0
0 1
0
1
n−1
1
0
0
0
0
1
0
⎞ ⎛
0
⎜
0 ⎟
⎟ ⎜
1 ⎠...⎝
n−1
1
1
0
0
0
1
1
0
0
0
0
1
0
⎞
0
0⎟
⎟.
1⎠
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
22
Отсюда
⎛
⎞
n
1
l
⎜ 1
l=1
⎜
⎜ 0 1
V̄ (n + 1) = ⎜
⎜
⎜
⎝
O
⎛
O
1
0
n
1
l=1
l
⎟
⎟
⎟
⎟=
⎟
⎟
⎠
1
1 ln n + C1 + O(n−1)
⎜ 0
1
=⎜
⎝
O
⎞
O
⎟
⎟.
1 ln n + C1 + O(n−1) ⎠
0
1
Сделаем в (22) замену v(n) = V̄ (n)v1(n). Получаем:
ˆ −1 + R̂(n)]V̄ (n)v1(n).
V̄ (n + 1)v1(n + 1) = [I + Jn
Учитывая, что V̄ (n) удовлетворяет системе (23), заключаем
v1(n + 1) = [I + V̄ (n + 1)−1R̂(n)V̄ (n)]v1(n),
(24)
где остаток V̄ (n + 1)−1R̂(n)V̄ (n) входит в класс 1 . Таким образом, система (24) имеет -диагональный вид. Из теоремы 1 следует, что для
ее фундаментальной матрицы справедливо асимптотическое представление
V1 (n) = I + o(1),
n → ∞.
Для решений системы (1) справедливы следующие асимптотические
формулы при n → ∞:
x1 = 4 sina ω1 ln n(ei(ω1+ω2 ) c1 e−inω1 + e−i(ω1 +ω2) c2 einω1 ) + o(ln n),
x2 = eiω2 c1 e−inω2 + e−iω2 c2 einω2 + o(1),
где c1 , c2 — произвольные постоянные.
3.2.2. Случай α + β < 2.
Вернемся к системе (16) и преобразуем ее:
v1(n + 1) = [I + (Λ + Bn
α+β
2 −1
)n−
α+β
2
+ R2 (n)]v1(n).
(25)
Выпишем теперь следующую систему, формально с предыдущей не
связанную:
α+β
(26)
v1(n + 1) = [Λ + Bn 2 −1]v1(n).
Собственные числа матрицы Λ различны, если ω1 + ω2 = π. Из леммы 1 тогда следует существование такой матрицы C(n) = I + o(1),
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
23
что замена v1 (n) = C(n)v2(n) приводит (26) к -диагональному виду.
Осуществим теперь такую замену в системе (25):
v2(n+1)=[C −1(n+1)C(n)+C −1(n+1)(Λ+Bn
α+β
2 −1
)C(n)n−
α+β
2
+R3 (n)]v2(n).
Очевидно, что матрица R3 (n) = C −1(n + 1)R2(n)C(n) принадлежит
классу 1. Заметим, что
C −1(n + 1)C(n) = (C(n)[I + C −1(n)ΔC(n)])−1C(n) =
= I − C −1(n)ΔC(n) + O(ΔC 2(n)), (27)
так как C −1(n) ограничено, а ΔC(n) ∈ 1 . Тогда
v2(n + 1) = [I + Λn−
α+β
2
+ B̂n−1 + R̂3 (n)]v2(n),
(28)
где R̂3(n) ∈ 1 , а B̂ = α−β
4 I. Остается лишь применить теорему 1,
чтобы получить асимптотику фундаментальной матрицы системы (28)
при n → ∞:
V2 (n) = [I + o(1)]
n−1
I + Λn
− α+β
2
+ B̂n
−1
,
l=n0
где Λ определяется формулой (14).
В зависимости от знака ab получаем два случая:
1. ab > 0
Несложно видеть, что в этом случае
Re γ1 = − Re γ2 = −iγ̂ sin(
ω1 + ω2
)=μ>0
2
и
ω1 + ω2
) = ν.
2
Выпишем асимптотику решений исходной системы:
a sin ω2 β−α
α+β
2μ
x1 = i b sin ω1 n 4 exp{ 2−α−β
n1− 2 }×
α+β
α+β
1− 2
1− 2
i(ω1 +ω2 )
i(ω1 +ω2 )
−2iν
2iν
× e− 2 c1 einω1 e 2−α−β n
+e 2 c2 e−inω1 e 2−α−β n
+o(1) ,
Im γ1 = Im γ2 = −iγ̂ cos(
x2 = n
α−β
4
2μ
exp{ 2−α−β
n1−
× e−iω2 c1 einω2 e
α+β
2
}×
1−
−2iν
2−α−β n
α+β
2
− eiω2 c2 e−inω2 e
где c1 , c2 — произвольные постоянные.
1−
2iν
2−α−β n
α+β
2
+ o(1) ,
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
24
2. ab < 0
В этом случае
Re γ1 = Re γ2 = γ̂ cos(
ω1 + ω2
)=μ
2
и
ω1 + ω2
) = ν.
2
Получаем следующую асимптотику для решений исходной системы:
a sin ω2 β−α
α+β
2μη
x1 = η − b sin ω1 n 4 exp{ 2−α−β
n1− 2 }×
α+β
2iην
−2iην 1− α+β
1− 2
i(ω1 +ω2 )
i(ω1 +ω2 )
2
n
n
× e− 2 c1 einω1 e 2−α−β
−e 2 c2 e−inω1 e 2−α−β
+o(1) ,
Im γ1 = Im γ2 = γ̂ sin(
x2 = n
α−β
4
2μ
exp{ 2−α−β
n1−
× e−iω2 c1 einω2 e
α+β
2
}×
α+β
2iην
1− 2
2−α−β n
+ eiω2 c2 e−inω2 e
−2iην 1− α+β
2
2−α−β n
+ o(1) ,
где
η = sign (ω1 + ω2 − π)
и c1 , c2 — произвольные постоянные.
3.2.3. Случай α + β = 2.
Система (16) выглядит следующим образом:
v1(n + 1) = [I + Λ̂n−1 + R2(n)]v1(n),
где Λ̂ = B + Λ.
Вычислим собственные значения матрицы (I + Λ̂n−1) :
α − β − μ1
,
4n
α − β − μ2
λ3 = 1 +
,
4n
λ1 = 1 +
α − β + μ1
,
4n
α − β + μ2
λ4 = 1 +
,
4n
λ2 = 1 +
где
μ1 =
ϕσ1
√
r(cos
ϕσ
ϕσ1
+ i sin 1 ),
2
2
μ2 =
√
ϕσ
ϕσ
r(cos 2 + i sin 2 ),
2
2
2 cos (ω +ω )
a2 b 2
1
2
r =
(α − β)4 − 2ab(α−β)
+
sin ω1 sin ω2
sin ω1 sin ω2 ,
ab sin (ω1 + ω2)
.
= −ϕσ2 = arctg
(α − β)2 sin ω1 sin ω2 − ab cos (ω1 + ω2)
(29)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
25
Выпишем матрицу из собственных векторов для системы (29):
⎞
⎛ 4γ1 +μ1 4γ1 −μ1
0
0
α−β
α−β
⎜ 1
1
0
0 ⎟
⎟
H=⎜
4γ2 +μ2 4γ2 −μ2 ⎠ .
⎝ 0
0
α−β
α−β
0
0
1
1
Заметим, что H обратима при ω1 +ω2 = π, случай равенства требует
отдельного рассмотрения. Также отметим, что
√
ϕσ
Re μ1 = Re μ2 = r cos 1 ,
2
и обозначим
μ = Re μ1 = Re μ2 .
Сделаем в (29) замену v1 (n) = Hv2 (n). В результате получаем:
v2(n + 1) = [I + Λ̂1 n−1 + R3(n)]v2(n),
где
⎛
⎜
Λ̂1 = ⎜
⎝
α−β−μ1
4
0
0
0
0
α−β+μ1
4
0
0
0
0
α−β−μ2
4
0
0
0
0
⎞
⎟
⎟
⎠
α−β+μ2
4
и R3 (n) = H −1 R2 (n)H ∈ 1 . По теореме 1 получаем:
v2 (n) = [I + o(1)]
n−1
(I + Λ̂1 l−1).
n0
Получаем следующую асимптотику для решений исходной системы (1)
при n → ∞:
β−α+μ
√
ϕσ1
√
ϕσ1
x1 = n 4 (c1 κ1 e−iω1 einω1 ei r sin 2 ln n +c2 κ2 eiω1 e−inω1 e−i r sin 2 ln n +o(1))
√
√
ϕσ1
ϕσ1
α−β+μ
x2 = n 4 (c1 e−iω2 einω2 ei r sin 2 ln n +c2 eiω2 e−inω2 e−i r sin 2 ln n+o(1)),
где
eiω2 (e−iω2 + eiω2 )
e−iω2 (e−iω2 + eiω2 )
, κ2 = χ
,
κ1 = χ
eiω1 (e−iω1 − eiω1 )
e−iω1 (e−iω1 − eiω1 )
i ab , при ab > 0,
χ= a
− b , при ab < 0,
и c1 , c2 — произвольные постоянные.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. Н. Агафончиков
26
4. Заключение. Таким образом, нам удалось выяснить, как ведут
себя решения системы (1) в зависимости от параметров.
В случае α > 1, β > 1 существуют только ограниченные решения.
При ω = ω1 − ω2 , ω = ω2 − ω1, ω = ω1 + ω2 (этот случай называется
нерезонансным) решения также ограничены, если α + β > 1.
В случае ω = ω1 − ω2 справедливы следующие результаты. При
α + β > 2, 0 < α ≤ 1 < β решение x1(n) неограниченно возрастает по абсолютной величине, а решение x2(n) остается ограниченным.
При этом если α < 1, то рост амплитуды колебаний происходит по
степенному закону, а если α = 1 — по логарифмическому.
Когда α и β удовлетворяют условию α+β < 2, амплитуда колебаний
решений x1 (n) и x2(n) растет.
Если α + β = 2, возможно такое поведение решений, при котором
амплитуда колебаний решения x1(n) растет, а амплитуда колебаний
x2(n) может как возрастать, так и убывать.
Чтобы получить асимптотику для случая ω = ω2 − ω1 , следует в
асимптотиках для случая ω = ω1 − ω2 поменять ω1 и ω2 местами.
При ω = ω1 + ω2 следует заметить, что ω1 + ω2 = ω1 − (−ω2), тогда
будет справедлива асимптотика, полученная для случая ω = ω1 − ω2
с точностью до замены ω2 на −ω2 . Кроме того, если нам необходимо
получить результаты для случая ab > 0, следует взять результаты, полученные нами для случая ω = ω1 −ω2 , ab < 0. Если же нас интересует
случай ab < 0, надо взять результаты в случае ω = ω1 − ω2 , ab > 0.
Литература
1. Benzaid Z., Lutz D. A. Asymptotic representation of solutions of
perturbed systems of linear difference equations // Studies in Appl.
Math. 1987. V. 77. P. 195–221.
2. Bourd A. V. Asymptotic behavior of solutions of some linear
difference equations with oscillatory decreasing coefficients //
Journal of Difference Equations and Applications. 2003. V. 9, №2.
P. 211–225.
3. Бурд В. Ш., Нестеров П. Н. Системы дифференциальных и разностных уравнений: метод усреднения и асимптотика решений:
учеб. пособие. Ярославль: ЯрГУ, 2008.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 519.711.2
А. А. Антонычев, А. А. Короткин
Игровая автоматная модель
локального управления в системе распределения
общего нерасходуемого ресурса
Рассматривается игра автоматов, функционирующих в непрерывной
шкале времени, как способ управления локально организованной системой, компоненты которой используют общий ограниченный ресурс.
Доказывается устойчивость соответствующей динамической системы.
Приводится дискретная реализация полученной системы применительно к задаче назначения рабочих частот для коллектива радиоэлектронных средств, работающих в общем диапазоне.
Введение
В настоящее время активно развивается теория управления в локально организованных сложных системах. Под локально организованной системой понимается система A = {A1 , A2, . . . , An}, компоненты Ai которой функционируют в некоторой общей среде, при этом
действие ai каждой компоненты Ai связано с достижением локальной
цели Pi независимо от действий других компонент и Ai доступна лишь
локальная информация о действиях других компонент [1]. Важной
особенностью локально организованной системы является отсутствие
для нее глобальной целевой функции, характеризующей качество работы всей системы A. Примерами систем подобного типа могут служить сети передачи данных, группировки радиоэлектронных средств,
работающих в общем диапазоне рабочих частот, интеллектуальные
операционные системы и ряд других. В таких системах, как правило, возникают конфликтные ситуации, связанные с использованием
некоторого ограниченного нерасходуемого ресурса, например, общего
радиочастотного диапазона, модулей памяти компьютера и т. п.
Управление в локально организованной системе естественно рассматривать как игру автоматов c непрерывным или дискретным множеством действий, каждый из которых ассоциирован с соответствующей компонентой Ai. Основные положения теории игр автоматов
для ряда моделей локально организованных систем изложены в монографиях [1]–[3]. В рамках этой теории в данной работе исследуется
коллективное поведение системы автоматов с полным графом взаимодействия и аддитивными локальными целевыми функциями.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Антонычев, А. А. Короткин
28
Модель взаимного влияния
Пусть имеется совокупность n автоматов A1, . . . , An, взаимодействующих между собой в непрерывной шкале времени. Это взаимодействие связано с использованием автоматами некоторого нерасходуемого ресурса, например, радиочастотного спектра. В момент времени
t автомат Aj выбирает величину aj (t) ∈ R, состояние системы характеризуется вектором a(t) = (a1 (t), . . . , an (t)) ∈ Rn .
Взаимодействие автоматов происходит следующим образом. В зависимости от выбранных действий автомат Ai создает нежелательное воздействие («помеху») для автомата Aj , которое оценивается
величиной pij (ai , aj ) 0. Естественно, что pjj (aj , aj ) = 0 для всех
j = 1, . . . , n.
Будем далее считать, что результирующее воздействие всех Ai ,
i = 1, . . . , j − 1, j + 1, . . . , n на Aj аддитивно, т. е. суммарная помеха
для Aj есть величина
Pj (a) =
n
pij (ai , aj ) .
i=1
i
=j
На рис. 1 приведена схема взаимодействия автоматов в рассматриваемой модели.
i =1
pi1 (ai , a1)
i =2
pi2(ai , a2)
A1
i =n
pin(ai , an)
A2
An
a1
a2
an
Рис. 1. Взаимодействие автоматов
Далее будем предполагать, что взаимное помеховое влияние в «дуэльной» ситуации Ai Aj симметрично, т. е. pij (ai , aj ) = pji (aj , ai )
для всех пар (i, j). Кроме того, будем предполагать, что все функции
pij (ai , aj ) ограничены и непрерывно дифферецируемы по обоим аргументам.
Очевидно, что целью каждого автомата является снижение суммарного уровня помех от других автоматов: Pj (a1 , . . . , aj , . . . , an ) → min,
aj
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
29
j = 1, 2, . . . , n. В этом случае изменение действия aj (t) каждого автомата Aj во времени естественно определить как движение по антиградиенту его целевой функции. Таким образом, динамика состояния
всей совокупности автоматов описывается следующей системой:
ȧj = −
∂Pj (a)
,
∂aj
(1)
j = 1, ..., n..
Устойчивость локального управления
Рассмотрим вопрос о предельном характере траектории a(t) системы автоматов. Стандартным способом исследования динамических систем является построение функции Ляпунова. Определим функцию1
1
V (a) =
Pj (a).
2 j=1
n
Очевидно, что V (a) ограничена снизу нулем. Рассмотрим поведение V (a) на траекториях системы (1). Для этого определим производd V (a(t))
ную
, где a (t) — произвольное решение системы (1).
dt
n
n
n
n
1 ∂Pk
d
1 ∂Pk
∂Pj
=
V (a (t)) =
ȧj =
· −
dt
2 j=1
∂aj
2 j=1
∂aj
∂aj
k=1
k=1
⎡
⎤
n
n
n
n
1 ∂Pj ∂Pk
1 ∂Pj ⎢ ∂Pj ∂Pk ⎥
=−
= −
+
⎣
⎦=
2 j=1 ∂aj
∂aj
2 j=1 ∂aj ∂aj
∂aj
⎡
k=1
n ∂Pj
1⎢
=− ⎣
2 j=1 ∂aj
2
k=1
k
=j
⎤
n
∂Pj ∂Pk ⎥
+
·
⎦
∂a
∂aj
j
j=1
(2)
k=1
k
=j
Далее заметим, что для любого j ∈ {1, 2, . . . , n}
n
∂Pk
k=1
k
=j
∂aj
=
∂Pj
.
∂aj
(3)
Действительно,
n
∂Pk
k=1
k
=j
1
∂aj
=
n
n ∂pik (ai , ak )
k=1 i=1
k
=j
∂aj
=
n
∂pjk (aj , ak )
k=1
k
=j
∂aj
=
n
∂pkj (ak , aj )
k=1
k
=j
∂aj
=
∂Pj
.
∂aj
Для динамических систем типа нейронных сетей Хопфилда функции такого типа называются
функциями энергии.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Антонычев, А. А. Короткин
30
Предпоследнее равенство в этой цепочке справедливо в силу симметрии взаимного влияния (pjk = pkj ).
∂Pk
Подставляя значение для
из (3) в (2), окончательно поk
=j ∂aj
лучим
1
d
V (a (t)) = −
dt
2
n ∂Pj 2
j=1
∂aj
+
2
n ∂Pj
j=1
∂aj
'
=−
2
n ∂Pj
j=1
∂aj
≤ 0.
Таким образом, функция V (a) является функцией Ляпунова и,
следовательно, рассматриваемая модель устойчива. Другими словами,
эволюция во времени коллектива автоматов, описываемая системой
(1), представляет собой некоторую траекторию в пространстве состояний, обеспечивающую нахождение минимума (в общем случае локального) функции энергии и приходящую к некоторой фиксированной точке a∗ .
Замечание 1. В [1] для градиентной системы более общего вида
доказательство устойчивости было проведено в предположении, что
структура взаимодействия автоматов описывается ориентированным
корневым деревом (иерархическая система). В рассматриваемой нами модели взаимодействие задается полным ориентированным графом,
однако при доказательстве устойчивости существенно использовалось
условие симметрии взаимного влияния автоматов и аддитивности результирующего воздействия.
Замечание 2. Можно показать, что стационарное состояние a∗ динамической системы (1) является равновесием Нэша. Другими словами, изменение автоматом Aj (j = 1, . . . , n) действия a∗j на любое aj
при условии, что остальные автоматы не меняют свои действия a∗i ,
(i = 1, . . . , j − 1, j + 1, . . . , n), не приводит к уменьшению суммарной
«помехи» Pj (a∗ ).
Замечание 3. В реальных локально организованных системах действия автоматов ограничены некоторым диапазоном, т. е.
aj (t) ∈ [w−, w+] и допустимым множеством состояний системы является гиперкуб K = [w− , w+]n . В этом случае будем рассматривать следующую модификацию системы (1):
⎧
⎨− ∂Pj (a) ,
∂aj
ȧj =
⎩
0,
если w− < aj < w+;
j = 1, ..., n.
(4)
если aj = w− ∨ aj = w+ ,
При такой модификации системы несложно показать, что траектория
a(t) не выходит за пределы внутри гиперкуба K (при условии, что
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
31
a(0) ∈ K) и устойчивость ее сохраняется. При этом если k компонент
n-мерного вектора a(t) приняли к моменту t значения w− или w+ , то
дальнейшая эволюция системы не выходит за пределы соответствующей (n − k)-мерной грани гиперкуба.
Можно рассматривать поведение автоматов с динамикой (1) или (4)
как некоторую бескоалиционную игру n игроков, стремящихся достигнуть равновесия по Нэшу. Специфика этой игры в том, что в реальных ситуациях функции «проигрыша» P1 (a), P2(a), . . . , Pn (a) автоматам
неизвестны. Автомат Aj располагает лишь локальной информацией о
собственной целевой функции, зная поведение Pj (a) в некоторой малой окрестности точки, в которой находится система. Точнее, Aj в
состоянии оценивать лишь направление убывания Pj (a) по собственной переменной aj .
Рассмотрим эту ситуацию в случае дискретного времени. Повидимому, адекватной реализацией динамической системы (1) будет
следующая итерационная процедура, реализующая т. н. индикаторное
поведение:
∂Pj (at )
t+1
t
t
aj = aj − Δj · sign
,
(5)
∂aj
где Δtj > 0 означает длину шага. Вопрос о выборе параметра Δtj , гарантирующего сходимость процесса (5), требует отдельного изучения.
Ниже приводится конкретная реализация дискретной динамики (5).
Выбор рабочих частот как игра автоматов
В качестве модельной системы коллективного поведения автоматов
рассмотрим группировку радиоэлектронных средств (РЭС), работающих в общем диапазоне радиочастот [w−, w+]. При работе на совпадающих или близких частотах между РЭС возникают взаимные помехи,
приводящие к снижению качества их работы. Задачам оптимального
назначения рабочих частот с целью обеспечения их электромагнитной
совместимости посвящено много работ (см., например, [4] и приведенную там библиографию). В основном в этих работах приводятся алгоритмы централизованного назначения частот, направленные на минимизацию некоторой глобальной целевой функции. Рассмотрим задачу
локального управления (в смысле определения в [1]) этим процессом.
В первом приближении величину помехи, создаваемой передатчиком i-го РЭС на входе приемника j-го РЭС, можно описать убывающей
функцией «частотного разноса» РЭС [4]
αij
,
pij (ai , aj ) =
1 + βij (ai − aj )2
где ai , aj — рабочие частоты РЭС, αij > 0, βij > 0 — значения характеристик i-го и j-го РЭС и их взаимного расположения. Далее будем
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Антонычев, А. А. Короткин
32
предполагать, что матрицы A = [αij ] и B = [βij ] симметричные с нулевой главной диагональю. Принимая (опять же в первом приближении)
гипотезу об аддитивности взаимных помех, мы приходим к рассматриваемой выше модели коллективного поведения автоматов.
Будем считать, что каждый автомат Aj , ассоциированный с j-м
РЭС, в момент времени t = 2, 3, . . . , хранит в памяти четыре величины:
t−1
at−1
и atj , Pjt . Выбор в момент времени t рабочей частоты at+1
j , Pj
j
можно сделать, экстраполируя поведение мощности помехи Pj , как
показано на рис. 2.
Pit-1
Pit-1
Pit
Pit
at-1
i
ati
{
Δt+1
{
Δt+1
at+1
i
ati
( )
( )
Pit-1
Pit-1
Pit
Pit
{
Δt+1
{
Δt+1
at+1
i
at-1
at+1
i
i
at-1
i
ati
( )
at+1
i
ati
at-1
i
()
Рис. 2. Правила выбора рабочей частоты
Такой выбор соответствует концепции локальности информации о
состоянии всей системы у автомата Aj .
Пусть ΔPjt = Pjt − Pjt−1 и Δat = atj − at−1
j . Поскольку выбор частоты
t+1
t
aj определяется знаками величин Δaj и ΔPjt , четыре варианта (а)
– (г) изменения рабочей частоты aj , приведенные на рис. 2, можно
записать в виде следующего разностного уравнения:
at+1
j
)
(
1 t−1
= aj + atj − sign ΔPjt · Δat − Δt · sign ΔPjt · Δat
2
(6)
Очевидно, что на сходимость процесса (6) влияет выбор величины
Δ . Примем в рассматриваемой модели Δt = δ0/t, что соответствует алгоритмам стохастической аппроксимации, в которых на выбор величи
∞
t
t 2
ны шага накладывются условия Δt → 0, ∞
Δ
=
∞,
t=1
t=1 (Δ ) < ∞.
t
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
33
Для иллюстрации поведения дискретной системы (6) приведем результаты компьютерного моделирования для коллектива из трех РЭС
с одинаковым взаимным влиянием во всех «дуэльных» ситуациях, т. е.
для матриц A и B следующего вида:
⎡
⎤
⎡
⎤
0 1 1
0 β β
A = ⎣ 1 0 1 ⎦, B = ⎣ β 0 β ⎦
1 1 0
β β 0
В этом случае
можно провести полный анализ функции энергии
3
P (a(t)) = j=1 Pj (a(t)). При β < 0.5 минимальное значение P (a(t))
достигается, когда две рабочие частоты установлены на одном из концов диапазона [w−, w+], а третья частота — на противопожном конце.
При β > 0.5 минимум достигается, когда две частоты установлены в
противоположных концах, а третья находится в середине диапазона.
В случае β = 0.5 оба варианта дают одинаковое значение минимума.
На рис. 3 – 6 приведена временная динамика изменения рабочих частот aj (t) ∈ [1, 5] и функции энергии P (a(t)) при β = 0.1 и
β = 0.8. Два начальных значения a−1
и a0j выбирались случайным
j
образом внутри отрезка [1, 5]; параметр Δt = 0.5/t. В обоих случаях
наблюдалось прогнозируемое поведение траекторий системы (6).
5
4.5
a3(t)
4
a (t)
1
3.5
3
2.5
2
1.5
a (t)
2
1
0
10
1
10
t
2
10
3
10
Рис. 3. Динамика рабочих частот ai (t) (β = 0.1)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Антонычев, А. А. Короткин
34
6
P=Σ P (at)
5.5
i
i
5
4.5
4
3.5
0
10
1
10
2
3
10
t
10
Рис. 4. Поведение суммарной мощности помех P =
i Pi (a(t))
5
a3(t)
4.5
4
3.5
a2(t)
3
2.5
2
1.5
a (t)
1
1
0
10
1
10
2
10
3
t
10
4
10
Рис. 5. Динамика рабочих частот ai (t) (β = 0.8)
(β=0.1)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
35
5.5
5
4.5
4
3.5
P = Σi Pi(at)
3
2.5
2
1.5
1
0
10
1
10
2
10
3
t
4
10
Рис. 6. Поведение суммарной мощности помех P =
10
i Pi (a(t))
(β=0.8)
Литература
1. Стефанюк В. Л. Локальная организация интеллектуальных систем. М.: ФИЗМАТЛИТ, 2004.
2. Варшавский В. И. Коллективное поведение автоматов. М.: Наука, 1973.
3. Опойцев В. И. Равновесие и устойчивость в моделях коллективного поведения. М.: Наука, 1977. 245 с.
4. Соловьев В. В. Методы оптимального присвоения частот. М.:
Изд-во НПФ «Гейзер», 2000. 133 с.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 517.928
С. Е. Ануфриенко, В. А. Прописнова
Трехкратная волна в кольце
из модифицированных импульсных нейронов
В статье рассматривается кольцо из модифицированных импульсных нейронов. Сформулированы условия существования и определены
характеристики трехкратной волны.
Присутствие в мозге замкнутых структур обнаружено уже давно [1]. На важность роли, которую могут играть кольцевые нейронные
образования в механизмах памяти, указывал Ф. Розенблат [2]. В данной статье описывается периодический режим, получивший название
трехкратная волна.
Для построения нейронного кольца используется модель импульсного нейрона, учитывающая тот факт, что ток ионов натрия во время
генерации спайка регулируется двумя видами ворот: открывающимися
“m”-воротами и закрывающимися “h”-воротами. Уравнение, описывающее динамику мембранного потенциала нейрона, имеет вид [4]:
u̇ = λ[(a − fN1 a (u))fN2 a(u(t − 1)) − 1 + fK (u(t − 1))]u.
(1)
Здесь 0 < a < 1 — константа, fN1 a (u), fN2 a(u), fK (u) — положительные,
достаточно гладкие функции, которые монотонно стремятся к нулю
при u → ∞, fN2 a (0) = 1. Параметр a < 1, поскольку по экспериментальным данным [3] при достаточно больших значениях величина u(t)
экспоненциально убывает. Начало и окончание спайка будем связывать с моментами, когда u(t) пересекает единичное значение соответственно с положительной и отрицательной скоростью.
Введем параметры:
α = a − fN1 a (0) − 1 + fK (0) > 0,
α1 = a − 1 + fK (0) > 1.
Это коэффициенты роста (в логарифмической шкале) на участках медленного и быстрого возрастания u(t).
Обозначим через S класс непрерывных на отрезке [−1, 0] функций
ϕ(s), удовлетворяющих условиям:
ϕ(0) = 1,
0 < ϕ(s) ≤ eαλs/2 .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
37
Следующие асимптотические при λ → ∞ равенства определяют решение уравнения (1) с начальным условием u(s) = ϕ(s) при s ∈ [−1, 0]
[4]:
t ∈ [δ, 1 − δ];
u(t) = eλα1 (t+o(1)) ,
λ(α1 −(t−1)+o(1))
,
t ∈ [1 + δ, T1 + 1 − δ];
u(t) = e
λ(α(t−T1 −1)−1+o(1))
, t ∈ [T1 + 1 + δ, T2 − δ];
u(t) = e
Здесь 0 < δ 1 — малое фиксированное число, через o(1) обозначены
слагаемые, стремящиеся к нулю при λ → ∞,
T1 = α1 + 1 — асимптотическая продолжительность спайка,
T2 = α1 + 2 + 1/α1 — собственный период нейрона.
Рассмотрим однородное кольцо из N нейронов, в котором i-й нейрон связан с (i + 1)-м. При этом (N + 1)-й нейрон отождествляется с
первым, а предшественником первого считается N -й нейрон. В этом
случае система, моделирующая взаимодействие, приобретает вид [4]:
u̇i = λ[(a − fN1 a (ui))fN2 a(ui(t − 1)) − 1 + fK (ui(t − 1))
+ αH(ui )g Θ(ui−1 − 1)]ui,
(2)
i = 1, . . . , N.
Здесь g > 0 — синаптический коэффициент, характеризующий силу
воздействия, H(u) — функционал, обеспечивающий наличие рефрактерного периода. H(u) может быть представлен в следующем виде:
H(u) = Θ(1 − u(t)) · Θ(1 − u(t − (1 − ε)T1)) · Θ(1 − u(t − 2(1 − ε)T1)).
Здесь 0 < ε 1, Θ(s) — функция Хевисайда:
*
1 при s ≥ 0,
Θ(s) =
0 при s < 0.
Функционал H(u) обращается в нуль во время спайка и в течение времени 2(1 − ε)T1 после него. Таким образом, продолжительность рефрактерного периода, включая время спайка, составляет
TR = (3 − 2ε)T1. Это соответствует биологическим данным, согласно
которым 2T1 < TR < 3T1. Будем считать, что период рефрактерности
короче периода собственной активности нейрона: TR < T2.
Предположим, что внешний сигнал со стороны предыдущего нейрона поступает в момент, когда нейрон уже вышел из рефрактерного
состояния, но еще не начал генерировать новый спайк (период восприимчивости). В этом случае величина латентного периода (время
между моментом прихода внешнего воздействия и началом вызванного спайка) определяется по формуле:
Q=
T2 − (tv − t0 )
,
1+g
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
С. Е. Ануфриенко, В. А. Прописнова
38
где tv — начало внешнего воздействия, t0 — начало предыдущего спайка нейрона.
Опишем биологический смысл трехкратной волны. Пусть в нулевой
момент времени начался спайк у первого нейрона. Предположим, что
по каким-либо причинам в тот момент времени, когда первая волна
еще не дошла до N -го нейрона, начался новый спайк первого нейрона,
а спустя некоторое время еще один. В результате по кольцевой структуре вслед за первой побегут вторая и третья волны возбуждения.
Такой режим назовем трехкратной волной.
Обозначим через ξi (i = 2, . . . , N ) интервалы времени между началами спайков соседних нейронов для первой волны на начальном такте
проведения возбуждения, через ηi — запаздывание вторичного спайка
i-го нейрона по отношению к первичному, а через γi — запаздывание
третьего спайка i-го нейрона по отношению к вторичному. Другими
словами, величины
0,
i
ξj (j = 2, . . . , N );
j=2
η1 ,
i
ξj + ηi (j = 2, . . . , N );
j=2
η1 + γ 1 ,
i
ξj + ηi + γi (j = 2, . . . , N )
j=2
задают моменты начала спайков для первой, второй и третьей волн
на начальном такте. При этом должны быть выполнены следующие
условия:
0 < ξi < T1 (i = 2, . . . , N ),
0 < ξi + (ηi − ηi−1) < T1 (i = 2, . . . , N ),
0 < ξi + (ηi − ηi−1) + (γi − γi−1) < T1 (i = 2, . . . , N ),
N
ξj > η1 + γ1 + TR .
j=2
Первое неравенство означает, что спайки соседних нейронов при прохождении первичной волны перекрываются во времени. Второе и третье — то же при прохождении следующих двух волн. Последнее неравенство показывает, что первичная волна подходит к первому нейрону
в тот момент, когда он уже вышел из рефрактерного состояния после генерации третьего спайка. В результате первый нейрон начнет
генерацию нового спайка в момент времени
N
i=2
ξi + ξ1 .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
39
Введем числа ξi (i = 2, . . . , N ), ηi и γi (i = 1, . . . , N ), имеющие тот
же смысл для второго цикла проведения волны возбуждения. Будем
считать, что для них выполнены аналогичные неравенства.
Выведем рекуррентные формулы для ξi , ηi и γi. Из априорных допущений следует, что волна подходит к любому нейрону, когда тот
находится в состоянии восприимчивости. Следовательно, используя
формулу для вычисления латентного периода, получим:
T2 −
N
ξj − η1 − γ1
j=2
ξ1 =
1+g
;
T2 + g(ηN − ξ1 )
;
=
1+g
T2 + g(ηN − ξ1 + γN − η1 )
;
γ1 =
1+g
N
i−1
T2 −
ξj +
ξj − ηi − γi
η1
ξi =
j=i+1
j=1
, i = 2, . . . , N − 1;
1+g
− ξi )
T2 + g(ηi−1
, i = 2, . . . , N − 1;
ηi =
1+g
− ξi + γi−1
− ηi )
T2 + g(ηi−1
, i = 2, . . . , N − 1;
γi =
1+g
−1
N
T2 −
ξj − ηN − γN
ξN
=
j=1
;
1+g
T2 + g(ηN
−1 − ξN )
;
ηN =
1+g
T2 + g(ηN
−1 − ξN + γN −1 − ηN )
.
γN =
1+g
Эти формулы задают отображение в конечномерном пространстве.
Система уравнений имеет стационарное решение:
ξi = ξ 0 =
3T2
,
N + 3g
ηi = η 0 =
T2 N
,
N + 3g
γi = γ 0 =
T2 N
.
N + 3g
Для доказательства устойчивости стационарной точки перепишем
рекуррентные формулы в виде:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
С. Е. Ануфриенко, В. А. Прописнова
40
T2 −
γi+N =
ξj − ηi − γi
j=i+1
ξi+N =
ηi+N =
i+N
−1
, i = 1, . . . , N ;
1+g
T2 + g(ηi+N −1 − ξi+N )
, i = 1, . . . , N ;
1+g
T2 + g(ηi+N −1 − ξi+N + γi+N −1 − ηi+N )
, i = 1, . . . , N.
1+g
Вычислим характеристический полином:
N −1
1
1 1
N
μ +
−
μj
−
1 + g j=1
1+g
1+g
g
g
P (μ) = N
N
μ
μN −1
μ
−
0
1
+
g
1
+
g
g
g
g
μN
(μN − μN −1 ) μN −
μN −1
1+g
1+g
1+g
.
Раскроем определитель:
3 N −1
P (μ) = (1 + g) μ
2
N −2
+ (1 + g) (1 − 2g)μ
3
N −3
+ (1 + g )μ
+
N
−4
μj .
j=1
Домножим обе части равенства на (μ − 1):
(μ − 1)P (μ) = μN −3[(1 + g)μ − g]3 − 1.
Предположим, что у полинома (μ − 1)P (μ) есть корень |μ| ≥ 1, тогда
|(1 + g)μ − g|3 ≤ 1,
g
μ −
≤ 1 .
1 + g 1 + g
Данное неравенство задает на комплексной плоскости круг с центром в точке (g/(1+g), 0) радиуса 1/(1+g). Этот круг полностью лежит
внутри единичной окружности и касается ее при μ = 1. Следовательно, полином (μ − 1)P (μ) имеет число μ = 1 в качестве единственного корня, не лежащего внутри единичной окружности. Заметим, что
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
41
P (1) = N + 3g, поэтому все корни полинома P (μ) удовлетворяют неравенству μ < 1. Это означает, что стационарное решение асимптотически устойчиво.
Для предельных значений ξ 0 , η 0 , γ 0 должны выполняться те же
ограничения, что и для ξi , ηi и γi. Из неравенства ξ 0 < T1 получим
3T2 − N T1
,
3T1
из неравенства (N − 1)ξ 0 > η 0 + γ 0 + TR вытекает
g>
(N − 3)T2 − N TR
.
3TR
Из условия совместности ограничений получаем:
g<
N −3>
3TR
> 6.
T1
Здесь учтено, что TR > 2T1. Следовательно, для существования трехкратной волны кольцо должно содержать не менее 10 нейронов.
Таким образом, при выполнении всех необходимых условий система (2) имеет аттрактор, состоящий из трех волн, бегущих друг за
другом. Временные промежутки между спайками соседних нейронов
асимптотически близки к ξ 0, вторая волна запаздывает по отношению
к первой на время, асимптотически близкое к η 0 , третья по отношению
ко второй — на γ 0.
Литература
1. Экклс Дж. Физиология синапсов. М.: Мир, 1966.
2. Rosenblatt F. The perceptron: a probabilistic model for information
storage and organization in the brain // Psychological Review. 1958.
№65. P. 386–408.
3. Hodgkin A., Huxley A. A quantitative description of membranew
current and its application to conduction and excitation in nerve //
J. Physiol. 1952. №117. P. 500–544.
4. Майоров В. В., Ануфриенко С. Е. Исследование модифицированной модели сальтаторного проведения возбуждения // Моделирование и анализ информационных систем. 2007. T. 14, №4. C. 3–6.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 517.9
Н. Д. Быкова
Критический случай наибольшего вырождения
в задаче с двумя запаздываниями
Изучается обобщенное уравнение Хатчинсона с двумя запаздываниями. Анализируются фазовые перестройки, происходящие с построенной нормальной формой при изменении параметров. Показано, что в
рассматриваемом случае потеря устойчивости нетривиального состояния равновесия исследуемой задачи происходит с возникновением либо
одного, либо двух сосуществующих предельных циклов.
Рассмотрим обобщенное уравнение Хатчинсона с двумя запаздываниями
(
)
aN (t − h1 ) + bN (t − h2 )
Ṅ = r 1 −
N.
k
В этом уравнении N (t) — численность популяции, r — мальтузианский
коэффициент линейного роста, k — средняя численность популяции,
a, b — весовые коэффициенты, определяющие вклад каждой из возрастных групп N (t − h1 ), N (t − h2 ) в воспроизводство популяции. Все
параметры будем считать положительными, кроме того, a + b = 1 и
h1 > h2 .
Сделав замены th1 → t и N/k → N , получим задачу более простого
вида, которую и будем изучать
Ṅ = r [1 − aN (t − 1) − (1 − a)N (t − h)] N,
(1)
где h = h2 /h1 < 1 и rh1 обозначено за r.
Уравнение (1) имеет два состояния равновесия N = 0 и N = 1. Первое из них всегда неустойчиво, поэтому будем рассматривать только
второе.
Характеристический квазимногочлен задачи (1) имеет вид
P (λ) ≡ λ + r(ae−λ + (1 − a)e−λh ).
(2)
Для задачи, линеаризованной на рассматриваемом состоянии равновесия, в [1] доказано следующее утверждение.
Теорема. 1. Пусть параметр h > 0 достаточно мал, тогда существует счетное число таких значений ak (h), rk (h), k = 1, 2, . . ., что при
a = ak (h) и r < rk (h) корни характеристического квазимногочлена (2)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
43
лежат в левой комплексной полуплоскости, а при r = rk (h) две пары
корней ±iω1 (h), ±iω2(h) выходят на мнимую ось. Кроме того, имеют
место асимптотические формулы:
1 π2
ak (h) = − (2k + 1)2(2k + 3)2h4 + O(h5 ),
2 ( 12
)
π2
1
2
2
3
rk (h) =
1 + (4k + 8k + 5)h + O(h ) .
h
3
В статье [1] была подробно изучена первая кривая, мы же будем
изучать вторую кривую a2 (h).
Выясним, когда две пары корней ±iω1(h), ±iω2(h) квазимногочлена (2) выходят на мнимую ось. Для этого подставим в (2) λ = iω и
получим систему уравнений
(1 − a) cos ωh + a cos ω = 0,
ω
r(ω) =
.
(1 − a) sin ωh + a sin ω
Для того чтобы на мнимой оси было две пары корней, необходимо
(1 − a) cos ω1h + a cos ω1 = 0,
(1 − a) cos ω2h + a cos ω2 = 0,
ω1
ω2
r(ω1) =
= r(ω2) =
.
(1 − a) sin ω1h + a sin ω1
(1 − a) sin ω2h + a sin ω2
(3)
Как оказалось, кривые a = ak (h) прерываются при h > 0. Для
отыскания крайних точек необходимо дополнить (3) уравнением
(1 − a)h sin ω1 h + a sin ω1 = 0.
(4)
Решая систему (3), (4) численно, можно найти точку
(h, a) ≈ (0.1359, 0.2001), в которой прерывается вторая кривая. Учитывая, что, согласно теореме 1, при h, стремящемся к нулю, a стремится
к 1/2, получаем, что другой крайней точкой рассматриваемой кривой
является точка (h, a) = (0, 0.5). Используя это и систему (3), кривая
a2 (h) была численно построена, и ее график в плоскости параметров
a, h имеет вид, изображенный на рис. 1.
Пусть параметры a0 и h0 лежат на рассматриваемой кривой, тогда
можно найти соответствующее им значение r0 = r2(h), при котором
характеристический квазимногочлен задачи (1) имеет две пары корней
±iw1, ±iw2.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Н. Д. Быкова
44
a
0.5
0.4
0.3
0.2
0.1
0.02 0.04 0.06 0.08 0.10 0.12
h
Рис. 1. Кривая a2 (h)
Для выяснения фазовых перестроек, происходящих при изменении
параметра r вблизи критического значения r2(h), предполагаем, что
r = r2(h) + ε, и при достаточно малых ε в (1) выполняем замену
√
N (t) = 1 + ε(z1 (s) exp (iω1t) + z̄1 (s) exp (−iω1t) + z2 (s) exp (iω2t)+
+ z̄2 (s) exp (−iω2t)) + εu1(t, s) + ε3/2u2 (t, s) + . . . ,
√
где s = εt. Приравнивая коэффициенты при одинаковых степенях ε,
на третьем шаге из условий разрешимости соответствующей задачи
в классе тригонометрических функций, согласно [1], получаем укороченную нормальную форму следующего вида
z1 = Φ1z1 + (A11z12 + A12z22 )z1 ,
z2 = Φ2z2 + (A21z12 + A22z22 )z2 ,
(5)
где параметры вычисляются по формулам
iwj
,
(iw )
r
P
0
j
(wj − wk )wj
1
(w1 + w2)wj
Ajk = − 2iwj +
+
,
P (iwj )
P
(i(w
+
w
))
P
(i(w
−
w
))
1
2
j
k
wj2
1
iwj +
, j, k = 1, 2, j = k.
Ajj = − P (iwj )
P (2iwj )
Φj =
После полярной замены zj = ξj exp(iτj ), j = 1, 2 вместо системы
(5) получаем четыре уравнения для ξj и τi, i, j = 1, 2. Причем уравнения для ξ1 , ξ2 не зависят от уравнений для τ1 , τ2, поэтому будем
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
45
рассматривать систему только для амплитудных переменных:
ξ˙1 = ϕ1 ξ1 + (a11ξ12 + a12ξ22 )ξ1,
ξ˙2 = ϕ2 ξ2 + (a21ξ12 + a22ξ22 )ξ2,
(6)
где ϕj = Re Φj , ajk = Re Ajk , j, k = 1, 2.
Для состояний равновесия системы (6) выполнена следующая теорема о соответствии.
Теорема. 2. Пусть система (6) имеет состояние равновесия (ξ1∗ , ξ2∗)
экспоненциально асимптотически устойчивое или дихотомичное, тогда найдется такое ε0, что для всех ε из промежутка (0, ε0) исходная
задача имеет:
• состояние равновесия, если ξ1∗ = ξ2∗ = 0,
• цикл, если одна из величин ξ1∗, ξ2∗ обращается в нуль,
• тор, если ξ1∗ и ξ2∗ одновременно не равны нулю,
которые имеют ту же устойчивость.
Учитывая сформулированную теорему, перейдем к исследованию
состояний равновесия нормальной формы и их устойчивости.
Сначала численно найдем коэффициенты системы (6) (их зависимости от h изображены на рис. 2) и выясним, при каких условиях она
является диссипативной.
Необходимым условием диссипативности является отрицательность a11(h) и a22(h). Если дополнительно одна из величин a12(h),
a21(h) отрицательна, то система диссипативна. Таким образом, согласно рис. 2, нормальная форма диссипативна на всем рассматриваемом
промежутке изменения h при выполнении условия a11(h) < 0.
В зависимости от параметров система (6) может иметь четыре состояния равновесия:
+ +
+
+
Δ1
Δ2
ϕ2
ϕ1
(0, 0), 0, −
,
,
,
− ,0 ,
a22
a11
Δ
Δ
где Δ = a11 a22 − a12 a21, Δ1 = −ϕ1 a22 + ϕ2a12 , Δ2 = −ϕ2a11 + ϕ1a21 .
Условиями существования второго и третьего состояния равновесия
является отрицательность величин aϕ222 и aϕ111 соответственно, последнее
Δ
же состояние равновесия существует, если Δj > 0, j = 1, 2. Из приведенных на рис. 3 графиков видно, что при 0 < h < h1 система (6)
имеет все четыре состояния равновесия, при h1 < h < h3 — первые
три, а при h > h3 — только первое и второе.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Н. Д. Быкова
46
0.4
a12
a11
0.2
h
0.0
-
0.2
-
0.4
0.00
a21
a22
0.02
0.04
0.06
0.08
0.10
0.12
0.14
Рис. 2. Зависимости коэффициентов нормальной формы от h
Рис. 3. Графики величин Δ, a11 , a12 ,
Δ1 Δ2
, Δ
Δ
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
47
Рассмотрим вопрос об устойчивости состояний равновесия.
Вычисления показали, что ϕ1 > 0 и ϕ2 > 0 на всем рассматриваемом промежутке изменения h. В силу этого тривиальное состояние
равновесия всегда неустойчиво.
Линеаризуем задачу (6) на втором состоянии равновесия
Δ1
0
− a22
u
u̇
.
=
v
v̇
0 −2ϕ2
Отсюда видно, что его устойчивость зависит только от знака Δ1 (в
силу отрицательности a22).
Аналогично, устойчивость третьего состояния равновесия зависит
от знака величины aΔ112 . При этом, в силу условий его существования и
положительности ϕ1 , получаем, что это состояние равновесия устойчиво при Δ2 < 0.
Теперь рассмотрим матрицу линейной части системы для последнего состояния равновесия
√
Δ1 Δ2
Δ1
2a11
2a12 Δ
√ Δ
Δ1 Δ2
2a21 Δ
2a22 ΔΔ2 .
Чтобы определить его устойчивость на области существования, выпишем характеристическое уравнение
Δ
Δ2 Δ1 Δ2
1
2
+ a22
λ+4
= 0.
λ − 2 a11
Δ
Δ
Δ
Как видно из риc. 3, коэффициент при λ положителен, а свободный
член отрицателен. Это значит, что уравнение имеет два действительных корня разных знаков и рассматриваемое состояние равновесия —
седло.
Опишем устойчивость всех состояний равновесия в зависимости от
параметра h.
Пусть 0 < h < h1 . На этом интервале сосуществуют все состояния
равновесия. Причем величины Δ1 и Δ2 отрицательны, таким образом,
второе и третье состояния равновесия устойчивы, а четвертое неустойчиво. В силу этого фазовый портрет исследуемой нормальной формы
имеет вид, изображенный на рис. 4. Таким образом, согласно теореме о соответствии, у исходной системы сосуществуют два устойчивых
цикла и неустойчивый тор.
Далее рассмотрим интервал h1 < h < h3 . На этом промежутке
существуют только два нетривиальных состояния равновесия: второе
и третье. Очевидно, что при таких h величина Δ1 является положительной, а Δ2 — отрицательной, поэтому второе состояние равновесия
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Н. Д. Быкова
48
Рис. 4.
Рис. 5.
Рис. 6.
неустойчиво, а третье устойчиво. Фазовый портрет нормальной формы
на этом промежутке имеет вид, изображенный на рис. 5. У исходной
системы сосуществуют устойчивый и неустойчивый циклы.
И наконец, рассмотрим участок h > h3 , где задача (6) недиссипативна. Здесь есть только одно нетривиальное состояние равновесия —
расположенное на оси ξ2 , являющееся неустойчивым. Эскиз фазового портрета изображен на рис. 6. Отметим, что возмущения системы,
нормальная форма которой оказывается недиссипативной, и характер
устойчивости режимов ветвящихся от состояния равновесия определить не удается.
Суммируя, отметим, что потеря устойчивости ненулевого состояния
равновесия задачи (1) происходит с возникновением либо одного, либо
двух сосуществующих устойчивых предельных циклов.
Литература
1. Глызин С. Д. Учет возрастных групп в уравнении Хатчинсона //
Моделирование и анализ информационных систем. 2007. Т.14,
№3. С. 29–42.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 517.9
А А. Кащенко
Исследование устойчивости решений вида
бегущих волн в уравнении Гинзбурга–Ландау
с малой диффузией 1
В работе исследуется устойчивость бегущих волн в зависимости от
значений параметров. Найдены необходимые условия неустойчивости и
достаточные условия устойчивости бегущих волн.
Введение
Уравнение Гинзбурга–Ландау возникает при описании большого
класса волновых явлений в пространственно распределенных системах [1, 2].
Известно, что динамика уравнения Гинзбурга–Ландау может быть
достаточно сложной [3], однако большинство результатов о поведении
решений этого уравнения получены численно.
В настоящей работе аналитически будут получены необходимые и
достаточные условия устойчивости решений вида бегущих волн для
уравнения Гинзбурга–Ландау с малой диффузией.
1. Постановка задачи
Рассмотрим уравнение Гинзбурга-Ландау с малой диффузией
u̇ = u(1 − (1 + ib)|u|2) + ε2(1 + id)u
(1)
с периодическими краевыми условиями
u(t, x + 2π) ≡ u(t, x).
(2)
Здесь u — комплекснозначная функция, ε — малый положительный
параметр, точкой обозначена производная по t, а штрихом — по x.
Краевая задача (1), (2) имеет набор решений вида бегущих волн“:
”
uk = ρk eiωk t+ikx , где
ρk = 1 − ε2k 2 , ωk = −b(1 − ε2k 2 ) − ε2dk 2,
k — целое. Поставим задачу исследования устойчивости бегущих волн
при достаточно малых значениях параметра ε.
1
Работа выполнена при финансовой поддержке целевой программы «Научные и научнопедагогические кадры инновационной России» (государственные контракты № 14.740.11.0873 и
№ П2223).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Кащенко
50
2. Построение семейства характеристических многочленов
Хорошо известно, что для параболических уравнений работает теорема Ляпунова об устойчивости решений по первому приближению,
поэтому будем исследовать линеаризованную на бегущей волне краевую задачу.
Для удобства изучения устойчивости найденных решений в уравнении (1) сделаем замену u = uk (1+v), где v = v1 +iv2. После сокращения
на uk получим уравнение на v1 и v2:
iωk (1 + v1 + iv2) + v˙1 + iv˙2 = (1 + v1 + iv2)[1 − (1 + ib)ρ2k (1 + 2v1+
+v12 + v22 )] + ε2(1 + id)[−k 2(1 + v1 + iv2) + 2ik(v1 + iv2 ) + v1 + iv2],
v2(t, x + 2π) ≡ v2(t, x).
v1 (t, x + 2π) ≡ v1(t, x),
(3)
Устойчивость uk в уравнении (1) эквивалентна устойчивости нулевого
решения в уравнении (3). Для изучения устойчивости нулевого решения уравнения (3) линеаризуем его в окрестности нуля, выделив
действительную и мнимую части, получим систему:
v˙1 = −2(1 − ε2 k 2)v1 − 2ε2dkv1 + ε2 v1 − 2ε2kv2 − ε2dv2 ,
v˙2 = −2b(1 − ε2k 2 )v1 + 2ε2kv1 + ε2 dv1 − 2ε2dkv2 + ε2 v2,
v1(t, x + 2π) ≡ v1(t, x),
v2(t, x + 2π) ≡ v2 (t, x).
(4)
Благодаря выполненной замене, получившаяся система (4) автономна. Поэтому будем искать решения системы (4) в виде решений
Эйлера v1(t, x) = eλt v10(x), v2 (t, x) = eλt v20(x). Т. к. v10 и v20
2π-периодические и дважды дифференцируемые функции,
∞ то они
inx
представимы
в виде сходящихся рядов Фурье: v10 =
,
n=−∞ pn e
∞
inx
v20 = n=−∞ qn e .
Таким образом, для каждого целого n получим характеристическое
уравнение на собственное значение λ = λ(n) и на собственный вектор
с компонентами (pn, qn):
pn
pn
A
=λ
,
qn
qn
где
A=
−2ε2dkin − ε2n2 − 2(1 − ε2 k 2) −2ε2kin + ε2dn2
+2ε2kin − ε2dn2 − 2b(1 − ε2 k 2) −2ε2dkin − ε2 n2
.
Отсюда получаем счетное семейство характеристических полиномов
(при каждом целом n имеем характеристический полином):
λ2 + 2λ(2ε2dkin + ε2 n2 + 1 − ε2 k 2) + (d2 + 1)ε2n2(ε2n2 − 4ε2k 2)+
+2(1 − ε2k 2 )((bd + 1)ε2n2 + 2(d − b)ε2kni) = 0.
(5)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
51
В силу того что мы изучаем устойчивость периодического решения
уравнения (1), уравнение (5) имеет корень λ = 0 при n = 0.
Для каждого номера волны k будем исследовать расположение корней уравнения (5) при всех целых ненулевых значениях n. Если окажется, что при всех ненулевых n все корни характеристического уравнения (5) лежат в левой полуплоскости, то это будет означать устойчивость k-й волны; если же при каком-нибудь целом n найдется корень
уравнения (5) в правой полуплоскости, то k-я волна неустойчива.
3. Исследование расположения корней уравнения (5)
3.1. Получение достаточных условий неустойчивости
Рассмотрим случай асимптотически больших номеров волн. Пусть
z — произвольное фиксированное число из объединения интервалов
(−1, 1)\{0}. Представим k в виде k = z/ε + θz + k1 , где θz из полуинтервала [0,1) и дополняет z/ε до целого, k1 — целое число.
Уравнение (5) тогда принимает вид
λ2 + 2λ[2εdin(z + ε(θz + k1 )) + 1 − z 2 − 2zε(θz + k1 ) + O(ε2 )]+
+2(1 − z 2 − 2zε(θz + k1 ))[(bd + 1)ε2n2 + 2(d − b)εni(z + ε(θz + k1 ))]−
−4(d2 + 1)ε2n2 z 2 + o(ε2 ) = 0.
(6)
Пусть θz — фиксированный параметр. Тогда корни уравнения (6) зависят от ε регулярно. Исследуем их расположение. При ε = 0 и любом
n есть корень λ = 0, поэтому при ненулевых ε разложим корень λ по
степеням ε : λ = ελ1 + ε2λ2 + O(ε3 ), где λ1 и λ2 — комплексные числа.
Приравняем коэффициенты уравнения (6) при одинаковых степенях
ε. Из выражения при ε1 найдем значение λ1 :
λ1 = 2(b − d)niz.
(7)
Пользуясь (7), из выражения при ε2 найдем действительную часть λ2 :
Re λ2 = −(bd + 1)n2 +
2z 2 (b2 + 1)n2
1 − z2
Заметим, что λ1 и Re λ2 от θz не зависят, поэтому при θz = θz (ε) асимптотика получается равномерной по θz из отрезка [0,1], и проведенные
выше вычисления правомерны.
При условии bd + 1 < 0 при любом z из интервала (-1,1) Re λ2 будет
положительной. Если же bd + 1 > 0, то действительная часть λ2 будет
положительной при
+
bd + 1
= z2 < |z| < 1.
2b2 + bd + 3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Кащенко
52
Из вышесказанного следует, что справедливы следующие теоремы.
Теорема. 1. Пусть z ∈ (−1, 1) — произвольное фиксированное число.
Пусть выполнено неравенство bd + 1 < 0. Тогда при всех достаточно
малых ε бегущая волна Uz,k1 (t, x) неустойчива.
Теорема. 2. Пусть z ∈ (−1, −z2) ∪ (z2, 1) — произвольное фиксированное число. Пусть выполнено неравенство bd + 1 > 0. Тогда при всех
достаточно малых ε бегущая волна Uz,k1 (t, x) неустойчива.
Здесь и далее
Uz,k1 (t, x)=uz/ε+θz +k1 (t, x) = 1−(z+ε(θz +k1 ))2 exp(i(z/ε + θz + k1)x)×
× exp (i(−b + (b − d)(z + ε(θz + k1 ))2)t).
3.2. Получение достаточных условий устойчивости
Везде далее считаем, что bd + 1 > 0.
В уравнении (5) введем обозначения. Пусть εk = z, εn = m. Отметим, что из условия неотрицательности ρk имеем |z| < 1. Тогда
получим уравнение
λ2 + 2λ(2dizm + m2 + 1 − z 2 ) + (d2 + 1)m2(m2 − 4z 2 )+
+2(1 − z 2 )((bd + 1)m2 + 2(d − b)izm) = 0.
(8)
В новых терминах нас интересует расположение корней (8) в зависимости от z при каждом ненулевом m. В пункте 3.1. было доказано,
что при |z| > z2 наблюдается неустойчивость, поэтому нас будут интересовать только значения |z| < z2 . Будем искать корни уравнения
(8) в виде λ = a + ic. Подставляя это соотношение в уравнение (8),
получим:
2a + a2 + 2ic + 2iac − c2 + 2m2 +2am2 +2icm2 +2bdm2+m4 +d2m4 −
−4ibmz + 4idmz + 4iadmz − 4cdmz−2az 2 −2icz 2 −6m2 z 2 −2bdm2z 2 −
−4d2m2 z 2 + 4ibmz 3 − 4idmz 3 = 0.
Выделим действительную и мнимую части уравнения. Действительная
часть:
2a + a2 − c2 + 2m2 + 2am2 + 2bdm2 + m4 + d2m4 − 4cdmz−
−2az 2 − 6m2 z 2 − 2bdm2z 2 − 4d2m2 z 2 = 0,
мнимая:
2c + 2ac + 2cm2 − 4bmz + 4dmz + 4admz − 2cz 2 + 4bmz 3 − 4dmz 3 = 0.
Нас будет интересовать только действительная часть λ, поэтому выразим c через a.
−2mz(−b + d + ad + bz 2 − dz 2 ) = c(1 + a + m2 − z 2 ).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
53
Заметим, что случай равенства нулю выражения 1 + a + m2 − z 2 нам
неинтересен, т. к. мы получаем, что a = −1+z 2 −m2 , что при любом m
и любом |z| < 1 отрицательно. Поэтому считаем, что 1 + a + m2 − z 2 =
0, тогда подставим выражение для c в действительную часть уравнения
(8), получим:
(1 + a + m2 − z 2 )−2[2(1 − z 2 )2(1 + bd − (3 + 2b2 + bd)z 2 )m2+
+(1 − z 2 )(5 + 4bd + d2 − (13 + 12bd + d2)z 2 )m4 + (1 + d2 )m8+
+2(2 + bd + d2 − (4 + bd + 3d2)z 2 )m6 + a4 + 4(m2 + 1 − z 2 )a3 +
+[5(m2+1−z 2 )2 +4d2z 2 m2 +m2 ((d2+1)(m2−4z 2 )+2(1−z 2 )(1+bd))]a2+
+[(m2+1−z 2 )2+4d2z 2 m2 +m2 ((d2+1)(m2−4z 2 )+2(1−z 2 )(1+bd))]×
×2(m2 + 1 − z 2 )a] = 0.
(9)
В получившемся уравнении нас интересуют только действительные
корни, т. к. по смыслу задачи a — действительная часть λ, корня уравнения (8). Заметим, что если при фиксированном z и всех ненулевых
значениях m коэффициенты при всех степенях a будут положительны,
то уравнение (9) не будет иметь неотрицательных корней.
Лемма. 1. Пусть |z| < z2 . Тогда коэффициенты при a1 и a2 уравнения
(9) положительны.
Доказательство.
Докажем, что при |z| < z2 выражение
(m2 + 1 − z 2)2 + 4d2z 2 m2 + m2 ((d2 + 1)(m2 − 4z 2 ) + 2(1 − z 2)(1 + bd)) (10)
положительно. Преобразуем (10):
(m2 + 1 − z 2 )2 + 4d2z 2 m2 + m2 ((d2 + 1)(m2 − 4z 2 ) + 2(1 − z 2 )(1 + bd))=
= 1 + 2(2 + bd)m2 + (2 + d2 )m4 − 2(1 + 4m2 + bdm2 )z 2 + z 4 .
В результате замены z 2 = t получим квадратный трехчлен относительно t:
f (t) = 1 + 2(2 + bd)m2 + (2 + d2)m4 − 2(1 + 4m2 + bdm2 )t + t2 .
Докажем, что при t < z22 значения f (t) положительны. Заметим, что
значение выражения f (t) в точке z22 = (bd + 1)/(2b2 + bd + 3) равно
(3 + 2b2 + bd)−2[2(1 + bd)m2(2 + 10b2 + 4b4 + m2 (3 + 2b2)(d2 + 2))+
4(1 + b2)2 + 4m2 (2 + 3b2 + 2b4 + b4 d2) + m4 (2+d2 )(3+8b2+4b4+b2 d2)],
что больше нуля в силу предположения bd + 1 > 0. Графиком функции
f (t) является парабола, ветви которой направлены вверх. Абсцисса
вершины данной параболы равна 1 + 4m2 + bdm2 , что больше единицы,
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. А. Кащенко
54
следовательно, больше z22 . Мы доказали, что у параболы f (t), ветви
которой направлены вверх, абсцисса вершины правее z22 , а в точке z22
ордината положительна. Исходя из этого, получаем, что при всех z
из интервала (−z2 , z2) выражение (10) положительно, следовательно,
коэффициенты при a1 и a2 в уравнении (9) положительны.
Коэффициенты при a4 и a3 в уравнении (9) положительны при любом ненулевом m и |z| < 1. При |z| < z0 = min{z2, z4 , z6}, где
+
+
5 + 4bd + d2
2 + bd + d2
z4 =
,
z
=
,
6
13 + 12bd + d2
4 + bd + 3d2
коэффициент при a0 уравнения (9) положителен при любом ненулевом
значении m.
Теорема. 3. Пусть выполнено неравенство bd + 1 > 0. Пусть
z ∈ (−z0 , z0) — произвольное фиксированное число. Тогда при всех
достаточно малых ε бегущая волна uz/ε устойчива.
Рассмотрим разности z42 − z22 и z62 − z22 .
z42 −z22 =
2((1+d2 )(1+b2 )+4(1+bd)b(b−d))
5+4bd+d2
1+bd
=
−
13+12bd+d2 3+2b2+bd
(3+2b2+bd)(13+12bd+d2 )
2((1+d2 )(1+b2 )+(1+bd)(b2−d2 ))
2+bd+d2
1+bd
=
−
4+bd+3d2 3+2b2+bd
(3+2b2+bd)(4+bd+3d2)
Заметим, что при дополнительном условии |b| ≥ |d| наименьшим из
чисел z2 , z4 , z6 является z2 . Как следствие, имеем следующую теорему.
Теорема. 4. Пусть bd + 1 > 0 и |b| ≥ |d|. Тогда при всех достаточно
малых ε бегущая волна uz/ε устойчива, если |z| < z2 , и неустойчива,
если z2 < |z| < 1.
Выводы
Относительно устойчивости по Ляпунову решений уравнения (1),
(2) вида бегущих волн получены следующие результаты.
1. При выполнении неравенства bd+1 < 0 неустойчивы все бегущие
волны.
2. При выполнении системы неравенств bd + 1 > 0, |b| < |d| бегущие волны uz/ε при |z| < z0 устойчивы, а при |z| > z2 неустойчивы.
3. При выполнении системы неравенств bd + 1 > 0, |b| ≥ |d| выражение z2 является критическим значением, в том смысле, что при
|z| < z2 наблюдается устойчивость, а при |z| > z2 — неустойчивость.
z62 −z22 =
Литература
1. Гинзбург В. И., Ландау Л. Д. К теории сверхпроводимости //
ЖЭТФ. 1950. Т. 20. С. 1064.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
55
2. Кудряшов Н. А. Методы нелинейной математической физики:
учеб. пособие. Долгопрудный: Издательский дом «Интеллект»,
2010.
3. Ахромеева Т. С. и др. Нестационарные структуры и диффузионный хаос. М.: Наука, 1992.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 517.928
И. И. Коновалов
О существовании интегрируемых с квадратом
решений одномерного уравнения Шредингера
с параметром
В работе изучается вопрос о существовании интегрируемых с квадратом решений одномерного уравнения Шредингера c колебательно
убывающим потенциалом при различных значениях спектрального параметра. Исследование проводилось при помощи специальной теории
усреднения с использованием известных результатов теории асимптотического интегрирования.
1. Постановка задачи. Цель работы состоит в определении условий,
а также значений параметра λ > 0, при которых существуют решения
y(t) из класса L2[t∗ , ∞) у одномерного уравнения Шредингера
ÿ + (λ − q(t))y = 0,
(1)
с потенциалами
q(t) =
и
P (t)
,
tα
(2)
P (t) Q(t)
+ β ,
(3)
tα
t
где α и β ∈ (0, 1], а P (t) и Q(t) суть тригонометрические многочлены
q(t) =
P (t) =
Q(t) =
N
−N
N
cj eiωj t ,
(4)
dj eiνj t .
−N
Мы предполагаем, что функции P (t) и Q(t) действительнозначны и,
следовательно,
∀j c¯j = c−j , ω−j = −ωj ,
∀j d¯j = d−j , ν−j = −νj
(5)
Сначала мы рассмотрим задачу (1), (2), некоторые результаты
исследования которой впоследствии можно будет распространить на
(1), (3). Исследование обеих задач будем проводить при помощи теории усреднения, краткое изложение которой представим ниже.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
2. Вспомогательные сведения.
дифференциальных уравнений:
57
Рассмотрим следующую систему
dx = Λ(t) + R(t) x,
dt
(6)
где x(t) — комплекснозначный вектор размерности m,
Λ(t) = diag λ1 (t), . . . , λm (t)
— непрерывная диагональная матрица, а R(t) ∈ L1[t0, ∞). Последняя
запись означает, что матрица R(t) абсолютно интегрируема, т. е. существует конечный интеграл (вообще говоря, лебегов)
∞
R(t)dt.
t0
Определение. Системы вида (6) называют L-диагональными.
Потребуем далее, чтобы для элементов матрицы Λ(t) были выполнены следующие условия, известные как условия дихотомии: пусть
для каждой пары индексов (i, j) имеет место либо
t2
Re λi (s) − λj (s) ds ≤ K1,
t2 ≥ t1 ≥ t0 ,
(7)
Re λi (s) − λj (s) ds ≥ K2,
t2 ≥ t1 ≥ t0 ,
(8)
t1
либо
t2
t1
где K1, K2 — некоторые постоянные.
Теперь мы можем сформулировать теорему Левинсона (см., например, [1–3]).
Теорема 1 (Левинсон). Пусть выполнены условия дихотомии (7),
(8). Тогда фундаментальная матрица X(t) L-диагональной системы (6) допускает следующее асимптотическое представление при
t → ∞:
, t
X(t) = I + o(1) exp
Λ(s)ds ,
t∗ ≥ t0 .
(9)
t∗
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
58
Теорема Левинсона дает нам возможность построить асимптотику, однако исходную задачу (1) сперва необходимо привести к Lдиагональному виду. Для этого нам потребуется теорема об усреднении линейных систем с колебательно убывающими коэффициентами.
Определение. Классом Σ назовем множество матриц, элементами
которых являются тригонометрические многочлены. Кроме того, если
матрица A(t) из класса Σ имеет нулевое среднее значение, т. е.
1
M A(t) = lim
T →∞ T
T
A(t)dt = 0,
0
мы будем писать, что A(t) ∈ Σ0.
Рассмотрим систему
n
dx = A0 +
Ai(t)vi(t) +
Ai1 i2 (t)vi1 (t)vi2 (t) + . . . +
dt
i=1
1≤i1 ≤i2 ≤n
+
Ai1... ik (t)vi1 (t) · . . . · vik (t) + R(t) x,
x ∈ Cm . (10)
1≤i1 ≤...≤ik ≤n
Здесь A0, Ai1 ... il (t), R(t) — квадратные m × m-матрицы, а
v1(t), . . . , vn(t) — скалярные функции. Пусть
10 . A0 — постоянная матрица с вещественными собственными значениями.
20 . v1 (t) → 0, v2(t) → 0, . . . , vn(t) → 0 при t → ∞.
30 . v̇1 (t), v̇2(t), . . . , v̇n(t) ∈ L1 [t0, ∞).
40 . Произведение vi1 (t)vi2 (t) . . . vik+1 (t) ∈ L1[t0 , ∞) для любого набора 1 ≤ i1 ≤ i2 ≤ . . . ≤ ik+1 ≤ n.
50 . Матрицы Ai1... il (t) принадлежат классу Σ.
60 . Матрица R(t) ∈ L1[t0, ∞).
При сформулированных выше условиях справедлива следующая
теорема (см. [4, 5]).
Теорема 2. Система (10) при достаточно больших t заменой
n
x= I+
Yi (t)vi(t) +
i=1
Yi1 i2 (t)vi1 (t)vi2 (t) + . . . +
1≤i1 ≤i2 ≤n
+
1≤i1 ≤...≤ik ≤n
Yi1 ... ik (t)vi1 (t) · . . . · vik (t) y, (11)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
59
где I — единичная матрица, а матрицы Yi1 ... il (t) принадлежат классу Σ0, приводится к виду
n
dy = A0 +
Aivi (t) +
Ai1i2 vi1 (t)vi2 (t) + . . . +
dt
i=1
1≤i1 ≤i2 ≤n
Ai1... ik vi1 (t) · . . . · vik (t) + R1 (t) y (12)
+
1≤i1≤...≤ik ≤n
с постоянными матрицами Ai1 ... il и матрицей R1 (t) ∈ L1[t0, ∞).
Нам в дальнейшем потребуются явные формулы для постоянных
матриц Ai1 ... il в некоторых частных случаях. Имеем
Aκ(j) = M
j−1
Aκ(j−l)(t)Yκ(l)(t) ,
j = 1, . . . , k,
(13)
l=0
где κ(j) есть символьная функция, повторяющая символ κ в точности
j раз:
κ(j) = κ
. . κ1,
. ./0
κ = 1, . . . , n,
j
κ(0) = 0,
например, 5(3) = 555. Кроме того,
Aij = M Aij (t) + Ai(t)Yj (t) + Aj (t)Yi(t) ,
1 ≤ i < j ≤ n,
(14)
а матрицы Yκ(j) из класса Σ0 определяются из уравнения
Ẏκ(j) (t) − A0Yκ(j) (t) + Yκ(j) (t)A0 =
j−1
Aκ(j−l) (t)Yκ(l)(t) −
l=0
j−1
l=0
Yκ(l) (t)Aκ(j−l),
(15)
где j = 1, . . . , k и κ = 1, 2, . . . , n.
Нам потребуется несколько вспомогательных утверждений (см.
[4]).
Утверждение 1. Если все собственные числа матрицы A0 различны и она имеет канонический вид A0 = Λ0 , то система (12) при
достаточно больших t с помощью замены
y= I+
n
i=1
Civi (t) +
Ci1i2 vi1 (t)vi2 (t) + . . . +
1≤i1 ≤i2 ≤n
+
1≤i1 ≤...≤ik ≤n
Ci1... ik vi1 (t) · . . . · vik (t) z, (16)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
60
где Ci1 ... il — постоянные матрицы, приводится к L-диагональному
виду
n
dz = Λ0 +
Λi vi(t) +
Λi1 i2 vi1 (t)vi2 (t) + . . . +
dt
i=1
1≤i1 ≤i2 ≤n
+
Λi1 ... ik vi1 (t) · . . . · vik (t) + R2(t) z. (17)
1≤i1 ≤...≤ik ≤n
В системе (17) Λi1 ... il — постоянные диагональные матрицы и
R2(t) ∈ L1[t0 , ∞).
Определение. Будем говорить, что матрица A ∈ Ξ , если она имеет
следующую структуру:
a11 a12
A=
.
ā12 ā11
Утверждение 2. Если в системе (10) матрицы A0 , Ai(t), . . . , Ai1...ik (t)
принадлежат классу Ξ, то все матрицы Yi1 ...il (t) в (11) и все постоянные матрицы Ai1 ...il в (12) также принадлежат Ξ.
Утверждение 3. Пусть в системе (10)
M[tr Ai1...il (t)] = 0,
1 ≤ i1 ≤ . . . ≤ il ≤ n,
l ≤ k.
Тогда все матрицы в (12) имеют нулевой след, т. е.
tr Ai1...il = 0,
1 ≤ i1 ≤ . . . ≤ il ≤ n,
l ≤ k.
3. Случай простого потенциала. В этом разделе мы исследуем задачу (1) с потенциалом (2). Перейдем от уравнения (1) к системе
*
ẏ = x,
ẋ = (−λ + q(t))y.
y
Полагая y0 =
, представим эту систему в матричном виде
x
ẏ0 = (A + q(t)B)y0,
где
A=
0 1
−λ 0
,
B=
0 0
1 0
.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
61
Найдем собственные значения матрицы A:
√
μ = ±i λ
Сделаем замену y0 = Cy1, где
√
√ i λ i λ
.
C=
λ −λ
Приходим к системе
ẏ1 = (Â + q(t)B̂)y1,
где
 =
√
−i λ √
0
,
0
i λ
i
B̂ = √
2 λ
1 1
−1 −1
.
Чтобы избавиться от постоянной матрицы Â, произведем замену
√
−i λt
e
0
√
y1 =
y2 ,
i λt
0
e
в результате которой получим систему
ẏ2 = A1 (t)t−αy2 ,
где
i
A1(t) = P (t) √
2 λ
1
√
−2i λt
−e
(18)
√
2i λt
e
−1
.
3.1. Первое приближение. Положим k = 1 в теореме 2, что накладывает на параметр α следующее ограничение:
1
< α ≤ 1.
2
Воспользуемся теоремой 2 и сделаем в системе (18) усредняющую
замену вида (11), которая в нашем случае имеет вид
−α
y2 = I + Y1(t)t y3.
(19)
В дальнейшем нам понадобится явный вид матрицы Y1 (t). Эта матрица
определяется как решение уравнения
Ẏ1 = A1 (t) − A1 .
(20)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
62
с нулевым средним значением. Из (20) следует, что сначала необходимо вычислить матрицу A1:
⎛
⎞⎤
⎡
√ N
N
cj eiωj t
e2i λt
cj eiωj t ⎟⎥
⎢ i ⎜
−N
−N
⎜
⎟⎥ .
A1 = M [A1(t)] = M ⎢
√ N
N
⎠⎦
⎣ 2√λ ⎝
−e−2i λt
cj eiωj t −
cj eiωj t
−N
−N
Без ограничения общности считаем, что ωi =
ωj ∀i, j : i = j, тогда
матрица имеет вид
i
c∗
c0
,
A1 = √
2 λ −c̄∗ −c0
2
где c∗ = cn , если ∃ n ∈ N : λ = ω4n (выполнено условие резонанса
первого порядка), и c∗ = 0 в противном случае. Следовательно,
√
2i
λt
i
P√(t) − c0
e
P (t) − c∗
Ẏ1 = √
,
−P (t) + c0
2 λ −e−2i λt P (t) + c̄∗
и, окончательно, для нерезонансного случая (c∗ = 0) получаем:
⎞
⎛
√
N
N
cj iωj t
cj
√ e(ωj +2 λ)it
⎟
⎜
iωj e
iωj +2i λ
⎟
⎜
−N
−N
i ⎜ j
=0
⎟
Y1 = √ ⎜
⎟.
√
N
N
⎟
cj
c
2 λ⎜
j
(ω
−2
λ)it
iω
t
j
√ e j
−
e
⎠
⎝−
iωj
iω −2i λ
−N
j
(21)
−N
j
=0
Итак, вернемся к системе (18), которая после замены (19) примет
вид
(
)
i
c∗
c0
ẏ3 = √
t−α + R(t) y3 ,
−c̄
−c
∗
0
2 λ
где R(t) ∈ L1 [t∗, ∞).
1. Сперва рассмотрим нерезонансный случай, c∗ = 0:
(
)
i
c0 0
t−α + R(t) y3
ẏ3 = √
0
−c
0
2 λ
Очевидно, система уже является L-диагональной, и ее линейно
независимые решения имеют следующую асимптотику:
*
2
ic0
t−α dt , t → ∞,
y1,2(t) = [e1,2 + o(1)] exp ± √
2 λ
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
63
где e1 , e2 – векторы канонического базиса. Такие решения не принадлежат классу L2 [t∗, ∞).
2. Более интересен резонансный случай, c∗ = cn .
Для нахождения собственных чисел матрицы A1 получаем уравне1
(|cn |2 − |c0 |2 ). Тогда в зависимости от знака (|cn |2 − |c0 |2 )
ние μ2 = 4λ
выделяем два подслучая:
2. a) |cn | < |c0 |
В этой ситуации собственные
числа будут вычисляться по формуле
i
2
μ1,2 = ∓ 2√λ γ, где γ =
|c0 | − |cn |2 . Найдем собственные векторы
матрицы A1 и сделаем замену
cn
cn
y3 =
z.
−c0 − iγ −c0 + iγ
Приходим к L-диагональной системе
(
)
i
−γ 0
ż = √
t−α + R1 (t) z,
0
γ
2 λ
(22)
фундаментальная матрица которой при t → ∞ имеет следующую
асимптотику:
*
2
i
Z(t) = [I + o(1)] exp √
t−α diag(−γ, γ) dt .
2 λ
Таким образом, у системы (22) не существует решений из L2[t∗ , ∞), а,
следовательно, их не существует и у исходного уравнения (1).
2. b) Перейдем к подслучаю |c0 | < |cn |.
Собственные числа матрицы A1 имеют вид μ1,2 = ± 2√1 λ γ ∗, где
γ ∗ = |cn |2 − |c0 |2 . Как и в прошлом случае, делаем замену, диагонализирующую матрицу A1. Получаем асимптотику для фундаментальной матрицы системы (22) при t → ∞:
*
2
1
t−α diag(γ ∗, −γ ∗) dt .
Z(t) = [I + o(1)] exp √
2 λ
Легко видеть, что одно базисное решение растет неограниченно и
не принадлежит классу L2[t∗ , ∞). Другое же принадлежит классу
L2[t∗, ∞), если α < 1, а при α = 1 оно принадлежит классу L2[t∗ , ∞)
лишь в том случае, когда λ < |cn |2 − |c0 |2 .
3.2. Второе приближение. Полагаем k = 2 в теореме 2, что дает
нам условие
1
1
<α≤ .
3
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
64
Вновь проделаем усредняющую замену типа (11), которая на этот раз
имеет вид
−α
−2α
(23)
y3.
y2 = I + Y1 (t)t + Y11(t)t
Согласно теореме об усреднении 2, в результате этой замены система
(18) приводится к виду
−α
−2α
ẏ3 = A1t + A11t
+ R(t) y3 ,
(24)
где R(t) ∈ L1 [t∗, ∞).
Несложно показать, используя утверждения 2 и 3, что в случае
A1 = 0 поведение решений будет определяться именно матрицей A1
и будут верны результаты, изложенные нами в пункте 3.1. Поэтому
далее мы будем рассматривать лишь случай, когда A1 = 0.
Найдем, согласно (13), матрицу A11 = M[A1(t)Y1(t)]. Воспользовавшись формулой (21), получаем
⎛
⎞
N 2
2
cj ck
c c
|ck |
|ck | √
√ − j k ⎟
⎜
iωk − iωk −2i λ
iωk
iω
+2i
λ
k
⎟
⎜ −N
(j,k):
√
⎟
⎜
ωj +ωk
1 ⎜
λ=− 2
⎟
A11 = − ⎜
⎟.
N
|ck |2
⎟
4λ ⎜
c̄j c̄k
c̄j c̄k
|ck |2
√ −
√
⎟
⎜−
−
iωk
iωk
iωk +2i λ
iωk +2i λ
⎠
⎝
−N
(j,k):
√
ω +ω
λ=− j 2 k
Произведем элементарные преобразования: на главной диагонали сложим в каждой из сумм k-й и (−k)-й члены, а на побочной диагонали
приведем каждый элемент суммы к общему знаменателю. Тогда
1
ϕ ψ
A11 = −
,
4λ ψ̄ ϕ̄
где
N
√ ϕ = 4i λ
√
ψ = 2i λ
1
|ck |2
,
ωk2 − 4λ
(j,k):
√
ω +ω
λ=− j 2 k
cj ck
√ ,
ωk (ωk + 2 λ)
(25)
а ϕ̄ и ψ̄ комплексно-сопряженные величины для ϕ и ψ соответственно.
Система (24) принимает вид
(
)
1
ϕ ψ
t−2α + R(t) y3 .
ẏ3 = −
ψ̄
ϕ̄
4λ
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
65
(ω +ω )2
1. В нерезонансном случае λ = j 4 k получим
(
)
1
ϕ 0
−2α
ẏ3 = −
t
+ R(t) y3 .
4λ 0 ϕ̄
Очевидно, что эта система уже имеет L-диагональную форму. Следовательно, мы можем выписать асимптотику ее фундаментальной матрицы при t → ∞:
*
2
1
Y = [I + o(1)] exp −
t−2α diag(ϕ, ϕ̄)dt .
4λ
Так как ϕ есть величина чисто мнимая, решения не принадлежит классу L2[t∗, ∞).
(ω +ω )2
2. В случае резонанса λ = j 4 k имеем
(
)
1
ϕ ψ
−2α
ẏ3 = −
t
+ R(t) y3 .
4λ ψ̄ ϕ̄
Так как Re ϕ = Re ψ = 0, то ϕ̄ = −ϕ, ψ̄ = −ψ. Получаем собственные
1
2
2
числа матрицы A11 вида μ2 = 16λ
2 (|ψ| −|ϕ| ). Далее задача разбивается
на два подслучая:
i
2. a) Если
|ψ| < |ϕ|, то собственные значения имеют вид μ = ∓ 4λ γ,
|ϕ|2 − |ψ|2 . Проделываем замену y3 = Cz, диагонализигде γ =
рующую матрицу A11, и выписываем асимптотику базисных решений
полученной системы:
*
2
1
−2α
z1 (t) = [e1 + o(1)] exp −iγ
t dt ,
4λ
*
2
1
t−2α dt .
z2 (t) = [e2 + o(1)] exp iγ
4λ
Решения z1 (t) и z2 (t) не принадлежат классу L2[t∗ , ∞).
2. b) В случае |ψ| > |ϕ|, вновь проделав замену y3 = Cz, диагонализирующую матрицу A11, получаем асимптотику базисных решений:
*
2
∗ 1
−2α
z1 (t) = [e1 + o(1)] exp −γ
t dt ,
4λ
*
2
1
t−2α dt ,
z2 (t) = [e2 + o(1)] exp γ ∗
4λ
где γ ∗ = |ψ|2 − |ϕ|2 . Решение z2 (t) не принадлежит L2[t∗ , ∞), а решение z1 (t) принадлежит данному классу, если α = 12 , а√при α = 12 оно
принадлежит L2[t∗ , ∞) только в том случае, когда λ <
|ψ|2 −|ϕ|2
.
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
66
3.3. Общий случай. Несложно получить вид k-го резонанса (позволим себе опустить доказательство):
(ωj1 + . . . + ωjk )2
λ=
.
4
Таким образом, мы отыскали условие резонанса, при котором матрица k-го приближения отлична от нуля. Зададимся теперь вопросом
о том, когда она является ведущей матрицей, то есть когда матрицы
предыдущих приближений равны нулю. Общего ответа на такой вопрос мы дать не можем, но мы знаем условия равенства нулю матриц
первого и второго приближений:
⇐⇒ c0 = 0,
λ =
N
|cj |2
= 0 ⇐⇒
= 0, λ =
ω 2 −4λ
A1 = 0
A11
1
j
Заметим, что для разрешимости уравнения
ω2
ω2
N
1
ωj 2
4 ,
(ωi +ωj )2
.
4
|cj |2
ωj2 −4λ
(26)
= 0 необходимо,
чтобы min 4k < λ < max 4k .
Очевидно, условия (26) являются необходимыми для того, чтобы
k-й резонанс повлиял на асимптотику решений.
4. Случай сложного потенциала. В этом разделе мы, опираясь на
полученные в разделе 3 результаты, исследуем задачу (1) с потенциалом (3).
После ряда замен — таких же, как и в первой задаче, — приводим
уравнение (1) к виду:
√ 2i λt
i
1√ e
y.
(27)
ẏ = √ q(t)
−2i λt
−e
−1
2 λ
Тогда, полагая
i
A1(t) = √ P (t)
2 λ
i
A2 (t) = √ Q(t)
2 λ
получим систему
1
√
−2i λt
√
2i λt
e
−e
1
√
−2i λt
−e
,
−1
√
2i λt
e
−1
ẏ0 = (A1(t)t−α + A2(t)t−β )y0.
,
(28)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
67
Очевидно, что в случае α = β эта задача сводится к задаче, рассмотренной нами в предыдущем разделе. В дальнейшем считаем для
определенности, что
α < β.
(29)
Выполним усредняющую замену (11), приводящую систему (28) к
виду (12).
4.1. Первое приближение. В условиях теоремы 2 положим k = 1,
что приводит нас к необходимости потребовать, с учетом (29), выполнения следующих условий:
1
< α < β ≤ 1.
2
Тогда система (28) с помощью замены
y0 = I + Y1 (t)t−α + Y2(t)t−β y
перейдет в усредненную систему
ẏ = (A1t−α + A2 t−β + R(t))y.
(30)
Здесь R(t) ∈ L1 [t∗, ∞), а матрицы A1 , A2 имеют следующий вид:
i
i
c0
d0
c∗
d∗
,
A2 = √
,
A1 = √
¯
2 λ −c̄∗ −c0
2 λ −d∗ −d0
где c0 = M[P (t)], d0 = M[Q(t)], а c∗ и d∗ отвечают за резонансы первого
порядка.
Дальнейшее исследование в значительной мере повторяет задачу
исследования случая простого потенциала, поэтому не будем на нем
останавливаться подробно, ограничившись лишь результатами, приведенными в заключении.
4.2. Второе приближение. Во втором приближении полагаем k = 2,
что, учитывая (29), дает нам следующие ограничения:
*
1/3 < α ≤ 1/2,
(31)
1/3 < β ≤ 1.
В этих условиях система (30) принимает вид:
ẏ = [A1t−α + A2 t−β + A11t−2α + A12t−α−β + A22t−2β + R(t)]y.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
68
Матрица A11 была определена выше. Матрица A22 имеет вид сходный с A11, отличие лишь в том, что частоты ωj везде изменятся на
νj , а коэффициенты cj — на dj . Матрица A12 выглядит следующим
образом:
(
)
a11 a12
A12 = M
,
a21 a22
где вид aij несложно получить из тех же соображений, что использовались ранее. Тогда
⎛ N √
√
√
2i√λck dj
2i λdj ck
2i λdj ck
2i λcj dk
√
√
√ +
√
⎜ −N − νj (νj −2 λ) − ωj (ωj −2 λ)
νj (νj +2 λ) ωk (ωk +2 λ)
(j,k):
⎜
(ν +ω )2
1 ⎜
λ= j 4 k
⎜
A12=− ⎜
√
√
√
N 2i√λck dj
4λ ⎜
2i λcj dk
2i λdj ck
2i λdj ck
√ +
√
√
√
⎜
− ν (ν +2 λ) − ω (ω +2 λ)
νj (νj −2 λ) ωk (ωk −2 λ)
j j
j
j
⎝ (j,k):
−N
λ=
(νj +ωk )2
4
Рассмотрим далее лишь случай, когда A1 = A2 = 0. Получаем
систему
ẏ = [A11t−2α + A12t−α−β + A22t−2β + R(t)]y.
В данном случае «ведущей» матрицей (т. е. определяющей асимптотику) является матрица A11, и именно она будет определять поведение
решений. В этой ситуации исследование будет полностью повторять
результаты п. 3.2.
Более интересен случай, когда «ведет» матрица A12. Для этого
должно выполняться равенство A11 = 0. Следовательно, необходимо,
чтобы, во-первых, не выполнялись резонансы второго порядка, а, вовторых
N
|ck |2
2 − 4λ = 0.
ω
k
1
С учетом всех полученных условий нами был построен пример, для
которого ведущей является матрица A12. Для этого был следующим
образом выбран потенциал:
q(t) = t−α (sin t + sin 2t) + t−β (sin t + sin νt),
+
5
− 1 ≈ 0.58113883.
ν=
2
В ходе численного эксперимента, проводимого с помощью [6], как и
предсказывала теория, в случае λ = 58 возник резонанс, подтвердив
возможность существования смешанных резонансов в уравнении (1) с
потенциалом вида (3).
⎞
⎟
⎟
⎟
⎟
⎟.
⎟
⎟
⎠
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
69
5. Заключение. Итак, нам удалось при помощи теории усреднения
выяснить, при каких значениях параметров существуют решения из
класса L2[t∗, ∞) для задачи (1) с потенциалами (2) и (3). Подытожим
полученные результаты.
Для потенциала (2) имеем следующие условия:
1. λ =
ωn2
4 .
(a) α = 1 и λ < |c0 |2 − |cn |2 ,
(b) α < 1 и |c0 | < |cn |.
2. λ =
(ωj +ωk )2
,
4
(a) α =
(b) α <
3. λ =
1
2
1
2
ωn2
4 ,
λ =
√
иλ<
c0 = 0.
|ψ|2 −|ϕ|2
,
2
и |ϕ| < |ψ|, где ϕ, ψ определяются по формулам (25).
(ωj1 +...+ωjk )2
,
4
λ =
(ωj1 +...+ωjl )2
,
4
∀l = 1, k − 1.
Необходимые условия для осуществления k-го резонанса:
N
|cj |2
c0 = 0,
= 0.
ω 2 −4λ
1
j
Для потенциала (3), полагая α < β (случай β < α симметричен),
получаем следующие результаты:
1. λ =
ωn2
4 ,
α < β ≤ 1, |c0 | < |cn |.
2. λ =
νn2
4,
λ =
ωn2
4 ,
c0 = 0, β < 2α.
(a) β = 1 и λ < |d0|2 − |dn |2
(b) β < 1 и |d0 | < |dn |
(ω +ω )2
(ν +νk )2
4
3. Для резонансов вида λ = j 4 k , λ = j
поправками результаты первой задачи.
4. λ =
(ωj +νk )2 1
, 3
4
<α≤
1 1
,
2 3
верны с очевидными
< β ≤ 1, c0 = 0, d0 = 0,
N
1
|ck |2
ωk2 −4λ
= 0.
Большинство аналитических выводов было проверено в ходе численного эксперимента с использованием [6], который подтвердил их
правильность.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
И. И. Коновалов
70
Литература
1. Eastham M. S. P. The asymptotic nature of the solutions of linear
differential systems. Oxford: Clarendon Press, 1989.
2. Демидович Б. П. Лекции по математической теории устойчивости. М.: Наука, 1967. 472 с.
3. Коддингтон Э. А., Левинсон Н. Теория обыкновенных дифференциальных уравнений. М.: ИЛ, 1958. 475 с.
4. Бурд В. Ш., Нестеров П. Н. Системы дифференциальных и разностных уравнений: метод усреднения и асимптотика решений:
учеб. пособие. Ярославль: ЯрГУ, 2008.
5. Нестеров П. Н. Метод усреднения в задаче асимптотического интегрирования систем с колебательно убывающими коэффициентами // Дифференциальные уравнения. 2007. Т. 43, №6. С. 731–
742.
6. Глызин Д. С. Пакет программ для анализа динамических систем
«Tracer». Свидетельство о государственной регистрации программы для ЭВМ 2008611464. Зарегистрировано в Реестре программ
для ЭВМ 24 марта 2008 г.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 519.681.5: 519.682
Е. А. Бойцов, В. В. Васильчиков
Кроссплатформенная библиотека
параллельного выполнения rpC-программ
Описывается новая версия библитотеки поддержки параллельного режима работы программ, написанных в соответствии с концепцией
рекурсивно-параллельного программирования. Библиотека является существенной составной частью инструментальной среды RpmShell.
Предмет и цели разработки
Инструментальная среда RpmShell [1] предназначена для создания, отладки, исследования и эксплуатации рекурсивно-параллельных
(РП-) прикладных программ, написанных на языке rpC. Она состоит
из следующих основных компонентов:
• оболочки, позволяющей производить все операции по созданию,
отладке и эксплуатации приложения. Она включает в себя текстовый редактор, инструменты для настройки и выполнения всех
основных операций: выбор режима работы, создание проекта
Visual Studio, компиляция, сборка, копирование необходимых
файлов на другие компьютеры системы, удаленный запуск на
выполнение;
• препроцессоров, осуществляющих предварительную обработку
исходного текста на rpC в зависимости от выбранного режима
исполнения, а также генерирующих соответствующий C++ проект для последующей обработки посредством выбранной версии
Visual Studio;
• библиотек периода выполнения. В настоящий момент они включают в себя библиотеку поддержки параллельного режима исполнения РП-программы, а также библиотеку последовательного исполнения с формированием трассы параллельного вычислительного процесса;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
72
Е. А. Бойцов, В. В. Васильчиков
• модулей (реализованных как dll), обеспечивающих обмен информацией между ПМ непосредственно перед запуском РПпрограммы в параллельном режиме. Позволяют установить связь
между компьютерами сети, переслать необходимые файлы, сформировать список исполнителей и удаленно запустить приложение.
Библиотека поддержки параллельного режима исполнения РПпрограммы является ключевым элементом среды RpmShell, поэтому
основные усилия разработчиков были (да и будут в дальнейшем) направлены именно на ее совершенствование. Ранее разработанная версия библиотеки [2, 3] в целом выполняла свою задачу и обеспечивала
возможность разработки и использования программ, написанных на
языке rpC под операционными системами семейства Win32. Вместе с
тем она имела ряд недостатков, которые и была призвана устранить
данная разработка. Как основные недостатки мы бы отметили следующие два:
• широкое использование небезопасных возможностей языка C, в
особенности нетипизированных указателей (void*), положенных
в основу системы сообщений, что сильно затрудняет отладку и
увеличивает вероятность ошибок;
• не самым лучшим образом выстроенная архитектура библиотеки,
"размазывавшая" по коду разных классов логически целостные
алгоритмы и наоборот, близко объединявшая несвязанные участки, что ощутимо усложняло отладку и снижало надежность.
Кроме того, при разработке кроссплатформенного решения препятствием могло стать широкое использование в коде функций и объектов
WinAPI, которые отсутствуют под другими платформами. Этот момент
также был учтен при разработке исходного кода новой версии библиотеки. Наконец, в целях повышения эффективности РП-программ была
поставлена и решена следующая задача.
При программной реализации целого ряда алгоритмов зачастую
возникает ситуация, когда бывает сложно заранее оценить размер
входных или выходных данных рекурсивно-параллельной процедуры.
В случае традиционного (не РП-) программирования в таких ситуациях используются динамические структуры данных переменного размера. В предыдущей версии языка rpC и библиотеках поддержки был
реализован вариант использования структур фиксированного размера
в качестве блоков параметров. Они передавались целиком и при передаче активации на другой процессорный модуль (ПМ), и при возврате
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
73
результатов. Таким образом, у разработчика было только два варианта
решения проблемы:
• Ограничить сверху допустимые значения основных параметров
задачи некоторыми значениями и использовать структуры данных, заведомо достаточные для решения задачи при условии
выполнения указанных ограничений. Недостатки такого подхода
очевидны: это собственно необходимость наложения ограничений, а также излишние затраты оперативной памяти и накладные
расходы при организации сетевого обмена.
• Разработать свой механизм динамического выделения и перераспределения статической и/или разделяемой памяти, который мог
бы эмулировать работу кучи на уровне всей вычислительной сети. Очевидно, что такой подход отличается сложностью и невысокой производительностью.
С целью решения перечисленных выше проблем и было принято решение перепроектировать библиотеку и переписать ее на основе
имеющегося кода, добавив недостающую функциональность и устранив отмеченные архитектурные недостатки. Разработку было решено
вести в объектно ориентированном стиле, при этом как можно больше внимания уделить унификации подходов к реализации систем со
сходным назначением, а также максимально использовать возможности компилятора в обнаружении и локализации ошибок, как в самой
библиотеке, так и в коде клиентских приложений. При этом основные
алгоритмы, структуры данных и логические сущности библиотеки, хорошо зарекомендовавшие себя на практике, должны были остаться без
существенных изменений.
Работа со сложными типами данных и изменения в
прикладном интерфейсе
Основной задачей, которую требовалось решить при разработке новой версии библиотеки, являлось обеспечение возможности работы с
типами данных переменного размера. Для этого необходим некоторый
универсальный контейнер, способный хранить (принимать и отдавать)
любые данные, при этом предоставляя максимально простой интерфейс. В качестве такого контейнера был избран поток данных с двумя
основными операциями: запись N байт данных и чтение N байт данных. Для выражения данной абстракции на уровне структур данных
введен интерфейс rpm::IStream, экспортируемый из нашей библиотеки. Он содержит два основных метода:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
74
Е. А. Бойцов, В. В. Васильчиков
void Write(const char* buf, size_t size); // запись в поток
void Read(char* buf, size_t size); // чтение из
потока
Выделение интерфейса потока позволяет определить две обобщенные операции: сохранения объекта в поток и чтения объекта из потока.
Чтобы с помощью интерфейса IStream можно было передавать данные
пользовательского типа, в клиентском коде должны быть реализованы
функции со следующими прототипами:
IStream & operator < < (IStream & stream, const
UserType & value);
IStream & operator > > (IStream & stream, UserType &
value);
Реализовывать данные функции необходимо лишь для типов, содержащих указатели на области памяти, выделенные динамически,
при этом появляется возможность использования произвольной комбинации уже существующих реализаций, что существенно упрощает
разработку. Для простых структур (которые использовались в предыдущем интерфейсе) и типов подойдет шаблонная реализация по умолчанию.
Основное требование к данным операторам — полная "обратимость" : если N байт данных было помещено в поток оператором < <, то
именно N байт должно быть извлечено из него оператором > >, иначе
структура потока будет нарушена, что приведет к падению программы.
Никаких других ограничений на реализацию не накладывается. Данные можно передавать в любом удобном формате, бинарном или текстовом. В библиотеке предоставлены реализации данных операторов
для ряда контейнеров библиотеки stl (vector, map), а также объектов
класса std::string. Тот же факт, что сам вышеуказанный интерфейс содержит всего два основных метода и не накладывает ограничений на
метод внутреннего представления данных, позволяет реализовать его
на основе различных способов передачи и хранения: в качестве потока
может выступать простой буфер в памяти, файл на диске компьютера
или сетевой сокет.
Реализация такого расширения потребовала внести некоторые изменения и в способ описания параллельных процедур. От обязательного создания собственного типа структуры для каждой процедуры
было решено отказаться (оно стало необязательным), описание РПпроцедуры стало более приближенным к описанию обычной функции
языка С. Параметры процедуры теперь делятся на два типа: входные и
выходные. Входные параметры передаются по значению и после испол-
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
75
нения вызова обратно не возвращаются. Выходные параметры передаются по указателю (хотя реально используется тот объект, на который
данный указатель указывает), после завершения активации измененное значение возвращается на ПМ, породивший данную активацию.
Реализовать данное поведение оказалось возможным благодаря
шаблонам языка C++. Основная идея реализации состоит в преобразовании вызова в функтор, инкапсулирующий входные параметры
и адреса для возврата выходных параметров. Шаблоны позволяют сохранять эту информацию без потери данных о типах, генерируя собственный класс функтора для каждой конкретной пользовательской
процедуры. Кроме того, шаблоны обеспечивают проверку переданных
пользователем параметров при каждом вызове на соответствие сигнатуре вызываемой функции. Несоответствие их сигнатуре влечет ошибку компиляции. На практике это выглядит примерно так:
CPP(some_func, int, int, int*); // описание процедуры
...
int result; // переменная, используемая как outпараметр
// вызов процедуры, 5 и 10 передаются по значению,
// result используется для возврата
P_Call(some_func, 10, 5, &result);
...
// Пример ошибочного вызова, приводящего к
// ошибке компиляции, т.к. &d_var имеет тип
double*
double d_var;
P_Call(some_func, 10, 5, &d_var);
Описанный способ вызова обеспечивает большую типобезопасность и, кроме того, более приближен к обычному стилю вызова функции в языке C. Разумеется, реализация через шаблоны и сам характер
распределенной системы накладывают некоторые ограничения на параметры, а именно:
• нельзя определять функции с переменным числом параметров;
• количество параметров функции не должно быть больше десяти,
если в функцию необходимо передать больше параметров, то их
придется упаковывать в структуру;
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Е. А. Бойцов, В. В. Васильчиков
76
• рекурсивно-параллельные процедуры не могут возвращать значение, для этих целей должны использоваться выходные параметры;
• нельзя задавать значения параметров по умолчанию;
• бессмысленно (и даже опасно) передавать в качестве параметра
указатель на указатель или нулевой указатель.
Вышеописанные ограничения хоть и проводят некоторую границу
между обычными функциями языка C и рекурсивно-параллельными
процедурами, все же мягче ограничений предыдущей версии языка и
в меньшей степени сказываются на удобстве разработки.
Архитектура библиотеки
В новой версии значительной переработке подверглось ядро библиотеки RPM, однако переработка касалась способа реализации, а не
логической структуры. При проектировании новой архитектуры ядра
был учтен опыт предыдущей версии [2, 3], ее сильные и слабые стороны, а также использована некоторая часть исходного кода. Как показала практика разработки, отладка распределенной системы, работа
каждого компонента которой происходит в несколько потоков, является крайне сложной. Традиционные отладчики не имеют достаточных
средств для отладки такой системы. Почти все ошибки, обнаруженные
в предыдущей реализации, никогда не проявлялись напрямую в точке, где они были допущены, а порождали так называемые наведенные
ошибки, проявлявшиеся значительно позже при исполнении других
участков кода.
По этой причине при разработке новой версии библиотеки следовало сделать код максимально "безопасным" и строгим, уйти от потенциально вызывающих ошибки конструкций, обеспечить наилучшую
возможность локализации ошибки в случае ее возникновения. Обобщенная схема архитектуры библиотеки представлена на рисунке 1,
стрелками обозначены зависимости компонент.
Так как спецификация процессорного модуля предполагает наличие
трех слабосвязанных компонент [1]: арифметического (АП), управляющего (УП) и коммутационного (КП) процессоров, — каждый из них
логично было реализовать в виде отдельного потока (thread), и, следовательно, библиотека RPM является многопоточной. Однако для реализации многопоточности на разных платформах используются разные
средства.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
77
Рис. 1. Логическая архитектура библиотеки
В ОС Windows для организации потоков, взаимодействия между
ними, а также синхронизации используются соответствующие функции и объекты WinAPI, в UNIX-подобных ОС — библиотека pthreads.
Поэтому в целях унификации кода для различных платформ был написан ряд классов-оберток, полностью инкапсулирующих в себе работу
с потоками и основными примитивами синхронизации, а клиентскому коду предоставляется общий интерфейс для работы с ними. Как
и в предыдущей версии, для реализации арифметического процессора
были использованы волокна (fibers), позволяющие вручную осуществлять переключение контекста в потоке АП. Для UNIX-подобных ОС
подобная функциональность была реализована посредством функций
make/swapcontext POSIX-API (что в плане производительности оказалось даже более эффективным). Как и в случае с потоками, клиентский код данных отличий не видит, так как они скрыты в классахобертках.
Как было упомянуто выше, еще одна проблема заключалась в "размазанности" логики алгоритмов по функциям-обработчикам событий
и коду различных процессоров. События — это основной механизм
обмена информацией между процессорами. В целях устранения данной проблемы было принято решение сместить акценты в размещении
данной логики и полностью переместить ее в сами сообщения, выполнив их в виде функторов, реализующих основополагающий интерфейс
библиотеки IRPMJob.
Основная идея состоит в следующем: любой рекурсивнопараллельный вычислительный процесс является иерархическим, все
активации рекурсивно-параллельных процедур находятся друг с другом в отношении "потомок-предок" , при этом родительская активация
не может быть завершена до тех пор, пока не будут завершены все ее
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
78
Е. А. Бойцов, В. В. Васильчиков
дочерние активации. Но это же рассуждение верно и для служебных
операторов языка rpC: каждый такой оператор можно рассматривать
как потомка вызвавшей его активации, при этом активация не может
быть завершена ранее завершения работы оператора.
Это замечание позволяет сделать вывод о возможности унификации подходов к обработке активаций и служебных операторов с точки
зрения основной абстракции — некоторой законченной подзадачи в
вычислительной системе. В качестве такой подзадачи может выступать что угодно: активация процедуры, оператор доступа в память,
запрос захвата замка и т. д. С точки зрения проектирования выделение данной абстракции означает необходимость описания интерфейса,
ей соответствующего. Это и есть интерфейс IRPMJob. Поскольку с
его помощью организуется большая часть алгоритмов библиотеки, к
данному интерфейсу и его реализациям предъявляются следующие
требования:
• Полная инкапсуляция всей логики своей обработки: у внешних
сущностей не должно появляться необходимости определять, с
какой именно подзадачей они имеют дело, и как-либо вмешиваться в процесс их исполнения — вся работа должна вестись
через общий интерфейс.
• Возможность сериализации в поток и десериализации из него.
Данное требование очевидно, поскольку многие типы сообщений
предусматривают отправку на другие ПМ системы. В частности, такой возможностью должны обладать активации процедур,
а также операции по работе с распределенной и статической памятью.
• Возможность порождения дочерних сообщений и синхронизации
с ними. Так как рекурсивно-параллельный вычислительный процесс имеет иерархическую древовидную структуру, наличие такой возможности в интерфейсе было бы крайне желательным и
позволило бы максимально естественно организовать управление
временем жизни подзадач в зависимости от статуса их потомков.
• Возможность однозначно идентифицировать подзадачу в рамках вычислительной системы. Данное требование вытекает из
предыдущего. Если подзадачи находятся в отношении "предокпотомок" , то дочерняя подзадача должна иметь возможность
найти своего предка по иерархии, например, для того чтобы известить его о своем завершении. Так как архитектура RPM является распределенной, для выполнения данной задачи мы не можем
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
79
полагаться на указатели и должны использовать другой способ
идентификации подзадач.
При условии выполнения вышеуказанных требований, объекты
классов, реализующих интерфейс сообщения, действительно становятся "квантами" работы и могут вместить в себя большую часть логики
работы библиотеки, собрав воедино код, ответственный за выполнение
той или иной операции от начала до конца.
При разработке описываемой версии библиотеки были приняты следующие архитектурные решения. Каждый процессор в рамках процессорного модуля представлен своим классом. Создание объекта каждого
из этих классов означает запуск дополнительного потока управления
(для коммутационного процессора порождается два потока: на прием
и отправку данных).
В соответствии со спецификацией RPM задачей процессоров является порождение сообщений и реакция на них. Поскольку основная
часть логики переносится в сами сообщения, то роль процессоров сводится к предоставлению "площадки" для исполнения последних, а также выполнению некоторых задач, не относящихся непосредственно к
вычислительному процессу. На каждом из процессоров есть несколько
очередей, упорядоченных по приоритетам, в которые функторы помещают себя после порождения либо десериализации из сетевого потока.
Код функционирования каждого процессора, таким образом, представляет собой вечный цикл выборки задач из очередей и запуска их на
выполнение (рис. 2). Такой подход делает код каждого процессора относительно простым и легко сопровождаемым.
На основе структур данных и сервисов ядра функционируют прикладные подсистемы библиотеки (см. рис. 1). Каждая такая прикладная подсистема — это набор сообщений и, опционально, некоторая
управляющая структура (например, хранилище блоков памяти). На
данный момент в библиотеке присутствует три такие подсистемы, а
именно: подсистема для работы с памятью (статической и распределенной), подсистема синхронизации и подсистема сбора статистики.
Самой обширной из данных подсистем является подсистема работы с
памятью, обеспечивающая функционирование операторов выделения,
освобождения и доступа к распределенной и статической памяти.
Тестирование
С целью тестирования данной версии библиотеки рекурсивнопараллельного программирования было специально разработано rpCприложение для решения задачи о нахождении максимальной клике
в неориентированном графе, основанное на алгоритме Брона-Кербоша
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
80
Е. А. Бойцов, В. В. Васильчиков
Рис. 2. Схема работы процессора
[4] (вариант метода ветвей и границ). Основными причинами такого
выбора были следующие:
• Параллельные ветви программы имели заранее неизвестную трудоемкость. Это позволяло проверить качество работы алгоритма
динамической балансировки загрузки ПМ.
• Для реализации алгоритма требовалось использовать как статическую, так и распределенную памяти, а также осуществлять
синхронизацию с использованием глобальных замков, что также
позволило протестировать соответствующие механизмы.
Для тестирования использовалась локальная сеть, состоящая из
различного числа компьютеров. Исходные данные представляли собой
случайные графы из достаточно большого числа вершин с различной плотностью. Результаты контрольных прогонов позволяют сделать
вывод о работоспособности описываемой библиотеки и достаточно высокой эффективности ее работы.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
81
Заключение
Разработанная версия библиотеки РП-программирования предоставляет прикладному разработчику более мощный интерфейс, чем
все предыдущие, что должно упростить разработку параллельных алгоритмов с ее использованием и расширить класс решаемых задач.
Вместе с тем работа над созданием и совершенствованием программных средств поддержки данного стиля программирования будет
продолжаться. Как ближайшие задачи можно отметить следующие:
• портирование под современные программные платформы средств
визуализации статистики и средств имитационного моделирования среды RPMSHELL;
• разработка последовательной версии библиотеки для первичной
отладки рекурсивных алгоритмов;
• разработка специализированной отладочной версии библиотеки, предназначенной для выявления ошибок, характерных для
рекурсивно-параллельных приложений.
Решение каждой из этих задач существенно упростит разработку и
отладку параллельных алгоритмов с использованием библиотеки RPM.
Литература
1. Васильчиков В. В. Средства параллельного программирования
для вычислительных систем с динамической балансировкой загрузки. Ярославль, 2001.
2. Васильчиков В. В., Силантьев А. О. Средства поддержки параллельного выполнения рекурсивно-параллельных программ для
платформы win32 // Актуальные проблемы естественных и гуманитарных наук на пороге XXI века. Информатика: сб. материалов Всероссийской научной конференции, посвященной 200летию Ярославского государственного университета им. П. Г. Демидова. Ярославль: ЯрГУ, 2003.
3. Васильчиков В. В., Шубин А. В. Библиотека параллельного исполнения rpC-программ для Win32 // Моделирование и анализ
информационных систем. 2008. Т. 15, №1. С. 37–40.
4. Bron C., Kerbosh J. Algorithm 457 — Finding all cliques of an
undirected graph // Comm. of ACM. 1973. №16. P. 575–577.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 004.891
А. Ю. Колесов
О классификации текстов в условиях неполноты
обучающего множества
Рассматривается один из подходов улучшения качества систем автоматической классификации в условиях неполного обучающего множества, основанный на модификации обучающего множества. Описаны
эксперименты, показывающие применимость данного подхода к реальным задачам категоризации текстов с большим количеством рубрик.
Введение
Для структурирования больших объемов данных часто применяют рубрикацию. Для решения этой задачи предложено большое количество методов. Тем не менее качество классификации для многих
задач является низким (менее 50% полноты и точности). Для коллекций с большим количеством текстовых документов обычно задается
большое число классов-рубрик, имеющих пересечения, т. е. требуется
решать задачу мультиклассовой классификации (один объект может
относиться к нескольким рубрикам). Это усложняет и делает более дорогим процесс создания обучающего множества. Для того чтобы среди
большого числа рубрик отметить полный набор рубрик, релевантных
документу, требуется много трудозатрат одного эксперта, либо участие
нескольких экспертов. Как показывает практика, не всегда эти условия являются приемлемыми и выполняются. Поэтому для реальных
задач зачастую документы из обучающего множества имеют неполный
набор отмеченных категорий. Отсутствие у документа из обучающего
множества метки класса А, который является релевантным данному
документу, приводит к тому, что при обучении он попадает в число
отрицательных примеров для класса А. Это искажает решающее правило, что отрицательно влияет на качество классификации.
В данной работе предложен подход к решению задачи классификации в условиях неполного набора меток объектов из обучения, основанный на модификации обучающего множества. Этот способ позволяет уменьшить противоречия в ней. На реальной коллекции данных
показано, что этот подход повышает эффективность применения одного из самых эффективных методов машинного обучения (SVM).
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
83
Постановка задачи и схема решения
Дано множество текстовых документов D и множество классов
(меток, категорий) C = {c1 , . . . , cm }. Задача мультиклассовой классификации может быть определена как задача оценки неизвестной целевой функции Φ : D × C → {−1, +1}, которая отражает, как должны
быть классифицированы документы. Оценка Φ̂ называется классификатором. Здесь значение функции обозначает принадлежность (+1)
или не принадлежность (−1) документа d классу c. Обычно задачу
многоклассовой классификации решают путем определения m независимых бинарных классификаторов Φ̂j : D → {−1, +1}, по одному для
каждого cj ∈ C.
Обучающее множество представляет собой некоторый набор
LS ⊆ {(d, c) | d ∈ D, c ∈ C}. Обозначим LSc = {d | (d, c) ∈ LS},
DLS = {d | ∃c ∈ C : d ∈ LSc }, ADc = {d | d ∈
/ LSc , Φ(d, c) = +1},
FLc = {d | d ∈ DLS, Φ(d, c) = +1}, FL = {(d, c) | d ∈ DLS, Φ(d, c) = +1}.
Очевидно, ADc = FLc \ LSc .
Теперь запишем на языке множеств предположения, которые делаются в данной работе. Во-первых, утверждается, что существуют объекты из обучающего множества, составленного экспертами, имеющие
неполный набор меток, и их достаточно много. Это можно3записать
так: ∃c ∈ C : | ADc | > 0 и мощность множества | AD | = | c∈C ADc |
довольно значительна. Пока не будем останавливаться подробно на
формальном разъяснении, что означает "довольно значительна" , т. к.
для этого требуется отдельное исследование. Во-вторых, предполагается, что эксперты не ошибаются: любая метка, которую эксперт проставил для документа, правильна: LS ⊆ FL. Т. е. в процессе создания обучающей выборки возможны только ошибки первого рода (при
проверке гипотезы «объект d принадлежит рубрике c»). В-третьих, исходим из гипотезы компактности, которая гласит: «Схожие объекты
гораздо чаще лежат в одном классе, чем в разных; или, другими словами, что классы образуют компактно локализованные подмножества
в пространстве объектов».
Отсюда ясно, что для успешного решения задачи классификации
в указанных предположениях необходимо применять следующую схему. Сначала для каждой рубрики требуется найти те документы из
обучения (множество DLS), которые, исходя из геометрии данных, релевантны рубрике. Т. е. находим оценки Φ̂DLS
: DLS ×C → {−1, +1}.
j
Далее используем для обучения (нахождения Φ̂j ) новое обучающее
(d, c) = +1} ⊇ LS.
множество EFL = {(d, c) | d ∈ DLS, Φ̂DLS
j
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. Ю. Колесов
84
2. Предлагаемый подход
Существует несколько подходов к модификации обучающей выборки для улучшения качества классификации. Самые известные из них
очистка данных (data cleaning – см. [5]), удаление выбросов (см. [12]),
отбор эталонных объектов (например, работа [1]). Отметим, что применимость этих подходов к реальным задачам классификации текстов
в настоящее время недостаточно исследована. Т.к. алгоритмы, основанные на вышеперечисленных подходах не предусматривают предположений, сделанных в данной работе, то необходим другой подход,
который и описан ниже. Для первоначальных экспериментов были исследованы следующие два алгоритма:
1. На базе одного из новых методов частичного обучения, описанного в [10], назовем его SoftSL;
2. На основе k взвешенных ближайших соседей.
Оба алгоритма используют такую структуру, как множество ближайших соседей для документа, что соответствует третьему предположению.
Схема метода модификации следующая. На первом шаге с помощью одного из указанных алгоритмов получаем возможные пары релевантности документ-рубрика, которые не отметили эксперты. Обозначим это множество так:
P C = {(d, c)| ψ(d, c) = 1}
где d — документ, c — рубрика, ψ — соответствующий алгоритм модификации. На втором шаге выбираем способ использования множества
P C. Рассмотрим два варианта:
1. Добавляем множество P C в обучение;
2. Для пар (d, c) ∈ P C – при обучении для рубрики c документ d
не попадет в отрицательные примеры для этой рубрики.
Т. о. оставляем в обучающей выборке те объекты, которые, согласно
алгоритму ψ, не принадлежат выборке, если их отметил эксперт, т. к.
предполагаем, что эксперт не ошибается. Далее опишем алгоритмы
обнаружения недостающих меток для документов.
2.1. Поиск недостающих меток на основе алгоритма SoftSL
Предлагаемый в этом разделе метод использует графовый алгоритм
частичного обучения (semi-supervised learning), подробно описанный
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
85
в статье [10]. Он основан на минимизации расстояний Кульбака–
Лейблера (также см. в [10]) между распределениями вероятностей
принадлежности классам, определенными для каждого документа.
В дальнейшем будем называть его Soft-supervised learning method
(SoftSL). Одним из достоинств алгоритма является то, что его можно напрямую применять к мультиклассовой задаче. В [11] показано
превосходство SoftSL перед другими современными методами.
Кратко опишем идею алгоритма. Пусть имеется множество, состоящее из размеченных и неразмеченных объектов D = {Dl , Du}.
Здесь Dl = {(xi, yi)}li=1, Du = {xi}ni=l+1, где xi — входные векторы,
соответствующие объектам для классификации, yi — метки классовкатегорий. Определим ненаправленный граф G = (V, E) с весами, где
V = {1, . . . , n}, n — количество объектов в множестве E = V × V .
Обозначим wij ∈ W — вес ребра между объектами i и j. Вес ребра
определяется так: wij = sim(xi, xj )δ(j ∈ K(i)), где K(i) — множество k ближайших соседей объекта xi. Для каждого объекта x ∈ D
сопоставляется набор вероятностей принадлежности каждому классу
pi = (pti)m
t=1 , где m — количество классов. Для каждого из размеченных
объектов имеется также известный набор вероятностей ri = (rit )m
t=1 —
то, что разметили эксперты. Задача сводится к минимизации функционала по наборам вероятностей p = (p1, . . . , pn):
min C1(p), where C1(p) =
p
l
DKL (ri||pi)+
i=1
+μ
n
i=1 j∈K(i)
wij DKL(pi||pj ) − ν
n
H(pi), (1)
i=1
где DKL(pi||pj ) — расстояние Kullback–Leibler, H(pi ) — энтропия. Первый член отвечает за то, чтобы результирующие наборы вероятностей
не сильно уклонялись от вероятностей, заданных экспертами. Второй
член позволяет учитывать геометрию графа, т. е. близкие (по мере близости) объекты должны иметь сходные распределения вероятностей по
рубрикам. Третий член — регуляризация, приближает распределения
по рубрикам к равновероятному, в случае если другие члены формулы не предпочитают обратного. Численно задача решается методом
alternating minimization (AM). При использовании алгоритма для рассматриваемой задачи неразмеченных данных Du нет. После минимизации функционала minp C1(p) мы получаем для каждого документа
di ∈ D набор вероятностей pi = (p1i , . . . , pm
i ). Далее вводится порог
T ∈ [0, 1], с помощью которого выделяем дополнительные рубрики,
релевантные документу: документ di ∈ cj , если pji ≥ T .
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. Ю. Колесов
86
2.2. Поиск недостающих меток на базе алгоритма weightedkNN
Алгоритм k-взвешенных ближайших соседей (например, см. [8])
также напрямую позволяет решать мультиклассовую задачу. Кратко опишем, как он работает. Пусть определена функция расстояния
ρ(d, d ) между документами. Определим функцию принадлежности документа d рубрике c:
ρ(d, d )ϕ(d , c)
S(d, c) =
d ∈KNN(d)
ρ(d, d )
,
d ∈KNN(d)
где KN N (d) — множество k ближайших соседей в обучающей выбор
ке для документа d, ϕ(d , c) = 0, если d ∈
/ c, и ϕ(d , c) = 1, если d ∈ c.
Вводится порог T : если S(d, c) ≥ T , то документ d ∈ c. Алгоритм состоит в подсчете величины S(d, c) для всевозможных (d, c). Все пары,
для которых S(d, c) ≥ T , определяем как недостающие метки. На основе этих пар документ-рубрика можно модифицировать обучающее
множество.
2.3. Схема предлагаемого алгоритма
Опишем схему работы предлагаемого алгоритма. В качестве входных данных имеем обучающее множество (пары документ-рубрика).
Выполняем следующие шаги:
1) модификация обучающей выборки (см. Методы модификации
обучающего множества);
2) применение метода обучения к обновленной обучающей выборке.
На выходе получается решающее правило (классификатор) a(d) для
рубрикации новых объектов. Например, при подходе one-vs-rest для
алгоритма SVM a(d) = (a1 (d), . . . , am (d)), где m — количество рубрик.
Далее, с помощью этого решающего правила можно делать предсказания классов для новых объектов.
3. Эксперименты
3.1. Данные
Для проведения экспериментов использовались данные о научных
проектах Agingportfolio (см. [3]). Система содержит базу данных проектов, связанных со старением и финансируемых Национальным институтом здоровья (NIH) и Европейской комиссии (EC CORDIS). В
настоящее время в базе Agingportfolio имеется более 1 млн. 100 тыс.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
87
проектов, на которые были выделены гранты. По проектам имеется
следующая информация: авторы, название, краткое описание мотивации и целей исследований, организация, период, на который получен грант. Для некоторых проектов были даны тэги — термины, характеризующие проект. В экспериментах была использована информация только на английском языке. Средняя длина описания проекта —
100 слов. В экспериментах использовались только поля с названием,
кратким описанием и тегами. Имеется таксономия категорий, состоящая из 335 рубрик на 6 уровнях иерархии. Подробно с ней можно ознакомиться на сайте [3]. Тренировочное и тестовое множества состоят
из вручную размеченных по категориям этой таксономии документов.
Для тестового множества разметка производилась особым образом.
Для каждого документа имелось два набора категорий, составленных
разными экспертами. В качестве меток взято объединение этих наборов. Это позволяет получить более полный набор категорий. Обучающее множество составлено с меньшим контролем, разными людьми,
в том числе пользователями ресурса Agingportfolio. Как показывает
визуальный анализ, в обучающем множестве довольно большое количество проектов имеет неполный набор категорий. Об этом свидетельствует также следующий факт. Среднее число рубрик на проект
в обучающей выборке составляет 4, 36, а на тестовой — 9, 79. Тестовое множество состояло из 750 проектов. Обучающее множество — из
3144 проектов.
3.2. Предобработка данных
Использовалась векторная модель представления текстов. Признаками являлись слова, приведенные к нормальной форме. Веса
признакам присваивались согласно правилу TFIDF в формулировке
INQUERY (см. [2],[9]). Вектора, представляющие документы, приводились к норме 1 в евклидовой метрике n-мерного пространства.
3.3. Алгоритм обучения
В качестве алгоритма классификации использовался линейный
SVM ([7, 13]), который по сути является двуклассовым классификатором. При наличии более двух классов используются различные
способы для мультиклассовой категоризации на базе SVM. Одним из
традиционных путей реализации мультиклассовой классификации является подход one-vs-rest (см. [8]). Он и был использован в наших
экспериментах. Т. е. для каждой рубрики строилось свое решающее
правило: wc x + bc > 0. Программа Liblinear ([4, 6]) была выбрана в
качестве реализации алгоритма SVM.
3.4. Подбор параметров SVM
Подбирались следующие параметры:
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
88
А. Ю. Колесов
• параметр C (характеризует компромисс между максимизацией
разделяющей полосы, и минимизацией суммарной ошибки, см.
работу [7]);
• параметр b (порог bc классификации в решающем правиле, см.
также [2]).
Подбор параметров осуществлялся методом скользящего контроля с
разбиением множества на 5 частей согласно следующей стратегии. Параметр C подбирался по сетке и сразу же (для каждого C из сетки)
подбирался параметр b для каждой рубрики. Оптимальным считается
набор пар параметров {(C, bc)}c∈C , доставляющий максимум F1 -мере
при макроусреднении (см. [8]) по всем рубрикам. C — число, единое
для всех рубрик, bc — оптимальный (при заданном параметре ) порог для рубрики c, для каждой рубрики находится свой оптимальный
порог.
3.5. Модификация обучающего множества
Модификация обучающего множества производилась методами на
основе SoftSL (так же обозначено в таблицах) и k взвешенных ближайших соседей (обозначение w-kNN). Стратегию добавления множества P C в обучающую выборку обозначим «add+». Стратегию удаления документа d из отрицательных примеров класса c, если пара
(d, c) содержится в множестве P C, обозначим «del+». Параметры k,
T , μ выбирались по сетке следующим способом. При подборе использовалось множество из 200 документов (обозначим его Ddev ), которое
было получено таким же способом, как и тестовое множество. На всей
обучающей выборке обучались, на Ddev тестировались.
Набор параметров считался оптимальным, если он максимизировал F1 -меру при макроусреднении. Параметры выбирались для каждого способа модификации обучающей выборки. Для SoftSL параметр
μ подбирался уже для оптимальных k и T , подобранных для метода
w-kNN. Параметр ν для SoftSL был взят равным 0, поскольку все
документы в экспериментах имели метки и регуляризации не требовалось. Порог принадлежности рубрике для модификации с помощью
SoftSL был фиксирован: T = 0, 005.
3.6. Базовые алгоритмы
Для того чтобы судить об улучшении/ухудшении качества классификации, опишем базовые алгоритмы, с результатами которых будем
сравнивать эффективность других методов. Первый из них это SVM с
параметрами по умолчанию (обозначим noFit-SVM), второй — SVM с
подбором параметров (обозначим SVM). Таким образом, можно будет
сравнить, какой вклад в улучшение качества классификации вносит
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
89
подбор параметров, и насколько улучшает результаты модификация
обучающего множества каждый из рассматриваемых способов.
3.7. Рассматриваемые алгоритмы
Согласно схеме из 2.4, эксперименты с модификацией обучающей
выборки производились следующим образом. В соответствии с заданным алгоритмом (SoftSL, w-kNN) подбирались оптимальные параметры для них, после чего находилось множество P C. Затем применялась
заданная («add+», «del+») стратегия использования P C. На полученном обучающем множестве запускался SVM (Liblinear) c подбором
параметров (см. Подбор параметров SVM). Далее полученное алгоритмом SVM решающее правило применялось к тестовому множеству
и подсчитывались метрики качества (полнота, точность, F1 -мера; см.
[8]).
4. Результаты и выводы
В этом разделе приведем таблицы с результатами экспериментов,
с некоторыми данными для их анализа, а также сделаем выводы по
каждой таблице.
Таблица 1. Результаты на Agingportfolio
macro_f
noFit-SVM
2,02%
SVM
14,61%
del+w-kNN 16,76%
add+w-kNN 20,15%
del+SoftSL 15,09%
add+SoftSL 16,11%
micro_f
22,64%
28,47%
24,34%
39,43%
20,37%
31,13%
В Таблице 1 приведены значения F1-меры для базовых алгоритмов
и при применении SVM с подбором параметров на модифицированной
обучающей выборке коллекции Agingportfolio (обозначения способов
модификации см. выше). Как видно из Таблицы 1:
• Подбор параметров SVM значительно повышает F1-меру.
• Модификация обучающего множества улучшает качество классификации.
• Результаты при модификации «добавление релевантных документов в обучающее множество» превосходит способ «удаление из
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. Ю. Колесов
90
отрицательных примеров релевантных документов». Этот факт
также подтверждает, что предположение неполноты наборов меток для документов в обучающем множестве верно. Т. е. в исходной обучающей выборке объекты, важные для построения решающих правил для рубрик, имеют противоположную релевантность.
• Модификация обучающего множества на базе w-kNN работает
значительно лучше.
В Таблице 2 содержится следующая информация об обучающих
множествах: среднее количество рубрик на документ (avg_rubr_cnt)
и среднее количество документов на рубрику (avg_doc_cnt). Эти
сведения даны для исходного обучающего множества (обозначение
no_add_modif; то же количество сохраняется при отсутствии добавления документов в обучение после модификации), а также для модифицированных обучающих множеств.
Таблица 2. Среднее количество рубрик на документ и документов
на рубрику в различных обучающих множествах
avg_rubr_cnt avg_doc_cnt
no_add_modif
4,36
44,35
add+w-kNN
11,86
120,62
add+SoftSL
10,78
111,05
По Таблице 2 можно сказать следующее:
• При использовании принципа «добавление релевантных документов в обучающее множество» количество положительных примеров для каждой рубрики значительно возрастает. Вероятно, это
и приводит к увеличению F1-меры (см. Таблицу 1).
• При использовании алгоритма SoftSL количество добавленных в
обучающее множество пар документ-рубрика несколько меньше,
чем при использовании алгоритма w-kNN, как и результаты по
F1 -мере (см. Таблицу 1).
• Значение среднего количества рубрик на документ на обновленном обучающем множестве больше, чем на тесте (9,79 против
11,86 и 10,78). Это может свидетельствовать о том, что, возможно, есть потенциал для увеличения качества классификации
даже с использованием рассмотренных в этой работе методов.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
91
Итак, эксперименты показывают, что предположения относительно
обучающей выборки коллекции Agingportfolio были верны. Модификация дает довольно много дополнительных меток. Благодаря этому
для каждой рубрики растет число положительных примеров при обучении. В итоге наблюдается улучшение качества классификации (по
F1-мере на 38%). Отметим также, что полнота и точность после модификации обучающего множества становятся боле сбалансированными
(см. Таблицу 3).
Таблица 3. Полнота и точность результатов классификации
noFit-SVM
SVM
del+w-kNN
add+w-kNN
del+SoftSL
add+SoftSL
micro_recall micro_prec
13,00%
87,77%
22,86%
37,73%
50,08%
16,07%
39,39%
39,46%
39,65%
25,62%
46,90%
13,01%
macro_recall macro_prec
1,63%
6,84%
15,70%
25,76%
30,68%
23,64%
27,61%
24,92%
23,21%
21,88%
33,56%
18,89%
Заключение
В данной работе представлен подход для повышения эффективности применения алгоритма SVM в задаче классификации в условиях
неполного набора меток объектов из обучения. Идея заключается в модификации обучающего множества. Предложены несколько способов
модификации. Эффективность подхода показана на задаче классификации научных грантов с большим числом рубрик. Метод на основе
w-kNN и стратегии «добавление релевантных документов в обучающее множество» дает улучшение качества классификации по сравнению с базовым (SVM) по F1-мере на 38% и при макроусреднении, и
при микроусреднении. Другие алгоритмы также улучшают F1 -меру, но
не столь значительно.
Эксперименты проводились с использованием ресурсов вычислительного кластера Т-Платформы ЯрГУ.
Литература
1. Борисова И. А. и др. Сходство и компактность // 14-я Всеросс. конф. «Математические методы распознавания образов».
М.: МАКС Пресс, 2009. С. 89–92.
2. Колесов А. Влияние векторного представления на качество классификации документов // III Российская летняя школа по информационному поиску RuSSIR’2009, 11–16 сентября 2009 г.: Труды
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А. Ю. Колесов
92
Третьей Российской конференции молодых ученых по информационному поиску. Петрозаводск: Изд-во ПетрГУ, 2009. С. 67–75.
3. AgingPortfolio Web site, 2011. URL: http://agingportfolio.org.
4. Chih-Jen Lin’s Home Page.
URL: http://www.csie.ntu.edu.tw/˜cjlin/index.html.
5. Esuli A., Sebastiani F. Training Data Cleaning for Text Classification // Proceedings of the 2nd International Conference on
the Theory of Information Retrieval (ICTIR’09). Cambridge, 2009.
P. 29-41.
6. Fan R. E. et al. LIBLINEAR: A library for large linear classification
// Journal of Machine Learning Research, 2008. Vol. 9. P. 1871–
1874.
7. Joachims T. Text Categorization with Support Vector Machines:
Learning with Many Relevant Features // Proceedings of ECML98: 10th European Conference on Machine Learning — 1998.
8. Manning C. D., Raghavan P., Schutze H. An Introduction to
Information Retrieval. Cambridge, England: Cambridge University
Press, 2009.
9. Robertson S. E. et al. Okapi at TREC-3. In Proceedings of the Third
Text Retrieval Conference (TREC 1994).
10. Subramanya A., Bilmes J. Soft-supervised text classification.
EMNLP. 2008.
11. Subramanya A., Bilmes J. Entropic graph regularization in nonparametric semi-supervised classification. NIPS. 2009
12. Tang J. et al. Capabilities of outlier detection formulation schemes,
framework and methodologies // Knowledge and Information
Systems. 2007. Vol. 11, №1. P. 45–84.
13. Vapnik V. The Nature of Statistical Learning Theory. New York:
Springer-Verlag, 1995.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 004.931
С. С. Кулаков, М. В. Краснов
Программный комплекс для локализации
области лица на фронтальном фотоизображении
Для решения задачи локализации области лица на фронтальном
фотоизображении использован метод сравнения с эталоном и представлена его программная реализация.
Локализация лица на изображении является необходимой базой
для решения многих задач компьютерного зрения: распознавания лица, распознавания выражения лица, реконструкции 3D модели лица
по фотографиям. От точности решения задачи локализации во многом
зависит точность решения задач анализа изображения лица более высокого уровня. В данной работе рассматривается задача локализации
лица на фронтальном фотоизображении.
Постановка задачи
Рассматривается задача выделения области лица человека на фронтальном фотоизображении. Вначале опишем, какие ограничения накладываются на исходный фотопортрет:
• на исходной фотографии лицо одного человека;
• отклонение головы при повороте вправо/влево и вверх/вниз относительно нормального положения допускается в пределах ±10◦;
• лицо человека должно быть освещено достаточно равномерно;
• центральная часть лица (брови — нос) не должна закрываться
волосами, очками или иными предметами.
Алгоритм решения задачи
Задача разбита на три подзадачи:
• предварительная обработка изображения;
• поиск области лица на фотопортрете;
• поиск центров зрачков на фотопортрете.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
94
С. С. Кулаков, М. В. Краснов
Для решения поставленной задачи был выбран алгоритм, построенный на основе метода сопоставления с эталоном [1]. Рассмотрим
алгоритм более подробно.
Предварительная обработка изображения
Любая из этих операций выполняется только в случае необходимости.
1. Если A является изображением в цветовой модели RGB, выполняем перевод в полутоновое изображение Aout по формуле
Aout = 0, 299R + 0, 587G + 0, 114B.
2. Если изображение A зашумлено, то можно воспользоваться одной из следующих операций: сглаживающий фильтр или медианный фильтр.
Поиск области лица на фотопортрете
На вход алгоритма подается полутоновое изображение A с размерами m × n.
Шаг 1. Выделяются края на исходном изображении. Для выполнения этого шага можно использовать один из следующих методов:
оператор Собеля, оператор Шарра, оператор Робертса, оператор Превитта [2]. В результате получаем изображение
A1, каждый элемент
которого получен по формуле A1 = (Mx ⊗ A)2 + (My ⊗ A)2 , где
⊗−операция свертки,
Mx , My − маски сверток.
⎛
⎛
⎞
⎞
−1 0 1
−1 −2 −1
а) оператор Собеля
Mx = ⎝−2 0 2⎠
My = ⎝ 0 0 0 ⎠
⎛ −1 0 1 ⎞
⎛ 1 2 1 ⎞
3 0 −3
3 10 3
⎝
⎠
⎝
0
0
0⎠
b) оператор Шарра
Mx = 10 0 −10
My =
3 0 −3
−3 −10 −3
1 0
0 1
c) оператор Робертса
Mx =
My =
⎛ 0 −1 ⎞
⎛ −1 0 ⎞
−1 0 1
−1 −1 −1
⎝
⎠
⎝
0 0 0⎠
d) оператор Превитта Mx = −1 0 1
My =
−1 0 1
1 1 1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
95
Пример выполнения этого шага алгоритма на рис. 1, б-д.
Рис. 1, а.
Рис. 1, б.
Рис. 1, в.
Исходное изображение После оператора Собеля После оператора Шарра
Рис. 1, г.
Рис. 1, д.
После оператора Робертса После оператора Превита
Шаг 2. Применяется операция инверсии к изображению A1 . В ре-
зультате получим изображение
A2 = G − A1 ,
где G — константа, равная количеству уровней яркости изображения,
в данном случае G = 255.
Шаг 3. Изображение A2 бинаризируется в соответствии с формулой
0, aij ≤ T out
A3 = Ot(A2 ) =
,
1, aij > T out
где T out — оптимальный для A2 порог бинаризации. Глобальный порог
бинаризации T out вычисляется по методу Отса [3]. Метод предполагает наличие в изображении двух групп пикселей и ищет оптимальный
порог, разделяющий эти два класса так, чтобы их внутриклассовая
дисперсия была минимальна. Введем следующие обозначения:
• P (0), . . . , P (I) — наблюдаемые вероятности значений яркости I;
• q1 (t), q2(t) — суммарная вероятность первой или второй группы;
• μ1 (t), μ2(t) — средние значения первой и второй группы.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
96
С. С. Кулаков, М. В. Краснов
Отс показал, что в качестве T out надо брать значение порога t, при котором достигается максимум межгрупповой дисперсии
σb2(t) = q1(t)(1 − q1(t))(μ1(t) − μ2 (t))2. Пример выполнения этого шага
алгоритма на рис. 2.
Рис. 2, а.
Рис. 2, б.
После оператора Робертса После бинаризации по Отсу
Шаг 4. Для изображения A3 строится пирамида, состоящая из
множества изображений Mz = {A13, . . . , Al3}, где Ar3 — изображение с размерами (m/c) × (n/c), c = 2r + p (в работе p = 6).
Каждый пиксель Ar3 вычисляется в соответствии с выражением
i+c/2 j+c/2
Ar3(i, j) = c12 x=i−c/2 y=j−c/2 A3 (x, y). Размеры изображений Al3 будут
варьироваться, но при сопоставлении эталона фиксированного размера с каждым из Al3 разница в масштабе не играет существенной роли. В качестве функции сравнения выбрана городская метрика
i+Tm/2 j+Tn/2
l
F (Al3, C) = x=i−T
y=j−Tn/2 |A3 (x, y) − C(x, y)|, где C(x, y) — этаm /2
лонное изображение размера 6 × 5. Пример выполнения этого шага
алгоритма на рис. 3.
Рис. 3, а.
Рис. 3, б.
Эталонное изображение C(x, y) После выполнения алгоритма
Поиск центров зрачков на фотопортрете
Шаг 1. Выполняется поиск области лица на фотопортрете. В резуль-
тате область, где происходит поиск зрачков, становится сравнительно
небольшой.
Шаг 2. Для области лица выполнены оператор Робертса, инверсия,
бинаризация по методу Отсу. Вычисляются все возможные радиусы R
для зрачка.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
97
Шаг 3. Для каждого радиуса применяется преобразование Хафа
[3]. Напомним основную идею преобразования Хафа для окружности
с известным радиусом:
Цикл по всем черным точкам (xi, yj ) предполагаемой окружности.
Цикл по a от Xmin до Xmax с шагом dx.
Цикл по b от Ymin до Ymax с шагом dy.
Если (R − 0, 5)2 < (xi − a)2 + (yi − b)2 < (R + 0, 5)2, то
H[a, b] := H[a, b] + 1.
Конец цикла по b.
Конец цикла по a.
Конец цикла по точкам (xi, yj ).
После этого находится ячейка массива H[a, b] с максимальным элементом. И рассматривается окружность радиуса R и с центром в точке
(a, b). Пример выполнения этого шага алгоритма на рис. 4.
Рис. 4. После выполнения алгоритма.
Литература
1. Самаль Д. И. Алгоритмы идентификации человека по фотопортрету на основе геометрических преобразований: дис. . . . канд.
техн. наук. Минск, 2002.
2. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005.
3. Шапиро Л., Стокман Дж. Компьютерное зрение. М.: Бином.
Лаборатория знаний, 2006.
Ярославский государственный университет им. П. Г. Демидова
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
98
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сборник научных трудов молодых ученых . . . . Вып. 12 (2011)
99
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Научное издание
СОВРЕМЕННЫЕ ПРОБЛЕМЫ
МАТЕМАТИКИ И ИНФОРМАТИКИ
Сборник научных трудов
молодых ученых, аспирантов и студентов
Выпуск 12
Редактор, корректор М. В. Никулина
Компьютерный набор, верстка П. Н. Нестеров
Подписано в печать 08.12.11. Формат 60×84/16.
Бум. офсетная. Гарнитура «Antiqua».
Усл. печ. л. 5.81. Уч.-изд. л. 5.0.
Тираж 45 экз. Заказ
Оригинал-макет подготовлен в редакционно-издательском отделе
Ярославского государственного университета им. П. Г. Демидова.
Отпечатано на ризографе.
Ярославский государственный университет им. П. Г. Демидова.
150000, Ярославль, ул. Советская, 14.
Документ
Категория
Без категории
Просмотров
10
Размер файла
1 264 Кб
Теги
1243, информатика, современные, вып, математика, проблемы
1/--страниц
Пожаловаться на содержимое документа