Метод Гаусса

Рассмотрим систему линейных алгебраических уравнений

. (3.1)

Будем предполагать, что определитель матрицы А отличен от нуля. Метод Гаусса основан на приведении матрицы А к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы. Сначала с помощью первого уравнения исключается x₁ из всех последующих уравнений системы. Затем с помощью второго уравнения исключается x₂ из третьего и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса, продолжается до тех пор, пока в левой части последнего (п -го) уравнения не останется лишь один член с неизвестным x_п, т.е. матрица системы будет приведена к треугольному виду.

Обратный ход метода Гаусса состоит в последовательном вычислении искомых неизвестных, т.е. решая последнее уравнение, находим значение x_п; далее, используя это значение, из предыдущего уравнения вычисляем x_п-1 и т.д. Последним найдем x₁ из первого уравнения.

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

(3.2)

где - коэффициенты первой строки матрицы А; - коэффициент i -го уравнения при j переменной, полученный в результате преобразований системы на т –м шаге. Предположим, что в к - ом уравнении коэффициент . Умножим к -ое уравнение системы на и вычтем полученное соотношение из i -го уравнения системы (3.2), где .

В результате последняя группа уравнений системы (3.2) примет вид:

где

(3.3)

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

Обратный ход, как уже указывалось, заключается в вычислении неизвестных . Последнее уравнение будет иметь вид

.

Откуда

.

Общая формула обратного хода для вычисления переменной x_к, имеет вид

.

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

Пусть на к - ом шаге имеем систему (З.2). Сначала добиваемся выполнения условия

,

путем перестановки двух уравнений системы (3.2), а также двух столбцов неизвестных со своими коэффициентами и соответствующей перенумерацией коэффициентов и неизвестных. При этом если переставляются столбцы, то соответствующая перестановка и перенумерация производятся и в уравнениях, которые на к - ом шаге не преобразуются, т.е. при .

Найденный максимальный по модулю элемент (если , то этот главный элемент всегда отличен от нуля) называется к - м главным элементом. Затем осуществляются преобразования к - го шага по формулам (3.3).

В большинстве существующих стандартных программ одновременно с решением системы линейных алгебраических уравнений (3.1) вычисляется определитель матрицы А. Определитель полученной в результате прямого хода треугольной матрицы равен произведению её диагональных элементов и отличается от определителя лишь знаком, поскольку в процессе преобразований осуществлялась перестановка строк в столбцов. Поэтому

,

где S - суммарное число перестановок строк и столбцов.

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

Метод Гаусса используется также для вычисления обратной матрицы. Пусть матрица А^-1 с элементами x_ij является обратной к матрице А. Тогда имеем матричное уравнение

,

где Е - единичная матрица. Отсюда каждый j – й столбец матрицы А^-1 удовлетворяет уравнению

(3.4)

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

Как уже указывалось выше, решение системы (З.1), полученное методом Гаусса, может быть искажено вычислительной погрешностью, являющейся следствием округлений при вычислениях. Рассмотрим способ уточнения решения.

Пусть найдено решение . Определим для него вектор невязок

. (3.5)

Обозначив вектор уточнений и вычтя из (З.1) уравнение (3.5), получим, что удовлетворяет системе

. (3.6)

Решим эту систему и положим . Если точность нового приближения представляется неудовлетворительной, то повторяем эту операцию. При решении системы (3.6) над компонентами правой части производятся те же линейные операции, что и над компонентами правой части при решении системы (3.1). Поэтому при вычислениях на машине с плавающей запятой естественно ожидать, что относительные погрешности решений этих систем будут одинаковы. Поскольку погрешности округлений обычно малы, . Тогда, и, по-видимому, решение системы (3.6) определяется с существенно меньшей абсолютной погрешностью, чем решение системы (3.1). Таким образом, применение описанного приема приводит к повышению точности приближенного решения.

Дата добавления: 2014-12-25