Алгоритм Барейса — алгоритм вычисления определителя или приведения к ступенчатому виду матрицы с целыми элементами с помощью исключительно целочисленной арифметики. Назван именем Э. Барейса. Любое деление, выполняемое по алгоритму, гарантирует точное деление (без остатка). Метод может быть использован также для вычисления определителя матрицы с (приблизительными) вещественными элементами, что исключает ошибки округления, за исключением ошибок, уже присутствующих во входных данных, и для решения систем линейных алгебраических уравнений (СЛАУ).
История Общий алгоритм Барейса отличается от одноимённого алгоритма для обращения матриц Тёплица.
В некоторых испаноязычных странах алгоритм известен также как алгоритм Барейса — Монтанте, поскольку Рене Марио Монтанте Пардо, профессор автономного университета штата Нуэво Леон в Мексике, популяризовал метод среди студентов.
Обзор Определение определителя использует только операции умножения, сложения и вычитания. Очевидно, что определитель будет целым, если все элементы матрицы целые. Однако фактическое вычисление определителя, исходя чисто из определения или используя формулу Лейбница, непрактично, поскольку требует операций.
Метод Гаусса имеет сложность , но использует деление, которое приводит к ошибкам округления в случае реализации с помощью арифметики с плавающей запятой.
Ошибки округления можно избежать, если все числа хранить как дроби вместо чисел с плавающей запятой. Однако размер каждого элемента растёт экспоненциально в зависимости от числа строк.
Барейс поставил вопрос проведения исключений в целых числах, сохраняя при этом величину промежуточных коэффициентов достаточно маленькой. Предложено два алгоритма: Алгоритм без деления — осуществляет сведение матрицы к треугольному виду вообще без операции деления. Алгоритм без остатков — использует деление для уменьшения промежуточных значений, но, вследствие , преобразование остаётся целым (деление имеет нулевой остаток).
Для полноты Барейс предложил также методы исключений без умножения, но с дробями.
Алгоритм Вычислительная структура этого алгоритма представляет собой простой тройной цикл, как и в обычном методе Гаусса. Однако в этом случае матрица модифицируется так, что каждый элемент содержит ведущий главный минор [M]k, k. Правильность алгоритма легко показывается индукцией по k.
Входные данные: M — матрица в предположении, что все ведущие главные миноры не нулевые. Положим Для всех от 1 до : Для всех от до : Для всех от до : Положим Выходные данные: Матрица изменена ,каждый элемент Mk, k содержит ведущий главный минор ,значение содержит определитель исходной матрицы M.
Если предположение о неравенству нулю главных миноров окажется неверным, то есть , а некоторые , то мы можем переставить строки k-1 и i местами, сменив знак конечного значения.
Анализ Во время выполнения алгоритма Барейса любое вычисленное целое является определителем подматрицы входной матрицы. Это позволяет с помощью неравенства Адамара ограничить размер целых чисел. В остальном алгоритм Барейса можно рассматривать как вариант метода Гаусса, который требует большего количества арифметических операций, так как в главном цикле, при каждом проходе, количество делений уменьшается на 1, а количество умножений удваивается.
Отсюда следует, что для матрицы с максимальным (абсолютным) значением для каждого элемента алгоритм Барейса работает за O(n3) элементарных операций с ограничением на абсолютную величину промежуточных значений. Вычислительная сложность алгоритма тогда составляет при использовании элементарной арифметики или при использовании .
Примечания
Литература
(Содержит ясное описание последовательности операций)
Категория:Определители Категория:Численные методы линейной алгебры Категория:Перестановочные алгоритмы Категория:Вычислительная алгебра