3.2. Образы числовых последовательностей

В качестве отправной точки для анализа выберем изображения-числовые последовательности, описанные в начале разд. 3.4 т. 1. Зная только конечную часть бесконечной последовательности, мы должны продолжить ее, используя обнаруженную регулярность. Это, конечно, зависит от того, что представляют собой основные арифметические операторы, которые можно применять при порождении последовательности.

Для описания имеющихся арифметических рекурсивных членов введем множество

линейных разностных операторов. Оператор La имеет вид

(3.2.1)

где Т обозначает оператор переноса i→i+1, Т⁰ - единичный оператор, l_k - функции аргумента t (l_n ≠ 0), причем n и {l_k} могут зависеть от а. Будет удобно потребовать, чтобы L_αφ = 0 и L_α, φ = 0 имели общим только нулевое решение φ = 0, если α ≠ α' и если мы имеем дело с бесконечномерными векторами φ = (φ₁, φ₂, φ₃, ...).

Выбор функций I зависит, конечно, от арифметических возможностей, однако по крайней мере следует допустить, что мы имеем алгебру , замкнутую относительно переноса Т, со счетным базисом (λ₁, λ₂,...), такую, что для произвольной l∈ существуют действительные постоянные a_υ:

(3.2.2)

Поскольку алгебра замкнута относительно T, имеет место соотношение

(3.2.3)

и так как есть алгебра, то справедливо сопутствующее соотношение

(3.2.4)

{a_υμ} и {a_υμχ} - структурные постоянные алгебры относительно Т и умножения.

Запишем множество решений Φ:

(3.2.5)

здесь L обозначает произвольный оператор вида

(3.2.6)

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

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

Если известно, что величина n в (3.2.6) самое большее равна некоторому натуральному числу n_max, то соответствующее множество операторов L можно параметризовать конечным числом параметров с помощью (3.2.2) - (3.2.4). Для каждого варианта выбора этого вектора параметров решения образуют конечномерное векторное пространство, и образующие можно вводить как базис в этом пространстве. Для того чтобы установить, можно ли представить какую-либо конечную часть заданной последовательности в виде линейной комбинации элементов базиса, достаточно простой линейной операции. Варьируя вектор параметров, можно отыскивать точное соответствие, и, если добиться соответствия не удается, следует увеличить значение n_max на единицу и снова повторить цикл поиска.

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

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

(3.2.7)

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

Две конфигурации отождествляются, если соответствующие композиции (в (3.2.7) это было бы L⁽¹⁾⋅L⁽²⁾⋅... ⋅L⁽ⁿ⁾) образуют один и тот же оператор. Такое отношение R представляет собой правило идентификации (см. разд. 3.1, т. 1) и, следовательно, определяет изображения как классы эквивалентности в (R). С помощью (3.2.2.) - (3.2.4) изображение можно представить в виде

(3.2.8)

здесь алгебра изображений натянута на действительные скаляры b_rs.

Очевидно, что алгебра изображений определяет бесконечную последовательность I = (i₁, i₂,...)" если известен достаточно длинный начальный отрезок I. Бесконечная последовательность I не должна, однако, обязательно определять однозначно; в этом нет необходимости потому, что мы имеем дело лишь с конечным отрезком I. Неважно, что представляет собой хотя мы будем пытаться выбирать некоторую "простую" алгебру которая обеспечивает соответствующий результат.

Мы имеем дело с двумя бесконечномерными алгебрами изображений и связанными между собой так, как было описано. На алгебре ?Г имеет место деформация маски (см. разд. 4. 5,т. 1) с окном w_t = ( 1,2, ..., t), так что

(3.2.9)

где t - длина заданного отрезка. Деформации D, разумеется, ковариантны.

Чтобы по заданному I^D_t найти допустимую алгебру следует определить b_rs, такие, что

(3.2.10)

где р - наибольшее значение s, появляющееся в конечной сумме (3.2.8). Эта процедура приемлема с вычислительной точки зрения и сводится к решению системы линейных уравнений. Если система не имеет решений, то величина р увеличивается на единицу и повторяется цикл алгоритма. Вполне может оказаться и так, что для какого-то t получено точное согласие, но соответствующая не работает как продолжение при увеличении t. В этом проявляется самая суть задачи: невозможно точно предсказать, когда будет обеспечено полное восстановление, можно быть уверенным только в том, что в конечном счете оно будет достигнуто.

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

(3.2.11)

где а и b действительные, b > 0; из этих образующих формируется множество разностных операторов L. Этот случай соответствует наличию у характеристического уравнения разностного оператора единственного действительного корня а или пары комплексносопряженных корней a±i√b. Тогда уравнение LI = 0 имеет решения, которые можно записать в виде тригонометрических и экспоненциальных многочленов. Пытаться представить таким образом It и отыскивать подходящие значения параметров, соответствующие характеристическим корням, - это черная работа, и лучше воспользоваться методом, предлагаемым в (3.2.10).

Нетрудно составить простую программу, обрабатывающую (3.2.10) как неоднородную линейную систему (см. ниже). В случаях, подобных приведенным в начале разд. 3.4 т. 1, полное восстановление при небольших значениях t достигается с минимальной затратой вычислительных усилий. Небольшой вычислительный эксперимент показал, что так же дело обстоит и при большем р. Объясняется это тем, что алгоритм восстановления использует структуру образа в процессе проведения соответствующего синтеза, основанного на разностных операторах как образующих.

Возникает, однако, вопрос: - устойчив ли метод восстановления, если при вычислении представленного конечного отрезка допускались случайные ошибки, не помешает ли это достичь приемлемого качества восстановления?

Здесь возникают добавочные деформации, обусловленные ошибками вычислений, и уравнение (3.2.10) следует заменить уравнением, правая часть которого может быть ненулевой с некоторой положительной вероятностью, скажем ε > 0. Алгоритм при этом необходимо модифицировать, так как теперь мы не можем надеяться получить точное согласие. При постоянных функциях I наше уравнение можно представить в следующем виде:

(3.2.12)

или, в матричной форме,

(3.2.13)

где

(3.2.14)

(3.2.15)

Очевидно, что уравнение (3.2.12) представляет схему авторегрессии. Вместо оператора получаем случайный оператор - YT⁰, который не должен обязательно принимать значения из , таким образом, появляются гетероморфные деформации. Для измерения усилия этих деформаций при заданном t используем функцию усилия e(d) = ||Y||. Тогда восстановление по минимуму усилия эквивалентно решению уравнений (3.2.12) -(3.2.14) методом наименьших квадратов при A, параметризующем , что приводит к

(3.2.15)

Это опять можно реализовать с помощью простой программы. Напомним, что величина р заранее неизвестна, поэтому начинаем со значения р = 1 и увеличиваем его до тех пор, пока ошибка метода наименьших квадратов не станет достаточно малой. Реализуя эту процедуру, необходимо иметь в виду следующее. Если р₀ - истинное значение (наименьшее возможное), то случайная матрица М^ТМ, по-видимому, будет близка к особенной, если р > р₀. Чтобы проверить это, мы воспользовались критерием

(3.2.16)

Когда это значение резко увеличивается, оно сигнализирует о том, что значение р выбрано слишком большим.

В качестве численного примера возьмем первый пример из разд. 3.4 т. 1, который, как нетрудно убедиться, удовлетворяет уравнению = T² - 2T + T₀, так что А = (2, -1). На рис. 3.2.1

верхний график представляет заданную последовательность при t = 60, а нижний -деформации, вызванные случайными ошибками вычислений при ε = 10%. Метод восстановления, описанный выше, приводит при р = 2 к средней кривой. Восстановление произведено, как будто, довольно неплохо. Этот метод восстановления обеспечивает также при А^* = (1,948; -0,9547) экстраполяцию изображения, по крайней мере на коротком "дополни- тельном" временном интервале.

Рис. 3.2.1

Поведение критерия (3.2.16) чрезвычайно интересно. При некотором заданном значении t, большом, но фиксированном, рассмотрим матрицу М^TМ по мере увеличения р от значения р = 1. Вычислительный эксперимент, один из результатов которого был представлен на рис. 3.2.1, как будто, свидетельствует о том, что эти матрицы ведут себя приблизительно так же, как конечные квадратные блоки большой матрицы. Последняя не особенная, хотя и не очень хорошо обусловлена. Если это так, то можно ожидать, что Кр увеличивается при p↑p₀ а затем его значение остается приблизительно постоянным. Этот факт можно использовать в качестве правила остановки: по достижении соответствующего уровня уменьшить значение р на единицу. По-видимому, имеет смысл провести точный анализ поведения К_р, однако это еще не было сделано.

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