Классический процесс Грама — Шмидта выполняется следующим образом:
На основе каждого вектора может быть получен нормированный вектор единичной длины, определённый как
Результаты процесса Грама — Шмидта:
— система ортогональных векторов либо
— система ортонормированных векторов.
Вычисление носит название ортогонализации Грама — Шмидта, а — ортонормализации Грама — Шмидта.
Геометрическая интерпретация
Рассмотрим формулу (2) — второй шаг алгоритма. Её геометрическое представление изображено на рис. 1:
получение проекции вектора на ;
вычисление , то есть перпендикуляра, которым выполняется проецирование на . Этот перпендикуляр — вычисляемый в формуле (2) вектор ;
перемещение полученного на шаге 2 вектора в начало координат. Это перемещение сделано на рисунке лишь для наглядности;
На рисунке видно, что вектор ортогонален вектору , так как является перпендикуляром, по которому проецируется на .
Рассмотрим формулу (3) — третий шаг алгоритма — в следующем варианте:
Её геометрическое представление изображено на рис. 2:
получение проекции вектора на ;
получение проекции вектора на ;
вычисление суммы , то есть проекции вектора на плоскость, образуемую векторами и . Эта плоскость закрашена на рисунке серым цветом;
вычисление , то есть перпендикуляра, которым выполняется проецирование на плоскость, образуемую векторами и . Этот перпендикуляр — вычисляемый в формуле (6) вектор ;
перемещение полученного в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (6).
На рисунке видно, что вектор ортогонален векторам и , так как является перпендикуляром, по которому проецируется на плоскость, образуемую векторами и .
Таким образом, в процессе Грама — Шмидта для вычисления выполняется проецирование ортогонально на гиперплоскость, натянутую на векторы . Вектор затем вычисляется как разность между и его проекцией. То есть — это перпендикуляр от к гиперплоскости, натянутой на векторы . Поэтому ортогонален векторам, образующим эту гиперплоскость.
Особые случаи
Процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов.
Кроме того, процесс Грама — Шмидта может применяться к линейно зависимым векторам. В этом случае он выдаёт (нулевой вектор) на шаге , если является линейной комбинацией векторов . Для сохранения ортогональности выходных векторов и для предотвращения деления на ноль при ортогонализации алгоритм должен отбрасывать нулевые векторы. Количество векторов, выдаваемых алгоритмом, будет равно размерности подпространства, порождённого векторами (то есть количеству линейно независимых векторов, которые можно выделить среди исходных векторов).
Произведение длин равно объёму параллелепипеда, построенного на векторах системы как на рёбрах.
Процесс Грама ― Шмидта для векторов-столбцов матрицы из определяет гомотопическую эквивалентность .
Дополнительные толкования
Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что является частным случаем разложения Ивасавы[].
Литература
Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Наука.
Евкли́дово простра́нство в изначальном смысле — это пространство, свойства которого описываются аксиомами евклидовой геометрии. В этом случае предполагается, что пространство имеет размерность, равную 3, то есть является трёхмерным.
Те́нзор — применяемый в математике и физике математический объект линейной алгебры, заданный на векторном пространстве конечной размерности. В физике в качестве векторного пространства обычно выступает физическое трёхмерное пространство или четырёхмерное пространство-время, а компонентами тензора являются координаты (проекции) взаимосвязанных физических величин. Использование тензоров в физике позволяет глубже понять физические законы и уравнения, упростить их запись за счёт сведения многих связанных физических величин в один тензор, а также записывать уравнения в форме, не зависящей от выбранной системы отсчёта.
Ма́трица — математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля, который представляет собой совокупность строк и столбцов, на пересечении которых находятся его элементы. Количество строк и столбцов задаёт размер матрицы. Матрицу можно также представить в виде функции двух дискретных аргументов. Хотя исторически рассматривались, например, треугольные матрицы, в настоящее время говорят исключительно о матрицах прямоугольной формы, так как они являются наиболее удобными и общими.
Векторное произведение двух векторов в трёхмерном евклидовом пространстве — вектор, перпендикулярный обоим исходным векторам, длина которого численно равна площади параллелограмма, образованного исходными векторами, а выбор из двух направлений определяется так, чтобы тройка из по порядку стоящих в произведении векторов и получившегося вектора была правой. Векторное произведение коллинеарных векторов считается равным нулевому вектору.
Определи́тель (детермина́нт) в линейной алгебре — скалярная величина, которая характеризует ориентированное «растяжение» или «сжатие» многомерного евклидова пространства после преобразования матрицей; имеет смысл только для квадратных матриц. Стандартные обозначения определителя матрицы — , , .
Определителем Грама (грамианом) системы векторов в евклидовом пространстве называется определитель матрицы Грама этой системы:
Пусть есть векторное пространство над полем .
Ме́тод Га́усса — классический метод решения системы линейных алгебраических уравнений (СЛАУ). Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних, находятся все переменные системы.
Ковариацио́нная ма́трица в теории вероятностей — это матрица, составленная из попарных ковариаций элементов одного или двух случайных векторов.
Ортогона́льный (ортонорми́рованный) ба́зис — ортогональная (ортонормированная) система элементов линейного пространства со скалярным произведением, обладающая свойством полноты.
Метод главных компонент — один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретён Карлом Пирсоном в 1901 году. Применяется во многих областях, в том числе в эконометрике, биоинформатике, обработке изображений, для сжатия данных, в общественных науках.
Норма́льные колеба́ния, со́бственные колебания или мо́ды — набор характерных для колебательной системы типов гармонических колебаний. Каждое из нормальных колебаний физической системы, например, колебаний атомов в молекулах, характеризуется своей частотой. Такая частота называется нормальной частотой, или собственной частотой. Набор частот нормальных колебаний составляет колебательный спектр. Произвольное колебание физической системы можно представить в виде суперпозиции различных нормальных колебаний. Вынужденные колебания физической системы испытывают резонанс на частотах, которые совпадают с частотами нормальных колебаний этой системы.
В линейной алгебре базис векторного пространства размерности — это последовательность из векторов , таких, что любой вектор пространства может быть представлен единственным образом в виде линейной комбинации базисных векторов. При заданном базисе операторы представляются в виде квадратных матриц. Так как часто необходимо работать с несколькими базисами в одном и том же векторном пространстве, необходимо иметь правило перевода координат векторов и операторов из базиса в базис. Такой переход осуществляется с помощью матрицы перехода.
Умноже́ние ма́триц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведе́нием ма́триц. Элементы новой матрицы получаются из элементов старых матриц в соответствии с правилами, проиллюстрированными ниже.
Произведение Кронекера — бинарная операция над матрицами произвольного размера, обозначается . Результатом является блочная матрица.
Криптосистема Сидельникова (Мак-Элиса—Сидельникова) — криптографическая система с открытым ключом, основанная на криптосистеме McEliece. Была предложена математиком, академиком Академии криптографии РФ Владимиром Михайловичем Сидельниковым в 1994 году. Сидельников предложил данную криптосистему, поскольку для системы McEliece к тому времени уже были найдены алгоритмы, взламывающие её за полиномиальное, либо субэкспоненциальное время работы.
В линейной алгебре квадратная матрица A называется диагонализируемой, если она подобна диагональной матрице, то есть если существует невырожденная матрица P, такая что P−1AP является диагональной матрицей. Если V — конечномерное векторное пространство, то линейное отображение T : V → V называется диагонализируемым, если существует упорядоченный базис в V, при котором T представляется в виде диагональной матрицы. Диагонализацией называется процесс нахождения соответствующей диагональной матрицы для диагонализируемой матрицы или линейного отображения. Квадратная матрица, которую нельзя диагонализировать, называется дефектной.
Анализ независимых компонент, называемый также Метод независимых компонент (МНК) — это вычислительный метод в обработке сигналов для разделения многомерного сигнала на аддитивные подкомпоненты. Этот метод применяется при предположении, что подкомпоненты являются негауссовыми сигналами и что они статистически независимы друг от друга. АНК является специальным случаем слепого разделения сигнала. Типичным примером приложения является задача вечеринки с коктейлем — когда люди на шумной вечеринке выделяют голос собеседника, несмотря на громкую музыку и шум людей в помещении: мозг способен фильтровать звуки и сосредотачиваться на одном источнике в реальном времени.
Алгоритм Ленстры — Ленстры — Ловаса — алгоритм редукции базиса решётки, разработанный Арьеном Ленстрой, Хендриком Ленстрой и Ласло Ловасом в 1982 году. За полиномиальное время алгоритм преобразует базис на решётке в кратчайший почти ортогональный базис на этой же решётке. По состоянию на 2019 год алгоритм Ленстры — Ленстры — Ловаса является одним из самых эффективных для вычисления редуцированного базиса в решётках больших размерностей. Он актуален прежде всего в задачах, сводящихся к поиску кратчайшего вектора решётки.
Ядро линейного отображения — это такое линейное подпространство области определения отображения, каждый элемент которого отображается в нулевой вектор. А именно: если задано линейное отображение между двумя векторными пространствами и , то ядро отображения — это векторное пространство всех элементов пространства , таких что , где обозначает нулевой вектор из , или более формально:
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.