Линейная алгебра — программируем с Numpy(ч .2)

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

Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.
А на YouTube-канале ты найдешь обучающие видео по программированию. Подписывайся!

Миноры порядка k

Дана матрица размером n \times n.

    \[A_{n \times n} = \begin{pmatrix}a_{11} & a_{12} & \ldots & a_{1n}\\a_{21} & a_{22} & \ldots & a_{2n}\\\vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \ldots & a_{nn}\\\end{pmatrix}\]

Def. Зафиксируем k (1 \le k \le n): i_1, i_2, \ldots, i_k и k столбцов: j_1, j_2, \ldots, j_k. Определитель матрицы, которая является пересечением выбранных строк и столбцов называется минором порядка k: M_{j_1, j_2, \ldots, j_k}^{i_1, i_2, \ldots, i_k}.

Пример.

    \[A_{4 \times 4} = \begin{pmatrix}1 & 2 & -3 & 4\\1 & 0 & -1 & 2\\3 & 2 & -2 & 5\\0 & 1 & 4 & 8\\\end{pmatrix}\]


    \[M_{2, 3}^{2, 4} = \begin{vmatrix}0 & -1\\1 & 4\\\end{vmatrix}\]

Минор, который является определителем матрицы, состоящей из пересечения всех остальных строк и столбцов, является дополняющей минором n - k минором.

    \[\overline{M}_{2, 3}^{2, 4} = \begin{vmatrix}1 & 4\\3 & 5\\\end{vmatrix}\]

Def. Алгебраическим дополнением минора называют

    \[\overline{A}^{i_1, i_2, \ldots, i_k}_{j_1, j_2, \ldots, j_k} = (-1)^{\sum^{k}_{n=1} i_n + \sum^{k}_{n=1} j_n} \cdot \overline{M}_{j_1, j_2, \ldots, j_k}^{i_1, i_2, \ldots, i_k}\]

Теорема Лапласа

Th Лапласа. Фиксируем k строк матрицы. Тогда определитель этой матрицы равен сумме всех возможных произведений миноров порядка k на этих строках с их алгебраическими дополнениями.

    \[det A = \sum_{j_1 \lt \ldots \lt j_k} M_{j_1, j_2, \ldots, j_k}^{i_1, i_2, \ldots, i_k} \cdot A_{j_1, j_2, \ldots, j_k}^{i_1, i_2, \ldots, i_k}.\]

Пример.

    \[\begin{vmatrix}1 & 2 & 3 & 4\\2 & 0 & 0 & 5\\1 & 3 & 4 & 2\\1 & 0 & 0 & -1\\\end{vmatrix} = \sum_{j_1 < j_2} M^{2, 4}_{j_1, j_2} \cdot A^{2, 4}_{j_1, j_2} = M^{2, 4}_{1, 2} \cdot A^{2, 4}_{1, 2} + M^{2, 4}_{1, 3} \cdot A^{2, 4}_{1, 3} +\]

    \[+ M^{2, 4}_{1, 4} \cdot A^{2, 4}_{1, 4} + M^{2, 4}_{2, 3} \cdot A^{2, 4}_{2, 3} + M^{2, 4}_{2, 4} \cdot A^{2, 4}_{2, 4} + M^{2, 4}_{3, 4} \cdot A^{2, 4}_{3, 4} =\]


    \[= \begin{vmatrix}2 & 5\\1 & -1\\\end{vmatrix} \cdot (-1)^{2 + 4 + 1 + 4} \cdot\begin{vmatrix}2 & 3\\3 & 4\\\end{vmatrix} = (-7) \cdot (-1) \cdot -1 = -7\]

Метод Гаусса вычисления определителя

Последней темой, которую мы затронем в этой статье, станет метод Гаусса вычисления определителя.

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

Сразу стоит отметить, что если a_{I1} = 0 \forall i, то определитель матрицы равен нулю. Далее мы производим следующую операцию:

    \[a_i = a_i - \frac{a_{i1}}{a_{11}} \cdot a_i, (i > 1)\]

В следствии, a_{i1} становится равен нулю. Таким же образом далее выполняем операцию для i > 2, только вместо a_{11} выбираем a_{22}. Если же a_{ii} равен нулю, мы меняем местами строки и меняем знак определителя.

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

Пример.

    \[\begin{vmatrix}1 & 2 & -1\\2 & 4 & 2\\1 & 3 & 0\\\end{vmatrix} = \begin{vmatrix}1 & 2 & -1\\0 & 0 & 4\\1 & 3 & 0\\\end{vmatrix} = \begin{vmatrix}1 & 2 & -1\\0 & 0 & 4\\0 & 1 & 1\\\end{vmatrix} = - \begin{vmatrix}1 & 2 & -1\\0 & 1 & 1\\0 & 0 & 4\\\end{vmatrix} = -4.\]

Программируем на Python

Реализуем функционал вычисления определителя квадратной матрицы, используя Python.

def det(matrix:np.ndarray) -> float:
    matrix = np.copy(matrix).astype('float32') 
    minus = False 

    if len(matrix.shape) != 2 or matrix.shape[0] != matrix.shape[1]: 
        raise TypeError('Matrix has to be square.') 

    for i in range(matrix.shape[0] - 1): 
        for j in range(matrix.shape[0] - 1, i, -1): 
             if matrix[j - 1][i] != 0: 
                 matrix[j] -= (matrix[j][i] / matrix[j - 1][i]) * matrix[j - 1] 
             else: 
                 buffer = np.copy(matrix[j - 1]) 
                 matrix[j - 1] = matrix[j] 
                 matrix[j] = buffer 
                 minus = 1 - minus 

     prod = np.prod(np.diagonal(matrix)) 
     return -prod if minus else prod

Разберём, что поэтапно выполняется в функции. Сначала мы копируем исходную матрицу и приводим её к типу 'float32'. Далее следует проверка, является ли матрица квадратной. После мы выполняем алгоритм, при чём при при смене строк местами меняем знак определителя.

После нам остается всего лишь вычислить произведение элементов главной диагонали и выбрать корректный знак.

Протестируем на матрице из примера выше.

matrix = np.array([[1, 2, -1],
                   [2, 4, 2],
                   [1, 3, 0]])
print(det(matrix), np.linalg.det(matrix))

- 4.0 -4.0

Всё работает прекрасно. На этом наш очередной шаг в мир линейной алгебры подходит к концу.

Заключение

Сегодня мы разобрали такие понятия из раздела «Линейная алгебра», как минор, алгебраическое дополнение и метод Гаусса вычисления определителя квадратной матрицы. Далее на изучение следует ещё очень много вещей, и со всем мы разберёмся.

Советую прочитать статью про нашу авторскую разработку: «Анализ данных групп во Вконтакте»,

А также подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.

Похожие записи

We use cookies to ensure that we give you the best experience on our website.