Формула Лейбница для определителей
Формула Лейбница — выражение для определителя квадратной матрицы [math]\displaystyle{ A = (a_{i,j}) }[/math] размера [math]\displaystyle{ n \times n }[/math] через перестановки её элементов:
- [math]\displaystyle{ \det(A) = \sum_{\tau \in S_n} \sgn(\tau) \prod_{i = 1}^n a_{i, \tau(i)} = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i = 1}^n a_{\sigma(i), i}, }[/math]
где [math]\displaystyle{ \sgn }[/math] — функция знака перестановки в группе перестановок [math]\displaystyle{ S_n }[/math], которая возвращает +1 или −1 для чётных и нечётных перестановок соответственно.
С использованием символа Леви-Чивиты и соглашений о суммировании Эйнштейна:
- [math]\displaystyle{ \det(A)=\epsilon_{i_1\cdots i_n}{a}_{1i_1}\cdots {a}_{ni_n} }[/math].
Названа в честь Готфрида Лейбница, который ввёл понятие определителя и способ его вычисления в 1678 году.
Единственная знакопеременная мультилинейная функция , обращающаяся в единицу на единичной матрице — это функция, определённая формулой Лейбница[1]; таким образом, определитель может быть однозначно определён как знакопеременная мультилинейная функция, полилинейная относительно столбцов, обращающаяся в единицу на единичной матрице.
Вычислительная сложность
Прямое вычисление по формуле Лейбница требует в общем случае [math]\displaystyle{ \Omega(n! \cdot n) }[/math] операций, то есть, число операций асимптотически пропорционально факториалу [math]\displaystyle{ n }[/math] (числу упорядоченных перестановок из [math]\displaystyle{ n }[/math] элементов). Для больших [math]\displaystyle{ n }[/math] определитель можно вычислить за [math]\displaystyle{ O(n^3) }[/math] операций путём формирования LU-разложения [math]\displaystyle{ A = LU }[/math] (обычно получаемого с помощью метода Гаусса или аналогичных методов), и в этом случае [math]\displaystyle{ \det A = (\det L) (\det U) }[/math], а определители треугольных матриц [math]\displaystyle{ L }[/math] и [math]\displaystyle{ U }[/math] равняются произведениям диагональных элементов матриц. (В практических приложениях вычислительной линейной алгебры, однако, явное вычисление определителя используется редко[2]).
Смотрите также
Литература
- Определитель — статья из Математической энциклопедии. Д. И. Супруненко
- Lloyd N. Trefethen, David Bau. Numerical Linear Algebra. — SIAM, 1997. — ISBN 978-0898713619.
- Serge Lang. Linear Algebra. — Springer-Verlag, 2004. — (Undergraduate texts in mathematic). — ISBN 0-387-96412-6.
Для улучшения этой статьи желательно: |
- ↑ Lang, 2004, с. 148 Theorem 2.3.
- ↑ Trefethen & Bau, 1997.