Метод Гаусса

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

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

Описание метода[править | править вики-текст]

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

\left\{\begin{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}\right.\iff Ax = b,\quad A=\left( \begin{array}{ccc}
a_{11} & \ldots & a_{1n}\\
\ldots &  &  \\
a_{m1} & \ldots & a_{mn}
\end{array}\right),\quad x = \left( \begin{array}{c}x_1 \\ \vdots \\ x_n \end{array} \right), \quad b = \left( \begin{array}{c}b_1 \\ \vdots \\ b_m \end{array} \right).\quad (1)

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

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

\left\{\begin{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} &=& \beta_1 \\
                     \alpha_{2j_2}x_{j_2}+\ldots+\alpha_{2j_r}x_{j_r}+\ldots+\alpha_{2j_n}x_{j_n} &=& \beta_2 \\
                                                                                               &\ldots& \\
                                                 \alpha_{rj_r}x_{j_r}+\ldots+\alpha_{rj_n}x_{j_n} &=& \beta_r \\
                                                                                                0 &=& \beta_{r+1} \\
                                                                                               &\ldots& \\
                                                                                                0 &=& \beta_m
\end{array}\right.,\qquad \alpha_{1j_1},\ldots,\alpha_{rj_r}\neq 0.

При этом будем считать, что базисный минор (ненулевой минор максимального порядка) основной матрицы находится в верхнем левом углу, то есть в него входят только коэффициенты при переменных x_{j_1},\ldots,x_{j_r}\![3].

Тогда переменные x_{j_1},\ldots,x_{j_r}\! называются главными переменными. Все остальные называются свободными.

Если хотя бы одно число \beta_i\neq 0\!, где i > r, то рассматриваемая система несовместна, т.е. у неё нет ни одного решения.

Пусть \beta_i = 0\! для любых i > r.

Перенесём свободные переменные за знаки равенств и поделим каждое из уравнений системы на свой коэффициент при самом левом x\! (\alpha_{ij_i},\, i=1,\ldots,r\!, где i\! — номер строки):

\left\{\begin{array}{rcc}
x_{j_1}+\widehat{\alpha}_{1j_2}x_{j_2}+\ldots+\widehat{\alpha}_{1j_r}x_{j_r}&=& \widehat{\beta}_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{\beta}_2-\widehat{\alpha}_{2j_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{2j_n}x_{j_n} \\
                                                           &\ldots& \\
                                                       x_{j_r}&=& \widehat{\beta}_r-\widehat{\alpha}_{rj_{r+1}}x_{j_{r+1}}-\ldots- \widehat{\alpha}_{rj_n}x_{j_n} \\
\end{array}\right., \qquad \widehat{\beta}_i=\frac{\beta_i}{\alpha_{ij_i}},\quad \widehat{\alpha}_{ij_k}=\frac{\alpha_{ij_k}}{\alpha_{ij_i}}\quad (2),
где i=1,\ldots,r,\quad k=i+1,\ldots,n.\!

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

Logo arte.jpg Следствия:
1: Если в совместной системе все переменные главные, то такая система является определённой.

2: Если количество переменных в системе превосходит число уравнений, то такая система является либо неопределённой, либо несовместной.

Условие совместности[править | править вики-текст]

Упомянутое выше условие \beta_i= 0\! для всех i > r\! может быть сформулировано в качестве необходимого и достаточного условия совместности:

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

Logo arte.jpg Теорема Кронекера — Капелли.
Система совместна тогда и только тогда, когда ранг её основной матрицы равен рангу её расширенной матрицы.

Следствия:

  • Количество главных переменных равно рангу системы и не зависит от её решения.
  • Если ранг совместной системы равен числу переменных данной системы, то она определена.

Алгоритм[править | править вики-текст]

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

Алгоритм Гаусса для решения САУ

Описание[править | править вики-текст]

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

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

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

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

Logo arte.jpg Теорема (о приведении матриц к ступенчатому виду).
Любую матрицу путём элементарных преобразований только над строками можно привести к ступенчатому виду.

Простейший случай[править | править вики-текст]

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

\left\{\begin{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}\right.

  • Прямой ход:

\begin{array}{ccc}
(2)\to (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)\to (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)\to (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)\to (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)\to (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}

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

Пример[править | править вики-текст]

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

\left\{\begin{array}{ccc}2x + y - z &=& 8 \\
-3x - y + 2z &=& -11 \\
-2x + y + 2z &=& -3 \end{array}\right.

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

\left\{\begin{array}{rcc}
2x + y - z &=& 8 \\
\frac{1}{2}y + \frac{1}{2}z &=& 1 \\
2y + z &=& 5 \end{array}\right.

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

\left\{\begin{array}{rcc}
2x + y - z &=& 8 \\
\frac{1}{2} y + \frac{1}{2} z &=& 1 \\
-z &=& 1 \\ \end{array}\right.

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

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

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

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

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

Применение и модификации[править | править вики-текст]

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

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

Достоинства метода[править | править вики-текст]

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

Устойчивость метода Гаусса[править | править вики-текст]

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

Неоптимальность метода Гаусса[править | править вики-текст]

В 1969 году Штрассен доказал, что большие матрицы можно перемножить за время \Theta(n^{log_2{7}})=\Theta(n^{2.81}).[6] Отсюда вытекает, что обращение матриц и решение СЛАУ можно осуществлять алгоритмами асимптотически более быстрыми по порядку, чем метод Гаусса. Таким образом, для больших СЛАУ метод Гаусса не оптимален по скорости.

См. также[править | править вики-текст]

Линейная алгебра

Методы оптимизации

Численные методы

Примечания[править | править вики-текст]

  1. Гаусс, Карл Фридрих (17771855) — немецкий математик, физик и астроном
  2. Н. Ш. Кремер, 2.3. «Метод Гаусса», стр. 44
  3. Такого расположения минора можно добиться перестановкой столбцов основной матрицы и соответствующей перенумерацией переменных.
  4. Н. Ш. Кремер, 2.4. «Система m линейных уравнений с n переменными», стр. 49
  5. УСТОЙЧИВОСТЬ И ТОЧНОСТЬ ПРЯМЫХ МЕТОДОВ
  6. Volker Strassen: Gaussian Elimination is not Optimal. In: Numerische Mathemetik, Bd. 13 (1969), S. 354—356, ISSN 00298-599X

Литература[править | править вики-текст]

  • Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: ФИЗМАТЛИТ, 2004. — 280 с.
  • Амосов А. А., Дубинский Ю. А., Копченова Н. П. Вычислительные методы для инженеров. — М.: Мир, 1998.
  • Бахвалов Н. С., Жидков Н. П., Кобельков Г. Г. Численные методы. — 8-е изд. — М.: Лаборатория Базовых Знаний, 2000.
  • Волков Е. А. Численные методы. — М.: Физматлит, 2003.
  • Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
  • Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н. Высшая математика для экономистов / Под ред. Н. Ш. Кремера. — 3-е изд. — М.: ЮНИТИ-ДАНА, 2007. — 479 с. — ISBN 5-238-00991-7.