Теория и практика защиты программ

       

Метод наименьших квадратов и задача самотестирования


Рассмотрим метод наименьших квадратов применительно к задачам двух типов: детерминированной и стохастической с известными вторыми моментами.

Детерминированная задача состоит в выборе вектора х

таким образом, чтобы минимизировать значение

 в уравнении:

=||Ах-у||2 =хТАТАх-2уTАх+||у||2,                                          (4.1)

где А — известная матрица, а у — известный вектор, индекс Т обозначает транспонирование матрицы или вектора.

Стохастическая задача наименьших квадратов состоит в выборе детерминированного весового вектора w для минимизации средней квадратической ошибки

:

=E(wTz-d)2=wTzRzw-2RTdzw+E(d2),                               (4.2)

где z — случайный вектор; d — случайная величина. Скалярная случайная величина wTz представляет собой линейную комбинацию компонентов случайного вектора z

и используется как линейная оценка случайной величины d. Математическое ожидание обозначается символом Е, через Rz обозначена матрица вторых моментов случайного вектора z: Rz=EzzТ. Аналогично вектор Rdz определяется как Rdz=E(dz).

В работе [УСБ] показана вычислительная эквивалентность стохастической задачи наименьших квадратов с оценкой вторых моментов и соответствующей детерминированной задачи. Поэтому достаточно для наших целей рассматривать вычислительные методы только для детерминированной задачи наименьших квадратов.

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

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



Содержание раздела