Процес Грама — Шмідта

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Процес ортогоналізації Грама — Шмідта на трьох лінійно незалежних, неортогональних векторах

Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації, в якому за лінійно-незалежною системою будується ортогональна система така, що кожний вектор лінійно виражається через , тобто матриця переходу від до верхня трикутна матриця.

Можна пронормувати систему і зробити, щоб діагональні елементи матриці переходу були додатніми; ці умови однозначно визначають систему та матрицю переходу.

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

Алгоритм

[ред. | ред. код]
Перші 2 кроки ортогоналізації

Визначимо ортогонально-проєкційний оператор

де <u, v> означає скалярний добуток векторів u and v. Цей оператор проектує вектор v ортогонально на вектор u.

Приймемо та запишемо рекурсивну формулу

Нормуючи вектори , отримаємо ортонормовану систему о.

Геометричний зміст процесу в тому, що вектор є проєкцією вектора на перпендикуляр до лінійної оболонки векторів

Властивості

[ред. | ред. код]
  • Для кожного лінійні оболонки систем та збігаються.
  • Добуток довжин дорівнює об'єму паралелепіпеда, побудованого на векторах системи , як на ребрах.

Числова стійкість

[ред. | ред. код]

Коли процес втілено на комп'ютері, вектори часто не точно ортогональні, через похибки заокруглювання. Для процесу Грама — Шмідта у вигляді описаному вище (іноді згадуваному як «класичний Грам — Шмідт») ця втрата ортогональності особливо шкідлива; кажуть, що (класичний) процес Грама — Шмідта числово нестійкий.

Процес Грама — Шмідта можна стабілізувати завдяки маленькій зміні; цю версію іноді згадують як модифікований Грам — Шмідт. Цей підхід дає той самий результат що й оригінальна формула в точній арифметиці і вводить менші похибки в арифметиці скінченної точності. Замість того, щоб обчислювати вектор uk як

його обчислюють як

Кожен крок знаходить вектор ортогональний до . Таким чином, також ортогональний похибкам введеним під час обчислення .

Джерела

[ред. | ред. код]