Метод Гаусса

Метод Гаусса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы.

История

Хотя в настоящее время данный метод повсеместно называется методом Гаусса, он был известен и до К. Ф. Гаусса. Первое известное описание данного метода — в китайском трактате «Математика в девяти книгах».

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

Пусть исходная система выглядит следующим образом:

{ a 11 x 1 + … + a 1 n x n = b 1 … a m 1 x 1 + … + a m n x n = b m {displaystyle left{{egin{array}{lcr}a_{11}x_{1}+ldots +a_{1n}x_{n}&=&b_{1}ldots &&a_{m1}x_{1}+ldots +a_{mn}x_{n}&=&b_{m}end{array}} ight.}

Её можно записать в матричном виде:

A x = b , {displaystyle Ax=b,}

где

A = ( a 11 … a 1 n … a m 1 … a m n ) , x = ( x 1 ⋮ x n ) , b = ( b 1 ⋮ b m ) . ( 1 ) {displaystyle A=left({egin{array}{ccc}a_{11}&ldots &a_{1n}ldots &&a_{m1}&ldots &a_{mn}end{array}} ight),quad x=left({egin{array}{c}x_{1}vdots x_{n}end{array}} ight),quad b=left({egin{array}{c}b_{1}vdots b_{m}end{array}} ight).quad (1)}

Матрица A {displaystyle A} называется основной матрицей системы, b {displaystyle b} — столбцом свободных членов.

Тогда, согласно свойству элементарных преобразований над строками, основную матрицу этой системы можно привести к ступенчатому виду (эти же преобразования нужно применять к столбцу свободных членов):

{ α 1 j 1 x j 1 + α 1 j 2 x j 2 + … + α 1 j r x j r + … + α 1 j n x j n = β 1 α 2 j 2 x j 2 + … + α 2 j r x j r + … + α 2 j n x j n = β 2 … α r j r x j r + … + α r j n x j n = β r 0 = β r + 1 … 0 = β m , {displaystyle left{{egin{array}{rcl}alpha _{1j_{1}}x_{j_{1}}+alpha _{1j_{2}}x_{j_{2}}+ldots +alpha _{1j_{r}}x_{j_{r}}+ldots +alpha _{1j_{n}}x_{j_{n}}&=&eta _{1}alpha _{2j_{2}}x_{j_{2}}+ldots +alpha _{2j_{r}}x_{j_{r}}+ldots +alpha _{2j_{n}}x_{j_{n}}&=&eta _{2}&ldots &alpha _{rj_{r}}x_{j_{r}}+ldots +alpha _{rj_{n}}x_{j_{n}}&=&eta _{r}&=&eta _{r+1}&ldots &&=&eta _{m}end{array}} ight.,}

где α 1 j 1 , … , α r j r ≠ 0. {displaystyle alpha _{1j_{1}},ldots ,alpha _{rj_{r}} eq 0.}

При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных x j 1 , … , x j r {displaystyle x_{j_{1}},ldots ,x_{j_{r}}} .

Тогда переменные x j 1 , … , x j r {displaystyle x_{j_{1}},ldots ,x_{j_{r}}} называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число β i ≠ 0 {displaystyle eta _{i} eq 0} , где i > r {displaystyle i>r} , то рассматриваемая система несовместна, т. е. у неё нет ни одного решения.

Пусть β i = 0 {displaystyle eta _{i}=0} для любых i > r {displaystyle i>r} .

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом x {displaystyle x} ( α i j i , i = 1 , … , r {displaystyle alpha _{ij_{i}},,i=1,ldots ,r} , где i {displaystyle i} — номер строки):

{ x j 1 + α ^ 1 j 2 x j 2 + … + α ^ 1 j r x j r = β ^ 1 − α ^ 1 j r + 1 x j r + 1 − … − α ^ 1 j n x j n x j 2 + … + α ^ 2 j r x j r = β ^ 2 − α ^ 2 j r + 1 x j r + 1 − … − α ^ 2 j n x j n … x j r = β ^ r − α ^ r j r + 1 x j r + 1 − … − α ^ r j n x j n , β ^ i = β i α i j i , α ^ i j k = α i j k α i j i ( 2 ) {displaystyle left{{egin{array}{rcc}x_{j_{1}}+{widehat {alpha }}_{1j_{2}}x_{j_{2}}+ldots +{widehat {alpha }}_{1j_{r}}x_{j_{r}}&=&{widehat {eta }}_{1}-{widehat {alpha }}_{1j_{r+1}}x_{j_{r+1}}-ldots -{widehat {alpha }}_{1j_{n}}x_{j_{n}}x_{j_{2}}+ldots +{widehat {alpha }}_{2j_{r}}x_{j_{r}}&=&{widehat {eta }}_{2}-{widehat {alpha }}_{2j_{r+1}}x_{j_{r+1}}-ldots -{widehat {alpha }}_{2j_{n}}x_{j_{n}}&ldots &x_{j_{r}}&=&{widehat {eta }}_{r}-{widehat {alpha }}_{rj_{r+1}}x_{j_{r+1}}-ldots -{widehat {alpha }}_{rj_{n}}x_{j_{n}}end{array}} ight.,qquad {widehat {eta }}_{i}={frac {eta _{i}}{alpha _{ij_{i}}}},quad {widehat {alpha }}_{ij_{k}}={frac {alpha _{ij_{k}}}{alpha _{ij_{i}}}}quad (2)} ,

где i = 1 , … , r , k = i + 1 , … , n . {displaystyle i=1,ldots ,r,quad k=i+1,ldots ,n.}

Если свободным переменным системы (2) придавать все возможные значения и решать новую систему относительно главных неизвестных снизу вверх (то есть от нижнего уравнения к верхнему), то мы получим все решения этой СЛАУ. Так как эта система получена путём элементарных преобразований над исходной системой (1), то по теореме об эквивалентности при элементарных преобразованиях системы (1) и (2) эквивалентны, то есть множества их решений совпадают.

Критерий совместности

Упомянутое выше условие β i = 0 {displaystyle eta _{i}=0} для всех i > r {displaystyle i>r} может быть сформулировано в качестве необходимого и достаточного условия совместности:

Напомним, что рангом совместной системы называется ранг её основной матрицы (либо расширенной, так как они равны).

Алгоритм

Блок-схема представлена на рисунке. Данный рисунок — адаптированный для написания программы на языке С/С++, где a — расширенная матрица, последний столбец в которой — столбец свободных членов. Количество строк — n.

Описание

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

• На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. Для этого среди элементов первого столбца матрицы выбирают ненулевой, перемещают содержащую его строку в крайнее верхнее положение, делая эту строку первой. Далее ненулевые элементы первого столбца всех нижележащих строк обнуляются путём вычитания из каждой строки первой строки, домноженной на отношение первого элемента этих строк к первому элементу первой строки. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают, пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.
• На втором этапе осуществляется так называемый обратный ход, суть которого заключается в том, чтобы выразить все получившиеся базисные переменные через небазисные и построить фундаментальную систему решений, либо, если все переменные являются базисными, то выразить в численном виде единственное решение системы линейных уравнений. Эта процедура начинается с последнего уравнения, из которого выражают соответствующую базисную переменную (а она там всего одна) и подставляют в предыдущие уравнения, и так далее, поднимаясь по «ступенькам» наверх. Каждой строчке соответствует ровно одна базисная переменная, поэтому на каждом шаге, кроме последнего (самого верхнего), ситуация в точности повторяет случай последней строки.

Метод Гаусса требует O ( n 3 ) {displaystyle O(n^{3})} арифметических операций.

Этот метод опирается на:

Простейший случай

В простейшем случае алгоритм выглядит так:

{ a 11 ⋅ x 1 + a 12 ⋅ x 2 + … + a 1 n ⋅ x n = b 1 ( 1 ) a 21 ⋅ x 1 + a 22 ⋅ x 2 + … + a 2 n ⋅ x n = b 2 ( 2 ) … a m 1 ⋅ x 1 + a m 2 ⋅ x 2 + … + a m n ⋅ x n = b m ( m ) {displaystyle left{{egin{array}{lcc}a_{11}cdot x_{1}+a_{12}cdot x_{2}+ldots +a_{1n}cdot x_{n}&=b_{1}&(1)a_{21}cdot x_{1}+a_{22}cdot x_{2}+ldots +a_{2n}cdot x_{n}&=b_{2}&(2)ldots &&a_{m1}cdot x_{1}+a_{m2}cdot x_{2}+ldots +a_{mn}cdot x_{n}&=b_{m}&(m)end{array}} ight.}

• Прямой ход:

( 2 ) → ( 2 ) − ( 1 ) ⋅ ( a 21 a 11 ) : a 22 ′ ⋅ x 2 + a 23 ′ ⋅ x 3 + … + a 2 n ′ ⋅ x n = b 2 ′ ( 3 ) → ( 3 ) − ( 1 ) ⋅ ( a 31 a 11 ) : a 32 ′ ⋅ x 2 + a 33 ′ ⋅ x 3 + … + a 3 n ′ ⋅ x n = b 3 ′ … ( m ) → ( m ) − ( 1 ) ⋅ ( a m 1 a 11 ) : a m 2 ′ ⋅ x 2 + a m 3 ′ ⋅ x 3 + … + a m n ′ ⋅ x n = b n ′ ( 3 ) → ( 3 ) − ( 2 ) ⋅ ( a 32 ′ a 22 ′ ) : a 33 ′ ′ ⋅ x 3 + … + a 3 n ′ ′ ⋅ x n = b 3 ′ ′ … ( m ) → ( m ) − ( m − 1 ) ⋅ ( a m , n − 1 ( m − 2 ) a m − 1 , n − 1 ( m − 2 ) ) : a m m ( m − 1 ) ⋅ x m + … + a m n ( m − 1 ) ⋅ x n = b m ( m − 1 ) {displaystyle {egin{array}{ccc}(2) o (2)-(1)cdot ({frac {a_{21}}{a_{11}}})&:&a_{22}^{prime }cdot x_{2}+a_{23}^{prime }cdot x_{3}+ldots +a_{2n}^{prime }cdot x_{n}=b_{2}^{prime }(3) o (3)-(1)cdot ({frac {a_{31}}{a_{11}}})&:&a_{32}^{prime }cdot x_{2}+a_{33}^{prime }cdot x_{3}+ldots +a_{3n}^{prime }cdot x_{n}=b_{3}^{prime }ldots &&(m) o (m)-(1)cdot ({frac {a_{m1}}{a_{11}}})&:&a_{m2}^{prime }cdot x_{2}+a_{m3}^{prime }cdot x_{3}+ldots +a_{mn}^{prime }cdot x_{n}=b_{n}^{prime }(3) o (3)-(2)cdot ({frac {a_{32}^{prime }}{a_{22}^{prime }}})&:&a_{33}^{prime prime }cdot x_{3}+ldots +a_{3n}^{prime prime }cdot x_{n}=b_{3}^{prime prime }ldots &&(m) o (m)-(m-1)cdot ({frac {a_{m,n-1}^{(m-2)}}{a_{m-1,n-1}^{(m-2)}}})&:&a_{mm}^{(m-1)}cdot x_{m}+ldots +a_{mn}^{(m-1)}cdot x_{n}=b_{m}^{(m-1)}end{array}}}

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

Пример

Покажем, как методом Гаусса можно решить следующую систему:

{ 2 x + y − z = 8 − 3 x − y + 2 z = − 11 − 2 x + y + 2 z = − 3 {displaystyle left{{egin{array}{ccc}2x+y-z&=&8-3x-y+2z&=&-11-2x+y+2z&=&-3end{array}} ight.}

Обнулим коэффициенты при x {displaystyle x} во второй и третьей строчках. Для этого прибавим к ним первую строчку, умноженную на 3 2 {displaystyle extstyle {frac {3}{2}}} и 1 {displaystyle 1} , соответственно:

{ 2 x + y − z = 8 1 2 y + 1 2 z = 1 2 y + z = 5 {displaystyle left{{egin{array}{rcc}2x+y-z&=&8{frac {1}{2}}y+{frac {1}{2}}z&=&12y+z&=&5end{array}} ight.}

Теперь обнулим коэффициент при y {displaystyle y} в третьей строке, вычтя из неё вторую строку, умноженную на 4 {displaystyle 4} :

{ 2 x + y − z = 8 1 2 y + 1 2 z = 1 − z = 1 {displaystyle left{{egin{array}{rcc}2x+y-z&=&8{frac {1}{2}}y+{frac {1}{2}}z&=&1-z&=&1end{array}} ight.}

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

На втором этапе разрешим полученные уравнения в обратном порядке. Имеем:

z = − 1 {displaystyle z=-1} из третьего; y = 3 {displaystyle y=3} из второго, подставив полученное z {displaystyle z} x = 2 {displaystyle x=2} из первого, подставив полученные z {displaystyle z} и y {displaystyle y} .

Таким образом, исходная система решена.

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

Реализация алгоритма на языке программирования 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; } } }

Применение и модификации

Помимо аналитического решения СЛАУ, метод Гаусса также применяется для:

• нахождения матрицы, обратной к данной (к матрице справа приписывается единичная такого же размера, что и исходная: [ A | E ] {displaystyle [A|E]} , после чего A {displaystyle A} приводится к виду единичной матрицы методом Гаусса—Жордана; в результате на месте изначальной единичной матрицы справа оказывается обратная к исходной матрица: [ E | A − 1 ] {displaystyle [E|A^{-1}]} );
• определения ранга матрицы (согласно следствию из теоремы Кронекера — Капелли ранг матрицы равен числу её главных переменных);
• численного решения СЛАУ в технических приложениях (для уменьшения погрешности вычислений используется Метод Гаусса с выделением главного элемента, суть которого заключена в том, чтобы на каждом шаге в качестве главной переменной выбирать ту, при которой среди оставшихся после вычёркивания очередных строк и столбцов стоит максимальный по модулю коэффициент).

Достоинства метода

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

Устойчивость метода Гаусса

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

Неоптимальность метода Гаусса

В 1969 году Штрассен доказал, что большие матрицы можно перемножить за время O ( n log 2 ⁡ 7 ) = O ( n 2 , 81 ) {displaystyle O(n^{log _{2}{7}})=O(n^{2{,}81})} . Отсюда вытекает, что обращение матриц и решение СЛАУ можно осуществлять алгоритмами асимптотически более быстрыми по порядку, чем метод Гаусса. Таким образом, для больших СЛАУ метод Гаусса не оптимален по скорости.