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

редактировать

Метод ортонормирования набора векторов

Первые два шага процесса Грама – Шмидта

In математика, в частности линейная алгебра и численный анализ, процесс Грама – Шмидта - это метод ортонормировки множества из векторов во внутреннем пространстве продукта , чаще всего в евклидовом пространстве R, снабженном стандартным внутренним продуктом . Процесс Грама – Шмидта принимает конечное, линейно независимое множество S = {v 1,..., v k } для k ≤ n и генерирует ортогональный набор S ′ = {u 1,..., u k }, который охватывает то же k-мерное подпространство R как S.

Метод назван в честь Йоргена Педерсена Грама и Эрхарда Шмидта, но Пьер-Симон Лаплас был знаком с ним еще до Грама и Шмидта. В теории разложений групп Ли это обобщается с помощью разложения Ивасавы.

Применение процесса Грама – Шмидта к векторам-столбцам полного столбца ранга матрица дает разложение QR (оно разлагается на ортогональную и треугольную матрицу ).

Содержание

1 Процесс Грама – Шмидта
2 Пример
- 2.1 Евклидово пространство
3 Свойства
4 Числовая стабильность
5 Алгоритм
6 Метод исключения Гаусса
7 Формула детерминанта
8 Альтернативы
9 Ссылки
10 Внешние ссылки

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

Модифицированный процесс Грама-Шмидта, выполняемый на трех линейно независимых, неортогональных векторах базиса для R . Щелкните изображение, чтобы узнать подробности. Модификация объясняется в разделе «Числовая стабильность» этой статьи.

Мы определяем оператор projection как

proju (v) = ⟨u, v⟩ ⟨u, u ⟩ U, {\ Displaystyle \ mathrm {proj} _ {\ mathbf {u}} \, (\ mathbf {v}) = {\ langle \ mathbf {u}, \ mathbf {v} \ rangle \ over \ langle \ mathbf {u}, \ mathbf {u} \ rangle} {\ mathbf {u}},}

{\ displaystyle \ mathrm {proj} _ {\ mathbf {u}} \, (\ mathbf {v}) = {\ langle \ mathbf {u}, \ mathbf {v} \ rangle \ over \ langle \ mathbf {u}, \ mathbf {u} \ rangle} {\ mathbf {u}},}

где $⟨u, v⟩ {\ displaystyle \ langle \ mathbf {u}, \ mathbf {v} \ rangle}$ $\ langle \ mathbf {u}, \ mathbf {v} \ rangle$ обозначает внутреннее произведение векторов u и v . Этот оператор проецирует вектор v ортогонально на линию, натянутую на вектор u . Если u= 0, мы определяем $p r o j 0 (v): = 0 {\ displaystyle \ mathrm {proj} _ {0} \, (\ mathbf {v}): = 0}$ $\ mathrm {proj} _ {0} \, (\ mathbf {v}): = 0$ . то есть карта проекции $p r o j 0 {\ displaystyle \ mathrm {proj} _ {0}}$ $\ mathrm {proj} _ {0}$ - это нулевая карта, отправляющая каждый вектор в нулевой вектор.

Затем процесс Грама – Шмидта работает следующим образом:

u 1 = v 1, e 1 = u 1 ‖ u 1 ‖ u 2 = v 2 - proju 1 (v 2), e 2 = u 2 ‖ u 2 ‖ u 3 = v 3 - proju 1 (v 3) - proju 2 (v 3), e 3 = u 3 ‖ u 3 ‖ u 4 = v 4 - proju 1 (v 4) - proju 2 (v 4) - proju 3 (v 4), e 4 = u 4 ‖ u 4 ‖ ⋮ ⋮ uk = vk - ∑ j = 1 k - 1 projuj (vk), ek = uk ‖ uk ‖. {\ displaystyle {\ begin {align} \ mathbf {u} _ {1} = \ mathbf {v} _ {1}, \ mathbf {e} _ {1} = {\ mathbf {u} _ { 1} \ over \ | \ mathbf {u} _ {1} \ |} \\\ mathbf {u} _ {2} = \ mathbf {v} _ {2} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {2}), \ mathbf {e} _ {2} = {\ mathbf {u} _ {2} \ over \ | \ mathbf {u} _ {2} \ |} \\\ mathbf {u} _ {3} = \ mathbf {v} _ {3} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {3}) - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {v} _ {3}), \ mathbf {e } _ {3} = {\ mathbf {u} _ {3} \ over \ | \ mathbf {u} _ {3} \ |} \\\ mathbf {u} _ {4} = \ mathbf {v } _ {4} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {4}) - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {v} _ {4}) - \ mathrm {proj} _ {\ mathbf {u} _ {3}} \, (\ mathbf {v} _ {4}), \ mathbf {e} _ {4} = {\ mathbf {u} _ {4} \ over \ | \ mathbf {u} _ {4} \ |} \\ {} \ \ \ vdots {} \ \ \ vdots \\\ mathbf {u} _ {k} = \ mathbf {v} _ {k} - \ sum _ {j = 1} ^ {k-1} \ mathrm {proj} _ {\ mathbf { u} _ {j}} \, (\ mathbf {v} _ {k}), \ mathbf {e} _ {k} = {\ mathbf {u} _ {k} \ over \ | \ mathbf { u} _ {k} \ |}. \ end {align}}}

{\ begin {align} \ mathbf {u} _ {1} = \ mathbf {v } _ {1}, \ mathbf {e} _ {1} = {\ mathbf {u} _ {1} \ over \ | \ mathbf {u} _ {1} \ |} \\\ mathbf {u } _ {2} = \ mathbf {v} _ {2} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {2}), \ mathbf {e} _ {2} = {\ mathbf {u} _ {2} \ over \ | \ mathbf {u} _ {2} \ |} \\\ mathbf {u} _ {3} = \ mathbf {v} _ {3} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {3}) - \ mathrm {proj} _ {\ mathbf { u} _ {2}} \, (\ mathbf {v} _ {3}), \ mathbf {e} _ {3} = {\ mathbf {u} _ {3} \ over \ | \ mathbf { u} _ {3} \ |} \\\ mathbf {u} _ {4} = \ mathbf {v} _ {4} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \,(\мат hbf {v} _ {4}) - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {v} _ {4}) - \ mathrm {proj} _ {\ mathbf {u} _ {3}} \, (\ mathbf {v} _ {4}), \ mathbf {e} _ {4} = {\ mathbf {u} _ {4} \ over \ | \ mathbf {u} _ {4} \ |} \\ {} \ \ \ vdots {} \ \ \ vdots \\\ mathbf {u} _ {k} = \ mathbf {v} _ {k} - \ сумма _ {j = 1} ^ {k-1} \ mathrm {proj} _ {\ mathbf {u} _ {j}} \, (\ mathbf {v} _ {k}), \ mathbf {e} _ {k} = {\ mathbf {u} _ {k} \ over \ | \ mathbf {u} _ {k} \ |}. \ end {align}}

Последовательность e u1,..., uk- требуемая система ортогональных векторов, а нормализованные векторы e1,..., ekобразуют ортонормированный набор. Вычисление последовательности u1,..., ukизвестно как ортогонализация Грама – Шмидта, а вычисление последовательности e1,..., ekизвестно как Грама – Шмидта ортонормировка, поскольку векторы нормализованы.

Чтобы проверить, что эти формулы дают ортогональную последовательность, сначала вычислите $⟨u 1, u 2⟩ {\ displaystyle \ langle \ mathbf {u} _ {1}, \ mathbf {u} _ { 2} \ rangle}$ ${\ displaystyle \ langle \ mathbf {u} _ {1}, \ mathbf {u} _ {2} \ rangle}$ путем замены приведенной выше формулы на u2: мы получаем ноль. Затем используйте это, чтобы снова вычислить $⟨u 1, u 3⟩ {\ displaystyle \ langle \ mathbf {u} _ {1}, \ mathbf {u} _ {3} \ rangle}$ ${\ displaystyle \ langle \ mathbf {u} _ {1}, \ mathbf {u} _ {3} \ rangle}$ , подставляя формулу на u3: получаем ноль. Общее доказательство проводится с помощью математической индукции.

Геометрически этот метод действует следующим образом: для вычисления uiон проецирует viортогонально на подпространство U, генерируемое u1,..., ui-1, которое совпадает с подпространством, сгенерированным v1,..., vi-1. Затем вектор uiопределяется как разность между viи этой проекцией, которая гарантированно ортогональна всем векторам в подпространстве U.

Процесс Грама – Шмидта также применяется к линейно независимая счетно бесконечная последовательность {vi}i. Результатом является ортогональная (или ортонормированная) последовательность {ui}iтакая, что для натурального числа n: алгебраический диапазон v1,..., vnтакой же, как у u1,..., un.

Если процесс Грама – Шмидта применяется к линейно зависимой последовательности, он выводит вектор 0 на i-м шаге, предполагая, что viявляется линейной комбинацией v1,..., vя-1. Если должен быть создан ортонормированный базис, то алгоритм должен проверить наличие нулевых векторов в выходных данных и отбросить их, потому что никакое число, кратное нулевому вектору, не может иметь длину 1. Число векторов, выведенных алгоритмом, будет тогда размерностью пространства, занимаемого исходными входами.

Вариант процесса Грама – Шмидта с использованием трансфинитной рекурсии, примененной к (возможно, несчетной) бесконечной последовательности векторов $(v α) α < λ {\displaystyle (v_{\alpha })_{\alpha <\lambda }}$ $(v _ {\ alpha}) _ {\ alpha <\ lambda}$ , дает набор ортонормированных векторы $(u α) α < κ {\displaystyle (u_{\alpha })_{\alpha <\kappa }}$ $(u _ {\ alpha}) _ {\ alpha <\ kappa}$ с $κ ≤ λ {\ displaystyle \ kappa \ leq \ lambda}$ $\ kappa \ leq \ lambda$ такие, что для любого $α ≤ λ {\ displaystyle \ alpha \ leq \ lambda}$ $\ alpha \ leq \ lambda$ , завершение диапазона ${u β: β < min ( α, κ) } {\displaystyle \lbrace u_{\beta }:\beta <\min(\alpha,\kappa)\rbrace }$ $\ lbrace u_ { \ beta}: \ beta <\ min (\ alpha, \ kappa) \ rbrace$ такое же, как и ${v β: β < α } {\displaystyle \lbrace v_{\beta }:\beta <\alpha \rbrace }$ $\ lbrace v_ { \ beta}: \ beta <\ alpha \ rbrace$ . В частности, при применении к (алгебраическому) базису гильбертова пространства (или, в более общем смысле, базису любого плотного подпространства), он дает (функционально-аналитический) ортонормированный базис. Обратите внимание, что в общем случае часто выполняется строгое неравенство $κ < λ {\displaystyle \kappa <\lambda }$ $\ каппа <\ лямбда$ , даже если начальный набор был линейно независимым, и промежуток $(u α) α < κ {\displaystyle (u_{\alpha })_{\alpha <\kappa }}$ $(u _ {\ alpha}) _ {\ alpha <\ kappa}$ не обязательно должен быть подпространством промежутка $(v α) α < λ {\displaystyle (v_{\alpha })_{\alpha <\lambda }}$ $(v _ {\ alpha}) _ {\ alpha <\ lambda}$ (скорее, это подпространство его пополнения).

Пример

Евклидово пространство

Рассмотрим следующий набор векторов в R (с обычным внутренним произведением )

S = { v 1 = (3 1), v 2 = (2 2)}. {\ Displaystyle S = \ left \ lbrace \ mathbf {v} _ {1} = {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix }}, \ mathbf {v} _ {2} = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} \ right \ rbrace.}

S = \ left \ lbrace \ mathbf {v} _ {1} = {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}, \ mathbf {v} _ {2} = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} \ right \ rbrace.

Теперь выполните Грама – Шмидта, чтобы получить ортогональное множество векторов:

u 1 = v 1 = (3 1) {\ displaystyle \ mathbf {u} _ {1} = \ mathbf {v} _ {1} = {\ begin {pmatrix} 3 \\ 1 \ конец {pmatrix}}}

\ mathbf {u} _ {1} = \ mathbf {v} _ {1} = {\ begin {pmatrix} 3 \\ 1 \ end { pmatrix}}

u 2 = v 2 - proju 1 (v 2) = (2 2) - proj (3 1) ((2 2)) = (2 2) - 8 10 (3 1) = (- 2/5 6/5). {\ Displaystyle \ mathbf {u} _ {2} = \ mathbf {v} _ {2} - \ mathrm {proj} _ {\ mathbf {u} _ {1} } \, (\ mathbf {v} _ {2}) = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} - \ mathrm {proj} _ {({3 \ atop 1})} \, ({{\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}})} = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} - {8 \ over 10} {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} -2/5 \\ 6/5 \ end {pmatrix}}.}

{\ displaystyle \ mathbf {u} _ {2} = \ mathbf {v} _ {2} - \ mathrm {proj } _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {2}) = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} - \ mathrm {proj} _ {({3 \ atop 1})} \, ({{\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}})} = {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}} - {8 \ более 10} {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}} = {\ begin {pmatrix} -2/5 \\ 6/5 \ end {pmatrix}}.}

Проверяем, что t Векторы u1и u2действительно ортогональны:

⟨u 1, u 2⟩ = ⟨(3 1), (- 2/5 6/5)⟩ = - 6 5 + 6 5 = 0, {\ displaystyle \ langle \ mathbf {u} _ {1}, \ mathbf {u} _ {2} \ rangle = \ left \ langle {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}, {\ begin {pmatrix} -2/5 \\ 6/5 \ end {pmatrix}} \ right \ rangle = - {\ frac {6} {5}} + {\ frac {6} {5}} = 0,}

\ langle \ mathbf {u} _ {1}, \ mathbf {u} _ {2} \ rangle = \ left \ langle {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}, {\ begin {pmatrix} -2/5 \\ 6/5 \ end {pmatrix}} \ right \ rangle = - {\ frac {6} {5}} + {\ frac {6} {5}} = 0,

отмечая, что если скалярное произведение двух векторов равно 0, то они ортогональны.

Для ненулевых векторов мы можем затем нормализовать векторы, разделив их размеры, как показано выше:

e 1 = 1 10 (3 1) {\ displaystyle \ mathbf {e} _ {1 } = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}}

\ mathbf {e} _ {1} = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}

e 2 = 1 40 25 (- 2/5 6/5) = 1 10 (- 1 3). {\ displaystyle \ mathbf {e} _ {2} = {1 \ over {\ sqrt {40 \ over 25}}} {\ begin {pmatrix} -2/5 \\ 6/5 \ end {pmatrix}} = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} -1 \\ 3 \ end {pmatrix}}.}

\ mathbf {e} _ {2} = {1 \ over {\ sqrt {40 \ over 25}}} {\ begin {pmatrix} -2/5 \\ 6/5 \ end {pmatrix}} = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} -1 \\ 3 \ end {pmatrix}}.

Свойства

Обозначим $GS ⁡ (v 1,…, vk) {\ displaystyle \ operatorname {GS} (v_ {1}, \ dots, v_ {k})}$ ${\ displaystyle \ operatorname {GS} (v_ {1}, \ dots, v_ {k})}$ результат применения процесса Грама – Шмидта к набору векторов $v 1,… vk {\ displaystyle v_ {1}, \ dots v_ {k}}$ ${\ displaystyle v_ {1}, \ dots v_ {k}}$ . Это дает карту $GS: (R n) k → (R n) k {\ displaystyle \ operatorname {GS} \ двоеточие (\ mathbf {R} ^ {n}) ^ {k} \ to (\ mathbf {R} ^ {n}) ^ {k}}$ ${\ Displaystyle \ OperatorName {GS} \ двоеточие (\ mathbf {R} ^ {n}) ^ {k} \ to (\ mathbf {R} ^ {n}) ^ {k}}$ .

Он имеет следующие свойства:

Непрерывный
Это ориентация с сохранением в том смысле, что $или ⁡ (v 1,…, vk) = или ⁡ (GS ⁡ (v 1,…, vk)) {\ displaystyle \ operatorname {or} (v_ {1}, \ dots, v_ {k}) = \ operatorname {or} (\ operatorname {GS} (v_ {1}, \ dots, v_ {k}))}$ ${\ displaystyle \ operatorname {or} (v_ {1}, \ dots, v_ {k}) = \ operatorname {or} (\ operatorname {GS} (v_ {1}, \ dots, v_ {k}))}$ .
Он коммутирует с ортогональными отображениями:

Пусть $g: R n → R n { \ displaystyle g \ двоеточие \ mathbf {R} ^ {n} \ to \ mathbf {R} ^ {n}}$ ${\ displaystyle g \ двоеточие \ mathbf {R} ^ {n} \ to \ mathbf {R} ^ {n}}$ быть ортогональным (относительно данного внутреннего продукта). Тогда имеем

GS ⁡ (g (v 1),…, g (vk)) = (g (GS ⁡ (v 1,…, vk) 1),…, g (GS ⁡ (v 1,…, vk) k)) {\ displaystyle \ operatorname {GS} (g (v_ {1}), \ dots, g (v_ {k})) = (g (\ operatorname {GS} (v_ {1}, \ dots, v_ {k}) _ {1}), \ dots, g (\ operatorname {GS} (v_ {1}, \ dots, v_ {k}) _ {k}))}

{\ displaystyle \ operatorname {GS} (g (v_ {1}), \ dots, g (v_ {k})) = (g (\ operatorname {GS} (v_ {1}, \ dots, v_ {k}) _ {1}), \ dots, g (\ operatorname {GS} (v_ { 1}, \ dots, v_ {k}) _ {k}))}

Далее параметризованный версия процесса Грама – Шмидта дает (сильную) деформационную ретракцию общей линейной группы $GL (R n) {\ displaystyle GL (\ mathbf {R} ^ {n})}$ ${\ displaystyle GL (\ mathbf {R} ^ {n})}$ на ортогональную группу $O (R n) {\ displaystyle O (\ mathbf {R} ^ {n})}$ ${\ displaystyle O (\ mathbf {R} ^ {n})}$ .

Числовая стабильность

Когда этот процесс реализуется на На компьютере векторы $uk {\ displaystyle \ mathbf {u} _ {k}}$ $\ mathbf {u} _ {k}$ часто не совсем ортогональны из-за ошибок округления. Для процесса Грама – Шмидта, описанного выше (иногда называемого «классическим методом Грама – Шмидта»), эта потеря ортогональности особенно велика; поэтому говорят, что (классический) процесс Грама – Шмидта численно нестабилен.

Процесс Грама – Шмидта можно стабилизировать с помощью небольшой модификации; эта версия иногда упоминается как модифицированная версия Грама-Шмидта или MGS. Этот подход дает тот же результат, что и исходная формула в точной арифметике, и вносит меньшие ошибки в арифметику конечной точности. Вместо вычисления вектора ukкак

uk = vk - proju 1 (vk) - proju 2 (vk) - ⋯ - projuk - 1 (vk), {\ displaystyle \ mathbf {u} _ {k} = \ mathbf {v} _ {k} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {k}) - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {v} _ {k}) - \ cdots - \ mathrm {proj} _ {\ mathbf {u} _ {k-1}} \, (\ mathbf { v} _ {k}),}

\ mathbf {u} _ {k} = \ mathbf {v} _ {k} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {k}) - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {v} _ {k}) - \ cdots - \ mathrm { proj} _ {\ mathbf {u} _ {k-1}} \, (\ mathbf {v} _ {k}),

вычисляется как

uk (1) = vk - proju 1 (vk), uk (2) = uk (1) - proju 2 (uk (1)), ⋮ uk (k - 2) = uk (k - 3) - projuk - 2 (uk (k - 3)), uk (k - 1) = uk (k - 2) - projuk - 1 (uk (k - 2)), uk = uk (k - 1) ‖ uk (k - 1) ‖ {\ displaystyle {\ begin {align} \ mathbf {u} _ {k} ^ {(1)} = \ mathbf {v } _ {k} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {k}), \\\ mathbf {u} _ {k} ^ { (2)} = \ mathbf {u} _ {k} ^ {(1)} - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {u} _ {k } ^ {(1)}), \\ \, \, \, \ vdots \\\ mathbf {u} _ {k} ^ {(k-2)} = \ mathbf {u} _ {k} ^ {(k-3)} - \ mathrm {proj} _ {\ mathbf {u} _ {k-2}} \, (\ m athbf {u} _ {k} ^ {(k-3)}), \\\ mathbf {u} _ {k} ^ {(k-1)} = \ mathbf {u} _ {k} ^ { (k-2)} - \ mathrm {proj} _ {\ mathbf {u} _ {k-1}} \, (\ mathbf {u} _ {k} ^ {(k-2)}), \\ \ mathbf {u} _ {k} = {\ mathbf {u} _ {k} ^ {(k-1)} \ over \ | \ mathbf {u} _ {k} ^ {(k-1)} \ |} \ end {align}}}

{\ displaystyle {\ begin {align} \ mathbf {u} _ {k} ^ {(1)} = \ mathbf {v} _ {k} - \ mathrm {proj} _ {\ mathbf {u} _ {1}} \, (\ mathbf {v} _ {k}), \\ \ mathbf {u} _ {k} ^ {(2)} = \ mathbf {u} _ {k} ^ {(1)} - \ mathrm {proj} _ {\ mathbf {u} _ {2}} \, (\ mathbf {u} _ {k} ^ {(1)}), \\ \, \, \, \ vdots \\\ mathbf {u} _ {k} ^ {(k-2)} = \ mathbf {u} _ {k} ^ {(k-3)} - \ m athrm {proj} _ {\ mathbf {u} _ {k-2}} \, (\ mathbf {u} _ {k} ^ {(k-3)}), \\\ mathbf {u} _ {k } ^ {(k-1)} = \ mathbf {u} _ {k} ^ {(k-2)} - \ mathrm {proj} _ {\ mathbf {u} _ {k-1}} \, (\ mathbf {u} _ {k} ^ {(k-2)}), \\\ mathbf {u} _ {k} = {\ mathbf {u} _ {k} ^ {(k-1) } \ over \ | \ mathbf {u} _ {k} ^ {(k-1)} \ |} \ end {align}}}

Этот метод используется в предыдущей анимации, когда промежуточный вектор v '3 используется при ортогонализации синего вектора v 3.

Алгоритм

Следующий алгоритм MATLAB реализует ортонормировку Грама – Шмидта для евклидовых векторов. Векторы v1,..., vk(столбцы матрицы V, так что V (:, j) является j-м вектором) заменяются ортонормированными векторами ( столбцы U ), которые охватывают одно и то же подпространство.

n = размер (V, 1); k = размер (V, 2); U = нули (n, k); U (:, 1) = V (:, 1) / sqrt (V (:, 1) '* V (:, 1)); для i = 2: k U (:, i) = V (:, i); для j = 1: i - 1 U (:, i) = U (:, i) - (U (:, j) '* U (:, i)) / (U (:, j)' * U ( :, j)) * U (:, j); конец U (:, i) = U (:, i) / sqrt (U (:, i) '* U (:, i)); end

Стоимость этого алгоритма асимптотически составляет O (nk) операций с плавающей запятой, где n - размерность векторов (Golub Van Loan 1996, §5.2.8).

Методом исключения Гаусса

Если строки {v 1,..., v k } записаны как матрица $A {\ displaystyle A}$ $A$ , затем применение исключения Гаусса к расширенной матрице $[AAT | A] {\ displaystyle [AA ^ {\ mathrm {T}} | A]}$ ${\ displaystyle [AA ^ {\ mathrm {T}} | A]}$ создаст ортогонализированные векторы вместо $A {\ displaystyle A}$ $A$ . Однако матрица $AAT {\ displaystyle AA ^ {\ mathrm {T}}}$ ${\ displaystyle AA ^ {\ mathrm {T}}}$ должна быть приведена к форме эшелона строк, используя только добавление скалярного числа, кратного единице. рядиться с другим. Например, взяв $v 1 = (3 1), v 2 = (2 2) {\ displaystyle \ mathbf {v} _ {1} = {\ begin {pmatrix} 3 1 \ end {pmatrix}}, \ mathbf {v} _ {2} = {\ begin {pmatrix} 2 2 \ end {pmatrix}}}$ ${\ displaystyle \ mathbf {v} _ {1} = {\ begin {pmatrix} 3 1 \ end {pmatrix}}, \ mathbf {v} _ {2} = {\ begin {pmatrix} 2 2 \ end {pmatrix}}}$ как и выше, у нас есть

[AAT | A] = [10 8 3 1 8 8 2 2] {\ displaystyle [AA ^ {\ mathrm {T}} | A] = \ left [{\ begin {array} {rr | rr} 10 8 3 1 \\ 8 8 2 2 \ end {array}} \ right]}

{\ displaystyle [AA ^ {\ mathrm {T}} | A] = \ left [{\ begin {array} {rr | rr} 10 8 3 1 \\ 8 8 2 2 \ end {array}} \ right]}

И сокращение этого до формы эшелона строк дает

[1.8.3.1 0 1 -.25.75] {\ displaystyle \ left [ {\ begin {array} {rr | rr} 1.8.3.1 \\ 0 1 -. 25.75 \ end {array}} \ right]}

{\ di splaystyle \ left [{\ begin {array} {rr | rr} 1.8.3.1 \\ 0 1 -. 25.75 \ end {array}} \ right]}

Нормализованные векторы тогда

e 1 = 1.3 2 +.1 2 (.3.1) = 1 10 (3 1) {\ displaystyle \ mathbf {e} _ {1} = {1 \ over {\ sqrt {.3 ^ {2} +. 1 ^ {2}}}} {\ begin {pmatrix}.3.1 \ end {pmatrix}} = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} 3 1 \ end {pmatrix}} }

{\ displaystyle \ mathbf {e } _ {1} = {1 \ over {\ sqrt {.3 ^ {2} +. 1 ^ {2}}}} {\ begin {pmatrix}.3.1 \ end {pmatrix}} = {1 \ над {\ sqrt {10}}} {\ begin {pmatrix} 3 1 \ end {pmatrix}}}

e 2 = 1,25 2 + 0,75 2 (- 0,25 0,75) = 1 10 (- 1 3). {\ displaystyle \ mathbf {e} _ {2} = {1 \ over {\ sqrt {.25 ^ {2} +. 75 ^ {2}}}} {\ begin {pmatrix} -. 25.75 \ end {pmatrix}} = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} -1 3 \ end {pmatrix}}.}

{\ displaystyle \ mathbf {e} _ {2} = {1 \ over {\ sqrt {.25 ^ {2} +. 75 ^ {2}}}} {\ begin {pmatrix} -. 25.75 \ end {pmatrix}} = {1 \ over {\ sqrt {10}}} {\ begin {pmatrix} -1 3 \ end {pmatrix}}.}

как в примере выше.

Формула детерминанта

Результат процесса Грама – Шмидта может быть выражен в нерекурсивной формуле с использованием определителей.

e j = 1 D j - 1 D j | ⟨V 1, v 1⟩ ⟨v 2, v 1⟩… ⟨vj, v 1⟩ ⟨v 1, v 2⟩ ⟨v 2, v 2⟩… ⟨vj, v 2⟩ ⋮ ⋮ ⟨v 1, vj - 1⟩ ⟨v 2, vj - 1⟩… ⟨vj, vj - 1⟩ v 1 v 2… vj | {\ displaystyle \ mathbf {e} _ {j} = {\ frac {1} {\ sqrt {D_ {j-1} D_ {j}}}} {\ begin {vmatrix} \ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {1} \ rangle \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {2} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {2} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {2} \ rangle \\\ vdots \ vdots \ ddots \ vdots \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {j-1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {j-1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {j-1} \ rangle \\\ mathbf {v} _ {1} \ mathbf {v} _ {2} \ dots \ mathbf {v} _ {j} \ end {vmatrix}}}

\ mathbf {e} _ {j} = {\ frac {1} {\ sqrt {D_ {j-1} D_ {j}}}} {\ begin {vmatrix} \ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {1} \ rangle \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {2} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {2} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {2} \ rangle \\\ vdots \ vdots \ ddots \ vdots \\\ langle \ mathbf {v} _ { 1}, \ mathbf {v} _ {j-1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {j-1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {j-1} \ rangle \\\ mathbf {v} _ {1} \ mathbf {v} _ {2} \ dots \ mathbf {v } _ {j} \ end {vmatrix}}

uj = 1 D j - 1 | ⟨V 1, v 1⟩ ⟨v 2, v 1⟩… ⟨vj, v 1⟩ ⟨v 1, v 2⟩ ⟨v 2, v 2⟩… ⟨vj, v 2⟩ ⋮ ⋮ ⟨v 1, vj - 1⟩ ⟨v 2, vj - 1⟩… ⟨vj, vj - 1⟩ v 1 v 2… vj | {\ displaystyle \ mathbf {u} _ {j} = {\ frac {1} {D_ {j-1}}} {\ begin {vmatrix} \ langle \ mathbf {v} _ {1}, \ mathbf {v } _ {1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf { v} _ {1} \ rangle \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {2} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v } _ {2} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {2} \ rangle \\\ vdots \ vdots \ ddots \ vdots \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {j-1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {j-1} \ rangle \ точки \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {j-1} \ rangle \\\ mathbf {v} _ {1} \ mathbf {v} _ {2} \ dots \ mathbf {v} _ {j} \ end {vmatrix}}}

\ mathbf {u} _ {j} = {\ frac {1} {D_ {j- 1}}} {\ begin {vmatrix} \ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v } _ {1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {1} \ rangle \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {2} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {2} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {2} \ rangle \\\ vdots \ vdots \ ddots \ vdots \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {j-1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {j-1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ m athbf {v} _ {j-1} \ rangle \\\ mathbf {v} _ {1} \ mathbf {v} _ {2} \ dots \ mathbf {v} _ {j} \ end {vmatrix }}

где D 0 = 1, а для j ≥ 1 D j равно определитель Грама

D j = | ⟨V 1, v 1⟩ ⟨v 2, v 1⟩… ⟨vj, v 1⟩ ⟨v 1, v 2⟩ ⟨v 2, v 2⟩… ⟨vj, v 2⟩ ⋮ ⋮ ⟨v 1, vj⟩ ⟨v 2, vj⟩… ⟨vj, vj⟩ |. {\ displaystyle D_ {j} = {\ begin {vmatrix} \ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {1} \ rangle \\\ langle \ mathbf {v} _ {1 }, \ mathbf {v} _ {2} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {2} \ rangle \ dots \ langle \ mathbf {v} _ { j}, \ mathbf {v} _ {2} \ rangle \\\ vdots \ vdots \ ddots \ vdots \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {j} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {j} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {j } \ rangle \ end {vmatrix}}.}

D_ {j} = {\ begin {vmatrix} \ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {1} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {1} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {1} \ rangle \\ \ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {2} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {2} \ rangle \ dots \ langle \ mathbf {v} _ {j}, \ mathbf {v} _ {2} \ rangle \\\ vdots \ vdots \ ddots \ vdots \\\ langle \ mathbf {v} _ {1}, \ mathbf {v} _ {j} \ rangle \ langle \ mathbf {v} _ {2}, \ mathbf {v} _ {j} \ rangle \ dots \ langle \ mathbf {v} _ {j }, \ mathbf {v} _ {j} \ rangle \ end {vmatrix}}.

Обратите внимание, что выражение для ukявляется «формальным» определителем, т.е. матрица содержит как скаляры, так и векторы; значение этого выражения определяется как результат расширения кофактора вдоль строки векторов.

Детерминантная формула для Грама-Шмидта в вычислительном отношении медленнее (экспоненциально медленнее), чем рекурсивные алгоритмы, описанные выше; это в основном теоретический интерес.

Альтернативы

Другие алгоритмы ортогонализации используют преобразования Хаусхолдера или вращения Гивенса. Алгоритмы, использующие преобразования Хаусхолдера, более стабильны, чем стабилизированный процесс Грама – Шмидта. С другой стороны, процесс Грама – Шмидта создает $j {\ displaystyle j}$ $j$ -й ортогонализированный вектор после $j {\ displaystyle j}$ $j$ -й итерации, в то время как ортогонализация с использованием отражений Хаусхолдера производит все векторы только в конце. Это делает применимым только процесс Грама – Шмидта для итерационных методов, таких как итерация Арнольди.

. Еще одна альтернатива мотивируется использованием разложения Холецкого для инвертирования матрица нормальных уравнений методом наименьших квадратов. Пусть $V {\ displaystyle \ mathbf {V}}$ $\ mathbf {V}$ будет матрицей ранга с полным столбцом, столбцы которой необходимо ортогонализировать. Матрица $V ∗ V {\ displaystyle \ mathbf {V} ^ {*} \ mathbf {V}}$ $\ mathbf {V} ^ {*} \ mathbf {V}$ является эрмитовой и положительно определенной, поэтому его можно записать как $V * V = LL *, {\ displaystyle \ mathbf {V} ^ {*} \ mathbf {V} = \ mathbf {L} \ mathbf {L} ^ {*},}$ $\ mathbf {V} ^ {*} \ mathbf {V} = \ mathbf {L} \ mathbf {L} ^ {*},$ с использованием разложения Холецкого. Нижняя треугольная матрица $L {\ displaystyle \ mathbf {L}}$ $\ mathbf {L}$ со строго положительными диагональными элементами является обратимой. Тогда столбцы матрицы $U = V (L - 1) ∗ {\ displaystyle \ mathbf {U} = \ mathbf {V} (\ mathbf {L} ^ {- 1}) ^ {*}}$ $\ mathbf {U} = \ mathbf {V} (\ mathbf {L} ^ {- 1}) ^ {*}$ являются ортонормированными и охватывают то же подпространство, что и столбцы исходной матрицы $V {\ displaystyle \ mathbf {V}}$ $\ mathbf {V}$ . Явное использование продукта $V * V {\ displaystyle \ mathbf {V} ^ {*} \ mathbf {V}}$ $\ mathbf {V} ^ {*} \ mathbf {V}$ делает алгоритм нестабильным, особенно если номер условия продукта большой. Тем не менее, этот алгоритм используется на практике и реализован в некоторых программных комплексах из-за его высокой эффективности и простоты.

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

Ссылки

^Cheney, Ward; Кинкейд, Дэвид (2009). Линейная алгебра: теория и приложения. Садбери, Ма: Джонс и Бартлетт. стр. 544, 558. ISBN 978-0-7637-5020-6.
^Pursell, Lyle; Тримбл, С. Ю. (1 января 1991 г.). "Ортогонализация Грама-Шмидта методом исключения Гаусса". Американский математический ежемесячник. 98 (6): 544–549. doi : 10.2307 / 2324877. JSTOR 2324877.
^Перселл, Юкихиро; и другие. (2011). «Расчеты из первых принципов электронных состояний кремниевой нанопроволоки со 100 000 атомов на компьютере K». SC '11 Труды Международной конференции по высокопроизводительным вычислениям, сетям, хранению данных и анализу 2011 г.: 1: 1--1: 11. doi : 10.1145 / 2063384.2063386.

Бау III, Давид; Трефетен, Ллойд Н. (1997), Численная линейная алгебра, Филадельфия: Общество промышленной и прикладной математики, ISBN 978-0-89871-361-9.
Голуб, Джин Х. ; Ван Лоан, Чарльз Ф. (1996), Matrix Computations (3-е изд.), Johns Hopkins, ISBN 978-0-8018-5414-9.
Greub, Вернер (1975), Линейная алгебра (4-е изд.), Springer.
Соливерез, CE; Gagliano, E. (1985), «Ортонормализация на плоскости: геометрический подход» (PDF), Mex. J. Phys., 31 (4): 743–758.

Внешние ссылки

Математический портал

, Энциклопедия математики, EMS Press, 2001 [ 1994]
Учебник по математике колледжа Харви Мадда по алгоритму Грэма-Шмидта
Самые ранние известные варианты использования некоторых слов математики: G В статье «Ортогонализация по Граму-Шмидту» содержится некоторая информация и ссылки на происхождение.
Демонстрации: процесс Грама Шмидта в плоскости и процесс Грама Шмидта в пространстве
Апплет ортогонализации Грама-Шмидта
NAG Ортогонализация по Граму – Шмидту n векторы подпрограммы порядка m
Доказательство: Раймонд Пуцио, Кинан Кидвелл. «Доказательство алгоритма ортогонализации Грама-Шмидта» (версия 8). PlanetMath.org.