Вычислительные методы алгебры и оценивания. Семушин И.В. - 76 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

4 Алгоритмы окаймления в LU-разложении
4.3 Окаймление неизвестной части разложения
Основная работа в алгоритмах ока ймления приходится на решение тре-
угольных систем (4.3). Это матрично-векторные операции, которые можно
реализовать в виде подпрограмм по типу рис. 4.1, добиваясь в них макс и-
мальной для данной машины эффективности. Еще один способ организа-
ции вычислений, кото рый называют алгоритмом Д онгарры–Айзенштата,
имеет то преимущество, что его основной операцией является матрично-
векторное умножение. Математически алгоритм можно описать следующим
образом. Выпишем из равенства (4.1) три других соотнош ения, на этот раз
для a
jj
, a
3j
и a
T
j3
. Отсюда получим
u
jj
= a
jj
− l
T
j1
u
1j
, u
T
j3
= a
T
j3
− l
T
j1
U
13
, l
3j
= (a
3j
− L
31
u
1j
) /u
jj
. (4.4)
Характер доступа к данным при таком вычислении показан на рис. 4.3.
⇐ u
T
j3
U
11
¯
L
11
L
31
U
13
A
33
⇑ l
3j
Рис. 4.3. Доступ к данным в алгоритмах окаймления неизвестной части разложения.
¯
L
11
, U
11
— вычисление закончено, обращений больше нет. L
31
, U
13
— вычисление
закончено, но обращения происходят. A
33
— обращ ений не было. Вычисляются: j-й
столбец l
3j
матрицы
¯
L и j-я строка u
T
j3
матрицы U
Видно, что блоки U
13
и L
31
, необходимые для вычислений (4.4), на каж-
дый такой момент времени уже известны, так же как и все другие величины
в правых частях равенств (4.4), поэтому здесь нет решения уравнений.
Основной операцией в (4.4) является умножение вектора на прямоуго ль-
ную матрицу. Можно реализовать такие умножения посредством скалярных
произведений или линейных комбинаций, что приводит к двум различным
формам алгоритма, показанным на рис. 4.4.
76

Страницы