Автор: Катя Романцова

Метод Гаусса

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

Метод Гаусса построен на элементарных преобразованиях СЛАУ.

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

Определение. Две системы называются эквивалентными, если уравнения одной системы являются линейной комбинацией уравнений другой. Также они имеют одинаковые решения или обе решений не имеют.

Алгоритм решения методом Гаусса заключается в следующих действиях:

  1. Прямой ход. Допустим, нам дана СЛАУ из $k$ уравнений с $n$ неизвестными $$\begin{equation}\left\{\begin{aligned}
    a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_{n}=b_1,\\
    a_{21}x_1+a_{22}x_2+a_{23}x_3+\ldots+a_{2n}x_{n}=b_2,\\
    a_{31}x_1+a_{32}x_2+a_{33}x_3+\ldots+a_{3n}x_{n}=b_3,\\
    \cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\\
    a_{k1}x_1+a_{k2}x_2+a_{k3}x_3+\ldots+a_{kn}x_n=b_k.\\
    \end{aligned}\right.
    \end{equation}$$     Сначала исключим неизвестное $x_1$ из уравнений ниже первого. Предположим $a_{11} \ne 0$ (в обратном случае — можно записать первым уравнение с коэффициентом при $x_1$, отличным от нуля). Теперь умножим обе части первого уравнения системы на $\frac{a_{21}}{a_{11}}$ и вычтем его из второго уравнения, затем обе части первого уравнения умножим на $\frac{a_{31}}{a_{11}}$ и вычтем из третьего и так пока не исключим во всех уравнениях ниже первого переменную $x_1$ (то есть пока коэффициенты при $x_1$ не будут равны нулю). Получаем эквивалентную системе (1) систему: $$\begin{equation}\left\{\begin{aligned}
    a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_{n}=b_1,\\
    \bar a_{22}x_2+\bar a_{23}x_3+\ldots+\bar a_{2n}x_{n}=\bar b_2,\\
    \bar a_{32}x_2+\bar a_{33}x_3+\ldots+\bar a_{3n}x_{n}=\bar b_3,\\
    \cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\\
    \bar a_{k2}x_2+\bar a_{k3}x_3+\ldots+\bar a_{kn}x_n=\bar b_k.\\
    \end{aligned}\right.
    \end{equation}$$     Далее делаем аналогичные действия со СЛАУ (2) (исключаем неизвестное $x_2$), но с уравнениями ниже второго при $a_{22} \ne 0$. Получим следующую эквивалентную системе (2) (значит и системе (1)) систему: $$\begin{equation}\left\{\begin{aligned}
    a_{11}x_1+a_{12}x_2+a_{13}x_3+\ldots+a_{1n}x_{n}=b_1,\\
    \bar a_{22}x_2+\bar a_{23}x_3+\ldots+\bar a_{2n}x_{n}=\bar b_2,\\
    \tilde a_{33}x_3+\ldots+\tilde a_{3n}x_{n}=\tilde b_3,\\
    \cdots\qquad\cdots\qquad\cdots\qquad\\
    \tilde a_{k3}x_3+\ldots+\tilde a_{kn}x_n=\tilde b_k.\\
    \end{aligned}\right.
    \end{equation}$$ Все эти действия нужно сделать, пока не получим систему ступенчатого вида.
  2. Обратный ход. Второй этап решения системы уравнений заключается в решении полученной нами системы ступенчатого вида. Количество уравнений в преобразованной системе может быть меньше, чем в изначальной. Получаем систему с $t (t\leqslant k)$ уравнениями и $n$ переменными. Выражаем через последнее уравнение неизвестную переменную $x_t$. И через неё выражаем остальные переменные. Получим решение, которое содержит зависимые (слева) и свободные (справа) переменные: $$\begin{equation}\left\{\begin{aligned}
    x_t=c_{tt+1}x_{t+1}+a_{tt+2}x_{t+2}+\ldots+c_{tn}x_{n,}\\
    \cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\cdots\qquad\\
    x_3=c_{3t+1}x_{t+1}+a_{3t+2}x_{t+2}+\ldots+c_{3n}x_{n},\\
    x_2=c_{2t+1}x_{t+1}+a_{2t+2}x_{t+2}+\ldots+c_{2n}x_{n},\\
    x_1=c_{1t+1}x_{t+1}+a_{1t+2}x_{t+2}+\ldots+c_{1n}x_{n}.\\
    \end{aligned}\right.
    \end{equation}$$ Для получения решения, в свободные переменные $x_{t+1} \ldots x_n$ мы подставляем произвольные значения в систему уравнений. Из чего находим зависимые переменные $x_1 \ldots x_t$.
Замечания

  • Если система уравнений получается треугольной (или же количество уравнений равно количеству переменных), то решение у этой системы одно (система называется определенной). Если система имеет несколько ответов, то система называется неопределенной.
  • Система есть несовместная, если она не имеет решений. Это можно понять по тому, если преобразованная нами система имеет уравнений больше, чем переменных (или мы можем получить уравнение, в котором все коэффициенты равны нулю, но свободный член отличен от нуля). В обратном случае — эта система совместная.
  • Обычно выполняют преобразования не с самой системой, а с матрицей системы: выписывают матрицу из коэффициентов системы с присоединенным к ней столбцом из свободных членов. Тогда стоит заметить, что такие элементарные преобразования можно выполнять только с матрицами системы. С обычными матрицами, которые просто даны в условии, так делать запрещается.
  • При вычитании одной строки из другой меняется только та строка, от которой отнимают. Аналогично и со сложением: меняется та строка, к которой прибавляют.
  • Если в ходе преобразований мы получаем нулевую строку (все коэффициенты и свободный член будут равны 0), то такую строку можно убрать.

Примеры решений

Пример 1. Решить систему уравнений методом Гаусса:$$\begin{equation}\left\{\begin{aligned}
3x_1-2x_2-5x_3+x_4=3,\\
2x_1-3x_2+x_3+5x_4=-3,\\
x_1+2x_2-4x_4=-3,\\
x_1-x_2-4x_3+9x_4=22.\end{aligned}\right.
\end{equation}$$

Запишем матрицу из коэффициентов системы уравнений и преобразуем (если переменной нет в уравнении, то коэффициент равен нулю) $$\left(\left.\begin{array}{rrrr}3 & -2 & -5 & 1 \\
2 & -3 & 1 & 5 \\
1 & 2 & 0 & -4 \\
1 & -1 & -4 & 9\end{array}\right|\begin{array}{r}3 \\ -3 \\ -3 \\ 22 \end{array}\right).$$ Поменяем местами первое уравнение с последним для удобства вычислений: $$\left(\left.\begin{array}{rrrr}1 & -1 & -4 & 9\\
2 & -3 & 1 & 5 \\
1 & 2 & 0 & -4\\
3 & -2 & -5 & 1 \end{array}\right|\begin{array}{r}22 \\ -3 \\ -3 \\ 3 \end{array}\right).$$ Умножим теперь первое уравнение на 2 и вычтем из второго уравнения. Затем, умножив на 1, вычтем из третьего. И умножив на 3, вычтем из четвертого. Получаем: $$\left(\left.\begin{array}{rrrr}1 & -1 & -4 & 9 \\
0 & -1 & 9 & -13 \\
0 & 3 & 4 & -13 \\
0 & 1 & 7 & -26\end{array}\right|\begin{array}{r}22 \\ -47 \\ -25 \\ -63 \end{array}\right).$$ Далее умножаем второе уравнение на -3, затем вычтем из третьего. Теперь второе уравнение умножаем на -1 из четвертого: $$\left(\left.\begin{array}{rrrr}1 & -1 & -4 & 9 \\
0 & -1 & 9 & -13 \\
0 & 0 & 31 & -52 \\
0 & 0 & 16 & -39\end{array}\right|\begin{array}{r}22 \\ -47 \\ -166 \\ -110 \end{array}\right).$$ Итак, последние действия прямого хода. Умножаем третье уравнение на $-\frac{16}{31}$ и вычитаем из четвертого. Получаем:$$\left(\left.\begin{array}{rrrr}1 & -1 & -4 & 9 \\
0 & -1 & 9 & -13 \\
0 & 0 & 31 & -52 \\
0 & 0 & 0 & -\frac{377}{31}\end{array}\right|\begin{array}{r}22 \\ -47 \\ -166 \\ -\frac{754}{31} \end{array}\right).$$ Получаем систему уравнений с новыми коэффициентами, которую будем решать обратным ходом: $$\begin{equation}\left\{
\begin{aligned}
x_1-x_2-4x_3+9x_4=22,\\
-x_2+9x_3-13x_4=-47,\\
31x_3-52x_4=-166,\\
-\frac{377}{31}x_4=-\frac{754}{31}.
\end{aligned}\right.
\end{equation}$$ Решение получается одно. Находим его: $$x_4=2,\\
x_3=\frac{-166+104}{31}=-2,\\
x_2=-(-47+18+26)=3,\\
x_1=22+3-8-18=-1.$$

Пример 2. Решить систему уравнений методом Гаусса:$$\begin{equation}\left\{
\begin{aligned}
4x_1-3x_2+x_3+5x_4-7=0,\\
x_1-2x_2-2x_3-3x_4-3=0,\\
3x_1-x_2+2x_3+1=0,\\
2x_1+3x_2+2x_3-8x_4+7=0.
\end{aligned}\right.
\end{equation}$$

Решение

Сначала перенесем все свободные члены вправо и выпишем расширенную матрицу. Преобразуем её: $$\left(\left.\begin{array}{rrrr}4 & -3 & 1 & 5\\
1 & -2 &-2 & -3\\
3 & -1 & 2 & 0\\
2 & 3 & 2 & -8\end{array}\right|\begin{array}{r}7\\3\\-1\\-7\end{array}\right).$$ Поменяем местами первую строку со второй: $$\left(\left.\begin{array}{rrrr}1 & -2 &-2 & -3\\
4 & -3 & 1 & 5\\
3 & -1 & 2 & 0\\
2 & 3 & 2 & -8\end{array}\right|\begin{array}{r}3\\7\\-1\\-7\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & -2 &-2 & -3\\
0 & 5 & 9 & 17\\
0 & 5 & 8 & 9\\
0 & 7 & 6 & -2\end{array}\right|\begin{array}{r}3\\-5\\-10\\-13\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & -2 &-2 & -3\\
0 & 5 & 9 & 17\\
0 & 0 & -1 & -8\\
0 & 0 & -\frac{33}{5} & -\frac{129}{5}\end{array}\right|\begin{array}{r}3\\-5\\-5\\20\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & -2 &-2 & -3\\
0 & 5 & 9 & 17\\0
& 0 & -1 & -8\\
0 & 0 & 0 & 27\end{array}\right|\begin{array}{r}3\\-5\\-5\\27\end{array}\right).$$ Получаем ответ: $$x_4=1,$$ $$x_3=-3,$$ $$x_2=1,$$ $$x_1=2.$$

[свернуть]

Пример 3. Решить систему уравнений методом Гаусса: $$\begin{equation}\left\{
\begin{aligned}
3x_1-7x_2+4x_3+5x_4=-11,\\
2x_1+5x_2+x_3-2x_4=5,\\
x_1+2x_2-3x_3+4x_4=7,\\
7x_1+2x_2-x_3+11x_4=6.
\end{aligned}\right.
\end{equation}$$

Решение

Записываем матрицу системы и преобразуем её: $$\left(\left
.\begin{array}{rrrr}3 & -7 & 4 & 5\\
2 & 5 & 1 & -2\\
1 & 2 & -3 & 4\\
7 & 2 & -1 & 11\end{array}\right|\begin{array}{r}-11\\5\\7\\6\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 4\\
2 & 5 & 1 & -2\\
3 & -7 & 4 & 5\\
7 & 2 & -1 & 11\end{array}\right|\begin{array}{r}7\\5\\-11\\6\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 4\\
0 & 1 & 7 & -10\\
0 & -13 & 13 &-7\\
0 & -12 & 20 & -17\end{array}\right|\begin{array}{r}7\\-9\\-32\\-43\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 4\\0 & 1 & 7 & -10\\
0 & 0 & 104 & -137\\
0 & 0 & 104 & -137\end{array}\right|\begin{array}{r}7\\-9\\-149\\-151\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 4\\
0 & 1 & 7 & -10\\
0 & 0 & 104 & -137\\
0 & 0 & 0 & 0\end{array}\right|\begin{array}{r}7\\-9\\-149\\-2\end{array}\right).$$ Видим, что у нас получилось уравнение с нулевыми коэффициентами при ненулевом свободном члене, значит тут мы можем уже остановиться — система несовместна, то есть решений не имеет.

[свернуть]

Пример 4. Решите систему уравнений методом Гаусса: $$\begin{equation}\left\{\begin{aligned}7x_1+3x_2-2x_3+4x_4=0,\\
-6x_1-x_2-x_3+x_4=1,\\
9x_1+7x_2-8x_3+14x_4=2,\\
x_1+2x_2-3x_3+5x_4=1.\end{aligned}\right.\end{equation}$$

Решение

Записываем матрицу системы уравнений и преобразуем: $$\left(\left.\begin{array}{rrrr}7 & 3 & -2 & 4\\
-6 & -1 & -1 &1 \\
9 & 7 & 8 & 14 \\
1 & 2 & -3 & 5\end{array}\right|\begin{array}{r}0\\1\\2\\1\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 5\\
-6 & -1 & -1 &1 \\
9 & 7 & 8 & 14 \\
7 & 3 & -2 & 4\end{array}\right|\begin{array}{r}1\\1\\2\\0\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 5\\
0 & 11 & -19 & 31\\
0 & -11 & 35 & -31\\
0 & -11 & 19 &-31\end{array}\right|\begin{array}{r}1\\7\\-7\\-7\end{array}\right)\sim~$$$$\sim~\left(\left.\begin{array}{rrrr}1 & 2 & -3 & 5\\
0 & 11 & -19 & 31\\
0 & 0 & 16 & 0\\
0 & 0 & 0 & 0\end{array}\right|\begin{array}{r}1\\7\\0\\0\end{array}\right)$$ Видим, что у нас появилась нулевая строка. Это значит, что это уравнение можно убрать. Так как мы получили систему, в которой количество уравнений меньше, чем количество переменных, значит система неопределённая, то есть имеет бесконечное множество решений. Количество зависимых переменных определяем по рангу матрицы. У нас получается 3 зависимых переменных. Возьмем $x_4$ за свободную переменную. Выражаем остальные 3 переменные через свободную и получаем общее решение: $$x_3=0$$ $$x_2=\frac{7-31x_4}{11}$$ $$x_1=1-2\times\frac{7-31x_4}{11}-5x_4.$$ Теперь можем подставить любое значение в переменную $x_4$ и получить один из бесконечного множества ответов, например: $$x_4=0,$$ $$x_3=0,$$ $$x_2=\frac{7}{11},$$ $$x_1=-\frac{3}{11}.$$

[свернуть]

Пример 5. Решить систему уравнений методом Гаусса: $$\begin{equation}\left\{
\begin{aligned}
2x_1-x_2+2x_4=0,\\
x_1+2x_2-x_3=0,\\
5x_1+x_2-x_3+2x_4=0,\\
x_1+x_2+x_3+x_4=1.
\end{aligned}\right.
\end{equation}$$

Решение

Запишем матрицу системы: $$\left(\left.\begin{array}{rrrr}2 & -1 &0 &2\\
1 & 2 &-1 & 0\\
5 & 1 &-1 & 2\\
1 & 1 & 1 & 1\end{array}\right|\begin{array}{r}0\\0\\0\\1\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 1 & 1 & 1\\
1 & 2 & -1 & 0\\
5 & 1 & -1 & 2\\
2 & -1 & 0 & 2\end{array}\right|\begin{array}{r}1\\0\\0\\0\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 1 & 1 &1\\
0 & 1 & -2 & -1\\
0 & -4 & -6 & -3\\
0 & -3 & -2 & 0\end{array}\right|\begin{array}{r}1\\-1\\-5\\-2\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 1 & 1 & 1\\
0 & 1 & -2 & -1\\
0 & 0 & -14 & -7\\
0 & 0 & -8 & -3\end{array}\right|\begin{array}{r}1\\-1\\-9\\-5\end{array}\right)\sim~$$ $$\sim~\left(\left.\begin{array}{rrrr}1 & 1 & 1 & 1\\
0 & 1 & -2 & -1\\
0 & 0 & -14 & -7\\
0 & 0 & 0 & 1\end{array}\right|\begin{array}{r}1\\-1\\-9\\\frac{1}{7}\end{array}\right).$$ Получаем ответ: $$x_4=\frac{1}{7},$$ $$x_3=\frac{4}{7},$$ $$x_2=\frac{2}{7},$$ $$x_1=0.$$

[свернуть]

Смотрите также

Метод Гаусса

Пройдите тест, чтобы проверить насколько точно вы поняли материал.

М13. Разность и сумма модулей

Задача из журнала «Квант» (1970 год, 11 выпуск)

Условие

Докажите, что если разность между наибольшим и наименьшим из $n$ вещественных чисел $a_1, a_2, \ldots, a_n$ равна $d$, а сумма модулей всех $\frac{n(n-1)}{2}$ попарных разностей этих чисел $\sum\limits_{i<j}|a_i — a_j|$ равна $s$, то $(n-1)$ $d\leqslant s\leqslant \frac{n^2}{4}d$.

Решение

рисунок
Нанесем точки $a_1, a_2, \ldots, a_n$ на числовую ось. Тогда $d$ — расстояние между крайними из этих точек, самой левой и самой правой, а $\sum\limits_{i<j}|a_i — a_j|$ — сумма всех попарных расстояний между этими точками. Можно, очевидно, считать, что точки обозначены через $a_1, a_2, \ldots, a_n$ в порядке возрастания: $a_1 \leqslant a_2\leqslant \ldots \leqslant a_n$ (рисунок). Обозначим расстояние между соседними точками $a_k$ и $a_{k+1}$ через $d_k(k=1, 2, \ldots, n-1)$. Очевидно, $$d=d_1+d_2 \ldots +d_{n-1}.$$ Выразим теперь $s$ через величины $d_k$. Для этого заменим в сумме $s$ длину каждого отрезка $|a_i-a_j|$ суммой тех $d_k$, из которых он состоит: $|a_i-a_j|=d_i+d_{i+1}+\ldots+d_{j-1}$. Ясно, что $d_k$ входит в те отрезки, у которых левый конец лежит в одной из точек $a_1,\ldots, a_k$, а правый — в одной из точек $a_{k+1}, \ldots a_n$, то есть в общей сложности $d_k$ входит в сумму $k(n-k)$ раз. Поэтому $$s=\sum\limits_{k=1}^{n-1}k(n-k)d_k.$$ Теперь доказываемое утверждение следует из двух совсем простых неравенств: для всех $k=1, \ldots, n-1$

  1. $k(n-k)\geqslant n-1\Leftrightarrow kn-k^2-n+1\geqslant 0 \Leftrightarrow (k-1)(n-k-1)\geqslant 0$
  2. $k(n-k)\leqslant\frac{n^2}{4}\Leftrightarrow n^2-4nk+4k^2\geqslant 0 \Leftrightarrow\left(n-2k\right)^2$

Пользуясь этими оценками $$\sum\limits_{k=1}^{n-1}k(n-k)d_k\geqslant \sum\limits_{k=1}^{n-1}(n-1)d_k=(n-1)d,$$ $$\sum\limits_{k=1}^{n-1}k(n-k)d_k\leqslant\sum\limits_{k=1}^{n-1}\frac{n^2}{4}d_k=\frac{n^2}{4}d.$$

Интересно выяснить

Являются ли указанные в условии задачи оценки точными, нельзя ли, скажем, вместо $n-1$ поставить в левом неравенстве большее число? Для того, чтобы убедиться в противном, достаточно привести пример такого случая, когда неравенство превращается в равенство (причем в обеих его частях стоят положительные числа). Такой пример легко придумать, разобравшись в нашем доказательстве: нужно расположить точки $a_1, a_2, \ldots, a_n$ так, чтобы все $d_k$, кроме первого — $d_1$, равнялись нулю, то есть взять $a_1 < a_2 = a_3 = \ldots = a_n$. Тогда $s = (n-1)d_1 = (n-1)d$.

Что касается второго неравенства $s\leqslant \frac{n^2}{4} d$, то при четном $n = 2m$ в нем тоже может достигаться равенство (достаточно взять $a_1 = a_2 = \ldots = a_m \lt a_{m+1} = \ldots = a_2m)$, а при нечетном $n = 2m + 1$ его можно несколько уточнить: нетрудно сообразить, что при нечетном $n$ наибольшее из чисел $k(n-k)$ равно $\frac{n-1}{2} \times \frac{n+1}{2} = \frac{n^2-1}{4}$; пользуясь этим вместо неравенства б), можно так же, как и выше, доказать более сильное неравенство $s \lt \frac{n^2-1}{4}d$. Равенство в нем достигается, когда $a_1 = \ldots = a_m \lt a_{m+1} = \ldots = a_{2m+1}$.

М1773. О равенстве четырехугольника и треугольника

Задача из журнала «Квант» (2001 год, 3 выпуск)

Условие

Высота $CD$ и биссектриса $AE$ прямоугольного треугольника $ABC (\angle C = 90 ^{\circ} )$ пересекаются в точке $F$ (см. рисунок). Пусть $G$ — точка пересечения прямых $ED$ и $BF$. Докажите, что площади четырехугольника $CEGF$ и треугольника $BDG$ равны.

Решение

Так как $AE$ — биссектриса $\triangle ABC$, а $AF$ — биссектриса $\triangle ADC$, $$\frac {EC}{BE} = \frac {AC}{AB} = \cos \angle BAC = \frac {DA}{AC} = \frac {DF}{FC},$$ $$EC \times FC = BE \times DF = (BC — EC) \times (CD — CF),$$ $$ BC \times CD = BC \times CF + EC \times CD. $$ Умножив обе части последнего равенства на $ \frac {1}{2} \sin \angle BCD$, получим, что $$ S_{BCD} = S_{BCF} + S_{ECD}. $$ Но $$ S_{BCD} = S_{CEGF} + S_{BEG} + S_{BGD} + S_{DFG},$$ $$ S_{BCF} = S_{GECF}+S_{BEG}, S_{ECD} = S_{GECF} + S_{DFG}, $$ откуда и следует требуемое равенство.

И. Жук