Содержание к диссертации
Введение
1. Анализ методов построения интерполирующей функции. Постановка задачи 11
1.1. Методы интерполяции 11
1.2. Разностные схемы 14
1.3. Дискретные преобразования 15
1.4. Постановка задачи 16
1.4.1. Цифровая фильтрация 17
1.4.2. Методы синтеза БИХ-фильтров по заданной импульсной характеристике 21
Выводы к главе 26
2. Синтез БИХ-фильтра по началу его импульсной характеристики 28
2.1 Алгоритм расчёта цифрового рекурсивного фильтра по началу импульсной характеристики 28
2.2. Область применимости алгоритма А1 33
Выводы к главе 51
3. Автоматическая интерполяция числовых данных функциями из заданного» множества с наименьшим количеством параметров 52
3.1. Определение функциональной зависимости по коэффициентам соответствующего фильтра 52
3.2. Расширение области применения 61
3.2.1. Линейная комбинация функций, уже известных алгоритму. 61
3.2.2. Проверка применимости к произвольным функциям 64
3.2.3. Замена функции рядом Тейлора 71
3.2.4. Использование метода для автоматического определения аппроксимирующей функции 73
3.3. Описание системы автоматической интерполяции, основанной на предложенном методе 76
3.4. Сравнение с другими методами отыскания функции, график которой проходит через заданный набор точек 85
Выводы к главе 92
Заключение 94
Список литературы 95
Приложение 1. Программа поиска функциональных зависимостей в числовых последовательностях 101
Приложение 2 104
Приложение 3 107
- Методы синтеза БИХ-фильтров по заданной импульсной характеристике
- Область применимости алгоритма А1
- Проверка применимости к произвольным функциям
- Описание системы автоматической интерполяции, основанной на предложенном методе
Введение к работе
Актуальность темы. Существует ряд классических методов построения функций, график которых точно проходит через заданный набор точек. Это различные интерполяционные формулы, а также различные дискретные преобразования. Полученную функцию (интерполянт) можно использовать для вычисления значений функции между исходными точками (интерполяция), за их пределами (экстраполяция), а также компактной записи или дальнейшего анализа исходных данных. Для интерполяции и экстраполяции также могут использоваться разностные схемы, хотя они и не дают точной записи интерполянта.
В качестве интерполянтов чаще всего используются многочлены, суммы экспонент, Фурье-суммы, сплайны. Количество слагаемых в указанных функциях определяется количеством исходных точек. Вид интерполянта в конкретной задаче обычно выбирается на основании дополнительной информации о зависимости между исходными значениями. То есть упомянутые методы не предназначены для поиска наиболее подходящей модели данных — каждый из них уже предполагает конкретную модель. Кроме того, классические методы не предназначены для построения интерполянта в виде сумм функций из разных классов (например, сумма экспонент и синусоид).
Таким образом, классические методы построения функций, график которых точно проходит через заданный набор точек, удобно использовать, когда вид интерполянта заранее выбран и остаётся только определить его параметры (коэффициенты). В случае если вид интерполянта заранее неизвестен, либо в заданном множестве функций необходимо определить интерполирующую функцию с наименьшим количеством параметров, то использование данных методов становится затруднительным, так как для каждого отдельного вида функции приходится выполнять отдельную процедуру построения интерполянта.
При обработке больших наборов данных в различных областях науки и техники кроме методов интерполяции не менее часто используются методы аппроксимации, образующие вместе группу методов приближения функций. Это связано с тем, что в значениях измеряемой величины практически всегда присутствует погрешность. Методы аппроксимации могут быть как модификациями методов интерполяции (например, аппроксимирующий сплайн), так и независимыми методами.
В связи с этим разработка метода, позволяющего автоматически определять из множества одномерных известных функциональных зависимостей такую, которая описывает исходные данные с наименьшим количеством параметров, представляет интерес. При этом полезными свойствами такого метода могли бы быть: возможность искать интерполянт в виде суммы функций из разных классов, а также возможность определения
функции, которая хорошо аппроксимирует заданный набор точек, если интерполирующей функции найти не удалось.
Цель исследования: разработка эффективного метода автоматического определения интерполирующей функции с наименьшим количеством параметров из некоторого множества функций, позволяющей настраивать множество видов искомых интерполянтов.
Задачи исследования:
Провести анализ современных методов интерполяции.
Разработать алгоритм синтеза рекурсивного цифрового фильтра (фильтра с бесконечной импульсной характеристикой, БИХ-фильтра), значения отсчётов импульсной характеристики которого задаются некоторой одномерной функциональной зависимостью.
Разработать метод определения вида интерполянта и вычисления её параметров исходя из коэффициентов БИХ-фильтра, получаемого с помощью предложенного алгоритма синтеза.
Разработать программную реализацию, использующую предложенный метод автоматической интерполяции числовых данных.
Методы исследования. В ходе исследования использовались основные положения цифровой обработки сигналов, линейной алгебры, функционального анализа, численных методов алгебры и анализа, а также теории алгоритмов.
Научная новизна работы состоит в следующем.
Доказана возможность синтеза рекурсивного цифрового фильтра по значениям отсчётов его импульсной характеристики, описываемой любой функцией f из определённого множества Ф (оно названо множеством функций, известных алгоритму). Показан алгоритм синтеза таких фильтров.
Разработан метод автоматической интерполяции на основе разработанного алгоритма синтеза рекурсивного цифрового фильтра, отличающийся от аналогов возможностью одновременного обнаружения функций нескольких видов, множество которых можно настраивать.
Разработаны способы расширения множества Ф; показана применимость алгоритма синтеза рекурсивного цифрового фильтра по импульсной характеристике, когда/является любой линейной комбинацией функций из множества Ф.
Программная реализация результатов работы. Программа поиска функциональных зависимостей в числовых последовательностях «FunSearch 1.0» прошла экспертизу и зарегистрирована в Отраслевом фонде алгоритмов и программ при Федеральном агентстве по образованию (№ государственной регистрации 50200700388, per. № ОФАП 7729).
Практическая значимость исследований. Разработанный алгоритм синтеза БИХ-фильтра по началу его импульсной характеристики имеет ряд
возможных приложений. В данной работе наиболее глубоко исследовано его применение для автоматической интерполяции числовых данных. Особенности алгоритма позволили разработать вычислительно эффективный метод для одновременного поиска в данных нескольких классов функций. На защиту выносятся:
Разработанный алгоритм синтеза рекурсивного цифрового фильтра по началу импульсной характеристики, члены которой задаются математической функцией, самостоятельно определяет необходимый порядок фильтра.
Теоремы существования и единственности БИХ-фильтров, импульсные характеристики которых определяются математическими функциями из указанного множества.
Метод автоматической интерполяции, основанный на предложенном алгоритме синтеза БИХ-фильтров, способен отыскивать наиболее простой интерполянт в выбранном множестве функций, а также позволяет настраивать это множество функций.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (2007 г.), Международной конференции IEEE по управлению и связи SIBCON-2007, международной научно-технической конференции «Радиолокация, навигация, связь» (RLNC-2007), Всероссийской научно-практической конференции с международным участием «Информационные технологии и математическое моделирование» (ИТММ-2009), международной научной конференции «Теоретические и прикладные проблемы математики, механики и информатики» (Караганда, 2010), а также на научно-практических семинарах кафедры безопасности информационных технологий СибГАУ (2006, 2009, 2011 г.).
Публикации. По теме диссертации опубликовано 12 печатных работ. Полный список публикаций представлен в конце автореферата. 3 работы опубликованы в изданиях, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и трех приложений общим объемом 106 с. Список использованной литературы содержит 83 наименования.
Методы синтеза БИХ-фильтров по заданной импульсной характеристике
Нахождение рекурсивного цифрового фильтра означает отыскание всех его коэффициентов a.k и Ь , которые однозначно определяют процесс фильтрации (а, значит, и импульсную характеристику) в соответствии с рекурсивным выражением (1.18).
В различных источниках можно встретить описание одних и тех же методов синтеза фильтров, но представляемых как методы синтеза цифровых фильтров в одних случаях [1, 7, 31, 70] и дискретных — в других [58]. Дело в том, что все эти методы являются, по сути, методами синтеза дискретных фильтров, а цифровые фильтры получаются из синтезированных фильтров путём квантования их коэффициентов. Процесс квантования универсален и не зависит от предшествующего метода синтеза фильтра. Поэтому если работа не посвящена эффектам конечной разрядности чисел в цифровых фильтрах, то разницей между цифровыми и дискретными фильтрами можно пренебречь. В этой работе используется только термин «цифровой фильтр», а эффекты квантования не рассматриваются.
Существует множество методов синтеза дискретных фильтров. Уделим внимание только тем из них, которые предназначены для расчёта цифровых фильтров по импульсной характеристике. Классификация методов синтеза ЦФ часто проводится по следующим двум признакам:
по типу получаемого фильтра:
рекурсивный;
нерекурсивный.
по наличию аналогового прототипа:
с использованием аналогового прототипа (уже рассчитанного аналогового фильтра);
без аналогового прототипа (прямые методы синтеза);
использование некоторой процедуры оптимизации расположения полюсов и нулей в z-плоскости, при котором обеспечивается-аппроксимация в том или ином смысле заданной характеристики фильтра.
Рассмотрим методы синтеза рекурсивных ЦФ, в которых каким-нибудь образом в качестве исходных данных используется импульсная характеристика синтезируемого цифрового фильтра. Таких методов совсем немного, так как расчёт ЦФ на практике обычно ведётся исходя не из знания импульсной характеристики, а совсем из других параметров. Как правило, спецификация требований к фильтру состоит из граничных частот полос подавления и пропускания и максимальных отклонений в каждой из этих полос [1], а импульсная характеристика строится уже после расчёта фильтра, если это необходимо.
Во-первых, к интересуемым методам относится метод инвариантного преобразования импульсной характеристики, принадлежащий классу методов синтеза с использованием аналогового прототипа. Его описание можно найти в [1, 55, 58]. Метод основан на следующих предпосылках. Сначала разрабатывается аналоговый фильтр с частотными характеристиками, удовлетворяющими поставленной задаче. Рекурсивный цифровой фильтр будет рассчитываться посредством дискретизации импульсной характеристики аналогового прототипа. Это возможно, так как импульсная характеристика аналоговой системы с сосредоточенными параметрами может быть представлена в виде суммы экспоненциальных слагаемых двух видов:
hx(t)=Aept (1.23)
h2{f)=AtnePt (1.24)
Для каждого такого слагаемого можно выполнить дискретизацию и найти Z-преобразование полученной последовательности. Выполнив это, найдём функцию передачи дискретного фильтра, импульсная характеристика которого представляет собой дискретизированную импульсную характеристику аналогового прототипа. Этот метод подходит для расчёта фильтров низких частот и полосовых фильтров и непригоден для синтеза фильтров высоких частот (ФВЧ) и режекторных фильтров1.
Однако, несмотря на приведённые теоретические предпосылки, на самом деле непосредственно импульсная характеристика аналогового фильтра для расчёта дискретного фильтра в данном методе не используется. Исходной является передаточная функция аналогового фильтра, которая для упрощения раскладывается на элементарные слагаемые, обратное преобразование Лапласа каждого из которых имеет вид (1.23) или (1.24). Название же метода определил тот факт, что импульсная характеристика получаемого дискретного фильтра ЫпТ) состоит из отсчётов импульсной характеристики аналогового прототипа h(t), взятых в дискретные моменты времени t = пТ, п = О, 1, ... (рис. 1.2), а также то, что импульсная характеристика используется при доказательстве корректности метода.
Среди других методов синтеза — прямых и с использованием процедуры оптимизации — имеется 2 метода, более близких к интересующей задаче, то есть они используют для расчёта значения отсчётов импульсной характеристики. Так как импульсная характеристика БИХ-фильтра бесконечна, они на самом деле используют некоторое количество её начальных отсчётов.
Среди прямых методов синтеза имеется метод, основанный на аппроксимации Паде. Данный вид аппроксимации предназначен для аппроксимации степенных рядов рациональной функцией. Предполагается, что значения отсчётов импульсной характеристики являются значениями степенного ряда, а передаточная функция рекурсивного ЦФ, как известно, является рациональной функцией. Таким образом, результатом данного метода являются коэффициенты передаточной функции. Как показано в [55, с. 295-297], результат данного метода может содержать значительные отклонения аппроксиманта, поэтому там же предлагается использовать коэффициенты фильтра, полученные таким методом, в качестве начальных значений при расчёте БРІХ-фильтров более сложными методами оптимизации.
Среди прямых методов синтеза с использованием процедуры оптимизации более близок к решению описанной задачи метод Прони, разработанный в 1795 г. Гаспаром Рише (бароном де Прони) для подгонки экспоненциальной модели под экспериментальные данные при исследовании физических свойств газов. Современный вариант метода Прони обобщён на модели, состоящие из затухающих синусоид, и модели, которые аппроксимируются экспоненциально-гармоническими суммами следующего вида [25].
Подробное описание метода можно найти в [38, 54], где показано, что он является процедурой отыскания полюсов некоторого авторегрессионого процесса. Метод Прони позволяет находить фильтр, импульсная характеристика которого аппроксимирует заданную импульсную характеристику. Отдельные этапы метода не имеют аналитических методов решения и требуют больших вычислительных затрат. Сначала при помощи ковариационного метода анализа авторегрессионных моделей определяются коэффициенты знаменателя передаточной функции. Затем коэффициенты числителя передаточной функции фильтра подбираются так, чтобы определённое количество первых отсчётов его импульсной характеристики совпадали с исходным вектором. Устойчивость фильтра не гарантируется. Другой недостаток метода заключается в том, что для- его успешного применения необходимо заранее знать порядок фильтра. Если выбрать порядок меньше, чем необходимо, то отклонение импульсной характеристики полученного фильтра от заданной будет очень велико. Кроме того, этот метод абсолютно не учитывает того, что отсчёты.импульсной характеристики могут быть значениями функции, отличной от суммы затухающих экспонент или гармоник, что важно для поставленной в данной работе задачи.
Как уже говорилось выше, цифровые фильтры обычно рассчитываются исходя из других данных, нежели на основе только импульсной характеристики. Поэтому два приведённые методы синтеза ЦФ исчерпывают весь список подобных методов. При этом они не пригодны для решения поставленной задачи.
Область применимости алгоритма А1
Возникает очевидный вопрос: при каких условиях L—M-N-1 линейных уравнений от М+N+l неизвестных линейно зависимы от остальных М+N+l уравнений построенной системы? Как оказалось, это выполняется, как раз тогда, когда члены последовательности Y являются отсчётами ряда функций Дх), взятыми с постоянным шагом. Установление всех таких функций является важным для предложенного метода. На данный момент доказано [48], что/может быть
любой полиномиальной функцией;
любой показательной функцией;
синусоидой или косинусоидой;
Ниже приведятся доказательства для каждого класса функций.
Теорема 1. Для последовательности Y длины L 2(n + l), члены которой являются равноотстоящими отсчётами полиномиальной функции одного переменного у, = рп(г) = CXQ-I" + ctyinA + ... + ап, аФ О, и заданы любые (п+l) подряд идущих члена ут, ут+\,... ут+п, существует единственный рекурсивный цифровой фильтр порядка п+l (M=n+l, N=n), импульсная характеристика которого совпадает с Y.
Доказательство. Часть 1. Пусть т = 0, а отсчёты функции берутся с шагом равным единице. Используя выражение (2.1) построим начальную систему уравнений для М+N+l первых элементов последовательности Y, приняв её за импульсную характеристику искомого ЦФ. Матрица системы:
Разделим.матрицу Р на 4 равных части, как показано выше, и приведём её эквивалентными преобразованиями к верхнему треугольному виду. Следует обратить внимание на особый вид матрицы Р. Видно, что при приведении к треугольному виду второй и третий квадрант матрицы не изменятся совсем, а первый квадрант изменится, но при этом совсем неважно как (вычитая столбцы из левой части, умноженные на соответствующий коэффициент, его вообще можно привести к нулевому виду). Поэтому имеет смысл, для краткости записей, рассматривать эквивалентные преобразования только четвёртого квадранта (назовём его подматрицей Z), при этом его; как и. матрицу Р, надо привести к верхнему треугольному виду.
Видно, что матрица Z является теплицевой. При приведении матрицы к треугольному виду будем производить над ней такие эквивалентные преобразования, чтобы- из элементов, находящихся на одной диагонали вычитались одинаковые выражения, и таким образом матрица останется теплицевой.
Такими преобразованиями может быть, например, следующая последовательность действий (будем нумеровать строки и столбцы с нуля): 1а) отнять п-й столбец из всех столбцов с нулевого по (я—1)-й; 1 б) отнять нулевую строку из всех строк с первой по я-ю; 2а) отнять (k+l) раз («—1)-й столбец из всех столбцов с нулевого по (я— 2)-й, где к — разность индексов столбцов.
Т.е. ранги матриц системы равны. Из вышеприведённого алгоритма нетрудно посчитать, что zn(ak) = -п\-а0. Таким образом, система обладает полным рангом при а0 Ф 0, что соответствует условию теоремы.
Следовательно, она имеет единственное решение (коэффициенты цифрового фильтра порядка п+1).
Пока что доказана справедливость теоремы только для случая, когда Y является последовательностью отсчётов полинома степени п, взятыми с шагом равным единице. Докажем, что она справедлива и в случае любого постоянного шага.
Данная система имеет единственное решение относительно а, для фиксированного т 0. Значит, если фиксированы у1} і = т,т + п, то фиксированы коэффициенты полинома аг А если фиксированы коэффициенты полинома, то фиксированы у„ і = 0,п, так как они однозначно выражаются через коэффициенты полинома. Следовательно, при т 0 справедливо доказательство из части 1 данной теоремы. Теорема доказана.
Доказательство теорем ЗА и ЗБ и всё что будет ниже говориться о синусоидальной функции, в равной степени справедливо и для косинусоиды, так как, фактически, косинусоида является синусоидой, смещённой на 7с/2 по оси абсцисс. А в решаемой задаче (интерполяция) в общем случае неважно, проходит ли искомая функция через начало координат.
Ниже приводятся ещё две теоремы о существовании рекурсивного ЦФ для случая, когда отсчёты его импульсной характеристики являются значениями произвольной периодической функцией при условии, что период функции кратен расстоянию между взятыми отсчётами. Данные теоремы представляются как дополнительный результат, так как, в отличие от предыдущих теорем, они не позволяют идентифицировать вид функции, а только позволяют определить периодичность исходной числовой последовательности и длину периода.
Проверка применимости к произвольным функциям
Рассмотрим теперь возможность расширения метода на остальные функции. Пусть необходимо обнаруживать участки, которые описываются функцией/ Эта функция может и не принадлежать ни одному виду функций из списка, представленного в п. 2.2, а также не являться их линейной комбинацией. Необходимо определить порядок- соответствующего фильтра и правила, которым должны соответствовать его коэффициенты.
Если порядок соответствующего БИХ-фильтра по какой-то причине не удается-точно определить, либо/вообще не является линейной комбинацией известных алгоритму функций, то можно- попытаться найти- подходящий порядок перебором. Именно так были предварительно (до проведения доказательства Теорем 1-4) найдены порядки.ЦФ и правила для обнаружения уже упомянутых функций — полиномов небольших степеней, показательных, синусов и произвольных периодических функций. В» Прил. 2 приведён листинг программы, выполняемой в системе MATLAB, которая перебирает порядки ЦФ от второго до указанного и выводит на экран соответствующие цифровые фильтры, если они были найдены. Минимальный порядок вычисленного фильтра и будет, скорее всего, ответом — то есть порядком ЦФ, соответствующего функции / Например, для функции, приведённой в листинге (Прил. 2) для примера, соответствующий БИХ-фильтр имеет порядок равный трём. Но если при выполнении программы указать больший порядок, то будут вычислены и фильтры больших порядков, но при этом можно будет видеть среди их коэффициентов «чистые» нули в количестве, равном разнице между их порядком и минимальных порядком найденного фильтра. То есть среди коэффициентов ЦФ 4-го порядка будет один нулевой коэффициент, 5-го порядка — два нулевых коэффициента, и т.д. Под «чистыми» нулями подразумеваются коэффициенты, которые точно равны нулю, а не близки к нему.
Принцип работы программы следующий. Сначала массив достаточной длины заполняется значениями анализируемой функции, взятыми с шагом равным единице. От размера массива зависит количество проверяемых далее порядков фильтра. После этого в цикле для каждого порядка от второго до некоторого вычисленного выполняется следующее. Сначала строятся матрицы системы уравнений (2.2). Затем вычисляются их ранги. Если они не равны, то программа переходит к проверке следующего порядка. Если равны, то вычисляется решение системы уравнений. Этим решением являются коэффициенты цифрового фильтра текущего порядка. Далее проверяется, удовлетворяет ли это решение всему массиву, полученному на первом шаге. Суть проверки таковаг вычисляется импульсная характеристика вычисленного фильтра и поэлементно сравнивается с исходным массивом. Если отклонение хотя бы в одной позиции превышает заданное небольшое отклонение, то происходит переход к следующему порядку фильтра. Если же для всех элементов проверка удачно пройдена, на экран выводятся текущий порядок фильтра и его коэффициенты, а затем происходит переход к следующему порядку фильтра. Сравнение элементов массива значений функции и импульсной характеристики выполняется, с использованием отклонения, из-за использования арифметики конечной разрядности. Если вычисленный ЦФ имеет нецелые коэффициенты (а для «сложных» функций это справедливо в большинстве случаев), то при вычислении отсчётов импульсной характеристики имеет место накапливаемая погрешность.
Из-за наличия этой погрешности результат работы программы оказывается не таким однозначным, как это выглядит в теории. Поскольку погрешность накапливаемая, то, выбрав достаточно большую длину массива, можно добиться того, что при любом порядке фильтра он не будет проходить вышеуказанную проверку. На основании этих рассуждений рекомендуется выбирать эту длину такой, чтобы проверке были подвергнуты фильтры порядков от А:-го до к + 3...5, где к — предполагаемый минимальный возможный порядок соответствующего фильтра для анализируемой функции. Поскольку к заранее, как правило, неизвестно, то для надёжности рекомендуется производить несколько проходов программы для различных размеров массива значений/
Несколько проходов программы,следует выполнять также ещё по одной причине. Следует выполнить несколько попыток вычисления с разными наборами параметров функции (см. комментарии в листинге). Например, для функции у(х) = С\1(с2 х + с3) + с,\, в зависимости от разных значений параметров ch минимальный порядок соответствующего БИХ-фильтра может оказаться 6, 7, 9, 10 и др. Возможно это связано с различными ограничениями, которые накладываются на с,-, то есть алгоритм А1 не является работоспособным для всего множества таких функций, как это например происходит с полиномами. Вероятно, определить эти ограничения поможет проведение доказательства теоремы для данного вида функций, подобной теоремам из параграфа 2.2. Пока такого доказательства нет, поэтому функцияу{х) = С\1{СУХ + с3) + с4 в данной работе не приводится среди функций известных алгоритму.
Таким образом, для того, чтобы с большой степенью достоверности вынести предположение о значении минимального значения порядка БИХ-фильтра, члены импульсной характеристики которого описываются заданной функцией, необходимо чтобы это подтверждалось результатами как минимум нескольких вычислений. После того как определён минимальный возможный порядок БИХ-фильтра, соответствующего интересующей функции, можно приступать к определению правил, которым должны соответствовать коэффициенты таких фильтров, чтобы по ним можно было определить наличие такой функции в анализируемых данных, а затем вычислить её параметры. Для определения правил использовался следующий подход. В интересующую функцию подставлялось несколько десятков различных сочетаний параметров, затем для каждой такой функции вычислялся соответствующий ЦФ. После этого параметры функции и коэффициенты фильтра заносились в таблицу и анализировались. Сначала выявлялись ключевые правила, общие для всех наборов коэффициентов, уникальные для данного вида функции, по которым можно было бы её однозначно идентифицировать.
Для «простых» функций такие правила, как уже указывалось выше, очень просты, и поэтому выявить их очень просто. Примеры таких правил приведены в табл. 3. Суть их в том, что у всех «простых» функций по определению коэффициенты обратной связи постоянны и имеют определённые значения для конкретного вида функции. Например, если вычислить для 20-ти разных квадратичных функций соответствующий фильтр, то у всех них коэффициенты ОС будут одинаковы: -3, 3, -1. При первоначальном анализе функции, скорее всего, будет неизвестно какая она — «простая» или «сложная». Определить это можно будет сразу же — если коэффициенты обратной связи всех полученных фильтров одинаковы, значит функция «простая», иначе — «сложная». Таким образом, правилом для идентификации «простой» функции будут полученные значения коэффициентов обратной связи соответствующих ЦФ.
Обнаружение «сложных» функций также производится по коэффициентам ОС. Однако их значения уже зависят не только от вида функции, но и частично от её параметров. Приведём пример для синусоидальной функции видау(х) = = Ci"sin(c2 je + с3) + с4 (табл. 8).
Описание системы автоматической интерполяции, основанной на предложенном методе
Итак, выше была описана» методика обнаружения зависимостей, форма которых; описывается любой функцией из определённого множества. Также сказано о возможности, применения методики в случае; когда искомая функция является конечной суммой, таких функций: Система обнаружения, основанная: на такой; методике, должна обладать некоторой базой знаний, о функциях, - которые она сможет обнаруживать... Такая база» знаний: должна1 содержать:
информацию, необходимую для; идентификации; определённой зависимости;
правила для, нахождения; значений параметров функции из значений коэффициентов соответствующего фильтра:
В качестве: идентифицирующей, информации для «простых» функций1 выступают точные значения; коэффициентов обратной связи соответствующего; фильтра; а для «сложных», функций — значения коэффициентов ЦФ и соотношения между ними.
Работа системы обнаружения должна осуществляться в»соответствии со следующей- методикой. Исходные данные для анализа либо уже имеются целиком, либої они в; цифровом; виде поступают на вход системы В; реальном времени. На первом этапе методики выполняется алгоритм; AT. То есть для начала исходной последовательности отсчётов- выполняется синтез соответствующего фильтра; Методика может использоваться для одновременного обнаружения различных функций, а значит, им могут соответствовать фильтры разных порядков. Таким образом, для; того, чтобы проверить в последовательности наличие всех функций из базы знаний, надо в худшем случае совершить N попыток синтеза БИХ-фильтра, где N - количество разных порядков ЦФ, соответствующих функциям из базы знаний. Для нахождения каждого такого фильтра необходимо 2к первых элементов исходной последовательности, где к — порядок фильтра. Во избежание этого алгоритм А1, построен так, что непосредственное вычисление БИХ-фильтра каждого порядка не выполняется. Он находит минимальный порядок ЦФ, соответствующего данной последовательности, при котором он является единственным, а уже потом вычисляет его.
После вычисления фильтра некоторого порядка к нужно- по его коэффициентам проверить наличие всех функций, которым соответствует фильтр такого порядка. Если для текущего порядка фильтра проверка не дала положительного результата (то есть полученные коэффициенты не соответствуют ни одному правилу из базы знаний), следует проверить фильтры меньших порядков.
Если в результате проверки оказалось, что начальные элементы последовательности не подчиняются ни одной функциональной зависимости из базы знаний, надо отбросить первый рассматриваемый элемент и повторить проверку для оставшейся части последовательности.
Когда найден БИХ-фильтр, коэффициенты которого говорят о том, что элементы последовательности, используемые при его вычислении, описываются функцией известной алгоритму, следует определить, на сколько следующих членов последовательности распространяется найденная функциональная зависимость. Суть такой проверки сводится к вычислению импульсной характеристики найденного фильтра и её поэлементному сравнению с рассматриваемой последовательностью. Первые 2к элементов совпадают по определению, так как они использовались при вычислении ЦФ как первые отсчёты импульсной характеристики.
После того, как длина участка последовательности, подчиняющегося найденной зависимости, определена, можно сохранить всю полученную информацию об этом участке и повторить проверку для оставшейся части последовательности. В качестве сохраняемой информации могут выступать индекс первого элемента участка, длина участка (количество членов последовательности), идентификатор типа найденной функции, коэффициенты соответствующего фильтра. Коэффициенты фильтра нужны для вычисления значений параметров функции, поэтому вместо них можно хранить сами параметры.
Таким образом, после подобного анализа будут известны участки исходной последовательности, в точности подчиняющиеся полностью определённым функциям одного переменного.
Далее рассмотрим некоторые моменты, касающиеся оптимизации скорости работы описанной системы обнаружения: оптимизация, перебора порядков фильтра, возможность настройки на нужные виды функций и др.
Процесс перебора фильтров всех порядков можно реализовать по-разному. Наиболее разумным представляется перебор от больших порядков к меньшим, так как фильтры более высоких позволяют обнаружить более сложные функции, охватывая при этом на этапе вычисления коэффициентов ЦФ большее количество- элементов исходной последовательности. Именно такой подход использовался в программной авторской реализации метода. Если для текущего порядка N фильтр не является- единственным, или он является единственным, но его коэффициенты не удовлетворяют ни одному правилу из базы знаний, то следующим вычисляется фильтр порядка iV-І. И так до минимального рассматриваемого порядка или пока не будет найден ЦФ, указывающий на наличие некоторой функциональной зависимости, известной алгоритму. Может показаться, что такой перебор не совсем оптимален, так как, согласно ему, первыми будут выполняться вычислительно более сложные действия (решения систем уравнений больших порядков), и если на самом деле элементы последовательности подчиняются одной из наиболее простых функций, либо вообще никакой не подчиняются, то большое количество вычислений будет произведено впустую. Однако была найдена закономерность, позволяющая ускорить переход к фильтру нужного порядка. Если при вычислении ЦФ по алгоритму А1 оказалось, что решаемая система уравнений имеет неполный ранг и он отличается от полного ранга на число г 2, то следующий ЦФ, который следует вычислять, должен иметь порядок на г 12 меньше, чем текущий. Вычисление промежуточных ЦФ можно пропустить, так как все соответствующие СЛАУ будут также иметь неполный ранг.
Кроме того, при переборе порядков фильтров от высших к низшим, при формировании каждой следующей системы уравнений не используется новых элементов исходной последовательности- (используется только часть тех, что используются на текущем шаге). Поэтому — с учётом архитектуры большинства существующих вычислительных систем — можно утверждать, что с большой долей вероятности все данные, требуемые для формирования новой СЛАУ, уже будут в кэш-памяти. А значит, матрицы всех систем уравнений, кроме первой, будут формироваться очень быстро.
Разумеется, возможны различные способы оптимизации, зависящие от специфики конкретного приложения. Например, если известно, что в анализируемых данных будет преобладать известная функциональная зависимость, то имеет смысл всегда начинать поиск с вычисления фильтра того порядка, который соответствует этой функции.
Стремление найти ЦФ минимального порядка обусловлено желанием найти функцию с наименьшим числом параметров, описывающую элементы последовательности. При этом поиск не предлагается начинать с меньших порядков ЦФ из-за вероятности обнаружения более простых функций, которые будут действовать на коротких участках исходной последовательности, и при этом они не будут давать обнаружить «более сложную» функцию, действующую на более длинном участке. Например, вместо длинного участка некоторой периодической функции будет обнаружено много коротких участков, подчиняющихся различным показательным или полиномиальным зависимостям. Если же никакой «сложной» функции на данном участке нет, а действительно имеются только более простые функции (т.е. с меньшим числом параметров), то при спуске от больших порядков ЦФ к меньшим они всё равно будут найдены.
Учитывая приведённое выше описание, можно изобразить блок-схему работы предлагаемой системы обнаружения зависимостей в следующем виде (рис. 3.3).
