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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

12
главной подматрицей матрицы U в качестве матрицы коэффициентов.
Продолжая указанные преобразования рекуррентно, мы получаем решение x .
Обозначив через n
U
число внедиагональных ненулевых элементов матрицы
U , можно показать , что обратная подстановка требует n
U
умножений и n
U
сложений .
Обратную подстановку можно рассматривать как алгоритм, выполняемый
за n шагов, в результате чего последовательно вычисляются векторы ω
(n)
≡ ω ,
ω
(n-1)
, … , ω
(2)
, ω
(1)
; при этом , начиная с k - й и заканчивая n-й, компоненты
векторов ω
(k)
и ω
(k-1)
совпадают. На k-м шаге, k = n, n – 1, … , 1, выполняются
следующие вычисления :
,
)( k
kk
x ω =
,1,...,1;
)()()1(
−=+−=
−
kigxu
k
ikik
k
i
k
i
ωω
где
)( k
i
g – ошибка, возникшая в результате выполнения вычислений с
плавающей запятой . Результат операций , выполненных над элементом ω
i
,
i<n, можно записать в виде
,
)1(
11,
)1(
11,
)(
i
i
iiii
n
inni
n
inini
xgxugxugxu =+−−+−+−
+
++
−
−−
Κω
или
.;
1
)(
nixug
n
ik
kik
n
ik
k
ii
<=+
∑∑
=+=
ω
Таким образом, если определить вектор ошибок δω:
,0
,;
1
)(
=
<=
∑
+=
n
n
ik
k
ii
nig
δω
δω
то можно записать следующее точное соотношение между вычисленными
величинами:
Ux = ω + δω. (**)
Для простоты будем предполагать , что матрица А линейной системы (1)
уже подготовлена для исключения , в том смысле, что диагональные
элементы могут быть непосредственной использованы в качестве главных
элементов в том порядке, в каком они расположены . В общем случае главные
элементы выбираются среди ненулевых элементов матрицы А , причем
элемент, выбранный в качестве главного, переводится на главную диагональ
посредством перестановки строк и столбцов. Выбор главных элементов 
                                                        12
главной подматрицей матрицы U в качестве матрицы коэффициентов.
Продолжая указанные преобразования рекуррентно, мы получаем решение x.
Обозначив через nU число внедиагональных ненулевых элементов матрицы
U, можно показать, что обратная подстановка требует nU умножений и nU
сложений.
    Обратную подстановку можно рассматривать как алгоритм, выполняемый
за n шагов, в результате чего последовательно вычисляются векторы ω(n) ≡ ω,
ω(n-1), … , ω(2), ω(1); при этом, начиная с k-й и заканчивая n-й, компоненты
векторов ω(k) и ω(k-1) совпадают. На k-м шаге, k = n, n – 1, … , 1, выполняются
следующие вычисления:

                                                  xk =ωk(k ) ,
                            ωi( k −1) =ωi( k ) −uik xk +g i( k ) ; i =1,..., k −1,

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

Страницы