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

UptoLike

ВУЗ: 

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

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

Рубрика: 

6 Разложения Холесского
В первом варианте треугольная система в (6.4) решается с помощью
строчного алгоритма (аналог алгоритма на рис. 4.1 слева), во втором — с
помощью алгоритма скалярных произведений (аналог алгоритма на рис. 4.1
справа). Псевдокоды этих двух вариантов приведены на рис. 6.1.
l
11
=
√
p
11
Для j = 2 до n
Для k = 1 до j − 1
l
jk
= p
jk
/l
kk
Для i = k + 1 до j
p
ji
= p
ji
− l
jk
l
ik
l
jj
=
√
p
jj
l
11
=
√
p
11
Для j = 2 до n
Для i = 2 до j
l
j,i−1
= p
j,i−1
/l
i−1,i−1
Для k = 1 до i − 1
p
ji
= p
ji
− l
jk
l
ik
l
jj
=
√
p
jj
Рис. 6.1. Алгоритмы окаймления известной части LL
T
-разложения: строчный (сле-
ва); алгоритм скалярных произведений (справа)
Для окаймления неизвестной части в LL
T
-разложении также существуют
два естественных способа реализации выражений (6.5). Здесь основной опе-
рацией явля ется умножение вектора на прямоугольную матрицу.
Можно реализовать такие умножения посредством скалярных произве-
дений или линейных комбинаций, что приводит к двум различным фор-
мам алго ритма, показанным на рис. 6.2, которые аналогичны алгоритмам
Донгарры–Айзенштата на рис. 4.4.
Для j = 1 до n
Для k = 1 до j − 1
p
jj
= p
jj
− l
jk
l
jk
l
jj
=
√
p
jj
Для k = 1 до j − 1
Для i = j + 1 до n
p
ij
= p
ij
− l
ik
l
jk
Для s = j + 1 до n
l
sj
= p
sj
/l
jj
Для j = 1 до n
Для i = j + 1 до n
Для k = 1 до j − 1
p
ij
= p
ij
− l
ik
l
jk
Для k = 1 до j − 1
p
jj
= p
jj
− l
jk
l
jk
l
jj
=
√
p
jj
Для s = j + 1 до n
l
sj
= p
sj
/l
jj
Рис. 6.2. Алгоритмы окаймления неизвестной части LL
T
-разложения: алгоритм ли-
нейных комбинаций (слева); алгоритм скалярных произведений (справа)
Таким образом, выше показано, что алгоритмы окаймления в LU-
разложении (см. разд. 4) легко модифицируются для случая с имметриче-
100

Страницы