Вычислительная математика

1. Упорядоченные множества элементов. Структура

и  способы представления  многомерных матриц. 

1.1. Теоретическая часть. 

     Круг  задач, которые представляются дискретными  моделями, чрезвычайно широк и  разнообразен: графы, транспортные потоки, логические системы, информацинно-поисковые системы, системы распознавания образов и многие другие. Особую трудность в решение дискретных задач вносит специфика многоуровневого управления, заключающаяся в том, что в дискретных моделях используются многоиндексные переменные. Например, множество А{i,j,k,l,m}, А - оценка, i - номер предмета, j - номер преподавателя, k - время, l - номер группы, m - номер студента удобно представлять с помощью многомерных матриц. 

      Многомерной матрицей (ММ) называется упорядоченная совокупность многоиндексных элементов a_i1i2…iW, где i_a=1,2,…,n_a; Целые положительные числа W, N_A=n₁n₂…n_W,n_a называются соответственно размерностью матрицы А, размером матрицы А, размером индекса i_a. Размерность W показывает число индексов в обозначении элементов a_i1i2…iW матрицы. Размер N_A матрицы А указывает общее число элементов матрицы. Размер индекса n_a показывает, сколько значений (от 1 до n_a) пробегает соответствующий индекс.

     Структура многомерных матриц определяется структурой их индексов. Структура индекса может быть столбцовой или строчной. Индексы, имеющие, например, строчную структуру (строчные индексы), показывают положение элементов внутри какого-либо столбца. При индексном представлении элементов матрицы целесообразно ставить знак + или – соответственно над столбцовым или строчным индексом. Например, - элементы обычной двухмерной (плоской) матрицы. Общее представление многомерной матрицы А имеет вид А = А(p,g), где р – число столбцовых индексов, g – число строчных индексов. Для получения индексного представления многомерной матрицы вводится помечивание индексов. Пометка начинается с последнего индекса, который при g>0 принимается за строчный. Далее столбцовые и строчные индексы чередуются до тех пор, пока один из видов индексов не исчерпывается. При p³g все оставшиеся индексы принимаются за столбцовые, при p<g – за строчные. Числа p и g  в сумме дают размерность W матрицы А: p+g=W. Если матрица А является функциональной, например зависит от времени t, от пространственных координат x, y и т.д., то структурные числа p  и g следует отделять от аргументов точкой с запятой, например A=A(p,g;t,x,y). Для наглядного представления многомерной матрицы используют табличное представление.  

     Табличное представление многомерной матрицы – это блочно-иерархическая таблица, отображающая на плоскости структуру матрицы и численные значения элементов. Иерархия согласована с иерархией индексов таким образом, что крайним левым индексам соответствуют наиболее крупные блоки. При этом столбцовые индексы изменяются в столбцах, а строчные – в строках. Примеры представления многомерных матриц приведены в таблице 1. 
 
 
 
 
 
 
 

                                                                                                 

 Таблица 1

 

     В некоторых частных, но важных случаях приходится пользоваться плоскими табличными представлениями многомерной матрицы, которые являются обычными плоскими матрицами и получаются из табличного представления путем снятия всех перегородок. Их обозначают следующим образом: А_табл = {A(p,g)}_табл.

     В ряде случаев записи математических выражений удобно представлять многомерные матрицы с помощью мультииндексов

                                           ,                                       (1.1)

где p⁺ - столбцовый мультииндекс, имеющий вид столбца    

p⁺ = [i₁⁺, i₂⁺,…,I_p⁺]^T;

- строчный мультииндекс, имеющий  вид строки  =[j₁^-, j₂^-,…,j_q^-]^T.

     Следует отметить, что обозначение мультииндексов в соотношении (1.1) является условным, так как индексы должны располагаться в соответствии с правилом помечивания, т.е. чередоваться, а не группироваться по столбцовому и строчному признакам, как это следовало бы из буквального понимания соотношения (1.1). 

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

 

1.2. Метод гиперплоскостей для построения выпуклой области дискретного конечного множества элементов 

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

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

     1. Выбираются произвольным образом первые (N+I) граничные точки и строятся по ним (N+1) гиперплоскости. Для каждой построенной гиперплоскости запоминаются координаты граничных точек, по которым она построена, и координаты ее вершины.

      Вершиной данной гиперплоскости условимся  называть ту точку из выбранных (N+1) точек, через которую не проводится гиперплоскость.

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

      Генеральных гиперплоскостей для  данной граничной точки может  быть несколько, особенно при построении многомерных областей работоспособности. Поэтому поиск генеральной гиперплоскости осуществляется среди всех ранее построены гиперплоскостей.

     Отсутствие  генеральной гиперплоскости для граничной  точки означает, что  точка находится  внутри области, образованной ранее проведенными гиперплоскостями.  

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

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

     4. Выбирается следующая по порядку граничная точка и все повторяется с п.2. (После перебора всех граничных точек процесс построения области работоспособности заканчивается (рис.1.) и производится определение знаков ³ и £ для системы линейных неравенств.) 

     Знаки неравенств ³ и £ определяются в результате подстановки координат вершин гиперплоскости в уравнение гиперплоскости. При этом используется свойство вершин принадлежать области работоспособности. Символ £ соответствует отрицательному знаку результата подстановки, символ ³ – положительному. Для удобства использования результатов построения области работоспособности все неравенства приводятся к виду ³ 0. 

Блок-схема алгоритма  построения области работоспособности  по граничным точкам приведена на рисунке 2. 

Рисунок 2 - Блок-схема алгоритма построения выпуклой области дискретного конечного множества элементов. 
 
 
 

     ПРИМЕР: Множество точек некоторого объекта задано матрицей:

        Х ₁   Х₂

     1  1     3

     2  7     3

     3  7     5

     4  1     5 

Попадает  ли точка с координатами (5;5) в область работоспособности.

а).  Построим область множества неупорядоченных  элементов при помощи метода гиперплоскостей (рис.3.). 

б). Составляем систему неравенств, ограничивающую область.

Сначала записываем линейную форму

             Ах₁ + Вх₂ + С = 0

1. (1-2) : 0х₁+0,3х₂-1=0;

2. (2-3) : -0,2х₁+0х₂+1,4=0;

3. (3-4) : 0х₁+0,1х₂-1=0;

4. (4-1) : -0,2х₁+0х₂+0,2=0; 

В линейную форму равенства подставляем  координаты вершины. Если значение равенства положительное, то соответствующее равенство заменяется знаком  >, если отрицательное – то <. Получим: