XXI Зарубин B.C. Математическое моделирование в технике (1081441), страница 60
Текст из файла (страница 60)
В данном случае п, ) пм и поэтому после выбора и просмотра массива АИ переключатели в массиве 1С займут позиции, представленные в табл. 7.1. Таблица 7.1 10 4 5 Номер позиции в массиве ТС 1 0 0 0 1 0 Переключатель При просмотре второго массива (в данном случае массива ВМ) замена нуля на переключатель в массиве 1С происходит аналогично, но только в тех позициях, в которых остались нули после просмотра первого массива.
Для рассматриваемого примера при просмотре массива ВХ замена нуля на переключатель в массиве 1С произойдет лишь в позиции 5, так как в позициях 4 и 10 такая замена произошла при просмотре массива АМ. В итоге массив 1С примет вид, представленный в табл. 7.2. Таблица 7.9 9 10 5 6 3 4 1 2 Номер позиции в массиве ХС 0 0 0 1 Переключатель 0 0 1 1 1 0 Замена нуля на переключатель при просмотре массива ВД7 означает, что после сложения векторов а и Ь вектор с наряду Т.Л. Операции е разреженными матрицами 395 с и ненулевыми координатами может иметь еще несколько ненулевых координат.
Поэтому после каждой такой замены номер соответствующей позиции массива 1С следует заносить в позиции, добавляемые к массиву АМ при формировании массива СМ. В данном случае такая замена произошла лишь один раз в позиции с номером 5 массива 1С. Поэтому к массиву АЖ следует добавить лишь одну позицию, в которую нужно записать этот номер, а массив индексов ненулевых элементов искомого вектора с будет иметь пе = па+ 1 позиций и примет вид СФ= (10,3,7,4, 51. После формирования массива СЯ, определяющего пока лишь структуру вектора с = а+ Ь, вычислительный этап алгоритма сложения векторов можно выполнить разными путями.
На первый взгляд достаточно прост следующий путь. В первой позиции этого массива стоит номер 10 индекса ненулевого элемента сю = ам + Ью искомого вектора. Для его вычисления необходимо путем просмотра массивов АМ и ВМ найти номера позиций, которые в массивах АЛ и ВЛ соответственно занимают значения аю = 0,2 и бю = 0,5, и только потом сложить эти значения, а затем перейти ко второй позиции массива СМ и т.д. Такой путь связан с выполнением большого количества операций просмотра массивов и поэтому неэффективен.
Целесообразно поступить следующим образом. Сначала при помощи массива СМ формируем так называемый массив УС указателей длиной и, начальные значения которых равны нулю. В рассматриваемом примере в первой позиции массива СИ стоит число 10, т.е. СФ(1) = 10. Это означает, что в первой позиции массива СВ длиной пе = 5, предназначенном для записи координат искомого вектора с, будет после вычисления записана координата сш. Поэтому полагаем УС(10) =1. Так как СМ(2) = 3, то полагаем УС(3) = 2, и вообще при СМ(й) = т имеем УС(т) = й. В итоге получим массив указателей, представленный в табл. 7.3. Далее формируем массив СВ длиной пе = 5 с нулевыми начальными значениями элементов.
Просматривая массивы АФ 396 7. АЛГОРИТМИЗАЦИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ Таблица 7.8 6 7 3 4 10 Номер позиции в массиве 1С 0 3 2 4 Указатель и Втт', при помощи массива стС определяем позиции массива СВ, в которых должна быть записана сумма соответствующих координат векторов а и Ь. Например, в первой позиции массива Аттт находим АФ(1) = 10. Этому значению соответствуют указатель УС(10) = 1 и значение АВ(1) = 0,2 координаты ате. Следовательно, можно записать СВ(1) = О+ АВ(1) = 0,2.
Затем находим АЖ(2) = 3, УС(3) = 2, АВ(2) = 0,3 и СВ(2) = О+ 0,3 = = 0,3. Ясно, что в итоге просмотра массива Аттт получим массив СВ = (0,2,0,3, 0,4, — 0,7,0), отличающийся от массива АВ лишь одной дополнительной позицией с нулевым значением. Поэтому в данном случае можно было бы не просматривать массив Атт', а сразу сформировать массив СВ в указанном виде.
Теперь переходим к просмотру массива Вот. Так как В1тт'(1) = 5, то стС(5) = 5, ВВ(1) = 0,6 и СВ(5) = СВ(5) + + ВВ(1) = О+ 0,6 = 0,6. Затем определяем ВМ(2) = 4, 77С(4) = = 4, ВВ(2) = 0,7 и СВ(4) = СВ(4) + ВВ(2) = — 0,7+ 0,7 = О. Наконец, по В1т1(3) = 10 находим стС(10) = 1, ВВ(3) = 0,5 и СВ(1) = СВ(1) + ВВ(3) = 0,2+ 0,5 = 0,7. В итоге получаем массив СВ = (0,7, 0,3, 0,4, О, О, 6). Отметим, что при сложении один из ожидаемых ненулевых элементов массива СВ оказался равным нулю.
Взаимное уничтожение действительных чисел происходит достаточно редко, и поэтому можно примириться с тем, что некоторые из хранимых координат разреженного вектора на самом деле являются нулями. Но при сложении специальных матриц (например, матриц инциденции в теории графов (Х1Х)), имеющих большое число элементов, равных ~1, такие случаи будут частыми, что потребует модифицировать алгоритм сложения векторов. 7.а. Операции е разреженными матрицами 397 Описанная процедура вычислительного этапа содержит число элементарных операций, пропорциональное сумме па+ пы К этому числу следует добавить п операций засылки нулей при формировании массива переключателей.
Отметим, что за один индексный и один вычислительный этапы можно сложить любое число разреженных векторов, а также вычислить их линейную комбинацию. При этом массив переключателей может объединить любое число массивов с индексами ненулевых элементов этих векторов. Этот же массив переключателей можно использовать при сложении разреженных матриц, когда приходится складывать несколько пар векторов, соответствующих, например, столбцам этих матриц. В этом случае в массиве переключателей каждому столбцу искомой матрицы должен соответствовать свой переключатель (например, номер этого столбца). Пусть теперь требуется вычислить скалярное произведение двух разреженных векторов а и Ь размера и при компактном неупорядоченном варианте их хранения в массивах АВ и ВВ длиной и и пь соответственно.
Прямолинейная попытка вычисления скалярного произведения привела бы к необходимости много раз просматривать массив ВМ с индексами ненулевых координат Ь; вектора Ь. Убедимся в этом на примере умножения тех же векторов, что и при сложении. Действительно, после нахождения в первой позиции массива АВ ненулевой координаты аю = 0,2 вектора а необходимо определить значение сомножителя Ью. Для этого надо просмотреть весь массив ВЛ и установить, что этому индексу соответствует третья позиция этого массива, затем из третьей позиции массива ВВ извлечь значение Ью = 0,5, наконец, вычислить аюЬю = 0,1 и запомнить это значение.
Во второй позиции массива АВ записана координата аз = 0,3. Снова придется повторить процедуру просмотра массива ВФ только для того, чтобы убедиться, что Ьз = О. В итоге число элементарных операций при просмотре будет равно папы 398 7. АЛГОРИТМИЗАЦИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ Более эффективен алгоритм скалярного умножения, использующий массив индексов У длиной п.
Этот массив формируется за один просмотр массива АФ, и для рассматриваемого примера его вид представлен в табл. 7.4. Таблица 7.4 9 10 1 2 Номер позиции в массиве ХС Индекс 0 0 0 1 0 0 Из табл. 7.4 следует, что значение аз записано в позиции 2 массива АВ, значение а4 — в позиции 4, а7 — в позиции 3 и аш — в позиции 1 этого массива, а все остальные координаты вектора а равны нулю.
Затем за один просмотр массива ВФ при помощи массива У удается найти все сомножители, которые дадут ненулевые произведения а,6; координат векторов а и Ь, вычислить и просуммировать эти произведения, получив искомый результат. В самом деле, на первом шаге просмотра массива ВМ устанавливаем, что ВХ(1) = 5, но 57(5) = О, т.е. аз = О, и, значит, произведение азЬз = 0 не даст вклада в искомое скалярное произведение векторов. На втором шаге находим ВМ(2) = 4 и У(4) = 4 ~ О. Поэтому из массивов АВ и ВВ извлекаем значения АВ(4) = а4 = 0,7 и ВВ(2) = 64 = — 0,7 соответственно, находим а464 = — 0,49 и записываем этот результат в ячейку 6 памяти, выделенную для значения скалярного произведения.
Наконец, на последнем (третьем) шаге просмотра массива ВФ, определяемом значением пь = 3, имеем ВФ(3) = 10 и У(10) = 1 уЕ О, из массивов АВ и ВЛ извлекаем значения АВ(1) = аш = 0,2 и ВВ(3) = Ьш = 0,5 соответственно, вычисляем ашЬш = 0,1 и получаем искомое значение Ь = Ь+ ашЬш = — 0,49+ 0,1 = — 0,39 скалярного произведения заданных векторов. Описанный алгоритм особенно удобен тогда, когда один и тот же вектор а нужно скалярно умножить на несколько различных векторов. В этом случае массив У формируется один 7.е. Операции с раареиеииыми матрицами 399 1 О О 2 8 9 3 О О 4 8 О 5 9 8 6 О 7 1 О О О О О О О 2 8 9 О О О О 8 3 О О О О О 9 О 4 8 О О 1 О О 8 5 9 8 1 О О О 9 6 О 1 О О О 8 О 7 В этом случае в матрице А размера 7 х 3 записана верхняя полулента, причем в первом столбце хранятся элементы главной раз и многократно используется при однократном просмотре массива индексов координат каждого из сомножителей вектора а.
Наряду с хранением симметрической разреженной матрицы по столбцам или строкам может оказаться рациональным ее хранение в виде так называемой ленты. Квадратную матрицу называют ленпаочиой, если все ее ненулевые элементы заключены внутри ленты, образованной побочными диагоналями. Для симметрической ленточной матрицы А ее элементы ае = О при ~1 — Я ) Д Е М и аа а е ~ О либо аа ье.д ~ О хотя бы для одного значения Й е 1Ч. Значение ~3 называют полушириной ленты, а значение 2,В+ 1 — ее шириной.
При ~3 = 1 ленточную матрицу называют трехдиагональной ~П?1, при 13 = 2 — плтидиаеоиальной, а при Д = О ленточная матрица вырождается в диагональную. Таким образом, в каждой строке симметрической ленточной матрицы не более 2р'+ 1 ненулевых элементов. Если это значение существенно меньше порядка и такой матрицы, то ее рационально хранить в виде верхней или нижней полуленты, т.е. в виде части ленты выше или ниже главной диагонали, включая главную диагональ. При этом используют диагональную схему хранения в виде прямоугольной матрицы А размера п х ф+ 1), иллюстрируемую следующим примером для матрицы А порядка п = 7 с полушириной ленты ф = 2: 400 7. АЛГОРИТМИЗАЦИЯ МА ТЕМА ТИЧЕСКИХ МОДЕЛЕЙ диагонали, а в следующих столбцах — элементы более коротких верхних побочных диагоналей.
При этом в столбце матрицы А с номером д', будет не определено д. — 1 элементов. При хранении нижней полуленты матрицы А главную диагональ записывают в последний столбец матрицы А, а нижние побочные диагонали — в остальные столбцы со сдвигом на одну позицию вниз при каждом смещении влево. Диагональная схема хранения удобна с точки зрения доступа к элементам матрицы А, поскольку имеется простое однозначное соответствие между положением каждого ненулевого элемента а; в матрице А и его положением в матрице А, где он сохраняет номер 1 строки, а его номер столбца принимает значение д — 1 при хранении верхней полуленты и значение д — г+ ~3+ 1 при хранении нижней полуленты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
