WikiDer > Разложение Лапласа

Laplace expansion

В линейная алгебра, то Разложение Лапласа, названный в честь Пьер-Симон Лаплас, также называемый расширение кофактора, является выражением для детерминант |B| из п × п матрица B это взвешенная сумма детерминантов п подматрицы (или несовершеннолетние) из B, каждый размером (п − 1) × (п - 1). Разложение Лапласа представляет дидактический интерес своей простотой и одним из нескольких способов просмотра и вычисления определителя. Для больших матриц вычисления быстро становятся неэффективными по сравнению с методами, использующими матричное разложение.

При вычислении определителя разложением Лапласа используется кофактор и незначительный. В я, j кофактор матрицы B это скаляр Cij определяется

куда Mij это я, j незначительный из B, то есть определитель (п − 1) × (п - 1) матрица, полученная в результате удаления я-й ряд и j-й столбец B.

Тогда разложение Лапласа дается следующим

Теорема. Предполагать является матрицу и выберите любую фиксированную . Предполагать фиксированный выбор . Тогда его определитель дан кем-то:
куда минор элемента , т.е. определитель подматрицы сформированный путем удаления ряд и столбец матрицы .

Примеры

Рассмотрим матрицу

Определитель этой матрицы может быть вычислен с помощью разложения Лапласа по любой из ее строк или столбцов. Например, расширение по первой строке дает:

Разложение Лапласа по второму столбцу дает тот же результат:

Убедиться в правильности результата несложно: матрица единственное число потому что сумма его первого и третьего столбца вдвое больше, чем второй столбец, и, следовательно, его определитель равен нулю.

Доказательство

Предполагать является п × п матрица и Для ясности мы также помечаем записи которые составляют его малая матрица в качестве

за

Рассмотрим слагаемые в разложении который имеет как фактор. Каждый имеет форму

для некоторых перестановка τSп с , и уникальная и очевидно связанная перестановка который выбирает те же второстепенные записи, что и τ. Подобным образом каждый выбор σ определяет соответствующий τ то есть соответствие это биекция между и Явная связь между и можно записать как

куда временное сокращенное обозначение цикл . Эта операция уменьшает все индексы, большие, чем j, так что каждый индекс помещается в набор {1,2, ..., n-1}

Перестановка τ может быть получено из σ следующим образом. к за и . потом выражается как

Теперь операция, которая применяется сначала, а затем применить is (Обратите внимание, что применение A перед B эквивалентно применению обратного A к верхней строке B в Двухстрочная запись Коши )

куда временное сокращенное обозначение .

операция, которая применяется сначала, а затем применить является

выше двух равны, таким образом,

куда является инверсией который .

Таким образом

Поскольку два циклы можно записать соответственно как и транспозиции,

А поскольку карта биективен,

из чего следует результат. Точно так же результат сохраняется, если индекс внешнего суммирования был заменен на .

Лапласовское разложение определителя дополнительными минорами

Разложение кофактора Лапласа можно обобщить следующим образом.

Пример

Рассмотрим матрицу

Определитель этой матрицы может быть вычислен с помощью разложения кофактора Лапласа по первым двум строкам следующим образом. Во-первых, обратите внимание, что есть 6 наборов двух разных чисел в {1, 2, 3, 4}, а именно пусть быть вышеупомянутым набором.

Определив дополнительные кофакторы как

и знак их перестановки быть

Определитель А можно записать как

куда дополнительный набор к .

В нашем явном примере это дает нам

Как и выше, легко проверить правильность результата: матрица единственное число потому что сумма его первого и третьего столбца вдвое больше, чем второй столбец, и, следовательно, его определитель равен нулю.

Общее утверждение

Позволять быть п × п матрица и набор k-элементные подмножества {1, 2, ... , п}, элемент в нем. Тогда определитель может быть расширен по k строки, идентифицированные следующее:

куда - знак перестановки, определяемый и , равно , малый квадрат получено путем удаления из строки и столбцы с индексами в и соответственно, и (называется дополнением ) определяется как , и являясь дополнением и соответственно.

Это совпадает с теоремой выше, когда . То же самое верно для любых фиксированных k столбцы.

Вычислительные затраты

Расширение Лапласа вычислительно неэффективно для матриц большой размерности с временная сложность в нотация большой O из . В качестве альтернативы, используя разложение на треугольные матрицы как в LU разложение может дать детерминанты с временной сложностью .[1] Следующее Python код рекурсивно реализует расширение Лапласа[нужна цитата]:

def детерминант(M):    # Базовый случай рекурсивной функции: матрица 2x2 (такая, что det (M) = ad - cb)    если len(M) == 2:        возвращаться (M[0][0] * M[1][1]) - (M[0][1] * M[1][0])    еще:        общий = 0        за столбец, элемент в перечислять(M[0]):            # Исключить первую строку и текущий столбец.            K = [Икс[:столбец] + Икс[столбец + 1 :] за Икс в M[1:]]            # Учитывая, что элемент находится в строке 1, знак отрицательный, если индекс нечетный.            если столбец % 2 == 0:                общий += элемент * детерминант(K)            еще:                общий -= элемент * детерминант(K)        возвращаться общий

Смотрите также

Рекомендации

  1. ^ Стоер Булирш: Введение в вычислительную математику
  • Дэвид Пул: Линейная алгебра. Современное введение. Cengage Learning 2005 г., ISBN 0-534-99845-3, стр. 265–267 (ограниченная онлайн-копия, п. 265, в Google Книги)
  • Харви Э. Роуз: Линейная алгебра. Чистый математический подход. Springer 2002, ISBN 3-7643-6905-1, стр. 57–60 (ограниченная онлайн-копия, п. 57, в Google Книги)

внешняя ссылка