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

UptoLike

ВУЗ: 

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

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

Рубрика: 

4 Алгоритмы окаймления в LU-разложении
трех блоков, которые окаймляют эту извест ную часть разложения, следуя
правилу перемножения блок-матриц, а именно, для a
T
j1
, a
1j
и a
jj
:
l
T
j1
U
11
= a
T
j1
,
¯
L
11
u
1j
= a
1j
, l
T
j1
u
1j
+ u
jj
= a
jj
. (4.2)
Из первого уравнения (4.2), переписанного в виде U
T
11
l
j1
= a
j1
, находим
l
j1
, из второго находим u
1j
и зате м из третьего находим u
jj
= a
jj
− l
T
j1
u
1j
.
При этом первое и второе уравнения описываются следующими нижнетре-
угольными системами
U
T
11
l
j1
= a
j1
,
¯
L
11
u
1j
= a
1j
. (4.3)
Существуют два естественных варианта реализации окаймления извест-
ной части LU-разложения.
В первом варианте треугольные системы (4.3) решаются с помощью
столбцового алгоритма, в о втором — с помощью алго ритма скалярных про-
изведений. Псевдокоды этих двух вариантов приведены на рис. 4.1.
Для j = 2 до n
Для k = 1 до j − 2
Для i = k+1 до j−1
a
ij
= a
ij
− l
ik
a
kj
Для k = 1 до j − 1
l
jk
= a
jk
/a
kk
Для i = k + 1 до j
a
ji
= a
ji
− l
jk
a
ki
Для j = 2 до n
Для i = 2 до j −1
Для k = 1 до i − 1
a
ij
= a
ij
− l
ik
a
kj
Для i = 2 до j
l
j,i−1
= a
j,i−1
/a
i−1,i−1
Для k = 1 до i − 1
a
ji
= a
ji
− l
jk
a
ki
Рис. 4.1. Алгоритмы окаймления известной части
¯
LU-ра зложения: столбцовый (сле-
ва) и алгоритм скалярных произведений (справа)
В первом цикле по i на рис. 4.1 (слев а ) выполняется модификация j-го
столбца матрицы A и тем с а м ым вычисляется j-й столбец матрицы U. Во
втором цикле по i модифицируется j-я строка матрицы A и вычисляется j-я
строка матрицы
¯
L. Заметим, что при i = j во втором цикле по i пересчи-
тывается элемент (j, j) матрицы A; в результате, согласно (4.2), получается
элемент u
jj
.
Во второй форме алгоритма окаймления на рис. 4.1 (справа) первый цикл
по i,k вычисляет j-й столбец матрицы U, для чего из элементов a
ij
вычи-
таются скалярные произведения строк с 2-й по (j − 1)-ю матрицы
¯
L с j-м
столбцом U. Это эквивалентно решению системы
¯
L
11
u
1j
= a
1j
. Во втором
74

Страницы