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

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

История

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

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

Обзор

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

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

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

Барейс поставил вопрос проведения исключений в целых числах, сохраняя при этом величину промежуточных коэффициентов достаточно маленькой. Предложено два алгоритмаШаблон:SfnШаблон:Sfn:

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

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

Алгоритм

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

• Входные данные: M — $n\times n$ матрица
  в предположении, что все ведущие главные миноры $[M{]}_{k,k}$ не нулевые.
• Положим $M_{0,0}=1$
• Для всех Шаблон:Mvar от 1 до Шаблон:Mvar:
  • Для всех Шаблон:Mvar от Шаблон:Mvar до Шаблон:Mvar:
    • Для всех Шаблон:Mvar от Шаблон:Mvar до Шаблон:Mvar:
      • Положим $M_{i,j}=\frac{M_{i,j}{M}_{k,k}-M_{i,k}{M}_{k,j}}{M_{k-1,k-1}}$
• Выходные данные: Матрица изменена Шаблон:Не переведено 5,
  каждый элемент M_{k, k} содержит ведущий главный минор $[M{]}_{k,k}$,
  значение $M_{n,n}$ содержит определитель исходной матрицы M.

Если предположение о неравенству нулю главных миноров окажется неверным, то есть $M_{k-1,k-1}=0$, а некоторые $M_{i,k-1}\ne 0(i=k,\dots ,n)$, то мы можем переставить строки k-1 и i местами, сменив знак конечного значения.

Анализ

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

Отсюда следует, что для $n\times n$ матрицы с максимальным (абсолютным) значением $2^L$ для каждого элемента алгоритм Барейса работает за O(n³) элементарных операций с ограничением $O(n^{\frac{n}{2}}{2}^{nL})$ на абсолютную величину промежуточных значений. Вычислительная сложность алгоритма тогда составляет $O(n^5{L}^2(\log (n{)}^2+L^2))$ при использовании элементарной арифметики или $O(n^{4}L(\log (n)+L)\log (log(n)+L)))$ при использовании Шаблон:Не переведено 5.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья (Содержит ясное описание последовательности операций)
• Шаблон:Статья