title | weight | authors | ||
---|---|---|---|---|
Матрицы |
-9 |
|
Определение. Функция
$f(x+y) = f(x) + f(y)$ $f(ax) = a f(x), ; a \in \mathbb{R}$
Например, линейными являются:
- Функция, которая «растягивает» вектор в
$k$ раз:$f(x) = k x$ . - Функция, которая поворачивает вектор на плоскости на угол
$\theta$ . - Функция, которая проецирует трёхмерный вектор на какую-нибудь плоскость.
- Скалярное произведение
$f(x, y) = x \cdot y = \sum x_ky_k$ также линейно по обоим параметрам.
Из одних лишь двух пунктов в определении можно вывести много полезных свойств:
- Сумма линейных функций является линейной функцией.
- Композиция линейных функций
$f(g(x)) = (f \circ g)(x)$ является линейной функцией. - Сумма линейных функций коммутативна:
$f+g = g+f$ . - Сумма линейных функций ассоциативна:
$(f+g)+h = f+(g+h)$ . - Композиция линейных функций ассоциативна:
$(f \circ g) \circ h = f \circ (g \circ h) = f \circ g \circ h$ . - Композиция в общем случае не коммутативна. Пример:
$f(x) = (-x_2, x_1)$ — поворот точки на плоскости на прямой угол,$g(x) = (x_1, 0)$ — проекция на$Ox$ . Почти для всех точек плоскости важен порядок этих двух операций.
Линейная алгебра занимается изучением линейных функций.
Можно показать, что любую линейную функцию
Матрицы представляют собой просто очень компактную запись этих коэффициентов
Каждой линейной функции
Если вектор — это упорядоченный набор скаляров, то матрицу можно рассматривать как вектор векторов. Вектор, в частности, можно представить как матрицу, у которой одна из размерностей равна единице — тогда его называют вектор-столбец либо вектор-строка.
typedef vector<vector<int>> matrix;
Ещё есть тензоры — ими называют все объекты ещё более высокого порядка: векторы матриц (трёхмерный тензор), матрицы матриц (четырёхмерный тензор) и векторы матриц матриц и так далее.
У тензоров есть своя интересная алгебра, но в контекстах, в которых с ними сталкивается обычный программист, никакая алгебра, как правило, не подразумевается, и этот термин используется лишь потому, что в словосочетании «многомерный массив» слишком много букв.
Пусть линейной функции
Читатель может убедиться в этом, аккуратно расписав подстановку формул для
При перемножении матриц руками удобно думать так: элемент на пересечении
Исходное выражение для
Напишем функцию, реализующую матричное умножение:
const int n, k, m;
matrix matmul(matrix a, matrix b) {
matrix c(n, vector<int>(m, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (int t = 0; t < k; t++)
c[i][j] += a[i][t] * b[t][j];
return c;
}
Такая реализация хоть и наиболее простая, но не оптимальная: мы на каждой итерации двигаем указатель для
Существуют способы соптимизировать матричное умножение и сильно дальше — в 50-100 раз по сравнению с наивным — но они выходят далеко за рамки этой статьи. Также наука знает способы способы перемножать матрицы асимптотически быстрее чем
К матрицам не нужно относиться как к табличкам, в которых стоят какие-то числа. Каждой матрице соответствует какая-то линейная функция, как-то преобразующая вектора. Центральными объектами линейной алгебры являются именно линейные функции, а не матрицы.
Благодаря этому взаимно однозначному соотношению все ранее упомянутые свойства линейных функций переносятся и на матрицы:
- Сумма матриц
$A$ и$B$ тоже является матрицей:$C = A+B: C_{ij} = A_{ij} + B_{ij}$ . - Сумма матриц коммутативна:
$A+B = B+A$ . - Сумма матриц ассоциативна:
$(A+B)+C = A+(B+C)$ . - Умножение матриц ассоциативно:
$(AB)C = A(BC) = ABC$ . - Умножение матриц в общем случае не коммутативно.
Матрицы не обязательно рассматривать только для действительных чисел — все эти свойства переносятся на произвольные поля: множества, для которых определены
Самый популярный класс таких полей — остатки по простому модулю. В частном случае, когда xor
в качестве сложения и and
в качестве умножения. Это позволяет эффективно хранить матрицы в виде битовых последовательностей.
Матрица «увеличь всё в два раза»:
Матрица «поменяй
Матрица поворота на угол
Матрица проецирования на плоскость
Матрица «ничего не делай», также известная как единичная матрица:
Единичную матрицу обычно обозначают как