билет 26
2). Решение систем линейных алгебраических уравнений с разреженными матрицами, метод диагональной модификации.
Ax=Y;
* *
* - матрица заполнена коэффициентами меньше чем на 10%,все остальное 0
* *
матрицу будем считать разреженной, если этот факт даст повышение эффективности вычислений
если k<<n,то тогда можно не выполнять операции, результат которых заранее известен
метод Гаусса:
в процессе работы в матрице появляются новые ненулевые элементы
Отсюда надо выбирать такой ход работы, чтобы появление новых ненулевых элементов было min.
(n!)2 – количество перестановок, где n-разряд
возникает противоречие, с одной стороны нужно, чтобы ведущие элементы были наибольшие по модулю для получения решения с заданной точностью, с другой стороны ведущими надо выбирать такие элементы, которые порождают меньше всего новых элементов.
если матрица симметрична и положительно определена, то нужно заниматься минимализацией количества новых элементов.
для общего вида выбор компромиссных вариантов основан на эвристических приемах, не имеющих строгого теоретического обоснования.
количество ненулевых элементов при работе по методу Гаусса увеличивается примерно в 2-9 раз.
критерии упорядочивания:
-
ранжируются все строки по количеству ненулевых элементов - чем меньше ненулевых элементов, тем раньше обрабатывается строка
-
проводится пробное разложение- берется строка с наименьшим количеством элементов, делаем один шаг разложения
на завершающих этапах используются нормализованные процессы, импользуя методы работы с плотными матрицами, методом диагональной модификации:
.
а
δ x = Y (A+ ΔA) (x +Δx) = Y; (1)
с B U
.
Ax + A Δx + ΔA x + ΔA Δx = Y; (сокращается)
(A+ ΔA) Δx = -ΔAx;
i
1
ΔA= q i = i 1 *q
(A + ΔA) Δx = - ei xiqi
B
V= Δx xi-1 qi-1
BV= -ei; (2)
Δx= V xiqi U= x+ Δx;
Ui= xi + δixiq
xi= Ui/(1+δiq)
x= U + Vq Ui/(1+δiq) – истинное решение