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

71 байт добавлено ,  5 месяцев назад
м
викификация, источники
(оформление)
Метка: Задача для новичков
м (викификация, источники)
Метки: визуальный редактор Задача для новичков
'''Алгоритм Барейса''', названный именем [[Эрвин Барейс|Эрвина Барейса]], — это [[алгоритм]] вычисления [[Определитель|определителя]] или [[Ступенчатый вид матрицы|ступенчатого вида]] [[Матрица (математика)|матрицы]] с [[Целое число|целыми]] элементами с помощью исключительно целочисленной арифметики. Любое [[Деление (математика)|деление]], выполняемое по алгоритму, гарантирует точное деление (без [[Деление с остатком|остатка]]). Метод может быть использован также для вычисления [[Определитель|определителя матрицы]] с (приблизительными) [[Вещественное число|вещественными]] элементами, что исключает ошибки [[Округление|округления]], за исключением ошибок, уже присутствующих во входных данных.
 
== История ==
[[Метод Гаусса]] имеет сложность O(''n''<sup>3</sup>), но использует деление, которое приводит к ошибкам округления в случае реализации с помощью арифметики с плавающей запятой.
 
{{iw|Ошибки округления||en|Round-off error}} можно избежать, если все числа хранить как дроби вместо чисел с плавающей запятой. Однако размер каждого элемента растёт [[Экспоненциальный рост|экспоненциально]] в зависимости от числа строк{{sfn|Middeke, Jeffrey, Koutschan|2020}}.
 
Барейс поставил вопрос проведения исключений в целых числах, сохраняя при этом величину промежуточных коэффициентов достаточно маленькой. Было предложено два алгоритма{{sfn|Bareiss|1968|с=565—578}}{{sfn|Bareiss|1966}}: