Відкрити головне меню

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

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

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

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

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

АлгоритмРедагувати

 
Перші 2 кроки ортогоналізації

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

 

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

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

 

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

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

ВластивостіРедагувати

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

Числова стійкістьРедагувати

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

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

 

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

 

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

ДжерелаРедагувати