You are here:
  • Increase font size
  • Default font size
  • Decrease font size

FIZMATIK.RU

Физико-математическая наука

Метод последовательного исключения неизвестных (метод Гаусса)


Одним из наиболее распространенных методов решения систем линейных алгебраических уравнений является метод последовательного исключения неизвестных - метод Гаусса. Этот метод основан на некоторых преобразованиях системы линейных уравнений, в результате которых получается система, эквивалентная исходной системе.

Пусть дана система (1) $s$ линейных уравнений с $n$ неизвестными.
\[
\begin{array}{l}
 a_{11} x_1 +a_{12} x_2 +\ldots +a_{1n} x_n =b_1 , \\
 a_{21} x_1 +a_{22} x_2 +\ldots +a_{2n} x_n =b_2 , \\
 \ldots \\
 a_{s1} x_1 +a_{s2} x_2 +\ldots +a_{sn} x_n =b_s . \\
 \end{array}
\]
Положим для определенности, что коэффициент $a_{11} $ не равен нулю (хотя он может оказаться и равным нулю, и тогда необходимо начать описанную ниже процедуру с другого уравнения системы, а именно с уравнения, у которого коэффициент при неизвестной $x_1 $ отличен от нуля). Преобразуем систему (1), исключая неизвестную $x_1 $ из всех уравнений, кроме первого. Для этого обе части первого уравнения умножим на число $a_{21} /a_{11} $ и вычтем из соответствующих частей второго уравнения, затем обе части первого уравнения,
умноженные на число $a_{31} /a_{11} $, вычтем из соответствующих частей третьего уравнения и т. д.

В результате указанных преобразований приходим к системе (2) из $s$ линейных уравнений с $n$ неизвестными.
\[
\begin{array}{l}
 a_{11} x_1 +a_{12} x_2 +\ldots +a_{1n} x_n =b_1 , \\
           a_{22}^{(1)} x_2 +\ldots +a_{2n}^{(1)} x_n =b_2^{(1)} , \\
           \ldots \\
          a_{s2}^{(1)} x_2 +\ldots +a_{sn}^{(1)} x_n =b_s^{(1)} , \\
 \end{array}
\]
где $a_{ij}^{(1)} $ и $b_i^{(1)} $ - новые коэффициенты при неизвестных и новые свободные члены, выражающиеся через коэффициенты и свободные члены исходной системы (1). Система (2) эквивалентна системе (1). Преобразуем теперь систему (2). При этом первое уравнение не будем трогать совсем и будем преобразовывать лишь часть системы (2), состоящую из всех уравнений, кроме первого. Кроме того, мы будем считать, что среди этих уравнений нет таких, у которых все коэффициенты левых частей равны нулю, --- такие уравнения мы отбросили бы, если бы их свободные члены были равны нулю (в противном случае мы уже доказали бы несовместность нашей системы). Итак, среди коэффициентов $a_{ij}^{(1)} $ имеются отличные от нуля; для определенности примем, что $a_{22}^{(1)} \ne 0$. Преобразуем теперь систему (2), вычитая из обеих частей третьего к каждого из следующих уравнений обе части второго уравнения, умноженные соответственно на числа
\[
\frac{a_{32}^{(1)} }{a_{22}^{(1)} },\frac{a_{42}^{(1)} }{a_{22}^{(1)}
},\ldots ,\frac{a_{s2}^{(1)} }{a_{22}^{(1)} }
\]
В результате из этих уравнений, кроме первого и второго, будет исключена неизвестная $x_2 $, и мы придем к следующей системе уравнений, эквивалентной системе (2), а следовательно, и системе (1):
\[
\begin{array}{l}
 a_{11} x_1 +a_{12} x_2 +a_{13} x_3 +\ldots +a_{1n} x_n =b_1 , \\
           a_{22}^{(1)} x_2 +a_{23}^{(1)} x_2 +\ldots +a_{2n}^{(1)} x_n
=b_2^{(1)} , \\
                       a_{33}^{(2)} x_2 +\ldots +a_{3n}^{(2)} x_n =b_3^{(2)}
, \\
                       \ldots \\
                       a_{t3}^{(2)} x_2 +\ldots +a_{tn}^{(2)} x_n =b_t^{(2)}
. \\
 \end{array}
\]
Система содержит теперь $t$ уравнений, причем $t\le s$, так как некоторые уравнения оказались, возможно, отброшенными. В дальнейшем будем подвергать преобразованиям лишь часть полученной системы, содержащую все уравнения, кроме двух первых.

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

1) если мы придем к системе, в которой одно из уравнений имеет отличный от нуля свободный член, а все коэффициенты левой части равны нулю, то исходная система несовместна;

2) либо мы получим следующую совместную систему (3) уравнений, эквивалентную системе (1):
\[
\begin{array}{l}
 a_{11} x_1 +a_{12} x_2 +a_{13} x_3 +\ldots +a_{1n} x_n =b_1 , \\
           a_{22}^{(1)} x_2 +a_{23}^{(1)} x_2 +\ldots +a_{2n}^{(1)} x_n
=b_2^{(1)} , \\
                       a_{33}^{(2)} x_2 +\ldots +a_{3n}^{(2)} x_n =b_3^{(2)}
, \\
                       \ldots \\
                       a_{k3}^{(k-1)} x_k +\ldots +a_{kn}^{(k-1)} x_n
=b_k^{(k-1)} . \\
 \end{array}
\]
Здесь $a_{11} \ne 0,a_{22}^{(1)} \ne 0,a_{33}^{(2)} \ne 0,\ldots ,a_{kk}^{(k-1)} \ne 0$, а верхний индекс, стоящий в скобках, указывает на
номер преобразования, после которого получены эти коэффициенты при неизвестных и новые свободные члены. Отметим также, что $k\le s$ и, очевидно, $k\le n$.

Эта система будет определенной при $k=n$ (число уравнений равно числу неизвестных) и неопределенной при $k<n$ (число уравнений меньше числа неизвестных). Действительно, так как при $k=n$ система (3) имеет вид (4)
\[
\begin{array}{l}
 a_{11} x_1 +a_{12} x_2 +a_{13} x_3 +\ldots +a_{1n} x_n =b_1 , \\
           a_{22}^{(1)} x_2 +a_{23}^{(1)} x_2 +\ldots +a_{2n}^{(1)} x_n
=b_2^{(1)} , \\
                       a_{33}^{(2)} x_2 +\ldots +a_{3n}^{(2)} x_n =b_3^{(2)}
, \\
                       \ldots \\
                                           a_{nn}^{(n-1)} x_n =b_n^{(n-1)} ,
\\
 \end{array}
\]
то из последнего уравнения мы получаем вполне определенное значение неизвестной $x_n $. Подставляя его в предпоследнее уравнение, мы найдем единственное значение для неизвестной $x_{n-1} $.

Подставляя найденные значения $x_n $ и $x_{n-1} $ в третье снизу уравнение системы, найдем значение $x_{n-2} $. Продолжая эту процедуру подстановки найденных значений неизвестных в оставшиеся уравнения, получим, что система (4), а следовательно, и система (1) имеют единственное решение, т. е. являются совместными и определенными (в этом случае также говорят, что система (1) приводится к треугольному виду).

Если же $k<n$, то для "свободных'' неизвестных $x_{k+1} ,\ldots ,x_n  \quad _{ }$мы возьмем произвольные числовые значения, после чего, двигаясь по системе (3) снизу вверх, мы, как и выше, найдем для неизвестных $x_k ,x_{k-1} ,\ldots ,x_2 ,x_1 $, вполне определенные значения. Так как значения свободных неизвестных можно выбирать бесконечным числом различных способов, то система (3), а следовательно, и система (1) будут совместными, но неопределенными. (В этом случае говорят, что система приводится к трапецеидальной форме.)

Итак, метод Гаусса применим к любой системе линейных уравнений. При этом система будет несовместной, если в процессе преобразований мы получим уравнение, в котором коэффициенты при всех неизвестных равны нулю, а свободный член отличен от нуля; если же такого уравнения не встретим, то система будет совместной. Совместная система уравнений будет определенной, если она приводится к треугольному виду (4), и неопределенной, если приводится к трапецеидальному виду (3) при $k<n$.

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

 

Конспекты занятий в детском саду на сайте osadik.ru