Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 11 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

11
треугольную систему порядка (n –1) с угловой главной подматрицей
матрицы L в качестве матрицы коэффициентов. Теперь можно вычислить ω
2
,
и приведенные рассуждения могут повторяться рекуррентно и далее, пока не
будет завершено вычисление всех компонент вектора ω. Если обозначить
через n
L
число внедиагональных ненулевых элементов матрицы L , то можно
убедиться в том, что прямая подстановка требует n операций деления , n
L
операций умножения и n
L
операций сложения .
Прямая подстановка может рассматриваться как алгоритм, выполняемый
в n шагов, в результате чего последовательно вычисляются векторы b
(1)
≡
b,
b
(2)
, … , b
(n)
; при этом первые k компонент векторов b
(k+1)
и b
(k)
совпадают.
На k-м шаге, k = 1, 2, … , n, выполняются следующие вычисления :
(
)
),1(/
)(
εω +=
kk
k
kk
lb
,,,1;
)()()1(
nkiflbb
k
ikik
k
i
k
i
Κ+=+−=
+
ω
где ε и
)( k
i
f – соответствующие вычислительные ошибки. Никаких
предположений относительно разреженности векторов b и ω мы не делаем .
Операции, выполненные над элементом b
i
, приводят к соотношению
,)1)(/)((
)1(
11,
)1(
11 iii
i
iiiiiii
lflflb ωεωω =++−−+−
−
−−
Κ
которое можно переписать в виде
,
1
1
1
1
)(
ε
ε
ωω
+
−=+
∑∑
=
−
=
iii
i
k
kik
i
k
k
ii
llfb
где при i = 1 суммирование в левой части должно быть опущено. Определим
вектор ошибок δ b с компонентами
.
1
,1;
1
1111
1
1
)(
ε
ε
ωδ
ε
ε
ωδ
+
=
>
+
+=
∑
−
=
lb
ilfb
iii
i
k
k
ii
Тогда вычисленный результат ω удовлетворяет точному соотношению
Lω = b + δ b. (*)
Если известен вектор ω , то систему (4) можно решить при помощи
обратной подстановки. Так как мы предполагаем , что матрица U имеет
единичную диагональ, то последнее уравнение (4) имеет вид x
n
= ω
n
, так что x
n
известно. Вычитая произведение последнего столбца матрицы U на ω
n
из
вектора ω, мы приходим к треугольной системе порядка (n – 1) с ведущей 
                                                                11
треугольную систему порядка (n –1) с угловой      главной       подматрицей
матрицы L в качестве матрицы коэффициентов. Теперь можно вычислить ω2,
и приведенные рассуждения могут повторяться рекуррентно и далее, пока не
будет завершено вычисление всех компонент вектора ω. Если обозначить
через nL число внедиагональных ненулевых элементов матрицы L, то можно
убедиться в том, что прямая подстановка требует n операций деления, nL
операций умножения и nL операций сложения.
     Прямая подстановка может рассматриваться как алгоритм, выполняемый
в n шагов, в результате чего последовательно вычисляются векторы b(1) ≡ b,
b(2), … , b(n); при этом первые k компонент векторов b(k+1) и b(k) совпадают.
На k-м шаге, k = 1, 2, … , n, выполняются следующие вычисления:

                                                        (             )
                                              ωk = bk( k ) / l kk (1 +ε),
                            ( k +1)
                          bi          =b     i
                                              (k )
                                                     −lik ωk + f i ; i =k +1,Κ , n,
                                                                     (k )




где ε и f i (k ) – соответствующие вычислительные ошибки. Никаких
предположений относительно разреженности векторов b и ω мы не делаем.
Операции, выполненные над элементом bi, приводят к соотношению

              ((bi −li1ω1 + f i (1) −Κ −li ,i −1ωi −1 + f i (i −1) ) / lii )(1 +ε) =ωi ,

которое можно переписать в виде
                                      i −1                  i
                                                                              ε
                              bi +∑ f i ( k ) =∑ lik ωk −liiωi                   ,
                                      k =1               k =1               1 +ε

где при i = 1 суммирование в левой части должно быть опущено. Определим
вектор ошибок δb с компонентами

                                              i −1
                                                                       ε
                                δbi =∑ f i ( k ) +liiωi                   ; i >1,
                                              k =1                   1 +ε
                                                         ε
                                δb1 =l11ω1                  .
                                                       1 +ε

   Тогда вычисленный результат ω удовлетворяет точному соотношению

                                      Lω = b + δb.                                         (*)

   Если известен вектор ω, то систему (4) можно решить при помощи
обратной подстановки. Так как мы предполагаем, что матрица U имеет
единичную диагональ, то последнее уравнение (4) имеет вид xn=ωn, так что xn
известно. Вычитая произведение последнего столбца матрицы U на ωn из
вектора ω, мы приходим к треугольной системе порядка (n – 1) с ведущей

Страницы