Содержание к диссертации
Введение
1. Методы автоматического распознавания образов и классификации данных, содержащихся в непрерывных сигналах 14
1.1. Общие сведения об автоматическом распознавании образов и классификации данных, содержащихся в непрерывных сигналах 14
1.1.1. Задача распознавания образов и классификации данных 14
1.1.2. Распознавание образов и классификации данных, содержащихся в непрерывных сигналах: история вопроса 17
1.1.3. Методы распознавания образов и классификации данных, содержащихся в непрерывных сигналах 23
1.1.4. Направления и методы, развиваемые в данной работе 28
1.2. Алгоритмы структурного распознавания образов и классификации данных, содержащихся в непрерывных сигналах 30
1.2.1. Схема Р. Харалика структурного распознавания на бесконечных совокупностях данных 30
1.2.2. Методы реализации решающего правила в схеме Р. Харалика... 35
1.3. Методы распознавания, ис пользующие динамику нелинейных систем 43
1.3.1. Модель Дж. Хопфилда системы с ассоциативной памятью на основе нейронной сети 43
1.3.2. Динамика системы типа «реакция-диффузия» и системы связанных осцилляторов Ван-дер-Поля 46
1.3.3. Одномерная система распознавания, использующая предельные циклы 52
ВЫВОДЫ 56
2. Алгоритм распознавания и классификации на основе сжимающих многозначных отображений 58
2.1. Многоуровневое представление непрерывного сигнала :-:. 58
2.1.1. Представление сигнала в виде нечеткого гиперграфа 58
2.1.2. Пример определения длительностей сегментов 60
2.1.3. Смысл представления сигнала с точки зрения схемы Р. Харалика. 62
2.2. Сведения из теории многозначных отображений и вычислительных структур. вычислительная структура с адаптацией 63
2.2.1. Сведения из теории многозначных отображений 63
2.2.2. Сведения из теории вычислительных структур 66
2.2.3. Вычислительная структура с адаптацией 67
2.3. Алгоритм распознавания и классификации 71
2.3.1. Общая схема алгоритма 71
2.3.2. Реализация алгоритма с помощью адаптивной вычислительной структуры 75
2.3.3. Сопоставление алгоритма и функциональной схемы распознавания, основанной на динамике нелинейных систем... 77
2.4. Реализация алгоритма распознавания и классификации в виде алгоритма марковского типа 80
2.4.1. Общие сведения 80
2.4.2. Алгоритм марковского типа с неподвижной точкой 81
2.4.3. Программа, реализующая алгоритм марковского типа с неподвижной точкой 84
2.4.4. Распознавание слов с помощью алгоритма марковского типа с неподвижной точкой 86
Выводы 89
3. Исследование динамики нелинейной неравновесной среды с диффузией 90
3.1. Уравнение непрерывности и оператор перехода от управляющего сигнала к пространственным структурам на поверхности среды 90
3.1.1. Уравнение непрерывности 90
3.1.2. Зависимость волновых решений уравнения непрерывности от граничных условий при квадратичной рекомбинации 94
3.2. Динамика двухслойной среды с ненулевой перекрестной диффузией 98
3.3. Параметры двухслойной среды с ненулевой перекрестной диффузией для случая кремния и германия 105
3.3.1. Соотношения между параметрами среды 105
3.3.2. Значения параметров для кремния и германия 111
ВЫВОДЫ 114
4. Исследование одномерной нелинейной системы, описываемой уравнением ван-дер-полевского типа с кубической нелинейностью 115
4.1. Фазовая динамика системы, описываемой уравнением ван-дер-полевского типа с кубической нелинейностью 115
4.1.1. Качественное исследование уравнения (1) 116
4.1.2. Методы анализа фазового портрета динамической системы 123
4.2. Решение уравнения, описывающего динамику одномерной нелинейной системы, в виде ряда фурье 130
4.3. Параметры одномерной нелинейной системы системы 135
4.3.1. Ограничения на параметры, обеспечивающие устойчивые
состояния равновесия 135
4.3.2. Управление параметрами уравнения (1) 138
4.3.3. Физический смысл параметров а, Д v, / и р 140
4.3.4. Зависимость параметра р от а, /?, v и / '.'."! 143
4.3.5. Зависимость регулярности фазового портрета уравнения (1) от параметров 144
Выводы 147
Заключение 148
Литература
- Распознавание образов и классификации данных, содержащихся в непрерывных сигналах: история вопроса
- Представление сигнала в виде нечеткого гиперграфа
- Вычислительная структура с адаптацией
- Зависимость волновых решений уравнения непрерывности от граничных условий при квадратичной рекомбинации
Введение к работе
Актуальность исследования. Задачи, связанные с построением алгоритмов и устройств, осуществляющих автоматическое распознавание сигналов, возникают в различных областях радиотехники и автоматики и при решении проблем в области искусственного интеллекта.
Исторически первой задачей этого типа была задача распознавания речевых команд и слитной речи, впервые посталенная в 1943 г. Л.Л.Мясниковым и решаемая путем выделения различных параметров сигнала и сравнения их с эталонными.
В дальнейшем было предложено несколько направлений решения задачи распознавания непрерывных сигналов. Целью этих исследований, по классификации А.Фора, является построение автоматических устройств, производящих идентификацию, анализ, синтез, обработку и классификацию данных, содержащихся в предъявляемом сигнале.
Общая схема алгоритма распознавания данных, содержащихся в бесконечных совокупностях, предложена в 1983 г. Р.Хараликом. Данная схема описывает общий алгоритм структурного распознавания и основывается на гомоморфизмах структур, заданных на множествах данных. Реализация данной схемы осуществляется с помощью линейных динамических систем.
Первой попыткой использования устройства, описываемого нелинейной динамической системой, для решения задач распознавания является исследование перцептрона, осуществленное в 1965 г. Ф.Розенблатом. В 1967 г. А.Т.Винфри и независимо в 1970 г. А.И.Радченко предложили обобщение модели перцептрона в виде системы связанных осцилляторов.
Наиболее удачной для задач распознавания распределенной системой является построенная в 1982 г. Дж.Хопфильдом дискретная модель системы связанных осцилляторов - нейронная сеть - действующая по схеме ассоциативной памяти. Эксперименты с данной моделью, проведенные в 1987 г. А.А.Чиллингаряном, Н.О.Худоняном, О.Б.Саакяном и Г.З.Зазяном в Ереванском физическом институте, показали, что модель Хопфильда обеспечивает стопроцентную идентификацию небольшого набора образов (5-7 букв) при помехе до 50%, однако для больших наборов процент правильно идентифицированных образов быстро падает. Непрерывной вариант модели Дж.Хопфильда для задач распознавания предложен в 1987 г. А.А.Веденовым, А.А.Ежовым, Е.Б.Левченко и А.С.Михайловым.
Другим направлением использования нелинейных динамических систем для задач распознавания является применение одномерных нелинейных систем.
В 1983 г. А.В.Гапонов-Грехов и М.И.Рабинович предложили одномерную нелинейную модель распознавания и принцип классификации, при котором признаками принадлежности предъявляемого сигнала некоторому классу являются особые точки и предельные циклы в фазовой плоскости системы. Практические исследования данного принципа классификации проводились начиная с 1991 г. в Институте радиотехники и электроники РАН группой под руководством А.С.Дмитриева. В результате была построена действующая система распознавания, поиска и архивации текстов.
Таким образом, к настоящему времени получено достаточно большое число теоретических и практических результатов, связанных с разработкой методов и устройств распознавания с помощью распределенных и сосредоточенных нелинейных динамических систем. Однако, совместое использование распределенных и сосредоточенных систем для идентификации и класификации данных специально не исследовалось. Также, в отличие от линейных систем структурного распознавания, для нелинейных систем не построен общий алгоритм распознавания данных.
Цель работы состоит в построении алгоритма распознавания данных, содержащихся в непрерывных сигналах, основанного на использовании распределенных и сосредоточенных нелинейных динамических систем, теоретическом исследовании динамики нелинейных систем в связи с задачами распознавания, а также исследовании возможности физической реализации этих систем в виде радиотехнических устройств.
Для достижения поставленной цели необходимо решить следующие задачи:
1. Построить общую схему распознавания непрерывных сигналов с помощью нелинейных динамических систем; источником значений параметров сосредоточенной динамической системы в данной схеме должна быть распределенная динамическая система.
2. Построить алгоритм распознавания, основанный на использовании многозначных отображений, и описывающий процесс распознавания с помощью нелинейных динамических систем.
3. Исследовать реализуемость предложенного алгоритма в виде вычислительной структуры.
4. Провести теоретическое исследование динамики распределенной неравновесной одно- и двухслойной среды с диффузией; изучить зависимость процессов формирования диссипативных структур от граничных условий; рассмотреть вопрос о возможности ее физической реализации.
5. Провести качественное исследование динамики сосредоточенной нелинейной динамической системы; изучить зависимость типов состояний равновесия от параметров; предложить метод анализа фазового портрета.
6. Привести пример работы алгоритма на известной модели и провести
численное моделирование указанных нелинейных систем.
Положения, выносимые на защиту:
1. Метод распознавания на основе динамики нелинейных неравновесных систем.
2. Алгоритм распознавания, основанный на использовании многозначных отображений, и реализующая его адаптивная вычислительная структура.
3. Математическая модель двухслойной неравновесной среды с диффузией, допускающей стационарные поверхностные структуры.
4. Математическая модель зависимости типов состояний равновесия от параметров системы и приближенное решение системы.
5. Методы физической реализации системы распознавания на основе нелинейных неравновесных структур.
Научная новизна работы заключается в том, что:
1. Предложена схема распознавания непрерывных сигналов, в которой распределенная неравновесная среда задает рельеф фазового пространства сосредоточенной нелинейной динамической системы классификации.
2. Построена основанная на многозначных отображениях модификация алгоритма Р.Харалика струкіурного распознавания, описывающая процесс распознавания с помощью нелинейных динамических систем.
3. Предложена адаптивная вычислительная структура, реализующая построенный алгоритм.
4. Построена математическая модель динамики двуслойной неравновесной среды среды с диффузией, базирующаяся, в отличии от предложенной Ю.И.Балкареем и др. модели, на уравнении непрерывности.
Исследована зависимость процессов формирования диссипативных структур в данной модели от граничных условий.
5. Установлена зависимость типов состояний равновесия от непрерывно меняющихся параметров для уравнения ван-дер-полевского типа с кубической нелинейностью и предложен метод приближенного решения этого уравнения в рядах Фурье.
6. Исследована возможность физической реализации предложенных систем в виде радиотехнических устройств.
Практическая значимость исследования определяется тем, что полученные в исследовании результаты и предложенные модели и методы могут быть использованы при исследовании, создании и реализации распознающих систем, совмещающих возможности ассоциативной памяти на нейронных сетях и нелинейных распознавателей, использующих фазовую динамику сосредоточенных нелинейных динамических систем.
Методы исследования. Проведенные в работе исследования базируются на применении методов теории алгоритмов, методов теории динамических систем, теории тригонометрических рядов, методов анализа и синтеза радиотехнических цепей и устройств.
Внедрение результатов работы. Результаты работы использованы на кафедре Прикладной математики РГПУ им. А.И.Герцена (г. С.Петербург) при разработке курсов «Основы информатики и вычислительной техники» и «Численные методы и математическое моделирование», читаемых студентам физического факультета.
Аппробация работы. Основные результаты исследования докладывались и обсуждались на:
- Региональной конференции студентов, аспирантов и молодых
специалистов Северного Кавказа «Методы и средства цифровой обработки сигналов» (18-19 ноября 1993 г.) в г. Таганроге;
- XX Молодежной научно-технической конференции «Гагаринские чтения» (5 - 8 апреля 1994 г.) в г. Москве;
- ХХХХ научно-технической конференции (1 марта - 30 апреля 1994 г.) в г. Таганроге;
- Научно-методической конференции «Математика и информатика» (1995 г.) в г. С.-Петербурге;
- Третьем международном семинаре по физике и математике (26 - 29 мая 1998 г.) в г. Мурманске;
- Международной конференции «Анализ и синтез» (апрель 2004 г.) в г. Таганроге;
- Международной конференции «Интеллектуальные системы» (3-10 сентября 2004 г.) в г. Дивноморске.
Публикации. По теме диссертации соискателем опубликовано 14 работ, включая 7 статей, в т.ч. в центральных изданиях, и 7 материалов докладов на конференциях.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и двух приложений. Диссертация изложена на 164 страницах, содержит 24 рисунка и 3 таблицы, список литературы состоит из 158 наименований, исключая работы автора.
Содержание работы Во введении дана общая характеристика работы, обоснована актуальность темы исследования, сформулированы цель и основные задачи работы, показаны ее научная новизна и практическая значимость, сформулированы основные положения, выносимые на защиту, а также краткое изложено ее содержание.
В первой главе дается краткий обзор имеющихся в литературе результатов по проблеме автоматического распознавания" образов, формулируется задача распознавания и приводятся сведения о методах распознавания сигналов.
Описывается схема Р.Харалика структурного распознавания образов, содержащихся в непрерывных совокупностях.
Излагаются принципы распознавания, основанные на использовании нейронных сетей и распределенных неравновесных систем, а на основе сосредоточенных нелинейных динамических систем.
Приводится общая схема предлагаемого в работе метода распознавания образов, содержащихся в непрерывных сигналах, используещего распределенную неравновесную систему для формирования параметров классификатора, представляющего собой нелинейную сосредоточенный) динамическую систему.
Во второй главе предлагается модификация схемы Р.Харалика, описывающая предложенную схему распознавания.
Строится алгоритм распознавания, основанный, в отличие от схемы Р.Харалика, на многозначных сжимающих отображениях.
Формулируется понятие адаптивной вычислительной структуры и устанавливается, что предложенный алгоритм реализуем с помощью этой структуры.
Устанавливается смысл предлагаемого алгоритма с точки зрения схемы распознавания, основанной на использовании нелинейных динамических систем.
Приводится пример реализации алгоритма в виде алгоритма марковского типа с неподвижной точкой.
В третьей главе исследуется распределенная неравновесная система типа «реакция-диффузия», используемая для формирования значений параметров классификатора и реализующая многозначное отображение алгоритма распознавания.
Строится модель одно- и двухслойной среды с диффузии, основанная на уравнении непрерывности.
Выводится зависимость диссипативных структур от управления с помощью граничных условий.
Исследуются решения системы, описывающие стационарные волновые структуры на поверхности системы.
Приводятся сведения о возможной реализации предлагаемой системы, даются численные значения параметров и приводятся результаты численного моделирования системы.
В четвертой главе производится исследование динамической системы ван-дер-полевского типа с кубической нелинейностью.
Проводится качественное исследование системы и отыскаиваются условия существования особых точек и предельных циклов и устанавливаются зависимости типов особых точек от ее параметров.
Отыскиваются налагаемые на параметры условия, обеспечивающие устойчивые состояния равновесия.
Строится ряд Фурье функции, мажорирующей решение системы.
Описываются общие методы анализа фазового портрета в целом и предлагается реализация метода К.-Е.Эриксона и К.Линдгрена для исследуемой системы.
Приводятся сведения о физический смысле параметров системы, а также примеры фазовых портретов, полученные с помощью численного моделирования.
В заключении сформулированы основные научные и практические результаты диссертационной работы.
В приложении 1 приводятся разностные схемы, использованные для численного моделирования динамики систем.
В приложении 2 приводятся листинги скриптов, реализующие численные модели в среде MATLAB 6.5.
Распознавание образов и классификации данных, содержащихся в непрерывных сигналах: история вопроса
Распознавание слитной речи. Исторически первой задачей распознавания образов, содержащихся в непрерывных сигналах, является задача распознавания образов, содержащихся в слитной речи. представляющая собой задачу распознавания в узком смысле. В изначальной формулировке эта задача предполагала распознавание звуков речи, а затем и слов при неограниченном объеме словаря только на основе характеристик речевого сигнала.
В первой посвященной этой проблеме работе, опубликованной в 1943 году [Мясников, 1943], действие строившегося для распознавания всех звуков речи устройства основывалось на анализе распределения энергии речевого сигнала. Признаками каждого звука выступали комбинации знаков разностей энергии в 14 взятых попарно полосах частот. Надежность распознавания гласных звуков этим устройством составляла 75-80%.
В последующие два десятилетия было разработано несколько вариантов устройств распознавания речи [Potter et al., 1947; Dreyfus-Graf, 1949; Smith, 1951; Dudley et al., 1958; Denes, 1959; Fry et al., 1958; Fry, 1959], основой которых был перевод речи в изображение в виде спектро-или сонограммы, к которой затем применялись методы анализа изображений (примеры спектро- и сонограмм речевых сигналов см. напр. в книге [Деркач и др., 1983]).
Первое законченное устройство "Одри", осуществлявшее распознавание десяти цифр (0-9) на основании анализа соответствующих отдельным фонемам изображений, было разработано в 1952г. [Davis et al., 1952]. Подстройка хранимых эталонов под голоса дикторов осуществлялась вручную, но при точном совпадении частот формант надежность распознавания произносимых в телефонном диапазоне цифр достигала 97-99%.
Начиная с 1960-х годов, после проведенного Р. Якобсоном [Jakobson et al., 1963] исследования, подтвердившего необходимость использования лингвистических характеристик при распознавании речи, задачи распознавания образов, содержащихся в слитной речи, основываются на анализе грамматической, контекстуальной и семантической структур речевого сигнала [Фланаган, 1968].
Основными уровнями лингвистического анализа являются [Плотников и др., 1988]: лексический анализ, использующий лексическую сетТь, в узлах которой находятся фонетические единицы речи, и осуществляющий выбор одного или нескольких слов из заданного словаря; синтаксический анализ, основанный на действующей в данном языке функциональной грамматике [Хомский, 1962] (описание и примеры см. также в [Фор, 1989; Плотников и др., 1988]) и проверяющий грамматическую правильность последовательностей слов; просодический анализ, фиксирующий границы предложений, фраз, оборотов и, в меньшей степени, слов; семантический анализ, определяющий является ли синтаксически правильная последовательность слов осмысленной, т.е. образует ли она предложение; прагматический анализ, выясняющий, является ли предложение осмысленным в рамках всего произносимого текста.
После выхода в 1960-м году работы [Denes et al., 1960], в которой описан распознающий десять цифр прибор, впервые использующий цифровое вычислительное устройство, в системах распознавания речи обработка высказывания на нижнем уровне осуществлялась аналоговыми устройствами, а лингвистический анализ - с помощью цифровых вычислителей. С середины 1970-х годов, с повышением быстродействия компьютеров и разработкой эффективных алгоритмов численного анализа, а также построением специализированных нечетких вычислителей [Мелихов и др., 1990; Асаи и др., 1993] на ЭВМ стала реализовываться вся, за исключением устройства ввода сигнала, система распознавания речи.
Представление сигнала в виде нечеткого гиперграфа
Осмыслим теперь данное представление с точки зрения схемы Р.Харалика структурного распознавания, описанной в п. 1.2.1.
В схеме Харалика задано множество данных X и покрытие этого множества и. Будем полагать, что это покрытие является покрытием и - XQ. Ясно, что для любого подмножества наблюдаемых данных
Xobs- сі из этого покрытия можно выбрать подпокрытие ugen. Отношение Г здесь является подграфом нечеткого графа G{f).
Предположение о том, что элементов покрытия и достаточно для обобщения на основе обучающего множества L є и8е" означает, что множетсво наблюдаемых данных таково, что в каждое множество из покрытия и попадает хотя бы один элемент множетства Xа s. А это означает, что можно проводить обобщение множеств из покрытия и-Х0 до множеств из покрытия Xv
Решающее правило состоит в расширении подграфа Т до графа D = G(f). В примере 2.1.2 подграф Т является «-срезом графа D. Для более сложных случаев правило построения графа D из графа Т является, разумеется, более проблематичным.
Нечеткий гиперграф в общем случае задает отображение множества вершин в некоторое покрытие множества вершин, образующее множество дуг этого графа. В п. 2.3 схема Харалика будет модернизирована с тем, чтобы построение покрытия Л", производилось автоматически за счет свойств отображений множества данных X в покрытие этого множества.
Построенный в п. 2.1 нечеткий гиперграф определяет отображение, при котором каждой вершине графа ставится в соотвествие некоторое множество вершин. Такое отображение является дискретным вариантом многозначного отображения, ставящего в соответствие точке некоторого множества подмножество этого же или другого множества.
Приведем некоторые сведения из теории многозначным отображений и из теории вычислительных структур, а также построим вычислительную структуру с адаптацией. Эта структура потребуется для демонстрации реализуемости предложенного алгоритма. Начальные сведения из теории многозначных отображений содержатся к книге [Борисович и др., 1986], а подробный обзор результатов этой теории - в статье [Борисович и др, 1982]. Для дальнейшего нам потребуются следующие определения (см. напр. [Колмогоров и др., 1976]).
Метрическим пространством называется пара (X, р), где X множество и р:Х xY -» Rl - однозначная, неотрицательная, действительная функция такая, что для любых х, у, z є X выполнено: р(х, у) = 0 тогда и только тогда, когда х = у; р(х,у)=р(х,у); р(х,у) р(х,у)+р(х,у). Функция р называется расстоянием или метрикой на X. Открытым и замкнутым шарами в (Х, р) называются, соответственно, множества в[х0, г]= {х:р(х0,х) г, х0,хе X] и В[х0,г]={х:р(х0,х) г, х0,хєХ}. Множество А с X называется ограниченным, если существует такой шар В а X (открытый или замкнутый), что А с В. Точка х є X называется предельной точкой множества А с: X , если для любого г выполнено В(х, г)п (А \ х) 0. Пусть LA - множество всех предельных точек множества А. Замыканием множества А называется множество = АиЬА. Множество А называется замкнутым, если А — А. Пусть Ах и А2 - непустые замкнутые ограниченные подмножества множества X. Метрикой Хаусдорфа, порожденной меторикои р, или расстоянием между множествами Ах и А2 называется величина Я(У4,, Л2) = тах sup р{х, А2 \ sup р{х, Л,) Теперь определим многозначное отображение.
Пусть X - произвольное множество и Р(х)=2Л \0 - множество всех непустых подмножеств множества X.
Многозначным отображением множества X в себя называется соответствие F : X —» Р{х), сопоставляющее каждой точке х є X непустое множество F(x)czX, F{X)GP(X). Множество F(x)dX называется образом точки х G X , а. множество F(A)= [JF(X), Ac: X,- образом множества А при отображении F. хеА Малым прообразом множества В с: X называется множество F;l(B)={x:xeX, F(x)eB], Полным прообразом множества В сі X называется множество F:l{B)={x:xeX, F(x)n ВФ0}. Ясно, что F; (B)CF M Точка х є X называется неподвижной точкой многозначного отображения F : X - Р{х), если х є F(x). Обозначим через Fix F множество всех неподвижных точек отображения F. Принцип неподвижной точки для многозначного отображения состоит в следующем. Пусть (х,р) - полное метрическое пространство, С(х)аР(х) совокупность всех непустых замкнутых ограниченных подмножеств множества X и Н(АХ,А2), АХ, А2еС(х) - метрика Хаусдорфа в С{х). порожденная меторикой р. Пусть F: X - С(х) - многозначное отображение. Если для любых х, у є X и фиксированного к, 0 к 1, выполнено неравенство H(F{x\F(y)) kp(x,y) (1) то отображение F имеет хотя бы одну неподвижную точку, т.е. FixF Ф 0. Многозначное отображение F:X- C{X), для которого выполнено неравенство (1) называется сжимающим (к-сжимающим). Принцип неподвижной точки для многозначного отображения является обобщением принципа о неподвижной точке однозначного отображения f : X —» X, введенного С.Банахом. Пусть (Х, р) - полное метрическое пространство. Точка х є X называется неподвижной точкой однозначного отображения f : X — X, если х - f{x).
Вычислительная структура с адаптацией
Поскольку предложенный алгоритм является физически реализуемым, то возможно осмыслить его с точки зрения функциональной схемы распознавания, предложенной в п. 1.1, Рисунок 1.1.5.
По постановке задачи все отображения, используемые в системе распознавания, являются вещественнозначными и значит на них может быть задана естественная метрика.
Отображения являются сжимающими, иначе классов окажется не меньше, чем признаков и задача распознавания потеряет смысл.
Модуль, осуществляющий описание образов, задает многозначное отображение F: X- Р{х) множества признаков в себя. Смысл данного отображения состоит в предоставлении набора описаний признаков - отображений X — X, которые используются при класификации. Данный набор формируется за счет задания параметров отображения f:X- X, реализуемого модулем, осуществляющим классификацию, и параметры должны быть постоянны для каждого образа F(x).
Модуль, осуществляющий классификацию, реализует множество отображений {/ :Х — Х}. В этом множестве предполагается, что отображения fap и ftt,p ПРИ выполнении хотя бы одного неравенства ах а2 и /?, /?2 являются различными, что возможно лишь при задании отображений /: X — X с помощью нелинейной динамической системы.
Тот факт, что отображения F: X — Р(х) и /: X - X являются сжимающими означает, что они реализуются динамическими системами с диссипацией.
Исходя из этого будем полагать, что:
отображение F: X — Р\Х) реализуется распределенной динамической системой с диффузией вида (1.3.8), где образам F(X) соответствуют волновые структуры, а множество FixF сформировано из устойчивых волновых структур вида (1.3.12);
отображение f:X— X реализуется одномерной нелинейной динамической системой вида (1.3.17). Тип фазовых траекторий и особых точек системы (1.3.17) определяется параметрами, входящими в отображение fa д н получаемыми от системы, реализующей отображение F:X P(X). Устойчивые узлы, фокусы и предельные циклы одномерной нелинейной динамической системы образуют множество Fix/.
Смысл использованного в алгоритме равенства FixF =Fix/ состоит в том, что значения параметров а и Д соответствующие признакам из множества FixF, таковы, что для них в отображении f : X— X реализуется множество Fix /.
Проиллюстрируем действие предложенного "алгоритма распознавания и классификации на модели распознавания последовательностей символов из некоторого алфавита. Для этого случая предложенный алгоритм является алгоритмом марковского типа с неподвижной точкой.
Пусть А - некоторый алфавит и А - множество слов в этом алфавите.
Алгоритмом А: А — А называется конечный конструктивный процесс, перерабатывающий слова Рє А в слова Qє А . Переработка слова Р в слово Q с помощью алгоритма А обозначается через А : Р = Q.
Переработка слов осуществляется с помощью схемы подстановок Z(A) алгоритма А, являющейся набором слов в алфавите ylu{—»}. Слова R є Z(A) называются правилами непосредственной переработки [Марков и др., 1996].
Программой называется следующая конструкция [Santos, 1997]. Пусть F - множество операционных символов, С - множество символов условий и L - множество символов меток. Для любых символов / є F, с є С и /, /і є Z, утверждения вида: start: go to /, I: do/, go to/і, /: if с then go to U, /: halt называются инструкциями. Программой называется упорядоченная последовательность имеющих различные метки инструкций, включающая единственную инструкцию start.
Данный алгоритм изложен в докладе [Kagan, 2004b].
Пусть А - алфавит и А:А -+А - алгоритм над алфавитом А. Обозначим через Р и Q слова в алфавите А и через Z = Z(A") - схему подстановок алгоритма А. Через А: Р = Q обозначим утвеждение, что алгоритм А применим к слову Р и через Q = А(р) - утверждение, что алгоритм перерабатывает слово P в слово Q. Слово Q называется результатом действия алгоритма на слово Р если A:P= Q и Q = А(Р). Условие Q - А(Р) позволяет исключить явную финальную подстановку из схемы подстановок Z. Алгоритм А, применимый к слову Q, и такой, что окончание его работы определяется соотношением Q = A{Q) называется алгоритмом с неподвижной точкой.
Зависимость волновых решений уравнения непрерывности от граничных условий при квадратичной рекомбинации
Наконец, найдем, как зависит наличие у системы (2) предельных циклов, охватывающих точки равновесия М], М2 и Мъ, от параметров системы.
Согласно критерию Бендиксона, если в некоторой односвязной области фазового пространства системы вида (2) функция cr(z/0.v()), задаваемая выражением (9) не меняет знака и не равна нулю тождественно, то в этой области не существует замкнутых контуров, составленных из траекторий системы. Рассмотрим выражение (9) для точек М,, М2 и Мъ. Для точки М], согласно (13), т, = а ; .- / Для точек М2 и М3, согласно (14), сг2 = т3 = а V Р )
Итак, найдены зависимости типов состояний равновесия и наличие предельных циклов от параметров системы. В следующем пункте систематизируем эти зависимости.
Рассмотрим методы анализа фазового портрета «в целом». Данный анализ призван ответить на два вопроса: 1. Является ли фазовый портрет в каком-то смысле регулярным? 2. Если фазовый портрет регулярен, то каковы количественные характеристики этой регулярности?
Разумеется, отрицательный ответ на первый вопрос означает, что система, с точки зрения данной задачи или в данном масштабе, демонстрирует стохастическую динамику. Замечание о маштабе связано с тем. что разностные системы демонстрируют так называемую «стохастическую паутину» [Заславский и др., 1991], т.е. траектории вблизи каждого заданного направления являются стохастическими, хотя сами направления образуют регулярную симметричную струкруру.
Показателем стохастичности динамики системы является показатель расходимости ее фазовых траекторий, определяемый следующим образом [Асташкина и др., 1980].
Пусть d(t) - расстояние между двумя соседними фазовыми траекториями в момент времени t. Показатель расходимости траекторий в момент времени / определяется формулой: где d(t0) - расстояние между траекториями в начальный момент времени.
Если с течением времени величина k(t) стремится к нулю, то это означает, что траектории притягиваются к устойчивому аттрактору и динамика системы является регулярной. Если же динамика системы стохастична, то расстояние между траекториями экспоненциально нарастает и существует предел K = \imk(t). /- 00 Величина К является энтропией Колмогорова или, что то же, максимальным характеристическим числом Ляпунова динамической системы и характеризует среднюю скорость разбегания фазовых траекторий: при К - const система приходит к равновесному состоянию, при К — оо демонстрирует хаотическое поведение. /-+00 Предположим, что К - const и значит ответ на первый вопрос Г-»оо положителен. Для задания количественной характеристики регулярности фазового портрета существуют следующие методы. В работе [Gaponov-Grekhov et al., 1983] предложен параметр г = . (16) т где т - размерность фазового пространства и D - размерность аттрактора, к которому при заданных параметрах притягиваются траектории системы. Значения параметра Р лежат в интервале от 0 до 1. Данный метод досточно хорошо характеризует свойства фазового портрета для случая странных аттракторов, однако требует заранее знать размерность аттракторов.
Другим методом количественного анализа регулярностей является метод Фурье-спектров [Заславский и др., 1991]. Пусть ОГ - множество фазовых точек, принадлежащих структуре фазового пространства размера Ги [0, M (9, где R — радиус-вектор точки, принадлежащей множеству Ог и RM -радиус-вектор произвольной точки фазовой плоскости.
В результате вычисления Фурье-спектра (результаты численных экспериментов см. в [Заславский и др., 1991]) выявляется группа симметрии структуры, образованной тракториями системы. Данный метод является исключительно эффективным и дает точное знание о свойствах фазового портрета системы, но требует громоздких вычислений, что затрудняет применение его в реальном времени.
Более практичным методом анализа регулярности фазового портрета и каждого отдельного состояния равновесия является следующий [Eriksson etal., 1987]. Зафиксируем некоторое число R0 0, называемое стандартным радиусом. RQ 0. Радусом разрешения называется величина R = RQe :\ где величина у 0 называется ясностью и характеризует масштаб, в котором анализируется фазовый портрет. Пусть M(u(t), v(/)) - фазовая траектория динамической системы. В фазовом пространстве зафиксируем область 0R(Mk) с центром в точке Мк = M(u(tk ), v{tk )), к Ф 0, и имеющую радиус R.
