XV Международная студенческая научная конференция Студенческий научный форум - 2023

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

Аналитический метод решения систем линейных алгебраических уравнений (СЛАУ) в научной сфере неуместен — размеры систем и соответствующие расчеты оказываются слишком громоздкими, что повышает риск ошибки в результате человеческого фактора[1]. Поэтому при решении массивных систем используются численные методы, основанные на компьютерных вычислениях. Постоянно ведутся исследования, разрабатываются новые методы, однако существует ряд классических методов, применяемых при решении такого типа задач, — именно их мы и рассмотрим в данной статье.

Теоретические сведения

Классификация методов решения СЛАУ

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

К прямым методам относятся:

Метод Крамера (формула Крамера);

Метод Гаусса;

Метод Гаусса-Жордана;

Метод прогонки.

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

К итерационным методам относятся[2]:

Метод Якоби(метод простых итераций);

Метод Зейделя;

Метод релаксации.

Прямые методы

Метод Крамера

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

Составление матрицы системы и матрицы свободных членов.

Нахождение определителя основной матрицы.

Замена i-ого столбца матрицы на столбец свободных членов и подсчет определителя новой матрицы. Таким образом, требуется найти определителей.

По формуле Крамера найти значения переменных.

Несмотря на удобство, алгоритм не применим для больших систем (причем как для аналитического решения, так и посредством компьютерных вычислений), так как при увеличении числа уравнений и переменных число операций растет со скоростью факториала. Общее количество операций можно вычислить по формуле: . Например, при решении СЛАУ, состоящей из 5 уравнений ( ) число операций достигнет 3605, поэтому метод абсолютно не применим для практических целей — в научной сфере применяются системы, состоящие из сотен и тысяч СЛАУ[3].

Кроме того, метод не подходит для решения СЛАУ, в которых число уравнений и число переменных различно.

Метод Гаусса

Численный метод Гаусса полностью основан на аналитическом способе решения систем линейных уравнений при помощи одноименного метода. Другое его название — метод последовательного исключения переменных — полностью отражает его суть.

Идея метода заключается в том, чтобы путём эквивалентных (элементарных) преобразований привести расширенную матрицу системы к виду верхней треугольной матрицы (прямой ход метода Гаусса), после чего выполняется обратная подстановка (обратный ход метода Гаусса).

Алгоритм численного нахождения решения системы линейных уравнений методом Гаусса сводится к двум шагам:

Последовательное исключение переменных. На каждом i-ом шаге к каждому уравнению, следующему за i-ым, прибавляется i-ое уравнение, умноженное на , где i — номер текущего уравнения, k — номер переменной. Этот элемент называется ведущим. При этом исходное i-ое уравнение не изменяется. Этот этап называется прямым ходом метода Гаусса.

Обратная подстановка полученных значений — обратный ход метода Гаусса.

Метод Гаусса является универсальным и подходит для решения СЛАУ любого типа (даже когда число уравнений не совпадает с числом переменных), а число операций растет значительно медленнее, чем при использовании метода Крамера — число операций , где n — число уравнений[4].

Однако у него имеется недостаток, который проявляется при программировании алгоритма, — при вычислении ведущего элемента может возникнуть деление на 0. В этом случае в столбце, соответствующем номеру шага, ищется элемент с максимальным по модулю коэффициентом, и уравнение, содержащее этот коэффициент, переставляется местами с i-ым уравнением. Эта модификация называется методом Гаусса с частичным выбором ведущего элемента. Из него же следует модификация метода, где на каждом шаге производится выбор ведущего элемента.

Метод Гаусса во всех его модификациях неудобен при решении таких систем, матрица которых представляет собой трёхдиагональную матрицу, — для них более применим метод прогонки.

Метод Гаусса-Жордана

Второе название метода Гаусса-Жордана — метод полного исключения переменных. Является ещё одной модификацией метода Гаусса. Суть его заключается в приведении матрицы к единичному виду. Метод характеризуется определенной последовательностью вычислений:

Первую единицу главной диагонали получим при делении первого уравнения на коэффициент при .

Остальные уравнения преобразуются по следующему принципу:

Обнуление коэффициентов первого столбца методом Гаусса, за исключением коэффициента при .

В результате предыдущего шага коэффициенты при станут равны нулю. Далее делим второе уравнение на коэффициент при — таким образом мы получим вторую единицу на главной диагонали.

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

Предварительно можно организовать диагональное преобладание, то есть переставить уравнения таким образом, чтобы на главной диагонали стояли наибольшие по модулю элементы. Тогда погрешность округления уменьшается[5].

Метод прогонки

Метод прогонки применяется для решения классических СЛАУ и тех, которые образуют трехдиагональную матрицу. Метод Гаусса при решении такой системы сработает, однако возникнет много лишних вычислений и временных затрат, так как трехдиагональная матрица содержит много нулей[6].

Суть метода сводится к последовательному выражению каждой переменной через другие — из первого уравнения выражается переменная , которая затем подставляется во второе. Затем из второго уравнения выражается и подставляется в 3 уравнение. Таким образом, из каждого уравнения выражается (где i — номер уравнения), а затем подставляется в уравнения.

Итерационные методы

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

Три основных итерационных метода — метод Якоби (метод простых итераций), метод Зейделя и метод релаксации.

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

Практическая часть

Существует много программ для решения СЛАУ, такие как Matlab, Excel и другие, однако наиболее рациональным способом является программирование численных методов.

Рис. 1. Методы Крамера, Гаусса и Гаусса-Жордана

Рис. 2. Метод прогонки

Рис. 3. Методы Якоби, Зейделя и релаксации

Сравнение прямых методов

Для демонстрации работы прямых методов были взяты системы уравнений, состоящие из 10 (для метода Крамера) и 50 (для остальных методов) уравнений. Было подсчитано время работы, а также количество арифметических действий. Результат приведен в таблице 1.

Таблица 1

Сравнение прямых методов

	Метод Крамера	Метод Гаусса	Метод Гаусса-Жордана	Метод прогонки
Количество уравнений в системе	10	50	50	50
Количество операций	399168010	83333	125000	9604
Затраченное время (мс)	2488	85	104	48

Как видно из приведенной таблицы, количество операций по методу Крамера значительно возрастает при вычислении решений системы уравнений, состоящей всего из 10 уравнений, в то время как методы Гаусса, Гаусса-Жордана и прогонки даже при 50 уравнениях выполняют в 3500 раз меньше операций и затрачивают значительно меньше времени.

Сравнение итерационных методов

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

Результаты вычислений приведены в таблице 2.

Таблица 2

Сравнение итерационных методов

На основе приведенной таблицы можно сделать вывод о том, что итерационные методы позволяют получить точное или приблизительное решение за приемлемое время с минимумом операций. Особенности работы данных методов отображены на следующих графиках (для метода релаксации параметр релаксации ω был взят равным 1,5):

На основе приведенной таблицы и графиков можно сделать вывод о том, что параметр ω был выбран неудачно, чем обусловлена низкая скорость сходимости метода релаксации. Сходимость же остальных методов зависит только от системы уравнений.

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

Заключение

В статье были рассмотрены различные методы, такие как метод Крамера, метод Гаусса, метод Гаусса-Жордана, метод прогонки и итерационные методы. Каждый из них имеет свои преимущества и недостатки, поэтому выбор метода зависит от конкретных условий и задач. Некоторые методы могут быть быстрыми и эффективными в одних случаях, но медленными и ненадежными в других.

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

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

Численные методы могут быть усовершенствованы с помощью использования более совершенных алгоритмов или применения более продвинутых технологий вычислений.

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

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

Список литературы

Трухан А.А., Ковтуненко В.Г. Линейная алгебра и линейное программирование: Учебное пособие. – СПб.: Лань, 2018. – 316 с.

Горбаченко В.И. Вычислительная линейная алгебра с примерами на MATLAB // Горбаченко В.И. – СПб.: БХВ-Петербург, 2011. – 320 с.

Терентьев В.И. Методы численного моделирования // В.И. Терентьев. – СПб.: Лань, 2005. – 512 с.

Шевцов Г.С., Крюкова О.Г., Мызникова Б.И. Численные методы линейной алгебры. – СПб.: Лань, 2011. – 496 с.

Канатников А.Н., Крищенко А.Н. Линейная алгебра. – Учебник. – М.: МГТУ им. Н. Э. Баумана, 2015. – 336 с.

Пименов В.Г., Ложников А.Б. Численные методы в 2 частях. Часть 2. Учебное пособие для вузов. – М.: Юрайт, 2017. – 108 с.

Код для цитирования: Скопировать