1. Введение
Проблема эффективной обработки информации, получаемой с датчиков и приборов, является одной из основных в цифровых технологиях управления. Обычно на первом этапе они при необходимости приводятся к цифровому виду для того, чтобы обеспечить их обработку в цифровых вычислительных устройствах. Получаемые реальные данные, как правило, зашумлены и в процессе передачи подвергаются воздействию помех различного рода, поэтому актуальной является задача максимального устранения данных помех и погрешностей.
Одним из эффективных инструментов обработки данных обратной связи является решение избыточного числа линейных уравнений, решение которых достаточно исследовано в математике, с последующей фильтрацией семейства получаемых решений.
2. Постановка задачи
Рассмотрим решение следующей задачи. По получаемым данным обратной связи формируется L уравнений относительно переменных x1, x2, … , xn. Они соответствуют данным, получаемым в моменты времени t1, t2, … , tn.
Каждое уравнения с номером j (0 ≤ j ≤ n-1) имеет вид:
aj,1 × x1 + aj, 2 × x2+…+ aj, n × * xn =bj
Необходимо:
- найти все системы уравнений размерности n, которые имеют решения,
- число таких систем r,
- найти решения этих систем
- выполнить фильтрацию полученных решений этих систем.
3. Предлагаемый алгоритм решения задачи
Для алгоритма решения используем следующие структуры данных.
Входные данные:
1) массив pt размерности L указателей на исходные уравнения,
2) структуры str, в которых хранятся коэффициенты уравнений.
Выходные данные:
- алгоритм возвращает логическое значение true, если найдено хоть одно решение, и false – если нет, в случае true дополнительно возвращается:
- число найденных результатов r,
- массив решений sol [r].
Вспомогательные данные:
1) номер первой свободной строки ifirst = n,
2) массив перестановок sort[n],
3) массив pts размерности n указателей на уравнения текущей системы.
Общий алгоритм решения содержит следующие шаги:
- начальные действия,
- формирование первой системы А1 и определение её решения Х1,
- формирование всех последующих систем Аk (k > 1) и определение их решений Хk,
- фильтрация всех найденных решений.
3.1. Начальные действия алгоритма
- Засылка начальных значений в массив перестановок sort :sort[i]=i, (0 ≤ i ≤ n-1).
- Инициализация номера первой свободной строки ifirst = n.
3.2 Формирование первой системы А1 и определение ее решения Х1
Обратный ход. Подготовка треугольной матрицы системы А1.
Начиная со строки n-1, двигаясь вверх, выполняем в каждой строке с номером i (i = n-1, n-2,…,0) следующие действия
- Обнуление элементов строки над главной диагональю - с номерами [i-1..n-1]
- Поиск максимального по модулю элемента строки из номеров [0,…,i-1]. Обозначим величину этого элемента max, а его номер imax.
- Выполняется проверка max > e, где e - малое число.
3.1. Если условие выполнено, то меняем в матрице местами столбцы с номерами i, imax, затем переход на Шаг 4.
3.2. Если условие не выполнено, то вначале проверяем условие ifirst ≤ L, если оно выполнено, то меняем местами элементы с номерами i и ifirst в массиве sort[n] и вместо строки i в матрицу вставляем строку с номером ifirst с учетом массива sort[n]. Если же ifirst = L + 1, то выход из алгоритма с отрицательным ответом false.
- Обнуление всех элементов с номерами i в вышележащих строках j =0 , …, i -1.
В конце обратного хода полученная треугольная матрица А1 сохраняется для ускоренного решения последующих систем.
Прямой ход. Определение решения Х1 первой системы А1.
В полученной треугольной матрице А1 на главной диагонали стоят достаточно большие по модулю элементы, что гарантирует получение решения первой системы.
Для получения решения первой системы А1 последовательно обрабатываем ее строки с номерами i (i = 0,1,…, n-1), выполняя в каждой строке i следующие действия.
- Деление всех элементов строки на ее элемент на главной диагонали а[i,i]. После этого этот элемент станет единичным: а[i,i] = 1.
- Обнуление всех элементов с номером i.в строках с номерами [i+1,...,n-1].
После завершение прямого хода все элементы х1[i] (i = 0,1,…, n-1) искомого решения Х1 первой системы А1 можно взять из элементов с номерами n строк матрицы А1.
Число найденных результатов r= 1.
3.3 Формирование всех последующих систем Аk (k > 1) и определение их решений Хk
Если ifirst = L + 1, то выход из алгоритма с ответом true.
Частичный обратный ход. Подготовка треугольной матрицы системы Аk.
С матрицей предыдущей системы Аk-1 выполняем следующие действия.
- Переход к неполной системе А(k-1)r. Для этого удаляем первую строку в Аk-1. Данное действие осуществляется сдвигом указателей в массиве pts: pts[i] = pts[i+1] (i = 0,1,…, n-2).
- Приведение неполной системы А(k-1)r к квазидиагональному виду. Для этого выполняем перестановку в ней столбцов с номерами 0 и (n-1). Также меняем номерами элементы 0 и (n-1) в массиве sort.
- Формирование полной системы Аk. Для этого вначале присваиваем вспомогательному ключу flag значение false. Затем в цикле по условию (ifirst ≤ L) выполняем следующие действия.
3.1. Запись уравнения с номером их исходного набора в матрицу Аk. Данное действие осуществляется присваиванием указателей в массиве pts: pts[n-1] = pt[ifirst]. В новом уравнении выполняем перестановку элементов в соответствии с массивом sort[n].
3.2. Если величина элемента (n-1) в строке (n-1) по модулю меньше e, то выполнение цикла по условию (ifirst ≤ L).
3.3. Если величина элемента (n-1) в строке (n-1) по модулю не меньше e, то присваиваем: flag = true и выходим из цикла по условию (ifirst ≤ L) на Шаг 4.
- Если flag = false, то выход из алгоритма с ответом true. Иначе – переход на Шаг 5.
- При подстановке решения Х(k-1) в систему А(k-1) первые (n-1) уравнений системы будут однородными. Но при подстановке Х = Х(k-1) в последнее уравнение в нем изменится свободный коэффициент
- Обнуление элементов с номерами (n-1) в строках (i = 0,1,…, n-2).
Прямой ход. Определение решения Хk системы Аk.
Выполняется аналогично определению решения системы А1. Получаемое решение обозначим как ΔХk . Полное решение Хk = Х(k-1) + ΔХk.
Фильтрация всех найденных решений выполняется известными методами.
Заключение
Устранение шумов и погрешностей в получаемых данных обратной связи позволяет повысить точность цифровых методов автоматизированного управления технологическими процессами. Особенно актуальным является решение данной задачи при управлении недетерминированными процессами. Предложенный алгоритм позволяет практически решить эту задачу.