Вычисление главных миноров

49. Однако шаги алгорифма § 48 могут быть модифицированы таким образом, что он будет иметь существенные преимущества. Модифицированный процесс также имеет основных шагов, но на первых шагах участвуют лишь первые строк Структура элементов после основных шагов для случая такова:

Строка является неизмененной строкой строки с 1-й до преобразуются способом, который станет ясным из следующего описания основного шага.

Для каждого значения от 1 до :

(i) Сравниваем Если переставляем

(ii) Вычисляем и записываем на место как . Если на шаге (i) имела место перестановка, то помечаем звездочкой.

(iii) Для каждого значения от до :

Вычисляем и записываем на место

(iv) Вычисляем и записываем на место .

Эта схема имеет два преимущества.

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

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

Если мы запоминаем текущее число перестановок к, которые имели место с начала первого основного шага, то после выполнения r-го шага имеем:

где - соответствующие значения.

Часто нам будет нужен лишь знак Он может быть получен следующим образом на r-м основном шаге.

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

Миноры могут быть вычислены и по алгорифму § 48, но метод, который мы описали, более удобен. Вообще говоря, главные миноры не могут быть вычислены, если мы используем метод Гаусса с выбором главного элемента по столбцу или по всей матрице, или если мы используем триангуляризацию Хаусхолдера.