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

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

История

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

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

Обзор

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

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

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

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

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

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

Алгоритм

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

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

Анализ

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

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

Примечания

Литература

• Middeke J., Jeffrey D.J., Koutschan C. Common Factors in Fraction-Free Matrix Decompositions // Math.Comput.Sci. — 2020. — doi:10.1007/s11786-020-00495-9.
• Erwin H. Bareiss. Sylvester's Identity and multistep integer-preserving Gaussian elimination // Mathematics of Computation. — 1968. — Т. 22, вып. 103. — С. 565—578. — doi:10.2307/2004533. — JSTOR 2004533.
• Erwin H. Bareiss. Multistep integer-preserving Gaussian elimination. — 1966. (Содержит ясное описание последовательности операций)
• Chee Keng Yap. Fundamental Problems of Algorithmic Algebra // Oxford University Press. — 2000.

Эта страница в последний раз была отредактирована 23 июня 2022 в 14:54.