Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе правого верхнего (традиционного), правого нижнего, левого верхнего или левого нижнего треугольного вида, из которой последовательно, начиная с последних или c первых (по номеру), находятся все переменные системыН. Ш. Кремер, 2.3. «Метод Гаусса», стр. 44Решение СЛАУ методом Гаусса. Куликов А. С.Решение СЛАУ упрощённым методом Гаусса. Куликов А. С..
История Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах».
Описание метода Пусть исходная система выглядит следующим образом:
Её можно записать в матричном виде:
где
Матрица называется основной матрицей системы, — столбцом свободных членов.
Тогда, согласно свойству элементарных преобразований над строками, основную матрицу этой системы можно привести к ступенчатому виду (эти же преобразования нужно применять к столбцу свободных членов):
где
При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных Такого расположения минора можно добиться перестановкой столбцов основной матрицы и соответствующей перенумерацией переменных..
Тогда переменные называются главными переменными. Все остальные называются свободными.
Если хотя бы одно число , где , то рассматриваемая система несовместна, т. е. у неё нет ни одного решения.
Пусть для любых .
Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом (, где — номер строки):
,
где
Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.
Следствия Если в совместной системе все переменные главные, то такая система является определённой. Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной.
Критерий совместности Упомянутое выше условие для всех может быть сформулировано в качестве необходимого и достаточного условия совместности:
Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).
Теорема Кронекера — Капелли Система совместна тогда и только тогда, когда ранг её основной матрицы равен рангу её расширенной матрицы.
Следствия: Количество главных переменных равно рангу системы и не зависит от её решения. Если ранг совместной системы равен числу переменных данной системы, то она определена.
Алгоритм Блок-схема представлена на рисунке. Данный рисунок — адаптированный для написания программы на языке C/C++, где a — расширенная матрица, последний столбец в которой — столбец свободных членов. Количество строк — n.
Описание Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа. На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. Для этого среди элементов первого столбца матрицы выбирают ненулевой, перемещают содержащую его строку в крайнее верхнее положение, делая эту строку первой. Далее ненулевые элементы первого столбца всех нижележащих строк обнуляются путём вычитания из каждой строки первой строки, домноженной на отношение первого элемента этих строк к первому элементу первой строки. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают, пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию. На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки. Метод Гаусса требует арифметических операций.
Этот метод опирается на: Теорема о приведении матриц к ступенчатому виду Любую матрицу путём элементарных преобразований только над строками можно привести к ступенчатому виду.
Простейший случай В простейшем случае алгоритм выглядит так:
Прямой ход:
(В 1966 году Барейс предложил алгоритм приведения матрицы СЛАУ с целочисленными коэффициентами к треугольному виду вообще без использования операции деления, который применим и для чисел с плавающей точкой. Сложность алгоритма такая же, как и в методе Гаусса - O(n3), но с уменьшением максимальных величин коэффициентов матрицы и медленнее.)
Обратный ход. Из последнего ненулевого уравнения выражаем базисную переменную через небазисные и подставляем в предыдущие уравнения. Повторяя эту процедуру для всех базисных переменных, получаем фундаментальное решение. (Обратный ход можно выполнить и методом Гаусса-Жордана, но медленнее.)
Пример
Покажем, как методом Гаусса можно решить следующую систему:
Обнулим коэффициенты при во второй и третьей строчках. Для этого прибавим к ним первую строчку, умноженную на и , соответственно:
Теперь обнулим коэффициент при в третьей строке, вычтя из неё вторую строку, умноженную на :
В результате мы привели исходную систему к треугольному виду, тем самым закончив первый этап алгоритма.
На втором этапе разрешим полученные уравнения в обратном порядке. Имеем: из третьего; из второго, подставив полученное из первого, подставив полученные и .
Таким образом, исходная система решена.
В случае, если число уравнений в совместной системе получилось меньше числа неизвестных, ответ будет записываться в виде фундаментальной системы решений.
Реализация алгоритма на языке программирования C# namespace Gauss_Method { class Maths
/// <summary> /// Метод Гаусса (Решение СЛАУ) /// </summary> /// <param name="Matrix">Начальная матрица</param> /// <returns></returns> public static double[] Gauss(double[,] Matrix)
int n = Matrix.GetLength(0); //Размерность начальной матрицы (строки) double[,] Matrix_Clone = new double[n, n + 1]; //Матрица-дублер for (int i = 0; i < n; i++) for (int j = 0; j < n + 1; j++) Matrix_Clone[i, j] = Matrix[i, j];
// Прямой ход (Зануление нижнего левого угла) for (int k = 0; k < n; k++) //k-номер строки
for (int i = 0; i < n + 1; i++) //i-номер столбца Matrix_Clone[k, i] = Matrix_Clone[k, i] / Matrix[k, k]; //Деление k-строки на первый член !=0 для преобразования его в единицу for (int i = k + 1; i < n; i++) //i-номер следующей строки после k
double K = Matrix_Clone[i, k] / Matrix_Clone[k, k]; //Коэффициент for (int j = 0; j < n + 1; j++) //j-номер столбца следующей строки после k Matrix_Clone[i, j] = Matrix_Clone[i, j] - Matrix_Clone[k, j] * K; //Зануление элементов матрицы ниже первого члена, преобразованного в единицу
for (int i = 0; i < n; i++) //Обновление, внесение изменений в начальную матрицу for (int j = 0; j < n + 1; j++) Matrix[i, j] = Matrix_Clone[i, j];
// Обратный ход (Зануление верхнего правого угла) for (int k = n - 1; k > -1; k--) //k-номер строки
for (int i = n; i > -1; i--) //i-номер столбца Matrix_Clone[k, i] = Matrix_Clone[k, i] / Matrix[k, k]; for (int i = k - 1; i > -1; i--) //i-номер следующей строки после k
double K = Matrix_Clone[i, k] / Matrix_Clone[k, k]; for (int j = n; j > -1; j--) //j-номер столбца следующей строки после k Matrix_Clone[i, j] = Matrix_Clone[i, j] - Matrix_Clone[k, j] * K;
// Отделяем от общей матрицы ответы double[] Answer = new double[n]; for (int i = 0; i < n; i++) Answer[i] = Matrix_Clone[i, n];
return Answer;
Реализация алгоритма на языке программирования Python def Gauss(Matrix): n = len(Matrix) for i in range(n): if Matrix[i][i] == 0: for k in range(i + 1, n): if Matrix[k][i] != 0: Matrix[i], Matrix[k] = Matrix[k], Matrix[i] break else: return "Система не имеет единственного решения"
for k in range(i + 1, n): c = Matrix[k][i] / Matrix[i][i] Matrix[k][i] = 0 for j in range(i + 1, n + 1): Matrix[k][j] = Matrix[k][j] - c * Matrix[i][j]
x = * n for i in range(n - 1, -1, -1): s = 0 for j in range(i + 1, n): s = s + Matrix[i][j] * x[j] x[i] = (Matrix[i][n] - s) / Matrix[i][i] return x
matrix = [ [2, 1, -1, 8], [-3, -1, 2, -11], [-2, 1, 2, -3], ] print("Решение:") print(Gauss(matrix)) Реализация алгоритма на языке программирования Borland Turbo Basic С приведением матрицы коэффициентов к правому верхнему треугольному виду и вычислением корней в обратном порядке, от X[N] до X: CLS COLOR 10
DATA 3 DATA 4.00, 0.24, -0.08, 8 DATA 0.09, 3.00, -0.15, 9 DATA 0.04, -0.08, 4.00, 20 'X=1.909198, X=3.194954, X=5.044807
05 PRINT "Reshenie sistemy iz N lineynyh uravneniy metodom Gaussa" 10 'INPUT "Chislo uravneniy N=";N READ N 20 DIM A[N,N],B[N],X[N]
'1. Vvod 30 FOR I=1 TO N 'PRINT USING "## Vvod koef. uravneniya ";I 40 FOR J=1 TO N 'INPUT A[I,J] READ A[I,J] PRINT USING "##.## ";A[I,J], 50 NEXT J 'INPUT B[I] READ B[I] PRINT USING "##.##";B[I] NEXT I
'2. Pryamoy hod 60 FOR I=1 TO N-1 FOR J=I+1 TO N 70 A[J,I]=-A[J,I]/A[I,I] FOR K=I+1 TO N 80 A[J,K]=A[J,K]+A[J,I]*A[I,K] NEXT K 90 B[J]=B[J]+A[J,I]*B[I] NEXT J NEXT I 100 X[N]=B[N]/A[N,N]
'3. Obratnyi hod 110 FOR I=N-1 TO 1 STEP -1 H=B[I] 120 FOR J=I+1 TO N H=H-X[J]*A[I,J] NEXT J 130 X[I]=H/A[I,I] NEXT I
'4. Vyvod 140 PRINT "Korni sistemy uravneniy" 150 FOR I=1 TO N PRINT USING "X[##]=##.######";I,X[I] 160 NEXT I END � С приведением матрицы коэффициентов к левому нижнему треугольному виду и вычислением корней в естественном прямом порядке, от X до X[N]: CLS COLOR 10
DATA 3 DATA 3, 2, -1, 4 DATA 2, -1, 5, 23 DATA 1, 7, -1, 5 'X=2.0, X=1.0, X=4.0
PRINT "Reshenie sistemy iz N lineynyh uravneniy prosteishim metodom Gaussa" PRINT "s nigney levoy treugolxnoy matricey"
READ N 'Chislo uravneniy DIM A[N,N+1],X[N] PRINT
'1. Vvod ------------------------- PRINT "Koefficienty sistemy uravneniy" FOR I=1 TO N FOR J=1 TO N+1 READ A[I,J] PRINT USING "###.## ";A[I,J], NEXT J PRINT NEXT I PRINT
'2. Pryamoy hod i vyvod X FOR L=0 TO N-2 FOR I=1 TO N-1-L K=A[I,N-L]/A[N-L,N-L] FOR J=1 TO N+1 A[I,J]=A[I,J]-A[N-L,J]*K NEXT J,I,L PRINT "Nignyaya levaya treugolxnaya matrica" GOSUB MATVYV PRINT PRINT "Korny sistemy uravneniy" X=A[1,N+1]/A[1,1] PRINT USING "X[ 1]=###.######";X
'3. Obratnyi hod i vyvod X[I], I>1 FOR I=2 TO N H=A[I,N+1] FOR J=1 TO I-1 H=H-A[I,J]*X[J] NEXT J X[I]=H/A[I,I] PRINT USING "X[##]=###.######";I,X[I] NEXT I END
MATVYV: FOR I=1 TO N FOR J=1 TO N+1 PRINT USING "###.###### ";A[I,J]; NEXT J PRINT NEXT I RETURN �
Применение и модификации Помимо аналитического решения СЛАУ, метод Гаусса также применяется для: