ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.03.2024
Просмотров: 3
Скачиваний: 0
ИНФОРМАЦИОННАЯ ТЕХНИКА. ЧАСТЬ 4.
Королев С.А.
каф. 2
Алгоритмы обработки информации
В ИИС реализуется множество алгоритмов обработки информации в соответствии с функциями системы, особенностями контролируемого объекта или процесса, с особенностями структуры системы.
Выделим следующие группы алгоритмов обработки информации:
-
Алгоритмы, связанные с централизацией выполнения определенных функций (выполнение одним устройством операций с сигналами от разных источников):
-
алгоритмы дискретизации во времени
-
алгоритмы массового обслуживания
-
алгоритмы сжатия информации
-
Алгоритмы повышения помехоустойчивости или нейтрализации влияния внешних факторов:
-
алгоритмы фильтрации
-
алгоритмы коррекции
-
алгоритмы стат. анализа (определение вероятностных характеристик, корреляционных функций, спектральных плоскостей и т.д.)
-
Алгоритмы восстановления значений сигналов и аппроксимации:
-
алгоритм восстановления дискретных сигналов (по отсчетам)
-
алгоритмы приближения
-
алгоритм оптимального обнаружения и различения сигналов
-
алгоритм обработки эмпирических (экспериментальных данных) зависимостей
Варианты задач обработки информации:
-
на непрерывном или дискретном множестве входных значений
-
ансамбль входных значений – во времени или в пространстве
-
в условиях шумов или нет
Нас прежде всего интересует информационный аспект реализации алгоритмов обработки информации (т.е. неоднозначность или погрешность преобразований), а не их техническая реализация.
Алгоритмы восстановления значений сигналов и аппроксимации
Различают следующие классы:
-
алгоритмы экстраполяции
-
алгоритмы интерполяции
-
алгоритмы приближения
Задачи 1. и 2. часто возникают при необходимости восстановления значений сигналов, теряемых вследствие их дискретизации. Использование для этих целей интерполяционных рядов Котельникова для ИИС реального времени неэффективно, но и даже невозмоно.
Экстраполяция
– исходный сигнал.
– отсчеты сигнала
Построение прогноза значений сигнала на по отсчетам до момента времени включительно. Простейший случай – по одному отсчету . В этом случае используют экстраполяцию нулевого порядка или 0 ступенчатую экстраполяцию.
Считая стационарным случайным процессом, получим:
В конце интервала экстраполяции ошибка увеличивается и равна:
Рассмотрим случай, когда сигнал зашумлен, тогда (считаем шум аддитивным):
Оценка средней по интервалу дисперсии ошибки:
Для оптимизации экстраполяции зашумленного сигнала можно использовать алгоритм статистической экстраполяции по нескольким предыдущим отсчетам (т.е. как линейную функцию взвешенных отсчетов с шумом).
– неопределенные коэффициенты, их следует определить из условия минимизации СКО.
Тогда, считая шум центрированным и аддитивным:
Определение - из минимизации (по сути, это алгоритм оптимальной фильтрации), т.е. из системы уравнений:
Оптимизация по одному отсчету ( дает результат:
Следовательно,
Видно, что экстраполированное значение всегда ближе к среднему значению .
Линейная экстраполяция по двум точкам
Рассмотрим задачу с шумом:
В конце интервала экстраполяции:
Т.к. при
Если при этом , то
Считаем,
Алгоритм интерполяции
Возможна задача интерполяции по всем отсчетам (массив отсчетов есть). Имеем отсчеты сигнала . Оценка (восстановление) значений сигнала на интервале осуществляется в общем случае по значениям всех отсчетов , причем в точках отсчетов .
Применение алгоритмов интерполяции:
-
в ИИС реального времени – восстановление значений в по значениям отсчетов – используется запаздывание на шаг.
-
в системах идентификации пространств распределенных объектов или полей, например:
-
поле энерговыделения
-
таблицы параметров воды/пара
Простейшие алгоритмы интерполяций для ИИС
- линейная интерполяция
Ошибка восстановления значений сигнала:
Для середины интервала интерполяции:
Если то
Алгоритмы интерполяции, требующие использования вычислительных средств.
Сплайн-интерполяция
Сплайн представляет собой функции, склеенные из различных кусков многочленов по заданному базису. Если в качестве базисных функций выбрать функции вида: 1, то сплайны полиномиальные.
Преимущества: простота реализации и устойчивость к локальным возмущениям.
Функцию называют полиномиальным сплайном дефекта , если на отрезках между соседними узлами она принадлежит множеству полиномов степени не выше и имеет на заданной области изменения непрерывные производные порядка, не ниже .
Обычно используют сплайны с . Для задач интерполяции удобно использовать сплайны нечетных степеней. Сплайн первой степени реализует кусочно-линейную интерполяцию. Кубический сплайн при обеспечивает непрерывность второй производной на отрезке и находится решением системы линейных алгебраических уравнений.
Задана сетка (равномерная) на отрезке .
– исходная интерполируемая функция на сетке
Обозначим - вторая производная в точке . Она линейна на , тогда:
Далее:
-
интегрируем это выражение дважды на отрезке ;
-
то же самое выполним на отрезке ;
-
учтем требование для кубического сплайна: .
После двукратного интегрирования на отрезке получаем:
Полагая , находим
Следовательно, на отрезке с учетом граничных условий. Получаем систему алгебраических уравнений относительно неизвестных .
Рассмотрим функцию . Введем определения:
- первая нисходящая разность
- первая восходящая разность
– вторая разность (порядка два)
– первая разделенная разность
- вторая разделенная разность
где – вторая разделенная разность функции на точках .
Целесообразность использования сплайнов
При наличии большого количества точек-отсчетов при построении единого интерполирующего полинома потребуется использовать полиномы/многочлены больших степеней, что очень неудобно для вычислений, а также приводит к большой чувствительности решения к возмущениям.
Сплайн аппроксимация позволяет использовать много полиномов с небольшими степенями, обычно или .
Другие алгоритмы интерполяции (по формулам Лагранжа, Ньютона, Бесселя и т.д.) используются редко и только в системах обработки информации в объемах с распределенными параметрами.
Алгоритмы аппроксимации на принципах приближения
Применение:
-
Аналитическая градуировка датчиков;
-
Идентификация характеристик сигналов/ объектов управления/ контроля/ ИС;
-
Выявление эмпирических зависимостей;
-
Оценка значений параметров по косвенным измерениям.
Предметом аппроксимации могут быть как непрерывные сигналы или характеристики, так и дискретные наборы данных или отсчетов.
Особые классы задач связаны с аппроксимацией зашумленных данных.
Аппроксимирующие функции
Чаще всего в качестве аппроксимирующих функций используют либо степенные полиномы, либо полиномы, состоящие из ортогональных функций. Использование степенных полиномов:
Для идентификации коэффициентов полинома степени необходимо знать значения в точке. Если число точек (т.е. значений ) совпадает со степенью полинома , то задача – однозначная, и по сути получаем интерполирующий полином. Если степень меньше, то коэффициенты необходимо определять исходя из минимизации ошибки аппроксимации.
Т.е. система уравнений должна быть:
Решение относительно дает возможность определить аппроксимирующую функцию. Особенностью аппроксимации степенными полиномами является зависимость от всех значений функции и точек , поэтому при изменении набора данных приходится все пересчитывать.
Аппроксимация полиномами, состоящими из ортогональных функций
где – ортогональные функции. Для них при :
где - аппроксимируемая функция. Коэффициент зависит только от функции и может быть найден независимо от других коэффициентов.
Критерии точности аппроксимации
-
Среднеквадратичный критерий:
-
Равномерный критерий:
Оценки на дискретных множествах:
При аппроксимации ортогональными полиномами коэффициенты будут оптимальны с точки зрения минимума квадратичного критерия. В качестве аппроксимирующих многочленов, состоящих из ортогональных функций, могут быть использованы ряды Фурье, классические ортогональные многочлены, многочлены, построенные на функциях Уолсиа и другие.
Классические ортогональные многочлены
Классические ортогональные многочлены – это многочлены Чебышева, Эрмита, Лежандра, Лагерра и т.д.
Ортогональные полиномы Лежандра
|
ортогональны на отрезке
и т.д.
|
Ортогональные полиномы Чебышева первого рода
Ортогональность на с
|
Все экстремумы равны
|
Ортонормированные многочлены Чебышева
Многочлены Чебышева с единичным старшим коэффициентом
Нули многочленов Чебышева первого рода:
Экстремумы многочленов Чебышева первого рода:
Смещенные многочлены Чебышева
на отрезке - те же свойства.
Многочлены Чебышева второго рода
С единичным старшим коэффициентом:
Равномерные приближения
Аппроксимирующие полиномы, рассчитанные по МНК (отрезки рядов Фурье для ортогональных многочленов) в отдельных точках или областях могут давать ошибки, превышающие доступные. Аппроксимация по МНК применима для обработки результатов наблюдения, т.к. позволяет сглаживать локальные ошибки или шумы в отсчетах (например, аналитическая градуировка датчиков).
Однако в ряде задач ИИС необходимо гарантировать, чтобы ошибка не превышала ошибки от заданной величины, т.е. по норме: