Русская Википедия:Алгоритм Барейса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

История

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

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

Обзор

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

Метод Гаусса имеет сложность <math>O(n^3)</math>, но использует деление, которое приводит к ошибкам округления в случае реализации с помощью арифметики с плавающей запятой.

Шаблон:Iw можно избежать, если все числа хранить как дроби вместо чисел с плавающей запятой. Однако размер каждого элемента растёт экспоненциально в зависимости от числа строкШаблон:Sfn.

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

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

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

Алгоритм

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

• Входные данные: M — <math>n \times n </math> матрица
  в предположении, что все ведущие главные миноры <math>[M]_{k,k}</math> не нулевые.
• Положим <math>M_{0,0} = 1</math>
• Для всех Шаблон:Mvar от 1 до Шаблон:Mvar:
  • Для всех Шаблон:Mvar от Шаблон:Mvar до Шаблон:Mvar:
    • Для всех Шаблон:Mvar от Шаблон:Mvar до Шаблон:Mvar:
      • Положим <math>M_{i,j} = \frac{M_{i,j} M_{k,k} - M_{i,k} M_{k,j}}{M_{k-1,k-1}}</math>
• Выходные данные: Матрица изменена Шаблон:Не переведено 5,
  каждый элемент M_{k, k} содержит ведущий главный минор <math>[M]_{k,k}</math>,
  значение <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(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.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья (Содержит ясное описание последовательности операций)
• Шаблон:Статья