Методы решения систем с разреженными матрицами. Теория графов. Глушакова Т.Н - 6 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

6
§2. Симметричная перестановка (СП)
Одна из важных задач гауссова исключения – задача об уменьшении ширины
ленты СПОМ.
Так как при гауссовом исключении ведущий элемент может стоять на
главной диагонали, то ширина ленты не увеличится, а попытаться уменьшить
её можно, что позволит сэкономить память и время.
Основным инструментом уменьшения ширины ленты будет СП.
Опр.
Перестановка называется симметричной, если вместе с перестановкой
i-той и j-той строки переставляются также i-тый и j-тый столбцы.
При СП сохраняются симметрия и положительная определённость матрицы,
элементы главной диагонали остаются там же.
Осуществляя для матрицы А СП с помощью матрицы Р (Р
T
P=I, где I –
единичная матрица), мы от системы Аx = f переходим к системе РАР
Т
Рx = Рf.
Если В = РАР
Т
, где Р – матрица перестановки, а G
A
и G
B
– графы, связанные с
матрицами А и В соответственно, то G
A
и G
B
идентичны с точностью до
нумерации вершин, т. е. при СП граф симметричной матрицы не меняется, а
меняется лишь нумерация его вершин.
Матрица P
ij
, осуществляющая перестановку i-той и j-той строк при
умножении на неё слева, и i-го и j-го столбца при умножении на неё справа,
имеет следующий вид:
§3. Разбиение на уровни смежности (УС)
Опр.
Говорят, что граф G(V,E) разбит на УС, если для множества вершин V
справедливо следующее представление:
Υ
m
i
i
LV
0
=
==
=
=
==
= (где L
i
– УС),
причём Adj (L
0
) ⊆ L
1
, Adj (L
m
) ⊆ L
m-1
, Adj (L
i
) ⊆ L
i-1
∪ L
i+1
(i=1,..,m–1).
Опр.
Число m называется длиной структуры УС (СУС) L
0,
L
1,
..., L
m
, а ши-
рина СУС определяется как максимальное количество вершин, образующих
=
1...0...0...00
..............
0...0...1...00
..............
0...1...0...00
..............
0...0...0...10
0...0...0...01
j
i
P
ij
                                  6


                  §2. Симметричная перестановка (СП)
  Одна из важных задач гауссова исключения – задача об уменьшении ширины
ленты СПОМ.
  Так как при гауссовом исключении ведущий элемент может стоять на
главной диагонали, то ширина ленты не увеличится, а попытаться уменьшить
её можно, что позволит сэкономить память и время.
  Основным инструментом уменьшения ширины ленты будет СП.
Опр. Перестановка называется симметричной, если вместе с перестановкой
 i-той и j-той строки переставляются также i-тый и j-тый столбцы.
  При СП сохраняются симметрия и положительная определённость матрицы,
элементы главной диагонали остаются там же.
  Осуществляя для матрицы А СП с помощью матрицы Р (РTP=I, где I –
единичная матрица), мы от системы Аx = f переходим к системе РАРТ Рx = Рf.
Если В = РАРТ , где Р – матрица перестановки, а GA и GB – графы, связанные с
матрицами А и В соответственно, то GA и GB идентичны с точностью до
нумерации вершин, т. е. при СП граф симметричной матрицы не меняется, а
меняется лишь нумерация его вершин.
   Матрица Pij, осуществляющая перестановку i-той и j-той строк при
умножении на неё слева, и i-го и j-го столбца при умножении на неё справа,
имеет следующий вид:
                          1   0 . . . 0 . . . 0 . . . 0
                                                       
                          0   1 . . . 0 . . . 0 . . . 0
                          .   . . . . . . . . . . . . .
                                                       
                        i 0   0 . . . 0 . . . 1 . . . 0
                   Pij = 
                          .   . . . . . . . . . . . . .
                                                        
                        j 0   0 . . . 1 . . . 0 . . . 0
                                                       
                          .   . . . . . . . . . . . . .
                          0   0 . . . 0 . . . 0 . . . 1
                                                       

                  §3. Разбиение на уровни смежности (УС)
Опр. Говорят, что граф G(V,E) разбит на УС, если для множества вершин V
                                                   m
  справедливо следующее представление:         V = Υ Li   (где    Li   – УС),
                                                   i =0
  причём   Adj (L0) ⊆ L1, Adj (Lm) ⊆ Lm-1, Adj (Li) ⊆ Li-1 ∪ Li+1 (i=1,..,m–1).

Опр. Число m называется длиной структуры УС (СУС) L0, L1,..., Lm , а ши-
 рина СУС определяется как максимальное количество вершин, образующих

Страницы