2 Алгоритм гаусса и трёхдиагональные матрицы

Алгоритм Гаусса – это алгоритм решения СЛУ, не требующий предварительной проверки системы на совместность и равенства числа неизвестных числу уравнений. При этом к результату приводит сравнительно небольшое число операций [3]. Важно рассмотреть его в работе, так как алгоритм Григорьева – это тропический аналог алгоритма Гаусса. Подробное рассмотрение будет излишним, для исследования интересны только идеи.

2.1 Метод Гаусса-Жордана

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

Система может быть преобразована двумя способами: строка может быть заменена своей линейной комбинацией с другой строкой и порядок строк можно менять.

Пусть дана система (2.1)

(2.1)

На i-ой итерации алгоритма i-ая переменная исключается из всех строк, кроме строки с номером i. Под исключением подразумевается процесс последовательной замены строк их линейными комбинациями с i-ой строкой. Таким образом, матрица приводится к диагональному виду, строки делятся на константу так, чтобы левая часть стала единичной матрицей, а в правой (для расширенной матрицы) стояли значения, а значит, мы получаем уравнения вида .

2.2 Алгоритм Гаусса

Для ускорения описанного в подразделе 2.1 метода существует алгоритм Гаусса [8][9]. Он разделяется на две части, называемые прямым и обратным ходом.

Вместо диагонального вида матрица приводится к треугольному. Треугольная матрица – матрица, в которой все элементы, лежащие строго ниже главной диагонали или строго выше неё, равны нулю. В первом случае речь идёт о верхне-треугольной матрице, а во втором – о нижне-треугольной.

Прямой ход – процесс приведения матрицы к верхне-треугольной матрице путём последовательного исключения переменных из строк, следующих за рассматриваемой. Это схоже с методом Гаусса-Жордана, только переменная исключается не из всех уравнений системы, кроме рассматриваемого, а из последующих. Под исключением также понимается обнуление коэффициентов последующих строк с помощью линейных комбинаций с рассматриваемой, которая делится на свой ведущий элемент (первый ненулевой коэффициент).

Обратный ход – процесс последовательного получения значений переменных из приведенной к треугольному виду СЛУ. Нахождение решения выполняется от последнего уравнения к первому путём подстановки уже известных значений.

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

2.3 Схема выбора главного элемента

В пункте 2.2 мы говорили о том, что матрица должна прийти к треугольному виду. Но деление на первый ненулевой элемент может привести к накоплению погрешности.

Для её уменьшения используется схема с выбором главного элемента. [8][9] На -ой итерации путём перестановок строк и столбцов нужно добиваться выполнения условия

, при , , ; ,  , ,

где – это коэффициент из уравнения в системе из формулы 2.1, а его индекс  показывает итерацию алгоритма, а так же номер рассматриваемой строки. Элемент – это -ый главный элемент. При этом на каждой итерации рассматривается подматрица со столбцами и строками . Иначе говоря, рассмотренные строки уже не поменяют своё расположение.

Делим -ую строку (а она изменилась из-за переупорядочивания) на её главный элемент. Исключаем из последующих уравнений.

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