Процес Грама — Шмідта
Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації, в якому за лінійно-незалежною системою будується ортогональна система така, що кожний вектор лінійно виражається через , тобто матриця переходу від до ― верхня трикутна матриця.
Можна пронормувати систему і зробити, щоб діагональні елементи матриці переходу були додатніми; ці умови однозначно визначають систему та матрицю переходу.
Процес Грама — Шмідта застосований до матриці з лінійно-незалежними стовпцями є QR розкладом матриці (розклад на ортогональну і верхню трикутну матрицю з додатніми діагональними елементами).
Алгоритм
Визначимо ортогонально-проекційний оператор
де <u, v> означає скалярний добуток векторів u and v. Цей оператор проектує вектор v ортогонально на вектор u.
Приймемо та запишемо рекурсивну формулу
Нормуючи вектори , отримаємо ортонормовану систему о.
Геометричний зміст процесу в тому, що вектор є проекцією вектора на перпендикуляр до лінійної оболонки векторів
Властивості
- Для кожного лінійні оболонки систем та збігаються.
- Добуток довжин дорівнює об'єму паралелепіпеда, побудованого на векторах системи , як на ребрах.
Числова стійкість
Коли процес втілено на комп'ютері, вектори часто не точно ортогональні, через похибки заокруглювання. Для процесу Грама — Шмідта у вигляді описаному вище (іноді згадуваному як «класичний Грам — Шмідт») ця втрата ортогональності особливо шкідлива; кажуть, що (класичний) процес Грама — Шмідта числово нестійкий.
Процес Грама — Шмідта можна стабілізувати завдяки маленькій зміні; цю версію іноді згадують як модифікований Грам — Шмідт. Цей підхід дає той самий результат що й оригінальна формула в точній арифметиці і вводить менші похибки в арифметиці скінченної точності. Замість того, щоб обчислювати вектор uk як
його обчислюють як
Кожен крок знаходить вектор ортогональний до . Таким чином, також ортогональний похибкам введеним під час обчислення .
Джерела
- Гантмахер Ф. Р. Теория матриц. — 2 изд. — Москва : Наука, 1967. — 576 с. — ISBN 5-9221-0524-8.(рос.)
- Гельфанд И. М. Лекции по линейной алгебре. — 5-е. — Москва : Наука, 1998. — 320 с. — ISBN 5791300158.(рос.)