Модифицированный процесс Грама-Шмидта выполняется на трех линейно независимых, неортогональных векторах базиса для R 3 . Щелкните изображение, чтобы узнать подробности. Модификация объясняется в разделе «Числовая стабильность» этой статьи.
где обозначает скалярное произведение векторов u и v . Этот оператор проецирует вектор v ортогонально на линию, натянутую на вектор u . Если u = 0 , определим, т. е. отображение проекции - это нулевая карта, отправляющая каждый вектор в нулевой вектор.
Тогда процесс Грама – Шмидта работает следующим образом:
Последовательность у 1 , ..., у к является искомой системой ортогональных векторов, а нормализованные векторы х 1 , ..., е к образуют орто нормальный набор. Вычисление последовательности u 1 ,…, u k известно как ортогонализация Грама – Шмидта , а вычисление последовательности e 1 ,…, e k известно как ортонормировка Грама – Шмидта, поскольку векторы нормализованы.
Чтобы проверить, что эти формулы дают ортогональную последовательность, сначала вычислите подставляя приведенную выше формулу для u 2 : получаем ноль. Затем используйте это для вычисленияснова подставив формулу для u 3 : получаем ноль. Общее доказательство проводится по математической индукции .
Геометрически этот метод действует следующим образом: для вычисления u i он ортогонально проецирует v i на подпространство U, порожденное u 1 ,…, u i −1 , которое совпадает с подпространством, порожденным v 1 ,…, v i −1 . Вектор U я затем определяется как разница между V я и эта проекция, гарантированно ортогональна все векторы в подпространстве U .
Процесс Грама – Шмидта также применим к линейно независимой счетно бесконечной последовательности { v i } i . Результатом является ортогональная (или ортонормированная) последовательность { u i } i такая, что для натурального числа n : алгебраическая оболочка v 1 ,…, v n такая же, как у u 1 ,…, u n .
Если процесс Грама – Шмидта применяется к линейно зависимой последовательности, он выводит вектор 0 на i- м шаге, предполагая, что v i является линейной комбинацией v 1 ,…, v i −1 . Если должен быть создан ортонормированный базис, тогда алгоритм должен проверить наличие нулевых векторов в выходных данных и отбросить их, потому что никакое число, кратное нулевому вектору, не может иметь длину 1. Число векторов, выведенных алгоритмом, будет тогда размером пространства, занимаемого исходными входами.
Вариант процесса Грама – Шмидта с использованием трансфинитной рекурсии, примененной к (возможно, несчетной) бесконечной последовательности векторов. дает набор ортонормированных векторов с участием такой, что для любого , завершение промежутка такой же, как у . В частности, когда он применяется к (алгебраическому) базису гильбертова пространства (или, в более общем смысле, базису любого плотного подпространства), он дает (функционально-аналитический) ортонормированный базис. Отметим, что в общем случае часто строгое неравенство выполняется, даже если исходный набор был линейно независимым, а промежуток не обязательно должно быть подпространством в промежутке (скорее, это подпространство его завершения).
Позволять быть ортогональным (по отношению к данному внутреннему продукту). Тогда у нас есть
Далее параметризованная версия процесса Грама – Шмидта дает (сильную) деформационную ретракцию общей линейной группы на ортогональную группу .
Численная стабильность
Когда этот процесс реализован на компьютере, векторы часто не совсем ортогональны из-за ошибок округления . Для процесса Грама – Шмидта, описанного выше (иногда называемого «классическим Грамом – Шмидтом»), эта потеря ортогональности особенно велика; поэтому говорят, что (классический) процесс Грама – Шмидта численно нестабилен .
Процесс Грама – Шмидта можно стабилизировать с помощью небольшой модификации; эту версию иногда называют модифицированной версией Грама-Шмидта или MGS. Этот подход дает тот же результат, что и исходная формула в точной арифметике, и вносит меньшие ошибки в арифметику конечной точности. Вместо вычисления вектора u k как
он вычисляется как
Этот метод используется в предыдущей анимации, когда промежуточный вектор v ' 3 используется при ортогонализации синего вектора v 3 .
Алгоритм
Следующий алгоритм MATLAB реализует ортонормировку Грама – Шмидта для евклидовых векторов. Векторы v 1 ,…, v k (столбцы матрицы V, так что V(:,j)это j- й вектор) заменяются ортонормированными векторами (столбцами U), которые охватывают то же подпространство.
функция [U] = грамшмидт ( В )[ n , k ] = размер ( V );U = нули ( n , k );U (:, 1 ) = V (:, 1 ) / norm ( V (:, 1 ));для i = 2 : kU (:, я ) = V (:, я );для j = 1 : i - 1U (:, i ) = U (:, i ) - ( U (:, j ) '* U (:, i ) ) / ( norm ( U (:, j ))) ^ 2 * U (:, j );конецU (:, i ) = U (:, i ) / norm ( U (:, i ));конецконец
Стоимость этого алгоритма асимптотически составляет O ( nk 2 ) операций с плавающей запятой, где n - размерность векторов ( Голуб и Ван Лоан, 1996 , §5.2.8).
С помощью исключения Гаусса
Если строки { v 1 ,…, v k } записаны в виде матрицы, затем применяя метод исключения Гаусса к расширенной матрице создаст ортогонализированные векторы вместо . Однако матрицадолжен быть приведен к форме эшелона строк , используя только строковую операцию добавления скалярного кратного одной строки к другой. [2] Например, взяв как и выше, у нас есть
И сокращение этого до формы эшелона строк дает
Нормализованные векторы тогда
как в примере выше.
Формула детерминанта
Результат процесса Грама – Шмидта может быть выражен в нерекурсивной формуле с использованием определителей .
где D 0 = 1, а для J ≥ 1, D J представляет собой определитель Грама
Обратите внимание, что выражение для u k является «формальным» определителем, т.е. матрица содержит как скаляры, так и векторы; значение этого выражения определяется как результат расширения кофактора по строке векторов.
Детерминантная формула для Грама-Шмидта в вычислительном отношении медленнее (экспоненциально медленнее), чем рекурсивные алгоритмы, описанные выше; это в основном теоретический интерес.
Альтернативы
Другие алгоритмы ортогонализации используют преобразования Хаусхолдера или вращения Гивенса . Алгоритмы, использующие преобразования Хаусхолдера, более стабильны, чем стабилизированный процесс Грама – Шмидта. С другой стороны, процесс Грама – Шмидта дает-й ортогонализированный вектор после й итерации, тогда как ортогонализация с использованием отражений Хаусхолдера производит все векторы только в конце. Это делает применимым только процесс Грама – Шмидта для итерационных методов, таких как итерация Арнольди .
Еще одна альтернатива мотивирована использованием разложения Холецкого для обращения матрицы нормальных уравнений в линейных наименьших квадратах . Позволять- матрица ранга с полным столбцом , столбцы которой необходимо ортогонализировать. Матрицаявляется эрмитовым и положительно определенным , поэтому его можно записать какс использованием разложения Холецкого . Нижнетреугольная матрицасо строго положительными диагональными элементами обратима . Тогда столбцы матрицыявляются ортонормированными и охватывает то же подпространство в качестве столбцов исходной матрицы. Явное использование продуктаделает алгоритм нестабильным, особенно если число условий продукта велико. Тем не менее, этот алгоритм используется на практике и реализован в некоторых программных комплексах из-за его высокой эффективности и простоты.
В квантовой механике существует несколько схем ортогонализации, характеристики которых лучше подходят для определенных приложений, чем оригинальные схемы Грама – Шмидта. Тем не менее, он остается популярным и эффективным алгоритмом даже для самых крупных расчетов электронной структуры. [3]
Рекомендации
^ Чейни, Уорд; Кинкейд, Дэвид (2009). Линейная алгебра: теория и приложения . Садбери, Ма: Джонс и Бартлетт. С. 544, 558. ISBN 978-0-7637-5020-6.
^Пурселл, Лайл; Trimble, SY (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 . ISBN 9781450307710. S2CID 14316074 .
Источники
Бау III, Давид; Трефетен, Ллойд Н. (1997), Численная линейная алгебра , Филадельфия: Общество промышленной и прикладной математики, ISBN 978-0-89871-361-9.
Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), Matrix Computations (3-е изд.), Johns Hopkins, ISBN 978-0-8018-5414-9.
Соливерез, CE; Гальяно, Э. (1985), "Ортонормализация на плоскости: геометрический подход" (PDF) , Mex. J. Phys. , 31 (4): 743–758.
Внешние ссылки
Математический портал
"Ортогонализация" , Математическая энциклопедия , EMS Press , 2001 [1994]
Учебник по математике колледжа Харви Мадда по алгоритму Грама-Шмидта
Самые ранние известные варианты использования некоторых слов математики: G В статье «Ортогонализация по Граму-Шмидту» содержится некоторая информация и ссылки на происхождение метода.
Демонстрации: процесс Грама Шмидта на плоскости и процесс Грама Шмидта в пространстве
Апплет ортогонализации Грама-Шмидта
Ортогонализация NAG по Граму – Шмидту n векторов порядка m.