О программной реализации методов прогонки и наименьших квадратов

Система линейных алгебраических уравнений (СЛАУ) — система уравнений, каждое уравнение в которой является линейным — алгебраическим уравнением первой степени.

В классическом варианте коэффициенты при переменных, свободные члены и неизвестные считаются вещественными числами, но все методы и результаты сохраняются (либо естественным образом обобщаются) на случай любых полей, например, комплексных чисел.

Решение СЛАУ — одна из классических задач линейной алгебры, во многом определившая её объекты и методы. В настоящее время решение СЛАУ является одной из основных задач вычислительной линейной алгебры. Большая часть данных методов различна (в особенности нелинейных) и включает в себя решение СЛАУ как простейшего шага используемого алгоритма.

В данной работе будет рассмотрен и проведен сравнительный анализ методов SVD и прогонки с точки зрения точности и быстродействия.

Метод сингулярного разложения (иначе метод SVD) является удобным методом при работе с матрицами. Он показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные. В свою очередь метод прогонки (иначе алгоритм Томаса) используется для решения СЛАУ трехдиагональных матриц. Данный алгоритм предполагает последовательное исключение неизвестных.

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

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

Вначале работы с программным обеспечением открывается форма, требующая ввода размерности матрицы (рисунок 2).

Рисунок 2 – Форма, требующая ввода размерности матрицы

После ввода размерности матрицы необходимо последовательно ввести элементы заданной матрицы (рисунок 3).

Рисунок 3 – Форма, требующая ввода элементов матрицы

После ввода в форму элементов матрицы программа производит вычисление двумя методами. На рисунке 4 предоставлено решение матрицы методом SVD.

Рисунок 4 – Решение методом SVD

На рисунке 5 показано решение матрицы методом прогонки.

Рисунок 5 – Решение методом прогонки

Время расчета методом прогонки составляет 1,7 секунды, методом SVD – 1,5.

Анализируя результаты, полученные с помощью системы, можно сделать ряд следующих выводов:

Метод SVD (так же называемый метод наименьших квадратов) дает точное решение системы линейных алгебраических уравнений, однако требует перед своим применением ряда дополнительных преобразований – проверку на то, что количество строк в матрице больше количество столбцов.

Количество строк сильно зависит от матрицы исходной системы уравнений вида Ax=b. Чем больше количество строк в уравнении, тем больше времени потребуется программному обеспечению, чтобы найти корни данной системы.

На количество шагов во многом влияет начальное приближение. Чем оно ближе к точному решению, тем меньше потребуется шагов для сходимости метода.

В итоге можно сделать общий вывод: метод SVD (наименьших квадратов) является наиболее подходящим при решении системы линейных алгебраических уравнений, он в свою очередь является менее объемным и требует меньше времени для нахождения корней, чем метод прогонки.