Рекуррентные вычисления на многомерных сетках

Рассмотрим задачу рекуррентного формирования случайного поля (СП)  на n-мерной прямоугольной сетке . При этом предполагается, во-первых, существование некоторой процедуры последовательного перебора точек , т.е. правила линейного упорядочения точек , , на основе которого можно сказать, что элемент  предшествует элементу  или наоборот. Во-вторых, должен быть задан алгоритм, определяющий, каким образом очередное значение СП  может быть найдено на основе ранее вычисленных значений , где  некоторая область индексов , предшествующих очередному элементу . Такую область  конечных размеров обычно называют каузальным окном, каузальной маской или областью локальных состояний [6,7]. Наконец, для формирования СП  с определёнными вероятностными характеристиками на каждом шаге рекуррентных вычислений функция  должна включать в качестве аргумента совокупность ,  вспомогательных случайных величин.

Таким образом, представление СП на основе рекуррентной; процедуры должно иметь следующий вид:

,     (1)

где  - области элементов , на которых уже определённо предыдущие значения СП ; ,  - вообще говоря, нелинейные скалярные или векторные функции двух тензорных аргументов. Наиболее простым частным случаем (1) является линейное стохастическое уравнение

,    (2)

с белым гауссовским СП , соответствующее известному уравнению авторегрессии - скользящего среднего [1] для случайных последовательностей. Однако в отличие от своего одномерного аналога, свойства СП , порождаемого (2), в настоящее время изучены не полностью даже для моделей (2) с постоянными коэффициентами  и не изменяющимся видом областей  и :

.    (3)

Важным частным случаем (3) является уравнение многомерной авторегрессии [3,5]

, (4)

свойства которого для двумерного СП изучались в большом числе работ.

Приведённые уравнения (3) и (4) описывают алгоритмы формирования СП  в точке . При этом предполагается, что в нашем распоряжении имеются все значения , , , СП, вычисленные на предыдущих шагах или заданные в качестве начальных условий. Именно такие процедуры будем называть пространственно рекуррентными. Заметим, что при белом поле  и конечных размерах области  подобных проблем хранения или рекуррентного формирования массива , не возникает. Таким образом, возможности пространственных рекуррентных вычислений по формулам (1), (2), (3) или (4) зависят от вида области локальных состояний , порядка последовательного

просмотра пространственной сетки  (правила развертки  в последовательность индексов) и соответствующих начальных условий.

Для иллюстрации рассмотрим двумерное СП , , на прямоугольной (MxM)-сетке  (рис.1). На этом же рисунке показана одна из возможных областей локальных состояний , допускающих рекуррентные вычисленная при последовательном, строка за строкой, формировании массива .

Рис. 1.

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

Описанная линейная развёртка определяет порядок чередования индексов  если , или  и , согласующийся с видом маски G, и обеспечивающий возможность рекуррентных вычислений по формулам . Для приведённой на рис.1 маски  существуют и другие способы развёртки для рекуррентного формирования СП. Одним из них является развёртка области  по строкам и диагоналям. В подобных ситуациях появляется возможность сравнения нескольких способов линейного упорядочения элементов  и выбора лучшего из этих способов. Вместе с тем можно привести и такие примеры масок  и , показанных на рис.1, для которых не существует ни одного способа построения развёртки сетки , обеспечивающего рекуррентное формирование СП.

Таким образом, при построчном сканировании на прямоугольной сетке  все множество масок, допускающих рекуррентное вычисления» может быть сведено к одной несимметричной полуплоскостной области G локальных состояний, представленной на рис.2. Но такую маску, а, следовательно, и любую каузальную область G, можно отобразить на область  одного квадранта (рис.3) с помощью преобразования координат ,  [6]. На рис. 2 такое преобразование можно представить как изменение направления сканирования. Вместо сканирования по строкам и столбцам упорядочение элементов производится по строкам и диагоналям. Итак, множество всех областей , допускающих рекуррентные вычисления, сводится к области одного квадранта (рис. 3).

Рис. 2

Рис. 3

Для того, чтобы уменьшить число слагаемых в (3), (4) и упростить анализ, введём векторные СП , .

Выбирая в качестве компонент такого вектора значения СП , можно привести уравнение (3) с любой n-мерной маской  одного квадранта и  к простейшему виду:

,        (5)

где  - единичный лектор k-й координатной оси; :  и  матрицы. Соответственно уравнение (4) пространственной авторегрессии после введения векторных обозначений перепишется следующим образом [3,5]:

   (6)

Размерность  вектора  необходимая для преобразования уравнения (3) в (4), определяется видом области . Например, для плоской области  с ненулевыми коэффициентами  в точках , отмеченных темными кружками (рис.3), необходимо включить в  элементы , , , , , , , . При этом уравнение (3) может быть переписано в виде , позволяющем определить все элементы матриц , , , ,  по известным коэффициентам , , , , входящим в формулу (5).

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

Таким образом, любые стохастические разностные уравнения (3) или |4), допускающие рекуррентные по развёртке вычисления на прямоугольной сетке , могут быть с помощью преобразования координат и последующего введения векторного СП представлены в форме (5) или (6) с минимальным числом слагаемых.