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

UptoLike

ВУЗ: 

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

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

Рубрика: 

6.5 Разложение Холесского: алгоритмы окаймления
Покажем, как выводятся такие матрично-векторные алгоритмы на при-
мере одного из четырех вариантов разложения Холесского (6.2), а именно,
варианта P = LL
T
. Пользуясь этим справочным материалом, любой студент
сможет самостоятельно построить родственные алгоритмы для других т рех
вариантов разложения. Для этого поделим все матрицы в данном варианте
на блоки, выделяя в каждой матрице j-ю строку и j-й столбец. Тем самым
разложение P = LL
T
будет представлено в блочной форме
j
⇓
P
11
a P
13
j ⇒ a
T
p
jj
b
T
P
31
b P
33
=
j
⇓
L
11
c
T
l
jj
L
31
d L
33
j
⇓
L
T
11
c L
T
31
l
jj
d
T
L
T
33
, (6.3)
где фрагменты j-й строки и j-го столбца обозначены как векторы-столбцы
выделенными символами a, b, c и d, а заглавные буквы обо значают мат-
рицы. Нулевые элементы треугольных матриц не показаны.
Перемножение матриц (6.3), выполняемое поблочно, дает девять соот-
ношений относительно блок-элементов матриц P и L. Пользуясь этим, рас-
смотрим два основных способа разложения матрицы P методом окаймления.
Окаймление известной части разложения. Из указанных девяти
соотношений в о зьмем только те, что окаймляют блок P
11
= L
11
L
T
11
, считая,
что в эт о й части разложение уже сделано, т. е. что блок L
11
уже вычислен.
В силу симметрии P из трех окаймляющих произведений имеем только два:
a = L
11
c и p
jj
= c
T
c + l
2
jj
. (6.4)
Отсюда сначала находим c как решение нижнетреугольной системы урав-
нений L
11
c = a; затем находим l
jj
= (p
jj
− c
T
c)
1/2
.
Окаймление неизвестной части разложения. Из указ а нных соот-
ношений возьмем те, что окаймляют блок P
33
, считая, что до этого блока
разложение уже сделано, т. е. что блоки L
11
, L
31
и c уже найдены. В силу
симметрии P из трех окаймляющих произведений имеем только два:
p
jj
= c
T
c + l
2
jj
и b = L
31
c + dl
jj
. (6.5)
Отсюда сначала находим l
jj
= (p
jj
− c
T
c)
1/2
; затем d = (b − L
31
c)/l
jj
.
Существует два естественных способа реализации окаймления известной
части в LL
T
-разложении.
99

Страницы