- Процесс Грама ― Шмидта
-
Процесс Грама (англ.) ― Шмидта — это один из алгоритмов, в которых на основе счётного множества линейно независимых векторов
строится множество ортогональных векторов
или ортонормированных векторов
, причём так, что каждый вектор
или
может быть выражен линейной комбинацией векторов
.
Содержание
Классический процесс Грама — Шмидта
Алгоритм
Пусть имеются линейно независимые векторы
.
Определим оператор проекции следующим образом:
где
— скалярное произведение векторов
и
. Этот оператор проецирует вектор
ортогонально на вектор
.
Классический процесс Грама — Шмидта выполняется следующим образом:
На основе каждого вектора
может быть получен нормированный вектор:
(у нормированного вектора направление будет таким же, как у исходного, а длина — единичной).
Результаты процесса Грама — Шмидта:
— система ортогональных векторов либо
— система ортонормированных векторов.
Вычисление
носит название ортогонализации Грама — Шмидта, а
— ортонормализации Грама — Шмидта.
Доказательство
Докажем ортогональность векторов
.
Для этого вычислим скалярное произведение
, подставив в него формулу (2). Мы получим ноль. Равенство нулю скалярного произведения векторов означает, что эти вектора ортогональны. Затем вычислим скалярное произведение
, используя результат для
и формулу (3). Мы снова получим ноль, то есть вектора
и
ортогональны. Общее доказательство выполняется методом математической индукции.
Геометрическая интерпретация — вариант 1
Рассмотрим формулу (2) — второй шаг алгоритма. Её геометрическое представление изображено на рис. 1:
1 — получение проекции вектора
на
;
2 — вычисление
, то есть перпендикуляра, которым выполняется проецирование конца
на
. Этот перпендикуляр — вычисляемый в формуле (2) вектор
;
3 — перемещение полученного на шаге 2 вектора
в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (2).
На рисунке видно, что вектор
ортогонален вектору
, так как
является перпендикуляром, по которому
проецируется на
.
Рассмотрим формулу (3) — третий шаг алгоритма — в следующем варианте:
Её геометрическое представление изображено на рис. 2:
1 — получение проекции вектора
на
;
2 — получение проекции вектора
на
;
3 — вычисление суммы
, то есть проекции вектора
на плоскость, образуемую векторами
и
. Эта плоскость закрашена на рисунке серым цветом;
4 — вычисление
, то есть перпендикуляра, которым выполняется проецирование конца
на плоскость, образуемую векторами
и
. Этот перпендикуляр — вычисляемый в формуле (6) вектор
;
5 — перемещение полученного
в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (6).
На рисунке видно, что вектор
ортогонален векторам
и
, так как
является перпендикуляром, по которому
проецируется на плоскость, образуемую векторами
и
.
Таким образом, в процессе Грама — Шмидта для вычисления
выполняется проецирование
ортогонально на гиперплоскость?, формируемую векторами
. Вектор
затем вычисляется как разность между
и его проекцией. То есть
— это перпендикуляр? от конца
к гиперплоскости?, формируемой векторами
. Поэтому
ортогонален векторам, образующим эту гиперплоскость?.
Геометрическая интерпретация — вариант 2
Рассмотрим проекции некоторого вектора
на вектора
и
как компоненты вектора
в направлениях
и
(рис. 3):
Если удалить из
компоненту в направлении
, то
станет ортогонален
(рис. 4):
Если из
удалить компоненты в направлениях
и
, то
станет ортогонален и
, и
(рис. 5):
В формуле (2) из вектора
удаляется компонента в направлении вектора
. Получаемый вектор
не содержит компоненту в направлении
и поэтому ортогонален вектору
.
В формуле (3) из вектора
удаляются компоненты в направлениях
и
(формуле 3 соответствует переход от рис. 3 к рис. 5; рис. 4 не соответствует формуле 3). Получаемый вектор
ортогонален векторам
и
.
В формуле (4) из вектора
удаляются компоненты в направлениях
. Получаемый вектор
ортогонален векторам
.
Таким образом, по формулам (1) — (4) на основе векторов
получается набор ортогональных векторов
.
Численная неустойчивость
При вычислении на ЭВМ по формулам (1) — (5) вектора
часто не точно ортогональны из-за ошибок округления. Из-за потери ортогональности в процессе вычислений классический процесс Грама — Шмидта называют численно неустойчивым.
Модифицированный процесс Грама — Шмидта
Процесс Грама — Шмидта может быть сделан более вычислительно устойчивым путём небольшой модификации. Вместо вычисления
как
этот вектор вычисляется следующим образом:
Геометрическая интерпретация
Рассмотрим получение
по формулам (8) — (11):
Геометрически это показано на рис 6:
На рис. 6 вектор
обозначен как
.
1 — получение проекции вектора
на
для формулы (12), то есть компоненты
в направлении
;
2 — вычитание по формуле (12), то есть удаление из
компоненты в направлении
. Получаемый вектор
ортогонален
, так как не имеет компоненты в направлении
;
3 — перенос вектора
в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (12).
4 — получение проекции вектора
на
для формулы (13), то есть компоненты
в направлении
;
5 — вычитание по формуле (13), то есть удаление из
компоненты в направлении
. Получаемый вектор
ортогонален
, так как не имеет компоненты в направлении
. При вычитании из
компоненты в направлении
в результирующем векторе
не появляется компонента в направлении
;
6 — перенос вектора
в начало координат. Это перемещение сделано на рисунке лишь для наглядности. Оно не является математическим действием и поэтому не отражается в формуле (13).
Таким образом, получаемый на рис. 6 вектор
не имеет компонент в направлениях
и
и поэтому ортогонален
и
.
Рассмотрим непосредственно формулы (8) — (11).В формуле (8) из вектора
удаляется компонента в направлении вектора
. Получаемый вектор
не содержит компоненту в направлении
и поэтому ортогонален вектору
.
Далее в формуле (9) из результата удаляется его компонента в направлении вектора
. Получаемый вектор
не содержит компоненту в направлении
и поэтому ортогонален вектору
.
Путём дальнейшего последовательного удаления из результата его компонент получается вектор
, не содержащий компонент в направлениях
и потому ортогональный векторам
.
Эквивалентность классического и модифицированного процессов
Классический и модифицированный процессы можно сопоставить следующим образом:
Формула (14) показывает вычисление
в классическом процессе, а формула (15) — в модифицированном.
Разница между (14) и (15) заключается в том, от каких векторов вычисляются компоненты: от
в классическом процессе или от результата предыдущего вычитания, то есть от
в модифицированном процессе.
представляет собой
, из которого удалены компоненты в направлениях
. Компонента вектора
в направлении
при этом удалении не затрагивается и поэтому она в
такая же, как в
. Другими словами,
На рис. 6 равенство (16) имеет форму «
».
Равенство (16) отображено знаками "||" между формулами (14) и (15). Это позволяет видеть, что формулы (14) и (15) эквивалентны. Таким образом, классический и модифицированный процессы эквивалентны, но только при идеально точных вычислениях. Реальные вычисления имеют погрешность из-за ошибок округления.
Особые случаи
Процесс Грама — Шмидта может применяться также к бесконечной последовательности линейно независимых векторов.
Кроме того, процесс Грама — Шмидта может применяться к линейно зависимым векторам. В этом случае он выдаёт
(нулевой вектор) на шаге
, если
является линейной комбинацией векторов
. Если это может случиться, то для сохранения ортогональности выходных векторов и для предотвращения деления на ноль при ортонормировании алгоритм должен делать проверку на нулевые вектора и отбрасывать их. Количество векторов, выдаваемых алгоритмом, будет равно размерности подпространства, порождённого векторами (т.е. количеству линейно независимых векторов, которые можно выделить среди исходных векторов).
Свойства
- Произведение длин
равно объёму параллелепипеда, построенного на векторах системы
как на рёбрах.
Единственность результата
Матрица перехода от
к
и множество векторов
определяются однозначно, если принять, что диагональные элементы матрицы перехода положительны.
Дополнительные толкования
Процесс Грама ― Шмидта может быть истолкован как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами ― QR-разложение, что есть частный случай разложения Ивасавы.
Реализации
Реализация для пакета Mathematica
Данный скрипт, предназначенный для пакета Mathematica, проводит процесс ортогонализации Грама ― Шмидта над векторами, заданными в фигурных скобках предпоследней строки. Количество векторов и их координат могут быть произвольными. В данном случае для примера взяты векторы
,
,
.
Projection[v1_, v2_] := (v1.v2*v2)/v2.v2 MultipleProjection[v1_, vecs_] := Plus @@ (Projection[v1, #1] &) /@ vecs GramSchmidt[mat_] := Fold[Join[#1, {#2 - MultipleProjection[#2, #1]}] &, {}, mat] GramSchmidt[{{-2, 1, 0}, {-2, 0, 1}, {-0.5, -1, 1}}]
Литература
- Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры. — М.: Наука.
Категория:- Линейная алгебра
Wikimedia Foundation. 2010.