Русская Википедия:Метод Гаусса

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

История

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

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

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

<math>\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. </math> Её можно записать в матричном виде:

<math>Ax = b,</math>

где

<math>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)</math>

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

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

<math>\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.,</math> где <math>\alpha_{1j_1},\ldots,\alpha_{rj_r}\neq 0.</math>

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

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

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

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

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

<math>\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)</math>,

где <math>i=1,\ldots,r,\quad k=i+1,\ldots,n.</math>

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

Шаблон:Message box

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

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

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

Шаблон:Message box

Алгоритм

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

Файл:Gauss.png
Алгоритм Гаусса для решения СЛАУ

Описание

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

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

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

Этот метод опирается на: Шаблон:Message box

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

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

<math>

\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. </math>

  • Прямой ход:
<math>\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}</math>

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

Пример

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

<math>\left\{\begin{array}{ccc}2x + y - z &=& 8 \\

-3x - y + 2z &=& -11 \\ -2x + y + 2z &=& -3 \end{array}\right.</math>

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

<math>\left\{\begin{array}{rcc}

2x + y - z &=& 8 \\ \frac{1}{2}y + \frac{1}{2}z &=& 1 \\ 2y + z &=& 5 \end{array}\right.</math>

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

<math>\left\{\begin{array}{rcc}

2x + y - z &=& 8 \\ \frac{1}{2} y + \frac{1}{2} z &=& 1 \\ -z &=& 1 \\ \end{array}\right.</math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В 1969 году Штрассен доказал, что большие матрицы можно перемножить за время <math>O(n^{\log_2{7}}) = O(n^{2{,}81})</math>Шаблон:Source-ref. Отсюда вытекает, что обращение матриц и решение СЛАУ можно осуществлять алгоритмами асимптотически более быстрыми по порядку, чем метод Гаусса. Таким образом, для больших СЛАУ метод Гаусса не оптимален по скорости.

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:ВС Шаблон:Методы решения СЛАУ

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Н. Ш. Кремер, 2.3. «Метод Гаусса», стр. 44
  2. ↑ Такого расположения минора можно добиться перестановкой столбцов основной матрицы и соответствующей перенумерацией переменных.
  3. ↑ Н. Ш. Кремер, 2.4. «Система m линейных уравнений с n переменными», стр. 49
  4. ↑ УСТОЙЧИВОСТЬ И ТОЧНОСТЬ ПРЯМЫХ МЕТОДОВШаблон:Недоступная ссылка
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Метод_Гаусса&oldid=10372888