Рубрика «матрицы» - 2

Доступно о кватернионах и их преимуществах - 1

От переводчика: ровно 175 лет и 3 дня назад были изобретены кватернионы. В честь этой круглой даты я решил подобрать материал, объясняющий эту концепцию понятным языком.

Концепция кватернионов была придумана ирландским математиком сэром Уильямом Роуэном Гамильтоном в понедельник 16 октября 1843 года в Дублине, Ирландия. Гамильтон со своей женой шёл в Ирландскую королевскую академию, и переходя через Королевский канал по мосту Брум Бридж, он сделал потрясающее открытие, которое сразу же нацарапал на камне моста.

$i^2=j^2=k^2=ijk=-1$

Доступно о кватернионах и их преимуществах - 3

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

В этой статье я постараюсь объяснить концепцию кватернионов простым для понимания образом. Я объясню, как можно визуализировать кватернион, а также расскажу о разных операциях, которые можно выполнять с кватернионами. Кроме того, я сравню использование матриц, углов Эйлера и кватернионов, а затем попытаюсь объяснить, когда стоит использовать кватернионы вместо углов Эйлера или матриц, а когда этого делать не нужно.
Читать полностью »

Введение

Ввиду того, что при решении задач оптимизации, дифференциальных игр, и в 2D и 3D расчётах, а вернее при написании софта, который проводит вычисления для их решения одними из наиболее часто выполняемых операций являются векторно-матричные преобразования типа $aX+bY$, где $a,b$ — скалярные значения, $X, Yin R^n$ — вектора или матрицы размерности $R^{ntimes m}$.
Собственно вот такие:
image
(источник).

Так, чтобы не углубляться в теорию оптимизации за примерами достаточно вспомнить формулу численного интегрирования Рунге-Кутты четвёртого порядка:

$Y_{n+1}=Y_n+frac{h}{6}(k_1 + 2 k_2 + 2 k_3+k_4),$

где $Y_i$ — очередное значение интегрируемой функции $f(t,Y)$ $h$ — шаг метода, а $k_i$, $i=1..4$ — значения интегрируемой функции в некоторых промежуточных точках — в общем случае векторах.

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

  • сложение и вычитание — более быстрые;
  • умножение и деление — более медленные.

О сложности вычислений хорошо написано в соответствующем курсе МФТИ.

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

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

Читать полностью »

В этой статье рассматривается проектирование типов для работы с объектами линейной алгебры: векторами, матрицами, кватернионами. Показано классическое применение механизма перегрузки стандартных операций, использование приёма «Copy On Write» и аннотаций.
Читать полностью »

На Тостере иногда встречаются вопросы о том, как научиться думать как программист. Год назад я ради развлечения решил написать программу которая решает всем хорошо известную задачку — головоломку о волке, козе и капусте. В англоязычных источниках известную как river crossing puzzle.

В этом посте я представлю вам пример мыслительного процесса от задачи к ee алгоритмическому решению.
Читать полностью »

Это заметка о том, что на основании алгоритма генерации спектров (о котором было рассказано в статье «Спектроскоп Салтана...») создан тестовый сервис, обратиться к которому может любой желающий.
Спектроскоп-калейдоскоп - 1
Под катом — инструкция по использованию сервиса и его возможностей.
Читать полностью »

image
В городе Куэрнавака в Мексике «шпионская» сеть повышает эффективность автобусного парка. В результате расписание отбытия автобусов везде соответствует шаблону «универсальности»

В 1999 году, сидя на автобусной остановке в городе Куэрнавака в Мексике, чешский физик Петр Шеба [Petr Šeba] заметил людей, дававших водителю автобуса кусочки бумаги в обмен на деньги. Он обнаружил, что это было не проявление организованной преступности, но другая «теневая» торговля: каждый водитель платил «шпиону», отмечавшему, когда предыдущий автобус отошёл от остановки. Если он отошёл недавно, то водитель этого автобуса замедлялся, чтобы на следующей остановке успели собраться пассажиры. Если тот автобус отошёл уже давно, водитель ускорялся, чтобы его не обогнали другие автобусы. Такая система максимизировала прибыль водителей. Что и дало Шебе идею.

«Мы подумали, что наблюдаем ситуацию, чем-то напоминающую хаотические квантовые системы», пояснил соавтор Шебы, Милан Крбалек [Milan Krbálek].
Читать полностью »

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

Под катом — расшифровка и большинство слайдов.

Читать полностью »

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

Сколько существует разных способов представить обыкновенный поворот в трехмерном пространстве? Большинство людей, когда-либо занимавшихся 3D-графикой или 3D-моделированием, сходу назовут три основных широко распространенных варианта:

  • Матрица поворота 3x3;
  • Задание поворота через углы Эйлера;
  • Кватернионы.

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

  • Ось поворота и угол.

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

Не так давно в процессе разработки редактора 2D-графики возникла задача разложить матрицу аффинного преобразования на плоскости, на произведение матриц простых преобразований с тем, чтобы отобразить их пользователю и предложить какую-то более-менее адекватную интерпретацию того, что произошло с объектом на канвасе. Честно говоря, эта задача вызвала у меня определенные трудности. Университет я закончил уже давно, и мне было непонятно, а возможно ли это сделать в принципе, учитывая, что исходная матрица могла быть результатом произвольной последовательности сдвигов, масштабов, поворотов, и переносов, причем каждое преобразование могло иметь свой произвольный центр. И, во-вторых, непонятно было, как найти семь параметров, имея всего шесть коэффициентов матрицы. Ключом к решению этой задачи оказалась статья "Разложение матрицы центроаффинного преобразования для нормализации изображения"¹, в которой рассматривается такая же задача, но без учета преобразования переноса и для преобразований относительно центра координат. Далее я фактически просто адаптирую результаты этой статьи с учетом переноса и для произвольного центра преобразований.Читать полностью »

Предисловие: Я пишу на Python более 6 лет и могу назвать себя профессионалом в этом языке. Недавно я даже написал о нем книгу. Однако последние 8 месяцев я переключился на D и уже 4 месяца активно участвую в разработке этого языка по части расширения стандартной библиотеки Phobos. Так же я участвовал в код-ревью модуля std.ndslice о котором и пойдет речь.

std.ndslice так же как и Numpy предназначен для работы с многомерными массивами. Однако в отличие от Numpy ndslice имет крайне низкий оверхэд так как базируется на ranges (диапазонах), которые используются в штатной библиотеке повсеместно. Ranges позволяют избежать лишние процедуры копирования, а так же позволяют красиво организовать ленивые вычисления.

В этой статье мне хотелось бы рассказать о том какие преимущества std.ndslice дает по сравнению с Numpy.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js