Выражение определителя в терминах миноров
В линейной алгебре, Расширение Лапласа, названное в честь Пьера-Симона Лапласа, также называемое кофакторным расширением, является выражением для детерминанта | B | матрицы B размером n × n , которая является взвешенной суммой детерминантов n подматриц (или миноров ) матрицы B, каждая размером (n - 1) × (n - 1). Разложение Лапласа представляет дидактический интерес своей простотой и одним из нескольких способов просмотра и вычисления определителя. Для больших матриц вычисление быстро становится неэффективным по сравнению с методами, использующими разложение матриц .
. При вычислении определителя с помощью разложения Лапласа используется кофактор и второстепенный. Коэффициент i, j матрицы B - это скаляр C ij, определенный как
где M ij - это i, j минор B, то есть, определитель матрицы (n - 1) × (n - 1), который получается в результате удаления i-й строки и j-го столбца B.
Тогда разложение Лапласа задается следующим
- Теорема . Предположим, что - матрица и выберите любой фиксированный . Предположим, что - фиксированный выбор . Тогда его определитель определяется по формуле:
- где - младший элемент , то есть определитель подматрицы формируется путем удаления строки и столбец матрицы .
Содержание
- 1 Примеры
- 2 Доказательство
- 3 Лаплас расширение определителя дополнительными минорами
- 3.1 Пример
- 3.2 Общие положения
- 4 Вычислительные затраты
- 5 См. также
- 6 Ссылки
- 7 Внешние ссылки
Примеры
Рассмотрим матрицу
Определитель этой матрицы можно вычислить, используя разложение Лапласа по любой из ее строк или столбцов. Например, расширение по первой строке дает:
Расширение Лапласа по второму столбцу дает тот же результат :
Легко проверить, что результат правильный: матрица сингулярная, потому что сумма ее первого и третьего столбца в два раза больше, чем второй столбец, и, следовательно, ее определитель равен нулю.
Доказательство
Предположим, - матрица размера n × n и Для ясности мы также помечаем записи , составляющие его вспомогательную матрицу как
для
Рассмотрим термины в расширении с коэффициентом . Каждый имеет вид
для некоторой перестановки τ ∈ Sn с и уникальной и очевидно связанной перестановкой , который выбирает те же второстепенные записи, что и τ. Точно так же каждый выбор σ определяет соответствующее τ, т.е. соответствие является взаимно однозначным соответствием между и Явная связь между и можно записать как
где - временное сокращение обозначение для цикла . Эта операция уменьшает все индексы, превышающие j, так, чтобы каждый индекс помещался в набор {1,2,..., n-1}
Перестановка τ может быть получена из σ следующим образом. Определим как для и . Тогда выражается как
Теперь, операция, которая применяется , а затем применить is (Обратите внимание, что применение A перед B эквивалентно применению обратного значения A к верхней строке B в Двухстрочная запись Коши )
где - временное сокращенное обозначение для .
операция, которая сначала применяет , а затем применяет is
два вышеупомянутых числа равны, таким образом,
где является обратным к который равен .
Таким образом
Поскольку два цикла могут быть записаны соответственно как и транспозиции,
И поскольку карта биективна,
из которого следует результат ws. Точно так же результат сохраняется, если индекс внешнего суммирования был заменен на .
разложение Лапласа определителя дополнительными минорами
Расширение кофактора Лапласа можно обобщить следующим образом.
Пример
Рассмотрим матрицу
Определитель этой матрицы можно вычислить, используя разложение кофактора Лапласа по первым двум строки следующим образом. Во-первых, обратите внимание, что в {1, 2, 3, 4} есть 6 наборов двух различных чисел, а именно пусть - вышеупомянутый набор.
Определив дополнительные сомножители как
и знак их перестановки должен быть
Определитель A можно записать как
где - дополнительный набор к .
В нашем явном примере это дает нам
Как и выше, легко проверить, что результат правильный: матрица сингулярна, потому что сумма ее первого и третьего столбца вдвое больше, чем второй столбец, и, следовательно, ее определитель равен нулю.
Общий оператор
Пусть будет матрицей n × n и набор k-элементных подмножеств {1, 2,..., n}, элемента в этом. Тогда определитель может быть расширен вдоль k строк, обозначенных следующим образом:
где - знак перестановки, определяемый и , равно , меньший квадрат , полученный путем удаления из строк и столбцов с индексами в и соответственно и (называемое дополнением ), определенное как , и является дополнением из и соответственно.
Это совпадает с теоремой выше, когда . То же самое верно для любых фиксированных k столбцов.
Вычислительные затраты
Расширение Лапласа вычислительно неэффективно для матриц большой размерности с временной сложностью в нотации большого O из . В качестве альтернативы, использование разложения на треугольные матрицы, как в разложение LU, может дать определители с временной сложностью . Следующий код Python рекурсивно реализует расширение Лапласа:
определитель def (M): # Базовый случай рекурсивной функции: матрица 2x2 (такая, что det (M) = ad - cb) if len (M) == 2: return (M [0] [0] * M [1] [1]) - (M [0] [1] * M [1] [0]]) else: total = 0 для столбца, элемент в enumerate (M [0]): # Исключить первую строку и текущий столбец. K = [x [: column] + x [column + 1:] для x в M [1:]] # Учитывая, что элемент находится в строке 1, знак отрицательный, если индекс нечетный. if столбец% 2 == 0: итог + = элемент * определитель (K) else: итог - = элемент * определитель (K) вернуть итог
См. также
- Портал математики
- Формула Лейбница для определителей
- Правило Сарруса для определителей
Ссылки
- ^Stoer Bulirsch: Introduction to Numerical Mathematics
- David Poole: Linear Algebra. Современное введение. Cengage Learning 2005, ISBN 0-534-99845-3, стр. 265–267 (ограниченная онлайн-копия, стр. 265, на Google Книги )
- Харви Э. Роуз: Линейная алгебра. Чистый математический подход. Springer 2002, ISBN 3-7643-6905-1, pp. 57–60 ( ограниченная копия в Интернете, стр. 57, на Google Книги )
Внешние ссылки
- Расширение Лапласа на C (на португальском языке)
- Расширение Лапласа в Java ( на португальском языке)