Алгебра спектральных преобразований в задачах обработки данных

• Автор: Тетуев, Руслан Курманбиевич
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Пущино
• Количество страниц: 111 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

ГЛАВА I Аналитические преобразования над спектром

1. 1 Общие свойства классических ортогональных систем

1.2 Основы спектрального представления функций

1.3 Предпосылки к развитию новых методов спектральной обработки.

1.4 Понятие спектрального преобразования функций

1.5 Задача поиска методов быстрых спектральных преобразований

1.6 Ранние попытки решения задачи. Матричный способ.

ГЛАВА II Быстрые аналитические преобразования над спектром

2.1 Достаточное условие существования быстрых алгоритмов спектрального преобразования.
2.2 Классические ортогональные полиномы.
2.3 Быстрые преобразования для оператора вида x . Лемма о суперпозиции линейных операторов.
2.4 Быстрые преобразования для операторов вида xx. Теорема обратимости линейных операторов
2.5 Быстрые преобразования для оператора дифференцирования i
2.6 Быстрые преобразования для оператора интегрирования.
2.7 Нахождение рекуррентных соотношений для различных модификаций ортогональных базисов
ГЛАВА III Общая вычислительная схема для реализации быстрых
спектральных преобразований
3.1 Определение спектрального каскада и диффузии
3.2 Метод спектрального каскада и диффузии
3.3 Пример применения метода каскададиффузии.
3.4 Сравнительный анализ результатов расчетов и основных характеристик алгоритмов.
ГЛАВА IV Обобщения алгебры спекгральных преобразований
4.1 Быстрые нелинейные спектральные преобразования
4.2 Быстрые спектральные преобразования для ортогональных систем
дискретного аргумента
4.3 Сверхбыстрые спектральные преобразования на системах с
параллельной архитектурой вычислений.
ГЛАВА V Применение быстрых спектральных преобразований
5.1 Применение в задачах распознавания образов
5.2 Применен ие в зада чах биоинформат ики
ЗАКЛЮЧЕНИЕ
ВЫВОДЫ
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ
ЛИТЕРАТУРА


Сформулирована и доказана Теорема о достаточном условии существования алгоритма быстрого спектрального вычисления. Показано соблюдение достаточного условия Теоремы для ряда линейных операторов и всех систем классических ортогональных полиномов и функций. В ходе доказательств получены рекуррентные соотношения особого вида для полиномов Якоби, Гегенбауэра и функций Якоби, Гегенбауэра, Сонина-Лагерра, Лагерра, Чебышева первого и второго рода, Эрмита. Сформулирована и доказана Теорема об обратимости линейных операторов, а также сформулирована и доказана Лемма о суперпозиции линейных операторов. На основе применения спектральных преобразований предложено и реализовано вычисление инвариантных геометрических признаков, описанных аналитически с помощью операторов дифференцирования высоких порядков. Найдены и применены аналитически описанные признаки, инвариантные к выбору начальной точки и вычисляемые на основе отрезков ортогонального ряда. Реализован программный комплекс “8реси*а1Кеу1$ог”, организующий локализацию участков тандемных повторов в ДНК последовательностях на основе вычисления и анализа некоторых первых производных от функций-профилей, построенных на данных генетических последовательностях. Предложенный метод сопоставляет некоторым часто используемым на практике аналитическим преобразованиям функций, набор простых и быстрых вычислений для получения соответствующего преобразования спектрального представления. Это позволяет применять метод в различных прикладных областях, где требуются быстрые, точные и устойчивые аналитические преобразования сигналов различной природы. Показано, что для сложных преобразований функции, являющихся группой более простых, возможно построение единой вычислительной схемы, составленной на основе объединения соответствующих элементарных схем. При этом, многие частные вычисления в узлах выстраиваемой общей схемы, как показано в работе, могут быть произведены одновременно. В ходе выполнения диссертационной работы были получены новые аналитические соотношения для ряда базисов, построенных на классических ортогональных полиномах, что может быть полезным для последующих исследований и разработок в смежных областях науки. С появлением и развитием систем параллельных вычислений увеличивается разрыв по времени исполнения между еще более ускорившимися, но по-прежнему не прибавившими в точности численными методами расчета с одной стороны и проведением аналитических преобразований функций посредством спектра с другой. В тоже время появился целый ряд успешных работ, посвященных проведению сверхбыстрого преобразования Фурье на системах параллельных вычислений. Однако, задача об ускорении самих спектральных вычислений, соответствующих определенным преобразованиям функций, оставалась по-прежнему актуальной как при реализации на вычислительных системах с последовательной, так и с параллельной архитектурой. Диссертационная работа посвящена изложению и обсуждению нового вычислительного метода, предложенного на основании проведенных нами исследований и позволяющего существенно понизить временную сложность спектральных вычислений для ряда основных аналитических преобразований функций и групп их суперпозиций. Вычислительный метод основан на знании полученных рекуррентных соотношений определенного вида и приводит к алгоритмам той же временной сложности, что имеют алгоритмы, основанные на использовании численных методов, то есть линейной и логарифмической для систем с последовательными и параллельными вычислениями соответственно. Очевидно, что при этом сохраняются иные преимущества спектрального подхода, такие как широкие адаптивные возможности при аппроксимации функций и более приемлемые с практической точки зрения результаты их преобразований. Заключительная часть работы посвящена изложению результатов применения предложенного метода в некоторых научных областях и сравнительному анализу с альтернативными подходами решения рассматриваемых задач. Под полиномами Сонина-Лагерра в диссертационной работе понимаются обобщенные полиномы Лагерра. Подобная терминология впервые предложена авторами работы [1] и введена на основании [7].