Методы решения систем с разреженными матрицами. Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 14 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

- 14 -
1
5
9
4
3
7
10
:
JC
3.3. Сложение РМ
Пусть на входе заданы две РМ
)
(
,
m
n
А
×
в неупорядоченном
РСФ . На выходе требуется получить
А
C
+
=
в том же формате .
Для решения этой задачи нам потребуется вспомогательный ЦМП
Y
и
РВН
X
. Размерность этих массивов равна числу столбцов
A
и
B
:
m
X
Y
=
=
dim
dim
. В основе алгоритма лежит идея поочередного сложения
строк матриц
A
и
B
как РВ с помощью РВН.
Алгоритм
1. Символический этап
(формирование
IC
JC
,
)
0
1
.
1
=
i
(номер строки).
0
2
. С помощью
JA
IA
,
и
JB
IB
,
определяем списки, соответствующие
i
-м строчкам матриц
A
и
B
и сливаем эти списки методом ПП с
помощью ЦМП
Y
. Список, полученный в результате слияния, помещаем в
1-ю свободную позицию массива
JC
.
0
3
. Полагаем
1
+
=
i
i
и идем на
0
2
. Повторяем действия до тех пор, пока
n
i
≤
. В результате получаем
JC
.
0
4
. Для получения
IC
достаточно на каждом этапе запоминать первую
свободную позицию
JC
.
2. Численный этап
(последовательное сложение строк
А
,
с помощью
РВН)
0
1
.
1
=
i
.
0
2
. С помощью
IC
JC
,
определяем список, полученный в результате
слияния списков столбцовых индексов
i
-й строки массивов
JA
и
JB
.
0
3
. С помощью этого списка и РВН
X
складываем
i
-е строки матриц
A
и
B
, как РВ . Результат сложения помещаем в текущие свободные
позиции вектора
CN
в соответствии с порядком столбцов из
JC
.
0
4
.
1
+
=
i
i
и идем на
0
2
. Повторяем действия до тех пор, пока
n
i
≤
. В
результате получим
CN
.
Замечание . После каждого сложения строк РВН
X
должен быть приведен
в нулевое состояние .
Задача 20. Даны две матрицы
А
,
. Найти
А
C
+
=
.
;
9731:
4261543153:
1112733412:
−
−
−
IA
JA
AN
                                      - 14 -

                          JC :   10     7      3   4   9    5    1

        3.3. Сложение РМ
        Пусть на входе заданы две РМ А, B ( n ×m) в неупорядоченном
  РСФ. На выходе требуется получить C =А +B в том же формате.
    Для решения этой задачи нам потребуется вспомогательный ЦМП Y и
РВН X . Размерность этих массивов равна числу столбцов A и B :
dim Y =dim X =m . В основе алгоритма лежит идея поочередного сложения
строк матриц A и B как РВ с помощью РВН.
                           Алгоритм
1. Символический этап (формирование JC, IC )
   10 . i =1 (номер строки).
   2 0 . С помощью IA, JA и IB, JB определяем списки, соответствующие
   i -м строчкам матриц A и B и сливаем эти списки методом ПП с
   помощью ЦМП Y . Список, полученный в результате слияния, помещаем в
   1-ю свободную позицию массива JC .
   30 . Полагаем i =i +1 и идем на 2 0 . Повторяем действия до тех пор, пока
   i ≤n . В результате получаем JC .
   4 0 . Для получения IC достаточно на каждом этапе запоминать первую
   свободную позицию JC .
2. Численный этап (последовательное сложение строк А, B с помощью
      РВН)
      10 . i =1 .
   2 0 . С помощью JC, IC определяем список, полученный в результате
   слияния списков столбцовых индексов i -й строки массивов JA и JB .
   30 . С помощью этого списка и РВН X складываем i -е строки матриц A
   и B , как РВ. Результат сложения помещаем в текущие свободные
   позиции вектора CN в соответствии с порядком столбцов из JC .
   4 0 . i =i +1 и идем на 2 0 . Повторяем действия до тех пор, пока i ≤n . В
   результате получим CN .
  Замечание. После каждого сложения строк РВН X должен быть приведен
  в нулевое состояние.
  Задача 20. Даны две матрицы А, B . Найти C =А +B .
  � AN : 2 −1 4 3 3 7 −2 −1 1 1
   �
     � JA : 3 5 1 3 4 5 1 6 2 4 ;
  �     IA : 1      3   7 9
  �

Страницы