Метод Гаусса

Метод Гаусса: описание алгоритма решения системы линейных уравнений, примеры, решения.

Метод Гаусса прекрасно подходит для решения систем линейных алгебраических уравнений (СЛАУ). Он обладает рядом преимуществ по сравнению с другими методами:

• во-первых, нет необходимости предварительно исследовать систему уравнений на совместность;

• во-вторых, методом Гаусса можно решать не только СЛАУ, в которых число уравнений совпадает с количеством неизвестных переменных и основная матрица системы невырожденная, но и системы уравнений, в которых число уравнений не совпадает с количеством неизвестных переменных или определитель основной матрицы равен нулю;

• в-третьих, метод Гаусса приводит к результату при сравнительно небольшом количестве вычислительных операций.

Краткий обзор статьи.

Сначала дадим необходимые определения и введем обозначения.

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

В заключении рассмотрим решение методом Гаусса систем линейных алгебраических уравнений, основная матрица которых либо прямоугольная, либо вырожденная. Решение таких систем имеет некоторые особенности, которые мы подробно разберем на примерах.

Навигация по странице.

• Основные определения и обозначения.

• Решение систем линейных алгебраических уравнений, в которых число уравнений равно числу неизвестных и основная матрица системы невырожденная, методом Гаусса.

• Решение систем линейных алгебраических уравнений, в которых число уравнений не совпадает с числом неизвестных или основная матрица системы вырожденная, методом Гаусса.

Основные определения и обозначения.

Рассмотрим систему из p линейных уравнений с n неизвестными (p может быть равно n): 
 
где   - неизвестные переменные,   - числа (действительные или комплексные),   - свободные члены.

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

Совокупность значения неизвестных переменных  , при которых все уравнения системы обращаются в тождества, называется решением СЛАУ.

Если существует хотя бы одно решение системы линейных алгебраических уравнений, то она называется совместной, в противном случае – несовместной.

Если СЛАУ имеет единственное решение, то она называется определенной. Если решений больше одного, то система называется неопределенной.

Говорят, что система записана в координатной форме, если она имеет вид 
.

Эта система в матричной форме записи имеет вид  , где  - основная матрица СЛАУ,   - матрица столбец неизвестных переменных,   - матрица свободных членов.

Если к матрице А добавить в качестве (n+1)-ого столбца матрицу-столбец свободных членов, то получим так называемую расширенную матрицу системы линейных уравнений. Обычно расширенную матрицу обозначают буквой Т, а столбец свободных членов отделяют вертикальной линией от остальных столбцов, то есть, 

Квадратная матрица А называется вырожденной, если ее определитель равен нулю. Если  , то матрица А называется невырожденной.

Следует оговорить следующий момент.

Если с системой линейных алгебраических уравнений  произвести следующие действия

• поменять местами два уравнения,

• умножить обе части какого-либо уравнения на произвольное и отличное от нуля действительное (или комплексное) число k,

• к обеим частям какого-либо уравнения прибавить соответствующие части другого уравнения, умноженные на произвольное число k,

то получится эквивалентная система, которая имеет такие же решения (или также как и исходная не имеет решений).

Для расширенной матрицы системы линейных алгебраических уравнений эти действия будут означать проведение элементарных преобразований со строками:

• перестановку двух строк местами,

• умножение всех элементов какой-либо строки матрицы T на отличное от нуля числоk,

• прибавление к элементам какой-либо строки матрицы соответствующих элементов другой строки, умноженных на произвольное число k.

Теперь можно переходить к описанию метода Гаусса.

К началу страницы

Решение систем линейных алгебраических уравнений, в которых число уравнений равно числу неизвестных и основная матрица системы невырожденная, методом Гаусса.

Как бы мы поступили в школе, если бы получили задание найти решение системы уравнений  .

Некоторые сделали бы так.

Заметим, что прибавив к левой части второго уравнения левую часть первого, а к правой части - правую, можно избавиться от неизвестных переменных x2 и x3 и сразу найти x1: 

Подставляем найденное значение x1=1 в первое и третье уравнение системы: 

Если умножить обе части третьего уравнения системы на -1 и прибавить их к соответствующим частям первого уравнения, то мы избавимся от неизвестной переменной x3 и сможем найти x2: 

Подставляем полученное значение x2=2 в третье уравнение и находим оставшуюся неизвестную переменную x3: 

Другие поступили бы иначе.

Разрешим первое уравнение системы относительно неизвестной переменной x1 и подставим полученное выражение во второе и третье уравнение системы, чтобы исключить из них эту переменную: 

Теперь разрешим второе уравнение системы относительно x2 и подставим полученный результат в третье уравнение, чтобы исключить из него неизвестную переменную x2: 

Из третьего уравнения системы видно, что x3=3. Из второго уравнения находим  , а из первого уравнения получаем  .

Знакомые способы решения, не правда ли?

Самое интересное здесь то, что второй способ решения по сути и есть метод последовательного исключения неизвестных, то есть, метод Гаусса. Когда мы выражали неизвестные переменные (сначала x1, на следующем этапе x2) и подставляли их в остальные уравнения системы, мы тем самым исключали их. Исключение мы проводили до того момента, пока в последнем уравнении не осталась одна единственная неизвестная переменная. Процесс последовательного исключения неизвестных называется прямым ходом метода Гаусса. После завершения прямого хода у нас появляется возможность вычислить неизвестную переменную, находящуюся в последнем уравнении. С ее помощью из предпоследнего уравнения находим следующую неизвестную переменную и так далее. Процесс последовательного нахождения неизвестных переменных при движении от последнего уравнения к первому называется обратным ходом метода Гаусса.

Следует заметить, что когда мы выражаем x1 через x2 и x3 в первом уравнении, а затем подставляем полученное выражение во второе и третье уравнения, то к такому же результату приводят следующие действия:

• к левой и правой частям второго уравнения прибавляем соответствующие части первого уравнения, умноженные на  ,

• к левой и правой частям третьего уравнения прибавляем соответствующие части первого уравнения, умноженные на  .

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

Нюансы с исключением неизвестных переменных по методу Гаусса возникают тогда, когда уравнения системы не содержат некоторых переменных.

Например, в СЛАУ   в первом уравнении отсутствует неизвестная переменная x1 (иными словами, коэффициент перед ней равен нулю). Поэтому мы не можем разрешить первое уравнение системы относительно x1, чтобы исключить эту неизвестную переменную из остальных уравнений. Выходом из этой ситуации является перестановка местами уравнений системы. Так как мы рассматриваем системы линейных уравнений, определители основных матриц которых отличны от нуля, то всегда существует уравнение, в котором присутствует нужная нам переменная, и мы это уравнение можем переставить на нужную нам позицию. Для нашего примера достаточно поменять местами первое и второе уравнения системы  , дальше можно разрешить первое уравнение относительно x1 и исключить ее из остальных уравнений системы (хотя во втором уравнении x1 уже отсутствует).

Надеемся, что суть Вы уловили.

Опишем алгоритм метода Гаусса.

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

Будем считать, что  , так как мы всегда можем этого добиться перестановкой местами уравнений системы. Исключим неизвестную переменную x1 из всех уравнений системы, начиная со второго. Для этого ко второму уравнению системы прибавим первое, умноженное на  , к третьему уравнению прибавим первое, умноженное на  , и так далее, к n-ому уравнению прибавим первое, умноженное на  . Система уравнений после таких преобразований примет вид 
  
где  , а  .

К такому же результату мы бы пришли, если бы выразили x1 через другие неизвестные переменные в первом уравнении системы и полученное выражение подставили во все остальные уравнения. Таким образом, переменная x1 исключена из всех уравнений, начиная со второго.

Далее действуем аналогично, но лишь с частью полученной системы, которая отмечена на рисунке 

Будем считать, что   (в противном случае мы переставим местами вторую строку с k-ой, где  ). Приступаем к исключению неизвестной переменной x2 из всех уравнений, начиная с третьего.

Для этого к третьему уравнению системы прибавим второе, умноженное на  , к четвертому уравнению прибавим второе, умноженное на  , и так далее, к n-ому уравнению прибавим второе, умноженное на  . Система уравнений после таких преобразований примет вид 
 
где  , а  . Таким образом, переменная x2 исключена из всех уравнений, начиная с третьего.

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

Так продолжаем прямой ход метода Гаусса пока система не примет вид 

С этого момента начинаем обратный ход метода Гаусса: вычисляем xn из последнего уравнения как  , с помощью полученного значения xn находим xn-1 из предпоследнего уравнения, и так далее, находим x1 из первого уравнения.

Разберем алгоритм на примере.