Алгоритм Барейса: различия между версиями

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

Основной алгоритм Барейса отличается от одноименногоодноимённого алгоритма для [[Матрица Тёплица|матриц Тёплица]].

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

{{не переведено 5iw|Ошибки округления|4=|en|Round-off_erroroff error}} можно избежать, если все числа хранить как дроби вместо чисел с плавающей запятой. Однако размер каждого элемента растёт экспоненциально в зависимости от числа строк{{sfn|Middeke, Jeffrey, Koutschan|2020}}.

Барейс поставил вопрос проведения исключений в целых числах, сохраняя при этом величину промежуточных коэффициентов достаточно маленькой. Было предложено два алгоритма{{sfn|Bareiss|1968|с=565-578565—578}}{{sfn|Bareiss|1966}}:

# Алгоритм без деления  — осуществляет сведение матрицы к треугольному виду вообще без операции деления.

# Алгоритм без остатков  — использует деление для уменьшения промежуточных значений, но, вследствие {{Не переведено 5|тождества Сильвестера|4=Sylvester's determinant identity}}, преобразование остаётся целым (деление имеет нулевой остаток).

Для полноты Барейс предложил также методы исключений без умножения, но с дробями{{sfn|Bareiss|1968|с=565-578565—578}}.

Вычислительная структура этого алгоритма представляет собой простой тройной цикл, как и в обычном [[Метод Гаусса|методе Гаусса]]. Однако в этом случае матрица модифицируется так, что каждый элемент <math>M_{k,k}</math> содержит ведущий главный [[Минор (линейная алгебра)|минор]] ''[M]_{k, k}''. Правильность алгоритма легко показывается индукцией по ''k''{{sfn|Yap|2000}}.

* Входные данные: M  — <math>n \times n </math> матрица <br/>в предположении, что все ведущие главные миноры <math>[M]_{k,k}</math> не нулевые.

* Выходные данные: Матрица изменена {{не переведено 5|алгоритм на месте|на месте||In-place_algorithm}},<br/>каждый элемент ''M_{k, k}'' содержит ведущий главный минор <math>[M]_{k,k}</math>,<br/>значение <math>M_{n,n}</math> содержит определитель исходной матрицы M.

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

Отсюда следует, что для <math>n \times n</math> матрицы с максимальным (абсолютным) значением <math>2^L</math> для каждого элемента алгоритм Барейса работает за [[«O» большое и «o» малое|O(''n''³)]] элементарных операций с ограничением <math>O(n^{\tfrac{n}{2}}2^{nL})</math> на абсолютную величину промежуточных значений. [[Вычислительная сложность]] алгоритма тогда составляет <math>O(n^5L^2 (\log(n)^2 + L^2))</math> при использовании элементарной арифметики или <math>O(n^4L(\log(n) + L) \log(log(n) + L)))</math> при использовании {{не переведено 5|алгоритм умножения|быстрого умножения|4=fast multiplication}}.

== Примечания ==

== Литература ==

* {{статья

* {{статья

* {{статья

* {{статья