Algorithm of solving a sparse system of linear algebraic equations of large dimension by conjugate gradient method

Abstract

The algorithm of solving sparse systems of linear algebraic equations of large dimension of a special type by using of the conjugate gradient method is described. The results of a computational experiment for different values of the input data are presented.

Full Text

При решении задач идентификации параметров динамических систем по экспериментальным данным [1–3] возникает необходимость решения разреженных систем линейных алгебраических уравнений большой размерности специального вида.

Рассмотрим систему линейных алгебраических уравнений следующего вида:

My = d,                                                                                                           (1)

где

-нулевые матрицы соответствующих размеров,

I_2N — единичная (2N×2N) -матрица, O₄— нулевая (4×4) -матрица, O_2N×4 — нулевая (2N×(2N+4)) -матрица,

T = T₁, T₂,..., T_N , T_𝜃],

T₁ – единичная (2×2) -матрица, – нулевые (2×2) -матрицы, T_𝜃 — нулевая (2×4) -матрица,

Компоненты вектора d вычисляются по формулам

Для приближенного нахождения решения системы (1) использовался метод сопряженных градиентов. Приведем алгоритм метода сопряженных градиентов [4] для системы (1):

1. Выберем начальное приближение y⁽⁰⁾.
2.  
3. Вычислим коэффициент
4. Найдем следующее приближение
5. Вычислим поправку к решению
6. Найдем коэффициент
7. Если то алгоритм завершается.
8. Вычислим вектор, вдоль которого вычисляется поправка
9. 𝑗∶=𝑗+1.

Перейдем к пункту 3.

На основании приведенного алгоритма разработано программное обеспечение на языке C#. Структура программного обеспечения имеет вид

Рис. 1. Структура программного обеспечения.

Опишем модули программного обеспечения.

LargeMatrix – библиотека, содержащая классы разреженной матрицы, плотного вектора и плотной матрицы, а также классов, отвечающих за построение системы уравнений заданного вида.

Tests – модульные тесты, покрывающие библиотеку LargeMatrix, а также метод решения СЛАУ.

SystemResolver – основной проект, содержащий алгоритм решения разреженной системы методом сопряженных градиентов.

WebAPI – API на ASP.NET, позволяющий делать запрос к серверу на получение данных решения.

WebClient – клиентское приложение, получающее и отображающее данные решения в браузере.

Для хранения разреженной матрицы использовался разреженный строчный формат (Compressed sparse row), который предполагает наличие трех одномерных массивов.

• Массив, содержащий все ненулевые элементы матрицы.
• Массив, содержащий номера столбцов для соответствующих элементов.
• Массив индексов элементов, с которых начинается описание строки.

Вычислительный эксперимент проводился при следующих начальных данных:

𝑁=10, 𝜃₁=−1, 𝜃₂=1, 𝜃₃=−0.5, 𝜃₄ = 0.5, ℎ=𝑐𝑜𝑙𝑢𝑚𝑛(100, 150)

Значения  и  приведены в таблице 1.

Таблица 1

Значения x_i,1 и x_i,2

i	1	2	3	4	5	6	7	8	9	10
xi,1	110	190	200	333	355	383	400	415	420	445
xi,2	151	163	175	204	222	244	266	333	355	380

Результаты вычислительного эксперимента при различных значениях погрешности вычисленийи параметра 𝜏 приведены в таблице 2.

Таблица 2

Количество итераций и время вычислений при различных   ε и 𝜏

Погрешность, ε	𝜏 = 0.5	𝜏 = 0.1	𝜏 = 0.05	𝜏 = 0.01
0.1	32 0,003185 сек.	27 0,003003 сек.	25 0,002839 сек.	24 0,003031 сек.
0.01	33 0,003587 сек.	27 0,003042 сек.	25 0,003219 сек.	24 0,003095 сек.
0.001	33 0,004341 сек.	30 0,003109 сек.	30 0,003307 сек.	24 0,003372 сек.

Анализ таблицы 2 показывает, что при уменьшении параметра 𝜏 количество итераций, требуемых для достижения заданной точности ε, уменьшается, и, следовательно, скорость сходимости итерационного метода увеличивается. Вместе с тем, при фиксированном значении параметра 𝜏 и уменьшении погрешности вычислений ε время вычислений и количество итераций увеличивается незначительно.