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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

[править | править код]

Литература

[править | править код]