Питон матрицы методом гаусса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метод Гаусса

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

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

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

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

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

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

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

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

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

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

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

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

print(«\n Результат: [a] — b =\n»,np.dot(a_orig, x) – b_orig)

Результат: [a] — 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.

Источник

Решение системы уравнений методом Гаусса на Python

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

Алгоритм метода Гаусса

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

Эти преобразования включают в себя:

1. Перестановка двух строк матрицы местами;
2. Умножение строки на ненулевое число;
3. Прибавление к одной строке другой строке, умноженной на число.

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

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

Решение СЛАУ методом Гаусса на Python

• Для решения СЛАУ методом Гаусса мы будем использовать библиотеку numpy, которая позволит сделать код чище и читаемее за счёт вынесения некоторой логики на уровень абстракции.

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

A = np.array([[2.7, 3.3, 1.3], [3.5, -1.7, 2.8], [4.1, 5.8, -1.7]]) B = np.array([2.1, 1.7, 0.8])

• Согласно формуле метода Гаусса, по нему необходимо пройтись циклом. Длина цикла будет равна длине массива свободных членов (B).

• В цикле в первую очередь нам нужно найти максимальный элемент в каждом столбце. Т.е. при каждой итерации цикла мы будем искать в i-том столбце.

 maxEl = abs(A[i][i]) maxRow = i for k in range(i + 1, n): if abs(A[k][i]) > maxEl: maxEl = abs(A[k][i]) maxRow = k

 for k in range(i, n): tmp = A[maxRow][k] A[maxRow][k] = A[i][k] A[i][k] = tmp tmp = B[maxRow] B[maxRow] = B[i] B[i] = tmp

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

 for k in range(i + 1, n): c = -A[k][i] / A[i][i] for j in range(i, n): if i == j: A[k][j] = 0 else: A[k][j] += c * A[i][j] B[k] += c * B[i]

• Далее мы делаем обратный ход, который является последней операцией над СЛАУ для решения её методом Гаусса.

x = np.zeros(n) for i in range(n - 1, -1, -1): x[i] = B[i] for j in range(i + 1, n): x[i] -= A[i][j] * x[j] x[i] /= A[i][i]

Полный код решения СЛАУ методом Гаусса на Python

import numpy as np # Определяем матрицу системы уравнений A = np.array([[2.7, 3.3, 1.3], [3.5, -1.7, 2.8], [4.1, 5.8, -1.7]]) # Определяем столбец свободных членов B = np.array([2.1, 1.7, 0.8]) # Прямой ход метода Гаусса n = len(B) for i in range(n): # Поиск максимального элемента в столбце i maxEl = abs(A[i][i]) maxRow = i for k in range(i + 1, n): if abs(A[k][i]) > maxEl: maxEl = abs(A[k][i]) maxRow = k # Обмен строками for k in range(i, n): tmp = A[maxRow][k] A[maxRow][k] = A[i][k] A[i][k] = tmp tmp = B[maxRow] B[maxRow] = B[i] B[i] = tmp # Приведение к верхнетреугольному виду for k in range(i + 1, n): c = -A[k][i] / A[i][i] for j in range(i, n): if i == j: A[k][j] = 0 else: A[k][j] += c * A[i][j] B[k] += c * B[i] # Обратный ход метода Гаусса x = np.zeros(n) for i in range(n - 1, -1, -1): x[i] = B[i] for j in range(i + 1, n): x[i] -= A[i][j] * x[j] x[i] /= A[i][i] # Вывод результата print("Result:") print(x)

Результат выполнения кода:

Выделим код в отдельную функцию

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

import numpy as np def gauss(A, B): # Прямой ход метода Гаусса n = len(B) for i in range(n): # Поиск максимального элемента в столбце i maxEl = abs(A[i][i]) maxRow = i for k in range(i + 1, n): if abs(A[k][i]) > maxEl: maxEl = abs(A[k][i]) maxRow = k # Обмен строками for k in range(i, n): tmp = A[maxRow][k] A[maxRow][k] = A[i][k] A[i][k] = tmp tmp = B[maxRow] B[maxRow] = B[i] B[i] = tmp # Приведение к верхнетреугольному виду for k in range(i + 1, n): c = -A[k][i] / A[i][i] for j in range(i, n): if i == j: A[k][j] = 0 else: A[k][j] += c * A[i][j] B[k] += c * B[i] # Обратный ход метода Гаусса x = np.zeros(n) for i in range(n - 1, -1, -1): x[i] = B[i] for j in range(i + 1, n): x[i] -= A[i][j] * x[j] x[i] /= A[i][i] return x # Определяем матрицу системы уравнений A = np.array([[2.7, 3.3, 1.3], [3.5, -1.7, 2.8], [4.1, 5.8, -1.7]]) # Определяем столбец свободных членов B = np.array([2.1, 1.7, 0.8]) x = gauss(A, B) # Вывод результата print("Result:") print(x)

Источник