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

Gaussian Elimination¶

In this section we define some Python functions to help us solve linear systems in the most direct way. The algorithm is known as Gaussian Elimination, which we will simply refer to as elimination from this point forward. The idea of elimination is to exchange the system we are given with another system that has the same solution, but is much easier to solve. To this end we will perform a series of steps called row operations which preserve the solution of the system while gradually making the solution more accessible. There are three such operations we may perform.

1. Exchange the position of two equations.
2. Multiply an equation by any nonzero number.
3. Replace any equation with the sum of itself and a multiple of another equation.

Example 1: Row operations and elimination¶

\[\begin \begin x_1 — x_2 + x_3 & = & 3\\ 2x_1 + x_2 + 8x_3 & = & 18\\ 4x_1 + 2x_2 -3x_3 & = & -2 \end \end\]

We could swap the first and last equation,

\[\begin \begin 4x_1 + 2x_2 -3x_3 & = & -2 \\ 2x_1 + x_2 + 8x_3 & = & 18\\ x_1 — x_2 + x_3 & = & 3 \end \end\]

or we could multiply the first equation by \(5\) ,

\[\begin \begin 5x_1 — 5x_2 + 5x_3 & = & 15\\ 2x_1 + x_2 + 8x_3 & = & 18\\ 4x_1 + 2x_2 -3x_3 & = & -2 \end \end\]

or we could add 2 times the first equation to the last equation.

\[\begin \begin x_1 — x_2 + x_3 & = & 3\\ 2x_1 + x_2 + 3x_3 & = & 8\\ 6x_1 \quad\quad -x_3 & = & 4 \end \end\]

The last operation is the most important because it allows us to eliminate a variable from one of the equations. Note that the third equation no longer contains the \(x_2\) term. This is the key to the elimination algorithm.

For computational purposes we can dispense with the variable names and the “=” symbol, and arrange all of the actual numbers in an array.

\[\begin \begin \left[ \begin 1 & -1 & 1 & 3 \\ 2 & 1 & 8 & 18 \\ 4 & 2 & -3 & -2 \end\right] \end \end\]

Now let’s build a NumPy array with these values. We’ll assign the array the name \(\texttt\) , so that we can refer to it later.

import numpy as np A=np.array([[1,-1,1,3],[2,1,8,18],[4,2,-3,-2]]) 

We could dive in an start performing operations on our array, but instead we will first write a few bits of code that will do each of these operations individually. We will tuck each operation inside a Python function so that we can use it again for future calculations.

def RowSwap(A,k,l): # ============================================================================= # A is a NumPy array. RowSwap will return duplicate array with rows # k and l swapped. # ============================================================================= m = A.shape[0] # m is number of rows in A n = A.shape[1] # n is number of columns in A B = np.copy(A).astype('float64') for j in range(n): temp = B[k][j] B[k][j] = B[l][j] B[l][j] = temp return B def RowScale(A,k,scale): # ============================================================================= # A is a NumPy array. RowScale will return duplicate array with the # entries of row k multiplied by scale. # ============================================================================= m = A.shape[0] # m is number of rows in A n = A.shape[1] # n is number of columns in A B = np.copy(A).astype('float64') for j in range(n): B[k][j] *= scale return B def RowAdd(A,k,l,scale): # ============================================================================= # A is a numpy array. RowAdd will return duplicate array with row # l modifed. The new values will be the old values of row l added to # the values of row k, multiplied by scale. # ============================================================================= m = A.shape[0] # m is number of rows in A n = A.shape[1] # n is number of columns in A B = np.copy(A).astype('float64') for j in range(n): B[l][j] += B[k][j]*scale return B 

We now have three new functions called \(\texttt\) , \(\texttt\) ,and \(\texttt\) . Let’s try them out to see what they produce.

B1 = RowSwap(A,0,2) B2 = RowScale(A,2,0.5) B3 = RowAdd(A,0,1,2) 

Источник

Решение системы уравнений методом Гаусса на 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)

Источник

Метод Гаусса в Python

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

Описание метода Гаусса

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

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

Для реализации метода Гаусса в Python, начнем с создания функции:

 def gauss_method(matrix, vector): n = len(matrix) for i in range(n): max_el = abs(matrix[i][i]) max_row = i for k in range(i + 1, n): if abs(matrix[k][i]) > max_el: max_el = abs(matrix[k][i]) max_row = k matrix[i], matrix[max_row] = matrix[max_row], matrix[i] vector[i], vector[max_row] = vector[max_row], vector[i] for k in range(i + 1, n): c = -matrix[k][i] / matrix[i][i] for j in range(i, n): if i == j: matrix[k][j] = 0 else: matrix[k][j] += c * matrix[i][j] vector[k] += c * vector[i] x = [0 for _ in range(n)] for i in range(n - 1, -1, -1): x[i] = vector[i] / matrix[i][i] for k in range(i - 1, -1, -1): vector[k] -= matrix[k][i] * x[i] return x 

Пример использования функции

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

 A = [ [3, 2, -1], [2, -2, 4], [-1, 0.5, -1] ] b = [1, -2, 0] 

Теперь, вызовем функцию gauss_method и выведем результат:

 result = gauss_method(A, b) print("Решение системы уравнений:", result) 

Выполнив данный код, мы получим решение системы уравнений с помощью метода Гаусса.

Вывод

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

Источник