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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

19
Уравнение (18) выражает тот факт, что в качестве значения l
ij
принимается результат выполнения последовательности операций типа (11).
Для j ≤ i определим
.
1
1
)(
∑
−
=
=
j
k
k
ijij
ee
(19)
Если элемент l
ij
ненулевой , то в силу того, что u
jj
= 1 ≠ 0 и
1
)(
=
j
ij
n
в (14),
сумма в (19) содержит n
ij
– 1 членов. Если же элемент l
ij
равен нулю, то в
рассматриваемой позиции заполнения не происходит , так что n
ij
= 0 и e
ij
= 0.
Наконец, подставляя (17) в (16) и (19) в (18), можно записать
LU=A+E. (20)
Рассмотрим невязку
r = Ax – b
для решения x системы (1), вычисленного с использованием арифметики с
плавающей запятой . Из уравнений (20), (*) и (**) получаем
r = - Ex + Lδω + δ b.
Взяв 1-норму или 4-норму, имеем оценку
||r|| ≤ ||E|| ||x|| + ||L|| ||δω|| + ||δ b||.
Положим
)(
max
k
ikMi
ωω =
, так что
.1;1;
)(
nkni
Mi
k
i
≤≤≤≤≤ ωω
В частности, для k = i получаем
i
i
i
x=
)(
ω , так что | x
i
| ≤ ω
Mi
. Пусть также ω
M
равно наибольшему из чисел ω
M i
, т.е.
.;,...,2,1;
)(
ikni
M
k
i
≥=≤ ωω (20')
Из (20') получаем следующие границы для норм вектора x:
.
,
1
M
M
x
nx
ω
ω
≤
≤
∞
Можно дать другую интерпретацию вектора невязки r. Пусть
x
~
– точное
решение системы (1), тогда
b
x
A
=
~
и
(
)
.
~
xxAr
−
=
                                                   19
Уравнение (18) выражает тот факт, что     в   качестве   значения    lij
принимается результат выполнения последовательности операций типа (11).
Для j ≤ i определим
                                        j −1
                                 eij =∑ eij( k ) .                       (19)
                                        k =1

Если элемент lij ненулевой, то в силу того, что ujj = 1 ≠ 0 и nij( j ) =1 в (14),
сумма в (19) содержит nij – 1 членов. Если же элемент lij равен нулю, то в
рассматриваемой позиции заполнения не происходит, так что nij = 0 и eij = 0.
Наконец, подставляя (17) в (16) и (19) в (18), можно записать

                                LU=A+E.                                  (20)
   Рассмотрим невязку
                               r = Ax – b
для решения x системы (1), вычисленного с использованием арифметики с
плавающей запятой. Из уравнений (20), (*) и (**) получаем

                                r = - Ex + Lδω + δb.

Взяв 1-норму или 4-норму, имеем оценку

                         ||r|| ≤ ||E|| ||x|| + ||L|| ||δω|| + ||δb||.

Положим ωMi =max k ωi( k ) , так что

                            ωi( k ) ≤ωMi ;1 ≤i ≤n;1 ≤k ≤n.


В частности, для k = i получаем ωi(i ) =xi , так что |xi| ≤ ωMi. Пусть также ωM
равно наибольшему из чисел ωMi, т.е.

                    ωi( k ) ≤ωM ; i =1,2,..., n; k ≥i.                  (20')

Из (20') получаем следующие границы для норм вектора x:

                                         x 1 ≤nωM ,
                                         x     ∞
                                                   ≤ωM .

   Можно дать другую интерпретацию вектора невязки r. Пусть ~x – точное
решение системы (1), тогда A~x =b и

                                       r = A(x −~
                                                x ).

Страницы