В предыдущих статьях мы уже говорили о СЛАУ, какими они бывают и о некоторых методах решения СЛАУ. Среди упомянутых алгоритмов был метод Крамера, про который мы писали в прошлой статье и метод Гаусса, про который мы поговорим сегодня.
Поговорим о методе
Метод Гаусса является одним из самых популярных прямых методов решения СЛАУ. Он является основой для многих других методов, связанных с решением СЛАУ. Назван метод в честь Карла Фридриха Гаусса — великого немецкого математика, с которым связанно большое множество фундаментальных исследований в разных областях математики.
Стоит отметить, что метод Гаусса ещё называют методом последовательного исключения неизвестных, поскольку в ходе алгоритма с каждым уравнением "убирается" одна неизвестная и в конце первого этапа (а всего их два) исходная прямоугольная СЛАУ преобразуется в треугольную систему уравнений.
Если говорить о вычислительной сложности алгоритма, то она составляет O(n³). Для больших задач данный метод не годится, поскольку занимает много времени, но, стоит отметить, что метод куда эффективнее метода Крамера.
Суть метода Гаусса
Поговорим теперь подробнее о методе решения СЛАУ в общем виде. Пусть имеется прямоугольная система с m уравнений с n неизвестных:
Для того, чтобы решить такую систему методом Гаусса, необходимо понимать, как преобразовывать исходную прямоугольную матрицу к ступенчатому виду.
Метод состоит из двух этапов:
- Прямой ход (приведение расширенной матрицы к ступенчатому виду);
- Обратный ход (нахождение корней СЛАУ, исходя из предыдущих
полученных уравнений).
Итак, представим СЛАУ в виде расширенной матрицы:
Прямой ход
На данном этапе необходимо при помощи элементарных преобразований над строками матрицы, привести её к ступенчатому (треугольному) виду.
Необходимо сделать так, чтобы в первом столбце, за исключением самого первого верхнего элемента, получились нулевые значения. Для этого нужно найти коэффициенты для каждой строчки, при умножении на который, с последствующим сложением с первой строчкой, получилось нулевое значение. После этого похожим образом нужно сделать со вторым столбцом, но начинать нужно уже не с первого элемента, а со второго и так далее по столбцам, пока не получим ступенчатую матрицу. Конечно, написанное с трудом адекватно воспринимается, поэтому весь метод будет сопровождаться картинками.
Итак, покажем на примере, как постепенно будет приводиться матрица к треугольному виду. Сначала умножаем вторую строку на первый элемент в первой строке, делим на первый элемент второй строки и умножаем это всё на -1, после чего умножаем третью строку на первый элемент в первой строке, делим на первый элемент третьей строки, умножаем на -1 и т. д. до конца:
Теперь нужно сложить первую строку со второй и результат оставить на месте второй строки, первую строку с третьей и результат оставить на месте третьей и т. д. Ещё введём обозначение (на картинке оно снизу), чтобы визуально полученная матрица выглядела более симпатично:
Собственно говоря, нужно проделать всё то же самое, но уже начиная со второго столбца, потом с третьего и так до тех пор, пока в последней строке не останется один единственный элемент. Получим следующую матрицу (здесь обозначения опустим, они аналогичны предыдущим):
Вот мы и привели матрицу к треугольному виду (не страшно если не понятно, дальше мы рассмотрим пример со значениями, чтобы точно разобраться в теме). Отсюда ещё видно, что мы постепенно исключали из строк переменные, почему метод и называют методом последовательного исключения неизвестных. Далее следует второй этап — обратный ход.
Обратный ход
На этом этапе находятся корни СЛАУ, причём находятся корни, начиная с последнего: в последней строке легко находится одна единственная неизвестная: свободный член делится на коэффициент перед неизвестной. Потом в предпоследней строке находим следующую неизвестную, подставляя при этом в уравнение предыдущую найденную неизвестную. И так снизу вверх до самого первого уравнения. Представим нашу получившуюся ступенчатую матрицу в виде системы уравнений:
Выражаем неизвестные:
На этом обратный ход заканчивается.
Мы рассмотрели метод Гаусса в общем виде, теперь рассмотрим пример со значениями.
Пример
Возьмём пример, который мы рассматривали, когда говорили о методе Крамера. Пусть имеется система, состоящая из 3-х уравнений, в каждом из которых по 3 неизвестных:
Представим систему в виде расширенной матрицы:
Теперь начинаем приводить эту матрицу к треугольной (прямой ход).
Умножим вторую строку на первый элемент первой строки (5), разделим на первый элемент второй строки (2) и умножим всё на (-1). Так же делаем и с третьей строкой — умножаем третью строку на первый элемент первой строки (5), делим на первый элемент третьей строки (13) и тоже умножаем на (-1):
Для чего мы вообще это делаем? Мы пытаемся сделать так, чтобы в первом столбце все элементы, за исключением первого, были нулевыми, а для этого нужно умножить строки на какой-то коэффициент, чтобы при сложении этой строки с первой строкой в первом элементе получился ноль. Собственно говоря, складываем первую строку со второй и результат записываем во вторую строку, так же делаем и с третьей строкой:
Теперь делаем то же самое, но начиная со второй строки: умножаем третью строку на первый элемент второй строки (-11/2), делим на первый элемент третьей строки (-3) и умножаем на (-1):
Осталось только сложить вторую строчку с третьей и результат записать в третью строку:
Ещё немного упростим систему, умножив вторую строку на (-2) и разделив третью строку на (26):
Мы привели матрицу к треугольному виду, теперь на очереди у нас обратный ход. Представим получившуюся матрицу в виде системы:
Выразим неизвестные, начиная снизу и подставляя полученные значения в следующие уравнения:
Мы нашли корни СЛАУ, на этом и закончился метод Гаусса для решения этого примера.
----------------------------------------------------------------------------------------
На этом статья заканчивается, хочется сказать от себя, что метод удобный, лёгкий (на самом деле, если решить пару примеров самостоятельно, то можно понять насколько метод лёгкий в исполнении), но, несмотря на всю свою лёгкость, при больших данных (много уравнений, неизвестных) наблюдается весьма низкая эффективность метода. Конечно, метод Гаусса куда лучше метода Крамера, но всё равно, для больших СЛАУ лучше использовать итерационные методы, о которых мы поговорим в следующих статьях.
Надеюсь данная статья поможет понять как решаются СЛАУ при помощи метода Гаусса, а также понять все тонкости данного метода.
