Алгоритм Барейса

Алгоритм Барейса — алгоритм вычисления определителя или приведения к ступенчатому виду матрицы с целыми элементами с помощью исключительно целочисленной арифметики. Назван именем Э. Барейса. Любое деление, выполняемое по алгоритму, гарантирует точное деление (без остатка). Метод может быть использован также для вычисления определителя матрицы с (приблизительными) вещественными элементами, что исключает ошибки округления, за исключением ошибок, уже присутствующих во входных данных.

История 
Общий алгоритм Барейса отличается от одноимённого алгоритма для обращения матриц Тёплица.

В некоторых испаноязычных странах алгоритм известен также как алгоритм Барейса — Монтанте, поскольку Рене Марио Монтанте Пардо, профессор автономного университета штата Нуэво Леон в Мексике, популяризовал метод среди студентов.

Обзор 
Определение определителя использует только операции умножения, сложения и вычитания. Очевидно, что определитель будет целым, если все элементы матрицы целые. Однако фактическое вычисление определителя, исходя чисто из определения или используя формулу Лейбница, непрактично, поскольку требует  операций.

Метод Гаусса имеет сложность , но использует деление, которое приводит к ошибкам округления в случае реализации с помощью арифметики с плавающей запятой.

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

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

Для полноты Барейс предложил также методы исключений без умножения, но с дробями.

Алгоритм 
Вычислительная структура этого алгоритма представляет собой простой тройной цикл, как и в обычном методе Гаусса. Однако в этом случае матрица модифицируется так, что каждый элемент  содержит ведущий главный минор [M]k, k. Правильность алгоритма легко показывается индукцией по k.

 Входные данные: M —  матрица в предположении, что все ведущие главные миноры  не нулевые.
 Положим 
 Для всех  от 1 до :
 Для всех  от  до :
 Для всех  от  до :
 Положим 
 Выходные данные: Матрица изменена ,каждый элемент Mk, k содержит ведущий главный минор ,значение  содержит определитель исходной матрицы M.

Если предположение о неравенству нулю главных миноров окажется неверным, то есть , а некоторые , то мы можем переставить строки k-1 и i местами, сменив знак конечного значения.

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

Отсюда следует, что для  матрицы с максимальным (абсолютным) значением  для каждого элемента алгоритм Барейса работает за O(n3) элементарных операций с ограничением  на абсолютную величину промежуточных значений. Вычислительная сложность алгоритма тогда составляет  при использовании элементарной арифметики или  при использовании .

Примечания

Литература 
 
 
  (Содержит ясное описание последовательности операций)
 

Определители
Численные методы линейной алгебры
Перестановочные алгоритмы
Вычислительная алгебра