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



Бондарь А.С., группа СУА-07м

Руководитель к.т.н., доц. Паслён В.В.

      Траекторные измерения возникли в практике лётных испытаний различных систем и летательных аппаратов (ЛА). Под ними понимается процесс измерения и обработки полученных данных с целью определения траектории движения ЛА.

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

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

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

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

      Методы (алгоритмы) сглаживания данных траекторных измерений предусматривают построение системы ортогональных базисных функций (ОБФ).

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

      Если ОБФ строятся в форме степенных многочленов с коэффициентом при старшей степени, равным единице, то для построения системы ОБФ обычно используют трехчленную рекуррентную формулу:

     

           (1.1)

      где:

     

           (1.2)

           (1.3)

      Для реализации формулы (1.1) для каждого момента времени необходимо выполнить по две операции умножения и вычитания, следовательно, четыре математических операции. Если использовать множество, состоящее из n точек, то количество математических операций составит:4n (по 2n операций умножения и вычитания).

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

      Аналогично, для реализации формулы (1.3) на множестве, состоящем из точек, необходимо выполнить 5n+1 математических операций ( 3n операций умножения, 2n операций сложения и одну операцию деления).

      Таким образом, общее число математических операций, необходимых для построения одной ОБФ, составит: 14n+2 ( 8n операций умножения, 4n операций сложения, 2n операций вычитания и две операции деления).

      При совмещении начала отсчета локального времени t с серединой интервала сглаживания формула (1.1) упрощается, т.к. В этом случае общее число математических операций, необходимых для построения одной ОБФ, составит: 9n+1 ( 5n операций умножения, по 2n операций сложения и вычитания, одну операцию деления).

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

           (1.4)

      Следовательно, используя формулы (1.1) – (1.3), необходимо построить пять ОБФ. Таким образом, общее число математических операций, необходимых для построения системы ОБФ, составит: 70n+10 (40n операций умножения, 20n операций сложения, 10n операций вычитания и 10 операции деления).

      А при совмещении начала отсчета локального времени с серединой интервала сглаживания общее число математических операций, необходимых для построения системы ОБФ, составит: 45n+5 (25n операций умножения, по 10n операций сложения и вычитания, 5 операции деления).

      Рассмотрим метод построения ОБФ, предложенный Шмидтом. Метод Шмидта также является рекуррентным и заключается в построении системы ОБФ по системе неортогональных базисных функций ЛНБФ. Общая рекуррентная формула имеет вид:

           (1.5)

      где:

     

           (1.6)

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

           (1.7)

      Следовательно, используя формулы (1.5) и (1.6), необходимо построить шесть ОБФ.

      Для реализации формулы (1.5) для каждого момента времени необходимо выполнить по 21 операции умножения и сложения, следовательно, 42 математических операции. Если использовать множество, состоящее из точек, то количество математических операций составит: 42n.

      Для реализации формулы (1.6) на множестве, состоящем из точек, необходимо выполнить следующие математические операции: 42n операций умножения, 42n операцию сложения и 21 операцию деления.

      Таким образом, общее число математических операций, необходимых для построения системы ОБФ, составит: 126n+21 ( 63n операций умножения, 63n операций сложения и 21 операцию деления).

      Найдём разность между числом математических операций, проделанных при построении системы ОБФ, при использовании трехчленной рекуррентной формулы, и числом математических операций, проделанных, при использовании алгоритма на основе метода ортогонализации Шмидта. Получим разность:

     

           (1.8)

      где R - разность между числом математических операций.

      Т.е. при использовании метода Шмидта необходимо выполнить на 23n операций умножения, 33n операций сложения (вычитания) и 11 операций деления больше, чем при использовании трехчленной рекуррентной формулы.

      А при совмещении начала отсчета локального времени t с серединой интервала сглаживания разность составит:

     

           (1.9)

      где R1- разность между числом математических операций.

      В этом случае при использовании метода Шмидта необходимо выполнить на 38n операций умножения, 43n операций сложения (вычитания) и 16 операций деления больше, чем при использовании трехчленной рекуррентной формулы.

Выводы:

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

      Верность подобных утверждений легко проверить, задавшись, например, множеством из двадцати семи точек: . При этом для построения системы ОБФ на основе трехчленной рекуррентной формулы необходимо выполнить: 70*27+10=1900 математических операций (1080 операций умножения, 540 операций сложения, 270 операцию вычитания и 10 операций деления). А при совмещении начала отсчета локального времени t с серединой интервала сглаживания необходимо выполнить: 45*27+5=1220 математических операций (675 операций умножения, по 270 операций сложения и вычитания, 5 операций деления). В то время, как для построения системы ОБФ на основе алгоритма метода ортогонализации Шмидта необходимо выполнить: 126*27+21=3423 математических операций (1701 операцию умножения, 1701 операцию сложения и 21 операцию деления). Разность между числом математических операций, проделанных при построении системы ОБФ разными методами, составит: 3423-1220=2203 математических операций (при совмещении начала отсчета локального времени с серединой интервала сглаживания). Т.е. при использовании метода Шмидта необходимо выполнить на 1024 операции умножения, 1161 операцию сложения (вычитания) и 16 операций деления больше, чем при использовании трехчленной рекуррентной формулы.

     

Список источников

      1. . Огороднийчук Н.Д. Обработка траекторной информации. Ч. II. – Киев: КВВАИУ, 1986. - 224 с.