Метод Гаусса с выбором главного элемента

При «обычном» применении метода Гаусса на k -том шаге исключается k -тое неизвестное. Это возможно, если коэффициент при k -том неизвестном отличен от нуля. Условием применимости такого метода является неравенство нулю всех угловых миноров матрицы A, то есть , , ,..., . Однако, может оказаться, что система имеет единственное решение, хотя какой-либо из угловых миноров матрицы A равен 0. Кроме того, заранее обычно неизвестно, все ли угловые миноры матрицы A отличны от 0. Отметим также, что если в процессе вычислений встречаются ведущие элементы, которые достаточно малы по сравнению с другими элементами матрицы, то это способствует увеличению погрешностей округлений (при делении на маленькие числа погрешность возрастает).

Избежать указанных недостатков «обычного» метода Гаусса позволяет метод Гаусса с выбором главного элемента.

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

.

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

.

Если определитель системы отличен от нуля, то после -го шага будет получена система вида

.

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

Описанные выше рассуждения называют прямым ходом метода Гаусса.

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

Заметим, что применение метода Гаусса с выбором главного элемента позволяет вычислить определитель матрицы A по формуле

,

где k – число перестановок строк и столбцов на всех шагах приведения матрицы к треугольному виду. Заметим также, что описанный выше алгоритм можно использовать в различных задачах линейной алгебры: при вычислении рангов матриц, при нахождении обратной матрицы и так далее.

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

Дата добавления: 2014-01-14