Метод Гаусса

Определение метода Гаусса

Пусть дана система
,  ∆≠0.           (1)
Метод Гаусса
– это метод последовательного исключения неизвестных
Как решать методом Гаусса

Суть метода Гаусса состоит в преобразовании (1) к системе с треугольной матрицей, из которой затем последовательно (обратным ходом) получаются значения всех неизвестных. Рассмотрим одну из вычислительных схем. Эта схема называется схемой единственного деления. Итак, рассмотрим эту схему. Пусть a11≠0 (ведущий элемент) разделим на a11 первое уравнение. Получим
              (2)
Пользуясь уравнением (2), легко исключить неизвестные x1 из остальных уравнений системы (для этого достаточно из каждого уравнения вычесть уравнение (2) предварительно умноженное на соответствующий коэффициент при x1), то есть на первом шаге получим
формула Гаусса.
Иными словами, на 1 шаге каждый элемент последующих строк, начиная со второй, равен разности между исходным элементом и произведением его «проекции» на первый столбец и первую (преобразованную) строку.
Вслед за этим оставив первое уравнение в покое, над остальными уравнениями системы, полученной на первом шаге, совершим аналогичное преобразование: выберем из их числа уравнение с ведущим элементом и исключим с его помощью из остальных уравнений x2 (шаг 2).
После n шагов вместо (1) получим равносильную систему
              (3)
Таким образом, на первом этапе мы получим треугольную систему (3). Этот этап называется прямым ходом.
На втором этапе (обратный ход) мы находим последовательно из (3) значения xn , xn-1, …, x1.
Обозначим полученное решение за x0. Тогда разность

называется невязкой.
Если ε=0, то найденное решение x0 является верным.

Вычисления по методу Гаусса выполняются в два этапа:

  1. Первый этап называется прямым ходом метода. На первом этапе исходную систему преобразуют к треугольному виду.
  2. Второй этап называется обратным ходом. На втором этапе решают треугольную систему, эквивалентную исходной.
Коэффициенты а11, а22, …, называют ведущими элементами.
На каждом шаге предполагалось, что ведущий элемент отличен от нуля. Если это не так, то в качестве ведущего можно использовать любой другой элемент, как бы переставив уравнения системы.

Назначение метода Гаусса

Метод Гаусса предназначен для решения систем линейных уравнений. Относится к прямым методам решения.

Виды метода Гаусса

  1. Классический метод Гаусса;
  2. Модификации метода Гаусса. Одной из модификаций метода Гаусса является схема с выбором главного элемента. Особенностью метода Гаусса с выбором главного элемента является такая перестановка уравнений, чтобы на k-ом шаге ведущим элементом оказывался наибольший по модулю элемент k-го столбца.
  3. Метод Жордано-Гаусса;
Отличие метода Жордано-Гаусса от классического метода Гаусса состоит в применении правила прямоугольника, когда направление поиска решения происходит по главной диагонали (преобразование к единичной матрице). В методе Гаусса направление поиска решения происходит по столбцам (преобразование к системе с треугольной матрицей).
Проиллюстрируем отличие метода Жордано-Гаусса от метода Гаусса на примерах.

Пример решения методом Гаусса
Решим систему:

Для удобства вычислений поменяем строки местами:

Умножим 2-ую строку на (2). Добавим 3-ую строку к 2-ой

Умножим 2-ую строку на (-1). Добавим 2-ую строку к 1-ой

Из 1-ой строки выражаем x3

Из 2-ой строки выражаем x2

Из 3-ой строки выражаем x1

Пример решения методом Жордано-Гаусса
Эту же СЛАУ решим методом Жордано-Гаусса.

Последовательно будем выбирать разрешающий элемент РЭ, который лежит на главной диагонали матрицы.
Разрешающий элемент равен (1).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
РЭ - разрешающий элемент (1), А и В - элементы матрицы, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

x1

x2

x3

B

1 / 1 = 1

2 / 1 = 2

-2 / 1 = -2

1 / 1 = 1



Разрешающий элемент равен (3).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Представим расчет каждого элемента в виде таблицы:

x1

x2

x3

B

0 / 3 = 0

3 / 3 = 1

1 / 3 = 0.33

4 / 3 = 1.33





Разрешающий элемент равен (-4).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Представим расчет каждого элемента в виде таблицы:

x1

x2

x3

B

0 / -4 = 0

0 / -4 = 0

-4 / -4 = 1

-4 / -4 = 1

Ответ:
x1 = 1
x2 = 1
x3 = 1

ПоказательМетод ГауссаМетод Жордано-Гаусса
Вид матрицыТреугольная матрицаЕдиничная матрица
Время решения0.0310.022
Объем используемой памяти, байт56473277

Реализация метода Гаусса

Метод Гаусса реализован на многих языках программирования, в частности: Pascal, C++, php, Delphi, а также имеется реализация метода Гаусса в онлайн режиме.

Использование метода Гаусса

Применение метода Гаусса в теории игр

В теории игр при отыскании максиминной оптимальной стратегии игрока составляется система уравнений, которая решается методом Гаусса.

Применение метода Гаусса при решении дифференциальных уравнений

Для поиска частного решения дифференциального уравнения сначала находят производные соответствующей степени для записанного частного решения (y=f(A,B,C,D)), которые подставляют в исходное уравнение. Далее, чтобы найти переменные A,B,C,D составляется система уравнений, которая решается методом Гаусса.

Применение метода Жордано-Гаусса в линейном программировании

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