НОРМАЛИЗОВАННЫЙ ВЕКТОР

Время на прочтение

В настоящий момент появилось достаточно большое количество библиотек дополненной реальности с богатым функционалом (ARCore, ARKit, Vuforia). Тем не менее я решил начать свой открытый проект, попутно описывая как это работает изнутри. Если повезет, то позже получится добавить какой-то особый интересный функционал, которого нет в других библиотеках. В качестве целевых платформ пока возьмем Windows и Android. Библиотека пишется на C++, и сторонние библиотеки будут задействованы по минимуму, т.е. преимущественно не будет использовано ничего готового. Фокус в статьях будет направлен на алгоритмы и математику, которые постараюсь описать максимально доступно и подробно. В этой статье пойдет речь про основы векторной алгебры.

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

Вектора — это частный случай матриц, состоящие либо из одного столбца, либо из одной строки. Когда мы говорим о векторе, обычно имеется вектор-столбец

. Но записывать вектор как столбец неудобно, поэтому будем его транспонировать —

Длина вектора

Первое, что мы рассмотрим — получение длины вектора —

— значение длины,

— наш вектор. Для примера возьмем двумерный вектор:

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

— это длины катетов, а

— длина его гипотенузы. По теореме Пифагора получается, что

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

Скалярное произведение

Скалярное произведение векторов — это сумма произведение их компонентов:

. Но так как мы знаем, что вектора — это матрицы, то тогда удобнее записать это в таком виде:

. Это же произведение можно записать в другой форме:

— угол между векторами

(для двумерного случая эта формула доказывается через теорему косинусов). По этой формуле можно заключить, что скалярное произведение — это мера сонаправленности векторов. Ведь, если

— это просто произведение длин векторов. Так как

— не может быть больше 1, то это максимальное значение, которые мы можем получить, изменяя только угол

. Минимальное значение

будет равно -1, и получается при

, т.е. когда вектора смотрят в противоположные направления. Также заметим, что при

, а значит какие бы длины не имели вектора

, все равно

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

Проекция вектора на другой вектор

Возьмем два вектора:

Вектора — это направления, поэтому их начало лежит в начале координат. Обозначим ключевые точки:

— начало координат,

— конечная точка вектора

В геометрическом смысле мы ищем такой

, чтобы конечная точка вектора (обозначим ее как —

) была ближайшей точкой к точке

, лежащей на прямой

Иначе говоря, мы хотим найти составляющую

, т.е. такое значение

Расстояние между точками

будет минимальным, если

. Получаем прямоугольный треугольник —

. Мы знаем, что

по определению косинуса через соотношение сторон прямоугольного треугольника
(

— прилежащий катет).
Также возьмем скалярное произведение

. Отсюда следует, что

. А значит

Тут вспоминаем, что

— это искомый вектор

, и получаем

. Умножаем обе части на

и получаем —

. Теперь мы знаем длину

отличается от вектора

длинной, но не направлением, а значит через соотношение длин можно получить:

. И мы можем вывести финальные формулы:

Нормализованный вектор

Хороший способ упростить работу над векторами — использовать вектора единичной длины. Возьмем вектор

и получим сонаправленный вектор

единичной длины. Для этого вектор разделим на его длину:

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

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

Хорошим преимуществом нормализованных векторов является то, что сильно упрощается формула проекции (т.к. длина равна 1, то она сокращается). Проекция вектора

Матрица поворота двумерного пространства

Предположим у нас есть некая фигура:

Чтобы ее нарисовать, заданы координаты ее вершин, от которых строятся линии. Координаты заданы в виде набора векторов следующим образом

. Наша координатная сетка задана двумя осями — единичными ортогональными (перпендикулярными) векторами. В двумерном пространстве можно получить два перпендикулярных вектора к другому вектору такой же длины следующим образом:

— левый и правый перпендикуляры. Берем вектор, задающим ось

— левый к нему перпендикуляр —

.
Выведем новый вектор, получаемый из наших базисный векторов:

Теперь попробуем как-то изменить нашу фигуру — повернем ее на угол

. Для этого повернем векторы

, задающих оси координат. Поворот вектора

задается косинусом и синусом угла —

. А чтобы получить вектор оси

, возьмем перпендикуляр к

. Выполнив эту трансформацию, получаем новую фигуру:

Теперь мы говорим о нескольких системах координат — базовой системы координат (назовем ее мировой), и локальной для нашего объекта (которую мы поворачивали). Удобно объединить наш набор векторов в матрицу —

В итоге —

, составляющая ортонормированный базис и описывающая поворот, называется матрицей поворота.

Также матрица поворота имеет ряд полезных свойств, которые следует иметь ввиду:

Теперь попробуем повернуть наш объект два раза, первый раз на угол

, второй раз на угол

. Матрицу, полученную из угла

, обозначим как

, из угла

. Распишем наше итоговое преобразование:

. И из двух операций мы получили одну. Так как поворот — это линейное преобразование (описали ее при помощи одной матрицы), множество преобразований можно описать одной матрицей, что сильно упрощает над ними работу.

Масштабирование в двумерном пространстве

Масштабировать объект достаточно просто, нужно только умножить координаты точек на коэффициент масштаба:

. Если мы хотим масштабировать объект на разную величину по разным осям, то формула принимает вид:

. Для удобства переведем операцию в матричный вид:

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

Сначала поворот, а затем масштабирование по осям:

Сначала масштабирование по осям, а затем поворот:

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

Хотя в данном случае, если

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

Векторное произведение векторов

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

Для примера возьмем два трехмерных вектора —

. И в результате векторного произведения получим

Визуализируем данную операцию:

Здесь наши вектора

. Вектора начинаются с начала координат, обозначенной точкой

. Конечная точка вектора

. Параллелограмм из определения формируются точками

. Координаты точки

находим как —

. В итоге имеем следующие соотношения:

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

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

, и мы раскладываем определить по строке как сумму определителей миноров исходной матрицы

Некоторые удобные свойства данного произведения:

Матрица поворота трехмерного пространства.

С тем, как формировать матрицу в двумерном пространстве мы разобрались. В трехмерном она формируется уже не двумя, а тремя ортогональными векторами —

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

и опорный вектор для оси

. Сам алгоритм:

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

. Однако, работать с ними не очень то просто. Если попробовать выразить итоговый вектор напрямую через эти повороты, то получим довольно объемную формулу, состоящую из синусов и косинусов наших углов. Есть еще пара проблем с этими углами. Первая проблема — это то, что сами по себе углы не задают однозначного поворота, так как результат зависит от того, в какой последовательности происходили повороты —

или как-то еще. Углы Эйлера — это последовательность поворотов, а как мы помним, смена порядка трансформаций меняет итоговый результат. Вторая проблема — это gimbal lock.

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

Существуют разные способы задания поворота в трехмерном пространстве, и каждый имеет свои плюсы и минусы:

Поворот вектора вокруг заданной оси

Теперь рассмотрим операцию, позволяющую реализовать поворот вектора вокруг оси.

— описывающий ось, вокруг которой нужно повернуть вектор

. Результирующий вектор обозначим как

мы можем разложить сумму векторов: вектора, параллельный к вектору

, и вектора, перпендикулярному к вектору к вектору

— это проекция вектора

— нормализованный вектор, то:

, которая принадлежит оси вращения (

) не измениться во время вращения. Повернуть нам нужно только

в плоскости перпендикулярной к

, Обозначим этот вектор как

. Тогда наш искомый вектор —

можем найти следующим образом:

Для того, чтобы повернуть

, выведем оси

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

. Один ортогональный вектор у нас уже есть —

, нормализуем его и обозначим как ось

Теперь получим вектор оси

. Это должен быть вектор, ортогональный к

(т.е. и к

). Получить его можно через векторное произведение:

. По свойству векторного произведения

будет равно площади параллелограмма, образуемого двумя исходными векторами (

). Так как вектора ортогональны, то у нас будет не параллелограмм, а прямоугольник, а значит

.
Поворот двумерного вектора

можно получить через синус и косинус —

в координатах полученной плоскости сонаправлен с осью

, то он будет равен

. Этот вектор после поворота —

. Отсюда можем вывести:

Теперь мы можем получить наш искомый вектор:

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

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

Напоминаю, что матрица поворота представляет собой три базисных вектора

, а углы Эйлера — три последовательных поворота вокруг осей

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

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

Также можно отдельно вывести матрицы вращения по каждой из осей

соответственно) и получить итоговую матрицу последовательным их умножением:

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

Итак, с вращением объекта разобрались. Переходим к остальным трансформациям.

Масштабирование в трехмерном пространстве

Все тоже самое что и двумерном пространстве, только матрица масштабирования принимает вид:

Перемещение объекта

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

Теперь мы умеем масштабировать объект по осям, поворачивать его и перемещать.
Объединим все одной формулой:

Чтобы упростить формулу, мы можем, как уже делали ранее, объединить матрицы

. В итоге наше преобразование описывает матрица

. Объединение вектора

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

Заключение

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

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

Об этой статье

Для многих начинающих исследователей данных линейная алгебра становится камнем преткновения на пути к достижению мастерства в выбранной ими профессии.

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

Произведения векторов

Для двух векторов x, y ∈ ℝⁿ их скалярным или внутренним произведением xᵀy

называется следующее вещественное число:

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

Для двух векторов x ∈ ℝᵐ, y ∈ ℝⁿ (не обязательно одной размерности) также можно определить внешнее произведение xyᵀ ∈ ℝᵐˣⁿ. Это матрица, значения элементов которой определяются следующим образом: (xyᵀ)ᵢⱼ = xᵢyⱼ, то есть

След

Следом квадратной матрицы A ∈ ℝⁿˣⁿ, обозначаемым tr(A) (или просто trA), называют сумму элементов на ее главной диагонали:

След обладает следующими свойствами:

Нормы

Норму ∥x∥ вектора x можно неформально определить как меру «длины» вектора. Например, часто используется евклидова норма, или норма l₂:

Заметим, что ‖x‖₂²=xᵀx.

Другими примерами норм являются норма l₁

и норма l∞

Все три представленные выше нормы являются примерами норм семейства lp, параметризуемых вещественным числом p ≥ 1 и определяемых как

Нормы также могут быть определены для матриц, например норма Фробениуса:

Линейная независимость и ранг

линейно зависимы, так как x₃ = −2xₙ + x₂.

Столбцовым рангом матрицы A ∈ ℝᵐˣⁿ называют число элементов в максимальном подмножестве ее столбцов, являющемся линейно независимым. Упрощая, говорят, что столбцовый ранг — это число линейно независимых столбцов A. Аналогично строчным рангом матрицы является число ее строк, составляющих максимальное линейно независимое множество.

Оказывается (здесь мы не будем это доказывать), что для любой матрицы A ∈ ℝᵐˣⁿ столбцовый ранг равен строчному, поэтому оба этих числа называют просто рангом A и обозначают rank(A) или rk(A); встречаются также обозначения rang(A), rg(A) и просто r(A). Вот некоторые основные свойства ранга:

Ортогональные матрицы

атрица U ∈ ℝⁿˣⁿ называется ортогональной, если все ее столбцы ортогональны друг другу и нормированы (в этом случае столбцы называют ортонормированными). Заметим, что понятие ортогональности имеет разный смысл для векторов и матриц.

Непосредственно из определений ортогональности и нормированности следует, что

Другими словами, результатом транспонирования ортогональной матрицы является матрица, обратная исходной. Заметим, что если U не является квадратной матрицей (U ∈ ℝᵐˣⁿ, n < m), но ее столбцы являются ортонормированными, то UᵀU = I, но UUᵀ ≠ I. Поэтому, говоря об ортогональных матрицах, мы будем по умолчанию подразумевать квадратные матрицы.

Еще одно удобное свойство ортогональных матриц состоит в том, что умножение вектора на ортогональную матрицу не меняет его евклидову норму, то есть

для любых вектора x ∈ ℝⁿ и ортогональной матрицы U ∈ ℝⁿˣⁿ.

Область значений и нуль-пространство матрицы

Областью значений R(A) (или пространством столбцов) матрицы A ∈ ℝᵐˣⁿ называется линейная оболочка ее столбцов. Другими словами,

Нуль-пространством, или ядром матрицы A ∈ ℝᵐˣⁿ (обозначаемым N(A) или ker A), называют множество всех векторов, которые при умножении на A обращаются в нуль, то есть

Квадратичные формы и положительно полуопределенные матрицы

Для квадратной матрицы A ∈ ℝⁿˣⁿ и вектора x ∈ ℝⁿ квадратичной формой называется скалярное значение xᵀ Ax. Распишем это выражение подробно:

• , если для всех ненулевых векторов x ∈ ℝⁿ справедливо неравенство xᵀAx < 0.
• Далее, симметричная матрица A ∈ 𝕊ⁿ называется отрицательно полуопределенной (), если для всех ненулевых векторов x ∈ ℝⁿ справедливо неравенство xᵀAx ≤ 0.

Собственные значения и собственные векторы

Для квадратной матрицы A ∈ ℝⁿˣⁿ комплексное значение λ ∈ ℂ и вектор x ∈ ℂⁿ будут соответственно являться собственным значением и собственным вектором, если выполняется равенство

На интуитивном уровне это определение означает, что при умножении на матрицу A вектор x сохраняет направление, но масштабируется с коэффициентом λ. Заметим, что для любого собственного вектора x ∈ ℂⁿ и скалярного значения с ∈ ℂ справедливо равенство A(cx) = cAx = cλx = λ(cx). Таким образом, cx тоже является собственным вектором. Поэтому, говоря о собственном векторе, соответствующем собственному значению λ, мы обычно имеем в виду нормализованный вектор с длиной 1 (при таком определении все равно сохраняется некоторая неоднозначность, так как собственными векторами будут как x, так и –x, но тут уж ничего не поделаешь).

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