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

В математике Bareiss алгоритм , названный в честь Эрвина Bareiss , является алгоритм для вычисления определителя или эшелон формы в виде матрицы с целыми записями с использованием только целочисленной арифметикой; любые выполняемые деления гарантированно будут точными (нет остатка ). Этот метод также можно использовать для вычисления определителя матриц с (приближенными) действительными записями, избегая введения каких-либо ошибок округления, помимо тех, которые уже присутствуют во входных данных.

История [ править ]

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

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

Обзор [ править ]

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

Исключение по Гауссу имеет сложность O ( n 3 ), но вводит деление, которое приводит к ошибкам округления при использовании чисел с плавающей запятой.

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

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

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

Для полноты картины Барейсс также предлагает методы исключения без умножения с получением дробей. [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 :
        • Набор
  • Выход: матрица модифицируется на месте ,
    каждая запись 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 ))) с помощью быстрого умножения .

Ссылки [ править ]

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