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

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

Процес Грама - Шмідта — найвідоміший алгоритм ортогоналізації, в якому за лінійно-незалежною системою \mathbf{v}_1, \mathbf{v}_2,\dots,\mathbf{v}_k будується ортогональна система \mathbf{u}_1,\mathbf{u}_2,\dots,\mathbf{u}_k така, що кожний вектор \mathbf{u}_i лінійно виражається через \mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_i, тобто матриця переходу від \{\mathbf{v}_i\} до \{\mathbf{u}_i\}верхня трикутна матриця.

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

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

Алгоритм[ред.ред. код]

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

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

\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{u,v} \rangle \over \langle \mathbf{u,u} \rangle} \mathbf{u}
= {\mathbf{u u^{\top}} \over \langle \mathbf{u,u} \rangle} \cdot \mathbf{v}
= \mathbf{e e^{\top}} \cdot \mathbf{v}, \qquad \mathbf{e} = {\mathbf{u} \over \| \mathbf{u} \|},

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

Приймемо \mathbf{u}_1=\mathbf{v}_1 та запишемо рекурсивну формулу

\mathbf{u}_i = \mathbf{v}_i-\sum_{j=1}^{i-1}\frac{\langle \mathbf{v}_i,\mathbf{u}_j\rangle}{\langle \mathbf{u}_j,\mathbf{u}_j\rangle} \mathbf{u}_j
=\mathbf{v}_i- \bigg( \sum_{j=1}^{i-1} \mathbf{e}_j \mathbf{e}_j^{\top} \bigg) \mathbf{v}_i.

Нормуючи вектори \mathbf{u}_i, отримаємо ортонормовану систему о\{\mathbf{e}_i\}.

Геометричний зміст процесу в тому, що вектор \mathbf{u}_i є проекцією вектора \mathbf{v}_i на перпендикуляр до лінійної оболонки векторов \mathbf{v}_1,\dots,\mathbf{v}_{i-1}.

Властивості[ред.ред. код]

  • Для кожного \ i лінійні оболонки систем \mathbf{v}_1,\dots,\mathbf{v}_i та \mathbf{u}_1,\dots,\mathbf{u}_i збігаються.
  • Добуток довжин \mathbf{u}_i дорівнює об'єму паралелепіпеда, побудованого на векторах системи \{\mathbf{v}_i\}, як на ребрах.

Джерела[ред.ред. код]