Процесс Грама ― Шмидта

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

Классический процесс Грама — ШмидтаПравить

АлгоритмПравить

Пусть имеются линейно независимые векторы   и пусть   — оператор проекции вектора   на вектор  , определённый как

 

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

Классический процесс Грама — Шмидта выполняется следующим образом:

 

На основе каждого вектора   может быть получен нормированный вектор   единичной длины, определённый как

 

Результаты процесса Грама — Шмидта:

  — система ортогональных векторов либо

  — система ортонормированных векторов.

Вычисление   носит название ортогонализации Грама — Шмидта, а   — ортонормализации Грама — Шмидта.

ДоказательствоПравить

Доказательство основывается на том, что проекция сохраняет скалярное произведение с  , то есть,

 ,

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

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

 

Здесь было учтено предположение индукции о том, что   при  .

Геометрическая интерпретацияПравить

 
Рис. 1. Второй шаг процесса Грама — Шмидта

Рассмотрим формулу (2) — второй шаг алгоритма. Её геометрическое представление изображено на рис. 1:

  1. получение проекции вектора   на  ;
  2. вычисление  , то есть перпендикуляра, которым выполняется проецирование   на  . Этот перпендикуляр — вычисляемый в формуле (2) вектор  ;
  3. перемещение полученного на шаге 2 вектора   в начало координат. Это перемещение сделано на рисунке лишь для наглядности;

На рисунке видно, что вектор   ортогонален вектору  , так как   является перпендикуляром, по которому   проецируется на  .

Рассмотрим формулу (3) — третий шаг алгоритма — в следующем варианте:

 

Её геометрическое представление изображено на рис. 2:

 
Рис. 2. Третий шаг процесса Грама — Шмидта
  1. получение проекции вектора   на  ;
  2. получение проекции вектора   на  ;
  3. вычисление суммы  , то есть проекции вектора   на плоскость, образуемую векторами   и  . Эта плоскость закрашена на рисунке серым цветом;
  4. вычисление  , то есть перпендикуляра, которым выполняется проецирование   на плоскость, образуемую векторами   и  . Этот перпендикуляр — вычисляемый в формуле (6) вектор  ;
  5. перемещение полученного   в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (6).

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

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

Особые случаиПравить

Процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов.

Кроме того, процесс Грама — Шмидта может применяться к линейно зависимым векторам. В этом случае он выдаёт   (нулевой вектор) на шаге  , если   является линейной комбинацией векторов  . Если это может случиться, то для сохранения ортогональности выходных векторов и для предотвращения деления на ноль при ортогонализации алгоритм должен и отбрасывать нулевые векторы. Количество векторов, выдаваемых алгоритмом, будет равно размерности подпространства, порождённого векторами (то есть количеству линейно независимых векторов, которые можно выделить среди исходных векторов).

СвойстваПравить

  • Произведение длин   равно объёму параллелепипеда, построенного на векторах системы   как на рёбрах.

Дополнительные толкованияПравить

Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что является частным случаем разложения Ивасавы[источник не указан 138 дней].

ЛитератураПравить

  • Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Наука.

СсылкиПравить