Помогите понять алгоритм: метод "Гусеница" для временных ряд

[logout2d]

Здравствуйте!
Есть такой вот труд:
http://www.gistatgroup.com/gus/book1/index.html
в нем интересная Глава 3 "Метод "Гусеница" для прогнозирования временных рядов"
На странице 84 описан алгоритм построения прогноза(выдержка):
Алгоритм 5.1 Пусть имеется набор последовательных значений функции дискретного аргумента, образующий ряд $(f_{i})^{N}_{i=1}$ ранга r.
1. Формируем многомерную матрицу наблюдений.
2. Проведем построение корреляционной матрици.
3. Найдем базис $u^{(1)},...,u^{(r)}$, соответствующий отличным от 0 собственным числам корреляционной матрици.
(До этого момента обычный алгоритм Анализа Главных Компонент (корреляционную матрицу раскладываем сингулярным разложением), на этом шаге мы имеем разложенный исходный ряд на компоненты. А вот далее непонятно, собственно сам прогноз)
4. Запишем систему алгебраических уравнений следующего вида:
$\begin{cases} & \sum_{j=1}^{r}{l_{j}u^{(j)}_{1}}=z^{(n+1)}_{1}\\ & ...\\ & \sum_{j=1}^{r}{l_{j}u^{(j)}_{\tau -1}}=z^{(n+1)}_{\tau -1} \end{cases}$ (12)
5. Исследуем систему на совместность
5.1 Если система не совместна, то исходный ряд не допускает продолжения.
5.2 Если система имеет решение, то исходный ряд имеет продолжение, это продолжение находится как решение уравнения
$\frac{z^{*}-\frac{1}{N-\tau +2}\left(\sum_{s=\tau }^{N}{f_{s}+z^{*}} \right)}{\sqrt{\frac{1}{N-\tau +2}\left\{(z^{*})^{2}+\sum_{s=\tau }^{N}{f^{2}_{s}} \right\}-\left\{\frac{1}{N-\tau +2}(z^{*}+\sum_{s=\tau }^{N}{f_{s}}) \right\}^{2}}}=\sum_{j=1}^{r}{l^{*}_{j}u^{(j)}_{\tau }}$, (13)
где $l^{*}_{1},...,l^{*}_{r}$ - решение системы (12). Уравнение (13) имеет, вообще говоря, два корня, отличающиеся знаком, который они доставляют левой части уравнения. Поэтому после решения (13) проблем с выбором корня не возникает.

Собственно что непонятно:

1. Система я так понимаю получается нелинейной? В каждом уравнении степень возрастает? Непонятно как решать такую систему, есть стандартные методы для таких?

2. Как решать уравнение (13) это что должен быть итерационный процесс какой-то что ли?!

Разъясните пожалуйста кто может, не понимаю как решается тут все
(Причем в самом АГК я разобрался, все работает )

[chessar]

1. Система (12) является линейной. Вверху же написан индекс, не зря же в скобочки специально взяли. И возрастает не степень, а номер вектора в базисе. Ну чтобы не путаться, запишите индексы снизу, например $u_{i,j}$ и $z_{i,n+1}$ ($i=1,\ldots,\tau$; $j=1,\ldots,r$). Верхний индекс $(j)$ - это номер вектора $u$, а $i$ в нижнем индексе - это $i$-ая координата вектора.
2. Никакой это не итерационный процесс, а по сути квадратное уравнение относительно $z^{\ast}$.

Почитайте сначала главу, со страницы 73, там все определения даны.

[logout2d]

Спасибо за ответ

Цитата:

1. Система (12) является линейной. Вверху же написан индекс, не зря же в скобочки специально взяли. И возрастает не степень, а номер вектора в базисе. Ну чтобы не путаться, запишите индексы снизу, например $u_{i,j}$ и $z_{i,n+1}$ ($i=1,\ldots,\tau$; $j=1,\ldots,r$). Верхний индекс $(j)$ - это номер вектора $u$, а $i$ в нижнем индексе - это $i$-ая координата вектора.

Цитата:

2. Никакой это не итерационный процесс, а по сути квадратное уравнение относительно $z^{\ast}$.

Вот оно что, сбили с толку индексы, я привык что степень пишут вверху, не мог понять как правильно составить систему, большое спасибо буду пробовать решать

Цитата:

Почитайте сначала главу, со страницы 73, там все определения даны.

Да я уже выучил наизусть все там Я же написал что понял и реализовал первую часть (сам АГК). Даже 2 опечатки там нашел, они меня тоже стопорили.

Огромное спасибо, буду разбираться дальше

[chessar]

Пожалуйста. Очень хорошо, что вы разобрались.

[logout2d]

Пробую применить на практике, вышеизложенную теорию
Дошел до решения (12).
Так как решаю в МатКаде (потом перевожу в С# код), решил применить общую формулу решения систем линейных уравнений:
$AX=B$, решение $X=A^{-1}B$
Не очень понимаю как составить матрици А и B.
Рассуждения:
В правой части (12) я полагаю уравнение гиперплоскости?
То есть в правой части нужно тоже написать сумматор?
И в левой части тоже уравнение гиперплоскости.
Значит одна строка системы уравнений будет выглядит так:
$u_{1}l_{1}+u_{2}l_{2}+...+u_{r}l_{r}=z_{1}l_{1}+z_{2}l_{2}+...+z_{r}l_{r}$
Так как u и z известны можно все перенести в левую сторону и $l$ с одинаковыми индексами сложить.
В итоге получаем:
$(u_{1}+z_{1})l_{1}+(u_{2}+z_{2})l_{2}+...+(u_{r}+z_{r})l_{r}=0$
Отсюда уже можно составить А, в нее войдут все множители $(u+z)$ и B состоящая из нулей.
Я правильно все понял?
А то у меня ничего пока не получается, видимо напутал с индексами опять...

[chessar]

logout2d,
у вас есть СЛАУ (система линейных алгебраических уравнений) (12):
$\left\{ \begin{array}{l} l_1u_1^{(1)}+l_2u_1^{(2)}+\cdots+l_ru_1^{(r)}=z_1^{(n+1)},\\ l_1u_2^{(1)}+l_2u_2^{(2)}+\cdots+l_ru_2^{(r)}=z_2^{(n+1)},\\ \cdots \\ l_1u_{\tau-1}^{(1)}+l_1u_{\tau-1}^{(2)}+\cdots+l_ru_{\tau-1}^{(r)}=z_{\tau-1}^{(n+1)}. \end{array} \right.$
c $r$ неизвестными $l_1,l_2,\ldots,l_r$ и с $\tau-1$ уравнениями. При этом $u_i^{(j)}$, $z_i^{(n+1)}$ - это числа (не векторы), являющиеся координатами векторов
$u^{(j)}=\left(\begin{array}{c}u_1^{(j)}\\ \vdots \\u_{\tau-1}^{(j)}\end{array}\right)$ и $z^{(n+1)}=\left(\begin{array}{c}z_1^{(n+1)}\\ \vdots \\z_{\tau-1}^{(n+1)}\end{array}\right)$.
Для удобства, перенесем для $u$ верхний индекс в скобочках вниз (это будет по сути номер столбца):
$u_i^{(j)}=u_{ij}$;
а также (т.к. в правой части системы рассматривается только один вектор $z$, а именно $(n+1)$-й), то обозначим его, скажем буквой $w$:
$w=z^{(n+1)}$, соответственно $w_i=z_i^{(n+1)}$.
(Везде считаем, что $i=1,2,\ldots,\tau-1$; $j=1,2,\ldots,r$).
В итоге имеем более понятный вид системы:
$\left\{ \begin{array}{l} u_{11}l_1+u_{12}l_2+\cdots+u_{1r}l_r=w_1,\\ u_{21}l_1+u_{22}l_2+\cdots+u_{2r}l_r=w_2,\\ \cdots \\ u_{\tau-1,1}l_1+u_{\tau-1,2}l_2+\cdots+u_{\tau-1,r}l_r=w_{\tau-1}. \end{array} \right.$
Обозначив через
$A=\left(\begin{array}{cccc}u_{11}&u_{12}&\cdots&u_{1r}\\ u_{21}&u_{22}&\cdots&u_{2r}\\ \vdots&\vdots&\ddots&\vdots\\ u_{\tau-1,1}&u_{\tau-1,2}&\cdots&u_{\tau-1,r}\end{array}\right)$ - $(\tau-1\times r)$-матрицу системы,
$l=\left(\begin{array}{c}l_1\\l_2\\ \vdots \\ l_r\end{array}\right)$ - вектор-столбец неизвестных, получаем систему в матричном виде
$Al=w$,
которую вы дальше можете решать либо методом Гаусса, либо какими-то численными методами.

[logout2d]

Огромное спасибо за предельно расписанное объяснение
Решение запрограммировал, вроде работает
Вектор решений $l$ по виду похож на собственные вектора, ну более менее что-то осмысленное получается. До этого мой вектор решений был больше похож на шум.

Теперь последний рубеж, решение (13)

1. Решение (13) дает всего 1 точку продолжения ряда?
Если да то для того чтобы найти следующую точку мне надо все процедуры повторить начиная с АГК и прогноз по новой и так для каждой новой точки?

2. Что такое $f$ мне непонятно, по аналогии с предыдущими главами в статье это исходный вектор, я правильно понял? Или же это восстановленные компоненты АГК, не очень понимаю этот момент.

chessar, огромное вам спасибо, без вас я бы долго парился

[chessar]

1. Да, он должен давать только одну точку (если решения будет два (т.к. это квадратное уравнение относительно $z^{\ast}$), то надо выбрать тот, знак которого соответствует остальным значениям исходного ряда). Если вы дальше до $N+2$ (и т.д.) хотите продолжить (уже продолженный до $N+1$) ряд $(f_i)^{N+1}_{i=1}$, то надо заново выполнять все построения, но уже для продолженного ряда $f$ до $N+1$. Ибо, такая именно задача и описана в книге. Но, наверное (с большой долей вероятности), там что-то можно оптимизировать и не выполнять лишних вычислений (и я думаю разработать более эффективный алгоритм для продолжения не на одну точку, а на несколько).
2. $f$ - это изначальный ряд длины $N$ (или числовая последовательность, вектор), который необходимо продолжить (экстраполировать), получив следующее (одно) значение в этой последовательности (такова постановка задачи).

[logout2d]

Цитата:

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

А есть какие-то конкретные соображения?

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

И даже эти мысли трудновыполнимы, потому что я использовал SVD из сторонней либы и поменять что-либо там не могу (до использования сторонней либы я пытался научиться сам делать SVD, поняв что на это уйдет куча времени я использовал сторонние наработки).