Участник:Lonalone/Генерация гауссовского вектора методом линейных преобразований

Материал из Алговики
Перейти к навигации Перейти к поиску

Автор описания: Меньших И. М.


1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Идея алгоритма заключается в линейном преобразовании n-мерного случайного вектора [math]Y[/math], компоненты которого независимы и одинаково распределены по нормальному закону со стандартными параметрами, в случайный вектор [math]X[/math] с требуемыми корреляционной матрицей и вектором математических ожиданий.

1.2 Математическое описание алгоритма

Даны корреляционная матрица [math]Q[/math], вектор математических ожиданий компонент вектора [math]X[/math]:

[math] Q = \|q_{ij}\| = \| M[(X_{i} - m_{x_{i}})(X_{j} - m_{x_{j}})]\|, \\ M = (m_{x_{1}}, m_{x_{2}}, ..., m_{x_{n}})^T. [/math]

Требуется найти такую матрицу [math]B[/math], которая позволяла бы получить вектор [math]X[/math] с требуемыми характеристиками в результате линейного преобразования [math]X = BY + M[/math], где [math]Y[/math] — n-мерный случайный вектор с независимыми нормально распределенными компонентами со стандартными параметрами. Эти компоненты можно получить с помощью приближения по ЦПТ (метод композиции[1]) случайными величинами, распределенными по равномерному закону на [math][0,1][/math].

Будем искать матрицу [math]B[/math] в виде нижней треугольной матрицы. Перейдем от матричной записи к системе алгебраических уравнений:

[math] \begin{pmatrix} X_{1} \\ X_{2} \\ \vdots \\ X_{n} \end{pmatrix} = \begin{pmatrix} b_{11} & 0 & \cdots & 0 \\b_{21} & b_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nn} \end{pmatrix} \times \begin{pmatrix} Y_{1} \\ Y_{2} \\ \vdots \\ Y_{n} \end{pmatrix} + \begin{pmatrix} m_{x_{1}} \\ m_{x_{2}} \\ \vdots \\ m_{x_{n}} \end{pmatrix} \Rightarrow [/math]


[math] \begin{cases}X_{1} - m_{x_{1}} = b_{11}Y_{1} \\X_{2} - m_{x_{2}} = b_{21}Y_{1} + b_{22}Y_{2} \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\X_{n} - m_{x_{n}} = b_{n1}Y_{1} + b_{n2}Y_{2} + \cdots + b_{nn}Y_{n} \end{cases} [/math]


Поскольку компоненты вектора [math]Y[/math] независимы и имеют стандартные параметры, справедливо выражение:

[math] M[Y_{i}Y_{j}] = \left\{\begin{matrix} 1, &i = j, \\ 0, &i \not= j, \end{matrix}\right . [/math]

Почленно перемножив сами на себя и между собой соответственно левые и правые части уравнений системы и взяв от результатов перемножения математическое ожидание, получим систему уравнений вида:

[math] \begin{cases} M[(X_{1} - m_{x_{1}})(X_{1} - m_{x_{1}})] = M[b_{11}Y_{1}b_{11}Y_{1}], \\M[(X_{1} - m_{x_{1}})(X_{2} - m_{x_{2}})] = M[(b_{21}Y_{1} + b_{22}Y_{2})b_{11}Y_{1}], \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \end{cases} [/math]

Как легко увидеть, в левых частях полученной системы уравнений располагаются элементы заданной корреляционной матрицы [math]Q[/math], а в правых — элементы искомой матрицы [math]B[/math]. Последовательно решая эту систему, получаем формулы для расчета элементов [math]b_{ij}[/math]:

[math] b_{11}=\sqrt{q_{11}}; b_{21}=\frac{q_{12}}{\sqrt{q_{11}}}; b_{22} = \sqrt{q_{22} - \frac{q_{12}}{q_{11}}}, \cdots [/math]

Формула для расчета любого элемента матрицы преобразования [math]B[/math] имеет вид:

[math] b_{ij} = \frac {q_{ij} - \sum_{k=1}^{j-1} b_{ij} b{jk}} {\sqrt{q_{ij} - \sum_{k=1}^{j-1} b^2{jk}}}, \quad 1 \leqslant j \leqslant i \leqslant n. [/math]

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. 1,0 1,1 Балдин К.В., Уткин В.Б. Информационные системы в экономике. - М.:ИТК Дашков и К, 2008. - 395 с.
  2. https://ru.wikipedia.org/wiki/Многомерное_нормальное_распределение