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

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

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

Выполненный анализ показывает, что трудоемкость метода Гаусса-Жордана примерно совпадает с трудоемкостью метода Гаусса. Сложности их алгоритмов одинаковы.

1.6 Решение систем линейных уравнений с использованием LU-разложения матрицы системы

LU-разложением (LU-факторизацией) называют представление матрицы A в виде произведения LU, где L -- нижняя треугольная матрица с единичной диагональю, а U -- верхняя треугольная матрица [7,16,17,33]:

(1.15)

Метод решения систем линейных уравнений, основанный на данном разложении, является разновидностью метода Гаусса.

Обозначим элементы L через l_ij, элементы U - через u_ij, (i,j=1,...,n). По свойствам определителей:

det(L)=1; det(L) = l₁₁ l₂₂ …l_nn = 1;

det(A) = det(L)det(U) = 1det(U) = u₁₁ u₂₂ …u_nn.

Идея LU-разложения основана на матричном представлении прямого хода метода Гаусса без выбора главных элементов строк. Обозначив для общности матрицу начальной системы уравнений А через А⁽⁰⁾, представим исходную систему уравнений в виде:

А⁽⁰⁾X =B.(1.16)

При выполнении прямого хода вначале обнуляются элементы столбца 1 матрицы системы под главной диагональю путем сложения строк расширенной матрицы с номерами 2,3,…,n с первой строкой, умноженной, соответственно, на коэффициенты (-а⁽⁰⁾₂₁/а⁽⁰⁾₁₁), (-а⁽⁰⁾₃₁/а⁽⁰⁾₁₁),…, (-а⁽⁰⁾_n1/а⁽⁰⁾₁₁). Это преобразование эквивалентно умножению левой и правой частей уравнения (1.16) на нижнюю треугольную матрицу с единичной диагональю вида:

С₁ (А⁽⁰⁾)А⁽⁰⁾X = С₁(А⁽⁰⁾)B.

Обозначим произведение С₁(А⁽⁰⁾)А⁽⁰⁾ через А⁽¹⁾ и представим преобразованную систему в виде А⁽¹⁾X = С₁(А⁽⁰⁾)B. Для того, чтобы в данной системе обнулить элементы столбца 2 матрицы системы А⁽¹⁾под главной диагональю, складываем строки расширенной матрицы с номерами 3,4,…,n со второй строкой, умноженной, соответственно, на коэффициенты (-а⁽¹⁾₃₂/а⁽¹⁾₂₂), (-а⁽¹⁾₄₂/а⁽¹⁾₂₂),…, (-а⁽¹⁾_n2/а⁽¹⁾₂₂). Это преобразование эквивалентно умножению левой и правой частей преобразованного уравнения на нижнюю треугольную матрицу с единичной диагональю вида:

С₂(А⁽¹⁾)А⁽¹⁾X = С₂(А⁽¹⁾)С₁(А⁽⁰⁾)B.

Затем в полученной новой системе уравнений умножаем обе части на матрицы С₃(А⁽²⁾), С₄(А⁽³⁾),… С_n-1(А^(n-2)). В итоге всех умножений, вводя обозначение С = С _n-1(А^(n-2)) С _n-2(А^(n-3))…С₂(А⁽¹⁾)С₁(А⁽⁰⁾), получим систему вида:

С А⁽⁰⁾X = С B,(1.17)

у которой матрица СА⁽⁰⁾ после завершения прямого хода имеет верхний треугольный вид. Матрица С является произведением (n-1) нижних треугольных матриц с единичной диагональю. Несложно показать, что С также будет нижней треугольной с единичной диагональю. Так как det(C) = 1, то обратная матрица C^-1 существует. Нетрудно доказать, что она также является нижней треугольной с единичной диагональю. Умножая обе части системы (1.17) на C^-1, получим исходную систему уравнений (1.16) в следующей форме:

С^-1 С А⁽⁰⁾X =B,

Матрица С^-1 удовлетворяет требованиям к матрице L, а произведение С А⁽⁰⁾ - к U, т.е.: L=С^-1, U=С А⁽⁰⁾ - матрица исходной системы после прямого хода.

Для определения коэффициентов матриц L и U используют прямой метод расчета, основанный на правиле умножения матриц и учете структуры матриц L и U. По нему на каждом шаге k (k =1,2,…,n) по ранее найденным элементам матриц определяются строка матрицы U и столбец матрицы L с номером k. Для примера рассмотрим вывод формул для k =1,2.

k =1. Из структуры матриц L и U следует, что элементы а_1j первой строки матрицы А образуются умножением на 1 (l₁₁) элементов u_1j: а_1j = l₁₁ u_1j = u_1j. Поэтому в первой строке матрицы U: u_1j = а_1j, (j = 1,...,n). Элементы а_i1 первого столбца матрицы А образуются умножением l_i1 на u₁₁: а_i1 = l_i1u₁₁. Поэтому в первом столбце матрицы L: l_i1 = а_i1/u₁₁, (i = 2,...,n). В итоге расчетные формулы шага i =1 с учетом l₁₁ =1 имеют вид:

u_1j = а_1j, (j = 1,...,n); l₁₁ =1; l_i1 = а_i1/ u₁₁, (i = 2,...,n) (1.18)

k =2. Элементы а_2j второй строки матрицы А рассчитываются по формуле: а_2j= l₂₁ u_1j+ l₂₂ u_2j. Учитывая, что l₂₂=1, u₂₁=0 и первая строка U уже найдена, формула для расчета элементов ее строки 2 имеет вид: u_2j = а_2j - l₂₁ u_1j, (j = 2,...,n). Аналогично из формулы для элементов второго столбца матрицы А: а_i2 = l_i1 u₁₂+ l_i2u₂₂, учитывая, что l₁₂=0, l₂₂=1 и первый столбец L уже найден, расчетная формула элементов ее столбца 2 имеет вид: l_i2 = (а_i2 - l_i1 u₁₂)/(u₂₂), (i = 3,...,n).. В итоге расчетные формулы шага i =2 имеют вид:

u₂₁=0; u_2j = а_2j - l₂₁ u_1j, (j = 2,...,n);

l₁₂=0; l₂₂=1; l_i2 = (а_i2 - l_i1 u₁₂)/(u₂₂). (i = 3,...,n)

По аналогии можно вывести расчетные формулы для произвольного шага k (k = 1,...,n), который заключается в расчете строки матрицы U и столбца L с номерами k:

u_k1=u_k2=…=u_k(k-1)=0;

u_kj = а_kj - ( l_k1 u_1j + l_k2 u_2j +…+ l_k(k-1) u_(k-1)j), (j = k,...,n);

l_1k=l_2k=…=l_(k-1)k =0; l_kk = 1;

l_ik = [а_jk - ( l_j1 u_1k + l_j2u_2k +…+ l_j(k-1) u_(k-1)k)]/u_kk, (i = (k +1),...,n).

Вычисления по формулам начинаются с расчета величины диагонального элемента u_kk матрицы U.

Если u_kk 0, то при (k = 1,...,n-1), можно продолжать дальнейшие расчеты по формулам, поскольку все величины в них определены.

Если u_kk = 0 при (k = 1,...,n-1), то из-за деления на нуль возникает неопределенность в расчете коэффициентов l_ik. Следовательно, для заданной исходной матрицы А LU-разложение не существует и следует прекратить выполнение алгоритма.

Критерии существования LU-разложения. Из общего вида расчетных формул (1.18.k.1)-(1.18.k.2) следует, что общим критерием, задающим необходимые и достаточные условия существования LU-разложения матрицы, является следующая совокупность неравенств:

u₁₁ 0, u₂₂ 0, u_33(n-1) 0,…, u_(n-1)(n-1) 0.(1.19)

Равенство u_nn = 0 может выполняться, поскольку на последнем шаге k=n не производится деления на диагональный элемент u_nn при расчете элементов матрицы L. Поэтому общий критерий выполняется и при det(A) 0 и при det(A) =0.

Отсутствие LU-разложения у исходной матрицы А не эквивалентно существованию единственного решения системы уравнений с матрицей А.

Общий критерий существования LU-разложения матрицы (1.19) не удобен для применения, так как требует почти полного расчета алгоритма (1.18.k.1)-(1.18.k.2). Поскольку наибольший интерес представляют случаи расчета LU-разложения матриц, когда соответствующие им системы имеют единственное решение (т.е. матрицы не вырождены), то в этом случае критерий имеет более простой вид.

Теорема 6.1. (Критерий существования LU-разложение невырожденной матрицы). LU-разложение невырожденной матрицы А существует тогда и только тогда, когда:

а₁₁ 0. (1.20)

Трудоемкость и сложность алгоритма LU-разложения.Суммируя числа арифметических операций для расчета элементов матриц U и L, получим на каждом шаге k следующие их значения, используя вспомогательную величину k₁ = (k-1):

- сравнений: с_k(n) = 1;

- сложений и вычитаний: s_k(n) = (k-1) (n - k+1) +(k-1) (n - k) = k₁(2n -1) - 2k₁²;

- умножений: m_k(n) = s_k(n);

- делений: d_k(n) = (n - k).

Трудоемкость всего алгоритма LU-разложения получим, суммируя числа операций для всех шагов k от 1 до n:

- сравнения: с_LU(n) = n;

- сложения и вычитания: s_LU(n) = (2n -1) [0+1+ … + ( n-1)] - 2[0²+1²+ … +( n-1) ²] = n (n-1)(2n-1)/6 n³/3.

- умножения: m_LU (n) = s_LU (n) = n (n-1)(2n-1)/6 n³/3;

- деления: d_LU (n) = [( n-1) +( n-1) +…1+0] = n(n-1)/2 n²/2.

По сравнению с алгоритмом прямого хода:

- число сравнений уменьшено на n(n-1)/2 n²/2;

- числа сложений (вычитаний), а также умножений уменьшены на:

n (n²-1)/3 - n (n-1)(2n-1)/6 = n (n-1)/6 n²/6;

- число делений осталось прежним.

Основную часть алгоритма составляют операции сложения (вычитания) и умножения, число которых расчет, как и у алгоритма прямого как n³/3. Сложность алгоритма LU-разложения равна О(n³).

Решение системы линейных уравнений с использованием результатов LU-разложения ее матрицы. Если LU-разложение найдено и det(U)0, то решение исходной системы уравнений (1.16) сводится к последовательному решению двух систем уравнений с треугольными матрицами коэффициентов:

LY = B ; (1.21)

UX = Y

Сложность решения систем уравнений с треугольными матрицами равна сложности обратного хода метода Гаусса, т.е. О(n²).

LU-разложение рекомендуется применять в том случае, когда систему вида АХ =В необходимо решать многократно при постоянной матрице А и переменных свободных векторах В. При этом по известным один раз найденным матрицам L и U решение системы требует выполнения О(n²) арифметических операций.

При программной реализации метода и последующего хранения матриц L и U применяют их компактное совместное представление в одной матрице порядка n (матрица L хранится без единичной диагонали):

(1.22)

Рассмотрим особенности LU-разложения. При его выполнении возможны ситуации, когда ведущий диагональный элемент u_kk матрицы U окажется равным нулю либо будет близок к нулю.

В первом случае возможны 3 ситуации.

1. Равен нулю первый диагональный элемент: u₁₁= а₁₁ = 0. В этом случае достаточно в матрице системы поменять порядок столбцов. Например, в матрице из примера 1 после перемены мест столбцов 1 и 2 для измененной матрицы А₁ получим:

2. Равен нулю средний диагональный элемент: u_kk = 0, при 2 ? k ? n-1. Это свидетельствует о том, что матрица А вырожденная и у нее нет LU-разложения.

3. Равен нулю последний диагональный элемент: u_nn = 0. При этом матрица А вырожденная, но у нее есть LU-разложение, в котором det(U)= 0.

Если диагональный элемент u_kk матрицы U близок к нулю, то в случае 1 ? k ? n-1 при делении на него могут быть получены большие погрешности в коэффициентах матрицы L и в дальнейшем решении системы. Метод LU-разложения не предусматривает выбор главного элемента (который мог бы предотвратить появление таких элементов на главной диагонали), поскольку перемена местами столбцов с номерами j₁ и j₂ эквивалентна умножению слева матрицы системы уравнений на вспомогательную матрицу вида:

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

Оптимальный с точки зрения уменьшения погрешностей решения порядок неизвестных в системе задает вектор их порядкаР, получаемый после выполнения прямого хода метода Гаусса. Поэтому для того, чтобы максимально уменьшить величину погрешностей в получаемом решении, можно вначале найти верхнюю треугольную матрицу U по методу Гаусса и заодно оптимальный вектор порядка неизвестныхР, а затем, изменив порядок переменных в А, выполнить часть LU-разложения по формулам относительно коэффициентов матрицы L.

1.7 Цифровые и аналоговые алгоритмы фильтрации и сглаживания данных

В работе [24] рассматриваются основные типы алгоритмов цифровой фильтрации. В таким типам алгоритмов относятся:

· алгоритмы линейной цифровой фильтрации;

· алгоритмы оптимальной цифровой фильтрации;

· алгоритмы адаптивной цифровой фильтрации;

· алгоритмы фильтрации на основе аппарата нечетких множеств;

· нейросетевые алгоритмы цифровой фильтрации.

Наиболее часто используемыми и хорошо изученными язляются алгоритмы линейной цифровой фильтрации сигналов. На их основе проектируются линейные цифровые фильтры и фильтры частотных селекций. Классическими трудами в данном направлении являются работы А.Н. Колмогорова, В.А. Котельникова, Р. Е. Калмана, Л. Рабинера.

Алгоритм линейной цифровой фильтрации описывается выражением:

,

где - отчеты выходного сигнала; - отчеты выходного сигнала; n - номер отсчета сигнала, который принимает только целые значения 0,1,2,3…; , - отсчеты решетчатых функций.

Оптимальные фильтры в общем случае определяются как частотно-избирательная система, обрабатывающая сигнал некоторым наилучшим образом. Наиболее часто данные фильтры используются для оценки физических величин, характеризующих систему, подверженную случайным возмущениям. Наибольшее число оптимальных цифровых фильтров построены на принципе минимизации среднеквадратичного отклонения оценивания. Так же оптимальные цифровые фильтры возможно подразделить на линейные и нелинейные в зависимости от уравнений используемых в алгоритме. Одним из наиболее известных алгоритмов оптимальной цифровой фильтрации является алгоритм Калмана. Если входной сигнал является случайным и марковским, то его можно представить как выходной сигнал линейной дискретной системы, возбуждаемой белым шумом w(n) с нулевым математическим ожиданием и дисперсией .

Во многих случаях отсутствует возможность использования цифровых фильтров с постоянными параметрами, в связи с отсутствием информации или динамичностью входного либо эталонного сигнала. При зависимости частотных характеристик цифровых фильтров от спектров обрабатываемых сигналов, такие фильтры называются адаптивными. Основы синтеза адаптивных цифровых фильтров были заложены в работах Я.З. Цыпкина, Р.Л. Стратоновича, В.В. Шахгильдяна, М.С. Лохвицкого, Б. Уидроу и С. Стирнза. В большинстве случаев под адаптивным понимается такой алгоритм принятия решения, при построении которого, используется предварительное обучение с целью преодоление априорное неопределенности. Целью применения алгоритма адаптивной фильтрации сигналов, является достижение экстремума рабочей функции. Из задач адаптивной фильтрации можно выделить линейное предсказание, заключающаяся в предсказании, по линейной комбинации предшествующих отчетов, будущего значения отсчета. Результатом же решения задачи линейного предсказания является набор коэффициентов адаптивного фильтра. Основные и первые работы по синтезу адаптивных фильтров были написаны Винером и Калманом. Структура адаптивных фильтров строится таким образом, что бы их поведение и функционирование, в результате взаимодействия с окружающей средой, непрерывно улучшались.

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

Ещё одним методом обработки нестационарных случайных сигналов является применение нейросетей. Теоретические основы нейросетей были заложены в работах У. Мак-Каллока и В. Питтса. Главной идеей подавляющего большинства алгоритмов обучения нейронной сети, является учет локального градиента в пространстве конфигураций для наискорейшего спуска по рабочей функции. Одними из наиболее совершенных является нечеткие нейронные сети, в которых выводы делаются на основе аппарата нечеткой логики, но функции принадлежности подстраиваются с использованием алгоритмов обучения нейронной сети.

В работе [21] на основе имитационного моделирования произведены оценки эффективности сглаживания многокритериальными способами и фильтром Винера.

В [10] говорится, что в среднем ошибка при синтез фильтра, оптимального по Чебышеву, выше чем при методе наименьших квадратов. Наиболее часто используемым алгоритмом синтеза фильтров Чебышева является алгоритм Паркса-Мак-Клеллана, в которой задача синтеза ставится как задача полиномиальной аппроксимации. Прямой метод Фурье даёт наилучшее приближение к требуемой характеристике, но влечет явление Гиббса, которое может быть исключено сглаживанием Ланцоша.

В [20] разработан метод и алгоритм использования вероятностного округления в рекуррентной мультипликативной процедуре. Сделаны оценки математического ожидания и дисперсии ошибки для детерминированного и вероятностного округления применительно к указанной процедуре. Результатами моделирования подтверждены аналитические выводы об устойчивости рекуррентной процедуры с вероятностным округлением к ошибкам округления и неустойчивости такого же вычислительного процесса с детерминированным округлением.

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

В работе [31] также рассмотрены рекуррентные оптимальные фильтры (оптимальный прогнозирующий фильтр, оптимальный одношаговый прогноз, оптимальный сглаживающей фильтр, оптимальное одношаговое сглаживание) и минимаксная фильтрация. Рассмотрена задача оптимального сглаживания в дискретном времени. Наиболее часто под адаптивным алгоритмом принятия решений принимают алгоритм, при построении которого для преодоления априорной неопределенности используется предварительное обучение. Главной задачей адаптивного фильтра является повышение качества обработки сигнала.

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

У симметричных линейных фильтров применительно к задачам управления движением две основные проблемы: 1) как реализовать линейность на неравномерной сетке событий и 2) какой должны быть оптимальная полуширина фильтра s.

1.8 Моменты наступления событий как случайные потоки событий в системах массового обслуживания

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

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

Вероятность наступления i событий за промежуток времени t обозначают как p_i(t). По свойству полной вероятности справедлива следующая сумма: p₀(t)+ p₁(t)+ p₂(t)+ …=1.

В теории рассматривают следующие основные свойства потоков событий.

1. Стационарность - независимость вероятности характеристик от времени. Такая вероятность поступления определенного числа событий за промежуток времени длиной t для стационарного потока не зависит от выбора начала его измерения, а зависит только то длины этого промежутка.

2. Последействие - вероятность поступления событий в интервале времени (t₁ ,t₂) зависит от событий, происшедших до момента t₁.

3. Ординарность - вероятность поступления двух и более событий за бесконечно малый интервал времени t, есть величина бесконечно малая, более высокого порядка малости, чем р₁(t).

Обозначим среднее значение событий на отрезке времени [t, t+t] через N[t, t+t]. В теории c использованием данной характеристики рассматривают следующие характеристики потоков событий.

1.Интенсивностью потока называют среднее значение (математическое ожидание) числа событий в единицу времени в данный момент времени t:

(t) = lim(N[t, t+t]/t) при t0.

Фактически (t) является пределом отношения среднего числа событий N на отрезке [t, t+t] к его длине t, стремящейся к нулю.

2. Параметром потока называют предел отношения вероятности наступления хотя бы одного события на отрезке [t, t+t] к его длине t, стремящейся к нулю.

(t) = lim(p_1,2,…(t)+ N[t, t+t]/t) при t0.

С учетом выше рассмотренных основных свойств потоков событий выполняются следующие соотношения:

1) у стационарного процесса интенсивность и параметр потока являются постоянными величинами, которые не зависят от времени,

2) у ординарных потоков величина параметра потока и интенсивность потока совпадают.

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

1.Простейший поток вызовов или поток Пуассона. Данным потоком вызовов называют стационарный ординарный поток без последействия.

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

3.Поток Пальма. Это стационарный ординарный рекуррентный поток с запаздываниями либо стационарный ординарный поток с ограниченным последействием.

4. Поток Эрланга. Образуется путем просеивания простейшего потока событий.

5.Поток Бернулли. Ординарный поток с ограниченным последействием, для которого на заданном отрезке [t, t+t] случайным образом поступает фиксированное (равное n) число событий.

6.Потоки с простым последействием. Это ординарные потоки, у которых параметр определяется текущим состоянием обслуживающей системы в рассматриваемый момент времени t.

Анализ исходной задачи показывает, что в ней поток событий может быть с достаточно большой точностью приближения принят простейшим.

Рассмотрим его свойства.

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

Е = t ,(1.23)

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

2. Вероятность того, что за время t, произойдет ровно k событий, равна

P_k(t) = ( t)^k exp(- t)/ k!. (1.24)

3. В том числе, вероятность того, что за время t не произойдет ни одного события (k =0), равна

P₀(t) = exp(- t). (1.25)

4. Функция плотности распределения промежутков времени t_j между произвольными двумя соседними событиями в простейшем потоке следующая:

f(t) = exp(- t). (1.26)

Данный закон распределения называют показательным, а величину - его параметром. График функции плотности f(t) показательного распределения дан на рис.1.1.

Рис 1.1. График функции плотности f(t) показательного распределения

5. Математическое ожидание величины t, распределенной по показательному закону:

Е(t)=1/.(1.27)

6. Дисперсия величины t, :

D(t)=1/².(1.28)

7. Среднеквадратичное отклонение t:

(t)=1/.(1.29)

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

1.9 Нормальное распределение, его свойства и моделирование

Нормальным распределением (распределением Гаусса) называют такое двухпараметрическое распределение вероятностей, при котором в одномерном случае функция плотности распределения для случайной величины х, определенной на всей числовой оси R, имеет следующий вид:

(1.30)

где параметр м -- математическое ожидание, медиана и мода распределения, а параметр у - стандартное отклонение (уІ -- дисперсия) распределения.

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

Свойства данного закона распределения.

1. Функция распределения:

1. Математическое ожиданиe: .

2. Мода: .

3. Медиана: .

4. Дисперсия: ².

Стандартным нормальным распределением называют нормальное распределение с математическим ожиданием 0 и среднеквадратичным отклонением, равным 1.

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

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

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

В первом варианте вначале генерируются две независимые случайные величины r и , каждая из которых равномерно распределена на интервале (0, 1]. По ним рассчитываются величины z₀ и z₁ с использованием следующих формул:

(1.31)

Случайные величины z₀ и z₁ являются независимыми и нормально распределенными с математическим ожиданием 0 и дисперсией 1, т.е. являются стандартными.

Во втором варианте преобразования Бокса -- Мюллера также вначале задаются две независимые случайные величины x и y, каждая из которых равномерно распределена на интервале [-1, 1]. По ним вначале вычисляется величина s(x,y)= x² + y². Если s(x,y) = 0 либо s(x,y) > 1, то величины x и y, отбрасываются и генерируется следующая пара. Процесс продолжается до тех пор, пока не будет получено значение 0 < s(x,y) 1.

Для полученного значения s(x,y), удовлетворяющего условиям 0 < s(x,y) 1, вначале рассчитывается величина

d = (-2ln(s)/s)^0.5. (1.32 а)

По ней рассчитываются псевдослучайные величины z₀ и z₁ , которые также являются независимыми и имеют стандартное нормальное распределение (с математическим ожиданием 0 и дисперсией 1):

z₀=хd; z₁=yd. (1.32 б)

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

После получения стандартной нормальной случайной величины , имеющей математическое ожиданием =0 и среднеквадратичное отклонение =1, перейти к нормально распределенной величине с произвольным математическим ожиданием и среднеквадратичным отклонением по формуле можно по формуле

(1.33)

Данное дополнительное преобразование позволяет моделировать нормально распределенные случайные величины с любыми наборами параметров (, ).

1.10 Построение линейных моделей с использованием данных обратной связи

Допустим, для динамического ОУ на отрезке изменения времени [t_н,t_к] выделено некоторое множество параметров {a(t)= (a₁(t), a₂(t),…, a_n(t)), b(t)}, прямо или косвенно характеризующих его состояние. Совокупность параметров {a(t), b(t)} связана на отрезке времени [t_н,t_к] линейной зависимостью, если существует набор постоянных коэффициентов x= (x₁, x₂,…, x_n), для которого при всех t[t_н,t_к] выполняется условие

x₁a₁(t)+ x₂a₂(t)+…+ x_na_n(t)= b(t). (1.34)

В векторной форме условие (1) принимает вид:

(x,a(t))= b(t). (1.35)

Параметрыa(t)= (a₁(t), a₂(t),…, a_n(t)) называют линейными, параметр b(t) - свободным. В общем случае деление параметров на линейные и свободный является условным. При любом динамическом параметре a_i (t),входящем в зависимость (1.34) с коэффициентом х_i ?0 (1?i?n), ее можно представить в аналогичном виде:

(-x₁/х_i)a₁(t)+ (-x₂/х_i)a₂(t)+… +(-x _{i -1} /х_i)a_{i -1}(t)+(-x _{i +1} /х_i)a_{i +1}(t)+…+ )+(-x_n /х_i)a_n(t)+(1/ х_i) b(t)= a_i (t).

Вначале рассмотрим идеальную САУ, у которой в измерительных и вычислительных блоках нет погрешностей. Поскольку зависимость (1.34) содержит n неизвестных коэффициентов x= (x₁, x₂,…, x_n), то для их одновременного определения надо использовать не одну, а n таких зависимостей.

Для этого на отрезке [t_н,t_к] надо выбрать n возрастающих моментов времени t_н? t₁< t₂<…< t_n ? t_к и рассмотреть систему из n уравнений вида

(x,a ⁱ (t_i))= b(t_i), (1?i?n). (1.36)

В векторном виде систему (1.36) обозначим как:

Ax =b,(1.37)

где A - матрица, состоящая из n строк вида (x,a ⁱ (t_i)),

b -вектор-столбец из значений b(t_i).

Необходимым и достаточным условием существования и единственности решения системы (1.36) для идеальной САУ является условие:

det(A) ?0.(1.38)

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

При выполнении условия det(A) ?0 решение точной системы (1.37) имеет вид:

x =( A)^-1b.(1.39)

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

Обозначим матрицу погрешностей линейных коэффициентов через , вектор погрешностей свободных коэффициентов - через . Подстановка реальной матрицы матрицу (A+) и вектора (b +) в систему (1.37) приведет к тому, что погрешность получит и вектор значений коэффициентов x= (x₁, x₂,…, x_n). Обозначим еех Величина данной погрешности требует отдельного рассмотрения.

Также требуется определить пути максимально возможного уменьшения погрешности х.

1.11 Анализ выполненного обзора. Постановка задачи исследования

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

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

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

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

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

Для моделирования шумов ближе всего подходит нормальный закон распределения. Генерирование нормальных шумов предпочтительно выполнять по второму варианта преобразования Бокса-Мюллера.

Асимметричные фильтры дают хорошие результаты для функций, близких к константам. Линейные симметричные фильтры дают хорошие результаты на функциях, близких к линейным. У таких фильтров применительно к задачам управления движением две основные проблемы: 1) как реализовать линейность на неравномерной сетке событий и 2) какой должны быть оптимальная полуширина фильтра s.

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

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

1)максимально возможной точностью решения,

2) минимальной вычислительной сложностью получаемого решения.

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

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

2. Выбор рациональных методов решения СЛАУ с учетом погрешностей данных обратной связи.

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

4. Оценка влияния погрешностей исходных данных на точность расчета коэффициентов линейной модели.

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

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

2.1 Оценка влияния погрешности исходных данных на точность расчета коэффициентов линейной модели

Изучаемые скалярные, векторные и матричные объекты рассматриваются в конечномерном векторном евклидовом пространстве с положительно определённым скалярным произведением.

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

Реальные зависимости a^p (t) (p - номер линейной переменной) и b(t) являются непрерывными функциями времени t. Однако предварительно обработанные данные, подставляемые в расчетные соотношения, имеют характерный пилообразный вид.

На рис.2.1 дан характерный пример: сплошной линией показан график изменения идеального коэффициента a^p (t) (b(t)), жирными точками, соединенными прямолинейными отрезками, показаны последовательные измеренные значения коэффициента a^p_и(t_j) для моментов времени t_j после их предварительной обработки. Разность между точным значением переменной a^p(t_j) (j = 1,…,N) и приближенным значением a^p_и(t_j) в точке t = t_j обозначим: a^p(t_j) = a^p(t_j) - a^p_и(t_j).

Рис. 2.1. Характерные графики изменения точной величины коэффициента a^p(t) и его приближенных значений

При большом числе рассмотренных точек N величину a^p(t_j) можно считать случайной нормально распределенной с нулевым математическим ожиданием: E(a^p(t_j))=0. Среднюю величину отклонения величины a^p(t_j) с достаточно высокой точностью можно принять равной среднеквадратичному отклонению (a^p(t_j)) соответствующей случайной величины.

Обозначим среднеквадратичное отклонение точных значений коэффициента a^p(t) через (a^p(t_j)). Для того, чтобы выразить соразмерность изменения самого коэффициента a^p(t_j) и погрешности его представления a^p(t_j), введем дополнительное понятие масштаба погрешности его представления:

М(a^p(t_j)) = (a^p(t_j)) / (a^p(t_j)). (2.1)

Вначале выясним, как погрешности задания линейных и свободных коэффициентов влияют на точность получаемых значений коэффициентов x= (x₁, x₂,…, x_n).

Обозначим матрицу погрешностей линейных коэффициентов через , вектор погрешностей свободных коэффициентов - через . Вызванную ими векторную погрешность значений коэффициентов x= (x₁, x₂,…, x_n) обозначим через х. Подставляя в систему (1.26) матрицу (A+) и векторы (b +) и (x +х), получаем ее в следующем виде:

(A+) (x +х) = (b +). (2.2)

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