7.2. РЕКУРРЕНТНЫЕ АЛГОРИТМЫ


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

P = ZTZ = Σi=1:kZiZiT, R = ZTY = Σi=1:kZiyi.


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

Pk = Pk–1 + ZkZkT, Rk = Rk–1 + Zkyk.


На каждом шаге рекуррентной идентификации, вслед измерениям матрицы корректируются, затем отыскивается решение θk = Pk–1Rk.

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

Для того, чтобы ограничить память процесса идентификации, применяют экспоненциальное взвешивание

Pk = WPk–1 + (1–W)ZkZkT, Rk = WRk–1 + (1–W)Zkyk,


где коэффициент 0 < W < 1.

В матричном виде такой обобщенный метод наименьших квадратов (ОМНК) выглядит более эстетично

Pθ = R, P = ZTWZ, R = ZTWY.


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

Рекуррентный метод наименьших квадратов (РМНК). Он основан на следующей лемме об инвертировании суммы матрицы с некоторым произведением (P+ABC)–1 = P–1 – P–1A(СP–1A+B–1)CP–1.

Согласно этой лемме матрицу системы нормальных уравнений можно инвертировать только один раз или задать обратной матрице некоторое начальное значение

P0–1 = ξ–1 diag (1 1 … 1),


где ξ – достаточно малое число (обычно 0.001). Каждое следующее измерение наращивает матрицу аддитивной составляющей ZTkZk, отсюда легко выводится алгоритм

Pk–1 = Pk–1–1 – γkpkT, θk = θk–1 + γk(yk–1 – ZkTθk–1),


где pk = Pk–1–1Zk, γk = pk/(1 + ZkTpk).

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

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

θk = θk–1 + γk grad ||Zθk–1 –Y||2 / 2 = θk–1 + γk(Rk – Pkθk–1),


Rambler's Top100