Вычислительная схема метода Гаусса

В каждом уравнении выделяется ведущий, не равный нулю, элемент, на который производится деление. Пусть в силу расположения уравнений это будет . Делим первое уравнение на :

,

Введем множителей:

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

, .

На втором шаге ведущим элементом выбирается , на него делится вторая строка.

Все остальные элементы преобразуются по формуле:

,

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

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

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

; ; ,

для .

В машинных расчетах в качестве ведущего элемента обычно выбирается максимальный элемент − го столбца с или строки с . Эта строка (или столбец) переставляются на место − ой строки (столбца). Такой выбор обеспечивает минимизацию ошибок округления при расчетах и называется метод Гаусса с выбором главного элемента. Метод Гаусса с выбором главного элемента является хорошо обусловленным алгоритмом. Это означает, что малые изменения в исходных данных такого алгоритма приводят к малым изменениям результатов вычислений. При ручных расчетах элементы матрицы записываются вместе с элементами вектора в расширенную матрицу:

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

	…	i	…	t	…
i	…		…		…
…	…	…	…	…	…
…	…	…	…	…	…
k	…		…		…
…	…	…	…	…	…

Пусть - ведущий элемент, тогда

.

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

Алгоритм исключения неизвестных для решения СЛАУ, рассмотренный выше, известен по крайней мере с 250 года до нашей эры, хотя и носит имя Гаусса.

Алгоритм метода Гаусса эквивалентен факторизации (разложению) исходной матрицы системы на три матрицы: , где -верхняя треугольная матрица, полученная в результате прямого хода метода, - нижняя треугольная матрица и - матрица перестановок, ответственная за перестановки уравнений при прямом ходе алгоритма. Доказывается, что такая факторизация всегда выполнима, а в случае, если - единичная матрица и исходная - нормализованная матрица (, ),то такая факторизация единственна.

На основе метода Гаусса созданы мощные и эффективные библиотеки программ для решения СЛАУ. Эти библиотеки являются приложениями всех современных языков программирования высокого уровня (Visual Fortran, Си) и входят в состав современных математических пакетов программ (Mathlab, Mathcad) и эффективно справляются с решением обычных СЛАУ размером до . Однако основным ограничением использования прямых методов и, в частности, метода Гаусса для решения больших СЛАУ размером и , возникающих в современных научно-технических задачах, является кубическая зависимость числа арифметических операций от размера матрицы, которая приводит для таких задач к нереально большому времени вычислений. Немаловажным являются также и требования прямых методов к объему оперативной памяти, поскольку возникает необходимость одновременно хранить несколько матриц большой размерности. Все это приводит к необходимости разработки и использования для решения больших СЛАУ сходящихся итерационных методов, имеющих квадратичную зависимость числа арифметических операций от размера матрицы и ослабленные требования к оперативной памяти ЭВМ.

В пакете программирования Mathcad [18] с языком интерпретируемого типа метод Гаусса реализован в стандартной подпрограмме-функции , где и соответственно матрица и правая часть СЛАУ. Результат в виде вектора решения присваивается имени функции.