Разложение по алгебраическим дополнениям (Лапласа): практическое руководство

Вычисление определителя матрицы 3×3 — или большей — уже не так просто, как в случае 2×2.

Нельзя просто перемножить две диагонали. По мере роста размера матрицы арифметика становится громоздкой. Без структурированного метода легко потерять нить вычислений. Именно для таких ситуаций и было создано разложение по алгебраическим дополнениям — его также называют разложением Лапласа.

Разложение по дополнениям — это метод вычисления определителя любой квадратной матрицы путём разложения по выбранной строке или столбцу. Он рекурсивно разбивает задачу на меньшие определители, которые вы уже умеете находить.

В этой статье мы разберём определение разложения по дополнениям, формулу, пошаговые примеры для матриц 2×2 и 3×3, ключевые свойства и практические применения.

Что такое разложение по алгебраическим дополнениям?

Разложение по дополнениям — это рекурсивный метод вычисления определителя любой квадратной матрицы.

Здесь «рекурсивный» означает, что вместо того чтобы вычислять определитель большой матрицы целиком, вы разбиваете его на определители меньших матриц. Те, в свою очередь, разбиваются ещё на более маленькие. Вы продолжаете, пока не останутся матрицы 2×2, для которых решение тривиально.

Метод работает для любой квадратной матрицы — 2×2, 3×3, 4×4 и далее. При этом он особенно полезен для матриц 3×3 и больше, где уже нельзя просто перемножить две диагонали.

Идея проста. Вы выбираете одну строку или один столбец и раскладываете по ним. Каждый элемент в выбранной строке или столбце даёт меньшую подзадачу. Решаете подзадачи, объединяете результаты — и получаете определитель. Вот и всё.

Минор и алгебраическое дополнение: ключевые определения

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

Минор

Минор M_ij — это определитель меньшей матрицы, полученной удалением из исходной матрицы строки i и столбца j.

Предположим, у вас есть матрица 3×3 A, и вам нужен минор M_12. Удалите строку 1 и столбец 2. Останется матрица 2×2. Вычислите её определитель — это и будет минор.

Алгебраическое дополнение

Алгебраическое дополнение C_ij делает шаг дальше. К минору применяется знаковый множитель, зависящий от позиции (i, j):

Алгебраическое дополнение

Множитель (-1)^(i+j) либо сохраняет знак минора, либо меняет его на противоположный — в зависимости от позиции в матрице.

Если i + j чётно, то (-1)^(i+j) = +1, и алгебраическое дополнение равно минору. Если i + j нечётно, то (-1)^(i+j) = -1, и знак минора изменяется на противоположный.

Шахматный узор знаков

Чередование знаков образует по всей матрице «шахматный» рисунок:

Шахматный узор

В левом верхнем углу всегда стоит знак +. Дальше знаки чередуются во всех направлениях. По этому узору сразу видно, будет ли соответствующее дополнение добавляться к определителю или вычитаться.

Формула разложения по дополнениям

Вот формула, которую вы ждали.

Разложение по строке i:

Разложение по строке i

Разложение по столбцу j:

Разложение по столбцу j

Проще говоря, вы умножаете каждый элемент выбранной строки или столбца на его алгебраическое дополнение, а затем складываете всё вместе.

Символы a_ij — это элементы матрицы. А C_ij — соответствующие им алгебраические дополнения. Перемножьте их, просуммируйте — и получите определитель.

Не важно, какую строку или какой столбец вы выберете. Разложение по первой строке даст тот же результат, что и по третьей строке или по второму столбцу. Определитель — фиксированное свойство матрицы; путь разложения — лишь ваш выбор.

Однако от выбора зависит объём работы. Строка или столбец с большим числом нулей означает меньше дополнений для вычисления. Если в строке два нуля и три ненулевых элемента, нужно считать дополнения только для этих трёх — нули не вносят вклад в сумму. Всегда просматривайте матрицу на наличие нулей перед выбором строки или столбца для разложения.

Пошагово: как работает разложение по дополнениям

Разложение по дополнениям всегда следует одному и тому же трёхшаговому процессу.

Шаг 1. Выберите строку или столбец. Просмотрите матрицу и выберите строку или столбец с наибольшим числом нулей. Меньше ненулевых элементов — меньше дополнений для расчёта.

Шаг 2. Для каждого ненулевого элемента в этой строке или столбце:

• Вычислите минор M_ij — удалите строку i и столбец j, затем возьмите определитель оставшейся матрицы.

• Примените знаковый множитель (-1)^(i+j), используя «шахматный» узор, чтобы получить дополнение C_ij.

• Умножьте элемент a_ij на его дополнение C_ij.

Шаг 3. Просуммируйте все произведения.

Определитель

Это и есть ваш определитель.

Если какие-либо из ваших подматриц больше 2×2, повторяйте тот же процесс для них, пока не сведёте всё к определителям 2×2 — их можно посчитать напрямую по формуле ad - bc.

Пример 1: разложение по дополнениям для матрицы 2×2

Свяжем всё на самом простом случае.

Рассмотрим матрицу 2×2:

Пример матрицы 2x2

Разложим по первой строке. Два элемента: a_11 = 3 и a_12 = 1.

• Для a_11 = 3: удаляем строку 1 и столбец 1. Остаётся просто (4). Знаковый множитель (-1)^(1+1) = +1. Значит, C_11 = +4.

• Для a_12 = 1: удаляем строку 1 и столбец 2. Остаётся просто (2). Знаковый множитель (-1)^(1+2) = -1. Значит, C_12 = -2.

Теперь сложим произведения:

Вычисление определителя

Вы заметите, что это совпадает со стандартной формулой для 2×2: ad - bc = (3)(4) - (1)(2) = 10. Разложение по дополнениям и «перемножение диагоналей» — два способа прийти к одному ответу.

Пример 2: разложение по дополнениям для матрицы 3×3

Теперь разберём полный пример 3×3.

Возьмём матрицу:

Пример матрицы 3x3

В первой строке стоит ноль в позиции (1,2), поэтому разложим по первой строке. Этот ноль позволяет полностью пропустить одно дополнение.

Шаг 1. Подготовим разложение

Настройка разложения (1)

Поскольку a_12 = 0, средний член исчезает:

Настройка разложения (2)

Нужно вычислить всего два дополнения. Это выгода от правильного выбора строки.

Шаг 2. Вычислим C_11

Теперь удалим строку 1 и столбец 1. Остаётся следующее:

Первое вычисление

Знак в позиции (1,1) равен (-1)^(1+1) = +1, поэтому C_11 = +2.

Шаг 3. Вычислим C_13

Далее удалим строку 1 и столбец 3. Остаётся следующее:

Второе вычисление

Знак в позиции (1,3) равен (-1)^(1+3) = +1, поэтому C_13 = +11.

Шаг 4. Сложим произведения

Вычисление определителя

Готово: это ваш определитель. Выбрав строку с нулём, вы превратили задачу с тремя дополнениями в задачу с двумя. Работайте с умом.

Как выбрать лучшую строку или столбец

Выбор строки или столбца не меняет результат, но влияет на объём вычислений.

Всегда сначала ищите нули. Каждый ноль в выбранной строке или столбце — это дополнение, которое не нужно считать. В примере 3×3 выше один ноль сократил работу с трёх дополнений до двух. В больших матрицах строка с несколькими нулями может избавить от вычисления множества подопределителей.

Вот несколько моментов, которые стоит запомнить

• Один ноль в строке или столбце — на одно дополнение меньше
• Два нуля — на два дополнения меньше
• Все нули, кроме одного — нужно вычислить только одно дополнение

Чем больше матрица, тем важнее это правило. Наивное разложение по дополнениям для матрицы n×n работает за факториальное время: для 4×4 нужно вычислить четыре определителя 3×3, каждый из которых раскладывается на три определителя 2×2. Это 24 отдельных вычисления до суммирования. Для 5×5 — уже 120.

Для больших матриц разложение по дополнениям — не лучший инструмент. Приведение строк и LU-разложение справляются с большими матрицами намного быстрее. Разложение по дополнениям лучше оставить для случаев 2×2 и 3×3 или для теоретической работы, где нужен символический вид определителя.

Если решаете вручную, уделите пару секунд поиску строки или столбца с наибольшим числом нулей. Это самый простой способ сократить число ошибок в арифметике.

Разложение по дополнениям и рекурсивная структура

Разложение по дополнениям по своей природе рекурсивно.

Чтобы найти определитель матрицы n×n, вы раскладываете по строке или столбцу и вычисляете определители матриц (n-1)×(n-1) размера. Каждая из них раскладывается на матрицы (n-2)×(n-2). Вы продолжаете до уровня 2×2 и решаете напрямую.

Именно эта рекурсивность алгебраически определяет, что такое определитель. Она говорит, что это такое для любого размера матрицы, а не только как его посчитать.

Однако у рекурсии есть цена.

Каждый уровень разложения умножает число подзадач, и для больших матриц вычисления быстро разрастаются. Поэтому численные библиотеки не используют разложение по дополнениям «под капотом». Приведение строк и методы факторизации масштабируются намного лучше.

Для малых матриц и теории рекурсивность — именно то, что нужно. Для всего большего лучше искать другой подход.

Связь с присоединённой матрицей

Алгебраические дополнения — строительный блок обращения матриц. Они нужны не только для вычисления определителей.

Если вычислить дополнение C_ij для каждого элемента матрицы A, вы получите матрицу дополнений C. Транспонируйте её — поменяйте строки и столбцы местами — и получите присоединённую матрицу:

Присоединённая матрица

Отсюда непосредственно следует формула обратной матрицы:

Обратная матрица

Проще говоря, нужно вычислить все дополнения, собрать их в матрицу, транспонировать её, затем разделить на определитель. Это и будет обратная матрица.

Здесь важно помнить две вещи:

1. Это работает только когда det(A) ≠ 0 — нулевой определитель означает, что обратной матрицы не существует
2. Эта формула точна, что делает её полезной для теории и символической алгебры. Для численных вычислений с большими матрицами другие методы быстрее.

Если вы задаётесь вопросом о связи с разложением по дополнениям, просто помните: каждый элемент присоединённой матрицы получается из дополнения, которое вы вычисляете при разложении. Тот же процесс, что даёт определитель, предоставляет всё необходимое для обращения матрицы.

Свойства разложения по дополнениям

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

Запомните четыре свойства:

• Разложение по любой строке или столбцу даёт один и тот же результат. Можно раскладывать по второй строке или третьему столбцу — определитель не изменится. Выбирайте то, где больше нулей
• Определитель линеен по каждой строке. Если умножить строку на константу k, определитель умножится на k. Это непосредственно следует из того, как дополнения умножаются на элементы
• Перестановка двух строк меняет знак определителя на противоположный. Поменяйте строки местами один раз — определитель сменит знак. Дважды — вернётся исходный. Поэтому при операциях со строками нужно тщательно отслеживать знаки
• Если две строки линейно зависимы, определитель равен нулю. Линейная зависимость означает, что одна строка — скалярный множитель другой, или, шире, что строки не порождают всё пространство. Такая матрица вырождена, и обратной у неё нет

Эти свойства позволяют упростить матрицы до разложения — сокращая строки, замечая зависимости и избегая лишних вычислений.

Типичные ошибки

У разложения по дополнениям есть несколько «ловушек», которые встречаются снова и снова. Обратите внимание на следующее.

• Забывают о знаке (-1)^(i+j). Это самая частая ошибка. Минор посчитан верно, умножили на элемент — и ответ неверный, потому что пропустили знаковый множитель. Всегда проверяйте «шахматный» узор перед записью дополнения
• Удаляют не ту строку или столбец при вычислении минора. При вычислении M_ij удаляются строка i и столбец j — те, что соответствуют элементу разложения. Часто ошибочно удаляют не те, особенно в 3×3, где оставшиеся матрицы могут быть похожи
• Слишком рано останавливаются в рекурсии. Если подматрица всё ещё 3×3 или больше, нужно продолжать разложение. Некоторые принимают минор 3×3 за 2×2 и сразу применяют ad - bc
• Арифметические ошибки на рекурсивных шагах. Чем глубже рекурсия, тем больше перемножений и смен знаков. Единственная ошибка на раннем этапе тянется через все последующие шаги. Аккуратно просчитывайте каждый определитель 2×2 перед объединением результатов

Если финальный ответ кажется неверным, в первую очередь перепроверьте знаковый узор и удаление строки/столбца для минора.

Когда использовать разложение по дополнениям

Разложение по дополнениям уместно в нескольких конкретных ситуациях.

Для небольших матриц это самый прямой подход. 2×2 решается мгновенно, 3×3 по силам вручную за пару минут. Начиная с 4×4 и далее число рекурсивных шагов растёт так быстро, что другие методы оказываются быстрее и надёжнее.

Также это основной инструмент для теоретических и символических задач. Если вы доказываете теорему, выводите формулу или вычисляете определитель с переменными вместо чисел, разложение по дополнениям даёт точное символическое выражение. Приведение строк отлично подходит для чисел, но с символами становится громоздким.

Кратко — когда к нему стоит прибегать:

• Вы работаете с матрицей 2×2 или 3×3
• Вам нужен точный символический результат, а не численное приближение
• Вы выполняете доказательство, требующее явного разложения определителя
• Вы формируете интуицию о том, что на самом деле означает определитель

Для больших численных матриц пропустите этот метод. Приведение строк и LU-разложение решают такие задачи гораздо быстрее и с меньшим риском накопления арифметических ошибок. Большинство численных библиотек используют именно их — по этой причине.

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

Заключение

Разложение по алгебраическим дополнениям — это систематический рекурсивный способ вычисления определителя любой квадратной матрицы.

Два базовых элемента — миноры и знаковый узор (-1)^(i+j) — управляют всем процессом. Освойте их — и остальное просто. Выбирайте строку или столбец с нулями, чтобы сократить работу, сведите задачу к определителям 2×2 и просуммируйте результаты.

Помимо определителей, метод связан с присоединённой матрицей и формулой обратной матрицы. Алгебраические дополнения, которые вы вычисляете при разложении, — те же, что образуют adj(A). Поэтому разложение по дополнениям — фундамент для понимания алгебраического обращения матриц.

Для малых матриц и теории это самый прозрачный метод. Для больших численных матриц используйте приведение строк или численную библиотеку.

Если хотите увидеть разложение по дополнениям в действии, запишитесь на наш курс Linear Algebra for Data Science in R.