автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Автоматическая интерполяция числовых данных функциями из заданного множества с наименьшим количеством параметров

На правах рукописи

Ш-

Никитин Дмитрий Александрович

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

05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

1 3 ОКТ 2011

Красноярск 2011

4856996

Работа выполнена в ФГБОУ ВПО «Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева».

Официальные оппоненты: доктор физико-математических наук,

профессор Винокуров Сергей Фёдорович

Ведущая организация: Институт проблем управления

им. В.А. Трапезникова РАН, г. Москва.

Защита состоится « 28 » октября 2011 г. в 14.00 часов на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу 660074, г. Красноярск, ул. Киренского, 26, ауд. УЖ 115.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета по адресу 660074, г. Красноярск, ул. Киренского, 26, ауд. 2-74.

Автореферат разослан « 26 » сентября 2011 г.

Научный руководитель:

доктор физико-математических наук, доцент Сафонов Константин Владимирович

доктор физико-математических наук, профессор Носков Михаил Валерианович

Ученый секретарь диссертационного совета кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

1. Провести анализ современных методов интерполяции.

2. Разработать алгоритм синтеза рекурсивного цифрового фильтра (фильтра с бесконечной импульсной характеристикой, БИХ-фильтра), значения отсчётов импульсной характеристики которого задаются некоторой одномерной функциональной зависимостью.

3. Разработать метод определения вида интерполянта и вычисления её параметров исходя из коэффициентов БИХ-фильтра, получаемого с помощью предложенного алгоритма синтеза.

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

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

Научная новизна работы состоит в следующем.

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

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

3. Разработаны способы расширения множества Ф; показана применимость алгоритма синтеза рекурсивного цифрового фильтра по импульсной характеристике, когда/является любой линейной комбинацией функций из множества Ф.

Программная реализация результатов работы. Программа поиска функциональных зависимостей в числовых последовательностях «FunSearch 1.0» прошла экспертизу и зарегистрирована в Отраслевом фонде алгоритмов и программ при Федеральном агентстве по образованию (№ государственной регистрации 50200700388, per. № ОФАП 7729).

Практическая значимость исследований. Разработанный алгоритм синтеза БИХ-фильтра по началу его импульсной характеристики имеет ряд

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

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

2. Теоремы существования и единственности БИХ-фильтров, импульсные характеристики которых определяются математическими функциями из указанного множества.

3. Метод автоматической интерполяции, основанный на предложенном алгоритме синтеза БИХ-фильтров, способен отыскивать наиболее простой интерполянт в выбранном множестве функций, а также позволяет настраивать это множество функций.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (2007 г.), Международной конференции ШЕЕ по управлению и связи SIBCON-2007, международной научно-технической конференции «Радиолокация, навигация, связь» (RLNC-2007), Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование» (ИТММ-2009), международной научной конференции «Теоретические и прикладные проблемы математики, механики и информатики» (Караганда, 2010), а также на научно-практических семинарах кафедры безопасности информационных технологий СибГАУ (2006, 2009, 2011 г.).

Публикации. По теме диссертации опубликовано 12 печатных работ. Полный список публикаций представлен в конце автореферата. 3 работы опубликованы в изданиях, рекомендованных ВАК РФ.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проведён анализ современных методов интерполяции дискретных данных. Обосновывается использование БИХ-фильтра в качестве математического объекта, однозначно связывающего две дискретные последовательности разного размера, и требующего для своего хранения объём памяти, меньший, чем большая из последовательностей.

Анализируются существующие методы синтеза БИХ-фильтров по импульсной характеристике. На основе проведённого анализа делается вывод об актуальности разработки метода автоматического определения интерполирующей функции. В соответствии с целью составляется список необходимых исследований.

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

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

Задана последовательность Y длины L. Необходимо рассчитать рекурсивный цифровой фильтр, начало импульсной характеристики которого совпадает с Y. Рекурсивные ЦФ, описываются выражением

у{П)=^Ькх{п-к)-^а,у{п-к) (1)

Здесь у(п) и х(п) — выходная и входная последовательности фильтра соответственно, ак и Ьк — коэффициенты фильтра. Наибольшее из чисел М и N считается порядком фильтра.

В таких фильтрах присутствует обратная связь, определяемая коэффициентами ак, за счёт чего импульсная характеристика фильтра получается бесконечной, при конечном числе его коэффициентов. Поскольку последовательность Y конечна, будем считать её началом импульсной характеристики рассчитываемого фильтра. Таким образом, известен выход фильтра (исходная последовательность Y) и вход — единичный импульс (так как мы приняли, что исходная последовательность это импульсная характеристика). Исходя из этого, необходимо рассчитать цифровой фильтр.

Синтез фильтра заключается в нахождении его коэффициентов ак и Ьк. Используя выражение (1) можно построить систему линейных уравнений, определяющую взаимосвязь коэффициентов фильтра с его импульсной характеристикой. У рекурсивного ЦФ такая система будет бесконечной, т.к. бесконечна сама импульсная характеристика. Вот как будет выглядеть система уравнений в общем виде для первых L>M+N+1 отсчётов импульсной характеристики (используем обозначения хп = х(п), у„ = у{п)):

¿0 = У о ¿1 ~а\Уа ~ У\ Ъг-ахух-агуй=у2

Ък ~ («, Уы-\ + «2 У N-2 + ■ • • + аи-\ У о) = У N -(Р\Уы-1 + агУн-г + • • •+ ам-1У\ +амУо)~ Ум

- (а1 У1-2 + а2 У1-Ъ + • ■ • + аи У1-ы-\) = У1-1

Здесь неизвестными являются коэффициенты ак и Ък, а выход фильтра ¥={ук} является его импульсной характеристикой и в нашей постановке задачи известен заранее. Система уравнений (2) состоит из Ь уравнений, в правой части каждого из которых стоит отсчёт импульсной характеристики. Поскольку в (2) М+Ы+1 неизвестных, то для того, чтобы система могла иметь единственное решение, должно выполняться условие

Ь>М+Ы+1 (3)

Чтобы начать решать систему уравнений (2) не хватает только знания М и N. Пусть Ы=М-1 (таким образом, количество коэффициентов ак и Ьк будет равным), а М выберем любое, удовлетворяющее неравенству (3). Теперь построим систему — назовём её начальной — из первых М+Ы+1 уравнений системы (2). Для удобства,запишем её в матричном виде:

(1 \ С и \ ьо г Уо

1 ~Уо ь, У\

1 -у, ~Уо ъ2 Уг

1 -Ун-1 , -У N-2 ■ ■ ~Уо — У N

-Ун ■ -Ух ~Уо а, Ут I

V ~ Уя+м-\ — у N+11-2 ■ ~Уи-г ~ Ум-1)

Матрицу системы уравнений и соответствующую ей расширенную

матрицу назовём Р и Р соответственно. Решив систему (4) найдём все коэффициенты ЦФ. Но прежде, чем её решать, необходимо убедиться, что

она совместна и определена. Для этого вычислим ранги матриц Р и Р. Далее возможны три случая:

; Если гапё(р) = гап§( Р) = М+Ы+1, то система (4) совместна, обладает полным рангом, и её можно решить каким-либо стандартным методом.

2. Если гагщ(Р) Ф гагщ( Р ), то система (4) несовместна и при данных М я N не существует БИХ-фильтра, у которого первые М+Ы+1 отсчётов импульсной характеристики совпадают с заданными. Но он может существовать при большем порядке фильтра. Поэтому, если позволяет длина исходной импульсной характеристики, следует увеличить М и N на единицу, заново построить систему (4) и попробовать решить новую систему.

3. Если га^(Р) = гап$(Р) < М+И+1, то система уравнений недоопределена, то есть имеет бесконечное множество решений. Было бы неправильно выбрать какое-то одно решение из этого множества, так как при меньшем порядке фильтра существует единственное решение системы (4). Поэтому следует уменьшить М и N на единицу, заново построить систему (4) и проверить её на наличие единственного решения.

Таким образом, за счёт второго и третьего пунктов, начав с любых Ми N придём к минимально возможным М и АГ, при которых система уравнений (4) имеет решение. Решив систему уравнений, фактически найдём БИХ-фильтр, у которого М+Ы+1 первых элементов импульсной характеристики совпадают с М+Ы+1 первыми элементами Г. То есть соответствие уже будет установлено, но ещё не для всей длины Г. Поэтому следующим шагом алгоритма является проверка остальных 1-М-N-1 членов заданной импульсной характеристики на соответствие найденному решению.

Из соображений оптимизации скорости и используемого объёма памяти был выбран следующий способ проверки. После решения начальной системы уравнений известны все коэффициенты фильтра ак и Ък. Поэтому можно сгенерировать его импульсную характеристику, начиная с 1-го отсчета и до 1-го Если все отсчёты совпали с исходной последовательностью У, значит решение верное. Назовём такое решение фильтром, соответствующим последовательности Г. Блок-схема алгоритма представлена на рис 1.

Интересной задачей является определение того, в каких случаях в системе уравнений (2) Ь-М-Ы-1 последних линейных уравнений от М+ЛГ+1 неизвестных линейно зависимы от первых М+Ы+1 уравнений. Исследования и вычислительные эксперименты показали, что это выполняется, когда члены последовательности Г являются отсчётами некоторой функции Дх), взятыми с постоянным шагом. Установление всех таких функций является важным для предложенного алгоритма. В данной работе доказано, что/может быть

• произвольной полиномиальной функцией;

• произвольной показательной функцией;

• произвольной синусоидой или косинусоидой;

Рис. 1. Блок-схема алгоритма расчёта рекурсивного цифрового фильтра по началу его импульсной характеристики

Формулировки доказанных теорем следующие.

ТЕОРЕМА 1. Для последовательности Y длины L>2(n + \), члены которой являются равноотстоящими отсчётами полиномиальной функции одного переменного у, = p„(i) = a0-f + arfA + ... + an, сю * О, и заданы любые (и+1) подряд идущих члена ут, у^Ут+п, существует единственный

рекурсивный цифровой фильтр порядка и+1 (М=и+1, Ы-п), импульсная характеристика которого совпадает с У.

ТЕОРЕМА 2. Для последовательности У=у(V длины Ь>А, члены которой являются равноотстоящими отсчётами показательной функции у. = /(/) = к-а"'+с, афО, аф\, ЬфО, кфО, и заданы первые 4 членау0, уь Уъ Уз, существует единственный рекурсивный цифровой фильтр второго порядка (М= 2, N=1), импульсная характеристика которого совпадает с У.

ТЕОРЕМА ЗА. Для последовательности У=у(0 Длины ¿>4, члены которой являются равноотстоящими отсчётами синусоидальной функции у, = /(/) = а• эт(Ь • I + с), афО, к е Ъ и заданы первые 4 членауй, Уи У2, Уз,

существует единственный рекурсивный цифровой фильтр второго порядка (М=2, N=1), импульсная характеристика которого совпадает с У.

ТЕОРЕМА ЗБ. Для последовательности У=у(0 длины Ь>6, члены которой являются равноотстоящими отсчётами синусоидальной функции =/(/) = в-8т(й-1 + с) + ^, аф О, \Ь\<%, кеЪ,т,ъ заданы первые 6 членов Уо, Уи ••■> У5, существует единственный рекурсивный цифровой фильтр третьего порядка {М= 3, N=2), импульсная характеристика которого совпадает с У.

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

ТЕОРЕМА 4А. Для любой периодической последовательности У=у(0 периода Г и длины Ь>Т существует рекурсивный цифровой фильтр порядка Т (М=Т, 1), импульсная характеристика которого совпадает с У.

Коэффициенты такого фильтра будут равны: Ъй = уй, Ь1 = у1, ..., Ьт= Ут, = О, а2 = 0,... аГ-1 = 0. «г = -1 > гдеУь-Ут — значение членов последовательности

на периоде.

ТЕОРЕМА 4 Б. Для любой периодической последовательности У=у(0 периода Т=2к со значениями на периоде вида Оо, ¿1» • • •> ¿ь-и ~ I. • ■ • > и длины 1>Т существует рекурсивный цифровой фильтр порядка к (М= к, Ы=к-1), импульсная характеристика которого совпадает с У. Коэффициенты такого фильтра будут равны: Ь0 = % Ь\ = ¿ч, ..., ¿ы = - 0, а2 - 0, ...,

ат~ 1 = 0, ат= 1.

Предложенный алгоритм позволяет рассчитывать рекурсивный ЦФ наименьшего возможного порядка с заданным началом импульснои

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

Таблица 1. Минимальные М и Ы, для некоторых функций

Зависимость М N ^-тт

Линейная у,- = к-1 + Ъ 2 1 4

Квадратичная у( = ач2 + Ьг + с 3 2 6

Кубическая у, = а-? + Ы2 + сЛ + й? 4 3 8

Полином 4-й степени у, = а-\ + Ъ-1 + с ^ + Ш + е 5 4 10

Периодическая, Т— количество отсчётов, приходящееся на один период произвольная Т Г-1 2 Г

Показательная у-, = ка'+ с 2 1 4

Синусоида у,- = а-ят(Ъ-1+ с) + (1 3 2 6

Косинусоида У1 = а-соз(Ьч+ с) + й 3 2 6

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

Таблица 2. Минимальные Мн N. для некоторых линейных комбинаций функций

Зависимость М N ■^тт

Сумма линейной и периодической с периодом 2 Например, >>,• = аЛ + Ъ + с-(-1)' 3 2 6

Сумма квадратичной и периодической с периодом 3 5 4 10

Сумма двух синусоид у1 = кх-зт(/г1 + (р\) + кг$т(/2-1 + + <Р2) + С 5 4 10

Сумма показательной, квадратичной и синусоидальной Функций у, = куа" + кгг2 + ку1 + кл-5т(/ч + + <р) + с 6 5 12

Сумма трёх синусоид у1 = + щ) + кг-$ т(/-г + + Фг) + куят^Н + <й) + с 7 6 и

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

Метод поиска интерполянта состоит из трёх основных шагов:

1) Для заданной последовательности чисел У=Ш однократно вычисляется соответствующий рекурсивный ЦФ.

2) По коэффициентам обратной связи найденного ЦФ, определяется вид функции/ которой подчиняются значения членов Г: у; =/)')•

3) Используя только коэффициенты найденного фильтра, вычисляются значения параметров функции/

Первый шаг выполняется в соответствии с описанным выше алгоритмом синтеза БИХ-фильтров. Суть второго и третьего шагов метода заключается в следующем. Вид некоторых функциональных зависимостей / можно сразу идентифицировать по значениям коэффициентов обратной связи ак, а все параметры (константы) функции определяются по коэффициентам Ък. Назовём такие функции «простыми». Для других (назовём их «сложными») необходимы несложные вычисления, так как в них коэффициенты ак зависят не только от вида, но и от её параметров.

«Простыми» функциями являются полиномы и периодические. В табл. 3 приведены значения коэффициентов обратной связи для различных «простых» функций.

Таблица 3. Коэффициенты обратной связи цифровых фильтров, соответствующих _ некоторым «простым» функциональным зависимостям

Зависимость Коэффициенты ак

Линейная у,- = $о-г+ \-2 11

Квадратичная У/ = [-3 3-11

Кубическая 3 и = *=0 [-4 6-4 1]

Полином 4-й степени *=0 [-5 10 -10 5 -1]

Полином 5-й степени *=0 [-6 15 -20 15 -6 1]

Полином 6-й степени б 4=0 [-7 21 -35 35 -21 7 -1]

Полином 7-й степени 7 *=0 [-8 28 -56 70 -56 28 -8 1]

Полином 8-й степени у,=!>*•''* 4=0 [-9 36 -84 126 -126 84 -36 9 -1]

Периодическая, с периодом Г отсчётов произвольная [0 0 ... 0 0 -1] 4-v-' Т-1 нулей

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

Коэффициенты Ьк фильтра, у которого значения членов импульсной характеристики задаются «простой» функцией, в свою очередь полностью определяются параметрами функции /. Приведём примеры.

Таблица 4. Зависимость коэффициентов Ьк от параметров «простых» функций

Зависимость Коэффициенты Ьк

Линейная У1 = к-г + Ъ \к+Ъ -61

Квадратичная у( = ач2 + Ьч + с [а+Ь+с а-Ь-2с с]

Кубическая [а+Ь+с+с1 4а-2с-Ъс1 а-Ъ+с+Ы

Полином 4-й степени [а+Ь+с+(1+е 11а+ЗЬ-с-Зс1-4е 11а-36-с+3с?+6е а-Ь+с-й?—4е е]

Периодическая, с периодом Г отсчётов Произвольная [Уо У1 ■■■ Ут-1]

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

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

Функция М N Коэффициенты

Показательная у< = к-аЬ1+с 2 1 Ь0 = к-аь + с ¿1 = - аь-(к + с) а2 = аь

Синусоида ¿V = а-зт(Ь-г+ с)+с! „О | .1 3 2 ¿>о = а-йп{Ъ+с)+<1 Ъ\ = а-(8т(Ь+с)+зт(с))-2-бг-со8(г>) Ь2 = а-5т(с)+с1 Д] = -2-со б(6) - 1 а2-2-со5{Ь) + 1 а3 = -1 ' • '

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

М= 2, N=1, а1+а2=-1, а2> 0, а2 + 1

Для синусоидальной функции:

М= 3, N=2, а\=-а2, -1<а2<3, а3=-1

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

Для суммы «простых» функций коэффициенты а* соответствующего ЦФ также оказались постоянными и не зависящими от параметров функции. То есть сумма «простых» функций является «простой» функцией и её тоже можно однозначно идентифицировать по коэффициентам обратной связи фильтра. Среди сумм с участием «сложных» функций проверялись

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

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

• информацию, необходимую для идентификации определённой функции;

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

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

На первом этапе метода для начала исходной последовательности отсчётов выполняется синтез соответствующего цифрового рекурсивного фильтра. Различным интерполянтам могут соответствовать фильтры разных порядков. Таким образом, для того, чтобы проверить в последовательности наличие всех функций из базы знаний, надо в худшем случае совершить N попыток синтеза БИХ-фильтра, где N — количество разных порядков ЦФ, соответствующих функциям из базы знаний. Алгоритм синтеза, построен так, что непосредственное вычисление БИХ-фильтра каждого порядка не выполняется. Он находит минимальный порядок ЦФ, соответствующего данной последовательности, при котором он является единственным, а уже потом вычисляет его.

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

Когда найден БИХ-фильтр, коэффициенты которого говорят о том, что элементы последовательности, используемые при его вычислении, описываются функцией известной алгоритму, следует определить, на сколько следующих членов последовательности распространяется найденная функциональная зависимость. Суть такой проверки сводится к вычислению импульсной характеристики найденного фильтра и её поэлементному сравнению с рассматриваемой последовательностью.

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

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

Далее в 3-й главе рассмотрена задача нахождения аппроксимирующей функции из заданного множества с наименьшим количеством параметров. Пусть в узлах значения исходных данных немного отличаются от точных значений некоторой функции, известной алгоритму. В этом случае коэффициенты обратной связи соответствующего ЦФ уже не будут точно подчиняться правилам идентификации данной функции. Тем не менее, в главе 3 показано, что их значения будут близкими к соответствующим точным значениям (это обусловлено тем, что коэффициенты фильтра являются решением СЛАУ, коэффициенты которой непрерывно зависят только от исходных данных). Поэтому небольшие отклонения исходных данных от идеальных значений будут приводить к малым отклонениям коэффициентов фильтра. Например, если коэффициенты обратной связи вычисленного ЦФ будут равны -3.04, 3.11, -0.97, значит, значения исходных точек очень близки к значениям квадратичной функции. Доказательство данного рассуждения в общем виде для одного вида функции приводится в 3-й главе диссертации. Таким образом, данный метод может быть использован, в том числе, и для аппроксимации числовых данных. Например, по теореме Вейерштрасса, любая непрерывная функция приближается многочленом, однако его степень может быть достаточно высока, и количество параметров - коэффициентов этого многочлена, которые необходимо найти, слишком велико (порядок фильтра для нахождения этого многочлена должен быть выше заданного). При этом может оказаться, что функция с той же точностью приближается, например, экспонентой с меньшим числом параметров, которые и будут найдены указанным методом при заданном порядке фильтра.

Опишем некоторые преимущества предлагаемого метода. Во-первых, она позволяет осуществлять потоковую обработку данных. То есть для начала её работы нет необходимости в наличии сразу всех обрабатываемых данных.

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

• определяется множество функций, приемлемых для описания исходных данных;

• в базу знаний вносятся правила для идентификации каждой такой функции;

• определяется множество порядков фильтров, соответствующих искомым функциям;

• далее в процессе работы перебираются порядки ЦФ только этого множества.

Покажем, что сложность вычислений, выполняемых при работе такой системы, с ростом количества видов искомых функций растет медленнее, чем в классическом случае. Пусть N - количество обнаруживаемых видов функций. Сложность классического случая растёт как О(А0, так как для обнаружения каждой функции требуются независимые действия. Пусть М -количество порядков ЦФ, необходимых для обнаружения этих N функций. М < N по определению. Соответственно, сложность вычислений при использовании предложенного метода равна О(М) < О(Ы). Даже более точно: сложность равна 0(М) + (И-М)-0(1) < 0(Ы).

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

Если не удалось установить возможность применения метода автоматической интерполяции к конкретному виду функции, можно в ряде случаев использовать разложение в ряд Тейлора интересующей функции /, неизвестной алгоритму, для ее обнаружения с некоторой допустимой ошибкой. Это возможно, если/является аналитичной функцией. Такой метод является приближённым и основан на том, что любая аналитичная функция по определению раскладывается в ряд Тейлора, который по сути является полиномом бесконечной степени. А если использовать реализацию метода в реальной цифровой системе, то можно, опираясь на максимальную необходимую точность для решаемой задачи, определить количество значащих членов ряда Тейлора. Отбросив остальные члены ряда, получим полином конечной степени. А для полиномов задача поиска уже решена (теорема 1).

Завершается третья глава описанием преимуществ предложенного метода автоматической интерполяции. Таковыми являются:

• Скорость работы не сильно зависит от их количества обнаруживаемых видов интерполянтов.

• Возможность настройки множества видов обнаруживаемых интерполянтов. Методика настройки описана в работе.

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

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

В приложениях содержатся листинги программ, выполняемых в системе МАТЬАВ, на которые имеются ссылки во второй главе диссертации, а также описана программная реализация предложенного метода.

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

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

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

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

Основные результаты и выводы.

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

2. Разработан метод автоматической интерполяции функциями из некоторого множества, основанный на предложенном алгоритме синтеза рекурсивного цифрового фильтра. Основные преимущества:

а) минимизация количества параметров интерполянтов;

б) вычислительная эффективность по сравнению с классическими методами при одновременном обнаружении нескольких видов функций;

в) возможность настройки множества отыскиваемых функций;

3. Разработаны способы расширения области применения метода: проверка применимости для произвольной функции и замена функции рядом Тейлора.

4. Разработана программная реализация метода: программа поиска функциональных зависимостей в числовых последовательностях.

Основные результаты диссертационной работы представлены в следующих публикациях автора.

1. Никитин Д.А. Об одной численной методике упрощения алгебраических выражений / Д.А. Никитин // Теоретические и прикладные проблемы математики, механики и информатики: Материалы междунар. научной конф. (24-26 июня 2010 г.). -Караганда: КарГУ. - 2010. - С. 150-153.

2. Никитин Д.А. Приложения алгоритма синтеза рекурсивных цифровых фильтров по импульсной характеристике / Д.А. Никитин // Цифровая обработка сигналов. - 2009. - №4. - С. 8-15.

3. Никитин Д.А. Теоремы о существовании и порядках цифровых рекурсивных фильтров с импульсными характеристиками определённой формы / Д.А. Никитин // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием (13-14 ноября 2009 г.). - Томск: Изд-во Том. ун-та. - 2009. -4.2.-С. 144-146.

4. Никитин Д.А. Синтез рекурсивных цифровых фильтров по импульсной характеристике, определяемой элементарной математической функцией / Д.А. Никитин, Ханов В.Х. II Цифровая обработка сигналов. - 2008. - №3. - С. 10-14.

5. Nikitin D.A. Compression with Usage of the Functional Dependences Searching / D.A. Nikitin II IEEE International Conference on Control and Communications (SIBCON-2007). Proceedings. - Tomsk: The Tomsk IEEE Chapter & Student. - Russia, Tomsk, April 20-21, 2007. -P. 72-76.

6. Никитин Д.А. Расчёт рекурсивного цифрового фильтра по его импульсной характеристике / Д.А. Никитин // Сборник докладов XIII междунар. науч.-технич. конф. «Радиолокация, навигация, связь» (RLNC-2007) / ООО НПФ «САКВОЕЕ» - Воронеж. - 2007. - Т. 1. - С. 335-341.

7. Никитин Д.А. Сжатие временных рядов с использованием блочной интерполяции / Д.А. Никитин // Информационные технологии моделирования и управления. - 2007. - Вып. 1 (35). - С. 85-89.

8. Никитин Д.А. Сжатие с использованием поиска функциональных зависимостей / Д.А. Никитин И Конференция-конкурс «Технологии Microsoft в теории и практике программирования». - Новосибирск: НГУ. - 2007. - С. 133-135.

9. Никитин Д.А. Программа поиска функциональных зависимостей в числовых последовательностях «FunSearch 1.0» - М.: ВНТИЦ. - 2007. -№ 50200700388, per. № ОФАП 7729.

Ю.Никитин Д.А. Алгоритм анализа числовых последовательностей / В.Х. Ханов, Д.А. Никитин // Вестник Сибирского государственного

аэрокосмического университета имени академика М. Ф. Решетнева. - 2006. - № 6 (13). - С. 11-15.

11 .Никитин Д.А. Алгоритм сжатия медиаданных / Д.А. Никитин // X Междунар. науч. конф. с междунар. участием «Решетневские чтения». - Красноярск: СибГАУ. - 2006. - С. 313-314. 12. Никитин Д. А. Программные способы оптимизации алгоритмов цифровой обработки сигналов / Д.А. Никитин // Схемотехника. - 2006. -№2, С. 27-30. -№ 3, С. 24-27.

Подписано в печать 19.09.2011 Формат 60x84/16. Уч.-изд. л. 1,1 Тираж 100 экз. Заказ № 4913

Отпечатано:

Полиграфический центр Библиотечно-издательского комплекса Сибирского федерального университета 660041, г. Красноярск, пр. Свободный, 82а

Введение.

1. Анализ методов построения интерполирующей функции. Постановка задачи.

1.1. Методы интерполяции.

1.2. Разностные схемы.

1.3. Дискретные преобразования.

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

1.4.1. Цифровая фильтрация.

1.4.2. Методы синтеза БИХ-фильтров по заданной импульсной характеристике.

Выводы к главе.

2. Синтез БИХ-фильтра по началу его импульсной характеристики.

2.1 Алгоритм расчёта цифрового рекурсивного фильтра по началу импульсной характеристики.

2.2. Область применимости алгоритма А1.

Выводы к главе.

3. Автоматическая интерполяция числовых данных функциями из заданного« множества с наименьшим количеством параметров.

3.1. Определение функциональной зависимости по коэффициентам соответствующего фильтра.

3.2. Расширение области применения.

3.2.1. Линейная комбинация функций, уже известных алгоритму.

3.2.2. Проверка применимости к произвольным функциям.

3.2.3. Замена функции рядом Тейлора.

3.2.4. Использование метода для автоматического определения аппроксимирующей функции.

3.3. Описание системы автоматической интерполяции, основанной на предложенном методе.

3.4. Сравнение с другими методами отыскания функции, график которой проходит через заданный набор точек.

Выводы к главе.

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

В качестве интерполянтов чаще всего используются алгебраические полиномы, суммы экспонент, Фурье-суммы, сплайны [7, 27, 28, 64]. Известны несколько способов построения интерполяционных многочленов степени не более п-1 по п исходным точкам. При этом любые п значений функции являются полиномиально зависимыми, и имеются формулы, которые дают принципиальную возможность выписать соответствующий многочлен степени п-1. Например, интерполяционные формулы Лагранжа и Ньютона [26] удобны при интерполировании точек, близких к первой исходной точке. Для точек, близких к остальным исходным точкам, целесообразно использовать формулы Стирлинга и Бесселя [20]. Для получения интерполяционного многочлена с заданными значениями производных до некоторого порядка можно также использовать интерполяционный многочлен Эрмита [57].

Большая погрешность вычислений при интерполяции может проявляться и в открытом Рунге эффекте осцилляции при использовании многочленов высоких порядков [80]. Этого недостатка можно избежать, если 3 использовать для интерполяции сплайны - кусочно-гладкие функции, например, классические сплайны, представленные на отрезках алгебраическими полиномами [26]. С 1960-х годов сплайны используются при моделировании в системах автоматизированного проектирования и компьютерной графике, однако они использовались математиками задолго до этого. В частности, показано, что кривые Безье являются частным случаем многочленов Бернштейна, описанных в 1912 году. Сплайны обладают тем недостатком, что объём обрабатываемых данных возрастает по сравнению с интерполяционным многочленом: возрастает количество полиномов, при этом для обеспечения гладкости в узлах сплайна добавляется информация о значениях производных в узлах.

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

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

Фурье (ДПФ) дает разложение в ряд гармоник [30, 3]. Из-за того, что количество и частота гармоник ограничены, возникают такие недостатки как эффект Гиббса и муар [58]. Модификацией ДПФ, лишённой некоторых недостатков, является дискретное косинусное преобразование [13]. Есть также ряд других преобразований, в которых в качестве базисных функций используются другие наборы базисных функций (дискретное преобразование

Хартли, преобразование Уолша-Адамара и др.). В последние 20-30 лет активно развивается такое направление как дискретное вейвлетпреобразование [21], начало которому было положено в работах Хаара. В таком преобразовании базисными функциями являются колебания, локализованные по времени и частоте. Уже описано довольно много видов 4 вейвлетов (см. например работы Добеши, Малла, Ньюланда) [35, 74, 78]. В настоящее время используются во многих сферах, в том числе заменяя собой преобразование Фурье, так как лучше подходят для описания ограниченных по времени и нестационарных сигналов. При использовании дискретного преобразования его базис должен быть выбран заранее, и при этом полученная функция будет чаще всего суммой всех базисных функций. То есть количество параметров (коэффициентов перед базисными функциями) получается сравнимым с количеством исходных точек.

Из других видов интерполянтов, кроме описанных выше, наиболее известна интерполяция рациональными функциями — отношениями двух полиномов. Такая интерполяция может быть полезна в случаях, плохо интерполируемых полиномиальными методами. Долгое время единственным алгоритмом рациональной интерполяции был алгоритм Булирша-Штера [5]. Недостатками данного алгоритма является отсутствие механизма обнаружения полюсов и то, что не всегда можно построить интерполирующую рациональную функцию. В 1986 году Шнайдер и Вернер описали алгоритм рациональной интерполяции, использующий барицентрическое представление рационального интерполянта [82]. Затем этот алгоритм был улучшен Беррутом и др. [73]. Улучшенный алгоритм решает практически все проблемы, препятствовавшие использованию алгоритма Булирша-Штера, однако обладает собственными недостатками. Почти в то же время появился алгоритм Флоатера и Хорманна построения рациональной интерполирующей функции, не имеющей полюсов на действительной оси [75]. Важными чертами алгоритма Флоатера-Хорманна являются высокая скорость работы, устойчивость и надежность. По этим параметрам он сравним со сплайн-интерполяцией.

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

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

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

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

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

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

Задачи исследования:

1. Провести анализ современных методов интерполяции.

2. Разработать алгоритм синтеза рекурсивного цифрового фильтра (фильтра с бесконечной импульсной характеристикой, БИХ-фильтра), значения отсчётов импульсной характеристики которого задаются некоторой одномерной функциональной зависимостью.

3. Разработать метод определения вида функции и вычисления её параметров-исходя из коэффициентов БИХ-фильтра, получаемого с помощью предложенного алгоритма синтеза.

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

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

Научная новизна работы состоит в следующем.

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

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

3. Разработаны способы расширения множества Ф; показана применимость алгоритма синтеза рекурсивного цифрового фильтра по импульсной характеристике, когда / является любой линейной комбинацией функций из множества Ф.

Реализация результатов работы. Программа поиска функциональных зависимостей в числовых последовательностях «FunSearch 1.0» прошла экспертизу и зарегистрирована в Отраслевом фонде алгоритмов и программ при Федеральном агентстве по« образованию (№ государственной регистрации 50200700388, per. № ОФАП 7729).

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

Основные защищаемые положения.

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

2. Теоремы существования и единственности БИХ-фильтров, импульсные характеристики которых определяются математическими функциями из указанного множества.

3. Метод автоматической интерполяции, основанный на предложенном алгоритме синтеза БИХ-фильтров, способен отыскивать наиболее простой интерполянт в выбранном множестве функций, а также позволяет настраивать это множество функций.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Конференции-конкурсе «Технологии 8 t і

Microsoft в теории и практике программирования» (2007 г.), Международной конференции IEEE по управлению и связи SIBCON-2007, международной научно-технической конференции «Радиолокация, навигация, связь» (RLNC-2007), Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование» (ИТММ-2009), международной научной- конференции «Теоретические и прикладные проблемы математики, механики и информатики» (Караганда, 2010), а также на научно-практических семинарах кафедры безопасности информационных технологий СибГАУ (2006, 2009, 2011 г.).

Публикации. По теме диссертации опубликовано 12 печатных работ. Полный список публикаций представлен в> конце автореферата. 3 работы опубликованы в изданиях, рекомендуемых ВАК.

Структура и объем работы. Диссертация состоит из введения, трёх глав, заключения и трёх приложений общим объемом. 108 с. Список использованной литературы содержит 83 наименования.

Выводы к главе

В данной главе описана система автоматической интерполяции, ядром алгоритмического обеспечения которой является алгоритм А1. Метод автоматической интерполяции состоит; из трёх шагов, на' первом (и самом трудоёмком; из которых) .применяется предложенный алгоритм. Остальные шаги очень просты. Результатом работы такой системы; является определение всех участков во; входных; данных', которые могут быть, интерполируются некоторой функцией. Каждый такой участок может описываться функцией со своими уникальными; параметрами. Для обнаружения; участка:' необходимо, чтобы описывающая егог-функция входила вошножество.функций, известных алгоритму. Множество,- таких функций (то есть,' фактически,, множество; 'зависимостей; которые могут быть обнаружены предлагаемым методом) определяется/множеством видов импульсных характеристик, к которым применим? алгоритм А1. Для: каждого, участка .описывающая его функция, определяется с точностью до свободного члена.

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

В. целом основными преимуществами такой, системы обнаружения зависимостей перед аналогами являются:

1. Скорость работы не сильно зависит от их количества обнаруживаемых видов интерполянтов.

2. Возможность настройки множества видов обнаруживаемых интерполянтов. Методика настройки описана в работе.

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

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

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

Далее, в приложениях, дан пример реального приложения, созданного для отработки и демонстрации работы алгоритма А1, а также листинги программ, выполняемых в системе МАТЬАВ.

Заключение

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

В основе метода лежит также разработанный в ходе диссертационного' исследования; алгоритм синтеза- рекурсивного« цифрового фильтра по. значениям отсчётов его- импульсной; характеристики. Применить данный, алгоритм для обнаружения зависимостей позволил тот факт, что он даёт решение: в том случае, когда значения отсчётов импульсной? характеристики, задаются некоторой одномерной функциональной зависимостью:- Приведены: доказательства корректности данного« алгоритма? для* нескольких; классов функций; Особенностью алгоритма является определение минимального необходимого порядка;фильтра. •.■■., .

Также предложены способы расширения; области применимости предложенного метода автоматической, интерполяции (для обнаружения других функций помимо тех, которые описаны, в работе).

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

94 V

1. Айфичер Э. С., Джервис Б. У. Цифровая обработка сигналов: практический подход. —М.: Издательский дом «Вильяме», 2004.

2. Алгоритмы и программы восстановления зависимостей / Под ред. В.Н. Вапника. —М.: Наука, Главная редакция физико-математической литературы, 1984.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., Мир; 1979.

4. Баскаков С. И. Радиотехнические цепи и сигналы: Учебник для вузов по спец. «Радиотехника». — М.: Высш. шк., 2000.

5. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. § 17. Рациональная интерполяция // Численные методы. — 6-е издание. — М.: Бином, 2008. — С. 85, —636 с.

6. Беклемишев Д. В. Дополнительные главы линейной алгебры. —М.: Наука, 1983.

7. Бер М.Г., Малозёмов В.Н. Об интерполяции дискретных периодических данных. // Проблемы передачи информации. Т. 28. 1992, Вып. 4. - С. 60-68.

8. Богнер Р., Константинидис А. Введение в цифровую фильтрацию. — М.: Мир, 1976.

9. Большаков А. А., Каримов Р.Н. Методы обработки многомерных данных и временных рядов. — М.: Горячая линия Телеком, 2007.

10. Ю.Васильев Н., Зелевинский А. Многочлены Чебышева и рекуррентные соотношения // Квант. — 1982. — № 1. — С. 12-19.

11. ГВащенко Г.В. Bычиcлитeльнaяíмaтeмaтикa: основы алгебраической и тригонометрической интерполяции. —Красноярск: СибГТУ. — 2008.

12. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. — М.: Наука, 1984.

13. Гайдышев И. Анализ и обработка данных: специальный справочник. — СПб.: Питер, 2001.

14. Галлагер Р. Теория информации и надёжная связь. — М.: Советское радио, 1974.

15. Гантмахер Ф.Р. Теория матриц. — М.: Государственное издательство технико-теоретической литературы, 1954.

16. Гашников М. В., Глумов Н. И., Сергеев В. В. Адаптивный алгоритм интерполяции для иерархической компрессии изображений // Компьютерная оптика — ИСОИ РАН, Самара, 2002. — Вып. 23. — С.89-93.

17. Гончар А. А., Рациональные аппроксимации аналитических функций, Совр. пробл. матем., 2003, 1, 83-106.

18. ГОСТ 19.002-80. ГОСТ 19.003-80. Схемы алгоритмов и программ.

19. Даутов Ш. А. Об абсолютной сходимости ряда из коэффициентов Тейлора рациональной функции двух переменных. Устойчивость двумерных цифровых рекурсивных фильтров. — Доклады АН СССР,' 1981, т. 257, №6, с. 1302-1305.

20. Демидович Б.П., МаронИ.А. Основы вычислительной математики. — М:: Наука, 1970. 664 с.

21. Дьяконов В. П. Вейвлеты. От теории к практике. М.: COJIOH-Пресс, 2002, 448 с.

22. Дьяконов В. П. MATLAB 6.0/6.1/6.5+SP1 + Simulink 4/5. Обработка сигналов^ изображений. — М'.: COJIOH-Пресс, 2005.

23. Дьяконов В. П. MATLAB 6.5 SP1/7 + Simulink 5/6. в математике и моделировании. —М.: COJIOH-Пресс, 2005.

24. Елисеев С. Н. Исследование линейных алгоритмов ^устройств цифровой обработки сигналов в системах связи и радиовещания. — Самара, 2002. — 223 с. '

25. Завьялов М. Н., Елизаров Д. В. Комбинированный вариантгармонического разложения Пронин Журн. СФУ. Сер: Матем. и.физ., 2008, 1(4), С. 443-452.26.3ализняк В. Е. Основы научных вычислений. Введение вычисленные методыдля физиков. —М.: Едиториал УРСС, 2002.

26. Избранные главы дискретного гармонического анализа и геометрического моделирования. Под ред. проф. В. Н. Малозёмова. -СПбГУ, 2009. 584 с.

27. Калиткин H.H. Численные методы. М., Наука, 1978. - 512 с.

28. Кловский Д. Д. Теория передачи сигналов. — М.: Связь, 1973.

29. Кормен Т. X., Лейзерсон Ч. И., Ривест Р. Л:, Штайн К. Алгоритмы: построение и анализ. —М.: Издательский дом «Вильяме», 2005.

30. Куприянов М. С., Матюшкин Б.Д. Цифровая обработка-сигналов: процессоры, алгоритмы, средства проектирования. — СПб.: Политехника, 1999.

31. Ланкастер П. Теория матриц. — М.: Наука, 1978.

32. Лебедев Е. К. Быстрые алгоритмы цифровой обработки сигналов. — Красноярск: КГУ, 1989.

33. Ли Р. Оптимальные оценки, определение характеристик и управление. — М.: Наука, 1966.

34. Малла С.— Вэйвлеты в обработке сигналов. — М.: Мир. — 2005.96

35. Маергойз Л. С., Варава Б. Н. Об одной модификации метода Прони // Сибирский журнал индустриальной математики, 2007, том X, № 2(30).

36. Макконелл Дж. Основы современных алгоритмов. —М.: Техносфера, 2004.

37. Марпл мл. С. Л. Цифровой спектральный анализ и его приложения. — М.: Мир, 1990.

38. Математический энциклопедический словарь. — М.: Большая Российская энциклопедия, 1995.

39. Никитин Д.А. Алгоритм сжатия медиаданных / Д.А. Никитин // X Междунар. науч. конф. с междунар. участием «Решетневские чтения» / СибГАУ. — Красноярск, 2006. — С. 313-314.

40. Никитин Д.А. Об одной численной методике упрощения алгебраических выражений / Д.А. Никитин // Теоретические и прикладные проблемы математики, механики и информатики: Материалы междунар. научной конф. (24-26 июня 2010 г.) Караганда: 2010. - С. 150-153.

41. Никитин Д.А. Приложения алгоритма синтеза рекурсивных цифровых фильтров по импульсной характеристике / Д.А. Никитин // Цифровая обработка сигналов. — 2009, №4. — С. 8-15.

42. Никитин Д.А. Программа поиска функциональных зависимостей в числовых последовательностях «EunSearch 1.0» — М.: ВНТИЦ, 2007. — № 50200700388, per. № ОФА1Г7729.

43. Никитин*Д?.А. Программные способы оптимизации алгоритмов, цифровой обработки сигналов / Д.А. Никитин // Схемотехника, 2006, №2 — С. 27-30, № 3 — С. 24-27.

44. Никитин Д.А. Сжатие временных рядов с использованием блочной интерполяции / Д.А. Никитин // Информационные технологии моделирования и управления. Науч.-технич. журнал. — Воронеж: Научная книга, 2007. — Вып. 1 (35). — С. 85-89.

45. Никитин Д.А. Сжатие с использованием поиска функциональных зависимостей / Д.А. Никитин // Конференция-конкурс «Технологии Microsoft в теории и практике программирования» / НГУ. — Новосибирск, 2007. — С. 133-135.

46. Никитин Д.А:, Ханов В.Х. Синтез рекурсивных цифровых фильтров по импульсной-характеристике, определяемой элементарной математической функцией /Д.А. Никитин // Цифровая-обработка сигналов; — Москва, 2008, №3. — С. 10-14.

47. Носов В. А. Основы теории алгоритмов и анализа их сложности: курс лекций. М. 1992: .■■■''. .

48. Пётрусев;А;С. Разностные схемы и,их анализ. МФТИ, 2004. - 89 с.,

49. Политехническийсл0варь / Редкол.:;Ишлинский А. Ю: (гл. ред.) и др. .—3"-е изд., перерабги-доп.—- Mi: БолынаяРоссийскаягэнциклопедия;2000: — ISBM5-85270-264-L.

50. Прохоров С. А., ЕрафкишВ: B'i. Анализ погрешности-аппроксимации; структурных функций ортогональными функциями экспоненциального типа // Вестник.СамГТУ, серия-физ.-мат. науки, 2007, №1(4); с. 188

51. Рабинер Л1 Р., Тоулд Б: Теория и применение:цифровой обработки сигналов. — Mi r Мир, 1978.

52. Самарекий A.A. Введение в теорию разностных схем: М.: Наука, 1971, - 553 с.

53. Самарский A.A., Г'улин A.B. Численные методы. М;: Наука; 1989, -432 с. .

54. Сергиенко А. Б. Цифровая обработка сигналов. — СПб.: Питер, 2003.

55. Смирнов В. И. Курс высшей математики, том 1. — М-;: Физматлит, 1958.

56. Солонина А. И., Улахович Д. А-., Яковлев Л. А. Алгоритмы и процессоры цифровой обработки сигналов. — СПб.: БХВ-Петербург, 2002'.

57. Трауб Дж., Васильковский F., Вожьняковский X. Информация, неопределённость, сложность. — М.: Мир, 1988.

58. Успенский В. А. Треугольник Паскаля. — М.: Наука, 1979:98

59. Успенский В. А., Семёнов A. JI. Теория алгоритмов: основные открытия и приложения. — М.: Наука. Гл. ред. физ.-мат. лит., 1987.

60. Фаддеев М.А. Марков К.А. Численные методы (учебное пособие). -ННГУ, 2010. 158 с.

61. Формалёв В. Ф., Ревизников Д.Л. Численные методы. — М.: ФИЗМАТЛИТ, 2004.

62. Ханов В.Х., Никитин Д.А. Алгоритм анализа числовых последовательностей // Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева. — Красноярск, 2006. —№ 6 (13). —С. 11-15.

63. Хашин С. И. Интерполяционный метод сжатия графики // Вестн. Иван, гос. ун-та. 2002. Вып. 3. — С. 140-143.

64. Хашин С. И. Семнадцатиточечная интерполяционная формула от 2 переменных // Вестн. Иван. гос. ун-та. 2003. Вып. 3. — С. 133-137.

65. Хэмминг Р.'В. Теория кодирования и теория информации. — М.: Радио и связь, 1983.

66. ХэммингР. В. Цифровые фильтры. —М. Сов. Радио, 1980.

67. Шахтарин Б. И. Обнаружение сигналов. — М.: Гелиос АРВ, 2006.

68. Щипин К. С. Система прогнозирования на основе многокритериального анализа временных рядов. — М. МИСиС, 2004.

69. Jean-Paul Berrut, Richard Baltensperger, Hans D. Mittelmann Recent developments in barycentric rational interpolation // International Series of Numerical Mathematics Vol. 151. — Basel: Birkhauser, 2005. — P:27-51.

70. Daubechies. Ten lectures on wavelets. SPAM, Philadelphia, PA, 1992.

71. Kailath Т., Poor H.V. Detection of stochastic processes // IEEE Trans. 1998. V. IT-44, № 6. P. 2230-2259. Русский перевод в 71.: Кайлат Т., Hyp X. Обнаружение стохастических процессов.

72. David Е. Newland, "Harmonic wavelet analysis," Proceedings of the Royal Society of London, Series A (Mathematical and Physical Sciences), vol. 443, no. 1917, p. 203-225 (8 Oct. 1993).

73. Runge К. Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten (нем.) // Zeitschrift für Mathematik und Physik. — 1901. — T. 46. — C. 224—243.

74. Sedgewick, R. Algorithms. —Addison-Wesley Publishing Company Inc., 1983.

75. C. Schneider, W. Werner Some new aspects of rational interpolation // Mathematics of Computation, №47 (175). — 1986. — P. 285-299.

76. WienerN. Extrapolation, Interpolation and Smoothing of Stationary Time Series, with Engineering Applications. New York: Wiley, 1949.