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

UptoLike

ВУЗ: 

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

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

Рубрика: 

4.3 Окаймление неизвестной части разложения
Для j = 1 до n
Для k = 1 до j −1
Для i = j до n
a
ji
= a
ji
− l
jk
a
ki
Для k = 1 до j −1
Для i = j + 1 до n
a
ij
= a
ij
− l
ik
a
kj
Для s = j + 1 до n
l
sj
= a
sj
/a
jj
Для j = 1 до n
Для i = j + 1 до n
Для k = 1 до j − 1
a
ij
= a
ij
− l
ik
a
kj
Для i = j до n
Для k = 1 до j − 1
a
ji
= a
ji
− l
jk
a
ki
Для s = j + 1 до n
l
sj
= a
sj
/a
jj
Рис. 4.4. Алгоритмы Донгарры–Айзенштата окаймления неизвестной части
¯
LU-
разложения: алгоритм линейных комбинаций (слева) и алгоритм скалярных про-
изведений (справа)
Первый цикл по k,i на рис. 4.4 (слева) производит последователь-
ные модификации j-й с троки матрицы A, которая по окончании цикла
k превращается в j-ю строку матрицы U. Эти модификации можно рас-
сматривать как вычитание векторно-матричного произведения l
T
j1
U
13
из
a
T
j3
во второй формуле u
T
j3
= a
T
j3
− l
T
j1
U
13
в (4.4) c помощ ь ю линей-
ных комбинаций строк U. В случае j = i результатом модификации
будет пе рвая величина u
jj
в (4.4). Во второй паре циклов по k и i
выполняются модификации j-го столбца матрицы A по формуле l
3j
=
= (a
3j
− L
31
u
1j
), т. е. по второй формуле (4.4) с точностью до деления
на u
jj
c вычислением матрично-векторного произведения L
31
u
1j
в (4.4) по-
средством линейных операций столбцов матрицы L. Обратите внимание, —
в отличие от алгоритма отложенных модификаций на рис. 3.6, те пе рь длины
векторов, участвующих в линейных комбинациях, одинаковы. Второй опе-
ратор цикла с индексом k можно удалить, причем программа снова будет
верна; мы вставили этот о пе рато р, чтобы подчеркнуть наличие линейных
комбинаций. Отметим еще, что в первом цикле по k,i происходит обращение
к строкам матрицы A, а во втором цикле по k,i — к ее столбцам. Следова-
тельно, эта форма неэффективна для векторных компьютеров, требующих
размещения элементов вектора в смежных ячейка х памяти.
Алгоритм на рис. 4.4 (справа) использует скалярные произведения. На
j-м шаге первый цикл по i, k вычисляет, с точностью до ф инального деле-
ния, j-й столбец матрицы L; с этой целью j- й столбе ц в A модифицируется
посредством скалярных произведений строк L и j-го столбца U. Во втором
77

Страницы