Методы программирования. Громов Ю.Ю - 32 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

32
−−
→
......
.........
......
......
1
...
......
......
.........
......
.........
......
a
bc
d
a
c
a
b
a
dc
ba
(29)
Так, осевой шаг применительно к матрице (28) с осевым элементом
10 приводит к следующей матрице:
−−
5003
0000
0201.0
010005
.
Отметим два случая в реализации осевого шага:
1) если в (29) b ≠ 0, c ≠ 0 и d = 0, то в представлении разреженной
матрицы нет узла для образующегося ненулевого элемента и поэтому
необходимо включить новый узел;
2) если b ≠ 0, c ≠ 0, d ≠ 0 и
a
bc
d −
= 0, то необходимо исключить
имеющийся узел.
Алгоритм S. (Осевой шаг в разреженной матрице.)
Для эффективного выполнения операций включения и исключения
узлов вводится таблица указателей PTR[j], по одному указателю на каж-
дый столбец матрицы. Благодаря этим переменным обеспечивается воз-
можность изменения связей узлов как в горизонтальном, так и в верти-
кальном измерениях. Алгоритм обрабатывает строки матрицы последо-
вательно снизу вверх, а переменная PIVOT указывает на осевой элемент.
S1. [Начальная установка.] I0 ← ROW(PIVOT), J0 ← COL(PIVOT),
ALPHA ← 1.0/VAL(PIVOT), VAL(PIVOT) ← 1.0, P0 ← LOC(BASEROW[I0]),
Q0 ← LOC(BASECOL[J0]).
S2. [Обработка осевой строки.] P0 ← LEFT(P0), J ← COL(P0). Если
J < 0, то перейти к шагу S3 (осевая строка пройдена до конца); в против-
ном случае PTR[J] ← LOC(BASECOL[J]), VAL(P0) ← ALPHA · VAL(P0) и
повторить шаг S2.
S3. [Поиск новой строки.] Q0 ← UP(Q0), I ← ROW(Q0). Если I < 0,
то конец алгоритма. Если I = I0, то повторить шаг S3; в противном случае
P ← LOC(BASEROW[I]), P1 ← LEFT(P).
n“"=
“2!%*=
kK= !
3
=
“2!%*=
Осевой
столбец
kK%L
!3%L
“2%K
n“"%L
=
n“"%L
“2%K
kK%L
!3%L
“2%K

Страницы