В математике Bareiss алгоритм , названный в честь Эрвина Bareiss , является алгоритм для вычисления определителя или эшелон формы в виде матрицы с целыми записями с использованием только целочисленной арифметикой; любые выполняемые деления гарантированно будут точными (нет остатка ). Этот метод также можно использовать для вычисления определителя матриц с (приближенными) действительными записями, избегая введения каких-либо ошибок округления, помимо тех, которые уже присутствуют во входных данных.
История [ править ]
Общий алгоритм Барейсса отличается от алгоритма Барейса для матриц Теплица .
В некоторых испаноязычных странах этот алгоритм также известен как Bareiss-Montante из-за Рене Марио Монтанте Пардо , профессора Автономного университета Нуэво-Леон , Мексика , который популяризировал этот метод среди своих учеников.
Обзор [ править ]
В определении детерминанта есть только операции умножения, сложения и вычитания. Очевидно, что определитель целочислен, если все элементы матрицы целочисленные. Однако фактическое вычисление определителя с использованием определения или формулы Лейбница непрактично, поскольку требует O ( n! ) Операций.
Исключение по Гауссу имеет сложность O ( n 3 ), но вводит деление, которое приводит к ошибкам округления при использовании чисел с плавающей запятой.
Ошибок округления можно избежать, если все числа будут храниться в виде целых дробей, а не с плавающей точкой. Но затем размер каждого элемента растет экспоненциально с увеличением количества строк. [1]
Барейсс поднимает вопрос о выполнении исключения с сохранением целого числа при сохранении разумно малых величин промежуточных коэффициентов. Предлагаются два алгоритма: [2] [3]
- Алгоритм без деления - выполняет приведение матрицы к треугольной форме без каких-либо операций деления.
- Алгоритм без дроби - использует деление, чтобы промежуточные записи были меньше, но из-за идентичности Сильвестра преобразование по-прежнему сохраняет целое число (остаток деления равен нулю).
Для полноты картины Барейсс также предлагает методы исключения без умножения с получением дробей. [2]
Алгоритм [ править ]
Программная структура этого алгоритма представляет собой простой тройной цикл, как и в стандартном методе исключения Гаусса. Однако в этом случае матрица модифицируется так, чтобы каждая запись M k, k содержала ведущий главный минор [M] k, k . Правильность алгоритма легко показать индукцией по k . [4]
- Ввод: M - n-квадратная матрица,
предполагающая, что ее главные главные миноры [M] k, k все ненулевые. - Пусть M 0,0 = 1 (Примечание: M 0,0 - специальная переменная)
- Для k от 1 до n-1 :
- Для i от k + 1 до n :
- Для j от k + 1 до n :
- Набор
- Для j от k + 1 до n :
- Для i от k + 1 до n :
- Выход: матрица модифицируется на месте ,
каждая запись M k, k содержит ведущий минор [M] k, k ,
запись M n, n содержит определитель исходного M.
Если предположение о главных минорах оказывается неверным, например, если M k − 1, k − 1 = 0 и некоторое M i, k − 1 ≠ 0 (i = k, ..., n), то мы можем поменять местами k-1 ряд с i-й строкой и изменить знак окончательного ответа.
Анализ [ править ]
Во время выполнения алгоритма Барейса каждое вычисляемое целое число является определителем подматрицы входной матрицы. Это позволяет с помощью неравенства Адамара ограничить размер этих целых чисел. В противном случае алгоритм Барейсса можно рассматривать как вариант исключения Гаусса и требует примерно того же количества арифметических операций.
Отсюда следует, что для матрицы размера n × n максимального (абсолютного) значения 2 L для каждой записи алгоритм Барейсса выполняется за O ( n 3 ) элементарных операций с ограничением O ( n n / 2 2 nL ) на абсолютное значение. требуемых промежуточных значений. Таким образом, его вычислительная сложность составляет O ( n 5 L 2 (log ( n ) 2 + L 2 )) при использовании элементарной арифметики или O ( n 4 L (log ( n ) + L) log (log ( n ) + L ))) с помощью быстрого умножения .
Ссылки [ править ]
- ^ Миддеке, Дж .; Джеффри, диджей; Кутшан, К. (2020), "Общие множители в дробных матричных декомпозициях", Math.Comput.Sci. , DOI : 10.1007 / s11786-020-00495-9
- ^ Б Bareiss, Эрвин Х. (1968), "Сильвестр Идентичность и многоступенчатое целое сохраняющего Гаусса" (PDF) , Математика вычислений , 22 (103): 565-578, DOI : 10,2307 / 2004533 , JSTOR 2004533
- ^ Барейсс, Эрвин Х. (1966), MULTISTEP INTEGER-СОХРАНЕНИЕ ГАУССОВСКОГО УСТРАНЕНИЯ (PDF) . (Содержит более четкое представление о последовательности операций)
- ^ Яп, Чи Кенг (2000), "Фундаментальные проблемы алгоритмической алгебры", Oxford University Press