Main menu
Линейная алгебра

Линейная алгебра (110)

Теорема Перрона-Фробениуса: положительные матрицы и экономика

В линейной алгебре большинство теорем о спектрах матриц (собственных значениях) опираются на их симметрию, ортогональность или вырожденность. Однако в начале XX века математики Оскар Перрон и Фердинанд Фробениус доказали удивительную теорему, опирающуюся исключительно на знаки элементов матрицы. Теорема Перрона-Фробениуса описывает свойства матриц, все элементы которых строго положительны (или неотрицательны). Эта теорема стала настоящим подарком для прикладных наук. Без нее невозможно было бы доказать сходимость алгоритма Google PageRank, рассчитывать стационарные распределения в марковских случайных цепях, анализировать демографические модели роста популяций и балансировать макроэкономические модели межотраслевого баланса.

Подробнее

Проекционные матрицы: ортогональные и косоугольные проекторы

Когда мы стоим на улице в солнечный день, мы отбрасываем тень на асфальт. Тень — это двумерная проекция нашего трехмерного тела на плоскость. В линейной алгебре эта физическая аналогия доведена до математического абсолюта с помощью проекционных матриц (проекторов). Линейный оператор проектирования берет вектор из пространства высокой размерности и жестко «прибивает» его к определенному подпространству (линии, плоскости, гиперплоскости), отсекая всю лишнюю информацию. Проекторы являются важнейшим инструментом в компьютерной 3D-графике (отвечая за рендеринг сцены на плоском экране монитора), в теории обработки сигналов и, конечно, в методе наименьших квадратов, где они помогают находить оптимальные приближения.

Подробнее

Блочные матрицы и формула обращения Фробениуса: разделяй и властвуй

Когда размерность систем линейных уравнений переваливает за тысячи и миллионы неизвестных, прямое применение стандартных матричных алгоритмов становится невозможным даже для современных суперкомпьютеров: данные просто не помещаются в кэш-память процессора. В таких случаях на помощь приходит стратегия «разделяй и властвуй» (divide and conquer), реализуемая в линейной алгебре через аппарат блочных (клеточных) матриц. Блочная матрица — это обычная матрица, разрезанная горизонтальными и вертикальными линиями на подматрицы меньшего размера (блоки). Работа с такими блоками как с едиными математическими объектами позволяет кардинально ускорить вычисления, оптимизировать использование памяти и аналитически обращать огромные матрицы с помощью знаменитой формулы Фробениуса.

Подробнее

Матрица Грама: измерение объемов и проверка независимости

Когда мы работаем с векторами в абстрактных линейных (евклидовых) пространствах, нам необходим математический инструмент для измерения «взаимоотношений» между ними: длин, углов и того, насколько сильно они пересекаются друг с другом. Датский математик Йорген Педерсен Грам ввел конструкцию, которая идеально решает эту задачу. Матрица Грама — это квадратная симметричная матрица, составленная из всех возможных попарных скалярных произведений заданного набора векторов. Эта матрица не только хранит в себе полную метрическую геометрию системы векторов, но и позволяет изящно вычислять многомерные объемы, расстояния от точек до гиперплоскостей и проверять векторы на линейную зависимость без использования метода Гаусса.

Подробнее

Спектральная теорема для симметричных матриц: геометрия и физика

Симметричные матрицы (у которых элементы симметричны относительно главной диагонали, A = A^T) встречаются в математике и физике повсеместно. Они описывают тензоры инерции твердых тел, матрицы напряжений в сопромате, матрицы ковариации в статистике и гамильтонианы в квантовой механике. Столь широкое распространение не случайно: симметричные матрицы обладают невероятно удобными и «красивыми» математическими свойствами, которые объединяются в одну из самых важных теорем всей линейной алгебры — Спектральную теорему. Эта теорема утверждает, что геометрия любого преобразования, заданного симметричной матрицей, сводится к простому масштабированию (растяжению или сжатию) вдоль взаимно перпендикулярных осей.

Подробнее

Метод главных компонент (PCA) с точки зрения линейной алгебры

Мы живем в эпоху Больших Данных, когда объекты часто описываются тысячами параметров: каждый пиксель на фотографии или каждый ген в ДНК пациента является отдельной переменной. Работать с таким массивом измерений напрямую невозможно: алгоритмы захлебываются в вычислениях, а человек не способен визуализировать пространства выше трехмерного. Эту проблему «проклятия размерности» изящно решает Метод Главных Компонент (Principal Component Analysis, PCA), разработанный Карлом Пирсоном. Несмотря на свое статистическое происхождение, PCA является чистейшим триумфом линейной алгебры. Он использует собственные векторы матриц ковариации для поворота координатных осей так, чтобы отделить значимую информацию (сигнал) от случайного шума.

Подробнее

Пространство нуль-пространства и фундаментальная система решений (ФСР)

При решении однородных систем линейных алгебраических уравнений (СЛАУ), где правая часть (вектор свободных членов) полностью состоит из нулей, система всегда имеет как минимум одно решение — тривиальное (все неизвестные равны нулю). Однако главный интерес для науки представляют те случаи, когда матрица системы вырождена, и помимо нулевого вектора существует бесконечное множество ненулевых решений. Множество абсолютно всех векторов, которые обнуляются при умножении на заданную матрицу A, называется ее нуль-пространством или ядром (Ker A). Понимание структуры ядра матрицы позволяет химикам балансировать сложнейшие уравнения реакций, а инженерам-строителям — анализировать степени свободы и внутренние напряжения фермовых конструкций мостов.

Подробнее

Тензорные разложения: CANDECOMP/PARAFAC и Таккера

Сингулярное разложение (SVD) является вершиной анализа двумерных матриц, позволяя находить скрытые факторы и сжимать данные. Но что делать, когда данные имеют более двух измерений? Например, видео (ширина, высота, время), цветные медицинские МРТ-сканы (X, Y, Z) или данные социальных сетей (пользователь, действие, контекст, время). Такие многомерные массивы описываются тензорами высоких рангов. Попытка сплющить тензор в обычную матрицу (матрицизация) приводит к колоссальной потере структурной информации. Для полноценного анализа многомерных данных математики обобщили SVD на многомерный случай, создав два фундаментальных метода: разложение CP (CANDECOMP/PARAFAC) и разложение Таккера. Эти алгоритмы лежат в основе современных рекомендательных систем и хемометрики.

Подробнее

Матрица Гессе: анализ кривизны многомерных функций

Когда мы исследуем функцию одной переменной, первая производная показывает нам скорость роста (наклон), а вторая производная — кривизну графика (выпуклость или вогнутость), что позволяет точно находить максимумы и минимумы. Но как быть с функциями многих переменных, которые описывают сложные многомерные поверхности? Здесь на помощь приходит матрица Гессе (гессиан), названная в честь немецкого математика Людвига Отто Гессе. Гессиан — это квадратная симметричная матрица, состоящая из всех возможных вторых частных производных скалярной функции. В симбиозе с градиентом (аналогом первой производной), матрица Гессе является главным математическим аппаратом теории оптимизации, машинного обучения и теоретической механики.

Подробнее

Вращения Гивенса и отражения Хаусхолдера: ортогональные преобразования

Приведение матриц к треугольному или диагональному виду — центральная задача вычислительной линейной алгебры. Однако классический метод Гаусса, использующий элементарные преобразования строк (сдвиги), обладает существенным недостатком: он может накапливать вычислительные ошибки округления при работе с числами с плавающей запятой. Для создания абсолютно устойчивых алгоритмов математики обратились к ортогональным преобразованиям, которые сохраняют длины векторов и не искажают пространство. Двумя самыми мощными инструментами в этом арсенале являются матрицы вращения Уоллеса-Гивенса (Givens rotations) и матрицы отражения Хаусхолдера (Householder reflections). Именно они лежат в основе современных алгоритмов QR-разложения и поиска собственных значений матриц.

Подробнее
Subscribe to this RSS feed

Соц. сети