На этом шаге мы напомним основные операции с матрицами и векторами.
Матрица - прямоугольная таблица из чисел (или элементов других типов данных - символьных, логических и т. д.), состоящая из строк и столбцов. Формально матрица A размерности n*m содержит n строк и m столбцов чисел, где n ≥ 1 и m ≥ 1. Обычно матрицы заключаются в квадратные или круглые скобки:
Если одна из размерностей равна 1, то такой математический объект называют вектором. Если же обе размерности равны 1, то объект становится скаляром, то есть числом.
Результатом транспонирования матрицы A размерности n*m является матрица AT размерности m*n, строками которой выступают столбцы матрицы A (а столбцами - строки A). Например, если
Матрицы (и векторы) можно складывать и умножать. Сумма A + B - это матрица, элементы которой равны ai,j + bi,j. Иными словами, матрицы (и векторы) складываются поэлементно. Поэтому A и B должны иметь одинаковую размерность. Типичный пример суммы векторов:
(4, -1, 2) + (2, 3, -7) = (6, 2, -5).
Умножение матриц гораздо сложнее сложения. Пусть а и b - два n-мерных вектора (столбца). Их скалярное произведение aTb (в других обозначениях - a⋅b или (a,b)) - определяется как сумма их поэлементных произведений:
n aTb = ∑ ai * bi (3.14) i=1
Векторы размерности n (то есть определённые в пространстве Rn) имеют также геометрическую интерпретацию. Можно показать, что
aTb = | a | * | b | * cos(α), (3.15)
__________________ | а | = √(a12 +... + an2). (3.16)
Если A и B - матрицы размерностей n*m и m*p соответственно, то их произведение C = A * B - матрица размерности n*p, элементы которой определяются как
m ci,j = ai,1 * b1,j + ai,2 * b1,2 + ... + ai,m * bm,j = ∑ ai,k * bk,j k=1
При этом число столбцов A (m) должно совпадать с числом строк B. Элемент с, равен скалярному произведению i-й строки A и j-го столбца B (которые можно считать векторами). Например, результатом произведения
Векторы можно также считать точками. Геометрически сложение двух векторов u и v можно понимать как новый вектор, конечная точка которого - результат "соединения" u и v, как показано на рисунке 1(a).
Рис.1. Геометрическая интерпретация сложения и вычитания векторов
Отсюда следует, что вектор, который начинается в конечной точке u и заканчивается в конечной точке v, есть вектор v - u, как показано на рисунке 1(b).
Наконец, двумерный вектор можно повернуть против часовой стрелки на а градусов (или радиан) путём умножения его на матрицу "поворота":
⌈ cos(α) -sin(α) ⌉ R = (3.17) ⌊ sin(α) cos(α) ⌋
Рис.2. Матрица поворота (против часовой стрелки)
На следующем шаге мы перейдем к временной сложности вычислений.