Метод Гаусса

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

История

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

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

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

$\{\begin{array}{ccc}{a}_{11}{x}_1+\dots +a_{1n}{x}_n& =& b_1\\ \dots & & \\ a_{m1}{x}_1+\dots +a_{mn}{x}_n& =& b_m\end{array}$

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

$Ax=b,$

где

$A=\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ \dots & & \\ a_{m1}& \dots & a_{mn}\end{array}\right),x=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right),b=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_m\end{array}\right).(1)$

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

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

$\{\begin{array}{ccc}{\alpha }_{1j_1}{x}_{j_1}+{\alpha }_{1j_2}{x}_{j_2}+\dots +{\alpha }_{1j_r}{x}_{j_r}+\dots +{\alpha }_{1j_n}{x}_{j_n}& =& {\beta }_1\\ {\alpha }_{2j_2}{x}_{j_2}+\dots +{\alpha }_{2j_r}{x}_{j_r}+\dots +{\alpha }_{2j_n}{x}_{j_n}& =& {\beta }_2\\ & \dots & \\ {\alpha }_{r{j}_r}{x}_{j_r}+\dots +{\alpha }_{r{j}_n}{x}_{j_n}& =& {\beta }_r\\ 0& =& {\beta }_{r+1}\\ & \dots & \\ 0& =& {\beta }_m\end{array},$

где ${\alpha }_{1j_1},\dots ,{\alpha }_{r{j}_r}\ne 0.$

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

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

Если хотя бы одно число ${\beta }_i\ne 0$, где $i>r$, то рассматриваемая система несовместна, т. е. у неё нет ни одного решения.

Пусть ${\beta }_i=0$ для любых $i>r$.

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

$\{\begin{array}{ccc}{x}_{j_1}+{\hat{\alpha }}_{1j_2}{x}_{j_2}+\dots +{\hat{\alpha }}_{1j_r}{x}_{j_r}& =& {\hat{\beta }}_1-{\hat{\alpha }}_{1j_{r+1}}{x}_{j_{r+1}}-\dots -{\hat{\alpha }}_{1j_n}{x}_{j_n}\\ x_{j_2}+\dots +{\hat{\alpha }}_{2j_r}{x}_{j_r}& =& {\hat{\beta }}_2-{\hat{\alpha }}_{2j_{r+1}}{x}_{j_{r+1}}-\dots -{\hat{\alpha }}_{2j_n}{x}_{j_n}\\ & \dots & \\ x_{j_r}& =& {\hat{\beta }}_r-{\hat{\alpha }}_{r{j}_{r+1}}{x}_{j_{r+1}}-\dots -{\hat{\alpha }}_{r{j}_n}{x}_{j_n}\end{array},{\hat{\beta }}_i=\frac{{\beta }_i}{{\alpha }_{i{j}_i}},{\hat{\alpha }}_{i{j}_k}=\frac{{\alpha }_{i{j}_k}}{{\alpha }_{i{j}_i}}(2)$,

где $i=1,\dots ,r,k=i+1,\dots ,n.$

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

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

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

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

Алгоритм

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

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

Описание

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

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

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

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

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

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

$\{\begin{array}{ccc}{a}_{11}\cdot x_1+a_{12}\cdot x_2+\dots +a_{1n}\cdot x_n& =b_1& (1)\\ a_{21}\cdot x_1+a_{22}\cdot x_2+\dots +a_{2n}\cdot x_n& =b_2& (2)\\ \dots & & \\ a_{m1}\cdot x_1+a_{m2}\cdot x_2+\dots +a_{mn}\cdot x_n& =b_m& (m)\end{array}$

• Прямой ход:

$\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+\dots +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+\dots +a_{3n}^{\prime }\cdot x_n=b_3^{\prime }\\ \dots & & \\ (m)\to (m)-(1)\cdot (\frac{a_{m1}}{a_{11}})& :& a_{m2}^{\prime }\cdot x_2+a_{m3}^{\prime }\cdot x_3+\dots +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+\dots +a_{3n}^{\prime \prime }\cdot x_n=b_3^{\prime \prime }\\ \dots & & \\ (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+\dots +a_{mn}^{(m-1)}\cdot x_n=b_m^{(m-1)}\end{array}$

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

Пример

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

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

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

$\{\begin{array}{ccc}2x+y-z& =& 8\\ \frac{1}{2}y+\frac{1}{2}z& =& 1\\ 2y+z& =& 5\end{array}$

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

$\{\begin{array}{ccc}2x+y-z& =& 8\\ \frac{1}{2}y+\frac{1}{2}z& =& 1\\ -z& =& 1\end{array}$

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

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

$z=-1$ из третьего;

$y=3$ из второго, подставив полученное $z$

$x=2$ из первого, подставив полученные $z$ и $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;
        }
    }
}

Реализация алгоритма на языке программирования Borland Turbo Basic

С приведением матрицы коэффициентов к верхнему правому треугольному виду и вычислением корней в обратном порядке, от X[N] до X[1]:

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]=1.909198, X[2]=3.194954, X[3]=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[1] до X[N]:

CLS
COLOR 10

DATA 3
DATA 3,  2, -1,  4
DATA 2, -1,  5, 23
DATA 1,  7, -1,  5
'X[1]=2.0, X[2]=1.0, X[3]=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[1]
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[1]=A[1,N+1]/A[1,1]
PRINT USING "X[ 1]=###.######";X[1]

'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
�

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

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

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

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

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

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

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

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

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

См. также

• Метод Гаусса — Жордана
• Метод Крамера
• Система линейных алгебраических уравнений
• Теорема Кронекера — Капелли
• Фундаментальная система решений
• Элементарные преобразования матрицы
• Метод Гаусса (оптимизация)
• Метод покоординатного спуска (Гаусса — Зейделя)
• Метод Якоби

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Шаблон:Citation