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

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

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

Алгоритмически перестановку строк матрицы можно реализовать путем умножения матрицы перестановок на преобразуемую матрицу[†]. Матрицей перестановок называется матрица, в каждой строке и каждом столбце которой содержится только один ненулевой элемент, равный единице, а остальные элементы равны нулю. Частным случает матрицы перестановок является единичная матрица. Элементарной матрицей перестановки называется матрица , полученная из единичной матрицы путем перестановки в ней строк с номерами и . Умножение матрицы на матрицу приводит к перестановке в последней -ой и -ой строк.

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

· Матрица перестановок является унитарной матрицей: .

· Произведение произвольного числа матриц перестановок является матрицей перестановок.

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

Алгоритм частичного упорядочения с выбором главного элемента по столбцам фактически состоит в определении позиции главного элемента и построении элементарной матрицы перестановок. Пусть, например, при исключении неизвестных в системе ЛАУ с матрицей 5x5 после двух шагов исключения неизвестных имеем, что ведущий элемент , максимальный элемент третьего столбца находится в четвертой строке:

. Тогда , .

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

Замечание 1. Кроме рассмотренного алгоритма частичного упорядочения с выбором главного элемента по столбцам существуют аналогичные варианты упорядочения по строкам, а также по строкам и столбцам одновременно.

Замечание 2. Надежность алгоритма частичного упорядочения существенно повышается, если матрица системы ЛАУ масштабирована таким образом, что максимальные значения модулей элементов в каждой строке и каждом столбце имеют одинаковый порядок. Если матрица не отвечает требованиям масштабирования полезно, по крайней мере, предварительно выполнить нормировку строк, нарушающих баланс матрицы.

Замечание 3. Среди немногочисленных случаев, когда частичное упорядочение оказывается излишним, можно отметить диагонально-доминирующие и симметричные положительно-определенные матрицы.