УДК 00.004

Реализация метода Гаусса на Python

Файзрахманова Регина Радиевна – магистрант МИРЭА – Российского технологического университета

Кондрахин Владимир Сергеевич – магистрант МИРЭА – Российского технологического университета

Хабибуллин Батырхан Тахирович – магистрант МИРЭА – Российского технологического университета

Аннотация: В данной статье формально рассматриваются методы решения систем линейных алгебраических уравнений, различия между методами и их решением. Более подробно был рассмотрен метод Гаусса при решении систем линейных алгебраических уравнений, принцип его работы. Предложена реализация метода Гаусса для решения систем линейных уравнений на языке программирования Python.

Ключевые слова: метод Гаусса, линейные уравнения, решение СЛАУ.

Методы решения систем линейных уравнений

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

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

Моделирование линейных систем приводит к линейным уравнениям вида Ах = b, где b – входной вектор, а вектор х – ответ системы. Матрица коэффициентов А, отражающая внутренние характеристики системы, не зависит от входных данных. То есть, если мы изменим входные данные, система решаемых линейных уравнений будет иметь другой вектор b, но ту же матрицу коэффициентов А.

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

Это преобразование может быть получено с помощью З фундаментальных операций[5]:

  1. Обмен двумя строками А (определитель знака изменений А).
  2. Умножить строку А на ненулевой скаляр λ (определитель A умножается на тот же скаляр).
  3. Замените строку А строкой, полученной добавлением этой строки другой строкой, умноженной на скаляр (оставляя определитель А неизменным).

Конечно, эти операции не влияют на решения системы, которые остаются прежними, но они могут повлиять на коэффициенты А и его детерминант.

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

Таблица 1.

Метод

Первая форма

Финальная форма

Метод Гаусса

Ax=b

Ux=c

LU-разложение

Ax=b

LUx=b

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

Ax=b

Ix=c

В таблице 1, в колонке окончательной формы уравнений, приведены три стандартные матрицы:

U = image001(1.1)

L = image002(1.2)

I = image003(1.3)

Мотивация для LU-разложения основана на наблюдении, что системы уравнений, включающие в себя треугольные коэффициент-матрицы, легче поддаются решению. Так и есть, ведь весь смысл метода Гаусса заключается в замене коэффициент-матрицы, которая является треугольной.

Причина, по которой прямые методы решения пытаются преобразовать матрицу А в треугольную матрицу, очевидна при записи, например, Ux=c, что означает решение следующей системы линейных уравнений[1]:

image004(1.4)

как вы видите, легко решить, начиная с последнего уравнения.

Метод Гаусса

В математике, Гауссово устранение, также известное как сокращение строк, является алгоритмом для решения систем линейных уравнений. Состоит из последовательности операций, выполняемых на соответствующей матрице коэффициентов. Этот метод также может быть использован для вычисления ранга матрицы, определителя квадратной матрицы и инверсии обратимой матрицы. Метод назван в честь Карла Фридриха Гаусса, хотя некоторые особые случаи метода, хоть и были представлены без доказательств, были известны китайским математикам ещё около 179 года[3]. Для уменьшения строк в матрице используется последовательность элементарных операций строки для изменения матрицы до тех пор, пока нижний левый угол матрицы не будет заполнен нулями, насколько это возможно. Существует три типа элементарных операций с строками:

  • Замена двух строк;
  • Умножение строки на ненулевое число;
  • Добавление кратного числа одной строки в другую (вычитание может быть достигнуто путем умножения одной строки на -1 и добавления результата в другую строку).

Используя эти операции, матрица всегда может быть преобразована в верхнюю треугольную матрицу, и, фактически, матрицу, находящуюся в форме ряда. Когда все ведущие коэффициенты (самый левый ненулевой элемент в каждой строке) равны 1, и каждый столбец, содержащий ведущий коэффициент, имеет нули в другом месте, считается, что матрица находится в виде редуцированного ряда. Эта окончательная форма уникальна; другими словами, она не зависит от последовательности используемых операций ряда. Например, в следующей последовательности операций строки (где две элементарные операции на разных строках выполняются на первом и третьем шагах), третья и четвертая матрицы являются теми, что в форме эшелона строк, а конечная матрица - это уникальная уменьшенная форма эшелона.

Метод Гаусса один из наиболее известных методов решения систем линейных уравнений. Он состоит из двух этапов: этапа ликвидации и этапа замещения[4]. Первая фаза имеет цель, как указано в предыдущей таблице, преобразовать уравнения из формы Ах=b в уравнения немедленного решения Ux=c. Фаза устранения выполняется путем многократного выполнения третьей фундаментальной операции из ранее обсуждавшегося списка. Но так же каждый математик знает следующие свойства метода Гаусса для решения систем линейных уравнений(а так же для вычисления обратной матрицы): метод верен, а так же неустойчив[2]. Но тем не менее пользуется большой популярностью, так как прост в использовании.

Существует два варианта в отношении ручного решения: во-первых, линии преобразуются вычитанием вместо суммы; во-вторых, преобразованные строки не заменяются исходными строками матрицы А, заменяются только элементы, соответствующие верхней треугольной матрице. Фактически, элементы, не принадлежащие U (преобразованная матрица), не имеют значения для расчета решений.

Решение систем линейных уравнений

Реализовывая метод программированием, была написана следующая функция:

import numpy as np

def gauss_method(a,b):

n = len(b)

for k in range(0,n-1):

for i in range(k+1,n):

if a[i,k] != 0.0:

lam = a [i,k]/a[k,k]

a[i,k+1:n] = a[i,k+1:n] - lam*a[k,k+1:n]

b[i] = b[i] - lam*b[k]

for k in range(n-1,-1,-1):

b[k] = (b[k] - np.dot(a[k,k+1:n],b[k+1:n]))/a[k,k]

 return b

На вход функции подаем массив значений матрицы(a) и значения вектора коэффициента(b) для системы линейных уравнений.

Делим каждый коэффициент i- го уравнения на первый ненулевой коэффициент этого уравнения:

for k in range(0,n-1):

for i in range(k+1,n):

Если не null определяем λ:

lam = a [i,k]/a[k,k]

Рассчитываем новую строку матрицы:

 

a[i,k+1:n] = a[i,k+1:n] - lam*a[k,k+1:n]

Обновляем вектор b:

b[i] = b[i] - lam*b[k]

Обратный ход:

for k in range(n-1,-1,-1):

b[k] = (b[k] – np.dot(a[k,k+1:n],b[k+1:n]))/a[k,k]

Введем исходные данные:

a=np.array([[1.0,1.0,1.0],[1.0,-1.0,-1.0],[1.0,-2.0,3.0]])

b=np.array([1.0,1.0,-5.0])

Сохраним значения матрицы и вектора

a_orig = a.copy()

b_orig = b.copy()

x = gauss_method(a,b)

print(a)

print("x =\n", x)

print("\n Результат: [a]{x} - b =\n",np.dot(a_orig, x) – b_orig)

Результат работы:

A= [[ 1. 1. 1.]

[ 1. -2. -2.]

[ 1. -3. 5.]]

x = [ 1. 1.2 -1.2]

Результат: [a]{x} - b = [2.22044605e-16 0.00000000e+00 0.00000000e+00]

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

  1. Федоров Ф. М., Иванова О. Ф., Павлов Н. Н., Потапова С. В. О численных методах решения бесконечных систем линейных алгебраических уравнений. Математические заметки СВФУ, Апрель-июнь, 2022. Том 29, № 2.
  2. Косовская Т.М. Обучение студентов использованию метода Гаусса для целочисленных матриц при реализации на компьютере. Компьютерные инструменты в образовании, 2019, № 3: 90-95.
  3. Joseph F. Grcar. Mathematicians of Gaussian Elimination. Notices of the AMS. Volume 58, Number 6, 782-792.
  4. Suriya Gharib, Syeda Roshana Ali, Rabia Khan, Nargis Munir& Memoona Khanam. System of Linear Equations, Guassian Elimination. Global Journal of Computer Science and Technology: C Software & Data Engineering Volume 15 Issue 5 Version 1.0 Year 2015.
  5. Adenegan, Kehinde Emmanuel and Aluko, Tope Moses. Gauss and gauss-jordan elimination methods for solving system of linear equations: comparisons and applications. Journal of Science and Science Education, Ondo Vol. 3 (1), pp. 97-105, 19th November, 2012.

Интересная статья? Поделись ей с другими: