Теперь углубим понимание и перейдём к методам, которые лежат в основе практических вычислений: обратимые матрицы, LU‑разложение и разложение Холецкого. Все эти техники развивают идеи алгоритма Гаусса, позволяя быстрее и надёжнее решать задачи, где матрицы играют ключевую роль.

А начнём мы с понятия обратимой матрицы — одного из фундаментальных кирпичиков линейной алгебры.

Обратимые матрицы

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

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

Следовательно, «деление» матрицы на матрицу (при условии, что она обратима) реализуется как умножение на . Формально операцию деления в матрицах вообще не вводят, поэтому пример выше нужен больше для интуитивного понимания. Также, в отличие от чисел, далеко не каждая матрица является обратимой.

💡Для произвольной матрицы не гарантировано существование обратной матрицы, но если матрица обратима, то существует матрица , удовлетворяющая , и эта матрица единственна.

Свойства:

Пусть является обратимой матрицей, тогда верно:

4. для
6. СЛУ имеет только нулевое решение . Данное свойство является эквивалентным, то есть если оно выполняется, то из этого следует, что и матрица обратима.

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

Теперь, когда мы поняли, как выглядят обратные матрицы и какими свойствами они обладают, самое время научиться их находить. В этом нам поможет алгоритм Гаусса, который мы рассмотрели в предыдущем параграфе.

Нахождение обратной матрицы методом Гаусса

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

Алгоритм:

1. На задачу поиска обратной матрицы можно смотреть как на поиск решения системы линейных уравнений вида: , где — это искомая обратная матрица, а — единичная матрица. Тогда составим расширенную матрицу системы вида .
2. Для матрицы выполним сперва прямой ход алгоритма Гаусса — приведем её к ступенчатому виду, а затем обратный ход алгоритма Гаусса — приведем её к улучшенному ступенчатому виду.
3. После применения алгоритма Гаусса к матрице возможны два случая:
   1. Получили матрицу вида , тогда матрица обратима, а матрица .
   2. Получили матрицу вида , где и у матрицы есть свободные переменные (нулевая строка). Тогда матрица не обратима.

Применим на примере. Рассмотрим матрицу :

Запишем её расширенный вид:

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

Выполним алгоритм Гаусса, сделав следующие элементарные преобразования:

Шаг №1:

Шаг №2:

Шаг №3:

Мы получили матрицу вида , то есть матрица обратима и . Выполним проверку:

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

LU-разложение

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

Cхема Дулитла

Существуют различные виды самого LU-разложения, которые отличаются исходной структурой матриц и . Наиболее популярной является схема Дулитла (Doolittle decomposition), где матрицы и имеют следующую структуру:

Заполнение единицами главной диагонали матрицы () позволяет уменьшить число вычисляемых коэффициентов. Данная схема используется также и в программных пакетах, например в scipy.linalg.lu.

Способы нахождения LU-разложения

Рассмотрим конкретный пример. Пусть дана следующая матрица :

Тогда в общем виде матрицы и выглядят так:

Перемножая и , получаем следующую матрицу:

Сразу можем найти значения следующих элементов:

Далее будем шаг за шагом находить значения всех последующих элементов, то есть:

И так далее. Проделав последующие вычисления, получим матрицы:

Выполнив проверку, получим:

Теперь давайте вспомним рассмотренный алгоритм Гаусса и матрицы элементарных преобразований. На самом деле с их помощью также можно найти LU-разложение!

Когда мы выполняем алгоритм Гаусса над матрицей (прямой ход), то путём элементарных преобразований () приводим её к ступенчатому верхнетреугольному виду :

Но мы знаем, что любое элементарное преобразование можно представить как умножение слева на соответствующую матрицу :

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

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

Получим:

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

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

Тогда, чтобы сделать следующий шаг алгоритма Гаусса, нам нужно занулить все элементы в столбце ведущего элемента, стоящие ниже него. Для рассматриваемого примера нужно прибавить первую строку, умноженную на , к третьей строке, что равносильно умножению слева на следующую матрицу :

Теперь ведущим стал элемент , поэтому матрицы и выглядят следующим образом:

Мы получили, что — уже верхнетреугольная ступенчатая матрица, и на этом прямой ход алгоритма завершен. Запишем его в матричном виде:

Теперь, если мы умножим обе части выражения на матрицу , то получим:

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

Найдем матрицы , и их произведение:

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

где:

• — нижнетреугольная матрица;
• — верхнетреугольная матрица;
• — матрица перестановки строк;
• — исходная матрица.

Умножив обе части равенства на , слева получим:

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

Найдем итоговое разложение матрицы :

Итак, мы рассмотрели как можно найти LU-разложение. Теперь давайте попробуем понять, всегда ли можно представить матрицу в виде LU-разложения и если да, то единственное ли такое разложение.

Существование и единственность LU-разложения

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

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

Если мы рассмотрим LU-разложение, то для любой обратимой диагональной матрицы можно записать:

При этом:

• — нижнетреугольная матрица;
• — верхнетреугольная матрица

Таким образом, мы получаем, что LU-разложение может быть не единственным. Однако в схеме Дулитла мы фиксируем диагональные элементы матрицы равными единице (), что приводит к единственности разложения при условии, что матрица обратима.

Решение СЛУ

Очень хороший пример использования LU-разложения — это решение СЛУ. Основное преимущество данного разложения над методом Гаусса заключается в том, что, получив однажды представление исходной матрицы в виде произведения двух треугольных, мы можем очень быстро решать СЛУ при изменении правой части — вектора свободных членов .

Как мы помним, система в матричном виде задаётся как . Тогда, воспользовавшись PLU-разложением, получаем:

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

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

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

Рассмотрим конкретный пример, пусть дана следующая СЛУ:

Выполним PLU-разложение и получим следующие матрицы:

Решим систему :

Выполнив прямую подстановку, получим:

• Из первого уравнения:
• Из второго уравнения:
• Из третьего уравнения:

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

Решим систему :

Выполнив обратную подстановку, получим:

• Из третьего уравнения:
• Из второго уравнения:
• Из первого уравнения:

Таким образом, получаем решение:

Итак, мы рассмотрели, как с помощью LU-разложения можно решать СЛУ. Если требуется решить несколько систем с одной и той же матрицей коэффициентов AA, то вычисление LU-разложения (однократно) с последующей подстановкой для разных правых частей значительно экономит ресурсы.

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

Нахождение обратной матрицы

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

где — вектор-столбец матрицы , а — вектор-столбец матрицы .

Для каждого :

Записывается система вида:

Используя PLU-разложение , переписываем эту систему как:

Далее воспользуемся схемой применения PLU-разложения для решения СЛУ:

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

В результате для каждого мы находим столбец обратной матрицы .

Давайте рассмотрим конкретный пример, пусть дана обратимая матрица , такая что:

Выполним PLU-разложение и получим следующие матрицы:

Найдем векторы :

Найдём , для этого сперва решим систему :

Теперь решим систему :

По аналогии найдём и , получим:

Теперь соберём обратную матрицу из найденных векторов и выполним проверку:

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

1    import numpy as np
2    from scipy.linalg import lu, lu_factor, lu_solve, inv
3    
4    # Определяем матрицу A и правую часть b
5    A = np.array([[0, 1, 0],
6                  [1, 1, 2],
7                  [0, 3, 1]], dtype=float)
8    b = np.array([0, 14, 17], dtype=float)
9    
10    # 1. Вычисляем PLU-разложение с помощью lu_factor
11    lu_and_piv = lu_factor(A)
12    print(f"Комбинированная матрица LU: \n {lu_and_piv[0]}")
13    print(f"Индексы перестановок: \n {lu_and_piv[1]}")
14    
15    # 2. Решаем систему Ax = b, используя полученную факторизацию
16    x = lu_solve(lu_and_piv, b)
17    print(f"Решение системы Ax = b: \n {x}")
18    
19    # 3. Вычисляем обратную матрицу A^{-1} с помощью scipy.linalg.inv
20    A_inv = inv(A)
21    print(f"Найденная обратная матрица A^{-1}: \n {A_inv}")
22    
23    # Проверяем, что A * A_inv = E
24    res = np.allclose(np.eye(A.shape[0]), A @ A_inv)
25    print(f"Проверка: 'A * A_inv = E' is {res}")
26    
27    # 4. Матрицы P, L, U можно получить с помощью scipy.linalg.lu
28    P, L, U = lu(A)
29    print(f"Перестановочная матрица P: \n {P}")
30    print(f"Нижнетреугольная матрица L: \n {L}")
31    print(f"Верхнетреугольная матрица U: \n {U}")
32    
33    # Проверяем, что A = PLU
34    res = np.allclose(A, P @ L @ U)
35    print(f"Проверка: 'A = PLU' is {res}")
36    
37    # Output:
38    # Комбинированная матрица LU: 
39    #  [[ 1.          1.          2.        ]
40    #  [ 0.          3.          1.        ]
41    #  [ 0.          0.33333333 -0.33333333]]
42    # Индексы перестановок: 
43    #  [1 2 2]
44    # Решение системы Ax = b: 
45    #  [-20.   0.  17.]
46    # Найденная обратная матрица A^-1: 
47    #  [[ 5.  1. -2.]
48    #  [ 1.  0.  0.]
49    #  [-3.  0.  1.]]
50    # Проверка: 'A * A_inv = E' is True
51    # Перестановочная матрица P: 
52    #  [[0. 0. 1.]
53    #  [1. 0. 0.]
54    #  [0. 1. 0.]]
55    # Нижнетреугольная матрица L: 
56    #  [[1.         0.         0.        ]
57    #  [0.         1.         0.        ]
58    #  [0.         0.33333333 1.        ]]
59    # Верхнетреугольная матрица U: 
60    #  [[ 1.          1.          2.        ]
61    #  [ 0.          3.          1.        ]
62    #  [ 0.          0.         -0.33333333]]
63    # Проверка: 'A = PLU' is True

Итак, мы подробно рассмотрели LU-разложение и возможности его применения в различных задачах. На практике данный алгоритм достаточно популярен и используется в библиотеках scipy и numpy через LAPACK‑рутины. Например, dgetrf для факторизации и dgetri для вычисления обратной матрицы.

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

Давайте разберём, в чём его особенности и как его находить.

Разложение Холецкого

В анализе данных часто возникает задача эффективного и надёжного решения систем линейных уравнений, вычисления определителей и обратных матриц. Среди классических методов выделяются метод Гаусса и LU‑разложение, которые работают с произвольными обратимыми матрицами. Однако для специального класса матриц существует более экономный и устойчивый при численных расчётах метод — разложение Холецкого.

Применимость

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

Давайте рассмотрим, что такое симметричные положительно определённые матрицы. Для того чтобы дать определение положительной определённости, мы немного забежим вперёд и воспользуемся определителем (это числовая характеристика квад­рат­ной матрицы, обладающая рядом важных свойств и имеющая геометрический смысл), о котором мы поговорим в следующем параграфе.

• Симметричность. Матрица называется симметричной, если её элементы зеркально совпадают относительно главной диагонали:

• Положительная определённость. Матрица называется положительно определённой, если для каждого определитель верхней левой подматрицы положителен:

  Для :

  Для :

Способ нахождения разложения Холецкого

Для нахождения элементов искомой матрицы определены рекуррентные формулы:

Вычисление происходит сверху вниз, слева направо, то есть сперва , а затем . Давайте рассмотрим конкретный численный пример. Пусть дана матрица , такая что:

Тогда:

Важно заметить, что разложение Холецкого может быть также использовано для решения СЛУ и нахождения обратной матрицы по аналогии с LU-разложением. Возникает логичный вопрос, а зачем тогда нужно ещё одно разложение?

Как мы сказали ранее, разложение Холецкого может быть применено только для специального класса матриц, и оказывается, что для таких матриц оно работает быстрее, чем LU-разложение.

Так, для получения разложения LU-разложения требуется порядка операций, а для разложения Холецкого — , то есть оно в два раза быстрее. Кроме того, меньшее количество операций ведёт к меньшим накопленным вычислительным погрешностям, что повышает точность и устойчивость полученного разложения.

1    import numpy as np
2    
3    # 1. Задаём A и b
4    A = np.array([[4,12,-16],[12,37,-43],[-16,-43,98]], dtype=float)
5    b = np.array([1,2,3], dtype=float)
6    
7    # 2. Разложение Холецкого
8    L = np.linalg.cholesky(A)  # A = L @ L.T
9    
10    # 3. Решение A x = b
11    y = np.linalg.solve(L, b)       # прямой ход
12    x = np.linalg.solve(L.T, y)     # обратный ход
13    
14    # 4. Обратная матрица и определитель
15    invA = np.linalg.inv(A)
16    
17    # 5. Оформление результатов
18    print('L (Cholesky):', L, sep='\n')
19    print('y:', y, sep='\n')
20    print('x:', x, sep='\n')
21    print('A^{-1}:', invA, sep='\n')
22    
23    # Output:
24    # L (Cholesky):
25    # [[ 2.  0.  0.]
26    #  [ 6.  1.  0.]
27    #  [-8.  5.  3.]]
28    # y:
29    # [ 0.5 -1.   4. ]
30    # x:
31    # [28.58333333 -7.66666667  1.33333333]
32    # A^{-1}:
33    # [[ 49.36111111 -13.55555556   2.11111111]
34    #  [-13.55555556   3.77777778  -0.55555556]
35    #  [  2.11111111  -0.55555556   0.11111111]]

Итак, мы рассмотрели алгоритм разложения Холецкого, а также класс матриц, для которых его можно применять. На практике данный алгоритм относительно популярен и реализован в библиотеках numpy и scipy.

Среди практических применений данного алгоритма можно выделить Гауссовские процессы. В библиотеке scikit-learn данное разложение используется для вычисления и логарифма функции правдоподобия, а также рассматривается его применение на больших данных.

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

Применение СЛУ в анализе данных

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

где:

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

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

Чтобы минимизировать , вычисляют его градиент по и приравнивают к нулю:

Получаем следующее уравнение:

При условии что матрица обратима, решение находится аналитически:

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

Давайте рассмотрим наглядный пример, как решение СЛУ может быть полезно в задаче анализа данных. Представьте, что вы работаете в компании по разработке новых сплавов. Вам поручено создать сплав, который должен иметь заданную плотность и прочность. Для этого необходимо комбинировать три базовых сплава A, B и C. Каждый из них характеризуется известными параметрами (плотностью и прочностью).

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

• плотность: 7.85 г/см³
• прочность: 580 МПа

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

Ранее мы уже разобрали, как можно решать СЛУ в Python:

1import numpy as np
2import scipy
3
4# Матрица коэффициентов
5A = np.array([
6    [1,     1,    1],
7    [8.0,  7.8,  7.7],
8    [560, 580, 600]
9])
10
11# Вектор свободных членов
12b = np.array([1, 7.85, 580])
13
14# Решаем систему уравнений Ax = b
15x = scipy.linalg.solve(A, b)
16
17# Вывод решения
18x_A, x_B, x_C = x
19print(f"Решение системы: x_A = {x_A:.4f}, x_B = {x_B:.4f}, x_C = {x_C:.4f}")
20
21# Output:
22# Решение системы: x_A = 0.5000, x_B = 0.0000, x_C = 0.5000

Получаем значения:

Это означает, что для достижения требуемых параметров (целевой плотности 7.85 г/см³ и прочности 580 МПа) оптимально смешивать сплавы следующим образом:

• 50 % сплава
• 0 % сплава
• 50 % сплава

Итак, в этом параграфе мы познакомились с понятием обратимой матрицы, LU-разложения и увидели, как решения СЛУ могут быть применимы в практических задачах анализа данных. Но это только верхушка айсберга.

В машинном обучении линейная алгебра — это не просто формальность, а основа устойчивой и быстрой работы с моделями.

Вот что особенно важно помнить:

• Умение быстро понять, сколько решений у СЛУ, — это способ диагностики болезней данных: мультиколлинеарности, недоопределённости, плохой обусловленности (condition number). Всё это может привести к нестабильным или бессмысленным результатам, если не распознать проблему вовремя.

• Любая линейная модель в постановке наименьших квадратов в итоге приводит к решению уравнения:

  Золотым стандартом считаются решения через Cholesky или LU-разложение в связке с регуляризацией, особенно когда размерность данных растёт.

• Даже в более сложных моделях — Gaussian Processes, GraphSAGE, PageRank — всё сводится к варианту одной задачи:

Чем глубже вы понимаете структуру таких уравнений, тем проще вам будет работать как с ML-фреймворками, так и с задачами масштабирования на кластере.

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